پیشنهاد و مقایسه دو ﻃﺮح ﺗﺴﻬﯿﻢ ﭼﻨﺪ راز ﺗﺼﺪﯾﻖ ﭘﺬﯾﺮ: یک طرح ﺧﻄﯽ ﺑﺎ اﻣﻨﯿﺖ اﺳﺘﺎﻧﺪارد و یک طرح مشبکه مبنا

نوع مقاله: مقاله پژوهشی

نویسندگان

دانشگاه علم و صنعت ایران

چکیده

در این مقاله، دو طرح تسهیم چند راز با خاصیت تصدیق پذیری ارائه داده می‌شود که شامل یک ‎‏طرح تسهیم چند راز خطی با ساختار دسترسی عمومی و یک طرح آستانه‌ای (t,n)‎ بر اساس مسئله یادگیری با خطا ‎(LWE)‎ می‌باشد‎.‎ طرح اول، یک تسهیم چند راز (MSS) خطی می‌باشد که در آن تعدادی راز از طریق واسطه، متناسب با ساختار دسترسی مربوط به هر راز، در میان گروهی از سهامداران توزیع می‌شود. این طرح مزیت‌های طرح‌های قبلی را دارد و در مقایسه با آن‌ها کاربردهای عملی بسیاری مانند تصدیق پذیری و ویژگی ‌چند بار مصرفی را دارا می‌باشد. بازسازی رازها نیز بر اساس ترتیب از پیش تعیین شده توسط واسطه انجام می‌شود. به علاوه امنیت طرح نیز در مدل استاندارد ثابت شده است‎.‎ این طرح بر پایه مسائل سخت نظریه اعدادی بوده و بنابراین در برابر حملات کوانتومی ایمن نیست. طرح دوم ارائه شده در این مقاله یک طرح تسهیم راز مبتنی بر مشبکه‌ها می‌باشد. در این طرح که یک تسهیم چند راز آستانه‌ای  (t,n)‎ است، حضور هم‌زمان حداقل ‎t‎ شرکت کننده برای بازسازی راز الزامی است. امنیت این طرح برمبنای سختی مسئله ‎LWE‎ است. این مسئله بسیار سخت بوده و در برابر الگوریتم‌های کوانتومی مقاوم می‌باشد.

کلیدواژه‌ها


