تسهیم چندراز پیش‌نگر با استفاده از درونیابی لاگرانژ و قضیه باقیمانده چینی
محورهای موضوعی : آمار
محمد ابراهیم ابراهیمی کیاسری
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.
دسترسي در سايتِ http://jnrm.srbiau.ac.ir
سال ششم، شماره بيست و هشتم، بهمن و اسفند 1399
|
تسهیم چندراز پیش‌نگر با استفاده از درونیابی لاگرانژ و قضیه باقیمانده چینی
ابراهیمی کیاسری محمد ابراهیم1، میرقدری عبدالرسول2 ،پاک‌نیت نصراله31، نظری مجتبی4
(1) گروه ریاضی، واحد خرم‌آباد، دانشگاه آزاد اسلامی، خرم‌آباد، ایران
(2) دانشکده و پژوهشکده فناوری اطلاعات و ارتباطات، دانشگاه جامع امام حسین(ع)، تهران، ایران
(3) پژوهشکده علوم اطلاعات، پژوهشگاه علوم و فناوری اطلاعات ایران (ایرانداک)، تهران، ایران
(4) گروه ریاضی، واحد خرم‌آباد، دانشگاه آزاد اسلامی، خرم‌آباد، ایران
تاريخ ارسال مقاله: 06/05/1398 تاريخ پذيرش مقاله: 19/10/1398
چکيده
در یک طرح تسهیم چندراز پیش‌نگر، یک یا چند راز به گونه‌ای بین مجموعه‌ای از شرکتکنندگان تسهیم می‌شود که 1) امکان نوسازی سهام در فواصل زمانی مشخص بدون کمک تسهیم‌کننده وجود داشته باشد و 2) در حالی که زیرمجموعه‌هایی مشخص از شرکتکنندگان به نام زیرمجموعه‌های مجاز قادر به بازسازی راز(ها) هستند، سایر زیرمجموعه‌ها قادر به کسب اطلاع در مورد راز(ها) نباشند. تنها طرح تسهیم چندراز پیش‌نگر موجود را می‌توان به عنوان ترکیبی از یک طرح تسهیم (تک) راز پیش‌نگر شناخته شده و چندین بار استفاده از سیستم رمزنگاری یک بار مصرف در نظر گرفت. این طرح دارای امنیت ضعیف است. به عبارت دیگر، افشا یا بازسازی یک یا چند راز در این طرح منجر به افشای سایر رازها می‌شود. علاوه براین، در این طرح، امکان بازسازی تدریجی رازها وجود نداشته و در آن تمام رازها به صورت همزمان بازسازی میشوند. برای حل این مشکلات، در این مقاله با استفاده از درونیابی لاگرانژ، قضیه باقیمانده چینی و سختی مساله لگاریتم گسسته یک طرح تسهیم چندراز پیش‌نگر جدید ارایه شده که امکان بازسازی تدریجی رازها با ترتیبی از پیش تعیین شده را فراهم می‌کند. همچنین با توجه به سختی مساله لگاریتم گسسته، این طرح ویژگی وارسی‌پذیری را برآورده کرده و دارای امنیت قوی است.
واژه‌هاي کليدي: تسهیم چندراز، امنیت پیش‌نگر، وارسی‌پذیری، درونیابی لاگرانژ، قضیه باقیمانده چینی.
[1] . عهدهدار مکاتبات: Email: pakniat@irandoc.ac.ir
1- مقدمه
در سال 1979، شمیر1 [1] و بلکلی2 [2] مفهوم تسهیم راز را مستقل از یکدیگر معرفی کردند. در یک طرح تسهیم راز، یک تسهیم‌کننده مقدار یک راز را به‌گونه‌ای مابین مجموعه‌ای از شرکتکنندگان تسهیم می‌کند که در آینده شرکتکنندگان موجود در برخی زیرمجموعه‌های مشخص (که زیرمجموعه‌های مجاز نامیده میشوند) بتوانند با استفاده از سهام خود، راز را بازسازی کنند و سایر زیرمجموعه‌ها (که زیرمجموعه‌های غیرمجاز نامیده میشوند) نتوانند با استفاده از سهام خود اطلاعی درباره راز به دست آورند. مجموعه تمام زیرمجموعه‌های مجاز در یک طرح تسهیم راز را ساختار دسترسی آن طرح گویند. ساختار دسترسی آستانه‌ای 
پرکاربردترین نوع ساختار دسترسی طرح‌های تسهیم راز بوده که در آن هر زیرمجموعه‌ای شامل حداقل 
شرکت‌کننده مجموعه‌ای مجاز است. ذکر این نکته در اینجا ضروری است که ساختار دسترسی هر دو طرح شمیر [1] و بلکلی [2] آستانه‌ای است. در یک طرح تسهیم راز معمولی، تسهیم‌کننده راز و شرکتکنندگان قادرند با ارایه سهام نامعتبر به سوء استفاده از سایر شرکتکنندگان بپردازند. برای جلوگیری از این کار، چور3 و همکاران [3]، مفهوم تسهیم راز وارسی‌پذیر را ارایه کرده‌اند. امنیت یک طرح تسهیم راز را می‌توان در برابر دو نوع متخاصم ایستا یا متخاصم سیار بررسی کرد. امنیت در برابر متخاصم ایستا برای رازهای با طول عمر کم کافی است. اما در بسیاری از کاربردها مانند تسهیم کلیدهای اصلی رمزنگاری، فایل‌های داده، اسناد حقوقی و غیره نیاز است که رازها برای مدت زمانی طولانی ذخیره شوند. در این شرایط، یک متخاصم سیار قادر است با توجه به وجود زمان کافی، در طول زمان به سهام متناظر با هر زیرمجموعه مجازی از شرکتکنندگان دست یافته و راز را بازسازی کند. در نتیجه، برای اطمینان از امنیت رازهای با طول عمر زیاد باید سهام متناظر با راز در زمان‌هایی مشخص به‌گونه‌ای نوسازی شوند که سهام موجود در بازه‌های زمانی قبل در بازه زمانی جدید بدون ارزش شوند.
این دقیقا همان کاری است که در تسهیم راز پیش‌نگر انجام می‌شود. در یک طرح تسهیم راز پیش‌نگر، زمان به چندین زیربازه تقسیم شده و در آغاز هر زیربازه، شرکتکنندگان به کمک یکدیگر سهام جدید خود از راز را به دست آورده و سهام قبلی خود را حذف می‌کنند [4، 5].
1-1هدف و ضرورت
متاسفانه، اغلب طرح‌های تسهیم راز پیش‌نگر موجود، تنها قادر به تسهیم یک راز در هر بار اجرای خود هستند. تنها طرح تسهیم چند راز پیش‌نگر ارایه شده [6] و همچنین، تنها روش ارایه شده برای تبدیل طرح‌های تسهیم (یک) راز به طرح‌های تسهیم چند راز [7] نیز از مجموعه‌ای از نقطه‌ضعف‌ها رنج می‌برند که از آن جمله می‌توان به موارد زیر اشاره کرد:
1. امکان بازسازی تدریجی رازها در آن وجود ندارد.
2. در صورت افشا یک راز، سایر رازها نیز افشا میشوند.
3. مقادیر اعلام عمومی شده، اطلاعاتی را در مورد رازها افشا می‌کنند.
2-1 نوآوری
در این مقاله، برای حل مشکلات فوق، از ایده طرح تسهیم چند راز ارایه شده در [2] استفاده کرده و با استفاده از خواص چندجمله‌ای‌ها و قضیه باقیمانده چینی4، یک طرح تسهیم چندراز پیش‌نگر جدید ارایه می‌کنیم که در آن ویژگی وارسی‌پذیری5 نیز با توجه به سختی حل مساله لگاریتم گسسته6 تامین شده است. در ادامه، امنیت طرح پیشنهادی و کارایی آن را بررسی کرده و به مقایسه آن با طرح‌های مشابه موجود می‌پردازیم. نتایج ارزیابی نشان‌دهنده این است که طرح پیشنهادی از نظر هزینه محاسباتی، مخابراتی و اندازه سهام از کارایی بهتری در مقایسه با طرح‌های موجود برخوردار بوده و در عین حال ویژگی‌های قابلیت بازسازی تدریجی و ترتیبی رازها و همچنین امنیت قوی در تسهیم چند راز را فراهم می‌کند.
3-1 کارهای مرتبط
امنیت طرح‌های تسهیم راز در برابر متخاصم سیار اولین بار توسط استروسکی7 و یانگ8 [4] مورد بحث واقع شده است، اما اولین طرح تسهیم راز پیش‌نگر در [5] توسط هرزبرگ و همکاران ارایه شده است. در [8]، ژو9 و همکاران یک طرح تسهیم راز پیش‌نگر جدید ارایه کرده‌اند. متاسفانه در این طرح، بازسازی سهام نیازمند به مشارکت تسهیم‌کننده است. در سال 2005، ژاو10 و همکاران [9] یک طرح تسهیم راز پیش‌نگر جدید ارایه کردند که قابل استفاده در سیستم‌های غیرهمگام است. در سال 2010، اسکولتز11 و لیسکو12 [10] یک طرح تسهیم راز پیش‌نگر جدید ارایه کردند که در آن مجموعه شرکتکنندگان نیز در طول زمان متغیر است. در [11]، نویسندگان یک طرح تسهیم راز پیش‌نگر با ساختار دسترسی کلی ارایه کرده‌اند. تسهیم راز اجتماعی [12-14] یکی از کاربردهای اصلی تسهیم راز پیش‌نگر است که در آن نیاز به نوسازی سهام وجود داشته و ارزش سهام شرکتکنندگان نیز در طول زمان متغیر است.
در همه روش‌های بررسی شده تا بدین‌جا، در هر اجرا تنها یک راز قابل تسهیم است. به عبارت دیگر برای تسهیم چند راز با استفاده از این روش‌ها، باید هر یک از این روش‌ها را به تعداد رازها اجرا کرد. با توجه به این مساله، این طرح‌ها در موقعیت‌هایی که تسهیم همزمان چندین راز مدنظر است ناکارا هستند. مفهوم تسهیم چند راز برای اولین بار در سال 1995 توسط هارن13 [15] ارایه شده است. در ادامه، طرح‌های تسهیم چند راز زیادی ارایه شده که در آن‌ها سعی شده کارایی یا امنیت افزایش یافته و یا قابلیت‌های جدیدی ارایه شده و یا از ساختار دسترسی‌های گسترده‌تری پشتیبانی شود. برای کسب اطلاع بیشتر در مورد این طرح‌ها، خوانندگان علاقمند به [16-22] ارجاع داده میشوند. در [7]، نویسندگان با استفاده از اتوماتای سلولی و رمزگذاری متقارن روشی ارایه کرده‌اند که با استفاده از آن می‌توان هر طرح تسهیم راز تکی را به یک طرح تسهیم چند راز تبدیل کرد.
در [6]، فنگ14 و همکاران یک طرح تسهیم چندراز پیش‌نگر ارایه کرده‌اند. در این طرح، یکی از رازها با استفاده از روش هرزبرگ15 و همکاران [5] مابین مجموعه شرکتکنندگان تسهیم شده و نتیجه xor سایر رازها با این راز اعلام عمومی می‌شود. برای بازسازی رازها، نیز در ابتدا از فرایند بازیابی طرح هرزبرگ و همکاران استفاده شده و راز تسهیم شده بازسازی می‌شود. در ادامه سایر رازها، با xor مقدار به دست آمده و مقادیر اعلام عمومی شده محاسبه میشوند.
4-1 ساختار مقاله
در ادامه این مقاله، در بخش 2، به بررسی پیش‌نیازهای این مقاله شامل درونیابی لاگرانژ، قضیه باقیمانده چینی و مساله لگاریتم گسسته پرداخته می‌شود. در بخش 3، طرح تسهیم چند راز پیش‌نگر پیشنهادی ارایه شده و امنیت و کارایی آن در بخش 4 بررسی می‌شود. در نهایت، نتیجه‌گیری‌ها در بخش5 بیان شده است.
2- مباحث مقدماتی
1-2 درونیابی لاگرانژ
تعریف 2-1-1 درونیابی لاگرانژ16: فرض کنیم نقاط 
با مولفه‌های اول متمایز داده شده باشند. مساله درونیابی لاگرانژ متناظر با نقاط فوق عبارت است از محاسبه چندجملهای
با کمترین درجه ممکن به طوری که
(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- چندجملهای زیر را می‌سازد:
(7) |
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
(8) |
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
(10) |
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
(11) |
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
پروتکل بازسازی | پروتکل نوسازی | پروتکل تسهیم راز | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| TTP |
|
|
| D | |||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||
پروتکل بازسازی | پروتکل نوسازی | پروتکل تسهیم راز | طرح | |||||||||||||||||||||||||||||||||||
|
|
| [5] | |||||||||||||||||||||||||||||||||||
|
|
| [5] و [7] | |||||||||||||||||||||||||||||||||||
|
|
| [6] | |||||||||||||||||||||||||||||||||||
|
|
| پیشنهادی |
امنیت | قابلیت بازسازی تدریجی رازها | قابلیت بازسازی ترتیبی رازها | قابلیت تسهیم چند راز | وارسی پذیری | اندازه‌ی سهام | طرح |
قوی | خیر | خیر | خیر | خیر |
| [5] |
قوی | خیر | خیر | بلی | خیر |
| [5] و [7] |
ضعیف | خیر | خیر | بلی | بلی |
| [6] |
قوی | بلی | بلی | بلی | بلی |
| پیشنهادی |
