A Study on the Average Information Ratio of Perfect Secret-Sharing Schemes for Access Structures Based On Bipartite Graphs
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.
[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.
[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.
@article{"International Journal of Engineering, Mathematical and Physical Sciences:62196", author = "Hui-Chuan Lu", title = "A Study on the Average Information Ratio of Perfect Secret-Sharing Schemes for Access Structures Based On Bipartite Graphs", 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.", volume = "6", number = "9", pages = "1338-6", }
