A New Bound on the Average Information Ratio of Perfect Secret-Sharing Schemes for Access Structures Based On Bipartite Graphs of Larger Girth

Authors: Hui-Chuan Lu

Abstract:

In a perfect secret-sharing scheme, a dealer distributes 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 the participants in any unqualified subset is statistically independent of the secret. The access structure of the scheme refers to the collection of all qualified subsets. In a graph-based access structures, 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 a given access structure is the ratio of the average length of the shares given to the participants to the length of the secret. The infimum of the average information ratio of all possible perfect secret-sharing schemes realizing an access structure is called the optimal average information ratio of that access structure. We study the optimal average information ratio of the access structures based on bipartite graphs. Based on some previous results, we give a bound on the optimal average information ratio for all bipartite graphs of girth at least six. This bound is the best possible for some classes of bipartite graphs using our approach.

Keywords: Secret-sharing scheme, average information ratio, star covering, deduction, core cluster.

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

References:

[1] G. R. Blakley, "Safeguarding cryptographic keys”, in: Amer. Fed. Inf. Process. Soc. Proc. 1979, vol.48, pp.313–317.
[2] C. Blundo, A. De Santis, R. De Simone and U. Vaccaro, "Tight bounds on the information rate of secret sharing schemes”, Des. Codes Cryptogr., vol.11, pp.107–122, 1997
[3] C. Blundo, A. De Santis, L. Gargano and U. Vaccaro, "On the information rate of secret sharing schemes”, Theor. Comp. Soc., vol. 154, pp.283–306, 1996.
[4] C. Blundo, A. De Santis, A. Giorgio Gaggian and U. Vaccaro, "New bounds on the information rate of secret sharing schemes”, IEEE Trans. Inf. Theory, vol.41, pp.549–554, 1995.
[5] C. Blundo, A. De Santis, D. R. Stinson and U. Vaccaro, "Graph decompositions and secret sharing schemes”, J. Cryptol., vol.8, pp.39–64, 1995.
[6] E. F. Brickell and D. M. Davenport, "On the classification of ideal secret sharing schemes”, J. Cryptol., vol.4, pp.123–134, 1991.
[7] E. F. Brickell and D. R. Stinson, "Some improved bounds on the information rate of perfect secret sharing schemes”, J. Cryptol., vol.5, pp.153–166, 1992.
[8] L. Csirmaz, "The size of a share must be large”, J. Cryptol., vol.10, pp.223-231, 1997.
[9] L. Csirmaz, "An impossibility result on graph secret sharing”, Des. Codes Cryptogr., vol.53, pp.195–209, 2009.
[10] L. Csirmaz, "Secret sharing schemes on graphs”, Studia Mathematica Hungarica, vol.10, pp.297–306, 1997.
[11] L. Csirmaz and P. Ligeti, "On an infinite families of graphs with information ratio 2 − 1/k”, Computing, vol.85, pp.127–136, 2009.
[12] L. Csirmaz and G. Tardos, "Exact bounds on tree based secret sharing schemes”, Tatracrypt 2007, Slovakia.
[13] I. Csisz´ar and J. K¨orner, Information Theory. Coding Theorems for Discrete Memoryless Systems, Academic Press, New York, 1981.
[14] M. van Dijk, "On the information rate of perfect secret sharing schemes”, Des. Codes Cryptogr., vol.6, pp.143–169, 1995.
[15] W.-A. Jackson and K. M. Martin, "Perfect secret sharing schemes on five participants”, Des. Codes Cryptogr., vol.9, pp.267–286, 1996.
[16] H-C Lu and H-L Fu, "The exact values of the average information ratio of perfect secret-sharing schemes for tree-based access structures”, Des. Codes Cryptogr. DOI 10.1007/s10623-012-9792-1.
[17] H-C Lu and H-L Fu, "The average informaion ratio of perfect secretsharing schemes for access structures based on sparse bipartite graphs”, submitted.
[18] A. Shamir, "How to share a secret”, Commun. ACM, vol.22, pp.612– 613, 1979.
[19] D. R. Stinson, "An explication of secret sharing schemes”, Des. Codes Cryptogr., vol.2, pp.357–390, 1992.
[20] D. R. Stinson, "New general lower bounds on the information rate of perfect secret sharing schemes”, in Advances in Cryptology – CRYPTO ’92, Lecture Notes in Computer Science, 1993, vol.740, pp.168–182.
[21] D. R. Stinson, "Decomposition constructions for secret sharing schemes”, IEEE Trans. Inf. Theory, vol.40, pp.118–125, 1994.
[22] D. B. West, Introduction to graph Theory, Prentice Hall, 2001.