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

الموضوعات :

محمد ابراهیم ابراهیمی کیاسری ¹ , عبدالرسول میرقدری ² , نصراله پاک‌نیت ³ , مجتبی نظری ⁴

1 - گروه ریاضی، واحد خرم‌آباد، دانشگاه آزاد اسلامی، خرم‌آباد، ایران
2 - دانشکده و پژوهشکده فناوری اطلاعات و ارتباطات، دانشگاه جامع امام حسین(ع)، تهران، ایران
3 - پژوهشکده علوم اطلاعات، پژوهشگاه علوم و فناوری اطلاعات ایران (ایرانداک)، تهران، ایران
4 - گروه ریاضی، واحد خرم‌آباد، دانشگاه آزاد اسلامی، خرم‌آباد، ایران

تاريخ الإرسال : 25 الأحد , ذو القعدة, 1440 تاريخ التأكيد : 14 الخميس , جمادى الأولى, 1441 تاريخ الإصدار : 07 الجمعة , رجب, 1442

الکلمات المفتاحية: Lagrange interpolation, Multi-secret sharing, Chinese remainder theorem, Verifiability, Proactive security,

ملخص المقالة :

در یک طرح تسهیم چندراز پیش‌نگر، یک یا چند راز به گونه‌ای بین مجموعه‌ای از شرکت‌کنندگان تسهیم می‌شود که 1) امکان نوسازی سهام در فواصل زمانی مشخص بدون کمک تسهیم‌کننده وجود داشته باشد و 2) در حالی که زیرمجموعه‌هایی مشخص از شرکت‌کنندگان به نام زیرمجموعه‌های مجاز قادر به بازسازی راز(ها) هستند، سایر زیرمجموعه‌ها قادر به کسب اطلاع در مورد راز(ها) نباشند. تنها طرح تسهیم چندراز پیش‌نگر موجود را می‌توان به عنوان ترکیبی از یک طرح تسهیم (تک) راز پیش‌نگر شناخته شده و چندین بار استفاده از سیستم رمزنگاری یک بار مصرف در نظر گرفت. این طرح دارای امنیت ضعیف است. به عبارت دیگر، افشا یا بازسازی یک یا چند راز در این طرح منجر به افشای سایر رازها می‌شود. علاوه‌ براین، در این طرح، امکان بازسازی تدریجی رازها وجود نداشته و در آن تمام رازها به صورت هم‌زمان بازسازی می‌شوند. برای حل این مشکلات، در این مقاله با استفاده از درونیابی لاگرانژ، قضیه باقیمانده چینی و سختی مساله لگاریتم گسسته یک طرح تسهیم چندراز پیش‌نگر جدید ارائه شده که امکان بازسازی تدریجی رازها با ترتیبی از پیش تعیین شده را فراهم می‌کند. همچنین با توجه به سختی مساله لگاریتم گسسته، این طرح ویژگی وارسی‌پذیری را برآورده کرده و دارای امنیت قوی است.

المصادر:

 

[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.

نص كامل:



دسترسي در سايتِ http://jnrm.srbiau.ac.ir

سال ششم، شماره بيست و هشتم، بهمن و اسفند 1399

شماره شاپا: 2588-588X

 

 

 

 

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

 

 

ابراهیمی کیاسری محمد ابراهیم1، میرقدری عبدالرسول2 ،پاک‌نیت نصراله3¹، نظری مجتبی4

 

(1)   گروه ریاضی، واحد خرم‌آباد، دانشگاه آزاد اسلامی، خرم‌آباد، ایران

(2)  دانشکده و پژوهشکده فناوری اطلاعات و ارتباطات، دانشگاه جامع امام حسین(ع)، تهران، ایران

(3)  پژوهشکده علوم اطلاعات، پژوهشگاه علوم و فناوری اطلاعات ایران (ایرانداک)، تهران، ایران

(4)   گروه ریاضی، واحد خرم‌آباد، دانشگاه آزاد اسلامی، خرم‌آباد، ایران

 

 

تاريخ ارسال مقاله: 06/05/1398   تاريخ پذيرش مقاله: 19/10/1398

چکيده

در یک طرح تسهیم چندراز پیش‌نگر، یک یا چند راز به گونه‌ای بین مجموعه‌ای از شرکت‌کنندگان تسهیم می‌شود که 1) امکان نوسازی سهام در فواصل زمانی مشخص بدون کمک تسهیم‌کننده وجود داشته باشد و 2) در حالی که زیرمجموعه‌هایی مشخص از شرکت‌کنندگان به نام زیرمجموعه‌های مجاز قادر به بازسازی راز(ها) هستند، سایر زیرمجموعه‌ها قادر به کسب اطلاع در مورد راز(ها) نباشند. تنها طرح تسهیم چندراز پیش‌نگر موجود را می‌توان به عنوان ترکیبی از یک طرح تسهیم (تک) راز پیش‌نگر شناخته شده و چندین بار استفاده از سیستم رمزنگاری یک بار مصرف در نظر گرفت. این طرح دارای امنیت ضعیف است. به عبارت دیگر، افشا یا بازسازی یک یا چند راز در این طرح منجر به افشای سایر رازها می‌شود. علاوه‌ براین، در این طرح، امکان بازسازی تدریجی رازها وجود نداشته و در آن تمام رازها به صورت هم‌زمان بازسازی می‌شوند. برای حل این مشکلات، در این مقاله با استفاده از درونیابی لاگرانژ، قضیه باقیمانده چینی و سختی مساله لگاریتم گسسته یک طرح تسهیم چندراز پیش‌نگر جدید ارایه شده که امکان بازسازی تدریجی رازها با ترتیبی از پیش تعیین شده را فراهم می‌کند. همچنین با توجه به سختی مساله لگاریتم گسسته، این طرح ویژگی وارسی‌پذیری را برآورده کرده و دارای امنیت قوی است.

 

 

