ОЦЕНКА ВРЕМЕНИ ВЫПОЛНЕНИЯ ПОИСКА СОСТАВЛЯЮЩИХ КЛЮЧА В АТАКЕ С ИЗВЕСТНЫМ ОТКРЫТЫМ ТЕКСТОМ НА КРИПТОСИСТЕМУ ДОМИНГО-ФЕРРЕРА
Аннотация
Представлено краткое описание полностью гомоморфной криптографической системы Доминго-Феррера, приводится характеристика этапов атаки с известным открытым текстом на данную криптосистему. Анализируется этап поиска составляющих ключа рассматриваемой атаки, для которого описываются существующие методы реализации, среди которых определяется метод, обладающий минимальной вычислительной сложностью. Обоснование вычислительной сложности и временных затрат рассматриваемого метода реализации этапа поиска составляющих ключа формируется на основе теоретических расчётов, а также экспериментальных исследований. Целью исследования является оценка сложности реализации этапа поиска составляющих ключа в атаке с известным открытым текстом на полностью гомоморфную криптографическую систему Доминго-Феррера с помощью метода Гаусса, разработанного для решения систем линейных алгебраических уравнений по модулю простого числа. Основным результатом настоящей работы является оценка вычислительной сложности этапа поиска составляющих ключа в атаке с известным открытым текстом на криптографическую систему Доминго-Феррера, реализованного с использованием метода Гаусса. Оценка сложности выражена в количестве базовых математических операций и подтверждена рядом экспериментальных исследований, что позволяет сделать обоснованные выводы о вычислительной сложности рассматриваемого метода. Проведенное исследование представляет собой значимый вклад в развитие полностью гомоморфной криптосистемы Доминго-Феррера, основанной на задаче факторизации целых чисел. Оно обладает практической значимостью, так как позволяет оценить критичность атаки с известным открытым текстом на данную криптосистему. Полученные результаты могут служить основой для исследователей и криптографов при разработке рекомендаций по выбору параметров криптосистемы Доминго-Феррера для обеспечения необходимого уровня безопасности в различных приложениях.
Список литературы
1. Prudnikova A.A., Sadovnikova T.M. Analiz oblachnykh servisov s tochki zreniya informatsionnoy be-zopasnosti [Analysis of cloud services from the point of view of information security], T-Comm-Telekommunikatsii i Transport [T-Comm-Telecommunications and Transport], 2012, No. 7, pp. 153-156.
2. Babenko L.K., Rusalovskiy I.D. Metod realizatsii gomomorfnogo deleniya [Method for implementing homomorphic division], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2020, No. 4 (214), pp. 212-221. DOI: 10.18522/2311-3103-2020-4-212-221.
3. Gentry C. A fully homomorphic encryption scheme. Stanford university, 2009.
4. Lyubashevsky V., Peikert C., Regev O. On ideal lattices and learning with errors over rings, Advances in Cryptology–EUROCRYPT 2010: 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques, French Riviera, May 30–June 3, 2010. Proceedings 29. Springer Berlin Heidelberg, 2010, pp. 1-23.
5. Babenko L.K. i dr. Polnost'yu gomomorfnoe shifrovanie (obzor) [Fully homomorphic encryption (re-view)], Voprosy zashchity informatsii [Information Security Issues], 2015, No. 3, pp. 3-26.
6. Acar A. et al. A survey on homomorphic encryption schemes: Theory and implementation, ACM Com-puting Surveys (Csur), 2018, Vol. 51, No. 4, pp. 1-35.
7. Armknecht F. et al. On constructing homomorphic encryption schemes from coding theory, IMA Inter-national Conference on Cryptography and Coding. Berlin, Heidelberg: Springer Berlin Heidelberg, 2011, pp. 23-40.
8. Domingo-Ferrer J. A provably secure additive and multiplicative privacy homomorphism, International Conference on Information Security. Berlin, Heidelberg : Springer Berlin Heidelberg, 2002,
pp. 471-483.
9. Zhirov A., Zhirova O., Krendelev S.F. Practical fully homomorphic encryption over polynomial quotient rings, World Congress on Internet Security (WorldCIS-2013). IEEE, 2013, pp. 70-75.
10. Kipnis A., Hibshoosh E. Efficient methods for practical fully homomorphic symmetric-key encrypton, randomization and verification, Cryptology ePrint Archive, 2012.
11. Merkel W. et al. Factorization of numbers with physical systems, Fortschritte der Physik: Progress of Physics, 2006, Vol. 54, No. 8‐10, pp. 856-865.
12. Lenstra A. K. et al. The factorization of the ninth Fermat number, Mathematics of Computation, 1993, Vol. 61, No. 203, pp. 319-349.
13. Cheon J.H., Nam H.S. A cryptanalysis of the original domingo-ferrer's algebraic privacy homomophism, Cryptology EPrint Archive, 2003.
14. Trepacheva A. V. Improved known plaintexts attack on Domingo-Ferrer homomorphic cryptosystem, Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS), 2014,
Vol. 26, No. 5, pp. 83-98.
15. Chernyavskiy A.F., Kozlova E.I., Chernyavskiy Yu.A. Osobennosti strukturno-apparatnogo obespecheni-ya preobrazovaniya informatsii v kriptosistemakh [Features of structural and hardware support for in-formation transformation in cryptosystems], Doklady Belorusskogo gosudarstvennogo universiteta in-formatiki i radioelektroniki [Reports of the Belarusian State University of Informatics and Radioelectron-ics], 2024, Vol. 22, No. 5, pp. 80-88. DOI: 10.35596/1729-7648-2024-22-5-80-88.
16. Sokolova E.V. Obobshchenie pryamykh i iteratsionnykh metodov resheniya sistem lineynykh alge-braicheskikh uravneniy [Generalization of direct and iterative methods for solving systems of linear al-gebraic equations], Matematika i IT - vmeste v tsifrovoe budushchee: Sb. trudov Molodezhnoy shkoly, Nizhniy Novgorod, 25–29 aprelya 2022 goda [Mathematics and IT - together into the digital future: Col-lection of works of the Youth School, Nizhny Novgorod, April 25-29, 2022]. Nizhniy Novgorod: Natsional'nyy issledovatel'skiy Nizhegorodskiy gosudarstvennyy universitet im. N.I. Lobachevskogo, 2022, pp. 111-120.
17. Efanov V.V., Zakota A.A., Gun'kina A.S. Metodika otsenki tochnosti opredeleniya parametrov dvizheniya vozdushnoy tseli v usloviyakh skrytnogo nablyudeniya za ney na osnove primeneniya metoda iteratsii [Methodology for assessing the accuracy of determining the motion parameters of an air target under covert surveillance based on the iteration method], Tr. MAI [Proceedings of MAI], 2021, No. 117. DOI: 10.34759/trd-2021-117-18.
18. Sechenov P.A. Sravnenie bystrodeystviya chislennykh metodov Gaussa i LUP-razlozheniya v zadache nakhozhdeniya ravnovesnogo khimicheskogo sostava [Comparison of the performance of numerical Gaussian methods and LUP decomposition in the problem of finding the equilibrium chemical composi-tion], Vestnik Voronezhskogo gosudarstvennogo tekhnicheskogo universiteta [Bulletin of the Voronezh State Technical University], 2023, Vol. 19, No. 2, pp. 79-85. DOI: 10.36622/VSTU.2023.19.2.012.
19. Iliev A., Kyurkchiev N. The faster extended Euclidean algorithm, Collection of scientific works from con-ference, 2018, pp. 21-26.
20. Abramov S.A. Matematicheskie postroeniya i programmirovanie [Mathematical constructions and pro-gramming], 1978.
21. Babenko L.K., Starodubtsev V.S. Otsenka vremeni vypolneniya operatsiy shifrovaniya, rasshifrovaniya, gomomorfnykh vychisleniy s ispol'zovaniem kriptosistemy Domingo-Ferrera [Estimation of execution time of encryption, decryption, homomorphic computations using the Domingo-Ferrer cryptosystem], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2024, No. 5 (241), pp. 6-15. – DOI: 10.18522/2311-3103-2024-5-6-15.
22. Babenko L.K., Starodubtsev V.S. Osobennosti realizatsii sistemy kriptoanaliza gomomorfnykh shifrov, osnovannykh na zadache faktorizatsii chisel [Features of the implementation of the cryptanalysis system of homomorphic ciphers based on the problem of number factorization], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2024, No. 3 (239), pp. 55-64. DOI: 10.18522/2311-3103-2024-3-55-64.
23. Babenko L.K., Starodubtsev V.S. Osobennosti realizatsii sistem kriptoanaliza gomomorfnykh shifrov, osnovannykh na zadache faktorizatsii chisel, na primere kriptosistemy MORE [Features of the imple-mentation of cryptanalysis systems of homomorphic ciphers based on the problem of number factoriza-tion, using the example of the MORE cryptosystem], Voprosy kiberbezopasnosti [Cybersecurity Issues], 2024, No. 3 (61), pp. 141-145. DOI: 10.21681/2311-3456-2024-3-141-145.
