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

Кустов Елизар Филаретович, Беззатеев Сергей Валентинович

doi:10.17586/2226-1494-2025-25-3-446-456

2025 , ТОМ 25, НОМЕР 3 ( май-июнь )

ISSN 2226-1494 (print), ISSN 2500-0373 (online)

Меню

Публикации

Главный редактор

НИКИФОРОВ
Владимир Олегович
д.т.н., профессор

Партнеры

doi: 10.17586/2226-1494-2025-25-3-446-456

УДК 004.056.55

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

Кустов Е.Ф., Беззатеев С.В.

Читать статью полностью

Язык статьи - русский

Ссылка для цитирования:

Кустов Е.Ф., Беззатеев С.В. Анализ применимости существующих схем разделения секрета в условиях постквантовой эры // Научно-технический вестник информационных технологий, механики и оптики. 2025. Т. 25, № 3. С. 446–456. doi: 10.17586/2226-1494-2025-25-3-446-456

Аннотация

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

Ключевые слова: постквантовая криптография, схема распределение секрета, пороговая схема, криптография с открытым ключом, теория решеток, эллиптические кривые, многомерные уравнения, коды исправляющее ошибки, хэш-функции

Благодарности. Работа выполнена в рамках государственного задания (проект № FSER-2025-0003).

Список литературы

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
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
Ильин В.А., Позняк Э.Г. Основы математического анализа. М.: Физматлит, 2005. 646 с.
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.
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
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
Menezes A.J. Handbook of Applied Cryptography. Taylor & Francis, 1997. 810 p.
Feldman P. A practical scheme for non-interactive verifiable secret sharing // Proc. of the 28^th Annual Symposium on Foundations of Computer Science (sfcs 1987). 1987. P. 427–438. https://doi.org/10.1109/SFCS.1987.4
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
Massey J.L. Minimal codewords and secret sharing // Proc. of the 6^thjoint Swedish-Russian international workshop on information theory. 1993. P. 276–279.
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
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.
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
Massey J.L. Some applications of coding theory in cryptography // Codes and Ciphers: Cryptography and Coding IV. 1995. P. 33–47.
Steinfeld R., Wang H., Pieprzyk J. Lattice-based threshold-changeability 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
Ajtai M. Generating hard instances of lattice problems (extended abstract) // Proc. of the 28^th Annual ACM Symposium on Theory of Computing (STOC '96). 1996. P. 99–108. https://doi.org/10.1145/237814.237838
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
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
Khorasgani H.A. Asaad S., Eghlidos T., Aref M. A lattice-based threshold secret sharing scheme // Proc. of the 11^th International ISC Conference on Information Security and Cryptology. 2014. P. 173–179. https://doi.org/10.1109/ISCISC.2014.6994043
Ajtai M., Dwork C. A public-key cryptosystem with worst-case/average-case equivalence // Proc. of the 29^th Annual ACM Symposium on Theory of Computing (STOC '97). 1997. P. 284–293. https://doi.org/10.1145/258533.258604
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
Peikert C., Rosen A. Efficient collision-resistant hashing from worst-case assumptions on cyclic lattices // Lecture Notes in Computer Science. 2006. V. 3876. P. 145–166. https://doi.org/10.1007/11681878_8
Georgescu A. A LWE-based secret sharing scheme // IJCA Special Issue on Network Security and Cryptography, NSC. 2011. V. 3. P. 27–29.
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
Golub G.H., Van Loan C.F. Matrix Computations. JHU press, 2013. 784 p.
Shor P.W. Algorithms for quantum computation: discrete logarithms and factoring // Proc. of the 35^th Annual Symposium on Foundations of Computer Science. 1994. P. 124–134. https://doi.org/10.1109/SFCS.1994.365700
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
Couveignes J.M. Hard homogeneous spaces: Preprint // HAL science ouverte. 2006. hal-04538731
Rostovtsev A., Stolbunov A. Public-key cryptosystem based on isogenies // IACR Cryptology ePrint Archive. 2006.
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
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
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
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
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
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
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
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
Sotáková J. Elliptic curves, isogenies, and endomorphism rings: Preprint. 2020.
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
Meyer M. Practical isogeny-based cryptography: dissertation. Universität Würzburg, 2021. 167 p.
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
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
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
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.
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
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
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
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.
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
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
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
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

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License