Robust sharing of secrets when the dealer is honest or cheating

ABSTRACT

The problem of Verifiable Secret Sharing (VSS) is the following: A dealer, who may be honest or cheating, can share a secret s, among n ≥ 2t + 1 players, where t players at most are cheaters. The sharing process will cause the dealer to commit himself to a secret s. If the dealer is honest, then, during the sharing process, the set of dishonest players will have no information about s. When the secret is reconstructed, at a later time, all honest players will reconstruct s. The solution that is given is a constant round protocol, with polynomial time local computations and polynomial message size. The protocol assumes private communication lines between every two participants, and a broadcast channel. The protocol achieves the desired properties with an exponentially small probability of error.A new tool, called Information Checking, which provides authentication and is not based on any unproven assumptions, is introduced, and may have wide application elsewhere.For the case in which it is known that the dealer is honest, a simple constant round protocol is proposed, without assuming broadcast.A weak version of secret sharing is defined: Weak Secret Sharing (WSS). WSS has the same properties as VSS for the sharing process. But, during reconstruction, if the dealer is dishonest, then he might obstruct the reconstruction of s. A protocol for WSS is also introduced. This protocol has an exponentially small probability of error. WSS is an essential building block for VSS. For certain applications, the much simpler WSS protocol suffice.All protocols introduced in this paper are secure in the Information Theoretic sense.

REFERENCES

• 1: Donald Beaver, Multiparty protocols tolerating half faulty processors, Proceedings on Advances in cryptology, p.560-572, July 1989, Santa Barbara, California, United States
• 2: 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]
• 3: 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]
• 4: 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]
• 5: ~CHOR, B., GOLDWASSER, S., MiCALI, S., AND AWERBUCH, B. 1985. Verifiable secret sharing and ~achieving simultaneity in the presence of faults. In Proceedtngs of the 1985 Symposzum on ~Foundatiolzs of Computer Science. IEEE, New York, pp. 383-395.
• 6: ~DOLEV, D., DWORK, C., WAARTS, 0., AND YUNG, M. 1990. Perfectly secure message transmis- ~sion. In Proceedings of the 1990 Symposu~m on Foundations of Computer Science. IEEE, New ~York, pp. 36-45.
• 7: ~FELDMAN, P., 1988. Optimal algorithms for Byzantine agreement. Ph.D. dissertation, Dept. of ~Mathematics. MIT, Cambridge, Mass.
• 8: Paul Feldman , Silvio Micali, Optimal algorithms for Byzantine agreement, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.148-161, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62225]
• 9: ~GOt_DREICH, O., M~CALk S., AND W1GDERSON, A. 1986. Proofs that yield nothing but the validity ~of the assertion, and a methodology of cryptographic protocol design. In Proceedings of the 1986 ~Symposium on Foundations of Computer Scicnce. IEEE, New York, pp. 174 187.
• 10: ~KARLIN, A., AND YAO, A. 1986. Probabilities lower bounds for Byzantine agreement. Unpub- ~lished manuscript.
• 11: R. J. McEliece , D. V. Sarwate, On sharing secrets and Reed-Solomon codes, Communications of the ACM, v.24 n.9, p.583-584, Sept. 1981 [doi>10.1145/358746.358762]
• 12: 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]
• 13: ~RABIN, M. 1983. Randomized Byzantine generals. In Proceedings of the 1983 Symposium on ~Foundations of Computer Science. IEEE, New York, pp. 403-409.
• 14: ~RAmN, M. 1978. Digitalized signatures, foundations of secure computations (R. Demillo and ~R. Lipton, eds.). Academic Press, Orlando, Fla., pp. 155-165.
• 15: 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]
• 16: 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]
• 17: ~TOMPA. M. AND WELL, H. 1986. HOW to share a secret with cheaters. IBM Res. Rep. RC 11840 ~(Log #52910).

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Protocol verification

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Network problems

General Terms:
Algorithms, Security, Theory, Verification