# Bit Independence Criterion Extended to Stream Ciphers
## 3 BIC Algorithm in Stream Ciphers
### BIC Test Algorithm
#### 3.4.2 Parameter Selection  
As seen in the previous section, the number of operations of the BIC algorithm depends on three parameters, the number \(l\) of inputs, the number \(n\) of bits of each input, and the number \(m\) of bits of each output. _Selection of \(l\) such that \(\widehat{p}\approx 0.5\) and \(HW(s^{i}_{jk})\) fit to the binomial distribution \(B(n,1/2)\)._ The number \(l\) of entries influences the effectiveness of the \(\chi^{2}\)-test in determining whether two columns are independent. Increasing \(l\) guarantees a greater fit of \(HW(s^{i}_{jk})\) to the binomial distribution \(B(n,1/2)\); however,it causes an increase in the number of operations. In practice, the idea is to obtain a cost-effectiveness ratio using a value of \(l\) such that it maintains the fit and provides a practical number of operations. Using the confidence interval for proportions [47], it is possible to obtain a value of \(l_{0}\), such that prefixing \(l>l_{0}\) achieves a good fit. This confidence interval is given by  
\[P\left(-Z_{\alpha_{1}/2}<\frac{\widehat{p}-p}{\sqrt{\frac{pq}{l}}}<Z_{\alpha_{ 1}/2}\right)=1-\alpha_{1}. \tag{14}\]  
Solving for \(l\) we get to  
\[l>l_{0}=\frac{Z_{\alpha_{1}/2}^{2}\ pq}{e^{2}}, \tag{15}\]  
where \(e=\widehat{p}-p\), is the deviation of \(\widehat{p}\) over \(p\), and \(\ q=(1-p)\). **Example 1**. : _Calculation of the lower bound \(l_{0}\) for \(l\). A value \(l_{0}\) from which, with high probability, it is satisfied that \(\widehat{q}\approx\widehat{p}\approx 0.5\) is needed. Then, substituting for a significance level \(\alpha_{1}=0.01\) and a deviation \(e\) whose absolute value \(|e|\) satisfy inequality \(|e|=|\widehat{p}-0.5|\leq 0.03\), we get_  
\[l_{0}=\frac{Z_{0.005}^{2}\cdot 0.25}{0.03^{2}}\approx 2189.\]  
_In this way, for the significance level \(\alpha_{1}\) and the deviation \(e\) selected, it is concluded that \(l\) must be chosen such that \(l>l_{0}=2189\)._  
**Example 2**. : _Convergence of \(\widehat{p}\) and deviation \(\widehat{e}\). Table 2 shows the behavior of the deviation \(\widehat{e}\) observed for several \(l\), \(l>l_{0}=2189\), with \(n=64\) and \(m=32\). It can be seen how, for most of the estimated \(e\), the imposed condition is met \(|\widehat{e}|\leq 0.03\)._  
_Selection of \(n,m\) under the null hypothesis \(H_{0}\)._ The number \(n\) of inputs and the number \(m\) of outputs influence the sample size for the calculation of the number \(T\) of rejections of \(H_{0}\). In general, we will have \(d=n\cdot C_{2}^{m}\) pairs of columns to check and it is expected, with probability \(\alpha_{1}\), that \(\lambda=\alpha_{1}\cdot d\) pairs of columns will be rejected. Let \(\lambda_{0}=\alpha_{1}\cdot d_{0}\) be some default value of \(\lambda\) from which the distribution of \(T\) can be approximated to \(N(0,1)\). It is necessary to select \(n\) and \(m\) such that \(d>d_{0}\) is satisfied and a value of \(\lambda\) such that \(\lambda>\lambda_{0}\) is obtained. It is advisable to select a high value of \(\lambda_{0}\) that avoids the use of corrections and provides a good fit. It is known that increasing \(\lambda_{0}\) provides better precision in the Poisson approximation to the Normal distribution. To obtain \(d_{0}\), we can use the confidence interval for proportions [47], this time in an approximation to the Normal distribution with one tail. So, we have  
\[P\left(\frac{\widehat{p}-p}{\sqrt{\frac{pq}{d}}}<Z_{\alpha_{2}}\right)=1- \alpha_{2}. \tag{16}\] \begin{table}
\begin{tabular}{c c c} \hline \hline \(I\) & **Mean Value \(\widehat{p}\)** & \(|\widehat{e}|\) \\ \hline
4096 & 0.5 & 0.05 \\ \hline
8192 & 0.5 & 0.03 \\ \hline
16,384 & 0.5 & 0.03 \\ \hline
32,768 & 0.5 & 0.02 \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Values of the deviation \(|\widehat{e}|\) for several \(l\), \(l>l_{0}=2189\) with \(n=64\) and \(m=32\). Solving for \(d\) we get to  
\[d>d_{0}=\frac{Z_{\alpha_{2}}^{2}pq}{e^{2}}. \tag{17}\]  
**Example 3**. : _Calculation of the lower bound \(d_{0}\) for \(d\).