Анализ применимости существующих схем разделения секрета в условиях постквантовой эры

Рассмотрены современные подходы к разделению секрета, включая как классические, так и постквантовые криптографические схемы. Исследованы методы распределения секретной информации между несколькими участниками с использованием математических примитивов, таких как многочлены Лагранжа и Ньютона, китайская теорема об остатках, коды исправляющие ошибки, теория решеток, изогении эллиптических кривых, многомерные уравнения и хэш-функции. Приведен сравнительный анализ различных схем с точки зрения их устойчивости к квантовым атакам, эффективности и соответствия критериям Шамира. Особое внимание уделено оценке устойчивости схем к атакам с использованием квантовых компьютеров, что особенно актуально в условиях развития квантовых технологий. Рассмотрены преимущества и недостатки каждой из схем, включая их вычислительную сложность, гибкость и возможность адаптации к различным условиям. Показано, что классические схемы, такие как схемы Шамира и Ньютона, остаются эффективными и простыми в реализации, но уязвимы к квантовым атакам. В то же время постквантовые схемы, основанные на теории решеток, демонстрируют высокий уровень безопасности, но требуют более сложных вычислений.

1. Blakley G.R. Safeguarding cryptographic keys // Proc. of the International Workshop on Managing Requirements Knowledge (MARK). 1979. P. 313–313. https://doi.org/10.1109/mark.1979.8817296

2. Shamir A. How to share a secret // Communications of the ACM. 1979. V. 22. N 11. P. 612–613. https://doi.org/10.1145/359168.35917

3. Ильин В.А., Позняк Э.Г. Основы математического анализа. М.: Физматлит, 2005. 646 с.

4. Barker E., Barker W., Burr W., Polk W., Smid M. NIST special publication 800-57 // NIST Special publication. 2007. V. 800. N 57. P. 1–142.

5. Desmedt Y., Frankel Y. Threshold cryptosystems // Lecture Notes in Computer Science. 1990. V. 435. P. 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. V. 1592. P. 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. P. 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. V. 24. N 9. P. 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. P. 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. V. 64. N 6. P. 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. V. E95.A. N 11. P. 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. P. 33–47.

15. Steinfeld R., Wang H., Pieprzyk J. Lattice-based thresholdchangeability for standard Shamir secret-sharing schemes // Lecture Notes in Computer Science. 2004. V. 3329. P. 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. P. 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. V. 56. N 6. P. 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. V. 7322. P. 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. P. 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. P. 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. V. 4052. P. 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 S c i e n c e . 2 0 0 6 . V. 3876. P. 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. V. 3. P. 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. V. 18. N 4. P. 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. P. 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. V. 11321. P. 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. V. 19. P. 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. V. 22. N 1. P. 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. V. 7071. P. 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. V. 11274. P. 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. V. 11921. P. 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. V. 4. N 2. P. 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. V. 12111. P. 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. V. 12100. P. 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. V. 11975. P. 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. V. 3017. P. 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. V. 37. N 3. P. 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. V. 11. N 6. P. 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. V. 3. N 1. P. 37–42.

45. Das A., Adhikari A. An efficient multi-use multi-secret sharing scheme based on hash function // Applied Mathematics Letters. 2010. V. 23. N 9. P. 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. V. 6. N 5. P. 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. V. 7881. P. 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. V. 8. N 2. P. 142–157.

49. Karnin E., Greene J., Hellman M. On secret sharing systems // IEEE Transactions on Information Theory. 1983. V. 29. N 1. P. 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. V. 11274. P. 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. V. 29. N 2. P. 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. V. 15. N 6. P. 339–348. https://doi.org/10.1080/09720529.2012.10698386