Abstract
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 2O(n), where n is the number of participants in the access structure. It is a long standing open problem to improve these schemes or prove that they cannot be improved. The best known lower bound is by Csirmaz (J. Cryptology 97), who proved that there exist access structures with n participants such that the size of the share of at least one party is n/logn times the secret size. Csirmaz’s proof uses Shannon information inequalities, which were the only information inequalities known when Csirmaz published his result. On the negative side, Csirmaz proved that by only using Shannon information inequalities one cannot prove a lower bound of ω(n) on the share size. In the last decade, a sequence of non-Shannon information inequalities were discovered. This raises the hope that these inequalities can help in improving the lower bounds beyond n. However, in this paper we show that all the inequalities known to date cannot prove a lower bound of ω(n) on the share size.
The original version of the book was revised: The copyright line was incorrect. The Erratum to the book is available at DOI: 10.1007/978-3-642-00457-5_36
Partially supported by the Frankel Center for Computer Science at the Ben-Gurion University.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Babai, L., Gál, A., Wigderson, A.: Superpolynomial lower bounds for monotone span programs. Combinatorica 19(3), 301–319 (1999)
Beimel, A., Chor, B.: Universally ideal secret sharing schemes. IEEE Trans. on Info. Theory 40(3), 786–794 (1994)
Beimel, A., Franklin, M.: Weakly-private secret sharing schemes. In: Vadhan, S.P. (ed.) TCC 2007. LNCS, vol. 4392, pp. 253–272. Springer, Heidelberg (2007)
Beimel, A., Livne, N., Padró, C.: Matroids can be far from ideal secret sharing. In: Canetti, R. (ed.) TCC 2008. LNCS, vol. 4948, pp. 194–212. Springer, Heidelberg (2008)
Bellare, M., Rogaway, P.: Robust computational secret sharing and a unified account of classical secret-sharing goals. In: 14th CCS, pp. 172–184 (2007)
Ben-Or, M., Goldwasser, S., Wigderson, A.: Completeness theorems for noncryptographic fault-tolerant distributed computations. In: 20th STOC, pp. 1–10 (1988)
Benaloh, J.C., Leichter, J.: Generalized secret sharing and monotone functions. In: Goldwasser, S. (ed.) CRYPTO 1988. LNCS, vol. 403, pp. 27–35. Springer, Heidelberg (1990)
Blakley, G.R.: Safeguarding cryptographic keys. In: Proc. of the 1979 AFIPS National Computer Conference, pp. 313–317 (1979)
Blundo, C., De Santis, A., Gargano, L., Vaccaro, U.: On the information rate of secret sharing schemes. Theoretical Computer Science 154(2), 283–306 (1996)
Blundo, C., De Santis, A., Vaccaro, U.: On secret sharing schemes. Inform. Process. Lett. 65(1), 25–32 (1998)
Brickell, E.F.: Some ideal secret sharing schemes. Journal of Combin. Math. and Combin. Comput. 6, 105–113 (1989)
Capocelli, R.M., De Santis, A., Gargano, L., Vaccaro, U.: On the size of shares for secret sharing schemes. J. of Cryptology 6(3), 157–168 (1993)
Chan, T.H., Yeung, R.W.: On a relation between information inequalities and group theory. IEEE Trans. on Info. Theory 48(7), 1992–1995 (2002)
Chaum, D., Crépeau, C., Damgård, I.: Multiparty unconditionally secure protocols. In: 20th STOC, pp. 11–19 (1988)
Chor, B., Kushilevitz, E.: Secret sharing over infinite domains. J. of Cryptology 6(2), 87–96 (1993)
Cover, T.M., Thomas, J.A.: Elements of Information Theory. John Wiley & Sons, Chichester (1991)
Cramer, R., Damgård, I.B., Maurer, U.M.: General secure multi-party computation from any linear secret-sharing scheme. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, pp. 316–334. Springer, Heidelberg (2000)
Csirmaz, L.: The size of a share must be large. In: De Santis, A. (ed.) EUROCRYPT 1994. LNCS, vol. 950, pp. 13–22. Springer, Heidelberg (1995)
Csirmaz, L.: The dealer’s random bits in perfect secret sharing schemes. Studia Sci. Math. Hungar. 32(3–4), 429–437 (1996)
Desmedt, Y.G., Frankel, Y.: Shared generation of authenticators and signatures. In: Feigenbaum, J. (ed.) CRYPTO 1991. LNCS, vol. 576, pp. 457–469. Springer, Heidelberg (1992)
van Dijk, M.: A linear construction of perfect secret sharing schemes. In: De Santis, A. (ed.) EUROCRYPT 1994. LNCS, vol. 950, pp. 23–34. Springer, Heidelberg (1995)
van Dijk, M.: On the information rate of perfect secret sharing schemes. Designs, Codes and Cryptography 6, 143–169 (1995)
Dougherty, R., Freiling, C., Zeger, K.: Six new non-Shannon information inequalities. In: ISIT 2006, pp. 233–236 (2006)
Dougherty, R., Freiling, C., Zeger, K.: Networks, matroids, and non-Shannon information inequalities. IEEE Trans. on Info. Theory 53(6), 1949–1969 (2007)
Fujishige, S.: Polymatroidal dependence structure of a set of random variables. Information and Control 39(1–3), 55–72 (1978)
Gál, A.: A characterization of span program size and improved lower bounds for monotone span programs. Computational Complexity 10(4), 277–296 (2002)
Goyal, V., Pandey, O., Sahai, A., Waters, B.: Attribute-based encryption for fine-grained access control of encrypted data. In: 13th CCS, pp. 89–98 (2006)
Guille, L., Chan, T.H., Grant, A.: The minimal set of Ingleton inequalities. Technical Report 0802.2574, arxiv.org (2008), http://arxiv.org/abs/0802.2574
Ingleton, A.W.: Conditions for representability and transversability of matroids. In: Proc. Fr. Br. Conf. 1970, pp. 62–67. Springer, Heidelberg (1971)
Ito, M., Saito, A., Nishizeki, T.: Secret sharing schemes realizing general access structure. In: Globecom 1987, pp. 99–102 (1987)
Karchmer, M., Wigderson, A.: On span programs. In: Proc. of the 8th IEEE Structure in Complexity Theory, pp. 102–111 (1993)
Karnin, E.D., Greene, J.W., Hellman, M.E.: On secret sharing systems. IEEE Trans. on Info. Theory 29(1), 35–41 (1983)
Makarychev, K., Makarychev, Y., Romashchenko, A., Vereshchagin, N.: A new class of non-Shannon type inequalities for entropies. Communications in Information and Systems 2(2), 147–166 (2002)
Matúš, F.: Infinitely many information inequalities. In: IEEE International Symposium on Information Theory 2007, pp. 41–44 (2007)
Matúš, F.: Two constructions on limits of entropy functions. IEEE Trans. on Info. Theory 53(1), 320–330 (2007)
Naor, M., Wool, A.: Access control and signatures via quorum secret sharing. IEEE Transactions on Parallel and Distributed Systems 9(1), 909–922 (1998)
Oxley, J.G.: Matroid Theory. Oxford University Press, Oxford (1992)
Rabin, M.O.: Randomized Byzantine generals. In: Proc. of the 24th IEEE Symp. on Foundations of Computer Science, pp. 403–409 (1983)
Riis, S.: Graph entropy, network coding and guessing games. Technical Report 0711.4175, arxiv.org (2007), http://arxiv.org/abs/0711.4175
Shamir, A.: How to share a secret. Comm. of the ACM 22, 612–613 (1979)
Shannon, C.E.: Communication theory of secrecy systems. Bell System Technical Journal 28(4), 656–715 (1949)
Simmons, G.J., Jackson, W., Martin, K.M.: The geometry of shared secret schemes. Bulletin of the ICA 1, 71–88 (1991)
Waters, B.: Ciphertext-policy attribute-based encryption: An expressive, efficient, and provably secure realization. Technical Report 2008/290, Cryptology ePrint Archive (2008), http://eprint.iacr.org/
Xu, W., Wang, J., Sun, J.: A projection method for derivation of non-Shannon-type information inequalities. In: ISIT 2008, pp. 2116–2120 (2008)
Yeung, R.W.: A First Course in Information Theory. Springer, Heidelberg (2006)
Zhang, Z.: On a new non-Shannon type information inequality. Communications in Information and Systems 3(1), 47–60 (2003)
Zhang, Z., Yeung, R.W.: On characterization of entropy function via information inequalities. IEEE Trans. on Info. Theory 44(4), 1440–1452 (1998)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Beimel, A., Orlov, I. (2009). Secret Sharing and Non-Shannon Information Inequalities . In: Reingold, O. (eds) Theory of Cryptography. TCC 2009. Lecture Notes in Computer Science, vol 5444. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-00457-5_32
Download citation
DOI: https://doi.org/10.1007/978-3-642-00457-5_32
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-00456-8
Online ISBN: 978-3-642-00457-5
eBook Packages: Computer ScienceComputer Science (R0)