Paper 2022/223
ZeroKnowledge Protocols for the Subset Sum Problem from MPCintheHead with Rejection
Abstract
We propose zeroknowledge arguments for the modular subset sum problem. Given a set of integers, this problem asks whether a subset adds up to a given integer $t$ modulo a given integer $q$. This NPcomplete problem is considered since the 1980s as an interesting alternative in cryptography to hardness assumptions based on number theory and it is in particular believed to provide postquantum security. Previous combinatorial approaches, notably one due to Shamir, yield arguments with cubic communication complexity (in the security parameter). More recent methods, based on the MPCinthehead technique, also produce arguments with cubic communication complexity. We improve this approach by using a secretsharing over small integers (rather than modulo $q$) to reduce the size of the arguments and remove the prime modulus restriction. Since this sharing may reveal information on the secret subset, we introduce the idea of rejection to the MPCinthehead paradigm. Special care has to be taken to balance completeness and soundness and preserve zeroknowledge of our arguments. We combine this idea with two techniques to prove that the secret vector (which selects the subset) is well made of binary coordinates. Our new techniques have the significant advantage to result in arguments of size independent of the modulus $q$. Our new protocols for the subset sum problem achieve an asymptotic improvement by producing arguments of quadratic size (against cubic size for previous proposals). This improvement is also practical: for a 256bit modulus $q$, the best variant of our protocols yields 13KB arguments while previous proposals gave 1180KB arguments, for the best general protocol, and 122KB, for the best protocol restricted to prime modulus. Our techniques can also be applied to vectorial variants of the subset sum problem and in particular the inhomogeneous short integer solution (ISIS) problem for which they provide an efficient alternative to stateoftheart protocols when the underlying ring is not small and NTTfriendly. We also show the application of our protocol to build efficient zeroknowledge arguments of plaintext and/or key knowledge in the context of fullyhomomorphic encryption. When applied to the TFHE scheme, the obtained arguments are more than 20 times smaller than those obtained with previous protocols. Eventually, we use our technique to construct an efficient digital signature scheme based on a pseudorandom function due to BonehHaleviHowgraveGraham.
Note: This version presents a new digital signature scheme based on the pseudorandom function due to BonehHaleviHowgraveGraham.
Metadata
 Available format(s)
 Category
 Cryptographic protocols
 Publication info
 A major revision of an IACR publication in ASIACRYPT 2022
 Keywords
 zeroknowledge subset sum postquantum cryptography
 Contact author(s)
 damien vergnaud @ lip6 fr
 History
 20221123: revised
 20220225: received
 See all versions
 Short URL
 https://ia.cr/2022/223
 License

CC BY
BibTeX
@misc{cryptoeprint:2022/223, author = {Thibauld Feneuil and Jules Maire and Matthieu Rivain and Damien Vergnaud}, title = {ZeroKnowledge Protocols for the Subset Sum Problem from MPCintheHead with Rejection}, howpublished = {Cryptology ePrint Archive, Paper 2022/223}, year = {2022}, note = {\url{https://eprint.iacr.org/2022/223}}, url = {https://eprint.iacr.org/2022/223} }