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 in being distributed as shares compared with 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. [15]. 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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
A. Beimel and B. Chor. Universally ideal secret sharing schemes. Proc. Crypto '92. Lecture Notes in Computer Science, Vol. 740. Springer-Verlag, Berlin, 1993, pp. 185–197.
J. Benaloh and J. Leichter. Generalized secret sharing and monotone functions. Proc. Crypto '88. Lecture Notes in Computer Science, Vol. 403. Springer-Verlag, Berlin, 1990, pp. 27–35.
C. Berge. Graphs, 2nd rev. edn. North-Holland, Amsterdam, 1985.
G. R. Blakley. Safeguarding cryptographic keys. AFIPS Conf. Proc. 48 (1979), 313–317.
B. Blakley, G. R. Blakley, A. H. Chan, and J. L. Massey. Threshold schemes with disenrollment. Proc. Crypto '92. Lecture Notes in Computer Science, Vol. 740. Springer-Verlag, Berlin, 1993, pp. 546–54.
C. Blundo. Secret Sharing Schemes for Access Structures Based on Graphs. Tesi di Laurea, University of Salerno, 1991 (in Italian).
C. Blundo, A. Cresti, A. De Santis, and U. Vaccaro. Fully dynamic secret sharing schemes. Proc. Crypto '93. Lecture Notes in Computer Science, Vol. 773. Springer-Verlag, Berlin, 1994, pp. 110–125.
C. Blundo, A. De Santis, L. Gargano, and U. Vaccaro. On the information rate of secret sharing schemes. Proc. Crypto '92. Lecture Notes in Computer Science, Vol. 740. Springer-Verlag, Berlin, 1993, pp. 149–169.
C. Blundo, A. De Santis, and U. Vaccaro. Efficient sharing of many secrets. Proc. STACS '93. Lecture Notes in Computer Science, Vol. 665. Springer-Verlag, Berlin, 1993, pp. 692–703.
E. F. Brickell. Some ideal secret sharing schemes. J. Combin. Math. Combin. Comput. 9 (1989), 105–113.
E. F. Brickell and D. M. Davenport. On the classification of ideal secret sharing schemes. J. Cryptology 4 (1991), 123–134.
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. Discrete Math. 4 (1991), 502–510.
E. F. Brickell and D. R. Stinson. Some improved bounds on the information rate of perfect secret sharing schemes. J. Cryptology 5 (1992), 153–166.
R. M. Capocelli, A. De Santis, L. Gargano, and U. Vaccaro. On the size of shares for secret sharing schemes. J. Cryptology 6 (1993), 157–168.
M. Carpentieri, A. De Santis, and U. Vaccaro. Size of shares and probability of chearing in threshold schemes. Proc. Eurocrypt '93. Lecture Notes in Computer Science, Vol. 765. Springer-Verlag, Berlin, 1994, pp. 118–125.
E. Dawson, E. S. Mahmoodian, and A. Rahilly. Orthogonal arrays and ordered threshold schemes. Austral. J. Combin. 8 (1993), 27–44.
M. R. Garey and D. S. Johnson. Computers and Intractability. A Guide to Theory of NP-Completeness. Freeman, New York, 1979.
O. Goldreich, S. Micall, and A. Wigderson. How to play any mental game. Proc. 19th ACM Symp. on Theory of Computing, 1987, pp. 218–229.
I. Ingemarsson and G. J. Simmons. A protocol to set up shared secret schemes without the assistance of a mutually trusted party. Proc. Eurocrypt '90. Lecture Notes in Computer Science, Vol. 473. Springer-Verlag, Berlin, 1991, pp. 266–282.
M. Ito, A. Saito, and T. Nishizeki. Secret sharing scheme realizing general access structure. Proc. IEEE Globecom '87, 1987, pp. 99–102.
M. Ito, A. Saito, and T. Nishizeki. Multiple assignment scheme for sharing secret. J. Cryptology 6 (1993), 15–20.
W.-A. Jackson and K. M. Martin. On ideal secret sharing schemes. Preprint.
W.-A. Jackson, K. M. Martin, and C. M. O'Keefe. Multisecret threshold schemes. Proc. Crypto '93. Lecture Notes in Computer Science, Vol. 773. Springer-Verlag, Berlin, 1994, pp. 126–135.
E. D. Karnin, J. W. Greene, and M. E. Hellman. On secret sharing systems. IEEE Trans. Inform. Theory 29 (1983), 35–41.
K. M. Martin. Discrete Structures in the Theory of Secret Sharing. Ph.D. thesis, University of London, 1991.
K. M. Martin. New secret sharing schemes from old. J. Combin. Math. Combin. Comput. 14 (1993), 65–77.
R. J. McEliece and D. V. Sarwate. On sharing secrets and Reed-Solomon codes. Comm. ACM 24 (1981), 583–584.
T. Rabin and M. Ben-Or. Verifiable secret sharing and multiparty protocols with honest majority. Proc. 21st ACM Symp. on Theory of Computing, 1989, pp. 73–85.
P. D. Seymour. On secret-sharing matroids. J. Combin. Theory Ser. B 56 (1992), 69–73.
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.
G. J. Simmons. How to (really) share a secret. Proc. Crypto '88. Lecture Notes in Computer Science, Vol. 403. Springer-Verlag, Berlin, 1990, pp. 390–448.
G. J. Simmons. Prepositioned shared secret and/or shared control schemes. Proc. Eurocrypt '89. Lecture Notes in Computer Science, Vol. 434. Springer-Verlag, Berlin, 1990, pp. 436–467.
G. J. Simmons. Shared secret and/or shared control schemes. Proc. Crypto '90. Lecture Notes in Computer Science, Vol. 537. Springer-Verlag, Berlin, 1991, pp. 216–241.
G. J. Simmons. An introduction to shared secret and/or shared control schemes and their application. Contemporary Cryptology, IEEE Press, New York, 1991, pp. 441–497.
G. J. Simmons, W. Jackson, and K. Martin. The geometry of shared secret schemes. Bull. ICA 1 (1991), 71–88.
D. R. Stinson. An explication of secret sharing schemes. Designs Codes Cryptography 2 (1992), 357–390.
D. R. Stinson. New general lower bounds on the information rate of secret sharing schemes. Proc. Crypto '92. Lectures Notes in Computer Science, Vol. 740. Springer-Verlag, Berlin, 1993, pp. 170–184.
D. R. Stinson. Decomposition constructions for secret sharing schemes. IEEE Trans. Inform. Theory 40 (1994), 118–125.
M. Tompa and H. Woll. How to share a secret with cheaters. J. Cryptology 1 (1988), 133–138.
Author information
Authors and Affiliations
Additional information
Communicated by Ernest F. Brickell
The research of C. Blundo, A. De Santis, and U. Vaccaro was partially supported by the Italian Ministry of University and Research (M.U.R.S.T.) and by the National Council for Research (C.N.R.) under Grant 91.02326.CT12. The research of D. R. Stinson was supported by NSF Grant CCR-9121051.
Rights and permissions
About this article
Cite this article
Blundo, C., De Santis, A., Stinson, D.R. et al. Graph decompositions and secret sharing schemes. J. Cryptology 8, 39–64 (1995). https://doi.org/10.1007/BF00204801
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF00204801