Abstract
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. Secret sharing schemes for multipartite access structures have received considerable attention due to the fact that multipartite secret sharing can be seen as a natural and useful generalization of threshold secret sharing.
This work deals with efficient and explicit constructions of ideal multipartite secret sharing schemes, while most of the known constructions are either inefficient or randomized. Most ideal multipartite secret sharing schemes in the literature can be classified as either hierarchical or compartmented. The main results are the constructions for ideal hierarchical access structures, a family that contains every ideal hierarchical access structure as a particular case such as the disjunctive hierarchical threshold access structure and the conjunctive hierarchical threshold access structure, and the constructions for compartmented access structures with upper bounds and compartmented access structures with lower bounds, two families of compartmented access structures.
On the basis of the relationship between multipartite secret sharing schemes, polymatroids, and matroids, the problem of how to construct a scheme realizing a multipartite access structure can be transformed to the problem of how to find a representation of a matroid from a presentation of its associated polymatroid. In this paper, we give efficient algorithms to find representations of the matroids associated to the three families of multipartite access structures. More precisely, based on know results about integer polymatroids, for each of the three families of access structures, we give an efficient method to find a representation of the integer polymatroid over some finite field, and then over some finite extension of that field, we give an efficient method to find a presentation of the matroid associated to the integer polymatroid. Finally, we construct ideal linear schemes realizing the three families of multipartite access structures by efficient methods.
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
Similar content being viewed by others
References
Ball, S., Padró, C., Weiner, Z., Xing, C.: On the representability of the biuniform matroid. SIAM J. Discrete Math. 27(3), 1482–1491 (2013)
Beimel, A.: Secret-sharing schemes: a survey. In: Chee, Y.M., et al. (eds.) IWCC 2011. LNCS, vol. 6639, pp. 11–46. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-20901-7_2
Beimel, A., Chor, B.: Universally ideal secret sharing schemes. IEEE Trans. Inf. Theory 40(3), 786–794 (1994)
Beimel, A., Tassa, T., Weinreb, E.: Characterizing ideal weighted threshold secret sharing. SIAM J. Discrete Math. 22(1), 360–397 (2008)
Ben-Or, M., Goldwasser, S., Wigderson, A.: Completeness theorems for noncryptographic fault-tolerant distributed computations. In: Proceedings of the 20th ACM Symposium on the Theory of Computing, pp. 1–10 (1988)
Benaloh, J., Leichter, J.: Generalized secret sharing and monotone functions. In: Goldwasser, S. (ed.) CRYPTO 1988. LNCS, vol. 403, pp. 27–35. Springer, New York (1990). https://doi.org/10.1007/0-387-34799-2_3
Beutelspacher, A., Wettl, F.: On 2-level secret sharing. Des. Codes Cryptogr. 3(2), 127–134 (1993)
Blakley, G.R.: Safeguarding cryptographic keys. In: Proceedings of the National Computer Conference 1979, AFIPS Proceedings, vol. 48, pp. 313–317 (1979)
Brickell, E.F.: Some ideal secret sharing schemes. J. Combin. Maths. Combin. Comp. 9, 105–113 (1989)
Brickell, E.F., Davenport, D.M.: On the classification of ideal secret sharing schemes. J. Cryptol. 4, 123–134 (1991)
Chaum, D., Crépeau, C., Damgård, I.: Multiparty unconditionally secure protocols. In: Proceedings of the 20th ACM Symposium on the Theory of Computing, pp. 11–19 (1988)
Chor, B., Kushilevitz, E.: Secret sharing over infinite domains. J. Cryptol. 6(2), 87–96 (1993)
Collins, M.J.: A note on ideal tripartite access structures. Cryptology ePrint Archive, Report 2002/193. http://eprint.iacr.org/2002/193
Cramer, R., Damgård, I., Maurer, U.: 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). https://doi.org/10.1007/3-540-45539-6_22
Cramer, R., et al.: On codes, matroids and secure multi-party computation from linear secret sharing schemes. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol. 3621, pp. 327–343. Springer, Heidelberg (2005). https://doi.org/10.1007/11535218_20
Desmedt, Y., Frankel, Y.: Threshold cryptosystems. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 307–315. Springer, New York (1990). https://doi.org/10.1007/0-387-34805-0_28
Farràs, O., Martí-Farré, J., Padró, C.: Ideal multipartite secret sharing schemes. J. Cryptol. 25(3), 434–463 (2012)
Farràs, O., Padró, C.: Ideal hierarchical secret sharing schemes. IEEE Trans. Inf. Theory 58(5), 3273–3286 (2012)
Farràs, O., Padró, C., Xing, C., Yang, A.: Natural generalizations of threshold secret sharing. IEEE Trans. Inf. Theory 60(3), 1652–1664 (2014)
Fehr, S.: Efficient construction of the dual span program. Manuscript, May (1999)
Giulietti, M., Vincenti, R.: Three-level secret sharing schemes from the twisted cubic. Discrete Math. 310(22), 3236–3240 (2010)
Herranz, J., Sáez, G.: New results on multipartite access structures. IEE Proc. Inf. Secur. 153(4), 153–162 (2006)
Herzog, J., Hibi, T.: Discrete polymatroids. J. Algebraic Combinat. 16(3), 239–268 (2002)
Ito, M., Saito, A., Nishizeki, T.: Secret sharing schemes realizing general access structure. In: Proceedings of the IEEE Global Telecommunication Conference, Globecom 1987, pp. 99–102 (1987)
Kothari, S.C.: Generalized linear threshold scheme. In: Blakley, G.R., Chaum, D. (eds.) CRYPTO 1984. LNCS, vol. 196, pp. 231–241. Springer, Heidelberg (1985). https://doi.org/10.1007/3-540-39568-7_19
Massey, J.L.: Minimal codewords and secret sharing. In: Proceedings of the 6th Joint Swedish-Russian Workshop on Information Theory, pp. 276–279 (1993)
Massey, J.L.: Some applications of coding theory in cryptography. Codes and Ciphers: Cryptography and Coding IV, pp. 33–47 (1995)
Oxley, J.G.: Matroid Theory. Oxford Science Publications. The Clarendon Press, Oxford University Press, New York (1992)
Padró, C., Sáez, G.: Secret sharing schemes with bipartite access structure. IEEE Trans. Inf. Theory 46(7), 2596–2604 (2000)
Schrijver, A.: Combinatorial Optimization. Polyhedra and Efficiency. Springer, Berlin (2003)
Shamir, A.: How to share a secret. Commun. ACM 22, 612–613 (1979)
Shankar, B., Srinathan, K., Rangan, C.P.: Alternative protocols for generalized oblivious transfer. In: Rao, S., Chatterjee, M., Jayanti, P., Murthy, C.S.R., Saha, S.K. (eds.) ICDCN 2008. LNCS, vol. 4904, pp. 304–309. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-77444-0_31
Shoup, V.: New algorithm for finding irreducible polynomials over finite fields. Math. Comput. 54, 435–447 (1990)
Simmons, G.J.: How to (really) share a secret. In: Goldwasser, S. (ed.) CRYPTO 1988. LNCS, vol. 403, pp. 390–448. Springer, New York (1990). https://doi.org/10.1007/0-387-34799-2_30
Tassa, T.: Hierarchical threshold secret sharing. J. Cryptol. 20(2), 237–264 (2007)
Tassa, T.: Generalized oblivious transfer by secret sharing. Des. Codes Cryptol. 58(1), 11–21 (2011)
Tassa, T., Dyn, N.: Multipartite secret sharing by bivariate interpolation. J. Cryptol. 22(2), 227–258 (2009)
Welsh, D.J.A.: Matroid Theory. Academic Press, London (1976)
Acknowledgements
The authors would like to thank the reviewers for their helpful comments and suggestions. This research was supported in part by the Foundation of National Natural Science of China (No. 61772147, 61702124), Guangdong Province Natural Science Foundation of major basic research and Cultivation project (No. 2015A030308016), Project of Ordinary University Innovation Team Construction of Guangdong Province (No. 2015KCXTD014), Collaborative Innovation Major Projects of Bureau of Education of Guangzhou City (No. 1201610005) and National Cryptography Development Fund (No. MMJJ20170117).
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 International Association for Cryptologic Research
About this paper
Cite this paper
Chen, Q., Tang, C., Lin, Z. (2019). Efficient Explicit Constructions of Multipartite Secret Sharing Schemes. In: Galbraith, S., Moriai, S. (eds) Advances in Cryptology – ASIACRYPT 2019. ASIACRYPT 2019. Lecture Notes in Computer Science(), vol 11922. Springer, Cham. https://doi.org/10.1007/978-3-030-34621-8_18
Download citation
DOI: https://doi.org/10.1007/978-3-030-34621-8_18
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-34620-1
Online ISBN: 978-3-030-34621-8
eBook Packages: Computer ScienceComputer Science (R0)