Commitments with Efficient Zero-Knowledge Arguments from Subset Sum Problems

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