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

2 n ) time to compute δ . It grows linearly in k .Itispracticalfor
modest n , for example n

It needs O ( kn ×

32. Without our result, the naive computation needs
O (2 kn ) time. In contrast, note that under the independence assumption, it takes
time O ( k

≤

2 n ) to compute the bias by Piling-up lemma.
Next, let us see how the distribution D affects the bias δ .First,if D is a
uniform distribution, we can deduce that a i 's are independent and uniformly
distributed. On one hand, Piling-up lemma directly tells us that δ = δ 1 ·

×

δ k ,
where δ i denotes the bias of f i . On the other hand, from the assumption D is
uniform distribution, we know that

δ 2 ···

D ( x )=1for x =0and D ( x )=0for x

=0.

By Corollary 1, we have

1
2 kn

δ = g 1 (0) · g 2 (0) ··· g k (0)

1

As δ i = δ k . Thus we have seen that our result

incorporates the Piling-up lemma as a special case.
Second, if a 1 ⊕

2 n

g i (0), we also have δ = δ 1 ···

a 2 ⊕···⊕ a k = a 0 for a fixed n -bit a 0 ,thatis, D ( a 0 )=1,then

D ( x )=1if x

a 0 =0and D ( x )= · −

1if x

· a 0 = 1. By Corollary 1, now we have

g k ( x ) .

x : a 0 ·x =0 x : a 0 ·x =1

1
2 kn

δ = g 1 ( x ) ··· g k ( x ) − g 1 ( x ) ··· (7)

Note that when a 0 =0,wehave

2 kn
x

1

δ = g 1 ( x ) ··· g k ( x ) . (8)

The above result (8) with f 1 = f 2 = f 3 = f 4 and k = 4 was shown in [9].
Thirdly, let β =max x =0

D ( x ) be the largest bias of D . And we consider a

D (0) = 1.

general D with β = ± 1. Note that regardless of D , we always have

From Corollary 1,

⎛ ⎞

1
2 kn

⎝ D ( x ) ⎠ .

δ = g 1 (0) ··· g k (0) +

|< 1

g 1 ( x ) ··· g k ( x ) · (9)

x :0 <| D ( x )

In case that D is a weakly biased distribution, the second addend on the right-
hand side of Eq.(9) is negligible compared with the first addend (because β

1
and the number of biases which are roughly on the same order of magnitude is
also very small). Thus, we can have the approximation below

1
2 kn g 1 (0)

δ ≈ ··· g k (0) = δ 1 ···δ k .

If D is not weakly biased, the bias δ cannot be approximated by the bias in the
independence case. In Section 3, Section 4, we will demonstrate with an example
of strongly biased and weakly biased D respectively.
When comparing the value of the bias δ in our problem with the bias in the
independent case, we point out three important remarks below.