research-article

Secret Sharing, Rank Inequalities, and Information Inequalities

Authors:

Sebastia Martin,

An YangAuthors Info & Claims

IEEE Transactions on Information Theory, Volume 62, Issue 1

Pages 599 - 609

https://doi.org/10.1109/TIT.2015.2500232

Published: 01 January 2016 Publication History

Abstract

Beimel and Orlov proved that all information inequalities on four or five variables, together with all information inequalities on more than five variables that are known to date, provide lower bounds on the size of the shares in secret sharing schemes that are at most linear on the number of participants. We present here another two negative results about the power of information inequalities in the search for lower bounds in secret sharing. First, we prove that all information inequalities on a bounded number of variables can only provide lower bounds that are polynomial on the number of participants. Second, we prove that the rank inequalities that are derived from the existence of two common informations can provide only lower bounds that are at most cubic in the number of participants.

References

[1]

L. Babai, A. Gál, and A. Wigderson, “Superpolynomial lower bounds for monotone span programs,” Combinatorica, vol. 19, no. 3, pp. 301–319, 1999.

[2]

A. Beimel, “Secret-sharing schemes: A survey,” in Coding and Cryptology, vol. 6639, Y. M. Chee et al., Eds. Heidelberg, Germany: Springer-Verlag, 2011, pp. 11–46.

[3]

A. Beimel, A. Ben-Efraim, C. Padró, and I. Tyomkin, “Multi-linear secret-sharing schemes,” in Proc. 11th Theory Cryptogr. Conf. (TCC), vol. 8349. 2014, pp. 394–418.

[4]

A. Beimel, A. Gál, and M. Paterson, “Lower bounds for monotone span programs,” Comput. Complex., vol. 6, no. 1, pp. 29–45, 1997.

Digital Library

[5]

A. Beimel, N. Livne, and C. Padró, “Matroids can be far from ideal secret sharing,” in Proc. 5th Theory Cryptogr. Conf. (TCC), vol. 4948. 2008, pp. 194–212.

[6]

A. Beimel and I. Orlov, “Secret sharing and non-Shannon information inequalities,” IEEE Trans. Inf. Theory, vol. 57, no. 9, pp. 5634–5649, Sep. 2011.

Digital Library

[7]

J. Benaloh and J. Leichter, “Generalized secret sharing and monotone functions,” in Advances in Cryptology, vol. 403, S. Goldwasser, Ed. Heidelberg, Germany: Springer-Verlag, 1990, pp. 27–35.

[8]

G. R. Blakley, “Safeguarding cryptographic keys,” in Proc. AFIPS Conf., vol. 48. 1979, pp. 313–317.

[9]

C. Blundo, A. De Santis, R. De Simone, and U. Vaccaro, “Tight bounds on the information rate of secret sharing schemes,” Designs, Codes Cryptogr., vol. 11, no. 2, pp. 107–110, 1997.

Digital Library

[10]

R. M. Capocelli, A. De Santis, L. Gargano, and U. Vaccaro, “On the size of shares for secret sharing schemes,” J. Cryptol., vol. 6, no. 3, pp. 157–167, 1993.

Digital Library

[11]

T. Chan, “Recent progresses in characterising information inequalities,” Entropy, vol. 13, no. 2, pp. 379–401, 2011.

[12]

L. Csirmaz, “The size of a share must be large,” J. Cryptol., vol. 10, no. 4, pp. 223–231, 1997.

Digital Library

[13]

L. Csirmaz, “An impossibility result on graph secret sharing,” Designs, Codes Cryptogr., vol. 53, no. 3, pp. 195–209, 2009.

Digital Library

[14]

R. Dougherty, C. Freiling, and K. Zeger, “Six new non-Shannon information inequalities,” in Proc. IEEE Int. Symp. Inf. Theory, Jul. 2006, pp. 233–236.

[15]

R. Dougherty, C. Freiling, and K. Zeger. (2009). “Linear rank inequalities on five or more variables.” [Online]. Available: http://arxiv.org/abs/0910.0284

[16]

R. Dougherty, C. Freiling, and K. Zeger. (2011). “Non-Shannon information inequalities in four random variables.” [Online]. Available: http://arxiv.org/abs/1104.3602

[17]

O. Farràs, J. R. Metcalf-Burton, C. Padró, and L. Vázquez, “On the optimization of bipartite secret sharing schemes,” Designs, Codes Cryptogr., vol. 63, no. 2, pp. 255–271, 2012.

Digital Library

[18]

S. Fujishige, “Polymatroidal dependence structure of a set of random variables,” Inf. Control, vol. 39, no. 1, pp. 55–72, 1978.

[19]

S. Fujishige, “Entropy functions and polymatroids—Combinatorial structures in information theory,” Electron. Commun. Jpn., vol. 61, no. 4, pp. 14–18, 1978.

[20]

P. Gacs and J. Körner, “Common information is far less than mutual information,” Problems Control Inf. Theory, vol. 2, no. 2, pp. 149–162, 1973.

[21]

A. Gál, “A characterization of span program size and improved lower bounds for monotone span programs,” Comput. Complex., vol. 10, no. 4, pp. 277–296, 2001.

Digital Library

[22]

D. Hammer, A. Romashchenko, A. Shen, and N. Vereshchagin, “Inequalities for Shannon entropy and Kolmogorov complexity,” J. Comput. Syst. Sci., vol. 60, no. 2, pp. 442–464, 2000.

