Lattices: Algorithms and Cryptography (LattAC)

The LattAC project is funded by the European Research Council, as ERC Starting Grant ERC-2013-StG-335086-LATTAC, from January 2014 to December 2018. It is 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

Former members

Publications

On the Ring-LWE and Polynomial-LWE problems.
Miruna Rosca, Damien Stehlé and Alexandre Wallet.
In the proceedings of EUROCRYPT 2018. © Springer, 2018.

pdf
Learning With Errors and Extrapolated Dihedral Cosets.
Zvika Brakerski, Elena Kirshanova, Damien Stehlé and Weiqiang Wen.
In the proceedings of PKC 2018. © Springer, 2018.

pdf
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.

pdf
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).

pdf
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.

pdf
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.

pdf
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.

pdf
Improved Algorithms for the Approximate k-List Problem in Euclidean Norm.
Gottfried Herold and Elena Kirshanova.
In the proceedings of PKC'17. © Springer, 2017.

pdf
Encryption Switching Protocols Revisited: Switching Modulo p.
Guilhem Castagnos, Laurent Imbert and Fabien Laguillaumie.
In the proceedings of CRYPTO'17. © Springer, 2017.

pdf
Middle-Product Learning With Errors. Miruna Roșca, Amin Sakzad, Damien Stehlé and Ron Steinfeld.
In the proceedings of CRYPTO'17. © Springer, 2017.

pdf
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.

pdf
Verifiable Message-Locked Encryption.
Sébastien Canard, Fabien Laguillaumie and Marie Paindavoine.
In the proceedings of CANS'16. © Springer, 2016.

pdf
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.

pdf
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.

pdf
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.

pdf
Tuple lattice sieving, Shi Bai, Thijs Laarhoven and Damien Stehlé.
ANTS'16. LMS Journal of Computation and Mathematics, 2016.

pdf
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.

pdf
Faster LLL-type reduction of lattice bases. Arnold Neumaier and Damien Stehlé.
In the proceedings of ISSAC'16. © ACM, 2016.

pdf
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.

pdf
Sanitization of FHE Ciphertexts. Léo Ducas and Damien Stehlé.
In the proceedings of EUROCRYPT'16. © Springer, 2016.

pdf
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.

pdf
Implementing candidate graded encoding schemes from ideal lattices.
Martin Albrecht, Catalin Cocis, Fabien Laguillaumie and Adeline Langlois.
In proceedings of ASIACRYPT'15. © Springer, 2015.

pdf
Fully Homomorphic Encryption over the Integers Revisited. Jung Hee Cheon and Damien Stehlé.
In the proceedings of EUROCRYPT'15. © Springer, 2015.

pdf
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)

pdf
Better Polynomials for GNFS.
Shi Bai, Cyril Bouvier, Alexander Kruppa and Paul Zimmermann.
Mathematics of Computation, 85 (2016), 861-873.

pdf
Linearly Homomorphic Encryption from DDH.
Guilhem Castagnos and Fabien Laguillaumie.
In proceedings of CT-RSA'15. © Springer, 2015.

pdf
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.

pdf
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.

pdf
LLL reducing with the most significant bits.
Saruchi, Ivan Morel, Damien Stehlé and Gilles Villard.
In proceedings of ISSAC'14. © ACM, 2014.

pdf
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.

pdf
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.

pdf
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.

pdf
GGHLite: More Efficient Multilinear Maps from Ideal Lattices.
Adeline Langlois, Damien Stehlé and Ron Steinfeld.
In the proceedings of EUROCRYPT'14. © Springer, 2014.

pdf
Worst-case to average-case reductions for module lattices.
Adeline Langlois and Damien Stehlé.
In Designs, Codes and Cryptography, 2014.

pdf