واژه‌هاي کليدي: تسهیم چندراز، امنیت پیش‌نگر، وارسی‌پذیری، درونیابی لاگرانژ، قضیه باقیمانده چینی.

 

---

[1] . عهده­دار مکاتبات:                                           Email: [e-mail]

1- مقدمه

در سال 1979، شمیر¹ [1] و بلکلی² [2] مفهوم تسهیم راز را مستقل از یکدیگر معرفی کردند. در یک طرح تسهیم راز، یک تسهیم‌کننده مقدار یک راز را به‌گونه‌ای مابین مجموعه‌ای از شرکت‌کنندگان تسهیم می‌کند که در آینده شرکت‌کنندگان موجود در برخی زیرمجموعه‌های مشخص (که زیرمجموعه‌های مجاز نامیده می‌شوند) بتوانند با استفاده از سهام خود، راز را بازسازی کنند و سایر زیرمجموعه‌ها (که زیرمجموعه‌های غیرمجاز نامیده می‌شوند) نتوانند با استفاده از سهام خود اطلاعی درباره راز به دست آورند. مجموعه تمام زیرمجموعه‌های مجاز در یک طرح تسهیم راز را ساختار دسترسی آن طرح گویند. ساختار دسترسی آستانه‌ای  پرکاربردترین نوع ساختار دسترسی طرح‌های تسهیم راز بوده که در آن هر زیرمجموعه‌ای شامل حداقل  شرکت‌کننده مجموعه‌ای مجاز است. ذکر این نکته در اینجا ضروری است که ساختار دسترسی هر دو طرح شمیر [1] و بلک‌لی [2] آستانه‌ای است. در یک طرح تسهیم راز معمولی، تسهیم‌کننده راز و شرکت‌کنندگان قادرند با ارایه سهام نامعتبر به سوء استفاده از سایر شرکت‌کنندگان بپردازند. برای جلوگیری از این کار، چور³ و همکاران [3]، مفهوم تسهیم راز وارسی‌پذیر را ارایه کرده‌اند. امنیت یک طرح تسهیم راز را می‌توان در برابر دو نوع متخاصم ایستا یا متخاصم سیار بررسی کرد. امنیت در برابر متخاصم ایستا برای رازهای با طول عمر کم کافی است. اما در بسیاری از کاربردها مانند تسهیم کلیدهای اصلی رمزنگاری، فایل‌های داده، اسناد حقوقی و غیره نیاز است که رازها برای مدت زمانی طولانی ذخیره شوند. در این شرایط، یک متخاصم سیار قادر است با توجه به وجود زمان کافی، در طول زمان به سهام متناظر با هر زیرمجموعه مجازی از شرکت‌کنندگان دست یافته و راز را بازسازی کند. در نتیجه، برای اطمینان از امنیت رازهای با طول عمر زیاد باید سهام متناظر با راز در زمان‌هایی مشخص به‌گونه‌ای نوسازی شوند که سهام موجود در بازه‌های زمانی قبل در بازه زمانی جدید بدون ارزش شوند.

این دقیقا همان کاری است که در تسهیم راز پیش‌نگر انجام می‌شود. در یک طرح تسهیم راز پیش‌نگر، زمان به چندین زیربازه تقسیم شده و در آغاز هر زیربازه، شرکت‌کنندگان به کمک یکدیگر سهام جدید خود از راز را به دست آورده و سهام قبلی خود را حذف می‌کنند [4، 5].

1-1هدف و ضرورت

متاسفانه، اغلب طرح‌های تسهیم راز پیش‌نگر موجود، تنها قادر به تسهیم یک راز در هر بار اجرای خود هستند. تنها طرح تسهیم چند راز پیش‌نگر ارایه ‌شده [6] و همچنین، تنها روش ارایه شده برای تبدیل طرح‌های تسهیم (یک) راز به طرح‌های تسهیم چند راز [7] نیز از مجموعه‌ای از نقطه‌ضعف‌ها رنج می‌برند که از آن جمله می‌توان به موارد زیر اشاره کرد:

1.       امکان بازسازی تدریجی رازها در آن وجود ندارد.

2.       در صورت افشا یک راز، سایر رازها نیز افشا می‌شوند.

3.       مقادیر اعلام عمومی شده، اطلاعاتی را در مورد راز‌ها افشا می‌کنند.

2-1 نوآوری

