Paper 2023/1452

Commitments with Efficient Zero-Knowledge Arguments from Subset Sum Problems

Jules Maire, Sorbonne University
Damien Vergnaud, Sorbonne University
Abstract

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).

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. Minor revision. ESORICS 2023
Keywords
commitment schemezero-knowledge proof of knowledge
Contact author(s)
jules maire @ alumni epfl ch
damien vergnaud @ lip6 fr
History
2023-09-24: approved
2023-09-22: received
See all versions
Short URL
https://ia.cr/2023/1452
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2023/1452,
      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},
      url = {https://eprint.iacr.org/2023/1452}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.