Document Type : Review Article


1 Faculty of Basic Science, Islamic Azad University-Khorramabad Branch, Khorramabad, Iran.

2 Information Science Research Department, Iranian Research Institute for Information Science and Technology, Tehran, Iran.

3 Faculty and Research Center of Communication and Information Technology, Imam Hossein University, Tehran, Iran.


Secret sharing (SS) schemes allow the sharing of a secret among a set of trustees in such a way that only some qualified subsets of them can recover the secret. Ordinary SS schemes assume that the trust to each trustee is fixed over time. However, this is not the case in many real scenarios. Social secret sharing (SSS) is a recently introduced type of SS that addresses this issue. It allows the sharing of a secret among a set of trustees such that the amount of trust to each participant could be changed over time. There exist only a few SSS schemes in the literature; most of them can share only one secret during each execution. Hence, these schemes lack the required efficiency in situations where multiple secrets need to be shared. According to the literature, there exists only one social multi-secret sharing (SMSS) scheme in which, all the secrets are reconstructed at one stage. However, in many applications, the secrets should be recovered in multiple stages and even according to some specified order. To address these problems, this paper employs Birkhoff interpolation method and Chinese remainder theorem and proposes a new SMSS scheme. In the proposed scheme, the shareholders can recover the secrets in different stages and according to the specified order by the dealer. The security analysis of the proposed scheme shows that it provides all the needed security requirements. In addition, the performance analysis of the proposed scheme indicates its overall superiority over the related schemes.


