Lattices: Algorithms and Cryptography (LattAC)

The LattAC project was funded by the European Research Council, as ERC Starting Grant ERC-2013-StG-335086-LATTAC, from January 2014 to December 2018. It was hosted by ENS de Lyon.

Summary

Contemporary cryptography, with security relying on the factorisation and discrete logarithm problems, is ill-prepared for the future: It will collapse with the rise of quantum computers, its costly algorithms require growing resources, and it is utterly ill-fitted for the fast-developing trend of externalising computations to the cloud. A promising alternative to handle these concerns is lattice-based cryptography. In this framework, the security of the protocols is inherited from the conjectured hardness of problems on Euclidean lattices, i.e., the sets of all integer linear combinations of linearly independent real vectors. The LattAC project aims at studying all computational aspects of lattices, from algorithms for manipulating them to applications. The main objective is to enable the rise of lattice-based cryptography.

Members (at the end of the project)

Laurent Grémy (Research Engineer)
Gottfried Herold (Post-Doc)
Elena Kirshanova (Post-Doc)
Fabien Laguillaumie (University of Lyon professor)
Huyen Nguyen (PhD student)
Alice Pellet--Mary (PhD student)
Damien Stehlé (ENS de Lyon professor, principal investigator)
Alexandre Wallet (Post-Doc)

Former members

Shi Bai (Post-Doc, now assistant professor at FAU)
Adeline Langlois (PhD student, now CNRS researcher)
Benoît Libert (Post-Doc, now CNRS director of research)
Weiqiang Wen (PhD student, now post-doc at University of Rennes 1)

Publications

