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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
J. C. Benaloh and J. Leichter. Generalized secret sharing and monotone functions. In Advances in Cryptology-Crypto '88, New York, pp. 27–36, 1990.
G. R. Blakley. Safeguarding cryptographic keys. In Proceedings of the AFIPS 1979 National Computer Conference, vol. 48, pp. 313–317, 1979.
E. F. Brickell. Some ideal secret sharing schemes. Journal of Combinatorial Mathematics and Combinatorial Computing, 6:105–113, 1989.
M. Hall, Jr. Combinatorial Theory. Wiley, New York, 1986.
M. Ito, A. Saito, and T. Nishizeki. Secret sharing scheme realizing general access structure. In Proceedings of IEEE Globecom '87, Tokyo, pp. 99–102, 1987.
A. Shamir. How to share a secret. Communications of the ACM, 22(11):612–613, 1979.
G. J. Simmons. Robust shared secret schemes. Congressus Numerantium, 68:215–248, 1989.
D. R. Stinson and S. A. Vanstone. A combinatorial approach to threshold schemes. SIAM Journal of Discrete Mathematics, 1(2):230–236, 1988.
K. Truemper. On the efficiency of representability tests for matroids. European Journal of Combinatorics, 3:275–291, 1982.
S. Vajda. Patterns and Configurations in Finite Spaces. Hafner, New York, 1967.
D. J. A. Welsh. Matroid Theory. Academic Press, London, 1976.
A. Yao. Presentation at the Cryptography Conference in Oberwolfach, F.R. Germany, September, 1989.
Author information
Authors and Affiliations
Additional information
This work was performed at the Sandia National Laboratories and was supported by the U.S. Department of Energy under Contract No. DE-AC04-76DP00789.
Rights and permissions
About this article
Cite this article
Brickell, E.F., Davenport, D.M. On the classification of ideal secret sharing schemes. J. Cryptology 4, 123–134 (1991). https://doi.org/10.1007/BF00196772
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF00196772