Abstract
In this paper, we continue a study of secret sharing schemes for access structures based on graphs. Given a graph G, we require that a subset of participants can compute a secret key if they contain an edge of G; otherwise, they can obtain no information regarding the key. We study the information rate of such schemes, which measures how much information is being distributed as shares as compared to the size of the secret key, and the average information rate, which is the ratio between the secret size and the arithmetic mean of the size of the shares. We give both upper and lower bounds on the optimal information rate and average information rate that can be obtained. Upper bounds arise by applying entropy arguments due to Capocelli et al [10]. Lower bounds come from constructions that are based on graph decompositions. Application of these constructions requires solving a particular linear programming problem. We prove some general results concerning the information rate and average information rate for paths, cycles and trees. Also, we study the 30 (connected) graphs on at most five vertices, obtaining exact values for the optimal information rate in 26 of the 30 cases, and for the optimal average information rate in 28 of the 30 cases.
Partially supported by Italian Ministry of University and Research (M.U.R.S.T.) and by National Council for Research (C.N.R.) under grant 91.02326.CT12.
Research supported by NSERC (Canada) grant A9287.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
J. Benaloh and J. Leichter. Generalized secret sharing and monotone functions. Lecture Notes in Computer Science, 403:27–35, 1990.
C. Berge. Graphs. Second revised edition, North-Holland, 1985.
G. R. Blakley. Safeguarding cryptographic keys. AFIPS Conference Proceedings, 48:313–317, 1979.
C. Blundo. Secret Sharing Schemes for Access Structures based on Graphs. Tesi di Laurea, University of Salerno, Italy, 1991, (in Italian).
E. F. Brickell. Some ideal secret sharing schemes. J. Combin. Math. and Combin. Comput., 9:105–113, 1989.
E. F. Brickell and D. M. Davenport. On the classification of ideal secret sharing schemes. J. Cryptology, 4:123–134, 1991.
E. F. Brickell and D. R. Stinson. Some improved bounds on the information rate of perfect secret sharing schemes. Lecture Notes in Computer Science, 537:242–252, 1991. To appear in J. Cryptology.
E. F. Brickell and D. R. Stinson. Some improved bounds on the information rate of perfect secret sharing schemes. Department of Computer Science and Engineering Report Series # 106, University of Nebraska, May 1990.
E. F. Brickell and D. R. Stinson. The detection of cheaters in threshold schemes. SIAM J. on Discrete Math., 4:502–510, 1991.
R. M. Capocelli, A. De Santis, L. Gargano, and U. Vaccaro. On the size of shares for secret sharing schemes. Lecture Notes in Computer Science, 576:101–113, 1991. To appear in J. Cryptology.
M. R. Garey and D. S. Johnson. Computers and Intractability. A Guide to Theory of NP-Completeness. W. H. Freeman and Company, New York, 1979.
O. Goldreich, S. Micali, and A. Wigderson. How to play any mental game, Proc. 19th ACM Symp. on Theory of Computing, pages 218–229, 1987.
I. Ingemarsson and G. J. Simmons. A protocol to set up shared secret schemes without the assistance of a mutually trusted party. Lecture Notes in Computer Science, 473:266–282, 1991.
M. Ito, A. Saito, and T. Nishizeki. Secret sharing scheme realizing general access structure. Proc. IEEE Globecom’ 87, pages 99–102, 1987.
E. D. Karnin, J. W. Greene, and M. E. Ilellman. On secret sharing systems. IEEE Transactions on Information Theory, IT-29:35–41, 1983.
K. M. Martin. Discrete Structures in the Theory of Secret Sharing. PhD Thesis, University of London, 1991.
K. M. Martin. New secret sharing schemes from old. Submitted to Journal of Combin. Math. and Combin. Comput.
R. J. McEliece and D. V. Sarwate. On sharing secrets and Reed-Solomon codes. Commun. of the ACM, 24:583–584, 1981.
T. Rabin and M. Ben-Or. Verifiable secret sharing and multiparty protocols with honest majority. Proc. 21st ACM Symp. on Theory of Computing, pages 73–85, 1989.
P. D. Seymour. On secret-sharing matroids. Preprint.
A. Shamir. How to share a secret. Commun. of the ACM, 22:612–613, 1979.
G. J. Simmons. Shared secret and/or shared control schemes. Lecture Notes in Computer Science, 537:216–241, 1991.
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’. Congressus Number., 68:215–248, 1989.
G. J. Simmons. How to (really) share a secret. Lecture Notes in Computer Science, 403:390–448, 1990.
G. J. Simmons. An introduction to shared secret and/or shared control schemes and their application. Contemporary Cryptology, IEEE Press, pages 441–497, 1991.
G. J. Simmons. Prepositioned shared secret and/or shared control schemes. Lecture Notes in Computer Science, 434:436–467, 1990.
G. J. Simmons, W. Jackson, and K. Martin. The geometry of shared secret schemes. Bulletin of the ICA, 1:71–88, 1991.
M. Tompa and H. Woll. How to share a secret with cheaters. J. Cryptology, 1:133–138, 1988.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1993 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Blundo, C., De Santis, A., Stinson, D.R., Vaccaro, U. (1993). Graph Decompositions and Secret Sharing Schemes. In: Rueppel, R.A. (eds) Advances in Cryptology — EUROCRYPT’ 92. EUROCRYPT 1992. Lecture Notes in Computer Science, vol 658. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-47555-9_1
Download citation
DOI: https://doi.org/10.1007/3-540-47555-9_1
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-56413-3
Online ISBN: 978-3-540-47555-2
eBook Packages: Springer Book Archive