در این مقاله، برای حل مشکلات فوق، از ایده طرح تسهیم چند راز ارایه ‌شده در [2] استفاده کرده و با استفاده از خواص چندجمله‌ای‌ها و قضیه باقیمانده چینی⁴، یک طرح تسهیم چندراز پیش‌نگر جدید ارایه می‌کنیم که در آن ویژگی وارسی‌پذیری⁵ نیز با توجه به سختی حل مساله لگاریتم گسسته⁶ تامین شده است. در ادامه، امنیت طرح پیشنهادی و کارایی آن را بررسی کرده و به مقایسه آن با طرح‌های مشابه موجود می‌پردازیم. نتایج ارزیابی نشان‌دهنده این است که طرح پیشنهادی از نظر هزینه محاسباتی، مخابراتی و اندازه سهام از کارایی بهتری در مقایسه با طرح‌های موجود برخوردار بوده و در عین حال ویژگی‌های قابلیت بازسازی تدریجی و ترتیبی رازها و همچنین امنیت قوی در تسهیم چند راز را فراهم می‌کند.

 

 

 

3-1 کارهای مرتبط

امنیت طرح‌های تسهیم راز در برابر متخاصم سیار اولین بار توسط استروسکی⁷ و یانگ⁸ [4] مورد بحث واقع شده است، اما اولین طرح تسهیم راز پیش‌نگر در [5] توسط هرزبرگ و همکاران ارایه شده است. در [8]، ژو⁹ و همکاران یک طرح تسهیم راز پیش‌نگر جدید ارایه کرده‌اند. متاسفانه در این طرح، بازسازی سهام نیازمند به مشارکت تسهیم‌کننده است. در سال 2005، ژاو¹⁰ و همکاران [9] یک طرح تسهیم راز پیش‌نگر جدید ارایه کردند که قابل استفاده در سیستم‌های غیرهمگام است. در سال 2010، اسکولتز¹¹ و لیسکو¹² [10] یک طرح تسهیم راز پیش‌نگر جدید ارایه کردند که در آن مجموعه شرکت‌کنندگان نیز در طول زمان متغیر است. در [11]، نویسندگان یک طرح تسهیم راز پیش‌نگر با ساختار دسترسی کلی ارایه کرده‌اند. تسهیم راز اجتماعی [12-14] یکی از کاربردهای اصلی تسهیم راز پیش‌نگر است که در آن نیاز به نوسازی سهام وجود داشته و ارزش سهام شرکت‌کنندگان نیز در طول زمان متغیر است.

در همه روش‌های بررسی شده تا بدین‌جا، در هر اجرا تنها یک راز قابل تسهیم است. به عبارت دیگر برای تسهیم چند راز با استفاده از این روش‌ها، باید هر یک از این روش‌ها را به تعداد رازها اجرا کرد. با توجه به این مساله، این طرح‌ها در موقعیت‌هایی که تسهیم همزمان چندین راز مدنظر است ناکارا هستند. مفهوم تسهیم چند راز برای اولین بار در سال 1995 توسط هارن¹³ [15] ارایه شده است. در ادامه، طرح‌های تسهیم چند راز زیادی ارایه شده که در آن‌ها سعی شده کارایی یا امنیت افزایش یافته و یا قابلیت‌های جدیدی ارایه شده و یا از ساختار دسترسی‌های گسترده‌تری پشتیبانی شود. برای کسب اطلاع بیشتر در مورد این طرح‌ها، خوانندگان علاقمند به [16-22] ارجاع داده می‌شوند. در [7]، نویسندگان با استفاده از اتوماتای سلولی و رمزگذاری متقارن روشی ارایه کرده‌اند که با استفاده از آن می‌توان هر طرح تسهیم راز تکی را به یک طرح تسهیم چند راز تبدیل کرد.

در [6]، فنگ¹⁴ و همکاران یک طرح تسهیم چندراز پیش‌نگر ارایه کرده‌اند. در این طرح، یکی از رازها با استفاده از روش هرزبرگ¹⁵ و همکاران [5] مابین مجموعه شرکت‌کنندگان تسهیم شده و نتیجه xor سایر رازها با این راز اعلام عمومی می‌شود. برای بازسازی رازها، نیز در ابتدا از فرایند بازیابی طرح هرزبرگ و همکاران استفاده شده و راز تسهیم شده بازسازی می‌شود. در ادامه سایر رازها، با xor مقدار به دست آمده و مقادیر اعلام عمومی شده محاسبه می‌شوند.

4-1 ساختار مقاله

در ادامه این مقاله، در بخش 2، به بررسی پیش‌نیازهای این مقاله شامل درونیابی لاگرانژ، قضیه باقیمانده چینی و مساله لگاریتم گسسته پرداخته می‌شود. در بخش 3، طرح تسهیم چند راز پیش‌نگر پیشنهادی ارایه شده و امنیت و کارایی آن در بخش 4 بررسی می‌شود. در نهایت، نتیجه‌گیری‌ها در بخش5 بیان شده است.

 

2- مباحث مقدماتی

1-2 درونیابی لاگرانژ

