Tal Rabin
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.
- ~BEAVER, D. 1989. Multiparty protocols tolerating half faulty processors. In Proceedings of ~Clypto89. pp. 560-572. Google Scholar
- ~BEAVER, D., M1CALI. S., AND ROGAWAY, P. 1990, The round complexity of secure protocols. In ~Proceedings of the ACM 22nd Symposium on the Theory of Comt;uting (Baltimore, Md., May ~12 14). ACM, New York, pp. 503-512. Google Scholar
- ~BEN-OR, M., GOLDWASSER, S., AND WIGDERSON, A. 1988. Completeness theorems for noncrypto- ~graphic fault-tolerant distributed computation. In Proceedings fo the ACM 20th Symposium on ~ the Theory of Computing (Chicago, IlL, May 2-4). ACM, New York, pp. 1-10. Google Scholar
- ~CHAUM, D., CREPEAU, C., AND DAMGARD, I. 1988, Multiparty unconditionally secure protocols. ~In Proceedings of &e 20th A CM Symposium on the 77~eory of Computing (Chicago, IlL, May 2-4). ~ACM, New York, pp. 11-19. Google Scholar
- ~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.Google Scholar
- ~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.Google Scholar
- ~FELDMAN, P., 1988. Optimal algorithms for Byzantine agreement. Ph.D. dissertation, Dept. of ~Mathematics. MIT, Cambridge, Mass.Google Scholar
- ~FELDMAN, P., AND MICALI, S. 1988. Optimal algorithms for Byzantine agreement. In Proceedings ~of the 20th $3,mposztnn otz Theory of Computing (Chicago, Ill., May 2-4). ACM, New York, pp. ~148-161. Google Scholar
- ~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.Google Scholar
- ~KARLIN, A., AND YAO, A. 1986. Probabilities lower bounds for Byzantine agreement. Unpub- ~lished manuscript.Google Scholar
- ~CELIECE, R. J., AND SARWATE. D. V. 1981. On sharing secrets and Reed-Solomon codes. ~Commun. ACM 24, 9 (Sept.), 583-584. Google Scholar
- ~PEASE, M., SHOSTAK, R., AND LAMPORT, L. 1980. Reaching agreement in the presence of faults. ~J. ACM 27, 2 (Apr.), 228 234. Google Scholar
- ~RABIN, M. 1983. Randomized Byzantine generals. In Proceedings of the 1983 Symposium on ~Foundations of Computer Science. IEEE, New York, pp. 403-409.Google Scholar
- ~RAmN, M. 1978. Digitalized signatures, foundations of secure computations (R. Demillo and ~R. Lipton, eds.). Academic Press, Orlando, Fla., pp. 155-165.Google Scholar
- ~RAmN, T., AND BEN-OR, M. 1989. Verifiable secret sharing and multiparty protocols with honest ~majority. In Proceedings of the 21st ACM &,mposiz,n on the TheeO, of Computing (Seattle Wash., ~May 15-17). ACM, New York, pp. 73-85. Google Scholar
- SHAMm, A. 1979. How to share a secret. CommutL ACM 22, 11 (Nov.), 612-613. Google Scholar
- ~TOMPA. M. AND WELL, H. 1986. HOW to share a secret with cheaters. IBM Res. Rep. RC 11840 ~(Log #52910).Google Scholar
Index Terms
- Robust sharing of secrets when the dealer is honest or cheating
Recommendations
Detecting Dealer Cheating in Secret Sharing Systems
COMPSAC '00: 24th International Computer Software and Applications ConferenceThe concept of secret sharing can be used in a wide range of business application. A secret sharing system can implement the policies of secret sharing, and control the distribution of the secrets to the participants under the secret sharing policies. ...
Cheating Detectable Ramp Secret Sharing with Optimal Cheating Resiliency
Information Systems SecurityAbstractA (k, L, n) ramp secret sharing scheme allows a dealer to share a secret vector with a lesser share size compared to threshold secret sharing schemes. In this work, we formalize the definition of cheating in ramp secret sharing schemes and propose ...
Visual secret sharing with cheating prevention revisited
Visual secret sharing (VSS) is a variant form of secret sharing, and is efficient since secret decoding only depends on the human vision system. However, cheating in VSS, first showed by Horng et al., is a significant issue like a limelight. Since then, ...
Comments