On Sigma-Protocols and (Packed) Black-Box Secret Sharing Schemes
Pages 426 - 457
Abstract
-protocols are a widely utilized, relatively simple and well understood type of zero-knowledge proofs. However, the well known Schnorr -protocol for proving knowledge of discrete logarithm in a cyclic group of known prime order, and similar protocols working over this type of groups, are hard to generalize to dealing with other groups, in particular those of hidden order, due to the inability of the knowledge extractor to invert elements modulo the order.
In this paper, we introduce a universal construction of -protocols designed to prove knowledge of preimages of group homomorphisms for any abelian finite group. In order to do this, we first establish a general construction of a -protocol for -module homomorphism given only a linear secret sharing scheme over the ring, where zero knowledge and special soundness can be related to the privacy and reconstruction properties of the secret sharing scheme. Then, we introduce a new construction of 2-out-of-n packed black-box secret sharing scheme capable of sharing k elements of an arbitrary (abelian, finite) group where each share consists of group elements. From these two elements we obtain a generic “batch” -protocol for proving knowledge of k preimages of elements via the same group homomorphism, which communicates elements of the group to achieve knowledge error. For the case of class groups, we show that our -protocol improves in several aspects on existing proofs for knowledge of discrete logarithm and other related statements that have been used in a number of works.
Finally, we extend our constructions from group homomorphisms to the case of ZK-ready functions, introduced by Cramer and Damgård in Crypto 09, which in particular include the case of proofs of knowledge of plaintext (and randomness) for some linearly homomorphic encryption schemes such as Joye-Libert encryption. However, in the case of Joye-Libert, we show a better alternative, using Shamir secret sharing over Galois rings, which achieves knowledge soundness by communicating k ciphertexts to prove k statements.
References
[1]
Abspoel M, Cramer R, Damgård I, Escudero D, and Yuan C Hofheinz D and Rosen A Efficient information-theoretic secure multiparty computation over via galois rings TCC 2019, Part I 2019 Heidelberg Springer 471-501
[2]
Attema T, Cascudo I, Cramer R, Damgård I, and Escudero D Kiltz E and Vaikuntanathan V Vector commitments over rings and compressed -protocols TCC 2022, Part I 2022 Heidelberg Springer 173-202
[3]
Attema T and Cramer R Micciancio D and Ristenpart T Compressed -protocol theory and practical application to plug & play secure algorithmics CRYPTO 2020 2020 Heidelberg Springer 513-543
[4]
Ball, M., Çakan, A., Malkin, T.: Linear threshold secret-sharing with binary reconstruction. In: Tessaro, S. (ed.) 2nd Conference on Information-Theoretic Cryptography, ITC 2021, July 23-26, 2021, Virtual Conference, LIPIcs, vol. 199, pp. 12:1–12:22. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
[5]
Bartoli, C., Cascudo, I.: On sigma-protocols and (packed) black-box secret sharing schemes. Cryptology ePrint Archive, Paper 2023/1652 (2023). https://eprint.iacr.org/2023/1652
[6]
Bouvier C, Castagnos G, Imbert L, and Laguillaumie F I want to ride my BICYCL : BICYCL implements cryptography in class groups J. Cryptol. 2023 36 3 17
[7]
Braun L, Damgård I, and Orlandi C Handschuh H and Lysyanskaya A Secure multiparty computation from threshold encryption based on class groups Advances in Cryptology - CRYPTO 2023 2023 Cham Springer 613-645
[8]
Bünz, B., Bootle, J., Boneh, D., Poelstra, A., Wuille, P., Maxwell, G.: Bulletproofs: short proofs for confidential transactions and more. In: 2018 IEEE Symposium on Security and Privacy, pp. 315–334. IEEE Computer Society Press (2018)
[9]
Castagnos G, Catalano D, Laguillaumie F, Savasta F, and Tucker I Boldyreva A and Micciancio D Two-party ECDSA from hash proof systems and efficient instantiations CRYPTO 2019, Part III 2019 Heidelberg Springer 191-221
[10]
Castagnos G, Catalano D, Laguillaumie F, Savasta F, and Tucker I Kiayias A, Kohlweiss M, Wallden P, and Zikas V Bandwidth-efficient threshold EC-DSA PKC 2020, Part II 2020 Heidelberg Springer 266-296
[11]
Castagnos G and Laguillaumie F Nyberg K Linearly homomorphic encryption from Topics in Cryptology — CT-RSA 2015 2015 Cham Springer 487-505
[12]
Castagnos G, Laguillaumie F, and Tucker I Peyrin T and Galbraith S Practical fully secure unrestricted inner product functional encryption modulo p Advances in Cryptology – ASIACRYPT 2018 2018 Cham Springer 733-764
[13]
Castagnos G, Laguillaumie F, and Tucker I Agrawal S and Lin D Threshold linearly homomorphic encryption on ASIACRYPT 2022, Part II 2022 Heidelberg Springer 99-129
[14]
Catalano D, Di Raimondo M, Fiore D, and Giacomelli I Kiayias A, Kohlweiss M, Wallden P, and Zikas V Mona: fast maliciously secure two party computation on PKC 2020, Part II 2020 Heidelberg Springer 357-386
[15]
Cramer R and Damgård I Halevi S On the amortized complexity of zero-knowledge protocols CRYPTO 2009 2009 Heidelberg Springer 177-191
[16]
Cramer R, Damgård I, and Keller M On the amortized complexity of zero-knowledge protocols J. Cryptol. 2014 27 2 284-316
[17]
Cramer R and Fehr S Yung M Optimal black-box secret sharing over arbitrary Abelian groups CRYPTO 2002 2002 Heidelberg Springer 272-287
[18]
Cramer R, Fehr S, and Stam M Shoup V Black-box secret sharing from primitive sets in algebraic number fields CRYPTO 2005 2005 Heidelberg Springer 344-360
[19]
Cramer R and Xing C Canteaut A and Ishai Y Blackbox secret sharing revisited: a coding-theoretic approach with application to expansionless near-threshold schemes Advances in Cryptology – EUROCRYPT 2020 2020 Cham Springer 499-528
[20]
Das P, Jacobson MJ, and Scheidler R Carlet C, Guilley S, Nitaj A, and Souidi EM Improved efficiency of a linearly homomorphic cryptosystem Codes, Cryptology and Information Security 2019 Cham Springer 349-368
[21]
Desmedt Y and Frankel Y Brassard G Threshold cryptosystems Advances in Cryptology — CRYPTO’ 89 Proceedings 1990 New York Springer 307-315
[22]
Franklin, M.K., Yung, M.: Communication complexity of secure computation (extended abstract). In: 24th ACM STOC, pp. 699–710. ACM Press (1992)
[23]
Gennaro R, Leigh D, Sundaram R, and Yerazunis W Lee PJ Batching schnorr identification scheme with applications to privacy-preserving authorization and low-bandwidth communication devices Advances in Cryptology - ASIACRYPT 2004 2004 Heidelberg Springer 276-292
[24]
Guillou LC and Quisquater J-J Goldwasser S A “Paradoxical” Indentity-based signature scheme resulting from zero-knowledge Advances in Cryptology — CRYPTO’ 88 1990 New York Springer 216-231
[25]
Ishai Y, Kushilevitz E, Ostrovsky R, and Sahai A Zero-knowledge proofs from secure multiparty computation SIAM J. Comput. 2009 39 3 1121-1152
[26]
Joye M and Libert B Johansson T and Nguyen PQ Efficient cryptosystems from -th power residue symbols EUROCRYPT 2013 2013 Heidelberg Springer 76-92
[27]
Karchmer, M., Wigderson, A.: Characterizing non-deterministic circuit size. In: 25th ACM STOC, pp. 532–540. ACM Press (1993)
[28]
Karchmer, M., Wigderson, A.: On span programs. In: Proceedings of the Eight Annual Structure in Complexity Theory Conference, San Diego, CA, USA, May 18-21, 1993, pp. 102–111. IEEE Computer Society (1993)
[29]
Maurer UM Preneel B Unifying zero-knowledge proofs of knowledge AFRICACRYPT 2009 2009 Heidelberg Springer 272-286
[30]
Okamoto T and Uchiyama S Nyberg K A new public-key cryptosystem as secure as factoring Advances in Cryptology — EUROCRYPT’98 1998 Heidelberg Springer 308-318
[31]
Paillier P Stern J Public-key cryptosystems based on composite degree residuosity classes Advances in Cryptology — EUROCRYPT ’99 1999 Heidelberg Springer 223-238
[32]
Schnorr CP Brassard G Efficient identification and signatures for smart cards Advances in Cryptology — CRYPTO’ 89 Proceedings 1990 New York Springer 239-252
[33]
Xue, H.,et al.: Efficient multiplicative-to-additive function from Joye-Libert cryptosystem and its application to threshold ECDSA. Cryptology ePrint Archive, Paper 2023/1312 (2023). https://eprint.iacr.org/2023/1312. To appear in ACM CCS 23
[34]
Zhang M, Chen Y, Yao C, and Wang Z Guo J and Steinfeld R Sigma protocols from verifiable secret sharing and their applications Advances in Cryptology - ASIACRYPT 2023 2023 Singapore Springer 208-242
Recommendations
Black-Box Constructions of Protocols for Secure Computation
In this paper, we study the question of whether or not it is possible to construct protocols for general secure computation in the setting of malicious adversaries and no honest majority that use the underlying primitive (e.g., enhanced trapdoor ...
Sigma Protocols from Verifiable Secret Sharing and Their Applications
Advances in Cryptology – ASIACRYPT 2023AbstractSigma protocols are one of the most common and efficient zero-knowledge proofs (ZKPs). Over the decades, a large number of Sigma protocols are proposed, yet few works pay attention to the common design principal. In this work, we propose a generic ...
Evolving Ramp Secret-Sharing Schemes
Security and Cryptography for NetworksAbstractEvolving secret-sharing schemes, introduced by Komargodski, Naor, and Yogev (TCC 2016b), are secret-sharing schemes in which the dealer does not know the number of parties that will participate. The parties arrive one by one and when a party ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Apr 2024
468 pages
© International Association for Cryptologic Research 2024.
Publisher
Springer-Verlag
Berlin, Heidelberg
Publication History
Published: 15 April 2024
Author Tags
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 20 Nov 2024
Other Metrics
Citations
View Options
View options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in