RUDN Journal of Engineering ResearchRUDN Journal of Engineering Research2312-81432312-8151Peoples’ Friendship University of Russia named after Patrice Lumumba (RUDN University)2725210.22363/2312-8143-2021-22-1-7-15Research ArticleThe reversibility of one-dimensional cellular automataZhukovAlexey E.<p>Associate Professor of the Department of Information Security, BMSTU, Director of the «RusCrypto» Association, Ph.D. (Math.)</p>aez_iu8@rambler.ruhttps://orcid.org/0000-0002-1663-7773Bauman Moscow State Technical University (National Research University of Technology)«RusCrypto» Association2708202122171527082021Copyright © 2021, Zhukov A.E.2021<p style="text-align: justify;">Recently the reversible cellular automata are increasingly used to build high-performance cryptographic algorithms. The paper establishes a connection between the reversibility of homogeneous one-dimensional binary cellular automata of a finite size and the properties of a structure called binary filter with input memory and such finite automata properties as the prohibitions in automata output and loss of information. We show that finding the preimage for an arbitrary configuration of a one-dimensional cellular automaton of length L with a local transition function f is associated with reversibility of a binary filter with input memory. As a fact, the nonlinear filter with an input memory corresponding to our cellular automaton does not depend on the number of memory cells of the cellular automaton. The results obtained make it possible to reduce the complexity of solving massive enumeration problems related to the issues of reversibility of cellular automata. All the results obtained can be transferred to cellular automata with non-binary cell filling and to cellular automata of dimension greater than 1.</p>reversible cellular automatonbinary filter with input memoryan automaton with prohibitionsan automaton without prohibitionsinformation lossless automatoninformation lossy automatona graph of automaton prohibitionsобратимость клеточного автоматанелинейный фильтр с входной памятьюавтомат с запретамиавтомат без запретовавтомат с потерей информацииавтомат без потери информацииграф запретов[Zhukov A. Cellular automata in cryptography. Part 1. Voprosy kiberbezopasnosti [Cybersecurity issues]. 2017;3(21):70—76. (In Russ.) https://doi.org/10.21581/2311-3456-2017-3-70-76][Zhukov A. Cellular automata in cryptography. Part 2. Voprosy kiberbezopasnosti [Cybersecurity issues]. 2017;4(22):47—66. (In Russ.) https://doi.org/10.21681/2311-3456-2017-4-47-66][Lai X, Massey JL. Some connections between scramblers and invertible automata. In: Proc. 1988 Beijing Int. Workshop on Info. Theory, Beijing. China, July 4-7;1988:DI-5.1 — DI-5.5.][Preparata FP. Convolutional transformations of binary sequences: Boolean functions and their resynchronizing properties. IEEE Trans. Electron. Comput. 1966;15(6):898—909.][Sumarokov SN. Zaprety dvoichnyh funkcij i obratimost’ dlya odnogo klassa kodiruyushchih ustrojstv [Prohibitions of binary functions and reversibility for one class of coding devices]. Obozrenie prikladnoj i promyshlennoj matematiki, ser. diskretn. matem. [Obozrenie prikladnoy i promyshlennoy matematiki]. 1994;1(1):33—55.][Babash AV. Zaprety avtomatov i dvoichnyh funkcij [Prohibitions of automata and binary functions]. Trudy po diskretnoj matematike [Proceedings of Discrete] Mathematics. 2006;9:7—20. (In Russ.)][Olson RR. On the invertibility of finite state machines. Ph.D. diss. Notre Dame, Indiana, USA: Department of Electrical Engineering, University of Notre Dame; 1970.][Huffman DA. Canonical forms for information loss less finite state logical machines. IRE Trans. Circuit Theory. 1959;6(spec. suppl.):41—59.][Kohavi Z, Niraj K. Jha. Switching and Finite Automata Theory. Cambridge, UK: Cambridge University Press; 2009. https://doi.org/10.1017/CBO9780511816239]