Analysis of the applicability of existing secret separation schemes in the post-quaternary era
https://doi.org/10.17586/2226-1494-2025-25-3-446-456
Abstract
Modern approaches to secret sharing have been examined, encompassing both classical and post-quantum cryptographic schemes. The study explores methods for distributing secret information among multiple participants using various mathematical primitives, such as Lagrange and Newton polynomials, the Chinese remainder theorem, error-correcting codes, lattice theory, elliptic curve isogenies, multivariate equations, and hash functions. A comparative analysis of different schemes is provided in terms of their resistance to quantum attacks, efficiency, and compliance with Shamir’s criteria. Special attention is given to assessing the schemes resilience against attacks using quantum computers, which is particularly relevant given the advancement of quantum technologies. The advantages and disadvantages of each scheme are discussed, including their computational complexity, flexibility, and adaptability to various conditions. It is shown that classical schemes, such as those by Shamir and Newton, remain efficient and easy to implement but are vulnerable to quantum attacks. Meanwhile, post-quantum schemes based on lattice theory demonstrate a high level of security but require more complex computations.
Keywords
post-quantum cryptography,
secret sharing scheme,
threshold scheme,
public-key cryptography,
lattice theory,
elliptic curves,
multivariate equations,
error-correcting codes,
hash functions
Supporting agencies: The work was carried out within the framework of the State Assignment (project No. FSER-2025-0003).
About the Authors
E. F. Kustov
ITMO University
Russian Federation
Russian Federation
Elizar F. Kustov — PhD Student
Saint Petersburg, 197101
sc 57672934000
S. V. Bezzateev
Saint-Petersburg State University of Aerospace Instrumentation (SUAI);
ITMO University
Russian Federation
Russian Federation
Sergey V. Bezzateev — D.Sc., Associate Professor, Head of Department
Saint Petersburg, 190000;
Professor
Saint Petersburg, 197101
sc 6602425996
References
1. Blakley G.R. Safeguarding cryptographic keys. Proc. of the International Workshop on Managing Requirements Knowledge (MARK), 1979, pp. 313–313. https://doi.org/10.1109/mark.1979.8817296
2. Shamir A. How to share a secret. Communications of the ACM, 1979, vol. 22, no. 11, pp. 612–613. https://doi.org/10.1145/359168.35917
3. Ilin V.A., Pozniak E.G. Fundamentals of Mathematical Analysis. Moscow, Fizmatlit Publ., 2005. 656 p. (in Russian)
4. Barker E., Barker W., Burr W., Polk W., Smid M. NIST special publication 800-57. NIST Special publication, 2007, vol. 800, no. 57, pp. 1–142.
5. Desmedt Y., Frankel Y. Threshold cryptosystems. Lecture Notes in Computer Science, 1990, vol. 435, pp. 307–315. https://doi.org/10.1007/0-387-34805-0_28
6. Gennaro R., Jarecki S., Krawczyk H., Rabin T. Secure distributed key generation for discrete-log based cryptosystems. Lecture Notes in Computer Science, 1999, vol. 1592, pp. 295–310. https://doi.org/10.1007/3-540-48910-X_21
7. Menezes A.J. Handbook of Applied Cryptography. Taylor & Francis, 1997, 810 p.
8. Feldman P. A practical scheme for non-interactive verifiable secret sharing. Proc. of the 28th Annual Symposium on Foundations of Computer Science (sfcs 1987), 1987, pp. 427–438. https://doi.org/10.1109/SFCS.1987.4
9. McEliece R.J., Sarwate D.V. On sharing secrets and Reed-Solomon codes. Communications of the ACM, 1981, vol. 24, no. 9, pp. 583–584. https://doi.org/10.1145/358746.358762
10. Massey J.L. Minimal codewords and secret sharing. Proc. of the 6th joint Swedish-Russian international workshop on information theory, 1993, pp. 276–279.
11. Martínez-Peñas U. Communication efficient and strongly secure secret sharing schemes based on algebraic geometry codes. IEEE Transactions on Information Theory, 2018, vol. 64, no. 6, pp. 4191–4206. https://doi.org/10.1109/tit.2018.2823326
12. Sole P., Çalkavur S., Bonnecaze A., Dela Cruz R. Code Based Secret Sharing Schemes: Applied Combinatorial Coding Theory. World Scientific Pub Co Inc., 2022. 212 p.
13. Kurihara J., Uyematsu T., Matsumoto R. Secret sharing schemes based on linear codes can be precisely characterized by the relative generalized Hamming weight. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 2012, vol. E95.A, no. 11, pp. 2067–2075. https://doi.org/10.1587/transfun.e95.a.2067
14. Massey J.L. Some applications of coding theory in cryptography. Codes and Ciphers: Cryptography and Coding IV, 1995, pp. 33–47.
15. Steinfeld R., Wang H., Pieprzyk J. Lattice-based thresholdchangeability for standard Shamir secret-sharing schemes. Lecture Notes in Computer Science. 2004, vol. 3329, pp. 170–186. https://doi.org/10.1007/978-3-540-30539-2_13
16. Ajtai M. Generating hard instances of lattice problems (extended abstract). Proc. of the 28th Annual ACM Symposium on Theory of Computing (STOC ‘96), 1996, pp. 99–108. https://doi.org/10.1145/237814.237838
17. Regev O. On lattices, learning with errors, random linear codes, and cryptography. Journal of the ACM (JACM), 2009, vol. 56, no. 6, pp. 1–40. https://doi.org/10.1145/1568318.1568324
18. Bansarkhani R.E., Meziani M. An efficient lattice-based secret sharing construction. Lecture Notes in Computer Science, 2012, vol. 7322, pp. 160–168. https://doi.org/10.1007/978-3-642-30955-7_14
19. Khorasgani H.A. Asaad S., Eghlidos T., Aref M. A lattice-based threshold secret sharing scheme. Proc. of the 11th International ISC Conference on Information Security and Cryptology. 2014, pp. 173–179. https://doi.org/10.1109/ISCISC.2014.6994043
20. Ajtai M., Dwork C. A public-key cryptosystem with worst-case/ average-case equivalence. Proc. of the 29th Annual ACM Symposium on Theory of Computing (STOC ‘97), 1997, pp. 284–293. https://doi.org/10.1145/258533.258604
21. Lyubashevsky V., Micciancio D. Generalized compact knapsacks are collision resistant. Lecture Notes in Computer Science, 2006, vol. 4052, pp. 144–155. https://doi.org/10.1007/11787006_13
22. Peikert C., Rosen A. Efficient collision-resistant hashing from worstcase assumptions on cyclic lattices. Lecture Notes in Computer Science , 2006, vol. 3876, pp. 145–166. https://doi.org/10.1007/11681878_8
23. Georgescu A. A LWE-based secret sharing scheme. IJCA Special Issue on Network Security and Cryptography, NSC, 2011, vol. 3, pp. 27–29.
24. Dehkordi M.H., Farahi S.T., Mashhadi S. LWE-based verifiable essential secret image sharing scheme ((t, s, k, n) (t,s,k,n)-VESIS). IET Image Processing, 2024, vol. 18, no. 4, pp. 1053–1072. https://doi.org/10.1049/ipr2.13006
25. Golub G.H., Van Loan C.F. Matrix Computations. JHU press, 2013, 784 p.
26. Shor P.W. Algorithms for quantum computation: discrete logarithms and factoring. Proc. of the 35th Annual Symposium on Foundations of Computer Science, 1994, pp. 124–134. https://doi.org/10.1109/SFCS.1994.365700
27. Smith B. Pre-and post-quantum Diffie–Hellman from groups, actions, and isogenies. Lecture Notes in Computer Science, 2018, vol. 11321, pp. 3–40. https://doi.org/10.1007/978-3-030-05153-2_1
28. Couveignes J.M. Hard homogeneous spaces: Preprint. HAL science ouverte. 2006. hal-04538731
29. Rostovtsev A., Stolbunov A. Public-key cryptosystem based on isogenies. IACR Cryptology ePrint Archive, 2006.
30. Teske E. An elliptic curve trapdoor system. Journal of Cryptology, 2006, vol. 19, pp. 115–133. https://doi.org/10.1007/s00145-004-0328-3
31. Charles D.X., Lauter K.E., Goren E.Z. Cryptographic hash functions from expander graphs. Journal of Cryptology, 2009, vol. 22, no. 1, pp. 93–113. https://doi.org/10.1007/s00145-007-9002-x
32. Jao D., De Feo L. Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies. Lecture Notes in Computer Science, 2011, vol. 7071, pp. 19–34. https://doi.org/10.1007/978-3-642-25405-5_2
33. Castryck W., Lange T., Martindale C., Panny L., Renes J. CSIDH: an efficient post-quantum commutative group action. Lecture Notes in Computer Science, 2018, vol. 11274, pp. 395–427. https://doi.org/10.1007/978-3-030-03332-3_15
34. Beullens W., Kleinjung T., Vercauteren F. CSI-FiSh: efficient isogeny based signatures through class group computations. Lecture Notes in Computer Science, 2019, vol. 11921, pp. 227–247. https://doi.org/10.1007/978-3-030-34578-5_9
35. Stolbunov A. Constructing public-key cryptographic schemes based on class group action on a set of isogenous elliptic curves. Advances in Mathematics of Communications, 2010, vol. 4, no. 2, pp. 215–235. https://doi.org/10.3934/amc.2010.4.215
36. De Feo L., Meyer M. Threshold schemes from isogeny assumptions. Lecture Notes in Computer Science, 2020, vol. 12111, pp. 187–212. https://doi.org/10.1007/978-3-030-45388-6_7
37. Cozzo D., Smart N.P. Sashimi: cutting up CSI-FiSh secret keys to produce an actively secure distributed signing protocol. Lecture Notes in Computer Science, 2020, vol. 12100, pp. 169–186. https://doi.org/10.1007/978-3-030-44223-1_10
38. Sotáková J. Elliptic curves, isogenies, and endomorphism rings: Preprint. 2020.
39. Kim T. Security analysis of group action inverse problem with auxiliary inputs with application to CSIDH Parameters. Lecture Notes in Computer Science, 2020, vol. 11975, pp. 165–174. https://doi.org/10.1007/978-3-030-40921-0_10
40. Meyer M. Practical isogeny-based cryptography: dissertation. Universität Würzburg, 2021. 167 p.
41. Rogaway P., Shrimpton T. Cryptographic hash-function basics: Definitions, implications, and separations for preimage resistance, second-preimage resistance, and collision resistance. Lecture Notes in Computer Science, 2004, vol. 3017, pp. 371–388. https://doi.org/10.1007/978-3-540-25937-4_24
42. Zheng Y., Hardjono T., Seberry J. Reusing shares in secret sharing schemes. The Computer Journal, 1994, vol. 37, no. 3, pp. 199–205. https://doi.org/10.1093/comjnl/37.3.199
43. Liaojun P., Huixian L., Yumin W. An efficient and secure multi-secret sharing scheme with general access structures. Wuhan University Journal of Natural Sciences, 2006, vol. 11, no. 6, pp. 1649–1652. https://doi.org/10.1007/BF02831842
44. Lin H.Y., Yeh Y.S. Dynamic multi-secret sharing scheme. International Journal of Contemporary Mathematical Sciences, 2008, vol. 3, no. 1, pp. 37–42.
45. Das A., Adhikari A. An efficient multi-use multi-secret sharing scheme based on hash function. Applied Mathematics Letters, 2010, vol. 23, no. 9, pp. 993–996. https://doi.org/10.1016/j.aml.2010.04.024
46. Chum C.S., Zhang X. Hash function-based secret sharing scheme designs. Security and Communication Networks, 2013, vol. 6, no. 5, pp. 584–592. https://doi.org/10.1002/sec.576
47. Bertoni G., Daemen J., Peeters M., Van Assche G. Keccak. Lecture Notes in Computer Science, 2013, vol. 7881, pp. 313–314. https://doi.org/10.1007/978-3-642-38348-9_19
48. Putra R.A., Effendie A.R., Aisah S.N., Christy J.R., Marpaung E.C.F., Syarkowi M.Z.H., Devi P.K. Analyzing the relationship between capital and risk in Indonesian life insurance companies using the 2SLS and GMM methods. Jurnal Riset dan Aplikasi Matematika, 2024, vol. 8, no. 2, pp. 142–157.
49. Karnin E., Greene J., Hellman M. On secret sharing systems. IEEE Transactions on Information Theory, 1983, vol. 29, no. 1, pp. 35–41. https://doi.org/10.1109/TIT.1983.1056621
50. Ning Y., Miao F., Huang W., Meng K., Xiong Y., Wang X. Constructing ideal secret sharing schemes based on Chinese remainder theorem. Lecture Notes in Computer Science, 2018, vol. 11274, pp. 310–331. https://doi.org/10.1007/978-3-030-03332-3_12
51. Asmuth C., Bloom J. A modular approach to key safeguarding. IEEE Transactions on Information Theory, 1983, vol. 29, no. 2, pp. 208–210. https://doi.org/10.1109/tit.1983.1056651
52. Galibus T., Matveev G. Finite fields, Gröbner bases and modular secret sharing. Journal of Discrete Mathematical Sciences and Cryptography, 2012, vol. 15, no. 6, pp. 339–348. https://doi.org/10.1080/09720529.2012.10698386
Review
For citations:
Kustov E.F., Bezzateev S.V. Analysis of the applicability of existing secret separation schemes in the post-quaternary era. Scientific and Technical Journal of Information Technologies, Mechanics and Optics. 2025;25(3):446-456. (In Russ.) https://doi.org/10.17586/2226-1494-2025-25-3-446-456
Views:
5
Email this article 