Abstract
The round complexity of interactive protocols is one of their most important complexity measures. In this work we prove that existing lower bounds for the round complexity of VSS can be circumvented by introducing a negligible probability of error in the reconstruction phase. Previous results show matching lower and upper bounds of three rounds for VSS, with n = 3t + 1, where the reconstruction of the secrets always succeeds, i.e. with probability 1. In contrast we show that with a negligible probability of error in the reconstruction phase:
-
1
There exists an efficient 2-round VSS protocol for n = 3t + 1. If we assume that the adversary is non-rushing then we can achieve a 1-round reconstruction phase.
-
1
There exists an efficient 1-round VSS for t = 1 and n > 3.
-
1
We prove that our results are optimal both in resilience and number of sharing rounds by showing:
-
1
There does not exist a 2-round WSS (and hence VSS) for n ≤ 3t.
-
1
There does not exist a 1-round VSS protocol for t ≥ 2 and n ≥ 4.
-
1
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Ben-Or, M., Goldwasser, S., Wigderson, A.: Completeness Theorems for Non-Cryptographic Fault-Tolerant Distributed Computation. In: STOC, pp. 1–10 (1988)
Chaum, D., Crpeau, C., Damgård, I.: Multiparty Unconditionally Secure Protocols. In: FOCS, pp. 11–19 (1988)
Chor, B., Goldwasser, S., Micali, S., Awerbuch, B.: Verifiable Secret Sharing and Achieving Simultaneity in the Presence of Faults. In: STOC, pp. 383–395 (1985)
Cramer, R., Damgård, I., Dziembowski, S.: On the Complexity of Verifiable Secret Sharing and Multiparty Computation. In: STOC, pp. 325–334 (2000)
Cramer, R., Damgård, I., Dziembowski, S., Hirt, M., Rabin, T.: Efficient Multiparty Computations Secure Against an Adaptive Adversary. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 311–326. Springer, Heidelberg (1999)
Cramer, R., Damgård, I., Maurer, U.M.: General Secure Multi-Party Computation from Any Linear Secret-Sharing Scheme. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, pp. 316–334. Springer, Heidelberg (2000)
Dolev, D., Dwork, C., Waarts, O., Yung, M.: Perfectly Secure Message Transmission. JACM 40(1), 17–47 (1993)
Dwork, C.: Strong Verifiable Secret Sharing. In: van Leeuwen, J., Santoro, N. (eds.) WDAG 1990. LNCS, vol. 486, pp. 213–227. Springer, Heidelberg (1990)
Feldman, P.: A Practical Scheme for Non-Interactive Verifiable Secret Sharing. In: FOCS, pp. 427–437 (1987)
Fitzi, M., Garay, J., Gollakota, S., Pandu Rangan, C., Srinathan, K.: Round-Optimal and Efficient Verifiable Secret Sharing. In: Halevi, S., Rabin, T. (eds.) TCC 2006. LNCS, vol. 3876, pp. 329–342. Springer, Heidelberg (2006)
Gennaro, R., Ishai, Y., Kushilevitz, E., Rabin, T.: The Round Complexity of Verifiable Secret Sharing and Secure Multicast. In: STOC, pp. 580–589 (2001)
Golderich, O., Micali, S., Wigderson, A.: How to Play a Mental Game– a Completeness Theorem for Protocols with Honest Majority. In: STOC 1987, pp. 218–229 (1987)
Goldreich, O.: Secure Multiparty Computation (2007), http://www.wisdom.weizman.ac.il/~oded/pp.html
J. Katz, C. Koo, and R. Kumaresan. Improving the Round Complexity of VSS in Point-to-Point Networks. Cryptology ePrint 2007/358; In: Aceto, L., Damgård, I., Goldberg, L.A., Halldórsson, M.M., Ingólfsdóttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part II. LNCS, vol. 5126, pp. 499–510. Springer, Heidelberg (2008)
Patra, A., Choudhary, A., Rabin, T., Pandu Rangan, C.: The Round Complexity of Verifiable Secret Sharing Revisited. Cryptology ePrint 2008/172
Pedersen, T.P.: Non-Interactive and Information-Theoretic Secure Verifiable Secret Sharing. In: Feigenbaum, J. (ed.) CRYPTO 1991. LNCS, vol. 576, pp. 129–140. Springer, Heidelberg (1992)
Rabin, T.: Robust Sharing of Secrets When the Dealer is Honest or Cheating. J. ACM 41(6), 1089–1109 (1994)
Rabin, T., Ben-Or, M.: Verifiable Secret Sharing and Multiparty Protocols with Honest Majority. In: STOC, pp. 73–85 (1989)
Shamir, A.: How to Share a Secret. Comm. of the ACM 22(11), 612–613 (1979)
Tompa, M., Woll, H.: How to Share a Secret with Cheaters. In: Odlyzko, A.M. (ed.) CRYPTO 1986. LNCS, vol. 263, pp. 261–265. Springer, Heidelberg (1986)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Patra, A., Choudhary, A., Rabin, T., Rangan, C.P. (2009). The Round Complexity of Verifiable Secret Sharing Revisited. In: Halevi, S. (eds) Advances in Cryptology - CRYPTO 2009. CRYPTO 2009. Lecture Notes in Computer Science, vol 5677. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-03356-8_29
Download citation
DOI: https://doi.org/10.1007/978-3-642-03356-8_29
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-03355-1
Online ISBN: 978-3-642-03356-8
eBook Packages: Computer ScienceComputer Science (R0)