КіСА | Зміст

Том 61 >>> № 6 ЛИСТОПАД — ГРУДЕНЬ 2025

-->

УДК 621.391:519.2:519.7

В.К. ЗАДІРАКА
Інститут кібернетики ім. В.М. Глушкова НАН України, Київ, Україна,
zvk140@ukr.net

А.М. КУДІН
Фізико-технічний інститут Національного технічного університету України «Київський політехнічний інститут імені Ігоря Сікорського»; Національний банк України, Київ, Україна, pplayshner@gmail.com

І.А. КУДІН
Фізико-технічний інститут Національного технічного університету України «Київський політехнічний інститут імені Ігоря Сікорського», Київ, Україна,
mmzi.cat@gmail.com

І.В. ШВІДЧЕНКО
Інститут кібернетики ім. В.М. Глушкова НАН України, Київ, Україна,
inetsheva@gmail.com

КРИПТОСИСТЕМИ, СТІЙКІ В ПЕВНИХ МОДЕЛЯХ ОБЧИСЛЕНЬ

Анотація. Розглянуто проблему оцінювання стійкості криптографічних перетворень у сучасній криптографії, яке зазвичай реалізується з використанням аксіоматичного або доказового підходу. Оскільки квантова модель обчислень змінює складність певних обчислювальних задач (наприклад, задач факторизації цілих чисел), у криптографії вивчають класи алгоритмів, які залишатимуться стійкими в квантовій моделі обчислень — так звані «постквантові криптографічні алгоритми». Узагальненням цієї постановки задачі є дослідження моделей обчислень, що містять алгоритми криптоаналізу, найкращий з яких має експоненційну складність або наближену до неї. Розглянуто узагальнення проблеми існування криптосистем, стійких у постквантовому світі, а саме криптосистем, стійких у певних моделях обчислень, а також можливість практичного застосування таких моделей. Основним результатом роботи є створення універсальної обчислювальної моделі, яка узагальнює цілий клас перспективних обчислювальних моделей, зокрема квантової, та побудова криптосистеми, стійкої у межах такої обчислювальної моделі.

Ключові слова: постквантова криптографія, релятивістська криптографія, моделі обчислень, генетичні алгоритми, обернені обчислення, блокчейн.

повний текст

СПИСОК ЛІТЕРАТУРИ

