# A Novel Hybrid Elementary Cellular Automata and Its Application in a Stream Cipher
## 4 Stream Cipher Based on HECA-M
### Description of Proposed Stream Cipher
The \(p\)-value of the proposed stream cipher is always above 0.01 in any test. Moreover, in comparison to other lightweight stream ciphers [43] listed in Table 7, the proposed scheme exhibits stronger randomness due to its superior performance in universal tests. Thus, the randomness of the proposed stream is the strongest among these lightweight stream ciphers. ## 2 Berlekamp-Massey synthesis

The linear complexity is an important security property for a stream cipher. The Berlekamp-Massey synthesis [44] is widely used in estimating the linear complexity of a binary keystream generated by a stream cipher. As for a keystream, the ideal linear complexity \(l\) equals \(N/2\). \(N\) represents the length of the keystream. The keystreams generated by the proposed stream ciphers with different HECA-Ms are chosen to be analyzed by the B-M synthesis. Specifically, these HECA-Ms are under varying chaotic rule groups. Thus, there are 27 keystreams. Moreover, the length of them is 2000 bits. The B-M synthesis results of different keystreams are depicted in Figure 7.

In Figure 7, \(X\)-axis and \(Y\)-axis denote the length of the keystream \(N\) and the linear complexity \(l\), respectively. Apparently, the linear complexity of any keystream coincides with the ideal line \(l=N/2\). In conclusion, the proposed stream cipher possesses qualified linear complexity. Furthermore, it can resist linear algebraic attacks such as the B-M synthesis. 3. Linear analysis (distinguishing attack)

The minimal polynomial of the keystream can be acquired by the B-M synthesis. Furthermore, an equation of linear regression is deduced from the minimal polynomial, which can be used for implementing the distinguishing attack. The process is described as follows:

\[ \begin{array}{l}f(x)=1+c_{1}x+c_{2}x^{2}+\ldots+c_{n-1}x^{n-1}+x^{n}\\ \Rightarrow s_{t}=c_{1}s_{t-1}+c_{2}s_{t-2}+\ldots+c_{n-1}s_{t-n+1}+s_{t-n} \end{array} , \tag{8}\]

where \(f(x)\) represents the minimal polynomial of the sequences (\(s_{0}\), \(s_{1}\), \(s_{2}\), \(\ldots\), \(s_{t-n}\), \(s_{t-n+1}\), \(s_{t-2}\), \(s_{t-1}\), \(\ldots\)). Meanwhile, \(f(x)\) is acquired by the B-M synthesis. \(t\) represents the time dimension. The equation of linear regression in Equation (8) is employed to deduce subse \begin{table}
\begin{tabular}{c c c c c c c} \hline \hline
**Test** & **Lizard** & **Fruit** & **Plantlet** & **Sprout** & **Grain V1** & **Espresso** & **Proposed** \\ \hline Frequency & 0.350485 & 0.122325 & 0.924076 & 0.032923 & 0.122325 & 0.304126 & 0.551026 \\ Block frequency & 0.008879 & 0.350485 & 0.637119 & 0.897763 & 0.455937 & 0.739918 & 0.602458 \\ Cumulative sums & 0.350485 & 0.739918 & 0.514124 & 0.401199 & 0.122325 & 0.162606 & 0.232760 \\ Runs & 0.534146 & 0.911413 & 0.181557 & 0.574903 & 0.834308 & 0.834308 & 0.534146 \\ Longest runs & 0.350485 & 0.574903 & 0.739918 & 0.637119 & 0.883171 & 0.739918 & 0.242986 \\ Rank & 0.534146 & 0.213309 & 0.000070 & 0.000233 & 0.011791 & 0.010988 & 0.078086 \\ FFT & 0.991468 & 0.739918 & 0.004301 & 0.171867 & 0.045675 & 0.171867 & 0.468595 \\ Non-overlapping template & 0.550133 & 0.474986 & 0.657933 & 0.236810 & 0.616305 & 0.455937 & 0.637119 \\ Overlapping template & 0.350485 & 0.350485 & 0.851383 & 0.289667 & 0.236810 & 0.108791 & 0.819544 \\ Universal & 0.00621 & 0.000513 & 0.015826 & 0.000079 & 0.007315 & 0.002347 & 0.931952 \\ Approximate entropy & 0.350485 & 0.739918 & 0.191687 & 0.213309 & 0.439621 & 0.426931 & 0.392456 \\ Random excursions * & 0.028181 & 0.179539 & 0.080519 & 0.090936 & 0.012071 & 0.139921 & 0.031064 \\ Random excursions variant * & 0.031894 & 0.016717 & 0.041890 & 0.021505 & 0.077290 & 0.017912 & 0.117948 \\ Serial * & 0.137154 & 0.12911 & 0.262249 & 0.554420 & 0.000474 & 0.171867 & 0.105618 \\ Linear complexity & 0.035174 & 0.031254 & 0.383827 & 0.637119 & 0.040108 & 0.045675 & 0.468595 \\ \hline \hline \end{tabular}

* denotes that there are multiple tests in this sub-test. It means that the \(p\)-value is the minimum in these multiple tests.

\end{table}