论文标题
在正交蜂窝自动机产生的S框的线性组件空间上
On the Linear Components Space of S-boxes Generated by Orthogonal Cellular Automata
论文作者
论文摘要
我们研究了由正交细胞自动机（OCA）对定义的S盒，这是因为这种CA始终定义了Bioxtive vectorial Boolean函数的启发，因此对于块密码设计而言可能很有趣。特别是，我们对所有非线性OCA对直径$ d = 4 $和$ d = 5 $进行了详尽的搜索，该$ 6 \ times $ 6 \ times 6 $和$ 8 \ times 8 $。令人惊讶的是，所有这些S框都是线性的，因此它们对于块密码中的混淆层的设计并不有用。但是，对这些S盒的仔细检查揭示了一个非常有趣的结构。确实，我们指出，我们详尽搜索发现的基于OCA的S-box的线性组件空间本身就是线性CA的内核，或者等效地，\ emph {polyenmial codes}。我们最终对在详尽搜索中获得的S框的多项式代码进行了分类，并观察到，在大多数情况下，它们实际上与带有发电机多项式$ x^{b}+1 $的循环代码对应，其中$ b = d-1 $。尽管这些发现排除了使用OCA在块密码中设计良好的S盒的可能性，但是它们仍然为非线性OCA对的理论表征提供了一些有趣的见解，这通常是一个悬而未决的问题。
We investigate S-boxes defined by pairs of Orthogonal Cellular Automata (OCA), motivated by the fact that such CA always define bijective vectorial Boolean functions, and could thus be interesting for the design of block ciphers. In particular, we perform an exhaustive search of all nonlinear OCA pairs of diameter $d=4$ and $d=5$, which generate S-boxes of size $6\times 6$ and $8\times 8$, respectively. Surprisingly, all these S-boxes turn out to be linear, and thus they are not useful for the design of confusion layers in block ciphers. However, a closer inspection of these S-boxes reveals a very interesting structure. Indeed, we remark that the linear components space of the OCA-based S-boxes found by our exhaustive search are themselves the kernels of linear CA, or, equivalently, \emph{polynomial codes}. We finally classify the polynomial codes of the S-boxes obtained in our exhaustive search and observe that, in most cases, they actually correspond to the cyclic code with generator polynomial $X^{b}+1$, where $b=d-1$. Although these findings rule out the possibility of using OCA to design good S-boxes in block ciphers, they give nonetheless some interesting insights for a theoretical characterization of nonlinear OCA pairs, which is still an open question in general.