تعریف 2-1-1 درونیابی لاگرانژ¹⁶: فرض کنیم نقاط  با مولفه‌های اول متمایز داده شده باشند. مساله درونیابی لاگرانژ متناظر با نقاط فوق عبارت است از محاسبه چندجمله‌ایبا کمترین درجه ممکن به طوری که

(1)

برای محاسبه جواب مساله درونیابی لاگرانژ فوق، چندجمله‌ای  را به صورت زیر می‌سازیم:

(2)

که ها چندجمله‌ای‌های لاگرانژ بوده و به صورت زیر محاسبه می‌شوند:

(3)

2-2 مسئله لگاریتم گسسته (DLP)

امنیت بسیاری از سیستم‌های رمزنگاری بر حل یک مسئله‌ی سخت ریاضی به نام مسئله لگاریتم گسسته استوار است. مسائلی مانند توافق کلید دیفی–هلمن و مشتقات آن، سیستم رمزنگاری الجمال، امضای دیجیتال الجمال و مشتقات آن و غیره از این دسته‌اند.

تعریف 2-2-1 فرض کنید  یک گروه دوری متناهی از مرتبه  با عملگر   یک مولد و  یک عضو دلخواه از آن باشد. لگاریتم گسسته  در پایه ، که با  نشان داده می‌شود، عدد صحیحی مثل است که

تعریف 2-2-2 مسئله لگاریتم گسسته تعمیم‌یافته : اگر  یک گروه دوری متناهی از مرتبه  با عملگر  یک مولد و  یک عضو دلخواه از آن باشد، عدد صحیح  را بیابید که  همان‌طور که از نام این مسئله مشخص است، این مسئله تعمیم‌یافته مسئله لگاریتم گسسته است که تنها حالاتی را در نظر می‌گیرد که  و عددی اول باشد.

3-2 قضیه باقیمانده چینی 

فرض کنید  اعداد صحیح مثبت باشند. به طوری که دو به دو نسبت به هم اول باشند. فرض کنید  نیز اعدادی صحیح و دلخواه باشند. آن‌گاه دستگاه  فقط و فقط یک جواب در پیمانه    دارد که برابر است با:

(4)

که در آن . اثبات در [23].

 

3- طرح پیشنهادی

در این بخش، یک طرح تسهیم چند راز پیش‌نگر جدید ارایه می‌شود. در طرح پیشنهادی در ابتدا مجموعه‌ای از  راز مابین مجموعه شرکت‌کنندگان تسهیم می‌شود. در ادامه، شرکت‌‌کنندگان می‌توانند رازها را به ترتیبی از پیش تعیین‌شده بازسازی کنند. در طرح ارایه شده، برای به دست آوردن امنیت در دراز مدت، شرکت‌کنندگان قادر هستند بدون نیاز به کمک تسهیم‌کننده سهام خود را از مجموعه رازها نوسازی کرده و بدین طریق، در صورتی که متخاصمی سیار سعی کند در طول زمان به سراغ شرکت‌کنندگان موجود در مجموعه‌ای مجاز رفته، سهام آن‌ها را به دست آورده و از آن برای بازسازی راز استفاده کند، تلاش‌های این متخاصم را بی‌اثر کنند. برای سادگی، در طرح جدید ارایه شده برای تمام رازها یک ساختار دسترسی یکسان درنظر گرفته شده است اما به آسانی می‌توان آن را به‌گونه‌ای تغییر داد که هر راز ساختار دسترسی دلخواه منحصر به خود را داشته باشد.

فرض کنید  مجموعه‌ای شامل  شرکت‌کننده و  مقداری آستانه‌ای باشد. همچنین، فرض کنید  مجموعه رازهایی باشد که قصد تسهیم آن‌ها مابین مجموعه شرکت‌کننده‌ها وجود دارد. به‌علاوه‌،  را به عنوان عددی اول و بزرگ در نظر بگیرید. طرح تسهیم چند راز پیش‌نگر پیشنهادی از سه پروتکل 1) تسهیم راز، 2) نوسازی سهام و 3) بازیابی راز، تشکیل شده که در ادامه جزئیات این پروتکل‌ها بررسی می­شوند.

1-3 تسهیم راز

برای تسهیم مجموعه رازهای
 مابین مجموعه شرکت‌کننده‌های  از پروتکل تسهیم راز با گام‌های زیر استفاده می‌شود:

تسهیم‌کننده راز:

1-       اعداد  را که نسبت به هم اول هستند به عنوان پیمانه‌های متناظر با قضیه باقیمانده چینی انتخاب می‌کند.

2-       مولد ضربی  در  را انتخاب می‌کند.

3-       اعداد تصادفی را متناظر با رازهای  را انتخاب می‌کند.

4-       مقدار  را برابر با  قرار می‌دهد.

5-       مقدار  را به صورت تصادفی از  انتخاب می‌کند.

6-       مقادیر  را به صورت تصادفی از  انتخاب، مقدار  را محاسبه کرده و چندجمله‌ای زیر را می‌سازد:

(5)

7-       برای : سهم شرکت‌کننده  از راز  را به صورت  محاسبه می‌کند.

8-       برای : مقادیر
 را محاسبه می‌کند.

9-       مقدار  را محاسبه می‌کند.