[23]

A. W. Ingleton, “Representation of matroids,” in Combinatorial Mathematics and Its Applications, D. J. A. Welsh, Ed. London, U.K.: Academic, 1971, pp. 149–167.

[24]

M. Ito, A. Saito, and T. Nishizeki, “Secret sharing scheme realizing any access structure,” in Proc. IEEE Globecom, 1987, pp. 99–102.

[25]

W.-A. Jackson and K. M. Martin, “Perfect secret sharing schemes on five participants,” Designs, Codes Cryptogr., vol. 9, no. 3, pp. 267–286, 1996.

Digital Library

[26]

T. Kaced. (2013). “Equivalence of two proof techniques for non-Shannon-type inequalities.” [Online]. Available: http://arxiv.org/abs/1302.2994

[27]

R. Kinser, “New inequalities for subspace arrangements,” J. Combinat. Theory, A, vol. 118, no. 1, pp. 152–161, 2011.

Digital Library

[28]

F. Matúš, “Infinitely many information inequalities,” in Proc. IEEE Int. Symp. Inf. Theory (ISIT), Jun. 2007, pp. 41–44.

[29]

F. Matúš and L. Csirmaz. (2013). “Entropy region and convolution.” [Online]. Available: http://arxiv.org/abs/1310.5957

[30]

J. R. Metcalf-Burton, “Improved upper bounds for the information rates of the secret sharing schemes induced by the Vámos matroid,” Discrete Math., vol. 311, nos. 8–9, pp. 651–662, 2011.

Digital Library

[31]

C. Padró, L. Vázquez, and A. Yang, “Finding lower bounds on the complexity of secret sharing schemes by linear programming,” Discrete Appl. Math., vol. 161, nos. 7–8, pp. 1072–1084, 2013.

Digital Library

[32]

R. Rado, “Note on independence functions,” Proc. London Math. Soc., vol. 3, no. 7, pp. 300–320, 1957.

[33]

A. Schrijver, Combinatorial Optimization: Polyhedra and Efficiency. Berlin, Germany: Springer-Verlag, 2003.

[34]

A. Shamir, “How to share a secret,” Commun. ACM, vol. 22, no. 11, pp. 612–613, 1979.

Digital Library

[35]

D. J. A. Welsh, Matroid Theory. London, U.K.: Academic, 1976.

[36]

Z. Zhang, “On a new non-Shannon type information inequality,” Commun. Inf. Syst., vol. 3, no. 1, pp. 47–60, 2003.

[37]

Z. Zhang and R. W. Yeung, “On characterization of entropy function via information inequalities,” IEEE Trans. Inf. Theory, vol. 44, no. 4, pp. 1440–1452, Jul. 1998.

Digital Library

Cited By

Applebaum BArkis B(2020)On the Power of Amortization in Secret SharingACM Transactions on Computation Theory10.1145/341775612:4(1-21)Online publication date: 30-Sep-2020
https://dl.acm.org/doi/10.1145/3417756
Bamiloshin MBen-Efraim AFarràs OPadró C(2020)Common information, matroid representation, and secret sharing for matroid portsDesigns, Codes and Cryptography10.1007/s10623-020-00811-189:1(143-166)Online publication date: 28-Oct-2020
https://dl.acm.org/doi/10.1007/s10623-020-00811-1

Index Terms

Secret Sharing, Rank Inequalities, and Information Inequalities

Index terms have been assigned to the content through auto-classification.

Recommendations

Secret Sharing and Non-Shannon Information Inequalities

The known secret-sharing schemes for most access structures are not efficient; even for a one-bit secret the length of the shares in the schemes is 2^O(n), where n is the number of participants in the access structure. It is a long standing open problem ...
Secret Sharing and Non-Shannon Information Inequalities
TCC '09: Proceedings of the 6th Theory of Cryptography Conference on Theory of Cryptography

The known secret-sharing schemes for most access structures are not efficient; even for a one-bit secret the length of the shares in the schemes is 2^{<em>O</em> (<em>n</em> )}, where <em>n</em> is the number of participants in the access structure. It is ...
Fair secret reconstruction in (t, n) secret sharing

In Shamir's (t, n) threshold secret sharing scheme, one secret s is divided into n shares by a dealer and all shares are shared among n shareholders, such that knowing t or more than t shares can reconstruct this secret; but knowing fewer than t shares ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Transactions on Information Theory

IEEE Transactions on Information Theory Volume 62, Issue 1

Jan. 2016

624 pages

ISSN:0018-9448

Issue’s Table of Contents

Copyright © 2015.

Publisher

IEEE Press

Publication History

Published: 01 January 2016

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 27 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Applebaum BArkis B(2020)On the Power of Amortization in Secret SharingACM Transactions on Computation Theory10.1145/341775612:4(1-21)Online publication date: 30-Sep-2020
https://dl.acm.org/doi/10.1145/3417756
Bamiloshin MBen-Efraim AFarràs OPadró C(2020)Common information, matroid representation, and secret sharing for matroid portsDesigns, Codes and Cryptography10.1007/s10623-020-00811-189:1(143-166)Online publication date: 28-Oct-2020
https://dl.acm.org/doi/10.1007/s10623-020-00811-1

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents