Ideal Multipartite Secret Sharing Schemes
Tóm tắt
Multipartite secret sharing schemes are those having a multipartite access structure, in which the set of participants is divided into several parts and all participants in the same part play an equivalent role. In this work, the characterization of ideal multipartite access structures is studied with all generality. Our results are based on the well-known connections between ideal secret sharing schemes and matroids and on the introduction of a new combinatorial tool in secret sharing, integer polymatroids . Our results can be summarized as follows. First, we present a characterization of multipartite matroid ports in terms of integer polymatroids. As a consequence of this characterization, a necessary condition for a multipartite access structure to be ideal is obtained. Second, we use representations of integer polymatroids by collections of vector subspaces to characterize the representable multipartite matroids. In this way we obtain a sufficient condition for a multipartite access structure to be ideal, and also a unified framework to study the open problems about the efficiency of the constructions of ideal multipartite secret sharing schemes. Finally, we apply our general results to obtain a complete characterization of ideal tripartite access structures, which was until now an open problem.
Tài liệu tham khảo
A. Beimel, T. Tassa, E. Weinreb, Characterizing ideal weighted threshold secret sharing. SIAM J. Discrete Math. 22(1), 600–619 (2008)
M. Belenkiy, Disjunctive multi-level secret sharing, Cryptology ePrint Archive, report 2008/018, http://eprint.iacr.org/2008/018
J. Benaloh, J. Leichter, Generalized secret sharing and monotone functions, in Advances in Cryptology—CRYPTO ’88. Lecture Notes in Comput. Sci., vol. 403, pp. 27–35 (1990)
A. Beutelspacher, F. Wettl, On 2-level secret sharing. Des. Codes Cryptogr. 3, 127–134 (1993)
G.R. Blakley, Safeguarding cryptographic keys, in AFIPS Conference Proceedings, vol. 48, pp. 313–317 (1979)
C. Blundo, A. De Santis, L. Gargano, U. Vaccaro, On the information rate of secret sharing schemes, in Advances in Cryptology—CRYPTO ’92. Lecture Notes in Comput. Sci., vol. 740, pp. 148–167 (1993)
E.F. Brickell, Some ideal secret sharing schemes. J. Comb. Math. Comb. Comput. 9, 105–113 (1989)
E.F. Brickell, D.M. Davenport, On the classification of ideal secret sharing schemes. J. Cryptol. 4, 123–134 (1991)
R.M. Capocelli, A. De Santis, L. Gargano, U. Vaccaro, On the size of shares of secret sharing schemes. J. Cryptol. 6, 157–168 (1993)
M.J. Collins, A note on ideal tripartite access structures, Cryptology ePrint Archive, report no. 2002/193, http://eprint.iacr.org/2002/193
L. Csirmaz, The size of a share must be large. J. Cryptol. 10, 223–231 (1997)
O. Farràs, C. Padró, Ideal hierarchical secret sharing schemes, in 7th Theory of Cryptography Conference, TCC 2010. Lecture Notes in Comput. Sci., vol. 5978, pp. 219–236 (2010)
S. Fujishige, Submodular Functions and Optimization. Ann. Discrete Math., vol. 47, (North-Holland/Elsevier, Amsterdam, 1991)
M. Giuletti, R. Vincenti, Three-level secret sharing schemes from the twisted cubic. Discrete Math. 310(22), 3236–3240 (2010)
D. Hammer, A.E. Romashchenko, A. Shen, N.K. Vereshchagin, Inequalities for Shannon entropy and Kolmogorov complexity. J. Comput. Syst. Sci. 60, 442–464 (2000)
J. Herranz, G. Sáez, New results on multipartite access structures. IEE Proc. Inf. Secur. 153, 153–162 (2006)
J. Herzog, T. Hibi, Discrete polymatroids. J. Algebr. Comb. 16, 239–268 (2002)
M. Ito, A. Saito, T. Nishizeki, Secret sharing scheme realizing any access structure, in Proc. IEEE Globecom ’87 (1987), pp. 99–102
W.-A. Jackson, K.M. Martin, Perfect secret sharing schemes on five participants. Des. Codes Cryptogr. 9, 267–286 (1996)
E.D. Karnin, J.W. Greene, M.E. Hellman, On secret sharing systems. IEEE Trans. Inf. Theory 29, 35–41 (1983)
S.C. Kothari, Generalized linear threshold scheme, in Advances in Cryptology—CRYPTO ’84. Lecture Notes in Comput. Sci., vol. 196, pp. 231–241 (1985)
A. Lehman, A solution of the Shannon switching game. J. Soc. Ind. Appl. Math. 12, 687–725 (1964)
J. Martí-Farré, C. Padró, Secret sharing schemes with three or four minimal qualified subsets. Des. Codes Cryptogr. 34, 17–34 (2005)
J. Martí-Farré, C. Padró, On secret sharing schemes, matroids and polymatroids. J. Math. Cryptol. 4, 95–120 (2010)
J.L. Massey, Minimal codewords and secret sharing, in Proceedings of the 6-th Joint Swedish–Russian Workshop on Information Theory (1993), pp. 269–279
J.L. Massey, Some applications of coding theory in cryptography, in Codes and Ciphers: Cryptography and Coding IV, Formara Ltd., Essex, England (1995), pp. 33–47
F. Matúš, Matroid representations by partitions. Discrete Math. 203, 169–194 (1999)
P. Morillo, C. Padró, G. Sáez, J.L. Villar, Weighted threshold secret sharing schemes. Inf. Process. Lett. 70, 211–216 (1999)
K. Murota, Discrete Convex Analysis. SIAM Monographs on Discrete Mathematics and Applications (SIAM, Philadelphia, 2003)
S.-L. Ng, A representation of a family of secret sharing matroids. Des. Codes Cryptogr. 30, 5–19 (2003)
S.-L. Ng, Ideal secret sharing schemes with multipartite access structures. IEE Proc. Commun. 153, 165–168 (2006)
S.-L. Ng, M. Walker, On the composition of matroids and ideal secret sharing schemes. Des. Codes Cryptogr. 24, 49–67 (2001)
J.G. Oxley, Matroid Theory. Oxford Science Publications (Clarendon Oxford University Press, New York, 1992)
C. Padró, G. Sáez, Secret sharing schemes with bipartite access structure. IEEE Trans. Inf. Theory 46, 2596–2604 (2000)
A. Schrijver, Combinatorial Optimization. Polyhedra and Efficiency (Springer, Berlin, 2003)
P.D. Seymour, A forbidden minor characterization of matroid ports. Q. J. Math. Oxf. Ser. 27, 407–413 (1976)
P.D. Seymour, On secret-sharing matroids. J. Comb. Theory, Ser. B 56, 69–73 (1992)
A. Shamir, How to share a secret. Commun. ACM 22, 612–613 (1979)
G.J. Simmons, How to (really) share a secret. Advances in Cryptology—CRYPTO 88. Lecture Notes in Comput. Sci., vol. 403, pp. 390–448 (1990)
J. Simonis, A. Ashikhmin, Almost affine codes. Des. Codes Cryptogr. 14, 179–197 (1998)
D.R. Stinson, An explication of secret sharing schemes. Des. Codes Cryptogr. 2, 357–390 (1992)
T. Tassa, Hierarchical threshold secret sharing. J. Cryptol. 20, 237–264 (2007)
T. Tassa, N. Dyn, Multipartite secret sharing by bivariate interpolation. J. Cryptol. 22, 227–258 (2009)
D.J.A. Welsh, Matroid Theory (Academic Press, London, 1976)