10-       مقدار  را محاسبه می‌کند.

11-       مقدار  را برابر با  قرار داده و در صورتی که  باشد به مرحله 6 برمی‌گردد.

12-       از طریق یک کانال امن مقادیر  را به شخص سوم مورداعتماد و سهم‌های ، ، ... و  را به ترتیب به شرکت‌کننده‌های ، ، ... و  ارسال می‌کند.

13-       مقادیر ، ، ،  و  (برای  و ) را اعلام عمومی می‌کند.

هر شرکت‌کننده ، پس از دریافت سهم  درستی سهم دریافتی را به صورت زیر بررسی می‌کند:

(6)

در صورت برقراری رابطه فوق،  سهم دریافتی را پذیرفته و در غیر این صورت آن را رد کرده و علیه تسهیم‌کننده اعلام شکایت می‌کند.

2-3 نوسازی سهام

‌از طریق این پروتکل، سهم شرکت‌کننده‌ها در زمان‌هایی مشخص نوسازی می‌شود. این پروتکل نیازی به برخط بودن تسهیم‌کننده رازها نداشته و مجموعه‌ای مجاز از کاربران قادرند با کمک یکدیگر این پروتکل را اجرا کرده و سهم همه کاربران را نوسازی کنند. فرض کنید  مجموعه‌ای از شرکت‌کنندگان باشد که قصد دارند در فرایند نوسازی سهام شرکت کنند و  راز متناظر با سهم‌های فعلی شرکت‌کنندگان باشد. در این پروتکل، هر شرکت‌کننده :

1-       چندجمله‌ای زیر را می‌سازد:

که  به صورت تصادفی از  انتخاب شده‌اند.

2-       سهم هر شرکت‌کننده  از چندجمله‌ای  را به­صورت  محاسبه و از طریق یک کانال امن به او ارسال می‌کند.

3-       برای : مقادیر
 را محاسبه و اعلام عمومی می‌کند.

هر شرکت‌کننده ، پس از دریافت سهام خود از شرکت‌کنندگان موجود در :

1-       برای هر  که : درستی سهم دریافتی خود از   را به صورت زیر بررسی می‌کند:

(7)

،

در صورت عدم برقراری رابطه فوق علیه  اعلام شکایت می‌کند.

