PhD Defense

• Title: Post-Quantum Signatures from Secure Multiparty Computation
• When: Monday 23rd October 2023
• Where: Sorbonne University, Paris, France
• Manuscript: available here
• Slides: available here
• Distinction: Finalist (accessit) for the thesis award of GDR Sécurité Informatique (see website)

• Alain Couvreur, INRIA Saclay (reviewer)
• Geoffroy Couteau, IRIF (examiner)
• Tanja Lange, Technische Universiteit Eindhoven (examiner)
• Emmanuela Orsini, Bocconi University (reviewer)
• Nicolas Sendrier, INRIA Paris (examiner)
• Greg Zaverucha, Microsoft (guest)

• Jean Claude Bajard, Sorbonne University (director)
• Antoine Joux, Saarland University (co-director)
• Matthieu Rivain, CryptoExperts (co-supervisor)

The ongoing effort to build a quantum computer urges the cryptography community to develop new secure cryptosystems based on quantum-hard cryptographic problems. In this thesis, we focus on the design of signature schemes built from zero-knowledge proofs of knowledge. More precisely, we focus on the MPC-in-the-Head paradigm which provides a generic way to build zero-knowledge proofs using techniques from secure multiparty computation.

We propose several new signature schemes using the MPC-in-the-Head framework. Most of these schemes are competitive with the existing schemes in the post-quantum litterature. They have signature sizes between 5 KB and 20 KB for 128-bit security, and have very small public keys (less than 200 B). Their security relies on a large scope of hard problems. Some of them are relying on code-based assumptions, such as the hardness to solve the syndrome decoding problem for random linear codes. Others rely on the multivariate quadratic problem, the subset sum problem, and the MinRank problem.

We also develop two new MPC-in-the-Head techniques. The first one aims to efficiently address a context of small secret values over large modulus. The second one consists in a new way of transforming an MPC protocol into a zero-knowledge proof. This new transformation provides new trade-offs in terms of communication costs vs running times. In particular, it enables us to achieve small verification times.