1. Complete title: An Evolutionary View on Reversible Shift-Invariant Transformations --------------------- 2. Authors' names, addresses, e-mails and phone numbers: Luca Mariot Cyber Security Research Group, Delft University of Technology, Mekelweg 2, Delft, The Netherlands l.mariot@tudelft.nl +31 623 952 460 Stjepan Picek Cyber Security Research Group, Delft University of Technology, Mekelweg 2, Delft, The Netherlands s.picek@tudelft.nl +385 9822 6407 Domagoj Jakobovic Dept. of Electronics, Microelectronics, Computer and Intelligent Systems Faculty of Electrical Engineering and Computing, Unska 3, 10000 Zagreb, Croatia domagoj.jakobovic@fer.hr +385 1612 9967 Alberto Leporati Department of Informatics, Systems and Communications, University of Milano-Bicocca, Viale Sarca 336/14, 20126 Milano, Italy alberto.leporati@unimib.it +39 02 6448 7877 --------------------- 3. Corresponding author Luca Mariot --------------------- 4. Abstract We consider the problem of evolving a particular kind of shift-invariant transformation -- namely, Reversible Cellular Automata (RCA) defined by conserved landscape rules -- using GA and GP. To this end, we employ three different optimization strategies: a single-objective approach carried out with GA and GP where only the reversibility constraint of marker CA is considered, a multi-objective approach based on GP where both reversibility and the Hamming weight are taken into account, and a lexicographic approach where GP first optimizes only the reversibility property until a conserved landscape rule is obtained, and then maximizes the Hamming weight while retaining reversibility. The results are discussed in the context of three different research questions stemming from exhaustive search experiments on conserved landscape CA, which concern (1) the difficulty of the associated optimization problem for GA and GP, (2) the utility of conserved landscape CA in the domain of cryptography and reversible computing, and (3) the relationship between the reversibility property and the Hamming weight. --------------------- 5. Relevant criteria B, D, F --------------------- 6. Criteria statement The results presented in our paper show that GA and GP can evolve reversible cellular automata (RCA) of the conserved landscape (CL) type for any considered size of the local rules. Before our work, only a few examples of reversible CL rules of diameter at most four have been exhibited in the existing literature, all of which were found by exhaustive search [1,2]. On the contrary, in our paper, we found that GA and GP could reliably generate, with full success rate, reversible CL rules up to diameter 13. Moreover, the analysis performed on the number of fitness evaluations required to find an optimal solution suggested that both methods (especially GP) should be able to find reversible rules of greater sizes. We thus think that our work fully qualifies for criteria B and F, since it represents a significant improvement over state of the art related to the search of this particular type of reversible CA. Further, the fact that we used GP to optimize both the reversibility of conserved landscape rules and their Hamming weight using a multi-objective approach allowed us to observe a clear relationship between the two properties, which in turn led us to conclude that these rules are not suitable for cryptographic purposes. This result has an independent interest independently of the fact that it was discovered through evolutionary algorithms. Moreover, it could trigger further theoretical research on the subject, i.e., mathematically proving the relationship between reversibility and the Hamming weight found by GP. Additionally, the paper received very favorable reviews, and it was selected as a candidate for the best paper award at EuroGP 2020, where it has been published. Hence, for the above reason, we think that our work also qualifies for criterion D. --------------------- 7. Full citation Mariot L., Picek S., Jakobovic D., Leporati A. (2020) An Evolutionary View on Reversible Shift-Invariant Transformations. In: Hu T., Lourenço N., Medvet E., Divina F. (eds) Genetic Programming. EuroGP 2020. Lecture Notes in Computer Science, vol 12101. Springer, Cham @InProceedings{mpjl-eurogp-2020, author="Mariot, Luca and Picek, Stjepan and Jakobovic, Domagoj and Leporati, Alberto", editor="Hu, Ting and Louren{\c{c}}o, Nuno and Medvet, Eric and Divina, Federico", title="An Evolutionary View on Reversible Shift-Invariant Transformations", booktitle="Genetic Programming", year="2020", publisher="Springer International Publishing", address="Cham", pages="118--134", isbn="978-3-030-44094-7" } --------------------- 8. Prize statement Any prize money, if any, is to be divided equally among the co-authors. --------------------- 9. Best statement Reversible cellular automata have several applications in building reversible computing circuits and cryptographic primitives. Nevertheless, only a few classes of them are known in the literature, and their synthesis typically boils down to some ad-hoc constructions found either by exhaustive search or algebraic methods. With our paper, we showed that GA and GP can be used to reliably generate many different instances of a specific class of reversible CA, but also that they can be used to investigate such CA from a theoretical point of view. The relationship between the reversibility and the Hamming weight of a conserved landscape rule found by our multi-objective GP was not known before in the existing literature. In our opinion, this result represents the most remarkable outcome of our experiments, since it shows that evolutionary algorithms can discover interesting mathematical facts. Further, this discovery made by GP also allowed us to draw a practical conclusion about the usefulness of such reversible CA in the cryptographic context, in particular in a negative sense. --------------------- 10. Methods used GA (Genetic Algorithms), GP (Genetic Programming) --------------------- 11. Publication date 9 April 2020 (First Online) --------------------- References [1] Patt, Y.: Injections of Neighborhood Size Three and Four on the Set of Configurations from the Infinite One-Dimensional Tessellation Automata of Two-State Cells. Technical report, ARMY ELECTRONICS COMMAND FORT MONMOUTH NJ (1972) [2] Toffoli, T., Margolus, N.H.: Invertible cellular automata: a review. Physica D: Nonlinear Phenomena 45(1-3): 229--253 (1990)