Welcome to the resource topic for 2023/1452
Title:
Commitments with Efficient Zero-Knowledge Arguments from Subset Sum Problems
Authors: Jules Maire, Damien Vergnaud
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).
ePrint: https://eprint.iacr.org/2023/1452
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .