The round complexity of verifiable secret sharing and secure multicast

ABSTRACT

The round complexity of interactive protocols is one of their most important complexity measures. In this work we study the exact round complexity of two basic secure computation tasks: Verifiable Secret Sharing (VSS) and Secure Multicast.VSS allows a dealer to share a secret among several players in a way that would later allow a unique reconstruction of the secret. It is a well-studied primitive, which is used as a building block in virtually every general protocol for secure multi-party computation. Secure multicast is perhaps the simplest non-trivial instance of a secure computation. It allows a dealer to securely distribute an identical message to all players in a prescribed subset M. Both types of protocols are parameterized by the number of players, n, and a security threshold, t, which bounds the total number of malicious players (possibly including the dealer).We focus on a standard setting of perfect information-theoretic security, where all players have access to secure point-to-point channels and a common broadcast medium. For both types of primitives we prove, using related techniques, tight tradeoffs between the round complexity and the achievable security threshold. Specifically, for the VSS problem we show:2-round VSS is possible iff n>4t, where the ``if'' direction is realized by an efficient protocol.3-round VSS is possible iff n>3t, where the ``if'' direction is realized by an inefficient protocol.4-round efficient VSS is possible if n>3t.For the secure multicast problem we show:2-round secure multicast is (efficiently) possible iff

REFERENCES

