Page 144 - 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. 144
4.2 LFSR based stream ciphers and basic definitions
immune if for each subset of at most m input variables xi1 , . . . , xik , 1 ≤ i 1 · · · ≤ i k ≤ n ,
k ≤ m , the mutual information between the keystream z = f (x1, . . . , xn ) and the subset
xi1 , . . . , xik is equal to zero, i.e. I (z ; xi1 , . . . , xik ) = 0. Expressed in terms of probability we
have that
Prob(xi 1 ⊕ xi2 · · · ⊕ xik = z) = 1 z ∈ 2, for any k = 1, . . . , m .
,
2
Another important measure of cryptographical strength of Boolean functions is nonline-
arity. The nonlinearity of f , denoted by f , is defined to be the minimum Hamming
distance 2 to the set of affine functions. For an n -input variable function the set of affine
functions is given as n = {a 1x1 ⊕ · · · ⊕ a n xn ⊕b, a ∈ n ; b ∈ 2}. The set of all n variable
2
linear functions, when b = 0, is denoted by n . Thus, the nonlinearity of f is given by,
f = min d H ( f , g ). (4.3)
g∈ n
Prof. James Massey formulated it nicely once upon a time “ The linearity is the curse of
the cryptographer". Any cryptographic primitive somehow implements Shannon’s con-
cept of confusion which for our scheme (almost) directly corresponds to nonlinearity.
The linear functions will be represented by means of the scalar (inner) product,
n
ϕα : x ∈ n −→ α·x = αi xi .
2
i =1
Definition 4.2.7 A t -th order correlation immune function Boolean function f which is
balanced is called a t -resilient function.
The properties of Boolean functions are most comprehensibly viewed through the
W alsh transform.
Definition 4.2.8 The W alsh transform of f ∈ n in point α ∈ n is denoted by ( f + ϕα)
2
and calculated as,
α∈ n −→ ( f + ϕα) = Wf (α) = (−1)f (x )+ϕα(x ) . (4.4)
2
x∈ n
2
The values of these coefficients form the W alsh-spectrum of f , and clearly f is balanced
if and only if Wf (0) = 0. Notice that ϕα(x ) = α · x uniquely identifies one linear function,
see also relation (4.5).
Exercise 4.2.9 Show that the Hamming distance between a Boolean function f (x ) and
an affine function g (x ) = α · x + b (α ∈ n and b ∈ 2), can be calculated via the Walsh
2
transform as d H ( f , g ) = 2n−1 − (−1)b
( f +ϕα ) .
2
2The Hamming distance between two binary strings of the same length, say f and g , is the number of
positions where these strings differ, i.e., d H ( f , g ) = #{x | f (x ) = g (x )}.
immune if for each subset of at most m input variables xi1 , . . . , xik , 1 ≤ i 1 · · · ≤ i k ≤ n ,
k ≤ m , the mutual information between the keystream z = f (x1, . . . , xn ) and the subset
xi1 , . . . , xik is equal to zero, i.e. I (z ; xi1 , . . . , xik ) = 0. Expressed in terms of probability we
have that
Prob(xi 1 ⊕ xi2 · · · ⊕ xik = z) = 1 z ∈ 2, for any k = 1, . . . , m .
,
2
Another important measure of cryptographical strength of Boolean functions is nonline-
arity. The nonlinearity of f , denoted by f , is defined to be the minimum Hamming
distance 2 to the set of affine functions. For an n -input variable function the set of affine
functions is given as n = {a 1x1 ⊕ · · · ⊕ a n xn ⊕b, a ∈ n ; b ∈ 2}. The set of all n variable
2
linear functions, when b = 0, is denoted by n . Thus, the nonlinearity of f is given by,
f = min d H ( f , g ). (4.3)
g∈ n
Prof. James Massey formulated it nicely once upon a time “ The linearity is the curse of
the cryptographer". Any cryptographic primitive somehow implements Shannon’s con-
cept of confusion which for our scheme (almost) directly corresponds to nonlinearity.
The linear functions will be represented by means of the scalar (inner) product,
n
ϕα : x ∈ n −→ α·x = αi xi .
2
i =1
Definition 4.2.7 A t -th order correlation immune function Boolean function f which is
balanced is called a t -resilient function.
The properties of Boolean functions are most comprehensibly viewed through the
W alsh transform.
Definition 4.2.8 The W alsh transform of f ∈ n in point α ∈ n is denoted by ( f + ϕα)
2
and calculated as,
α∈ n −→ ( f + ϕα) = Wf (α) = (−1)f (x )+ϕα(x ) . (4.4)
2
x∈ n
2
The values of these coefficients form the W alsh-spectrum of f , and clearly f is balanced
if and only if Wf (0) = 0. Notice that ϕα(x ) = α · x uniquely identifies one linear function,
see also relation (4.5).
Exercise 4.2.9 Show that the Hamming distance between a Boolean function f (x ) and
an affine function g (x ) = α · x + b (α ∈ n and b ∈ 2), can be calculated via the Walsh
2
transform as d H ( f , g ) = 2n−1 − (−1)b
( f +ϕα ) .
2
2The Hamming distance between two binary strings of the same length, say f and g , is the number of
positions where these strings differ, i.e., d H ( f , g ) = #{x | f (x ) = g (x )}.
