A Study on the Average Information Ratio of Perfect Secret-Sharing Schemes for Access Structures Based On Bipartite Graphs

Authors: Hui-Chuan Lu

Abstract:

A perfect secret-sharing scheme is a method to distribute a secret among a set of participants in such a way that only qualified subsets of participants can recover the secret and the joint share of participants in any unqualified subset is statistically independent of the secret. The collection of all qualified subsets is called the access structure of the perfect secret-sharing scheme. In a graph-based access structure, each vertex of a graph G represents a participant and each edge of G represents a minimal qualified subset. The average information ratio of a perfect secret-sharing scheme  realizing the access structure based on G is defined as AR = (Pv2V (G) H(v))/(|V (G)|H(s)), where s is the secret and v is the share of v, both are random variables from  and H is the Shannon entropy. The infimum of the average information ratio of all possible perfect secret-sharing schemes realizing a given access structure is called the optimal average information ratio of that access structure. Most known results about the optimal average information ratio give upper bounds or lower bounds on it. In this present structures based on bipartite graphs and determine the exact values of the optimal average information ratio of some infinite classes of them.

Keywords: secret-sharing scheme, average information ratio, star covering, core sequence.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1080630

References:

[1] A. Beimel and N. Livne, On matroids and non-ideal secret sharing, in: Proceedings of the third theory of cryptography conference, LNCS, 3876 (2006), 482-501.
[2] G. R. Blakley, Safeguarding cryptographic keys, in "Proceedings of the National Computer Conference, 1979", American Federation of Information Processing Societies Proceedings, 48 (1979), 313-317.
[3] C. Blundo, A. De Santis, R. De Simone and U. Vaccaro, Tight bounds on the information rate of secret sharing schemes, Designs, Codes and Cryptography, 11 (1997), 107-122.
[4] C. Blundo, A. De Santis, L. Gargano and U. Vaccaro, On the information rate of secret sharing schemes, Theoretical Computer Science, 154 (1996), 283-306.
[5] C. Blundo, A. De Santis, A. Giorgio Gaggian and U. Vaccaro, New bounds on the information rate of secret sharing schemes, IEEE Transactions on Information Theory, 41 (1995), 549-554.
[6] C. Blundo, A. De Santis, D. R. Stinson and U. Vaccaro, Graph decompositions and secret sharing schemes, J. Cryptology, 8 (1995), 39-64.
[7] E. F. Brickell and D. M. Davenport, On the classification of ideal secret sharing schemes, J. Cryptology, 4 (1991), 123-134.
[8] 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.
[9] L. Csirmaz, The size of a share must be large, J. Cryptology, 10 (1997), 223-231.
[10] L. Csirmaz, An impossibility result on graph secret sharing, Designs, Codes and Cryptography, 53 (2009), 195-209.
[11] L. Csirmaz, Secret sharing schemes on graphs, Studia Mathematica Hungarica, 10 (1997), 297-306.
[12] L. Csirmaz and P. Ligeti, On an infinite families of graphs with information ratio 2 − 1 k , Computing, 85 (2009), 127-136.
[13] L. Csirmaz and G. Tardas, Exact bounds on tree based secret sharing schemes, Tatracrypt 2007, Slovakia.
[14] I. Csisz'ar and J. K¨orner, Information Theory. Coding Theorems for Discrete Memoryless Systems, Academic Press, New York, 1981.
[15] M. van Dijk, On the information rate of perfect secret sharing schemes, Designs, Codes and Cryptography, 6 (1995), 143-169.
[16] W.-A. Jackson and K. M. Martin, Perfect secret sharing schemes on five participants, Designs Codes and Cryptography, 9 (1996), 267–286.
[17] H-C Lu and H-L Fu, The exact values of the average information ratio for tree-based access structures of perfect secret sharing schemes, submitted.
[18] J. Marti-Farr´e and C. Padr´o, Secret sharing schemes with three or four minimal qualified subsets, Designs, Codes and Cryptography, 34 (2005), 17–34.
[19] P. Morillo, C. Padro, G. Saez and J. L. Villar, Weighted threshold secret sharing schemes, Information Processing Letters, 704 (1999), 211–216.
[20] C. Padro and G. Saez, Secret Sharing Schemes with Bipartite Access Structure, IEEE Transactions on Information Theory, 46(7) (2000), 2596–2604.
[21] A. Shamir, How to share a secret, Communications of the ACM, 22 (1979), 612–613.
[22] D. R. Stinson, An explication of secret sharing schemes, Designs Codes and Cryptography, 2 (1992), 357–390.
[23] D. R. Stinson, New general lower bounds on the information rate of perfect secret sharing schemes, in “Advances in Cryptology – CRYPTO ’92”, E. F. Brickell, ed., Lecture Notes in Computer Science, 740 (1993), 168–182.
[24] D. R. Stinson, Decomposition constructions for secret sharing schemes, IEEE Transactions on Information Theory, 40 (1994), 118–125.