4 papers
Predicting Module-Lattice Reduction
Léo Ducas, Lynn Engelberts, Paola de Perthuis
Is module-lattice reduction better than unstructured lattice reduction? This question was highlighted as 'Q8' in the Kyber NIST standardization submission (Avanzi et al., 2021), as…
An Improved Quantum Algorithm for 3-Tuple Lattice Sieving
Lynn Engelberts, Yanlin Chen, Amin Shiraz Gilani +3
The assumed hardness of the Shortest Vector Problem in high-dimensional lattices is one of the cornerstones of post-quantum cryptography. The fastest known heuristic attacks on SVP…
Wagner's Algorithm Provably Runs in Subexponential Time for SIS
Léo Ducas, Lynn Engelberts, Johanna Loyer
At CRYPTO 2015, Kirchner and Fouque claimed that a carefully tuned variant of the Blum-Kalai-Wasserman (BKW) algorithm (JACM 2003) should solve the Learning with Errors problem (LW…
Quantum Sieving for Code-Based Cryptanalysis and Its Limitations for ISD
Lynn Engelberts, Simona Etinski, Johanna Loyer
Sieving using near-neighbor search techniques is a well-known method in lattice-based cryptanalysis, yielding the current best runtime for the shortest vector problem in both the c…