# Bit Independence Criterion Extended to Stream Ciphers
## 3 BIC Algorithm in Stream Ciphers
### BIC Acceptance Test  
To decide whether the stream cipher \(f\) satisfies the BIC, it is necessary to take into account the number of rejections of \(H_{0}\) on the \(n\) matrices; for this, a random variable \(T\), which counts the total number of rejections on \(n\) matrices is defined:  
\[T=T\left(n,m,\alpha_{1}\right)=\sum_{i=1}^{n}T^{i}\left(m,\alpha_{1}\right), \tag{4}\]  
where  
\[T^{i}\left(m,\alpha_{1}\right)=T^{i}=\sum_{j=1}^{m-1}\sum_{k>j}^{m}t\left(v^{ i}_{\cdot j},\;v^{i}_{\cdot k},\alpha_{1}\right), \tag{5}\]  
and  
\[t(v^{i}_{\cdot j},\;v^{i}_{\cdot k},\alpha_{1})=\left\{ \begin{array}{ll}1& \text{If $H_{0}$ is rejected for $v^{i}_{\cdot j}$ and $v^{i}_{\cdot k}$}\\ &\text{with significance $\alpha_{1}$}\\ 0&\text{otherwise.}\end{array} \right. \tag{6}\]  
The variable \(T^{i}\) counts the number of rejections of the null hypothesis \(H_{0}\) in the matrix \(H^{i}\). Expected number of rejections of \(H_{0}\). In each of the n SAC \(H^{i}\) matrices, \(C_{2}^{m}\) pairs of columns are formed, thus the number of rejections \(T\) satisfies  
\[0\leq T\leq n\cdot C_{2}^{m}. \tag{7}\]When \(T=0\), we have the ideal case for compliance with the BIC, since all the pairs of columns are independent, while as \(T\gg 0\), the number of non-independent column pairs increases. Under the hypothesis test above, with a significance level \(\alpha_{1}\), the expected number of rejections of \(H_{0}\) is:  
\[E\left(T^{i}|\;H_{0}\right)=\left(\alpha_{1}\cdot C_{2}^{m}\right), \tag{8}\]  
for each matrix \(H^{i}\). In total, among the \(n\) matrices SAC are expected  
\[E\left(T|\;H_{0}\right)=n\cdot\left(\alpha_{1}\cdot C_{2}^{m}\right), \tag{9}\]  
\(H_{0}\) rejections. The random variable  
\[T=\sum_{l=1}^{n}\;\sum_{j=1}^{m-1}\;\sum_{k>j}^{m}t\left(v_{\cdot j}^{i},\;v_{ \cdot k}^{i},\alpha_{1}\right), \tag{10}\]  
follows a binomial distribution \(B(n\cdot C_{2}^{m},\alpha_{1})\). Taking into account that generally \(\alpha_{1}<0.1\), this distribution can be approximated, in this case, to the Poisson distribution with parameter \(\lambda=\left(\alpha_{1}\cdot n\cdot C_{2}^{m}\right)\). Since \(\lambda\) is large, due to large values of \(n\cdot C_{2}^{m}\), then the Poisson distribution can be approximated by the Normal distribution with mean and variance:  
\[E(T|H_{0})=\alpha_{1}\cdot n\cdot C_{2}^{m},\;\sigma^{2}(T|H_{0})=\alpha_{1} \cdot n\cdot C_{2}^{m}\cdot(1-\alpha_{1}). \tag{11}\]  
Thus  
\[Z_{T}=\frac{T-E(T|H_{0})}{\sqrt{\sigma^{2}(T|H_{0})}}\sim N(0,1). \tag{12}\]  
Decision criteriaTo compare the \(Z_{T}\) value with the \(N(0,1)\) distribution, a significance level \(\alpha_{2}\) is selected. Then, it is tested if \(f\) does not satisfy the BIC, with a significance level \(\alpha_{2}\), if \(Z_{T}>Z_{1-\alpha_{2}}\). It can be seen that if \(0\leq T\leq E(T|H_{0})\), then the values of \(Z_{T}\) decreases with respect to \(Z_{1-\alpha_{2}}\) and \(Z_{T}>Z_{1-\alpha_{2}}\) is not satisfied, so the BIC is fulfilled. On the other hand, if \(T\gg E(T|H_{0})\), then the values of \(Z_{T}\) will be greater as \(T\) increases, so \(Z_{T}>Z_{1-\alpha_{2}}\) is satisfied and the BIC compliance is rejected. Normality of the test statistic \(T\).In the expression of \(T\) there are \(n\cdot C_{2}^{m}\) Bernoulli variables \(t(v_{\cdot j}^{i},v_{\cdot k}^{i},\alpha_{1})\), whose distributions under \(H_{0}\) and \(H_{1}\) are different:  
Under \(H_{0}\), all variables \(t(v_{\cdot j}^{i},v_{\cdot k}^{i},\alpha_{1})\) are independent, identically distributed and take the value of \(1\) with probability \(p_{jk}^{i}=P(t(v_{\cdot j}^{i},v_{\cdot k}^{i},\alpha_{1})=1)=\alpha_{1}\), so \(T\) follows exactly a binomial distribution \(B\left(n\cdot C_{2}^{m},\;\alpha_{1}\right)\).