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 $$ for any Boolean circuit $$ (without revealing any information on those bits). The proof system achieves good communication and computational complexity since for a security parameter $$, the protocol's communication complexity is $$ (compared to $$ for the best code-based protocol due to Jain, Krenn, Pietrzak and Tentes).