Lower bounds of shortest vector lengths in random NTRU lattices

Jingguo Bi 1, 2 Qi Cheng 3
2 CRYPT - Cryptanalyse
LIAMA - Laboratoire Franco-Chinois d'Informatique, d'Automatique et de Mathématiques Appliquées, Inria Paris-Rocquencourt
Abstract : Finding the shortest vector of a lattice is one of the most important problems in computational lattice theory. For a random lattice, one can estimate the length of the shortest vector using the Gaussian heuristic. However, no rigorous proof can be provided for some classes of lattices, as the Gaussian heuristic may not hold for them. In this paper, we propose a general method to estimate lower bounds of the shortest vector lengths for random integral lattices in certain classes, which is based on the incompressibility method from the theory of Kolmogorov complexity. As an application, we can prove that for a random NTRU lattice, with an overwhelming probability, the ratio between the length of the shortest vector and the length of the target vector, which corresponds to the secret key, is at least a constant, independent of the rank of the lattice.
Type de document :
Article dans une revue
Theoretical Computer Science, Elsevier, 2014, 560 (2), pp.121-130. 〈10.1016/j.tcs.2014.10.011〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01110352
Contributeur : Phong Q. Nguyen <>
Soumis le : mercredi 28 janvier 2015 - 08:26:46
Dernière modification le : mercredi 10 octobre 2018 - 14:28:12

Lien texte intégral

Identifiants

Collections

Citation

Jingguo Bi, Qi Cheng. Lower bounds of shortest vector lengths in random NTRU lattices. Theoretical Computer Science, Elsevier, 2014, 560 (2), pp.121-130. 〈10.1016/j.tcs.2014.10.011〉. 〈hal-01110352〉

Partager

Métriques

Consultations de la notice

146