On bounded distance decoding, unique shortest vectors, and the minimum distance problem.

*(English)*Zbl 1252.94084
Halevi, Shai (ed.), Advances in cryptology – CRYPTO 2009. 29th annual international cryptology conference, Santa Barbara, CA, USA, August 16–20, 2009. Proceedings. Berlin: Springer (ISBN 978-3-642-03355-1/pbk). Lecture Notes in Computer Science 5677, 577-594 (2009).

Summary: We prove the equivalence, up to a small polynomial approximation factor \(\sqrt{n/\log n}\), of the lattice problems uSVP (unique shortest vector problem), BDD (bounded distance decoding) and GapSVP (the decision version of the shortest vector problem). This resolves a long-standing open problem about the relationship between uSVP and the more standard GapSVP, as well the BDD problem commonly used in coding theory. The main cryptographic application of our work is the proof that the M. Ajtai and C. Dwork [“A public-key cryptosystem with worst-case/average-case equivalence”, in: Proceedings of the 29th annual ACM symposium on theory of computing, STOC ’97. New York, NY: ACM Press. 284–293 (1997)] and the O. Regev [J. ACM 51, No. 6, 899–942 (2004; Zbl 1125.94026)] cryptosystems, which were previously only known to be based on the hardness of uSVP, can be equivalently based on the hardness of worst-case GapSVP\({_{O({n^{2.5}})}}\) and GapSVP\({_{O(n^{2})}}\), respectively. Also, in the case of uSVP and BDD, our connection is very tight, establishing the equivalence (within a small constant approximation factor) between the two most central problems used in lattice based public key cryptography and coding theory.

For the entire collection see [Zbl 1173.94004].

For the entire collection see [Zbl 1173.94004].