Two Verifiable Multi-Secret Sharing Schemes: A Linear Scheme with Standard Security and A Lattice-Based Scheme

Document Type : Original Article

Authors

Iran University of Science and Technology

Abstract

In this paper, we present two verifiable multi-secret sharing schemes, including a linear multi-secret sharing scheme with public access structure and a threshold (t, n) scheme based on the learning with errors (LWE) problem. The first scheme is a linear multi-secret sharing scheme in which a number of secrets is distributed by a dealer among a set of participants according to the access structure corresponding to each secret. This scheme has the advantages of the earlier ones and it also has many practical applications    compared to previous schemes including a multi-use verifiable multi-secret sharing scheme in which the secret reconstruction is according to the dealer’s preassigned order. In addition, the security of the scheme has been proven in the standard model. This scheme is based on the hard problems in number theory and therefore is not secure against quantum attacks. The second scheme presented in this paper is a lattice-based secret sharing scheme. In this scheme, which is a threshold (t, n) multi-secret sharing scheme, the presence of at least t participants is required for the reconstruction of the secret. The security of this scheme is based on the difficulty of the LWE problem and so it is resistant against quantum attacks.
 

Keywords


[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.##
Volume 8, Issue 3 - Serial Number 31
November 2020
Pages 101-115
  • Receive Date: 02 October 2019
  • Revise Date: 19 January 2020
  • Accept Date: 01 February 2020
  • Publish Date: 22 October 2020