Abstract
This paper demonstrates that Shamir’s scheme (“How to share a secret”, Communications of the ACM, vol. 22, no. 11, November 1979, 612–613) is not secure against cheating. A small modification to his scheme retains the security and efficiency of the original, is secure against cheating, and preserves the property that its security does not depend on any unproven assumptions such as the intractability of computing number-theoretic functions.
This material is based in part upon work supported by the National Science Foundation under grants DCR-8301212 and DCR-8352093.
Chapter PDF
Similar content being viewed by others
Bibliography
A. Aho, J. Hopcroft, and J. Ullman. The Design and Analysis of Computer Algorithms. Addison-Wesley, 1974.
B. Chor, S. Goldwasser, S. Micali, and B. Awerbuch. Verifiable secret sharing and achieving simultaneity in the presence of faults. Proc. 26th IEEE Symp. Found. Comp. Sci., pages 383–395, October 1985.
O. Goldreich, S. Micali, and A. Wigderson. How to prove all NP statements in zero-knowledge and a methodology of cryptographic protocol design. These Proceedings, 1987.
S. Goldwasser and J. Killian. Almost all primes can be quickly certified. Proc. 18th Annual ACM Symp. Theory Comput., pages 316–329, May 1986.
S. Goldwasser, S. Micali, and R. Rivest. A ‘paradoxical’ solution to the signature problem. Proc. 25th IEEE Symp. Found. Comp. Sci., pages 441–448, October 1984.
M. Rabin. Randomized Byzantine generals. Proc. 24th IEEE Symp. Found. Comp. Sci., pages 403–409, November 1983.
A. Shamir. How to share a secret. Comm. ACM, 22(11):612–613, November 1979.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1987 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Tompa, M., Woll, H. (1987). How to Share a Secret with Cheaters. In: Odlyzko, A.M. (eds) Advances in Cryptology — CRYPTO’ 86. CRYPTO 1986. Lecture Notes in Computer Science, vol 263. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-47721-7_20
Download citation
DOI: https://doi.org/10.1007/3-540-47721-7_20
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-18047-0
Online ISBN: 978-3-540-47721-1
eBook Packages: Springer Book Archive