تسهیم چندراز پیش‌نگر با استفاده از درونیابی لاگرانژ و قضیه باقیمانده چینی
محورهای موضوعی : آمارمحمد ابراهیم ابراهیمی کیاسری 1 , عبدالرسول میرقدری 2 , نصراله پاک‌نیت 3 , مجتبی نظری 4
1 - گروه ریاضی، واحد خرم‌آباد، دانشگاه آزاد اسلامی، خرم‌آباد، ایران
2 - دانشکده و پژوهشکده فناوری اطلاعات و ارتباطات، دانشگاه جامع امام حسین(ع)، تهران، ایران
3 - پژوهشکده علوم اطلاعات، پژوهشگاه علوم و فناوری اطلاعات ایران (ایرانداک)، تهران، ایران
4 - گروه ریاضی، واحد خرم‌آباد، دانشگاه آزاد اسلامی، خرم‌آباد، ایران
کلید واژه: Lagrange interpolation, Multi-secret sharing, Chinese remainder theorem, Verifiability, Proactive security,
چکیده مقاله :
در یک طرح تسهیم چندراز پیش‌نگر، یک یا چند راز به گونه‌ای بین مجموعه‌ای از شرکت‌کنندگان تسهیم می‌شود که 1) امکان نوسازی سهام در فواصل زمانی مشخص بدون کمک تسهیم‌کننده وجود داشته باشد و 2) در حالی که زیرمجموعه‌هایی مشخص از شرکت‌کنندگان به نام زیرمجموعه‌های مجاز قادر به بازسازی راز(ها) هستند، سایر زیرمجموعه‌ها قادر به کسب اطلاع در مورد راز(ها) نباشند. تنها طرح تسهیم چندراز پیش‌نگر موجود را می‌توان به عنوان ترکیبی از یک طرح تسهیم (تک) راز پیش‌نگر شناخته شده و چندین بار استفاده از سیستم رمزنگاری یک بار مصرف در نظر گرفت. این طرح دارای امنیت ضعیف است. به عبارت دیگر، افشا یا بازسازی یک یا چند راز در این طرح منجر به افشای سایر رازها می‌شود. علاوه براین، در این طرح، امکان بازسازی تدریجی رازها وجود نداشته و در آن تمام رازها به صورت هم‌زمان بازسازی می‌شوند. برای حل این مشکلات، در این مقاله با استفاده از درونیابی لاگرانژ، قضیه باقیمانده چینی و سختی مساله لگاریتم گسسته یک طرح تسهیم چندراز پیش‌نگر جدید ارائه شده که امکان بازسازی تدریجی رازها با ترتیبی از پیش تعیین شده را فراهم می‌کند. همچنین با توجه به سختی مساله لگاریتم گسسته، این طرح ویژگی وارسی‌پذیری را برآورده کرده و دارای امنیت قوی است.
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.
[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.