Practical Lattice Basis Sampling Reduction
We propose a practical sampling reduction algorithm for lattice bases based on work by Schnorr as well as two even more effective generalizations. We report the empirical behaviour of these algorithms. We describe how Sampling Reduction allows to stage lattice attacks against the NTRU cryptosystem with smaller BKZ parameters than before and conclude that therefore the recommeded NTRU security parameters offer $\leq 74$ Bit security.
The Security and Efficiency of Micciancio's Cryptosystem
We report experiments on the security of the GGH-like cryptosystem proposed by Micciancio. Based on these experiments, we conclude that the system can be securely used only in lattice dimensions > 781. Further experiments on the efficiency of the system show that it requires key sizes of 1 MByte and more and that the key generation as well as the decryption take inacceptibly long. Therefore, Micciancio's cryptosystem seems currently far from being practical.
Digital signatures have become a key technology for making the Internet and other IT infrastructures secure. But in 1994 Peter Shor showed that quantum computers can break all digital signature schemes that are used today and in 2001 Chuang and his coworkers implemented Shor s algorithm for the first time on a 7-qubit NMR quantum computer. This paper studies the question: What kind of digital signature algorithms are still secure in the age of quantum computers?