АЛГОРИТМЫ СНИЖЕНИЯ ВРЕМЕННЫХ ЗАТРАТ НА ВЫПОЛНЕНИЕ ОПЕРАЦИЙ КРИПТОСИСТЕМЫ ДОМИНГО-ФЕРРЕРА
Аннотация
Проведён анализ литературы по тематике полностью гомоморфного шифрования. Представлено краткое описание полностью гомоморфной криптографической системы Доминго-Феррера, основанной на задаче факторизации чисел, приведены временные характеристики этапов атаки с известным открытым текстом на данную криптосистему. Проанализированы временные характеристики операций криптосистемы, описаны методы и средства их практической реализации. Предложены новые алгоритмы реализации операций криптосистемы Доминго-Феррера, позволяющие снизить время их выполнения. Обоснование оценок временных затрат операций криптосистемы формируется на основе теоретических расчётов, а также результатов экспериментальных исследований. Целью исследования является снижение времени выполнения операций криптосистемы Доминго-Феррера посредством разработки алгоритмов их модификации, учитывающих особенности практической реализации. Основным результатом настоящей работы является снижение времени выполнения следующих операций криптосистемы Доминго-Феррера: шифрования – на 10-15%, расшифрования – в 2 раза, гомоморфного умножения – в 64 раза для цепочки из 200 умножений при использовании степени полиномов представления шифртекста d=100 и незначительном увеличении временных затрат на генерацию ключа. Проведённое исследование представляет собой значимый вклад в развитие полностью гомоморфной криптосистемы Доминго-Феррера, основанной на задаче факторизации целых чисел. Настоящая работа обладает практической значимостью, поскольку позволяет значительно повысить производительность гомоморфных вычислений данной криптосистемы. Полученные результаты могут стать основой для разработки эффективных (с точки зрения вычислительных затрат и обеспечиваемого уровня безопасности) программно-аппаратных комплексов облачных вычислений, использующих полностью гомоморфную криптосистему Доминго-Феррера для обеспечения конфиденциальности обрабатываемой информации.
Список литературы
1. Munjal K., Bhatia R. A systematic review of homomorphic encryption and its contributions in healthcare industry, Complex & Intelligent Systems, 2023, Vol. 9, No. 4, pp. 3759-3786. DOI: 10.1007/s40747-022-00756-z.
2. Yang W. et al. A review of homomorphic encryption for privacy-preserving biometrics, Sensors, 2023, Vol. 23, No. 7, pp. 3566. DOI: 10.3390/s23073566.
3. Sadeeq M.M. et al. IoT and Cloud computing issues, challenges and opportunities: A review, Qubahan Academic Journal, 2021, Vol. 1, No. 2, pp. 1-7. DOI: 10.48161/qaj.v1n2a36.
4. Marcolla C. et al. Survey on fully homomorphic encryption, theory, and applications, Proceedings of the IEEE, 2022, Vol. 110, No. 10, pp. 1572-1609. DOI: 10.36227/techrxiv.19315202.v5.
5. Rivest R.L. et al. On data banks and privacy homomorphisms, Foundations of secure computation, 1978, Vol. 4, No. 11, pp. 169-180.
6. Rivest R.L., Shamir A., Adleman L. A method for obtaining digital signatures and public-key cryptosys-tems, Communications of the ACM, 1978, Vol. 21, No. 2, pp. 120-126.
7. Gentry C. A fully homomorphic encryption scheme. – Stanford university, 2009.
8. Al Badawi A. et al. Openfhe: Open-source fully homomorphic encryption library, Proceedings of the 10th workshop on encrypted computing & applied homomorphic cryptography, 2022, pp. 53-63. DOI: 10.1145/3560827.3563379.
9. Xie Q. et al. Efficiency optimization techniques in privacy-preserving federated learning with homomor-phic encryption: A brief survey, IEEE Internet of Things Journal, 2024, Vol. 11, No. 14,
pp. 24569-24580. DOI: 10.1109/JIOT.2024.3382875.
10. Cheon J.H. et al. Homomorphic encryption for arithmetic of approximate numbers, International confer-ence on the theory and application of cryptology and information security. Cham: Springer International Publishing, 2017, pp. 409-437. DOI: 10.1007/978-3-319-70694-8_15.
11. Chillotti I., Gama N., Georgieva M., and Izabachène M. TFHE: Fast fully homomorphic encryption over the torus, J. Cryptol, 2019, Vol. 33, No. 1, pp. 1-58. DOI: 10.1007/s00145-019-09319-x.
12. El Mestari S.Z., Lenzini G., Demirci H. Preserving data privacy in machine learning systems, Comput-ers & Security, 2024, Vol. 137, pp. 103605. DOI: 10.1016/j.cose.2023.103605.
13. Doan T.V.T. et al. A survey on implementations of homomorphic encryption schemes: DT Van Thao et al., The Journal of Supercomputing, 2023, Vol. 79, No. 13, pp. 15098-15139. DOI: 10.1007/s11227-023-05233-z.
14. 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. DOI: 10.1007/3-540-45811-5_37.
15. Wagner D. Cryptanalysis of an algebraic privacy homomorphism, Information Security: 6th Interna-tional Conference, ISC 2003, Bristol, UK, October 1-3, 2003. Proceedings 6. Springer Berlin Heidel-berg, 2003, pp. 234-239. DOI: 10.1007/10958513_18.
16. Babenko L.K., Starodubtsev V.S., El'chaninova N.B. Otsenka vremeni vypolneniya poiska sostavlyay-ushchikh klyucha v atake s izvestnym otkrytym tekstom na kriptosistemu Domingo-Ferrera [Estimation of the search time for key components in a known plaintext attack on the Domingo-Ferrer cryptosystem], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2025, No. 3 (245), pp. 110-118. DOI: 10.18522/2311-3103-2025-3-110-118.
17. Babenko L.K., Starodubtsev V.S. Otsenka vremeni vypolneniya ataki s izvestnym otkrytym tekstom na kriptosistemu Domingo-Ferrera [Estimating the execution time of a known plaintext attack on the Do-mingo-Ferrer cryptosystem], Voprosy kiberbezopasnosti [Cybersecurity Issues], 2026, No. 1 (71), pp. 139-147. DOI: 10.21681/2311-3456-2026-1-139-147.
18. Babenko L.K., Starodubtsev V.S. Otsenka vremeni vypolneniya operatsiy shifrovaniya, rasshifrovaniya, gomomorfnykh vychisleniy s ispol'zovaniem kriptosistemy Domingo-Ferrera [Estimation of the execu-tion time of encryption, decryption, homomorphic calculations 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.
19. Alhassan E.A. et al. On some algebraic properties of the Chinese remainder theorem with applications to real life, Journal of Applied Mathematics and Computation, 2021, Vol. 5, No. 3. DOI: 10.26855/jamc.2021.09.008.
20. 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 the cryptanalysis systems of homomorphic ciphers based on the problem of factorization of numbers, using the example of the cryptosystem MORE], Voprosy kiberbezopasnosti [Cybersecurity Is-sues], 2024, No. 3 (61), pp. 141-145. DOI: 10.21681/2311-3456-2024-3-141-145.
21. Rajaby E., Sayedi S.M. A structured review of sparse fast Fourier transform algorithms, Digital Signal Processing, 2022, Vol. 123, pp. 103403. DOI: 10.1016/j.dsp.2022.103403.
22. Pornin T. Efficient and complete formulas for binary curves, Cryptology ePrint Archive, 2022.
23. Gao X. et al. A fast spectral sum-of-Gaussians method for electrostatic summation in quasi-2D systems, Numerische Mathematik, 2026, Vol. 158, No. 2, pp. 533-585. DOI: 10.48550/arXiv.2412.04595.
24. Mateer T. Fast Fourier algorithms with applications: Ph. D. Thesis. Clemson University, 2008.