2-       در صورتی که حداکثر  شرکت‌کننده علیه  اعلام شکایت کرده باشند،  را به مجموعه (ابتدا" تهی)  اضافه می‌کند و  سهم شرکت‌کننده‌هایی که علیه او اعلام شکایت کرده‌اند، را اعلام عمومی می‌کند.

3-       در صورتی که ، سهم جدید خود از راز‌های بازسازی نشده را به صورت زیر بازسازی می‌کند:

(9)

3-3 بازسازی راز

از طریق پروتکل بازسازی شرکت‌کنندگان قادر به بازسازی رازها به ترتیب از پیش تعیین‌شده هستند. فرض کنید  مجموعه‌ای از شرکت‌کنندگان باشد که قصد دارند بازسازی راز را انجام دهند. علاوه‌براین، فرض کنید  آخرین رازی است که در ترتیب در نظر گرفته شده بازسازی نشده است. با توجه به این موارد، برای بازسازی :

هر شرکت‌کننده :

مقدار  متناظر با سهم خود از راز  را از طریق کانال امن به شخص مورد اعتماد ارسال می‌کند.

شخص مورد اعتماد:

1-       با توجه به رابطه (10) درستی سهم متناظر با  را بررسی می‌کند:

(8)

،

2-       در صورت برقراری رابطه فوق  را به مجموعه (ابتدا" تهی)  اضافه می‌کند.

3-       در صورتی که ، با اعمال درون‌یابی لاگرانژ بر روی مجموعه زوج‌های  برای  و استفاده از ضریب ثابت چندجمله‌ای درونیابی شده راز  را بازسازی می‌کند.

4-       راز  را از طریق کانال امن به اعضای  ارسال می‌کند.

5-       در صورتی که  مقدار  را برابر با رشته‌ای تماما صفر قرار می‌دهد.

6-       مقدار  را محاسبه کرده و از طریق کانال امن به همه شرکت‌کنندگان ارسال می‌کند.

هر شرکت‌کننده :

1-       سهم خود از راز  را برابر با
 قرار می‌دهد.

2-       درستی سهم خود از راز  را به صورت زیر بررسی می‌کند:

(10)

.

 

4- بررسی امنیت و کارایی طرح پیشنهادی

در این بخش، ابتدا امنیت طرح پیشنهادی و سپس کارایی آن بررسی شده و با طرح‌های مشابه موجود مورد مقایسه قرار می‌گیرد.

 

1-4 بررسی امنیت

در این بخش، امنیت طرح پیشنهادی مورد بررسی قرار می‌گیرد. امنیت طرح پیشنهادی وابسته به امنیت طرح

ارایه شده توسط زارع‌پور و همکاران [22] و طرح فلدمن [24] است. در ادامه این بخش، برای بررسی امنیت طرح پیشنهادی، سناریوی حملات ممکن مورد بررسی قرار خواهد گرفت.

حمله: تعداد‌  یا کمتر شرکت‌کننده قصد بازسازی یک راز را داشته باشند.

تحلیل:

فرض کنید  آخرین رازی باشد که در ترتیب در نظر گرفته شده بازسازی نشده است. فرض کنید  شرکت‌کننده که بدون از دست رفتن کلیت مساله و برای سادگی فرض می‌کنیم  باشند، قصد بازسازی راز را داشته باشند. مجموعه شرکت‌کنندگان موجود در  به سهام خود از راز  یعنی ، ، ...،  دسترسی دارند، اما برای بازسازی راز با توجه به ویژگی‌های درونیابی لاگرانژ نیاز به  سهم وجود دارد که با توجه به عدم دسترسی به سهم آخر، بازسازی راز ناممکن می‌شود.

حمله:  شرکت‌کننده تلاش به بازسازی رازها در ترتیبی مغایر با ترتیب از پیش تعیین‌شده دارند.

تحلیل:

بازسازی هر راز نیازمند به بازسازی یک چند‌جمله‌ای (رابطه (5)) است که راز موردنظر ضریب ثابت آن چندجمله‌ای است. برای بازسازی چندجمله‌ای موردنظر در روش پیشنهادی نیازمند به  مقدار از آن چندجمله‌ای هستیم. از آن‌جا که در روش پیشنهادی، در هر زمان هر شرکت‌کننده تنها به سهم خود از آخرین راز دسترسی داشته و محاسبه سهم شرکت‌کننده از راز بعدی نیازمند محاسبه راز قبلی و مشارکت شخص مورد اعتماد است، چنین چیزی ناممکن است و در نتیجه رازها به همان ترتیب از پیش تعیین‌شده قابل بازیابی هستند.

حمله:  شرکت‌کننده به بازسازی یکباره همه رازها اقدام کنند.

تحلیل: در عمل ممکن است مجموعه‌ای از شرکت‌کنندگان، برخلاف اهداف سیستم، تصمیم به بازسازی یک‌باره همه رازها بگیرند. در روش پیشنهادی از آن‌جا که شرکت‌کنندگان برای محاسبه سهم خود از راز بعدی نیازمند مشارکت شخص سوم مورداعتماد هستند، قادر نیستند به دلخواه خود همه رازها را بازسازی کنند و شخص سوم مورد اعتماد می‌تواند در صورت مشاهده سوءاستفاده از سیستم از بازسازی سایر رازها جلوگیری کند.

حمله: یک متخاصم سعی کند در دراز مدت سهم متناظر با  شرکت‌کننده را به دست آورد.

تحلیل: در طرح ارایه شده، همانند سایر طرح‌های تسهیم راز پیش‌نگر، در زمان‌هایی مشخص و از پیش تعیین‌شده سهام شرکت‌کنندگان از آخرین راز قابل بازسازی نوسازی می‌شود. نحوه نوسازی نیز بدین طریق است که در هر نوسازی سهام شرکت‌کنندگان از یک چندجمله‌ای جدید تنها با ضریب ثابت یکسان با چندجمله‌ای قبل محاسبه و در اختیار شرکت‌کنندگان قرار می‌گیرد. در نتیجه، در صورتی که سهام در دسترس متخاصم متناظر با بازه‌های زمانی متفاوت باشد آن‌گاه متخاصم قادر به استفاده همزمان از آن‌ها نبوده و تنها می‌تواند سهام به دست آمده در یک بازه زمانی را مورد استفاده قرار دهد. با توجه به فرض اینکه، متخاصم در یک بازه زمانی حداکثر قادر به دستیابی به  راز است، می‌توان نتیجه گرفت در سناریوی در نظر گرفته شده متخاصم مزیتی نداشته و قادر به کسب اطلاعی در مورد راز نیست.

حمله: متخاصم تلاش کند تا یک سهم جعلی را به عنوان یک سهم واقعی در نوسازی سهم‌ها یا بازسازی یک راز وارد کند.

تحلیل: برای بررسی این سناریو باید موارد زیر را در نظر گرفت: 1) سهام دریافتی شرکت‌کنندگان از تسهیم‌کننده یا هر یک از شرکت‌کنندگانی که در پروتکل نوسازی سهام مشارکت می‌کنند معتبر باشد. 2) سهم ارایه شده توسط یک کاربر برای بازسازی یک راز معتبر باشد. با توجه به عمومی‌سازی  به توان ضرایب چندجمله‌ای به کار رفته توسط تسهیم‌کننده و شرکت‌کنندگان اجرا کننده پروتکل نوسازی سهام و خواص روش‌های تسهیم راز مبتنی بر چندجمله‌ای [24] دریافت‌کننده یک سهم به راحتی می‌تواند تولید سهم خود از چندجمله‌ای یکسان را بررسی کند. علاوه‌بر‌این، روابط (6) و (8)، اطمینان از ارایه سهام صحیح در پروتکل بازسازی رازها را ایجاد می‌کند.

حمله: استفاده از رازهای محاسبه یا افشا شده توسط متخاصم برای دستیابی به سایر رازها.

