VSS from Distributed ZK Proofs and Applications
Pages 405 - 440
Abstract
Non-Interactive Verifiable Secret Sharing (NI-VSS) is a technique for distributing a secret among a group of individuals in a verifiable manner, such that shareholders can verify the validity of their received share and only a specific number of them can access the secret. VSS is a fundamental tool in cryptography and distributed computing. In this paper, we present an extremely efficient NI-VSS scheme using Zero-Knowledge (ZK) proofs on secret shared data. While prior VSS schemes have implicitly used ZK proofs on secret shared data, we specifically use their formal definition recently provided by Boneh et al. in CRYPTO 2019. The proposed NI-VSS scheme uses a quantum random oracle and a quantum computationally hiding commitment scheme in a black-box manner, which ensures its ease of use, especially in post-quantum threshold protocols. Implementation results further solidify its practicality and superiority over current constructions. With the new VSS scheme, for parameter sets and (2048, 1023), a dealer can share a secret in less than 0.02 and 2.0 s, respectively, and shareholders can verify their shares in less than 0.4 and 5.0 ms. Compared to the well-established Pedersen VSS scheme, for the same parameter sets, at the cost of higher communication, the new scheme is respectively and faster in the sharing phase, and notably needs and less time in the verification. Leveraging the new NI-VSS scheme, we revisit several classic and PQ-secure threshold protocols and improve their efficiency. Our revisions led to more efficient versions of both the Pedersen DKG protocol and the GJKR threshold signature scheme. We show similar efficiency enhancements and improved resilience to malicious parties in isogeny-based DKG and threshold signature schemes. We think, due to its remarkable efficiency and ease of use, the new NI-VSS scheme can be a valuable tool for a wide range of threshold protocols.
References
[1]
Atapoor, S., Baghery, K., Cozzo, D., Pedersen, R.: CSI-SharK: CSI-FiSh with Sharing-friendly Keys. In: Simpson, L., Rezazadeh Baee, M.A. (eds.) Information Security and Privacy. ACISP 2023. LNCS, vol. 13915. Springer, Cham (2023).
[2]
Atapoor, S., Baghery, K., Cozzo, D., Pedersen, R.: Practical robust DKG protocols for CSIDH. In: Tibouchi, M., Wang, X., (eds.) Applied Cryptography and Network Security. ACNS 2023. LNCS, vol. 13906. Springer, Cham (2023).
[3]
Atapoor, S., Baghery, K., Cozzo, D., Pedersen, R.: VSS from distributed ZK proofs and applications. Cryptology ePrint Archive, Paper 2023/992 (2023). https://eprint.iacr.org/2023/992
[4]
Baghery K, Cozzo D, and Pedersen R Paterson MB An isogeny-based ID protocol using structured public keys Cryptography and Coding 2021 Cham Springer 179-197
[5]
Ben-Or, M., Goldwasser, S., Wigderson, A.: Completeness theorems for non-cryptographic fault-tolerant distributed computation (extended abstract). In: 20th Annual ACM Symposium on Theory of Computing, pp. 1–10, Chicago, IL, USA, 2–4 May 1988. ACM Press (1988)
[6]
Benhamouda, F., Lepoint, T., Loss, J., Orrù, M., Raykova, M.: On the (in)security of ROS. In: Canteaut, A., Standaert, F.-X. (eds.) Advances in Cryptology – EUROCRYPT 2021. EUROCRYPT 2021. LNCS, vol. 12696. Springer, Cham (2021).
[7]
Bernstein, D., De Feo, L., Leroux, A., Smith, B.: Faster computation of isogenies of large prime degree. arXiv preprint arXiv:2003.10118 (2020)
[8]
Beullens W, Disson L, Pedersen R, and Vercauteren F Cheon JH and Tillich J-P CSI-RAShi: distributed key generation for CSIDH Post-Quantum Cryptography 2021 Cham Springer 257-276
[9]
Beullens W, Kleinjung T, and Vercauteren F Galbraith SD and Moriai S CSI-FiSh: efficient isogeny based signatures through class group computations Advances in Cryptology – ASIACRYPT 2019 2019 Cham Springer 227-247
[10]
Bishnoi, A., Clark, P.L., Potukuchi, A., Schmitt, J.R.: On zeros of a polynomial in a finite grid. Combinat. Probab. Comput. 27(3), 310–333 (2018)
[11]
Boneh D, Boyle E, Corrigan-Gibbs H, Gilboa N, and Ishai Y Boldyreva A and Micciancio D Zero-knowledge proofs on secret-shared data via fully linear PCPs Advances in Cryptology – CRYPTO 2019 2019 Cham Springer 67-97
[12]
Bonnetain X and Schrottenloher A Canteaut A and Ishai Y Quantum security analysis of CSIDH Advances in Cryptology – EUROCRYPT 2020 2020 Cham Springer 493-522
[13]
Campos, F., Muth, P.: On actively secure fine-grained access structures from isogeny assumptions. In: Cheon, J.H., Johansson, T., (eds.) Post-Quantum Cryptography. PQCrypto 2022. LNCS, vol. 13512. Springer, Cham (2022).
[14]
Castryck W, Lange T, Martindale C, Panny L, and Renes J Peyrin T and Galbraith S CSIDH: an efficient post-quantum commutative group action Advances in Cryptology – ASIACRYPT 2018 2018 Cham Springer 395-427
[15]
Chor, B., Goldwasser, S., Micali, S., Awerbuch, B.: Verifiable secret sharing and achieving simultaneity in the presence of faults (extended abstract). In 26th Annual Symposium on Foundations of Computer Science, pp. 383–395. Portland, Oregon, 21–23 October 1985. IEEE Computer Society Press (1985)
[16]
Dalskov A, Lee E, and Soria-Vazquez E Moriai S and Wang H Circuit amortization friendly encodings and their application to statistically secure multiparty computation Advances in Cryptology – ASIACRYPT 2020 2020 Cham Springer 213-243
[17]
De Feo, L.: Mathematics of isogeny based cryptography. arXiv preprint arXiv:1711.04062 (2017)
[18]
Feo, L.D., et al.: SCALLOP: scaling the CSI-FiSh. In: Boldyreva, A., Kolesnikov, V. (eds.) Public-Key Cryptography – PKC 2023. PKC 2023. LNCS, vol. 13940. Springer, Cham (2023).
[19]
Don J, Fehr S, Majenz C, and Schaffner C Boldyreva A and Micciancio D Security of the Fiat-Shamir transformation in the quantum random-oracle model Advances in Cryptology – CRYPTO 2019 2019 Cham Springer 356-383
[20]
Feldman, P.: A practical scheme for non-interactive verifiable secret sharing. In: 28th Annual Symposium on Foundations of Computer Science, pp. 427–437. Los Angeles, CA, USA, 12–14 October 1987. IEEE Computer Society Press (1987)
[21]
Fiat A and Shamir A Odlyzko AM How to prove yourself: practical solutions to identification and signature problems Advances in Cryptology — CRYPTO’ 86 1987 Heidelberg Springer 186-194
[22]
Gennaro R, Jarecki S, Krawczyk H, and Rabin T Secure distributed key generation for discrete-log based cryptosystems J. Cryptol. 2007 20 1 51-83
[23]
Gennaro, R., Rabin, M.O., Rabin, T.: Simplified VSS and fast-track multiparty computations with applications to threshold cryptography. In: Coan, B.A., Afek, Y. (eds.) 17th ACM Symposium Annual on Principles of Distributed Computing, pp. 101–111. Puerto Vallarta, Mexico, 28 June - 2 July 1998. Association for Computing Machinery (1988)
[24]
Gentry, C., Halevi, S., Lyubashevsky, V.: Practical non-interactive publicly verifiable secret sharing with thousands of parties. In: Dunkelman, O., Dziembowski, S., (eds.) Advances in Cryptology – EUROCRYPT 2022. EUROCRYPT 2022. LNCS, vol. 13275. Springer, Cham (2022).
[25]
Groth, J.: Non-interactive distributed key generation and key resharing. Cryptology ePrint Archive, Report 2021/339 (2021). https://eprint.iacr.org/2021/339
[26]
Kitaev, A.Y.: Quantum measurements and the abelian stabilizer problem. Electron. Colloquium Comput. Complex. TR96-003, 22 (1996)
[27]
Komlo C and Goldberg I Dunkelman O, Jacobson, Jr. MJ, and O’Flynn C FROST: flexible round-optimized Schnorr threshold signatures Selected Areas in Cryptography 2021 Cham Springer 34-65
[28]
Pedersen TP Davies DW A threshold cryptosystem without a trusted party Advances in Cryptology — EUROCRYPT ’91 1991 Heidelberg Springer 522-526
[29]
Pedersen TP Feigenbaum J Non-interactive and information-theoretic secure verifiable secret sharing Advances in Cryptology — CRYPTO ’91 1992 Heidelberg Springer 129-140
[30]
Peikert C Canteaut A and Ishai Y He gives C-Sieves on the CSIDH Advances in Cryptology – EUROCRYPT 2020 2020 Cham Springer 463-492
[31]
Schnorr CP Brassard G Efficient identification and signatures for smart cards Advances in Cryptology — CRYPTO’ 89 Proceedings 1990 New York Springer 239-252
[32]
Schoenmakers B Wiener M A simple publicly verifiable secret sharing scheme and its application to electronic voting Advances in Cryptology — CRYPTO’ 99 1999 Heidelberg Springer 148-164
[33]
Shamir A How to share a secret Commun. ACM 1979 22 11 612-613
[34]
Shor, P.W.: Algorithms for quantum computation: discrete logarithms and factoring. In: 35th Annual Symposium on Foundations of Computer Science, pp. 124–134. Santa Fe, NM, USA, 20–22 November 1994. IEEE Computer Society Press (1994)
[35]
Silverman JH The Arithmetic of Elliptic Curves 2009 New York Springer
[36]
Tomescu, A., et al.: Towards scalable threshold cryptosystems. In: 2020 IEEE Symposium on Security and Privacy, pp. 877–893, San Francisco, CA, USA, 18–21 May 2020. IEEE Computer Society Press (2020)
[37]
Unruh D Fischlin M and Coron J-S Computationally binding quantum commitments Advances in Cryptology – EUROCRYPT 2016 2016 Heidelberg Springer 497-527
[38]
Unruh D Takagi T and Peyrin T Post-quantum security of Fiat-Shamir Advances in Cryptology – ASIACRYPT 2017 2017 Cham Springer 65-95
[39]
Vélu, J.: Isogénies entre courbes elliptiques. CR Acad. Sci. Paris, Séries A 273, 305–347 (1971)
[40]
Wagner D Yung M A generalized birthday problem Advances in Cryptology — CRYPTO 2002 2002 Heidelberg Springer 288-304
Recommendations
Communication efficient perfectly secure VSS and MPC in asynchronous networks with optimal resilience
AFRICACRYPT'10: Proceedings of the Third international conference on Cryptology in AfricaVerifiable Secret Sharing (VSS) is a fundamental primitive used in many distributed cryptographic tasks, such as Multiparty Computation (MPC) and Byzantine Agreement (BA). It is a two phase (sharing, reconstruction) protocol. The VSS and MPC protocols ...
VSS Made Simpler
Advances in Information and Computer SecurityAbstractVerifiable secret sharing (VSS) allows honest parties to ensure consistency of their shares even if a dealer and/or a subset of parties are corrupt. We focus on perfect VSS, i.e., those providing perfect privacy, correctness and commitment with ...
An asynchronous protocol for distributed computation of RSA inverses and its applications
PODC '03: Proceedings of the twenty-second annual symposium on Principles of distributed computingThis paper presents an efficient asynchronous protocol to compute RSA inverses with respect to a public RSA modulus N whose factorization is secret and shared among a group of parties. Given two numbers x and e, the protocol computes y such that ye≡x (...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
© International Association for Cryptologic Research 2023.
Publisher
Springer-Verlag
Berlin, Heidelberg
Publication History
Published: 18 December 2023
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 25 Nov 2024
Other Metrics
Citations
Cited By
View allView 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