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

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.

• Hui-Chuan Lu

• Secret-sharing scheme
• average information ratio
• star covering
• deduction
• core cluster.

[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.