The General Sieve Kernel and New Records in Lattice Reduction. Martin R. Albrecht, Léo Ducas, Gottfried Herold, Elena Kirshanova, Eamonn W. Postlethwaite and Marc Stevens. In the proceedings of EUROCRYPT 2019. © Springer, 2019.
Approx-SVP in Ideal Lattices with Pre-processing. Alice Pellet-Mary, Guillaume Hanrot and Damien Stehlé. In the proceedings of EUROCRYPT 2019. © Springer, 2019.
Practical Fully Secure Unrestricted Inner Product Functional Encryption Modulo p. Guilhem Castagnos, Fabien Laguillaumie and Ida Tucker. In the proceedings of ASIACRYPT 2018. © Springer, 2018.
On the Statistical Leak of the GGH13 Multilinear Map and Some Variants. Léo Ducas and Alice Pellet-Mary. In the proceedings of ASIACRYPT 2018. © Springer, 2018.
Measuring, simulating and exploiting the head concavity phenomenon in BKZ. Shi Bai, Damien Stehlé and Weiqiang Wen. In the proceedings of ASIACRYPT 2018. © Springer, 2018.
Adaptively Secure Distributed PRFs from LWE. Benoît Libert, Damien Stehlé and Radu Titiu. In the proceedings of TCC 2018. © Springer, 2018.
Quantum Attacks Against Indistinguishablility Obfuscators Proved Secure in the Weak Multilinear Map Model. Alice Pellet-Mary. In the proceedings of CRYPTO 2018. © Springer, 2018.
Higher dimensional sieving for the number field sieve algorithms. Laurent Grémy. In the proceedings of ANTS 2018.
Computing an LLL-reduced basis of the orthogonal lattice. Jingwei Chen, Damien Stehlé and Gilles Villard. In the proceedings of ISSAC 2018. © ACM, 2018.
Improved Quantum Information Set Decoding. Elena Kirshanova. In the proceedings of PQCRYPTO 2018. © Springer, 2018.
On the Ring-LWE and Polynomial-LWE problems. Miruna Rosca, Damien Stehlé and Alexandre Wallet. In the proceedings of EUROCRYPT 2018. © Springer, 2018.
Learning With Errors and Extrapolated Dihedral Cosets. Zvika Brakerski, Elena Kirshanova, Damien Stehlé and Weiqiang Wen. In the proceedings of PKC 2018. © Springer, 2018.
Speed-ups and time–memory trade-offs for tuple lattice sieving. Gottfried Herold, Elena Kirshanova and Thijs Laarhoven. In the proceedings of PKC 2018. © Springer, 2018.
CRYSTALS -- Dilithium: Digital Signatures from Module Lattices . Léo Ducas, Tancrède Lepoint, Vadim Lyubashevsky, Peter Schwabe, Gregor Seiler and Damien Stehlé. CHES 2018 (IACR Trans. CHES).
CRYSTALS -- Kyber: a CCA-secure module-lattice-based KEM. Joppe Bos, Léo Ducas, Eike Kiltz, Tancrède Lepoint, Vadim Lyubashevsky, John M. Schanck, Peter Schwabe and Damien Stehlé. In the proceedings of Euro S&P 2018. © IEEE, 2018.
Efficient Public Trace and Revoke from Standard Assumptions. Shweta Agrawal, Sanjay Bhattacherjee, Duong Hieu Phan, Damien Stehlé and Shota Yamada. In the proceedings of CCS 2017. © ACM, 2017.
New Techniques for Structural Batch Verification in Bilinear Groups with Applications to Groth-Sahai Proofs. Gottfried Herold, Max Hoffmann, Michael Klooß and Andy Rupp. In the proceedings of CCS 2017. © ACM, 2017.
Improved Algorithms for the Approximate k-List Problem in Euclidean Norm. Gottfried Herold and Elena Kirshanova. In the proceedings of PKC'17. © Springer, 2017.
Encryption Switching Protocols Revisited: Switching Modulo p. Guilhem Castagnos, Laurent Imbert and Fabien Laguillaumie. In the proceedings of CRYPTO'17. © Springer, 2017.
Middle-Product Learning With Errors. Miruna Roșca, Amin Sakzad, Damien Stehlé and Ron Steinfeld. In the proceedings of CRYPTO'17. © Springer, 2017.
All-But-Many Lossy Trapdoor Functions and Selective Opening Chosen-Ciphertext Security from LWE. Benoît Libert, Amin Sakzad, Damien Stehlé and Ron Steinfeld. In the proceedings of CRYPTO'17. © Springer, 2017.
Verifiable Message-Locked Encryption. Sébastien Canard, Fabien Laguillaumie and Marie Paindavoine. In the proceedings of CANS'16. © Springer, 2016.
Privately Outsourcing Exponentiation to a Single Server: Cryptanalysis and Optimal Constructions. Céline Chevalier, Fabien Laguillaumie and Damien Vergnaud. In the proceedings of ESORICS'16. © Springer, 2016.
A subfield lattice attack on overstretched NTRU assumptions: Cryptanalysis of some FHE and Graded Encoding Schemes. Martin Albrecht, Shi Bai and Léo Ducas. In the proceedings of CRYPTO'16. © Springer, 2016.
Effects of Some Lattice Reductions on the Success Probability of the Zero-Forcing Decoder. Jinming Wen, Chao Tong and Shi Bai. IEEE communications letters, 2016.
Tuple lattice sieving, Shi Bai, Thijs Laarhoven and Damien Stehlé. ANTS'16. LMS Journal of Computation and Mathematics, 2016.
Improved Reduction from the Bounded Distance Decoding Problem to the Unique Shortest Vector Problem in Lattices. Shi Bai, Damien Stehlé and Weiqiang Wen. In the proceedings of ICALP'16. © Springer, 2016.
Faster LLL-type reduction of lattice bases. Arnold Neumaier and Damien Stehlé. In the proceedings of ISSAC'16. © ACM, 2016.
Fully Secure Functional Encryption for Inner Products from Standard Assumptions. Shweta Agrawal, Benoît Libert and Damien Stehlé. In the proceedings of CRYPTO'16. © Springer, 2016.
Sanitization of FHE Ciphertexts. Léo Ducas and Damien Stehlé. In the proceedings of EUROCRYPT'16. © Springer, 2016.
Improved security proofs in lattice-based cryptography: using the Rényi divergence rather than the statistical distance, with Shi Bai, Adeline Langlois, Tancrède Lepoint and Ron Steinfeld. In the proceedings of ASIACRYPT'15. © Springer, 2015. (Best paper award) Journal of Cryptology, 2018, with Amin Sakzad as an additional co-author.
Implementing candidate graded encoding schemes from ideal lattices. Martin Albrecht, Catalin Cocis, Fabien Laguillaumie and Adeline Langlois. In proceedings of ASIACRYPT'15. © Springer, 2015.
Fully Homomorphic Encryption over the Integers Revisited. Jung Hee Cheon and Damien Stehlé. In the proceedings of EUROCRYPT'15. © Springer, 2015.
Cryptanalysis of the Multilinear Map over the Integers. Jung Hee Cheon, Kyoohyung Han, Changmin Lee , Hansol Ryu and Damien Stehlé. In the proceedings of EUROCRYPT'15. © Springer, 2015.(Best paper award)
Better Polynomials for GNFS. Shi Bai, Cyril Bouvier, Alexander Kruppa and Paul Zimmermann. Mathematics of Computation, 85 (2016), 861-873.
Linearly Homomorphic Encryption from DDH. Guilhem Castagnos and Fabien Laguillaumie. In proceedings of CT-RSA'15. © Springer, 2015.
Concise Multi-Challenge CCA-Secure Encryption and Signatures with Almost Tight Security. Benoît Libert, Marc Joye, Moti Yung and Thomas Peters. In proceedings of ASIACRYPT'14. © Springer, 2014.
Hardness of k-LWE and Applications in Traitor Tracing. San Ling, Duong Hieu Phan, Damien Stehlé and Ron Steinfeld. In proceedings of CRYPTO'14. © Springer, 2014. Algorithmica, 2017.
LLL reducing with the most significant bits. Saruchi, Ivan Morel, Damien Stehlé and Gilles Villard. In proceedings of ISSAC'14. © ACM, 2014.
Born and Raised Distributively: Fully Distributed Non-Interactive Adaptively Secure Threshold Signatures with Short Shares. Benoît Libert, Marc Joye and Moti Yung. In proceedings of PODC'14. © ACM, 2014.
Chiffrement avancé à partir du problème Learning With Errors (in French). Fabien Laguillaumie, Adeline Langlois et Damien Stehlé. Chapitre de l'ouvrage "Informatique Mathématique, une photographie en 2014", Presses Universitaires de Perpignan.
Lattice-Based Group Signatures Scheme with Verifier-local Revocation. Adeline Langlois, San Ling, Khoa Nguyen and Huaxiong Wang. In the proceedings of PKC'14. © Springer, 2014.
GGHLite: More Efficient Multilinear Maps from Ideal Lattices. Adeline Langlois, Damien Stehlé and Ron Steinfeld. In the proceedings of EUROCRYPT'14. © Springer, 2014.
Worst-case to average-case reductions for module lattices. Adeline Langlois and Damien Stehlé. In Designs, Codes and Cryptography, 2014.