تحلیل: با توجه به این که بازسازی راز ناشناخته نیازمند مقادیر محرمانه در اختیار شخص سوم مورداعتماد و همچنین پیمانه‌های در اختیار شرکت‌کنندگان است، در اختیار داشتن چندین راز هیچ مزیتی را برای متخاصم در راستای به دست آوردن سهام شرکت‌کنندگان و درنتیجه بازسازی رازهای نامعلوم ایجاد نمی‌کند. لازم به ذکر است که یک طرح تسهیم چند راز که در این سناریو حمله امن باشد را یک طرح تسهیم چند راز با امنیت قوی گویند و در غیر این صورت یک طرح تسهیم راز با امنیت ضعیف.

4-2 مقایسه با چند طرح مرتبط

در این بخش طرح پیشنهادی با چند طرح‌ مرتبط موجود مقایسه می‌شود. مقایسه از نظر پیچیدگی محاسباتی، پیچیدگی مخابراتی، قابلیت تسهیم چند راز، قابلیت بازسازی راز‌ها به مرور زمان، وجود ترتیب در بازسازی رازها، تصدیق‌پذیری و اندازه سهام صورت خواهد گرفت.

برای بررسی پیچیدگی محاسباتی، تنها عملگر‌های محاسباتی هزینه‌بر را در نظر گرفته و از عملگرهای سبک شامل xor، باقیمانده پیمانه‌ای، جمع و تفریق چشم‌پوشی خواهد شد. در طرح ارایه‌شده، تسهیم‌کننده رازها برای محاسبه سهم شرکت‌کنندگان نیاز به محاسبه  مقدار چندجمله‌ای از درجه  دارد که  مقدار آستانه،  تعداد کل شرکت‌کنندگان و  تعداد رازهاست. با توجه به نیاز به  عمل ضرب برای محاسبه مقدار یک چندجمله‌ای در یک نقطه، کل محاسبات قابل انجام توسط تسهیم‌کننده در این قسمت برابر با  است. علاوه بر محاسبه سهام، تسهیم‌کننده باید مقادیری را نیز برای تصدیق‌پذیری سهام محاسبه و اعلام عمومی کند. محاسبات موردنیاز برای پردازش این قسمت برابر با  عمل توان‌رسانی است. لذا هزینه محاسباتی کل موارد مربوط به تسهیم‌کننده رازها برابر با است با  که  هزینه محاسباتی یک عمل ضرب پیمانه‌ای و  هزینه محاسباتی یک عمل توان‌رسانی پیمانه‌ای است. هر شرکت‌کننده هم باید صحت سهم خود را از راز آخر در این پروتکل بررسی کند که با توجه به رابطه (6) هزینه محاسباتی وارده به هر شرکت‌کننده برابر است با
.

هر شرکت‌کننده  که در پروتکل نوسازی سهام طرح پیشنهادی مشارکت می‌کند، باید یک چندجمله‌ای از درجه  ساخته، مقدار این چندجمله‌ای را در  نقطه محاسبه کرده و مقادیری را برای بررسی صحت سهام تولید‌شده محاسبه و عمومی کند که هزینه این محاسبات برابر است با . علاوه‌براین، همه شرکت‌کنندگان باید اعتبار سهام دریافتی از سایر شرکت‌کنندگان را در پروتکل نوسازی سهام بررسی کرده و سهم نهایی خود را با استفاده از آن‌ها محاسبه کنند. برای این منظور، شرکت‌کنندگان باید از رابطه (8) استفاده کنند که با توجه به این رابطه، هزینه محاسباتی هر شرکت‌کننده برابر است با
. در بازسازی راز، شرکت‌کنندگان سهام خود را به شخص سوم مورد اعتماد ارسال کرده و او راز را بازسازی و در اختیار شرکت‌کنندگان قرار می‌دهد. بدین منظور، شخص سوم مورد اعتماد اعتبار سهام دریافتی را بررسی کرده، راز را با استفاده از درونیابی لاگرانژ محاسبه کرده و در اختیار شرکت‌کنندگان قرار می‌دهد. هزینه محاسباتی وارده به شخص سوم مورد اعتماد بدین منظور عبارت است از . علاوه‌بر‌این، هر شرکت‌کننده  نیز باید با استفاده از مقادیر دریافتی از شخص سوم، سهم جدید خود را محاسبه و صحت آن را بررسی کند که هزینه محاسباتی وارده به هر شرکت‌کننده بدین منظور عبارت است از . هزینه‌های محاسباتی طرح پیشنهادی به طور خلاصه در جدول 1 در زیر آورده شده است. لازم به ذکر است که از آن‌جا که سایر طرح‌های مرتبط [5، 6] ویژگی وارسی‌پذیری را تامین نمی‌کنند لذا مقایسه کارایی طرح پیشنهادی و سایر طرح‌های مرتبط عقلانی نبوده و در این مقاله انجام نخواهد شد.

