Abstract
In a secret sharing scheme, a dealer has a secret key. There is a finite set P of participants and a set Γ of subsets of P. A secret sharing scheme with Γ as the access structure is a method which the dealer can use to distribute shares to each participant so that a subset of participants can determine the key if and only if that subset is in Γ. The share of a participant is the information sent by the dealer in private to the participant. A secret sharing scheme is ideal if any subset of participants who can use their shares to determine any information about the key can in fact actually determine the key, and if the set of possible shares is the same as the set of possible keys. In this paper, we show a relationship between ideal secret sharing schemes and matroids.
This work performed at Saudia National Laboratories and supported by the U.S. Department of Energy under contract No. DE-AC04-76DP00789.
Chapter PDF
Similar content being viewed by others
References
J. C. Benaloh and J. Leichter, Generalized secret sharing and monotone functions. to appear in Advances in Cryptology-CRYPTO88.
G. R. Blakley, Safeguarding cryptographic keys, in Proceedings AFIPS 1979 National Computer Conference, vol. 48, 1979, pp. 313–317.
E. F. Brickell, Some ideal secret sharing schemes. to appear in the Journal of Combinatorial Mathematics and Combinatorial Computing.
M. Ito, A. Saito, and T. Nishizeki, Secret sharing scheme realizing general access structure, in Proceedings IEEE Globecom’87, Tokyo, Japan, 1987, pp. 99–102.
A. Shamir, How to share a secret, Communications of the ACM, 22 (1979), pp. 612–613.
G. J. Simmons, Robust shared secret schemes. to appear in Congressus Numer-antium, Vol. 68–69.
S. Vajda, Patterns and Configurations in Finite Spaces, Hafner Publishing, New York, 1967.
D. J. A. Welsh, Matroid Theory, Academic Press, London, 1976.
A. Yao. Presentation at the Cryptography conference in Oberwolfach, West Germany, Sep. 1989.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1990 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Brickell, E.F., Davenport, D.M. (1990). On the Classification of Ideal Secret Sharing Schemes. In: Brassard, G. (eds) Advances in Cryptology — CRYPTO’ 89 Proceedings. CRYPTO 1989. Lecture Notes in Computer Science, vol 435. Springer, New York, NY. https://doi.org/10.1007/0-387-34805-0_25
Download citation
DOI: https://doi.org/10.1007/0-387-34805-0_25
Published:
Publisher Name: Springer, New York, NY
Print ISBN: 978-0-387-97317-3
Online ISBN: 978-0-387-34805-6
eBook Packages: Springer Book Archive