Paper 2024/286

Efficient Zero-Knowledge Arguments and Digital Signatures via Sharing Conversion in the Head

Jules Maire, Sorbonne University
Damien Vergnaud, Sorbonne University

We present a novel technique within the MPC-in-the-Head framework, aiming to design efficient zero-knowledge protocols and digital signature schemes. The technique allows for the simultaneous use of additive and multiplicative sharings of secret information, enabling efficient proofs of linear and multiplicative relations. The applications of our technique are manifold. It is first applied to construct zero-knowledge arguments of knowledge for Double Discrete Logarithms (DDLP). The resulting protocol achieves improved communication complexity without compromising efficiency. We also propose a new zero-knowledge argument of knowledge for the Permuted Kernel Problem. Eventually, we suggest a short (candidate) post-quantum digital signature scheme constructed from a new one-way function based on simple polynomials known as fewnomials. This scheme offers simplicity and ease of implementation. Finally, we present two additional results inspired by this work but using alternative approaches. We propose a zero-knowledge argument of knowledge of an RSA plaintext for a small public exponent that significantly improves the state-of-the-art communication complexity. We also detail a more efficient forward-backward construction for the DDLP.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Major revision. ESORICS 2023
zero-knowledge protocolsmulti-party computationDDLPRSA
Contact author(s)
jules maire @ alumni epfl ch
damien vergnaud @ lip6 fr
2024-02-23: approved
2024-02-20: received
See all versions
Short URL
Creative Commons Attribution


      author = {Jules Maire and Damien Vergnaud},
      title = {Efficient Zero-Knowledge Arguments and Digital Signatures via Sharing Conversion in the Head},
      howpublished = {Cryptology ePrint Archive, Paper 2024/286},
      year = {2024},
      doi = {10.1007/978-3-031-50594-2\_22},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.