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

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

Researchers

Research units

Abstract

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.

Details

Original languageEnglish
Title of host publicationProceedings of 2018 International Symposium on Information Theory and Its Applications, ISITA 2018
Publication statusPublished - 8 Mar 2019
MoE publication typeA4 Article in a conference publication
EventInternational Symposium on Information Theory and Its Applications - Singapore, Singapore
Duration: 28 Oct 201831 Oct 2018
Conference number: 15

Conference

ConferenceInternational Symposium on Information Theory and Its Applications
Abbreviated titleISITA
CountrySingapore
CitySingapore
Period28/10/201831/10/2018

ID: 34409945