Bias Analysis of a Certain Problem with Applications to E0 and Shannon Cipher - Information Security and Cryptology-ICISC 2010 - page 23

( c t 0 ,...,c t 0 +25 ). Consequently,
following Corollary 1, we compute the bias δ of (13) as

LFSR outputs at t = t 0 +1 ,...,t 0 +24 to M ·

1
2 100 w

g ( x )) w ,

δ = (

x∈GF (2) 100 : LSB 4 ( x )=0

where g ( x )=( δ 0 if D is a very

weakly biased distribution. However, the Walsh spectrum of D indicates that
this approximation may not be appropriate.

− 1) f ( x ) .FromSection2,weknowthat δ ≈

3.2 Our Results

Due to limited computation power, we only compute for all 8-bit M ,where f :
GF (2) 28. Table 1 - Table 4 compare the real bias δ with δ 0

for M = (11111) 2 ,M = (100001) 2 ,M = (10111) 2 ,M = (110001) 2 ,M = (1011) 2 ,
w =2 ,..., 6 ('X' denotes no bias). Our computation shows that the bias can be
roughly approximated by using these largest

→ GF (2) and ≤

g ( x ) w ,where D ( x ) = 1. Thus, the

g ( x ), where D ( x ) = 1 determine the value of
the bias. Of all 8-bit M 's, we found out that when

number and the sign of these largest

D ( x ) = 1, the largest

is
achieved with M = (11111) 2 , (100001) 2 , (10111) 2 , (110001) 2 .Furthermore,each
of above M has 6 positive and 2 negative, 2 positive and 6 negative, 4 positive and
4 negative, 4 positive and 4 negative largest respectively. Consequently, as shown
in Table 1 - Table 4, it is easy to see that when w is even, the largest bias (up to 8
bits) is achieved with M = (11111) 2 , (100001) 2 , (10111) 2 , (110001) 2 ;if w is odd,
the largest bias (up to 8 bits) is achieved with M = (11111) 2 , (100001) 2 only. This
is in clear contrast to the result [7] of the traditional bias estimate approach based
on independence assumption, which concluded that M = (11111) 2 , (100001) 2 are
the only largest biases (up to 26 bits) regardless of parity of w .
Meanwhile, we give examples here to illustrate our important remarks in Sec-
tion 2. Table 4 shows a good example to Remark 1, where the bias approximation
by Piling-up lemma shows no bias but our result proves wrong. With regards

| g ( x ) |

Table 1. Comparison of δ with δ 0 for w =2 ,..., 6, where M = (11111) 2

w 23 4 5 6
log 2 |δ| -3 -8 -10.5 -14.7 -17
log 2 |δ 0 | -6.7 -10 -13.4 -16.7 -20

Table 2. Comparison of δ with δ 0

for w =2 ,..., 6, where M = (100001) 2

w 23 4 5 6
log 2 |δ| -2.6 -7 -10.4 -14.7 -17
log 2 |δ 0 | -6.7 -10 -13.4 -16.7 -20