ESTIMATION OF THE SEARCH TIME FOR KEY COMPONENTS IN A KNOWN PLAINTEXT ATTACK ON THE DOMINGO-FERRER CRYPTOSYSTEM
Abstract
This paper provides a brief description of the fully homomorphic Domingo-Ferrer cryptographic system and describes the stages of an attack with a known plaintext on this cryptosystem. The stage of searching for the key components of the attack in question is analyzed, for which existing implementation methods are described, among which the method with minimal computational complexity is determined. The rationale for the computational complexity and time costs of the considered method for implementing the key component search stage is based on theoretical calculations, as well as experimental studies. The aim of the study is to evaluate the complexity of implementing the stage of searching for key components in an attack with a known plaintext on a fully homomorphic Domingo-Ferrer cryptographic system using the Gauss method, developed for solving systems of linear algebraic equations modulo a prime number. The main result of this work is an assessment of the computational complexity of the key component search stage in a known plaintext attack on the Domingo-Ferrer cryptographic system, implemented using the Gauss method. The complexity estimate is expressed in the number of basic mathematical operations and is confirmed by a number of experimental studies, which allows us to draw reasonable conclusions about the computational complexity of the method under consideration. The conducted research represents a significant contribution to the development of a fully homomorphic Domingo-Ferrer cryptosystem based on the integer factorization problem. It has practical significance, as it allows us to assess the criticality of an attack with a known plaintext on a given cryptosystem. The results obtained can serve as a basis for researchers and cryptographers to develop recommendations for choosing the parameters of the Domingo-Ferrer cryptosystem to ensure the necessary level of security in various applications.
References
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.
