Security limitations of Shamir’s secret sharing

Lemnouar, Noui

doi:10.1080/09720529.2021.1961902

Open Access Research Article

Security limitations of Shamir’s secret sharing

^*Noui LemnouarCorresponding authornoui@univ-batna2.dzAffiliation 1Department of MathematicsFaculty of Mathematics and Computer ScienceUniversity of Batna2Batna, 05000, AlgeriaAffiliation 2Lamie LaboratoryUniversity of Batna2Batna, 05000, AlgeriaView full profile →

* Corresponding author · click or hover a name for details

pp. 977–989Vol. 26Issue 4June 2023DOI: 10.1080/09720529.2021.1961902 Crossmark XML

Received:: 01 Feb 2021
Accepted:: 01 May 2021
Published Online:: 08 Mar 2022
Article type:: Research Article
Language:: EN
Article no.:: JDMSC-1421
Pages:: 977–989

Abstract

The security is so important for both storing and transmitting the digital data, the choice of parameters is critical for a security system, that is, a weak parameter will make the scheme very vulnerable to attacks, for example the use of supersingular curves or anomalous curves leads to weaknesses in elliptic curve cryptosystems, for RSA cryptosystem there are some attacks for low public exponent or small private exponent. In certain circumstances the secret sharing scheme is required to decentralize the risk. In the context of the security of secret sharing schemes, it is known that for the scheme of Shamir, an unqualified set of shares cannot leak any information about the secret. This paper aims to show that the well-known Shamir’s secret sharing is not always perfect and that the uniform randomization before sharing is insufficient to obtain a secure scheme. The second purpose of this paper is to give an explicit construction of weak polynomials for which the Shamir’s (k, n) threshold scheme is insecure in the sense that there exist a fewer than k shares which can reconstruct the secret. Particular attention is given to the scheme whose threshold is less than or equal to 6. It also showed that for certain threshold k, the secret can be calculated by a pair of shares with the probability of 1/2. Finally, in order to address the mentioned vulnerabilities, several classes of polynomials should be avoided.

Keywords

Elliptic curve Perfect scheme RSA cryptosystem Secret Shamir’s secret sharing Threshold

Subject Classifications

94A6094A6211T71

References

[1] Menezes, A. J., Okamoto, T., & Vanstone, S. A. (1993). Reducing elliptic curve logarithms to logarithms in a finite field. iEEE Transactions on information Theory, 39(5), 1639-1646. DOI: 10.1109/18.259647
[2] Wiener, M. J., & Zuccherato, R. J. (1998, August). Faster attacks on elliptic curve cryptosystems. In International workshop on selected areas in cryptography (pp. 190-200). Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-48892-8_15
[3] Abderrahmane Nitaj & Emmanuel Fouotsa (2019) A new attack on RSA and Demytko’s elliptic curve cryptosystem, Journal of Discrete Mathematical Sciences and Cryptography, 22:3, 391-409, DOI: 10.1080/09720529.2019.1587827.
[4] Majid Mumtaz & Luo Ping (2019) Forty years of attacks on the RSA cryptosystem: A brief survey, Journal of Discrete Mathematical Sciences and Cryptography, 22:1, 9-29, DOI: 10.1080/09720529.2018.1564201
[5] Abhishek Mishra & Ashutosh Gupta (2018) Multi secret sharing scheme using iterative method, Journal of Information and Optimization Sciences, 39:3, 631-641, DOI: 10.1080/02522667.2017.1385161
[6] Naor, M., & Shamir, A. (1995).Visual Cryptography, Proceedings of the Advances in Cryptology- Eurocrypt’94 (Vol. 950,pp. 1-12). Lecture Notes in Computer Science. ISBN 3-540-60176-7
[7] Deng,F.G., &Long, G.L., & Zhou, H.Y. (2005). An efficient quantum secret sharing scheme with Einstein–Podolsky–Rosen pairs. Physics Letters A, 340, 43-50. https://doi.org/10.1016/j.physleta.2005.04.007
[8] Kim, J.L., & Nari, L. (2017) .Secret sharing schemes based on additive codes over GF (4). Applicable Algebra in Engineering, Communication and Computing, 28(1), 79-97. DOI 10.1007/s00200-016-0296-5
[9] Sassia, M., & Noui, L. (2019) Characterization of some minimal codes for secret sharing. Asian-European Journal of Mathematics, 12(02), 1950026. https://doi.org/10.1142/S1793557119500268
[10] Shamir, A. (1979) .How to share a secret. Communications of the ACM, 22(11). 612-613. https://doi.org/10.1145/359168.359176
[11] Blakley, G. R. (1979, December). Safeguarding cryptographic keys. In Managing Requirements Knowledge, International Workshop on (pp. 313-313). IEEE Computer Society. DOI: 10.1109/AFIPS.1979.98
[12] Sándor, J., Mitrinovic, D. S., & Crstici, B. (2005). Handbook of number theory I. Springer Science & Business Media.
https://doi.org/10.1007/1-4020-3658-2_1.
[13] Kaliski B. (2011) Legendre Symbol. In: van Tilborg H.C.A., Jajodia S. (eds) Encyclopedia of Cryptography and Security. Springer, Boston, MA. https://doi.org/10.1007/978-1-4419-5906-5_418.
[14] Noui Lemnouar (2020) , Weaknesses of Shamir’s secret sharing scheme, International Conference on Computational Techniques and Intelligent Machine, ICCTIM 2020, Baba Farid College, Bathinda, India, November 26-28, 2020. https://babafaridgroup.edu.in/ICCTIM-2020/.
[15] C. Lin, L. Harn and D. Ye, “Ideal Perfect Multilevel Threshold Secret Sharing Scheme,” 2009 Fifth International Conference on Information Assurance and Security, Xi’an, 2009, pp. 118-121, doi; 10.1109/IAS.2009.279.
[16] Tezuka, S. (1995). Derandomization. In Uniform Random Numbers (pp. 161-192). Springer, Boston, MA. https://doi.org/10.1007/978-1-4615-2317-8_3.
[17] Fuller, A. T. (1976). The period of pseudo-random numbers generated by Lehmer’s congruential method. The Computer Journal, 19(2), 173-177. https://doi.org/10.1093/comjnl/19.2.173
[18] Stipčević, M., & Koç, Ç. K. (2014). True random number generators. In Open Problems in Mathematics and Computational Science (pp. 275-315). Springer, Cham. DOI: 10.1007/978-3-319-10683-0_12
[19] Haahr, M. (1998) Random.org – True random number service. Retrieved on 28 may 2021 from www.random.org.
[20] Zhu, Y., & Pei, D. (2002). An algorithm for DLP on anomalous elliptic curves over F p. Science in China Series A: Mathematics, 45(6), 773-777. https://doi.org/10.1360/02ys9084
[21] Sutherland, A. V. (2012). Identifying supersingular elliptic curves. LMS Journal of Computation and Mathematics, 15, 317-325.
DOI: https://doi.org/10.1112/S1461157012001106

Views: 685Downloads: 36Citations: 2