The Double-Plane Algorithm: A simple algorithm for the closest vector problem

Ferdinand Blomqvist, Marcus Greferath

Tutkimustuotos: Artikkeli kirjassa/konferenssijulkaisussaConference contributionScientificvertaisarvioitu

1 Sitaatiot (Scopus)

Abstrakti

We present a new algorithm for solving the closest vector problem. The algorithm is called the double-plane algorithm and it is an extension of Babai's nearest plane algorithm. The algorithm is an approximative algorithm, and the performance of the algorithm depends on the quality of the lattice basis. However, given a high quality basis, the algorithm achieves correctness for lattices of sufficiently low rank, and very low error-rates when correctness can no longer be achieved. The computational complexity of the double-plane algorithm is upper bounded by that of sphere decoding using the Schnorr-Euchner enumeration strategy, and the higher the rank of the lattice, the larger the gap between the complexities of these decoding algorithms.

AlkuperäiskieliEnglanti
OtsikkoProceedings of 2018 International Symposium on Information Theory and Its Applications, ISITA 2018
KustantajaIEEE
Sivut193-197
Sivumäärä5
ISBN (elektroninen)9784885523182
DOI - pysyväislinkit
TilaJulkaistu - 8 maalisk. 2019
OKM-julkaisutyyppiA4 Artikkeli konferenssijulkaisuussa
TapahtumaInternational Symposium on Information Theory and Its Applications - Singapore, Singapore
Kesto: 28 lokak. 201831 lokak. 2018
Konferenssinumero: 15

Conference

ConferenceInternational Symposium on Information Theory and Its Applications
LyhennettäISITA
Maa/AlueSingapore
KaupunkiSingapore
Ajanjakso28/10/201831/10/2018

Sormenjälki

Sukella tutkimusaiheisiin 'The Double-Plane Algorithm: A simple algorithm for the closest vector problem'. Ne muodostavat yhdessä ainutlaatuisen sormenjäljen.

Siteeraa tätä