DOI
10.34229/KCA2522-9664.25.6.1
UDC 621.391:519.2:519.7
V.K. Zadiraka
V.M. Glushkov Institute of Cybernetics, National Academy of Sciences of Ukraine,
Kyiv, Ukraine, 
zvk140@ukr.net
A.M. Kudin
Institute of Physics and Technology of National Technical University of Ukraine “Igor Sikorsky Kyiv Polytechnic Institute,” Kyiv, Ukraine;
National Bank of Ukraine, Kyiv, Ukraine, pplayshner@gmail.com
I.A. Kudin
Institute of Physics and Technology of National Technical University of Ukraine “Igor Sikorsky Kyiv Polytechnic Institute,”
Kyiv, Ukraine,
mmzi.cat@gmail.com
I.V. Shvidchenko
V.M. Glushkov Institute of Cybernetics, National Academy of Sciences of Ukraine,
Kyiv, Ukraine, inetsheva@gmail.com
BEYOND POST-QUANTUM CRYPTOGRAPHY: CRYPTOSYSTEMS SECURE
IN CERTAIN MODELS OF COMPUTATION
Abstract. The problem of assessing the stability of cryptographic transformations in modern cryptography, which is usually implemented using an axiomatic or proof-based approach, is considered. Since the quantum computing model changes the complexity of certain computational problems (for example, integer factorization problems), cryptography studies classes of algorithms that will remain stable in the quantum computing model—the so-called “post-quantum cryptographic algorithms.” A generalization of this problem statement is the study of computational models containing cryptanalysis algorithms, the best of which has exponential complexity or complexity close to it. The generalization of the problem of the existence of cryptosystems that are secure in the post-quantum world, namely, cryptosystems that are secure in certain computational models, as well as the possibility of practical application of such models, is considered. The main result of the work is the creation of a universal computational model that generalizes a whole class of promising computational models, including quantum ones, and the construction of a cryptosystem that is stable within such a computational model.
Keywords: post-quantum cryptography, relativized cryptography, computing models, genetic algorithms, reversible computing, blockchain.
full text
REFERENCES
- 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. К. Shannon. Communication Theory in Secret Systems. In: K. Shannon. Works on Information Theory and Cybernetics. Moscow: IL, 1963. P.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. Kudin A., Tkach V., Nosok S. Problems of constructing axiomatics of modern cryptography: informational, computational and informational-computational approaches. Physical and mathematical modeling and information technologies. 2023. No. 36. P. 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. Kudin A.M. One-way functions with an information-noncomputable loophole. Applied Radio Electronics. 2012. Vol. 11, No. 2. P. 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. Aho A., Hopcroft J., Ullman J. Construction and analysis of computational algorithms [Russian translation]. Moscow: Mir, 1979. 536 p.
- 17. Verbitsky O.V. Introduction to Cryptology [in Ukrainian]. Lviv: VNTL, 1998. 248 p.
- 18. Brassard G. Cryptology column Quantum cryptography: A bibliography. Sigact News. 1993. Vol. 24, N 3. Р. 16–20.
- 19. Savchuk M.M., Fesenko A.V. Quantum computing: review and analysis. Kibernetika i sistemnyj analiz. 2019. Vol. 55, No. 1. P.14–29.
- 20. Sanyuk V.I., Sukhanov A.D. Dirac in twentieth-century physics. Uspekhi fizicheskikh nauk. 2003. Т. 173, № 9. P. 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. Zadiraka V.K., Kudin A.M. Construction of software and hardware complexes for the arithmetic of very large numbers. Computer mathematics. Optimization of calculations [in Russian]. Kiev: Institute of Cybernetics im. V.M. Glushkova, 2001. Vol. 1. P. 158–163.
- 32. Kudin A.M., Kovalchuk L.V., Kovalenko B.A. Theoretical foundations and applications of blockchain technologies: implementation of new consensus protocols and crowdsourcing of calculations. Matematychne ta komp'yuterne modelyuvannya. 2019. No. 19. P. 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. Ershov A.P. Mixed computations: potential applications and research problems. Methods of mathematical logic in problems of artificial intelligence & systematic programming. 1980. P. 26–55.
- 36.Traub D., Vasilkovsky G., Vozhnyakovsky H. Information, Uncertainty, Complexity [Russian translation]. Moscow: Mir, 1988. 184 p.
