Computationally secure multiple secret sharing: models, schemes, and formal security analysis



Department of Mathematics, Iran University of Science & Technology, Tehran, Iran.


A multi-secret sharing scheme (MSS) allows a dealer to share multiple secrets among a set of participants. in such a way a multi-secret sharing scheme (MSS) allows a dealer to share multiple secrets among a set of participants, such that any authorized subset of participants can reconstruct the secrets. Up to now, existing MSSs either require too long shares for participants to be perfect secure, or do not have a formal security analysis/proof. In 2013, Herranz et al. provided the first formal definition of computational security for multi-stage secret sharing scheme (MSSS) in the standard model and proposed a practical and secure scheme. As far as we know, their scheme is the only computationally secure MSS in the standard model, and there is no formal definition of the computational security for other categories of MSSs. Based on this motivation, in this paper, we define the first formal model of indistinguishability against the chosen secret attacks (CSA) for other types of MSSs in the standard model. Furthermore, we present two practical CSA-secure MSSs, belonging to different types of MSSs and enjoying the advantage of short shares. They are also provably secure in the standard model. Based on the semantic security of the underlying encryption schemes, we prove the security of our schemes.


[1] M. Bellare, A. Boldyreva, S. Micali, Public-key encryption in a multi-user setting: Security proofs and improvements, in: Proceeding of Euro-crypt'00, in: LNCS, 1807, Springer-Verlag, 2000, pp. 259-274.

[2] M. Bellare, A. Desai, E. Jokipii, P. Rogaway, A concrete security treatment of symmetric encryption, in: FOCS'97, IEEE Society Press, 1997, pp. 394-403.

[3] M. Bellare, P. Rogaway, Introduction to modern cryptography, Notes for the course CSE207 of the University of California, San Diego, available at, visited at November 2012.

[4] C. Cachin, On-line secret sharing, in Proceedings of IMA Conference'95, in: LNCS, 1025, Springer-Verlag, 1995, pp. 190-198.

[5] T.Y. Chang, M. S. Hwang, W. P.Yang, A new multi-stage secret sharing scheme using one-way function, ACM SIGOPS Operating Systems, 39, 2005, pp. 48-55.

[6] H.-Y. Chien, J.-K. Jan, Y.-M. Tseng, A practical (t, n) multi-secret sharing scheme, IEICE Transactions on Fundamentals of Electronics, Communications and Computer 83-A, 12, 2000, pp. 2762-2765.

[7] M. H. Dehkordi, S. Mashhadi, New efficient and practical verifiable multi-secret sharing schemes, Information Sciences 178, 9, 2008, pp. 2262-2274.

[8] J. He, E. Dawson, Multistage secret sharing based on one-way function, Electronics Letters 30, 19, 1994, pp. 1591-1592.

[9] J. Herranz, A. Ruiz, G. Sáez, Sharing many secrets with computational provable security, Information Processing Letters 113, 2013, pp. 572-579.

[10] C. Hu, X. Liao, X. Cheng, Verifiable multi-secret sharing based on LFSR sequences, Theoret. Commun. Sci. 445, 2012, pp. 52-62.

[11] M. Karchmer, A. Wigderson, On Span Programs, in: Proceeding of SCTC'93, IEEE Computer Society Press, 1993, pp. 102-111.

[12] J. Katz, Y. Lindell, Introduction to Modern Cryptography, Chapman & Hall/CRC, New York, 2008.

[13] J. Katz, M. Yung, Characterization of security notions for probabilistic private-key encryption, Journal of Cryptology, 19, 2006, pp. 67-95.

[14] H. Krawczyk, Secret sharing made short, in: Proceedings of Crypto'93, in LNCS, 773, Springer-Verlag, 1993, pp. 136-146.

[15] H. X. Li, C. T. Cheng, L. J. Pang, An improved Multi-stage (t, n)-threshold secret sharing scheme, LNCS 3739, 2005, pp. 267-274.

[16] H. Y. Lin, Y. S. Yeh, Dynamic multi-secret sharing scheme, Int. J. Contemp. Math. Sciences, 3, 2008, pp. 37-42.

[17] S. Mashhadi, M. Hadian Dehkordi, Two verifiable multi secret sharing schemes based on nonhomogeneous linear recursion and LFSR public-key cryptosystem, Information Sciences 294, 2015, pp. 31-40.

[18] B. Masucci, Sharing multiple secret: Models, schemes and analysis, Designs, Codes and Cryptography, 39, 2006, pp. 89-111.

[19] A. Shamir, How to share a secret, Communications of the ACM. 22, 1979, pp. 612-613.

[20] C.-C. Yang, T.-Y. Chang, M.-S. Hwang, A (t, n) multi-secret sharing scheme, Applied Mathematics and Computation 151, 2004, pp. 483-490.