1. Paper title: Evolving S-boxes Based on Cellular Automata with Genetic Programming Note: a similar (extended) evolutionary technique where we also optimize not only cryptographic properties but also implementation properties like area and power are accepted as the paper "Design of S-boxes Defined with Cellular Automata Rules" that was published at Malicious Software and Hardware in Internet of Things 2017 workshop, Siena, Italy (post-proceedings format). ------------------------- 2. Author contact details: Stjepan Picek, Afdeling ESAT - COSIC, Kasteelpark Arenberg 10 - bus 2452, 3001 Heverlee, Belgium, stjepan@computer.org, 0038598226407 Luca Mariot, DISCo, Universita degli Studi di Milano-Bicocca, Viale Sarca 336/14, 20126 Milano, Italy, luca.mariot@disco.unimib.it 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, 0038516129967 Alberto Leporati, DISCo, Universita degli Studi di Milano-Bicocca, Viale Sarca 336/14, 20126 Milano, Italy, alberto.leporati@unimib.it ------------------------- 3. Corresponding author: Stjepan Picek ------------------------- 4. Paper abstract: The design of cryptographically strong Substitution Boxes (S-boxes) is an interesting problem from both a cryptographic perspective as well as the combinatorial optimization one. Here we introduce the concept of evolving cellular automata rules that can be then translated into S-boxes. With it, we are able to find optimal S-boxes for sizes from 4x4 up to 7x7. As far as we know, this is the first time a heuristic approach is able to find optimal S-boxes for sizes larger than 4. ------------------------- 5. Relevant criteria: B, D, E, G ------------------------- 6. Statement: In our paper, we have shown that genetic programming is able to evolve cellular automata (CA) rules that can be used to construct cryptographically optimal S-boxes of various sizes. This approach easily outperforms other methods like random search, simulated annealing, and GA. We use our approach to find cryptographically optimal S-boxes of sizes 4x4 up to 7x7. We note that the mentioned S-box sizes are interesting not only from the optimization perspective but also in realistic scenarios - as an example, 5x5 S-box is used in the Keccak cipher that is now the SHA3 standard. Up to now, heuristics were able to reach optimal solutions only for size 4x4 which represents the search spaces size of 2^64. Here, for 7x7 size, we work with the search space size of 2^896. Besides the novel combination of genetic programming and cellular automata, we use an efficient mapping from genotype to phenotype, using the tree representation of the CA local rule that builds the S-box. This approach enables the GP to find significantly better solutions in this search space. When compared with other heuristics techniques, our approach is extremely lightweight and able to reach optimal solutions in matter of minutes. Furthermore, differing from algebraic constructions that always result in the same S-box, our approach is able to find large number of optimal S-boxes. ------------------------- 7. Citation: The paper is to be published at GECCO 2017 so there is no full citation of the paper at the moment. ------------------------- 8. Any prize money, if any, is to be divided equally among the co-authors. ------------------------- 9. "Best" statement: S-boxes play extremely important role in cryptography since they are the most used nonlinear element to build ciphers and without it, ciphers would be trivial to break. Up to now, no technique except algebraic construction was able to construct optimal S-boxes for sizes larger than 4x4. Our approach is easy to use and offers excellent results for larger sizes - up to 7x7. Consequently, we are able to move the bar and show not only to the evolutionary community but also to the cryptographic community how evolutionary algorithms can be used to evolve complex cryptographic primitives. Our contribution was accepted by an prominent conference in the field of natural computing - GECCO 2017. ------------------------- 10. Method used: Genetic Programming