# Bit Independence Criterion Extended to Stream Ciphers
## 3 BIC Algorithm in Stream Ciphers
### Building the SAC Matrix  
_First difference._ When evaluating the BIC in S-boxes, it is possible to go through the entire space of \(l=2^{n}\) inputs since \(n\) usually takes small values; however, this is impractical in stream ciphers where the dimension of the input space can be \(2^{128}\) or greater. To solve this problem, it is proposed to use the same approach applied in the randomness assessment to the outputs of pseudo-random generators through statistical tests [2]. This approach consists of generating a sample of \(l\) inputs with \(l\ll 2^{n}\), and to determine the strength of the cipher from the results obtained from this sample.  
The \(l\) inputs are chosen randomly in the space of \(2^{n}\) possible inputs. This is the main difference; while the BIC test works over all of the input space with S-boxes, the stream cipher works with a randomly selected subset of the sample space.  
Test of Independence between Two Avalanche Variables \(v_{\cdot j}^{i}\) and \(v_{\cdot k}^{i}\)  
_Second difference._ In [13], [PERSON]'s correlation coefficient \(\rho\) was used to measure the degree of independence between the pairs of avalanche variables. The use of such a coefficient in [13; 29] has two main disadvantages: the first one is that it only detects linear correlations, and the second one is that the critical region for the rejection of the null hypothesis is not explicitly defined, i.e., a threshold is not defined below which \(BIC_{Pearson}(f)\ \approx 0\) is decided. Thus, it can be a reason for an imprecision in the decision when dealing with small coefficient values. In order to solve the first aforementioned disadvantage, mutual information can be applied to measure the degree of independence between pairs of avalanche variables [44], but in this case, it is important to determine which estimator to use, since there are no estimators of unbiased entropy of minimal variance; the second disadvantage can be solved by defining the critical region using a transformation of the correlation coefficient of the type \(t=\sqrt{(N-2)\rho^{2}/(1-\rho^{2})}\), where \(t\) is distributed as a \(t\)-Student distribution with \(N-2\) degrees of freedom [45].  
Another approach is that when \(v^{i}_{\cdot j}\) and \(v^{i}_{\cdot k}\) are independent, then \(s^{i}_{jk}=v^{i}_{\cdot j}\;\bigoplus\;v^{i}_{\cdot k}\) is balanced [46]. In this work, independence will be evaluated by measuring the adjustment \(HW(s^{i}_{jk})\) to the binomial distribution \(B(l,1/2)\), where \(HW(\cdot)\) is the Hamming weight. This allows setting a threshold for the decision criterion on independence between \(v^{i}_{\cdot j}\) and \(v^{i}_{\cdot k}\).  
Since \(H^{i}\) is a binary matrix, the adjustment to the binomial distribution will be measured by the \(\chi^{2}\)-test with 1 degree of freedom, with the test hypothesis given by:  
\[H_{0}:\;v^{i}_{\cdot j}\;\textit{and}\;v^{i}_{\cdot k}\;\textit{ independent},\] \[H_{1}:v^{i}_{\cdot j}\;\textit{and}\;\;v^{i}_{\cdot k}\;\textit{ dependent}.\]  
That is,  
\[H_{0}:HW(s^{i}_{jk})\sim B\left(l,\frac{1}{2}\right),\] \[H_{1}:HW(s^{i}_{jk})\
ot\sim B\left(l,\frac{1}{2}\right).\]  
The test statistic used is  
\[\chi^{2}_{\cdot s^{i}_{jk}}=\frac{\left(HW(s^{i}_{jk})-\frac{l}{2}\right)^{2} }{\frac{l}{4}}. \tag{2}\]  
As usual [2], the value \(\alpha_{1}\) is such that  
\[P\left(\chi^{2}_{\cdot s^{i}_{jk}}\leq\chi^{2}_{\alpha_{1},1}\right)=1-\alpha_ {1}. \tag{3}\]  
If \(\chi^{2}_{\cdot s^{i}_{jk}}>\chi^{2}_{\alpha_{1},1}\) the null hypothesis \(H_{0}\) is rejected.  
It is left for future works, to compare the effectiveness of these three criteria for evaluating independence between the avalanche variables.