[1]     A. Shamir‎, “How to Share a Secret,” ‎Communications of the ACM‎, vol.‎ 22, no. 11, pp. ‎612-613‎, ‎1979‎.##
[2]     G. Blakley‎, “Safeguarding Cryptographic Keys,” ‎In Proc. AFIPS 1979 National‎ Computer Conf.‎, ‎pp‎. ‎313–317‎, ‎June 1979‎.##
[3]     Z. Eslami, ‎S. Kabiri Rad, “A New Verifiable Multi-Secret Sharing Scheme‎ Based on Bilinear Maps‎,” ‎Wirel‎. ‎Pers‎. ‎Commun.‎, ‎63‎, ‎pp‎. ‎459–467‎, ‎2012‎.##
[4]     Ch. Hsu‎, Q. Cheng‎, X. Tang‎, ‎et al, “An Ideal Multi-Secret Sharing Scheme Based on MSP‎,” ‎Inf‎. ‎Sci.‎, ‎181‎, ‎pp‎. ‎1403–1409‎, ‎2011‎.##
[5]     J. ‎Zhang‎, F. Zhang, “Information-theoretical Secure Verifiable Secret Sharing‎ with Vector Space Access Structures over Bilinear Groups and its Application,” Future Gener‎. ‎Comput‎. ‎Syst.‎ 52‎, ‎pp‎. ‎109–115‎, ‎2015‎.##
[6]     M. Ben-Or‎, Sh. Goldwasser‎, ‎A. Wigderson, “Completeness Theorems for Non-cryptographic Fault-Tolerant Distributed Computation (Extended Abstract),”‎ ‎ STOC‎, ‎p‎p. ‎1–10‎, ‎1988‎.##
[7]     D. Chaum‎, ‎C. Crepeau‎, I. ‎Damgard, “Multiparty Unconditionally Secure Protocols (Extended Abstract),” ‎ ‎STOC‎, ‎pp‎. ‎11–19‎, ‎1988‎.##
[8]     B Chor‎, ‎Sh. Goldwasser‎, ‎S Micali, ‎B. Awerbuch‎, “Verifiable Secret Sharing and Achieving Simultaneity in the Presence of Faults (Extended Abstract),” ‎ ‎FOCS‎, p‎p‎. ‎383–395‎, ‎1985‎.##
[9]     C. Ma, X. Ding, “Proactive Verifiable Linear Integer Secret Sharing Scheme,” Information and Communications Security‎, (LNCS‎, ‎5927)‎, ‎pp‎. ‎439–448‎, ‎2009‎.##
[10]  S. Mashhadi‎‎, M. Hadian‎, “Two Verifiable Multi Secret Sharing Schemes Based‎ on Nonhomogeneous Linear Recursion and LFSR Public-Key Cryptosystem‎,” Inf‎. ‎Sci.‎, ‎ 294‎, ‎pp‎. ‎31–40‎, ‎2015‎.##
[11]  T. S. Wu‎‎, Y. M. Tseng‎, “Publicly Verifiable Multi-Secret Sharing Scheme‎ from Bilinear Pairings,” ‎IET Inf‎. ‎Sec.‎, ‎7‎, ‎pp‎. ‎239–246‎, ‎2013‎.##
[12]  C. Lin‎, ‎L. Harn, “Unconditionally Secure Verifiable Secret Sharing Scheme‎,” AISS‎: ‎Adv‎. ‎Inf‎. ‎Sci‎. ‎Serv‎. ‎Sci.‎, ‎4‎, ‎pp‎. ‎514–518, 2012‎.##
[13]  D. R. ‎Stinson, R. ‎Wei “Unconditionally Secure Proactive Secret Sharing‎ Scheme with Combinatorial Structures‎, ‎Selected Areas in Cryptography‎,” Selected Areas in Cryptography‎: ‎SAC'99‎, ‎(LNCS‎, ‎1758)‎, ‎pp‎. ‎200–214‎, ‎2000‎.##
[14]  M. Fatemi‎, R. Ghasemi, T. ‎Eghlidos, M. R. Aref, “Efficient Multistage Secret‎ Sharing Scheme Using Bilinear Map,” ‎IET Inf‎. ‎Sec.‎, ‎8‎, ‎pp‎. ‎224–229‎, ‎2014‎.##
[15]  J. Herranz‎, ‎ A. Ruiz‎‎, ‎G. Sáez‎, “Sharing Many Secrets with Computational‎ Provable Security‎,” ‎Inf‎. ‎Proc‎. ‎Lett.‎, ‎113‎, ‎pp‎. ‎572–579‎, ‎2013‎.##
[16]  S. Mashhadi, “How to Fairly Share Multiple Secrets Stage by Stage” ‎, ‎Wirel‎. Pers‎. ‎Commun.‎, ‎90‎, ‎pp‎. ‎93–107‎, ‎2016‎.##
[17]  L. J. Pang, Y. M. ‎Wang‎, “A New (t‎, ‎n) Multi-Secret Sharing Scheme Based on Shamir’s Secret‎ Sharing‎,” ‎Applied Mathematics and Computation‎, vol. ‎167‎, ‎pp. 840-848‎, ‎2005‎.##
[18]  T. Y. Chang‎, M. S.  ‎Hwang‎, ‎W. P. Yang‎, ‎ “A New Multi-Stage Secret Sharing‎ Scheme Using One-Way Function,” ACM SIGOPS Oper‎. ‎Syst.‎, ‎39‎, ‎pp‎. ‎48–55, 2005‎.##
[19]  J. He‎‎, E.‎ Dawson‎, “Multistage Secret Sharing Based on One-Way Function‎,” Electron‎. ‎Lett.‎, vol. ‎30‎, ‎pp‎. ‎1591–1592‎, ‎1994‎.##
[20]  H. X. Li‎‎, ‎C. T. Cheng‎‎, L. J. ‎Pang‎‎, “An Improved Multi-Stage (t‎, ‎n)-Threshold‎ Secret Sharing Scheme‎,” ‎WAIM‎, ‎ (LNCS‎, ‎3739)‎, ‎pp‎. ‎267–274‎, ‎2005‎.##
[21]  P. W. Shor, “Algorithms for Quantum Computation‎: ‎Discrete Logarithms and‎ Factoring‎,” ‎Proc. of the 35th Annual Symposium on Foundations of‎ Computer Science‎, ‎Washington‎, ‎DC‎, ‎USA‎: ‎IEEE Computer Society‎, pp‎. ‎124-134‎, ‎1994‎.##
[22]  R‎. ‎J‎. ‎McEliece‎, “A Public-Key Cryptosystem Based on Algebraic Coding Theory‎,” DSN Progress Report‎, ‎vol‎. ‎42‎, ‎no‎. ‎44‎, ‎pp‎. ‎114-116‎, ‎1978‎.##
[23]  D‎. ‎Bernstein‎, ‎J‎. ‎Buchmann‎, ‎E‎. ‎Dahmen‎, “Post-Quantum Cryptography,”‎ Springer‎, ‎2009‎.##
[24]  M‎. ‎Ajtai‎, “Generating Hard Instances Of Lattice Problems (Extended Abstract),”‎ Proc. of the Twenty-Eighth Annual ACM Symposium on Theory of‎ Computing‎, ‎New York‎, ‎NY‎, ‎USA‎: ‎ACM‎‎, ‎pp‎. ‎99-108,  1996.##
[25]  O‎. ‎Goldreich‎, ‎S‎. ‎Goldwasser‎, ‎S‎. ‎Halevi, “Public-key Cryptosystems from Lat‎Tice Reduction Problems,” ‎Advances in Cryptology CRYPTO 97‎, ‎ser‎. ‎Lecture‎ Notes in Computer Science‎, ‎J‎. ‎Kaliski‎, ‎BurtonS.‎, ‎Ed‎. ‎Springer Berlin Hei‎delberg‎, ‎vol‎. ‎1294‎, ‎pp‎. ‎112-131‎, ‎1997‎.##
[26]  Georgescu‎, “A Lwe-Based Secret Sharing Scheme‎,” ‎IJCA Special Issue on‎ Network Security and Cryptography‎, ‎ ‎no‎. ‎3‎, ‎pp‎. ‎27-29‎, ‎December‎, ‎published by Foundation of Computer Science‎, ‎New York‎, ‎USA‎, ‎2011‎.
[27]  R‎. ‎El Bansarkhani‎, ‎M‎. ‎Meziani‎, ‎“An Efficient Lattice-Based Secret Sharing‎ Construction‎,” ‎Information Security Theory and Practice‎. ‎Security‎, ‎Privacy‎ and Trust in Computing Systems and Ambient Intelligent Ecosystems‎, ser‎. ‎Lecture Notes in Computer Science‎, ‎I‎. ‎Askoxylakis‎, ‎H‎. ‎Phls‎, ‎and J‎. Posegga‎, ‎Eds‎. ‎Springer Berlin Heidelberg‎, ‎vol‎. ‎7322‎, ‎pp‎. ‎160-168‎, ‎2012‎.##
[28]  J. Shao‎, ‎Z. F. Cao, “A New Efficient (t‎, ‎n) Verifiable Multi-Secret Sharing (VMSS) Based on YCH‎ Scheme‎,” ‎Applied Mathematics and Computation‎, ‎168‎, ‎pp. 135–140‎, ‎2005‎.##
[29]  M. ‎Tadayon‎, ‎H.‎ ‎Khanmohammadi‎‎, M. Haghighi‎, “Dynamic and Verifiable‎ Multi-Secret Sharing Scheme Based on Hermite Interpolation and Bilinear‎ Maps‎,” ‎IET Inf‎. ‎Sec.‎, ‎9‎, ‎pp‎. ‎234–239‎, ‎2015‎.##
[30]  Ch. Hsu‎, ‎L. Harn‎, G. Cui, “An Ideal Multi-Secret Sharing Scheme Based on Connectivity of Graphs‎,” Wireless Personal Communication, 77, pp. 383-394, 2014##.
[31]  Ch. Hsu‎, G. Cui‎, Q. Cheng‎, J. Chen, “A Novel Linear Multi-Secret Sharing Scheme for Group Communication in Wireless Mesh Networks‎,” Network and Computer Applications‎, 34, pp. 464-468, 2011‎.##
[32]  M. Liu‎, L. ‎Xiao‎, ‎Z. Zhang‎, “Linear Multi-Secret Sharing Schemes Based on Multi-Party‎ Computation‎,” ‎Finite Fields and Their Applications‎, vol. ‎12‎, ‎pp. 704-13‎, ‎2006‎.##
[33]  S. Mashhadi, M. Hadian Dehkordi, N. Kiamari, “Provably Secure Verifiable Multi-Stage Secret Sharing Scheme Based on Monotone Span Program‎,” IET Information Security, vol. 11, pp.326-331, 2017.##
[34]  S. Mashhadi, “Computationally-Secure Multiple Secret Sharing‎: ‎Models‎, Schemes‎, ‎and Formal Security Analysis‎,” ‎The ISC Int‎. ‎J‎. ‎Inf‎. ‎Sec.‎, vol. ‎7‎, ‎pp‎. 1–10‎, ‎2015‎.##
[35]  M‎. ‎Karchmer‎, ‎A‎. ‎Wigderson‎, ‎“On Span Programs‎,” ‎ In Proceedings of the‎ Eighth Annual Conf. On Structure in Complexity‎, ‎San Diego‎, ‎CA‎, ‎pp‎. ‎102-111‎, ‎May 1993‎.##
[36]  D‎. ‎Micciancio‎, ‎S‎. ‎Goldwasser‎, “Complexity of Lattice Problems‎: ‎A Cryp‎tographic Perspective‎,” ‎Ser‎. ‎Milken Institute Series on Financial Inno‎vation and Economic Growth‎. ‎Springer US‎, ‎2002‎. ‎[Online]‎. ‎Available‎: http://books.google.com/books?id=N4lHlGwy1AUC##
[37]  O. Regev‎, ‎ “On Lattices‎, ‎Learning with Errors‎, ‎Random Linear Codes‎, ‎and‎ Cryptography‎,” ‎J‎. ‎ACM‎, ‎56(6):34:134:40‎, ‎September 2009‎.##
[38]  J. ‎Hoffstein‎, ‎J‎. ‎Pipher‎, ‎J‎. ‎Silverman‎, ‎Ntru “A Ring-Based Public Key Cryp‎Tosystem‎,” ‎Algorithmic Number Theory‎, ‎Ser‎. ‎Lecture Notes in Computer‎ Science‎, ‎1423, pp.267-288, 1998.##
[39]  M.H. Dehkordi, R. Ghasemi, “A Lightweight Public Verifiable Multi Secret Sharing Scheme Using Short Integer Solution,” In Wireless Personal Communi- Cations, Springer, pp. 1459–1469, 2016.##
[40]  H. Pilaram, T. Eghlidos “An Efficient Lattice Based Multi-stage IEEE Transactions on Dependable and Secure Computing, vol. 14, no. 1, pp.2-8‎, 2015‎.##
[41]  B. Rajabi, Z. Eslami, “A Verifiable Threshold Secret Sharing Scheme Based on Lattices‎,” Information Sciences, Vol. 501 pp.655–661, 2019.##