Predicting lattice reduction. (English) Zbl 1149.94314

Smart, Nigel (ed.), Advances in cryptology – EUROCRYPT 2008. 27th annual international conference on the theory and applications of cryptographic techniques, Istanbul, Turkey, April 13–17, 2008. Proceedings. Berlin: Springer (ISBN 978-3-540-78966-6/pbk). Lecture Notes in Computer Science 4965, 31-51 (2008).
Summary: Despite their popularity, lattice reduction algorithms remain mysterious cryptanalytical tools. Though it has been widely reported that they behave better than their proved worst-case theoretical bounds, no precise assessment has ever been given. Such an assessment would be very helpful to predict the behaviour of lattice-based attacks, as well as to select keysizes for lattice-based cryptosystems. The goal of this paper is to provide such an assessment, based on extensive experiments performed with the NTL library. The experiments suggest several conjectures on the worst case and the actual behaviour of lattice reduction algorithms. We believe the assessment might also help to design new reduction algorithms overcoming the limitations of current algorithms.
For the entire collection see [Zbl 1133.94008].


94A60 Cryptography


Full Text: DOI