[1] Adi Shamir. How to share a secret. Communications of the ACM, 22(11):612–613, 1979.
[2] George Robert Blakley. Safeguarding cryptographic keys. In Managing Requirements Knowledge, International Workshop on, pages 313–313.
IEEE Computer Society, 1979.
[3] Benny Chor, Shafi Goldwasser, Silvio Micali, and Baruch Awerbuch. Verifiable secret sharing and achieving simultaneity in the presence of faults. In 26th Annual Symposium on Foundations of Computer Science (sfcs 1985), pages 383–395. IEEE, 1985.
[4] Lidong Zhou, Fred B Schneider, and Robbert Van Renesse. Apss: Proactive secret sharing in asynchronous systems. ACM transactions on information and system security (TISSEC), 8(3):259–286, 2005.
[5] David Schultz, Barbara Liskov, and Moses Liskov. Mpss: mobile proactive secret sharing. ACM Transactions on Information and System Security (TISSEC), 13(4):1–32, 2010.
[6] Lein Harn. Efficient sharing (broadcasting) of multiple secrets. IEE Proceedings-Computers and Digital Techniques, 142(3):237–240, 1995.
[7] Chou-Chen Yang, Ting-Yi Chang, and MinShiang Hwang. A (t, n) multi-secret sharing scheme. Applied Mathematics and Computation, 151(2):483–490, 2004.
[8] Liao-Jun Pang and Yu-Min Wang. A new (t, n) multi-secret sharing scheme based on shamir’s secret sharing. Applied Mathematics and Computation, 167(2):840–848, 2005.
[9] Jianjie Zhao, Jianzhong Zhang, and Rong Zhao. A practical verifiable multi-secret sharing scheme. Computer Standards & Interfaces, 29(1):138–141, 2007.
[10] Massoud Hadian Dehkordi and Samaneh Mashhadi. An efficient threshold verifiable multisecret sharing. Computer Standards & Interfaces, 30(3):187–190, 2008.
[11] Ziba Eslami and Saideh Kabiri Rad. A new verifiable multi-secret sharing scheme based on bilinear maps. Wireless Personal Communications, 63(2):459–467, 2012.
[12] Massoud Hadian Dehkordi and Samaneh Mashhadi. New efficient and practical verifiable multisecret sharing schemes. Information Sciences, 178(9):2262–2274, 2008.
[13] Ali Nakhaei Amroudi, Ali Zaghain, and Mahdi Sajadieh. A verifiable (k, n, m)-threshold multi-secret sharing scheme based on ntru cryptosystem. Wireless Personal Communications, 96(1):1393–1405, 2017.
[14] Nasrollah Pakniat, Mahnaz Noroozi, and Ziba Eslami. Reducing multi-secret sharing problem to sharing a single secret based on cellular automata. The CSI Journal on Computer Science and Engineering, 14(1), 2017.
[15] Massoud Hadian Dehkordi and Hossein Oraei. How to construct a verifiable multi-secret sharing scheme based on graded encoding schemes. IET Information Security, 13(4):343–351, 2019.
[16] Huanping Liu, Yixian Yang, and Fangchun Yang. Multistage secret sharing based on one-way function. Electronics Letters, 21(4):561–564, 1999.
[17] Hossein Pilaram and Taraneh Eghlidos. An efficient lattice based multi-stage secret sharing scheme. IEEE Transactions on Dependable and Secure Computing, 14(1):2–8, 2015.
[18] Mitra Fatemi, Reza Ghasemi, Taraneh Eghlidos, and Mohammad Reza Aref. Efficient multistage secret sharing scheme using bilinear map. IET Information Security, 8(4):224–229, 2014.
[19] Samaneh Mashhadi. New multi-stage secret sharing in the standard model. Information Processing Letters, 127:43–48, 2017.
[20] Samaneh Mashhadi, Massoud Hadian Dehkordi, and Niloofar Kiamari. Provably secure verifiable multi-stage secret sharing scheme based on monotone span program. IET Information Security, 11(6):326–331, 2017.
[21] Massoud Hadian Dehkordi, Samaneh Mashhadi, and Hossein Oraei. A proactive multi stage secret sharing scheme for any given access structure. Wireless Personal Communications, 104(1):491–503, 2019.
[22] Jamal Zarepour-Ahmadabadi, MohammadEbrahim Shiri-Ahmadabadi, and Alimohammad Latif. A cellular automata-based multi-stage secret image sharing scheme. Multimedia Tools and Applications, 77(18):24073–24096, 2018.
[23] Samaneh Mashhadi. Computationally secure multiple secret sharing: Models, schemes, and formal security analysis. The ISC International Journal of Information Security, 7(2):91–99, 2015.
[24] Amir Herzberg, Stanis law Jarecki, Hugo Krawczyk, and Moti Yung. Proactive secret sharing or: How to cope with perpetual leakage. In annual international cryptology conference, pages 339–352. Springer, 1995.
[25] Carles Padr´o and Germ´an S´aez. Secret sharing schemes with bipartite access structure. IEEE Transactions on Information Theory, 46(7):2596–2604, 2000.
[26] Tamir Tassa. Hierarchical threshold secret sharing. Journal of cryptology, 20(2):237–264, 2007.
[27] Tamir Tassa and Nira Dyn. Multipartite secret sharing by bivariate interpolation. Journal of Cryptology, 22(2):227–258, 2009.
[28] Ziba Eslami, Nasrollah Pakniat, and Mahnaz Noroozi. Hierarchical threshold multi-secret sharing scheme based on birkhoff interpolation and cellular automata. In 2015 18th CSI International Symposium on Computer Architecture and
Digital Systems (CADS), pages 1–6. IEEE, 2015.
[29] Nasrollah Pakniat, Mahnaz Noroozi, and Ziba Eslami. Distributed key generation protocol with hierarchical threshold access structure. IET Information Security, 9(4):248–255, 2015.
[30] Mehrdad Nojoumian, Douglas R Stinson, and Morgan Grainger. Unconditionally secure social secret sharing scheme. IET information security, 4(4):202–211, 2010.
[31] Douglas R Stinson and Ruizhong Wei. Unconditionally secure proactive secret sharing scheme with combinatorial structures. In International Workshop on Selected Areas in Cryptography, pages 200–214. Springer, 1999.
[32] Mehrdad Nojoumian and Douglas R Stinson. Socio-rational secret sharing as a new direction in rational cryptography. In International Conference on Decision and Game Theory for Security, pages 18–37. Springer, 2012.
[33] Mehrdad Nojoumian and Douglas R Stinson. Social secret sharing in cloud computing using a new trust function. In 2012 Tenth Annual International Conference on Privacy, Security and Trust, pages 161–167. IEEE, 2012.
[34] Ziba Eslami, Nasrollah Pakniat, and Mehrdad Nojoumian. Ideal social secret sharing using birkhoff interpolation method. Security and Communication Networks, 9(18):4973–4982, 2016.
[35] Nasrollah Pakniat and Ziba Eslami. Verifiable social multi-secret sharing secure in active adversarial model. Journal of Computing and Security, 4(1):3–12, 2017.
[36] Henri Cohen. A course in computational algebraic number theory, volume 8. Springer-Verlag Berlin, 1993.
[37] Lein Harn, Miao Fuyou, and Chin-Chen Chang. Verifiable secret sharing based on the chinese remainder theorem. Security and Communication Networks, 7(6):950–957, 2014.
[38] Wei Hua and Xiaofeng Liao. A secret image sharing scheme based on piecewise linear chaotic map and chinese remainder theorem. Multimedia Tools and Applications, 76(5):7087–7103, 2017.
[39] Mehrdad Nojoumian and Timothy C Lethbridge. A new approach for the trust calculation in social networks. In International Conference on E-Business and Telecommunication Networks, pages 64–77. Springer, 2006.
[40] Jamal Zarepour-Ahmadabadi, MohammadEbrahim Shiri-Ahmadabadi, Ali Miri, and AliMohammad Latif. A new gradual secret sharing scheme with diverse access structure. Wireless Personal Communications, 99(3):1329–1344, 2018.
[41] Virginia Vassilevska Williams. Multiplying matrices faster than coppersmith-winograd. In Proceedings of the forty-fourth annual ACM symposium on Theory of computing, pages 887–898, 2012.