A novel lattice reduction algorithm

Abstract

The quantum threats have made the traditional number theoretic cryptography weak. Lattice based cryptographic constructions are now considered as an alternative of the number theoretic cryptography which resists the quantum threats. The cryptographic hardness of the lattice based constructions mainly lies on the difficulty of solving two problems, namely, shortest vector problem (SVP) and closest vector problem (CVP). Solving these problems become “somewhat” easier if the lattice basis is almost orthogonal. Given any basis, finding an almost orthogonal basis is termed as lattice basis reduction (or simply lattice reduction). The SVP has been shown to be reducible to the CVP but the other way is still an open problem. In this paper, we work towards proving the equivalence of the CVP and SVP and provide a history of the progress made in this direction. We do a brief review of the existing lattice reduction algorithms and present a new lattice basis reduction algorithm similar to the well-studied Korkine-Zolotareff (KZ) reduction which is used frequently for decoding lattices. The proposed algorithm is very simple — it calls the shortest vector oracle for n−1 times and outputs an almost orthogonal lattice basis with running time O(n3), n being the rank of the lattice. Copyright © 2018 by SCITEPRESS – Science and Technology Publications, Lda. All rights reserved