On the classification of ideal secret sharing schemes. (English) Zbl 0747.94010
Summary: In a secret sharing scheme a dealer has a secret key. There is a finite set \(P\) of participants and a set \(\Gamma\) of subsets of \(P\). A secret sharing with \(\Gamma\) as the access structure is a method which the dealer can use to distribute shares to each participants so that a subset of participants can determine the key if and only if that subset is in \(\Gamma\). 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.
References:
| [1] | J. C. Benaloh and J. Leichter. Generalized secret sharing and monotone functions. In Advances in Cryptology-Crypto ’88, New York, pp. 27-36, 1990. · Zbl 0715.94003 |
| [2] | Blakley, G. R., Safeguarding cryptographic keys, Proceedings of the AFIPS 1979 National Computer Conference, vol. 48, 313-317 (1979) |
| [3] | Brickell, E. F., Some ideal secret sharing schemes, Journal of Combinatorial Mathematics and Combinatorial Computing, 6, 105-113 (1989) · Zbl 0685.94003 |
| [4] | Hall, M. Jr, Combinatorial Theory (1986), New York: Wiley, New York · Zbl 0588.05001 |
| [5] | 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. |
| [6] | Shamir, A., How to share a secret, Communications of the ACM, 22, 11, 612-613 (1979) · Zbl 0414.94021 |
| [7] | Simmons, G. J., Robust shared secret schemes, Congressus Numerantium, 68, 215-248 (1989) |
| [8] | Stinson, D. R.; Vanstone, S. A., A combinatorial approach to threshold schemes, SIAM Journal of Discrete Mathematics, 1, 2, 230-236 (1988) · Zbl 0667.05008 |
| [9] | Truemper, K., On the efficiency of representability tests for matroids, European Journal of Combinatorics, 3, 275-291 (1982) · Zbl 0505.05021 |
| [10] | Vajda, S., Patterns and Configurations in Finite Spaces (1967), New York: Hafner, New York · Zbl 0192.33301 |
| [11] | Welsh, D. J. A., Matroid Theory (1976), London: Academic Press, London · Zbl 0343.05002 |
| [12] | A. Yao. Presentation at the Cryptography Conference in Oberwolfach, F.R. Germany, September, 1989. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
