Abstract
In this paper we study secret sharing schemes for access structures based on graphs. A secret sharing scheme enables a secret key to be shared among a set of participants by distributing partial information called shares. Suppose we desire that some specified pairs of participants be able to compute the key. This gives rise in a natural way to a graphG which contains these specified pairs as its edges. The secret sharing scheme is calledperfect if a pair of participants corresponding to a nonedge ofG can obtain no information regarding the key. Such a perfect secret sharing scheme can be constructed for any graph. In this paper we study the information rate of these schemes, which measures how much information is being distributed as shares compared with the size of the secret key. We give several constructions for secret sharing schemes that have a higher information rate than previously known schemes. We prove the general result that, for any graphG having maximum degreed, there is a perfect secret sharing scheme realizingG in which the information rate is at least 2/(d+3). This improves the best previous general bound by a factor of almost two.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
J. Benaloh and J. Leichter, Generalized secret sharing and monotone functions,Advances in Cryptology—Crypto 88 Proceedings, Lecture Notes in Computer Science, Vol. 403, Springer-Verlag, Berlin, 1990, pp. 27–35.
Th. Beth, D. Jungnickel, and H. Lenz,Design Theory, Bibliographisches Institut, Zurich, 1985.
G. R. Blakley, Safeguarding cryptographic keys,AFIPS Conference Proceedings, Vol. 48, 1979, pp. 313–317.
E. F. Brickell, Some ideal secret sharing schemes,J. Combin. Math. Combin. Comput.,6 (1989), 105–113.
E. F. Brickell and D. M. Davenport, On the classification of ideal secret sharing schemes,Advances in Cryptology—Crypto '89 Proceedings, Lecture Notes in Computer Science, Vol. 435, Springer-Verlag, Berlin, 1990, pp. 278–285 (also inJ. Cryptology,4 (1991), 123–134).
R. M. Capocelli, A. De Santis, L. Gargano, and U. Vaccaro, On the sizes of shares for secret sharing schemes, presented at Crypto '91.
D. Chen and D. R. Stinson, Recent results on combinatorial constructions for threshold schemes,Australasian J. Combin.,1 (1990), 29–48.
M. Ito, A. Saito, and T. Nishizeki, Secret sharing scheme realizing general access structure,Proc. IEEE Globecom '87, Tokyo, 1987, pp. 99–102.
P. J. Schellenberg and D. R. Stinson, Threshold schemes from combinatorial designs,J. Combin. Math. Combin. Comput.,5 (1989), 143–160.
A. Shamir, How to share a secret,Comm. ACM,22 (1979), 612–613.
G. J. Simmons, Robust shared secret schemes or “how to be sure you have the right answer even though you don't know the question,”Congr. Numer.,68 (1989), 215–248.
D. R. Stinson and S. A. Vanstone, A combinatorial approach to threshold schemes,SIAM J. Discrete Math.,1 (1988), 230–236.
Author information
Authors and Affiliations
Additional information
Communicated by Gustavus J. Simmons
The work of E. F. Brickell was performed at the Sandia National Laboratories and was supported by the U.S. Department of Energy under Contract Number DE-AC04-76DP00789. The research of D. R. Stinson was supported by NSERC Operating Grant A9287 and by the Center for Communication and Information Science, University of Nebraska.
Rights and permissions
About this article
Cite this article
Brickell, E.F., Stinson, D.R. Some improved bounds on the information rate of perfect secret sharing schemes. J. Cryptology 5, 153–166 (1992). https://doi.org/10.1007/BF02451112
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF02451112