Abstract
Computing the information rate of access structures is an important part of the research of secret sharing schemes. In this paper, we investigate two combinatorial approaches of computing upper bounds on the information rate of access structures - the Csirmaz’s polymatroid approach and the independent sequence approach. We prove that the Csirmaz’s polymatroid approach is only a special variant of the independent sequence approach, and finding an independent sequence with respect to a graph-based access structure with maximum length is equivalent to finding a maximum alternating cycle-free matching in a bipartite graph, which is a NP hard problem.
Supported by National Natural Science Foundation of China (Grant No. 60573004) and National Basic Research Program of China (973 Program, Grant No. 2007CB311202).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Blakley, G.R.: Safeguarding cryptographic keys. In: Proc. AFIPS 1979 Nat. Computer Conf., vol. 48, pp. 313–317 (1979)
Blundo, C., De Santis, A., De Simone, R., Vaccaro, U.: Tight bounds on the information rate of secret sharing schemes. Designs, Codes and Cryptography 11(2), 107–110 (1997)
Blundo, C., De Santis, A., Gaggia, A.G., Vaccaro, U.: New bounds on the information rate of secret sharing schemes. IEEE Transactions on Information Theory IT-41(2), 549–554 (1995)
Blundo, C., De Santis, A., Gargano, L., Vaccaro, U.: On the information rate of secret sharing schemes. In: Brickell, E.F. (ed.) CRYPTO 1992. LNCS, vol. 740, pp. 148–167. Springer, Heidelberg (1993)
Blundo, C., De Santis, A., Stinson, D.R., Vaccaro, U.: Graph decompositions and secret sharing schemes. In: Rueppel, R.A. (ed.) EUROCRYPT 1992. LNCS, vol. 658, pp. 1–24. Springer, Heidelberg (1993)
Brickell, E.F., Stinson, D.R.: Some improved bounds on the information rate of perfect secret sharing schemes. Journal of Cryptology 5(3), 153–166 (1992)
Capocelli, R.M., De Santis, A., Gargano, L., Vaccaro, U.: On the size of shares for secret sharing schemes. Journal of Cryptology 6(3), 157–169 (1993)
Csirmaz, L.: The size of a share must be large. Journal of Cryptology 10(4), 223–231 (1997)
Csirmaz, L., Tardos, G.: Secret sharing on trees: problem solved. Cryptology ePrint Archive, Report 2009/071 (2009), http://eprint.iacr.org/
Dahlhaus, E.: The computation of the jump number of convex graphs. In: Bouchitté, V., Morvan, M. (eds.) ORDAL 1994. LNCS, vol. 831, pp. 176–185. Springer, Heidelberg (1994)
Ito, M., Saito, A., Nishizeki, T.: Secret sharing schemes realizing general access structure. In: Proc. IEEE Global Telecommunication Conf., Globecom 1987, pp. 99–102 (1987)
Karnin, E.D., Greene, J.W., Hellman, M.E.: On secret sharing systems. IEEE Transactions on Information Theory IT-29(1), 35–41 (1983)
Müller, H.: Alternating cycle-free matchings. Order 7(1), 11–21 (1990)
Oxley, J.G.: Matroid Theory. Oxford University Press, New York (1992)
Shamir, A.: How to share a secret. Communications of the ACM 22(11), 612–613 (1979)
van Dijk, M.: On the information rate of perfect secret sharing schemes. Designs, Codes and Cryptography 6(2), 143–169 (1995)
Welsh, D.J.A.: Matroid Theory. Academic, London (1976)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Zhou, Z. (2011). On the Combinatorial Approaches of Computing Upper Bounds on the Information Rate of Secret Sharing Schemes. In: Lai, X., Yung, M., Lin, D. (eds) Information Security and Cryptology. Inscrypt 2010. Lecture Notes in Computer Science, vol 6584. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-21518-6_9
Download citation
DOI: https://doi.org/10.1007/978-3-642-21518-6_9
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-21517-9
Online ISBN: 978-3-642-21518-6
eBook Packages: Computer ScienceComputer Science (R0)