Paper 2023/1452
Commitments with Efficient Zero-Knowledge Arguments from Subset Sum Problems
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)
- 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
-
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} }