Paper 2023/1452

Commitments with Efficient Zero-Knowledge Arguments from Subset Sum Problems

Jules Maire, Sorbonne University
Damien Vergnaud, Sorbonne University

We present a cryptographic string commitment scheme that is computationally hiding and binding based on (modular) subset sum problems. It is believed that these NP-complete problems provide post-quantum security contrary to the number theory assumptions currently used in cryptography. Using techniques recently introduced by Feneuil, Maire, Rivain and Vergnaud, this simple commitment scheme enables an efficient zero-knowledge proof of knowledge for committed values as well as proofs showing Boolean relations amongst the committed bits. In particular, one can prove that committed bits $m_0, m_1, ..., m_\ell$ satisfy $m_0 = C(m_1, ..., m_\ell)$ for any Boolean circuit $C$ (without revealing any information on those bits). The proof system achieves good communication and computational complexity since for a security parameter $\lambda$, the protocol's communication complexity is $\tilde{O}(|C| \lambda + \lambda^2)$ (compared to $\tilde{O}(|C| \lambda^2)$ for the best code-based protocol due to Jain, Krenn, Pietrzak and Tentes).

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Minor revision. ESORICS 2023
commitment schemezero-knowledge proof of knowledge
Contact author(s)
jules maire @ alumni epfl ch
damien vergnaud @ lip6 fr
2023-09-24: approved
2023-09-22: received
See all versions
Short URL
Creative Commons Attribution


      author = {Jules Maire and Damien Vergnaud},
      title = {Commitments with Efficient Zero-Knowledge Arguments from Subset Sum Problems},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1452},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.