%0 Generic %1 mariot2023classification %A Mariot, Luca %A Manzoni, Luca %D 2023 %K boolean_functions cellular_automata cryptography cyclic_codes orthogonal_latin_squares polynomial_codes s-boxes security %T A classification of S-boxes generated by Orthogonal Cellular Automata %U http://arxiv.org/abs/2303.05228 %X Most of the approaches published in the literature to construct S-boxes via Cellular Automata (CA) work by either iterating a finite CA for several time steps, or by a one-shot application of the global rule. The main characteristic that brings together these works is that they employ a single CA rule to define the vectorial Boolean function of the S-box. In this work, we explore a different direction for the design of S-boxes that leverages on Orthogonal CA (OCA), i.e. pairs of CA rules giving rise to orthogonal Latin squares. The motivation stands on the facts that an OCA pair already defines a bijective transformation, and moreover the orthogonality property of the resulting Latin squares ensures a minimum amount of diffusion. We exhaustively enumerate all S-boxes generated by OCA pairs of diameter $4 d 6$, and measure their nonlinearity. Interestingly, we observe that for $d=4$ and $d=5$ all S-boxes are linear, despite the underlying CA local rules being nonlinear. The smallest nonlinear S-boxes emerges for $d=6$, but their nonlinearity is still too low to be used in practice. Nonetheless, we unearth an interesting structure of linear OCA S-boxes, proving that their Linear Components Space (LCS) is itself the image of a linear CA, or equivalently a polynomial code. We finally classify all linear OCA S-boxes in terms of their generator polynomials.

@misc{mariot2023classification, abstract = {Most of the approaches published in the literature to construct S-boxes via Cellular Automata (CA) work by either iterating a finite CA for several time steps, or by a one-shot application of the global rule. The main characteristic that brings together these works is that they employ a single CA rule to define the vectorial Boolean function of the S-box. In this work, we explore a different direction for the design of S-boxes that leverages on Orthogonal CA (OCA), i.e. pairs of CA rules giving rise to orthogonal Latin squares. The motivation stands on the facts that an OCA pair already defines a bijective transformation, and moreover the orthogonality property of the resulting Latin squares ensures a minimum amount of diffusion. We exhaustively enumerate all S-boxes generated by OCA pairs of diameter $4 \le d \le 6$, and measure their nonlinearity. Interestingly, we observe that for $d=4$ and $d=5$ all S-boxes are linear, despite the underlying CA local rules being nonlinear. The smallest nonlinear S-boxes emerges for $d=6$, but their nonlinearity is still too low to be used in practice. Nonetheless, we unearth an interesting structure of linear OCA S-boxes, proving that their Linear Components Space (LCS) is itself the image of a linear CA, or equivalently a polynomial code. We finally classify all linear OCA S-boxes in terms of their generator polynomials.}, added-at = {2023-09-29T15:15:12.000+0200}, author = {Mariot, Luca and Manzoni, Luca}, biburl = {https://www.bibsonomy.org/bibtex/2734671d64425d33353f1025c4cb2f131/tabularii}, description = {[2303.05228] A classification of S-boxes generated by Orthogonal Cellular Automata}, interhash = {aff44a7ac57de7932f555629e8698a77}, intrahash = {734671d64425d33353f1025c4cb2f131}, keywords = {boolean_functions cellular_automata cryptography cyclic_codes orthogonal_latin_squares polynomial_codes s-boxes security}, note = {cite arxiv:2303.05228Comment: 22 pages. Extended version of "On the Linear Components Space of S-boxes Generated by Orthogonal Cellular Automata" arXiv:2203.14365v, presented at ACRI 2022. Currently under submission at Natural Computing}, timestamp = {2023-09-29T15:15:12.000+0200}, title = {A classification of S-boxes generated by Orthogonal Cellular Automata}, url = {http://arxiv.org/abs/2303.05228}, year = 2023 }