Proactive multi-secret sharing scheme based on Lagrange interpolation and Chinese remainder theorem

Subject Areas : Statistics

Mohammad Ebrahim Ebrahimi Kiasari ¹ , Abdolrasoul Mirghadri ² , Nasrollah Pakniat ³ , Mojtaba Nazari ⁴

1 - Faculty of Basic Science, Islamic Azad University-Khorramabad Branch, Khorramabad,Iran
2 - Faculty and Research Center of Communication and Information Technology, Imam Hossein University, Tehran, Iran
3 - Information Science Research Center, Iranian Research Institute for Information Science and Technology (IranDoc), Tehran, Iran
4 - Faculty of Basic Science, Islamic Azad University- Khorramabad Branch, Khorramabad, Iran

Received: 2019-07-28 Accepted : 2020-01-09 Published : 2021-02-19

Keywords: درونیابی لاگرانژ, امنیت پیش‌نگر, وارسی‌پذیری, قضیه باقیمانده چینی, تسهیم چندراز,

Abstract :

In a proactive secret sharing scheme, a set of secrets are distributed among a set of participants in such a way that: 1) the participants’ shares could be renewed in certain time periods without the aid of the dealer, and 2) while some specific subsets of the participants, called authorized subsets, are able to reconstruct the secrets, other subsets could not obtain any information about the secrets. To the best of our knowledge, there exists only one proactive multi-secret sharing scheme in the literature. This scheme can be considered as the combination of a well-known proactive (single) secret sharing scheme and the one-time-pad encryption system. This scheme is only weakly secure meaning that the disclosure or reconstruction of one of the secrets in this scheme would be lead to the disclosure of all the secrets. In addition to being weakly secure, this scheme reconstructs all the secrets at once and does not provide gradual reconstruction of the secrets. To solve these problems, we use Lagrange interpolation and the Chinese remainder theorem in this paper and propose a new proactive multi-secret sharing scheme. The proposed scheme is a strongly secure proactive multi-secret sharing scheme. It allows gradual reconstruction of the secrets in a predetermined order and provides verifiability using the intractability of discrete logarithm problem.

References:

 

[1]     Shamir, A. (1979). How to share a secret. Communications of the ACM, 22(11), 612-613.

[2]     Blakley, G. R. (1979, June). Safeguarding cryptographic keys. In Proceedings of the national computer conference (Vol. 48, No. 313).

[3]     Chor, B., Goldwasser, S., Micali, S., & Awerbuch, B. (1985, October). Verifiable secret sharing and achieving simultaneity in the presence of faults. In 26th Annual Symposium on Foundations of Computer Science (sfcs 1985) (pp. 383-395). IEEE.

[4]     Ostrovsky, R., & Yung, M. (1991, August). How to withstand mobile virus attacks. In PODC (Vol. 91, pp. 51-59).

[5]     Herzberg, A., Jarecki, S., Krawczyk, H., & Yung, M. (1995, August). Proactive secret sharing or: How to cope with perpetual leakage. In Annual International Cryptology Conference (pp. 339-352). Springer, Berlin, Heidelberg.

[6]     Feng, B., Guo, C., Li, M., & Wang, Z. H. (2015). A Novel Proactive Multi-secret Sharing Scheme. IJ Network Security, 17(2), 123-128.

[7]     Pakniat N., Noroozi M., & Eslami Z. (2016). Reducing Multi-Secret Sharing Problem to Sharing a Single Secret Based on Cellular Automata. Journal on Computer Science and Engineering, 14(1), 38 - 43.

[8]     Min, X. C. X. W. S., & Zhen, X. G. (2002). A Secret Sharing Scheme with Periodic Renewing to Identify Cheaters. Chinese Journal of Computers, 6.

[9]     Zhou, L., Schneider, F. B., & Van Renesse, R. (2005). APSS: Proactive secret sharing in asynchronous systems. ACM transactions on information and system security (TISSEC), 8(3), 259-286.

[10]  Schultz, D., Liskov, B., & Liskov, M. (2010). MPSS: mobile proactive secret sharing. ACM Transactions on Information and System Security (TISSEC), 13(4), 34.

[11]  Nikov, V., Nikov, S., Preneel, B., & Vandewalle, J. (2002). Applying General Access Structure to Proactive Secret Sharing Schemes. IACR Cryptology ePrint Archive, 2002, 141.

[12]  Nojoumian, M., Stinson, D. R., & Grainger, M. (2010). Unconditionally secure social secret sharing scheme. IET information security, 4(4), 202-211.

[13]  Eslami, Z., Pakniat, N., & Nojoumian, M. (2016). Ideal social secret sharing using Birkhoff interpolation method. Security and Communication Networks, 9(18), 4973-4982.

[14]  Pakniat, N., & Eslami, Z. (2017). Verifiable Social Multi-Secret Sharing Secure in Active Adversarial Model. Journal of Computing and Security, 4(1), 3-12.

[15]  Harn, L. (1995). Efficient sharing (broadcasting) of multiple secrets. IEE Proceedings-Computers and Digital Techniques, 142(3), 237-240.

[16]  Eslami, Z., Pakniat, N., & Noroozi, M. (2015, October). 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) (pp. 1-6). IEEE.

[17]  Eslami, Z., & Rad, S. K. (2012). A new verifiable multi-secret sharing scheme based on bilinear maps. Wireless Personal Communications, 63(2), 459-467.

[18]  Mashhadi, S., & Dehkordi, M. H. (2015). Two verifiable multi secret sharing schemes based on nonhomogeneous linear recursion and LFSR public-key cryptosystem. Information Sciences, 294, 31-40.

[19]  Liu, Y., Zhang, F., & Zhang, J. (2016). Attacks to some verifiable multi-secret sharing schemes and two improved schemes. Information Sciences, 329, 524-539.

[20]  Dehkordi, M. H., & Oraei, H. (2019). How to construct a verifiable multi-secret sharing scheme based on graded encoding schemes. IET Information Security.

[21]  Tentu, A. N., Venkaiah, V. C., & Prasad, V. K. (2018). CRT based multi-secret sharing schemes: revisited. International Journal of Security and Networks, 13(1), 1-9.

[22]  Zarepour-Ahmadabadi, J., Shiri-Ahmadabadi, M., Miri, A., & Latif, A. (2018). A new gradual secret sharing scheme with diverse access structure. Wireless Personal Communications, 99(3), 1329-1344.

[23]  Cohen, H. (2013). A course in computational algebraic number theory (4th ed., vol. 138). Berlin: Springer.

[24]    Feldman, P. (1987, October). A practical scheme for non-interactive verifiable secret sharing. In 28th Annual Symposium on Foundations of Computer Science (sfcs 1987) (pp. 427-438). IEEE.