Supervision : Damien VERGNAUD

Zero-Knowledge Arguments from Secure Multiparty Computation

This thesis aims to study zero-knowledge arguments, a cryptographic primitive that allows proving a statement while yielding nothing beyond its truth. Specifically, we focus on a family of arguments whose construction is based on a secure multiparty computation. It is well known that, given any functionality f, there exists a secure multiparty protocol computing it with passive security. Let us take any one-way function f, and a secure multiparty protocol computing f. It has been shown seventeen years ago that we can build a zero-knowledge argument for the NP-problem of finding a pre-image of f. This construction was considered only theoretical until a few years ago, and this thesis contributes to the emergence of new techniques as well as efficient applications.
As an appetizer, we develop simple zero-knowledge protocols that significantly improve the state-of-the-art communication complexity for some well-known problems. Our first substantial contribution, with a desire to share small elements over large fields, is the introduction of a sharing over the integers that is securely embedded in our protocols with some artificial abortion. In line with our sharing over the integers, we propose a cryptographic string commitment scheme based on subset sum problems. Then, we present a proof construction employing conversion between additive and multiplicative secret sharings, leading to efficient proofs of linear and multiplicative relations. Finally, leaving aside protocols conception, we explore cryptography foundations with multi-prover zero-knowledge proofs, a framework for distributing the prover's computation of zero-knowledge proofs.

2022-2024 Publications

• 2024
  • J. Maire : “Zero-Knowledge Arguments from Secure Multiparty Computation”, thesis, phd defence 10/11/2024, supervision Vergnaud, Damien (2024)
  • J. Maire, D. Vergnaud : “Secure Multi-Party Linear Algebra with Perfect Correctness”, IACR Communications in Cryptology, (International Association for Cryptologic Research (IACR)) (2024)
• 2023
  • J. Maire, D. Vergnaud : “Efficient Zero-Knowledge Arguments and Digital Signatures via Sharing Conversion in the Head”, Computer Security - ESORICS 2023 - 28^th European Symposium on Research in Computer Security, The Hague, Netherlands, September 25-29, 2023, Proceedings, The Hague, Netherlands, (Springer Nature) (2023)
  • J. Maire, D. Vergnaud : “Commitments with Efficient Zero-Knowledge Arguments from Subset Sum Problems”, Computer Security - ESORICS 2023 - 28^th European Symposium on Research in Computer Security,, Lecture Notes in Computer Science, The Hague, Netherlands, (Springer Nature) (2023)
• 2022
  • Th. Feneuil, J. Maire, M. Rivain, D. Vergnaud : “Zero-Knowledge Protocols for the Subset Sum Problem from MPC-in-the-Head with Rejection”, Advances in Cryptology - Asiacrypt 2022, vol. 13792, Lecture Notes in Computer Science, Taipei, Taiwan, Province of China, pp. 371–402, (Springer) (2022)