Practical Post-Quantum Signatures for Privacy

PhD Thesis of the University of Rennes 2024, publicly defended on June 18th, 2024.
Supervision: Pierre-Alain Fouque, Adeline Roux-Langlois, Olivier Sanders.
Jury:

• Damien Vergnaud, Sorbonne Université (president)
• Vadim Lyubashevsky, IBM Research Europe (reviewer)
• Olivier Blazy, École Polytechnique (reviewer)
• Alice Pellet–Mary, CNRS Bordeaux (examinator)
• Pierre-Alain Fouque, Université Rennes (director)
• Adeline Roux-Langlois, CNRS Caen (director)
• Olivier Sanders, Orange (supervisor)

Abstract

The transition to post-quantum cryptography has been an enormous effort for cryptographers over the last decade. In the meantime, cryptography for the protection of privacy, aiming at addressing the limitations inherent to basic cryptographic mechanisms in this domain, has also attracted a lot of attention. Nevertheless, despite the success of both individual branches, combining both aspects along with practicality turns out to be very challenging.

The goal of this thesis then lies in proposing new constructions for practical post-quantum privacy, and more generally advanced authentication mechanisms. To this end, we first focus on the lower level by studying one of the fundamental mathematical assumptions used in lattice-based cryptography: Module Learning With Errors. We show that it does not get significantly easier when stretching the secret and error distributions. We then turn to optimizing preimage samplers which are used in advanced signature designs. Far from being limited to this use case, we show that it also leads to efficient designs of regular signatures. Finally, we use some of the previous contributions to construct so-called signatures with efficient protocols, a versatile building block in countless advanced applications. We showcase it by giving the first post-quantum anonymous credentials, which we implement to demonstrate a theoretical and practical efficiency.