Lattice Enumeration Using Extreme Pruning

By Nicolas Gama, Phong Q. Nguyen, Oded Regev. International Conference on the Theory and Application of Cryptographic Techniques, 2010

313 citations recorded by the source corpus.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Frodo: Take off the Ring! Practical, Quantum-Secure Key Exchange from LWE (2016, background): “This is due to the fact that the numerically optimized pruned enumeration strategy does not yield a closed formula [30, 21].”
BKZ 2.0: Better Lattice Security Estimates (2011, methodology): “The main modification is the incorporation of the sound pruning technique developed by Gama, Nguyen and Regev [10] at EUROCRYPT ’10.”
Better Key Sizes (and Attacks) for LWE-Based Encryption (2011, methodology): “Using least-square regression, the best linear fit to our data for tBKZ(δ ): = lg(TBKZ(δ)), the log runtime (in seconds, on our machine) of BKZ as a function of δ ,i stBKZ(δ )=1 .806/ lg(δ) − 91. Since our experiments were limited by resources and available time, and we expect to see further improve”
Post-quantum Key Exchange - A New Hope (2016, methodology): “Typical implementations [20, 24, 35] use an enumeration algorithm as this SVP oracle, yet this algorithm runs in super-exponential time.”