Page 142 - 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. 142
4.2 LFSR based stream ciphers and basic definitions
LFSR11 x1 z1
x2 F zm
LFSR2 xn
.
.
.
LFSRn
Figure 4.6: Nonlinear combination generator
algebraic normal form (ANF):1
n
f (x1, . . . , xn ) = λu x u i , λu ∈ 2 , u = (u 1, . . . , u n ). (4.2)
i
u∈ n i =1
2
There are 2n different terms x u 1 x u 2 · · · x u n for different u ’s. As λu is binary it gives # n=
1 2 n
22n different functions in n variables x1, . . . , xn (denoting by n the set of all Boolean
functions in n variables), implying that a search for "good" functions becomes infeasible
already for n = 6 !
Example 4.2.4 For n = 3 there are 28 = 256 distinct functions specified by λu ,
3 = {λ01 ⊕ λ1x1 ⊕ λ2x2 ⊕ λ3x3 ⊕ λ4x1x2 ⊕ λ5x1x3 ⊕ λ6x2x3 ⊕ λ7x1x2x3}.
The algebraic degree of f , denoted by d e g (f ) or sometimes simply d , is the maximal
value of the Hamming weight of u such that λu = 0. There is a one-to-one correspon-
dence between the truth table and the ANF via so called inversion formulae.
x3 x2 x1 f (x )
000 0
001 0
010 0
011 1
100 1
101 1
110 0
111 1
The truth table of the Boolean function f (x1, x2, x3) = x1x2 + x2x3 + x3.
The easiest way to obtain the ANF from the truth table (without involving Möbius trans-
form) is to expand the ANF of f when f (x ) = 1 and add these together. For the above
example we have:
f (x ) = x1x2(1 + x3) + (1 + x1)(1 + x2)x3 + x1(1 + x2)x3 + x1x2x3 = x1x2 + x2x3 + x3,
1Addition operator over 2 denoted by “⊕” is often replaced with usual addition operator “+”.
LFSR11 x1 z1
x2 F zm
LFSR2 xn
.
.
.
LFSRn
Figure 4.6: Nonlinear combination generator
algebraic normal form (ANF):1
n
f (x1, . . . , xn ) = λu x u i , λu ∈ 2 , u = (u 1, . . . , u n ). (4.2)
i
u∈ n i =1
2
There are 2n different terms x u 1 x u 2 · · · x u n for different u ’s. As λu is binary it gives # n=
1 2 n
22n different functions in n variables x1, . . . , xn (denoting by n the set of all Boolean
functions in n variables), implying that a search for "good" functions becomes infeasible
already for n = 6 !
Example 4.2.4 For n = 3 there are 28 = 256 distinct functions specified by λu ,
3 = {λ01 ⊕ λ1x1 ⊕ λ2x2 ⊕ λ3x3 ⊕ λ4x1x2 ⊕ λ5x1x3 ⊕ λ6x2x3 ⊕ λ7x1x2x3}.
The algebraic degree of f , denoted by d e g (f ) or sometimes simply d , is the maximal
value of the Hamming weight of u such that λu = 0. There is a one-to-one correspon-
dence between the truth table and the ANF via so called inversion formulae.
x3 x2 x1 f (x )
000 0
001 0
010 0
011 1
100 1
101 1
110 0
111 1
The truth table of the Boolean function f (x1, x2, x3) = x1x2 + x2x3 + x3.
The easiest way to obtain the ANF from the truth table (without involving Möbius trans-
form) is to expand the ANF of f when f (x ) = 1 and add these together. For the above
example we have:
f (x ) = x1x2(1 + x3) + (1 + x1)(1 + x2)x3 + x1(1 + x2)x3 + x1x2x3 = x1x2 + x2x3 + x3,
1Addition operator over 2 denoted by “⊕” is often replaced with usual addition operator “+”.