1. Brassard G. An optimally secure relativized cryptosystem. ACM SIGACT News. 1983. Vol. 15, N 1. P. 28–33. https://doi.org/10.1145/1008908.1008912.
2. К. Шеннон. Теория связи в секретных системах. В кн.: К. Шеннон. Работы по теории информации и кибернетике. Москва: ИЛ, 1963. С. 333–369.
3. Goldwasser S., Bellare M. Lecture notes on cryptography. Cambridge, Massachusetts: MIT Computer Science and Artificial Intelligence Laboratory, 2008. 289 p.
4. Goldreich O. Foundations of cryptography. Vol. 1. Basic tools. London: Cambridge University Press, 2001. 555 p.
5. Zadiraka V.K., Kudin A.M. New models and methods for estimating the cryptographic strenght of information security systems. Cybernetics and Systems Analysis. 2017. Vol. 53, N 6. P. 978–985. https://doi.org/10.1007/s10559-017-9999-2.
6. Jurgensen H., Robbins L. Towards foundations of cryptography: investigation of perfect secrecy. Journal of Universal Computer Science. 1996. Vol. 2, N 5. P. 347–379.
7. Yao A.C. Theory and application of trapdoor functions. 23rd Annual Symposium on Foundations of Computer Science. Chicago, 1982. P. 80–91.
8. Blum M., de Santis A., Micali S., Persiano G. Non-interactive zero knowledge. SIAM J. Comput. 1991. Vol. 20, N 6. P. 1084–1118.
9. Bellare M., Rogaway P. Random oracles are practical: A paradigm for designing efficient protocols. CCS’93: 1st ACM Conference on Communications and Computing Security. (3–5 November, 1993, Virginia, Fairfax, USA). 1993. P. 62–73. https://doi.org/10.1145/168588.168596.
10. Morais E., Koens T., van Wijk C. et al. A survey on zero knowledge range proofs and applications. SN Appl. Sci. 2019. Vol. 1, 946. https://doi.org/10.1007/s42452-019-0989-z.
11. Goldreich O., Goldwasser S. On the possibility of basing Cryptography on the assumption that . Cryptology ePrint Archive. Paper 1998/005. 1998. https://eprint.iacr.org/1998/005.
12. Кудін А., Ткач В., Носок С. Проблеми побудови аксіоматики сучасної криптографії: інформаційний, обчислювальний та інформаційно-обчислювальний підходи. Фізико-математичне моделювання та інформаційні технології. 2023. № 36. С. 137–142. https://doi.org/10.15407/10.15407/fmmit2023.36.
13. Goldwasser S. Micali probabilistic encryption. Journal of Computer and System Sciences. 1984. N 28. Р. 270–299.
14. Кудин А.М. Однонаправленные функции с информационно невычислимой лазейкой. Прикладная радиоэлектроника. 2012. Т. 11, № 2. С. 245–249.
15. Maurer U. Abstract models of computation in cryptography. In: Smart N.P. (Eds.). Cryptography and Coding. Cryptography and Coding 2005. Lecture Notes in Computer Science. Berlin; Heidelberg: Springer, 2005. Vol. 3796. https://doi.org/10.1007/11586821_1.
16. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. Москва: Мир, 1979. 536 с.
17. Вербіцький О.В. Вступ до криптології. Львів: ВНТЛ, 1998. 248 c.
18. Brassard G. Cryptology column Quantum cryptography: A bibliography. Sigact News. 1993. Vol. 24, N 3. Р. 16–20.
19. Савчук М.М., Фесенко А.В. Квантові обчислення: огляд та аналіз. Кибернетика и системный анализ. 2019. Т. 55, № 1. С. 14–29.
20. Санюк В.И., Суханов А.Д. Дирак в физике ХХ века. Успехи физических наук. 2003. Т. 173, № 9. С. 965–984.
21. Lomont C. The hidden subgroup problem-review and open problems. arXiv preprint quant-ph/0411037. 2004.
22. Landauer R. Selected topics in signal processing. S. Haykin (Edы.). Englewood Cliffs, N.J.: Prentice-Hall, 1989. P. 18.
23. ITRS-2001 Reports. URL: https://www.researchgate.net/publication/2955547.
24. Toffoli T., Margolus N. Cellular automata machines. MIT Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA, USA. 1987.
25. Fredkin E., Toffoli T. Conservative logic. International Journal of Theoretical Physics. 1982. Vol. 21. P. 219–253. http://dx.doi.org/10.1007/BF01857727.
26. Sasamal T.N. Fault-tolerant and low-power reversible computing architectures for secure cloud datacenters. Authorea Preprints. 2025.
27. Refonaa J., Maheswari M., Poornima D. et al. Edge and fog computing for sustainability. In: Energy Efficient Algorithms and Green Data Centers for Sustainable Computing. IGI Global Scientific Publishing, 2025. P. 79–108. https://doi.org/10.4018/979-8-3373-0766-4.ch004.
28. Mudaliar D.N., Modi N., Dharwa J. A Novel approach to solve network security, cryptography problems using genetic algorithm. International Conference on Computing Science, Communication and Security. Cham: Springer Nature Switzerland, 2024. P. 282–293.
29. Li Y., Sze S.M., Chao T.S. A practical implementation of parallel dynamic load balancing for adaptive computing in VLSI device simulation. Engineering with Computers. 2002. Vol. 18. P. 124–137.
30. Naha R.K. et al. Fog computing: Survey of trends, architectures, requirements, and research directions. IEEE Access. 2018. Vol. 6. P. 47980–48009.
31. Задирака В.К., Кудин А.М. Построение программно-аппаратных комплексов арифметики сверхбольших чисел. Комп’ютерна математика. Оптимізація обчислень. Київ: Ін-т кібернетики ім. В.М. Глушкова, 2001. Т. 1. С. 158–163.
32. Кудін А.М., Ковальчук Л.В., Коваленко Б.А. Теоретичні засади та застосування блокчейн-технологій: імплементація нових протоколів консенсусу та краудсорсінг обчислень. Математичне та комп’ютерне моделювання. 2019. № 19. С. 62–68.
33. Bethany D. Genetic algorithms in cryptography. Thesis. Rochester Institute of Technology. 2004. 87 p.
34. Zadiraka V.K., Kudin A.M., Shvidchenko I.V., Seliukh P.V. Security estimates updating of asymmetric cryptosystems for modern computing. Recent Advances in Information Technology: Proceedings of the 13th Warsztaty Doktoranckie Conference (WD 2016) (June 11–13, 2016, Lublin, Poland), and the 13th International Conference on Measurement and Control in Complex Systems (MCCS 2016) (3–6 Oct., 2016, Vinnytsia, Ukraine). London, UK: Taylor&Francis Group, 2018. P. 1–12.
35. Ершов А.П. Смешанные вычисления: потенциальные применения и проблемы исследования. Методы математической логики в проблемах искусственного интеллекта & систематическое программирование. 1980. С. 26–55.
36. Трауб Д., Васильковский Г., Вожьняковский Х. Информация, неопределенность, сложность. Москва: Мир, 1988. 184 с.