Page 143 - Ellingham, Mark, Mariusz Meszka, Primož Moravec, Enes Pasalic, 2014. 2014 PhD Summer School in Discrete Mathematics. Koper: University of Primorska Press. Famnit Lectures, 3.
P. 143
s Pasalic: Symmetric Key Cryptography and its Relation to Graph Theory 131
after cancelling identical terms. A balanced Boolean function has equally many zeros
and ones in its truth table, i.e., { f (x ) = 0 : x ∈ n } = {f (x ) = 1 : x ∈ n } = 2n −1 . What can
2 2
be said about the upper bound on degree of balanced Boolean functions in n then ?
The reason why we require a high algebraic degree is related to the following attack
scenario. Recall that the basic goal of the attacker is to recover the secret state bits located
in LFSR. Since both LFSR, its connection polynomial c (x ), the filtering function f (x ) and
a portion of the output keystream sequence (known-plaintext attack) are known we have
the following. At each time instance the known keystream bit z t = f (x t , . . . , x t ), where
i 1 n
the time dependency of the inputs to f is due to the structure of LFSR. Anyway, any x t
i
L−1 (i ,t )s j
is a linear function of the initial secret state bits s0, . . . , s L−1, say x t = j =0 a j , due
i
to the linear update function of LFSR. Thus given f of degree d , whose ANF contains at
most T = n + n +...+ n terms, we get one equation of degree d is secret state bits.
0 1 d
Using so-called linearization we can introduce (at most) T new variables in s0, . . . , sL−1
and solve a linear system with respect to unknown and secret si . Since there are L secret
state variables after the above substitution our linear system has at most T = L + L +
0 1
L L L
...+ d terms. The complexity of solving a linear system of size ≈ d is of order ( d )3
using Gauss elimination. Therefore, a large d is desirable but the implementation cost
increases !
Assume now, that n maximum-length LFSRs as in Figure 4.6, whose lengths
L 1, L 2, . . . , L n
are relatively prime, are combined by a nonlinear Boolean function f (x1, . . . , xn ). Then
the linear complexity of the keystream sequence z is f (L 1, . . . , L n ), where the expression
is computed over the integers [6,12]. Since this expression is directly dependent on the
degree of f , then obviously a large linear complexity of the keystream is obtained by
functions of high degree.
Example 4.2.5 (Geffe generator) Assume that the lengths of LFSRs are relatively prime for
the scheme in Figure 4.6, with n = 3. Let the nonlinear combining function be f (x1, x2, x3) =
x1x2 ⊕ x2x3 ⊕ x3. The function f is obviously of degree 2. The Geffe generator is crypto-
graphically weak because the information about the states of LFSR1 and LFSR3 leaks to
the output. For fixed x3 = 0 the output is x1x2 and therefore 75% zeros and 25% of ones are
outputted in this case.
The observation in the above example leads to another important criteria for Boolean
functions used as a nonlinear combining function, which is the concept of correlation
immunity.
Definition 4.2.6 [11] Let x1, x2, . . . , xn be a set of independent uniformly distributed bi-
nary random variables. A Boolean function f (x1, x2, . . . , xn ) is called m th order correlation
after cancelling identical terms. A balanced Boolean function has equally many zeros
and ones in its truth table, i.e., { f (x ) = 0 : x ∈ n } = {f (x ) = 1 : x ∈ n } = 2n −1 . What can
2 2
be said about the upper bound on degree of balanced Boolean functions in n then ?
The reason why we require a high algebraic degree is related to the following attack
scenario. Recall that the basic goal of the attacker is to recover the secret state bits located
in LFSR. Since both LFSR, its connection polynomial c (x ), the filtering function f (x ) and
a portion of the output keystream sequence (known-plaintext attack) are known we have
the following. At each time instance the known keystream bit z t = f (x t , . . . , x t ), where
i 1 n
the time dependency of the inputs to f is due to the structure of LFSR. Anyway, any x t
i
L−1 (i ,t )s j
is a linear function of the initial secret state bits s0, . . . , s L−1, say x t = j =0 a j , due
i
to the linear update function of LFSR. Thus given f of degree d , whose ANF contains at
most T = n + n +...+ n terms, we get one equation of degree d is secret state bits.
0 1 d
Using so-called linearization we can introduce (at most) T new variables in s0, . . . , sL−1
and solve a linear system with respect to unknown and secret si . Since there are L secret
state variables after the above substitution our linear system has at most T = L + L +
0 1
L L L
...+ d terms. The complexity of solving a linear system of size ≈ d is of order ( d )3
using Gauss elimination. Therefore, a large d is desirable but the implementation cost
increases !
Assume now, that n maximum-length LFSRs as in Figure 4.6, whose lengths
L 1, L 2, . . . , L n
are relatively prime, are combined by a nonlinear Boolean function f (x1, . . . , xn ). Then
the linear complexity of the keystream sequence z is f (L 1, . . . , L n ), where the expression
is computed over the integers [6,12]. Since this expression is directly dependent on the
degree of f , then obviously a large linear complexity of the keystream is obtained by
functions of high degree.
Example 4.2.5 (Geffe generator) Assume that the lengths of LFSRs are relatively prime for
the scheme in Figure 4.6, with n = 3. Let the nonlinear combining function be f (x1, x2, x3) =
x1x2 ⊕ x2x3 ⊕ x3. The function f is obviously of degree 2. The Geffe generator is crypto-
graphically weak because the information about the states of LFSR1 and LFSR3 leaks to
the output. For fixed x3 = 0 the output is x1x2 and therefore 75% zeros and 25% of ones are
outputted in this case.
The observation in the above example leads to another important criteria for Boolean
functions used as a nonlinear combining function, which is the concept of correlation
immunity.
Definition 4.2.6 [11] Let x1, x2, . . . , xn be a set of independent uniformly distributed bi-
nary random variables. A Boolean function f (x1, x2, . . . , xn ) is called m th order correlation