• 1: J. Bar-Ilan , D. Beaver, Non-cryptographic fault-tolerant computing in constant number of rounds of interaction, Proceedings of the eighth annual ACM Symposium on Principles of distributed computing, p.201-209, June 1989, Edmonton, Alberta, Canada [doi>10.1145/72981.72995]
• 2: Donald Beaver, Multiparty protocols tolerating half faulty processors, Proceedings on Advances in cryptology, p.560-572, July 1989, Santa Barbara, California, United States
• 3: D. Beaver. Minimal-Latency Secure Function Evaluation. In Eurocrypt '00 , pp. 335-350. LNCS No. 1807.
• 4: D. Beaver, J. Feigenbaum, J. Kilian, and P. Rogaway. Locally random reductions: Improvements and applications. Journal of Cryptology, 10(1):17-36, 1997.
• 5: D. Beaver and S. Haber. Cryptographic protocols provably secure against dynamic adversaries. In Eurocrypt '92, pp. 307-323, 1992. LNCS No. 658.
• 6: D. Beaver , S. Micali , P. Rogaway, The round complexity of secure protocols, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.503-513, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100287]
• 7: Michael Ben-Or , Shafi Goldwasser , Avi Wigderson, Completeness theorems for non-cryptographic fault-tolerant distributed computation, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.1-10, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62213]
• 8: Piotr Berman , Juan A. Garay, Fast consensus in networks of bounded degree, Distributed Computing, v.7 n.2, p.67-73, December 1993 [doi>10.1007/BF02280836]
• 9: Piotr Berman , Juan A. Garay , Kenneth J. Perry, Bit optimal distributed consensus, Computer science: research and applications, Plenum Press, New York, NY, 1992
• 10: G. R. Blakley. Safeguarding cryptographic keys. In Proc. AFIPS 1979 National Computer Conference, pp. 313-317.
• 11: Manuel Blum , Alfredo De Santis , Silvio Micali , Giuseppe Persiano, Noninteractive zero-knowledge, SIAM Journal on Computing, v.20 n.6, p.1084-1118, Dec. 1991 [doi>10.1137/0220068]
• 12: Christian Cachin , Jan Camenisch , Joe Kilian , Joy Müller, One-Round Secure Computation and Secure Autonomous Mobile Agents, Proceedings of the 27th International Colloquium on Automata, Languages and Programming, p.512-523, July 09-15, 2000
• 13: R. Canetti. Studies in Secure Multiparty Computation. PhD thesis, Weizmann Institute of Science, 1995.
• 14: R. Canetti. Security and composition of multiparty cryptographic protocols. Journal of Cryptology, 13(1):143-202, 2000.
• 15: Ran Canetti , Uri Feige , Oded Goldreich , Moni Naor, Adaptively secure multi-party computation, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.639-648, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.238015]
• 16: R. Canetti, G. Itkis, J. Garay, D. Micciancio, M. Naor, and B. Pinkas. Issues in Secure Multicast . In INFOCOM'99.
• 17: David Chaum , Claude Crépeau , Ivan Damgard, Multiparty unconditionally secure protocols, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.11-19, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62214]
• 18: B. Chor, S. Goldwasser, S. Micali, and B. Awerbuch. Veriffiable Secret Sharing and Achieving Simultaneity in the Presence of Faults. In Proceeding 26th Annual Symposium on the Foundations of Computer Science, pp. 383-395.
• 19: Ronald Cramer , Ivan Damgård , Stefan Dziembowski, On the complexity of verifiable secret sharing and multiparty computation, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.325-334, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335343]
• 20: R. Cramer, I. Damgard, S. Dziembowski, M. Hirt, and T. Rabin. Efficient multiparty computations with dishonest minority. InEurocrypt '99, pp. 311-326. LNCS No. 1592.
• 21: R. Cramer, I. Damgard, and U. Maurer. General Secure Multiparty Computation from any Linear Secret Sharing Scheme. In Eurocrypt '00 , pp. 316-334. LNCS No. 1807.
• 22: D. Dolev, C. Dwork, O. Waarts, and M. Yung. Perfectly Secure Message Transmission. In Proc. of 31st FOCS, pp. 36-45, 1990.
• 23: Cynthia Dwork, Strong verifiable secret sharing (extended abstract), Proceedings of the 4th international workshop on Distributed algorithms, p.213-227, June 1991, Bari, Italy
• 24: Cynthia Dwork, On Verification in Secret Sharing, Proceedings of the 11th Annual International Cryptology Conference on Advances in Cryptology, p.114-128, August 11-15, 1991
• 25: Uri Feige , Joe Killian , Moni Naor, A minimal model for secure computation (extended abstract), Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.554-563, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195408]
• 26: P. Feldman. A Practical Scheme for Non-Interactive Veriffiable Secret Sharing. In Proc. 28th FOCS, pp. 427-437.
• 27: Mattias Fitzi , Ueli Maurer, From partial consistency to global broadcast, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.494-503, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335363]
• 28: M. Franklin and R. Wright. Secure communication in minimal connectivity models. Journal of Cryptology, 13(1):9-30, 2000.
• 29: O. Goldreich. Secure multi-party computation (working draft). www.wisdom.weizmann.ac.il/.oded/pp.html, 2000.
• 30: O. Goldreich , S. Micali , A. Wigderson, How to play ANY mental game, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.218-229, January 1987, New York, New York, United States [doi>10.1145/28395.28420]
• 31: Oded Goldreich , Silvio Micali , Avi Wigderson, Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems, Journal of the ACM (JACM), v.38 n.3, p.690-728, July 1991 [doi>10.1145/116825.116852]
• 32: Yuval Ishai , Eyal Kushilevitz, Private Simultaneous Messages Protocols with Applications, Proceedings of the Fifth Israel Symposium on the Theory of Computing Systems (ISTCS '97), p.174, June 17-19, 1997
• 33: Y. Ishai , E. Kushilevitz, Randomizing polynomials: A new representation with applications to round-efficient secure computation, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.294, November 12-14, 2000
• 34: M. Ito, A. Saito, and T. Nishizeki. Secret sharing schemes realizing general access structures. In Proc. IEEE Globecom 87, pp. 99-102, 1987.
• 35: Leslie Lamport , Robert Shostak , Marshall Pease, The Byzantine Generals Problem, ACM Transactions on Programming Languages and Systems (TOPLAS), v.4 n.3, p.382-401, July 1982 [doi>10.1145/357172.357176]
• 36: Nancy A. Lynch, Distributed Algorithms, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1996
• 37: Silvio Micali , Phillip Rogaway, Secure Computation (Abstract), Proceedings of the 11th Annual International Cryptology Conference on Advances in Cryptology, p.392-404, August 11-15, 1991
• 38: M. Pease , R. Shostak , L. Lamport, Reaching Agreement in the Presence of Faults, Journal of the ACM (JACM), v.27 n.2, p.228-234, April 1980 [doi>10.1145/322186.322188]
• 39: Torben P. Pedersen, Non-Interactive and Information-Theoretic Secure Verifiable Secret Sharing, Proceedings of the 11th Annual International Cryptology Conference on Advances in Cryptology, p.129-140, August 11-15, 1991
• 40: Tal Rabin, Robust sharing of secrets when the dealer is honest or cheating, Journal of the ACM (JACM), v.41 n.6, p.1089-1109, Nov. 1994 [doi>10.1145/195613.195621]
• 41: T. Rabin , M. Ben-Or, Verifiable secret sharing and multiparty protocols with honest majority, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.73-85, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73014]
• 42: Tomas Sander , Adam Young , Moti Yung, Non-Interactive CryptoComputing For NC1, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.554, October 17-18, 1999
• 43: Adi Shamir, How to share a secret, Communications of the ACM, v.22 n.11, p.612-613, Nov. 1979 [doi>10.1145/359168.359176]
• 44: A. C-C. Yao. How to generate and exchange secrets. Proc. 27th FOCS, pp. 162-167, 1986.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.0 General
          Subjects: Security and protection (e.g., firewalls)

  K. Computing Milieux
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS

General Terms:
Design, Measurement, Performance, Reliability, Security, Standardization, Theory, Verification