برای بررسی هزینه مخابراتی، به بررسی اندازه مجموع پیام‌های ارسالی در پروتکل‌های مختلف طرح ارایه شده پرداخته می‌شود. در این راستا، تنها پیام‌های ارسالی از طریق کانال امن در نظر گرفته شده و از سایر مقادیر ارسالی صرف‌نظر خواهد شد. به عبارت دیگر، تنها هزینه مخابراتی کانال امن در نظر گرفته خواهد شد. در پروتکل تسهیم طرح پیشنهادی، تسهیم‌کننده سهام شرکت‌کنندگان را به آن‌ها ارسال کرده و مقادیری را نیز در اختیار شخص سوم مورد اعتماد قرار می‌دهد که مجموع اندازه این مقادیر برابر با
 بیت است. در پروتکل نوسازی سهام، هر شرکت‌کننده عضو مجموعه اجرا‌کننده این پروتکل، مقدار یک چندجمله‌ای در یک نقطه را محاسبه و به سایرین ارسال می‌کند. در نتیجه، مجموع اندازه مقادیر ارسالی در این‌جا برابر با  بیت است. در پروتکل بازسازی، در ابتدا شرکت‌کنندگان موجود در یک مجموعه مجاز سهم خود را به شخص سوم مورد اعتماد ارسال می‌کنند. در ادامه، شخص سوم مورد اعتماد راز را بازسازی کرده و راز و مقداری که با استفاده از آن سهم جدید شرکت‌کنندگان محاسبه می‌شود را به شرکت‌کنندگان ارسال می‌کند. در نتیجه مجموع اندازه مقادیر ارسالی در این پروتکل طرح پیشنهادی برابر با  بیت است. نتایج مقایسه هزینه‌های مخابراتی طرح پیشنهادی با سایر طرح‌های مرتبط در جدول 2 آورده شده است. در این جدول و همچنین جدول 3 منظور از [5]+[7] پیاده‌سازی روش تعمیم تسهیم راز تکی به تسهیم چند راز ارایه شده در [7] با استفاده از روش تسهیم راز پیش‌نگر [5] است.

اندازه سهم هر شرکت‌کننده در یک طرح تسهیم راز برابر با میزان اطلاعاتی است که شرکت‌کننده باید محرمانه نگهداری کند و از اهمیت بالایی در طرح‌های تسهیم راز برخوردار است. هر سهم در طرح پیشنهادی از دو قسمت تشکیل شده است، 1) مقدار یک چندجمله‌ای در یک نقطه در پیمانه  و 2) یک پیمانه متناظر با باقیمانده چینی که این پیمانه نیز از مرتبه  است. در نتیجه اندازه سهم هر شرکت‌کننده در طرح پیشنهادی برابر با  بیت است.

در جدول 3 نتایج مقایسه طرح پیشنهادی با سایر طرح‌های مرتبط با توجه به اندازه سهام و ویژگی‌های ارایه شده توسط آن‌ها آورده شده است. همان طور که نتایج جداول 1 تا 3 نشان می‌دهد، طرح پیشنهادی از نظر هزینه محاسباتی، مخابراتی و اندازه سهام از کارایی بهتری برخوردار بوده و در عین حال ویژگی‌های قابلیت بازسازی تدریجی و ترتیبی رازها و همچنین امنیت قوی در تسهیم چند راز را فراهم می‌کند.

 

5- نتیجه‌گیری

در ابتدا مشکلات موجود در طرح‌های تسهیم چند راز پیش‌نگر مورد بررسی قرار گرفت. در ادامه، با استفاده از درونیابی لاگرانژ، قضیه باقیمانده چینی و سختی مساله لگاریتم گسسته، یک طرح تسهیم چند راز پیش‌نگر جدید ارایه شد که امکان بازسازی تدریجی و ترتیبی رازها را فراهم کرده، با توجه به سختی مساله لگاریتم گسسته ویژگی وارسی‌پذیری را ارایه کرده و دارای امنیت قوی است. طرح پیشنهادی از نظر هزینه محاسباتی، مخابراتی و اندازه سهام از کارایی بهتری برخوردار بوده و در عین حال ویژگی‌های قابلیت بازسازی تدریجی و ترتیبی رازها و همچنین امنیت قوی در تسهیم چند راز را فراهم می‌کند.

 

---

[1]  Shamir

[2]  Blakley

[3]  Chor

[4]  Chinese remainder theorem

[5]  Verifiability

[6]  Discrete logarithm problem

[7]  Ostrovsky

[8]  Yung

[9]  Xu

[10]  Zou

[11]  Schultz

[12]  Liskov

[13]  Harn

[14]  Feng

[15]  Herzberg

[16]  Lagrange interpolation

 

 

جدول 1: هزینه محاسباتی وارده به موجودیت‌های مختلف درگیر در پروتکل‌های مختلف طرح پیشنهادی.

(11)

 

 

جدول 2: بررسی هزینه مخابراتی طرح‌های مختلف

پروتکل بازسازی		پروتکل نوسازی		پروتکل تسهیم راز
	TTP				D

 

 

جدول 3: مقایسه چند طرح مختلف با طرح پیشنهادی از لحاظ شاخصه‌های امنیت و کارایی

پروتکل بازسازی	پروتکل نوسازی	پروتکل تسهیم راز	طرح
			[5]
			[5] و [7]
			[6]
			پیشنهادی

 

 

 

 

 

 

 

 

مراجع

 

[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. 

 

 

 

 

 

---