Summary
The 2018 International Symposium on Information Theory and Its Applications (ISITA2018)
2018
Session Number:Mo-PM-2-1
Session:
Number:Mo-PM-2-1.3
The Double-Plane Algorithm:A simple algorithm for the closest vector problem
Ferdinand Blomqvist, Marcus Greferath,
pp.193-197
Publication Date:2018/10/18
Online ISSN:2188-5079
DOI:10.34385/proc.55.Mo-PM-2-1.3
PDF download
Summary:
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.