Abstract
This paper demonstrates that Shamir's scheme [10] is not secure against certain forms of cheating. A small modification to his scheme retains the security and efficiency of the original, is secure against these forms of cheating, and preserves the property that its security does not depend on any unproven assumptions such as the intractability of computing number-theoretic functions.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
L. M. Adleman and M.-D. A. Huang, Recognizing primes in random polynomial time,Proc. 19th Annual ACM Symp. Theory Comput., pp. 462–469, May 1987.
A. V. Aho, J. E. Hopcroft, and J. D. Ullman,The Design and Analysis of Computer Algorithms, Addison-Wesley, Reading, MA, 1974.
J. C. Benaloh, Secret sharing homomorphisms: keeping shares of a secret secret,Advances in Cryptology—CRYPTO '86, pp. 251–260, Lecture Notes in Computer Science, vol. 263, Springer-Verlag, Berlin, 1987.
B. Chor, S. Goldwasser, S. Micali, and B. Awerbuch, Verifiable secret sharing and achieving simultaneity in the presence of faults,Proc. 26th Symp. Found. Comp. Sci., pp. 383–395, October 1985.
P. Feldman, A practical scheme for noninteractive verifiable secret sharing,Proc. 28th Symp. Found. Comp. Sci., pp. 427–437, October 1987.
O. Goldreich, S. Micali, and A. Wigderson, How to prove all NP statements in zero-knowledge and a methodology of cryptographic protocol design,Advances in Cryptology—CRYPTO '86, pp. 171–185, Lecture Notes in Computer Science, vol. 263, Springer-Verlag, Berlin, 1987.
S. Goldwasser, S. Micali, and R. L. Rivest, A “paradoxical” solution to the signature problem,Proc. 25th Symp. Found. Comp. Sci., pp. 441–448, October 1984.
J.D. Lipson,Elements of Algebra and Algebraic Computing, Addison-Wesley, Reading, MA, 1981.
M. O. Rabin, Randomized Byzantine generals,Proc. 24th Symp. Found. Comp. Sci., pp. 403–409, November 1983.
A. Shamir, How to share a secret,Comm. ACM,22(11): 612–613, November 1979.
Author information
Authors and Affiliations
Additional information
This material is based in part upon work supported by the National Science Foundation under Grant Nos. DCR-8301212 and DCR-8352093. Part of the work was performed while the second author was a visitor at the IBM Thomas J. Watson Research Center.
Rights and permissions
About this article
Cite this article
Tompa, M., Woll, H. How to share a secret with cheaters. J. Cryptology 1, 133–138 (1989). https://doi.org/10.1007/BF02252871
Issue Date:
DOI: https://doi.org/10.1007/BF02252871