Page 145 - 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. 145
s Pasalic: Symmetric Key Cryptography and its Relation to Graph Theory 133
A closely related concept, known as the Hadamard transform and denoted by WfH , sim-
ply uses the values f (x ) instead of (−1)f (x), that is WfH (α) = x∈ n f (x )(−1)ϕα(x). A simple
2
relationship between the two transforms is given as an exercise.
Exercise 4.2.10 Show that Wf (α) = −2WfH (α) + 2n ∆(α) for any α ∈ n , where ∆(α) = 1 if
2
α = 0, and zero otherwise.
The values of Walsh and Hadamard spectra of f ∈ n are easily obtained through Wf =
Hn f T , respectively, WfH = Hn (−1f )T , where f T denotes the transpose of the truth table
of f and Hn is the Hadamard matrix of size 2n × 2n defined recursively,
H1 = 11 , Hn = Hn−1 Hn−1 .
1 −1 Hn−1 −Hn−1
It is easy to show that H H T = 2n I and also H T H = 2n I , where I is the identity matrix
whose diagonal elements are ones.
The nonlinearity of f (x ) can be obtained via the Walsh transform as,
= 2n−1 − 1 max | ( f + ϕα)|. (4.5)
f 2 α∈ n
2
Lemma 4.2.11 [13] Let f ∈ n and let t be some positive integer. The function f is said to
be correlation immune (CI) of order t if and only if ( f + ϕα) = 0 for any a ∈ n such that
2
1 ≤ w t (α) ≤ t .
An important property of the Walsh spectra, referred to as Parseval’s equality [4],
states that for any Boolean function f ∈ n, α∈ n 2( f + ϕα) = 22n .
2
Exercise 4.2.12 Use a similar technique as in the proof of Proposition 4.2.14 to show Par-
seval’s equality. Consider the sum u∈ n Wf (u )Wf (u ⊕ v ) and show it is 22n if v = 0 and
2
zero otherwise.
We illustrate the cryptographic criteria discussed above with a detailed examination of
the nonlinear combining function used in the Geffe generator, see also Example 4.2.5.
Example 4.2.13 Consider the function f (x1, x2, x3) = x1x2 + x2x3 + x3 used in the Geffe
generator. The truth table and the Walsh spectra are given in Table 4.1. Note that the linear
functions ϕα are determined by x values. For instance the entry (x1, x2, x3) = (1, 0, 0) will
yield ϕα = (x1, x2, x3) · (1, 0, 0) = x1. Then, the nonlinearity f = 2n −1 − 1 maxα∈ n| (f +
2
2
ϕα)| = 2. The function is balanced but not correlation immune since ( f + x1) = ( f +
x3) = 0.
Notice that the Walsh spectra, constrained by Parseval’s equality, is integer valued and
obviously we cannot design cryptographically strong Boolean functions by specifying
A closely related concept, known as the Hadamard transform and denoted by WfH , sim-
ply uses the values f (x ) instead of (−1)f (x), that is WfH (α) = x∈ n f (x )(−1)ϕα(x). A simple
2
relationship between the two transforms is given as an exercise.
Exercise 4.2.10 Show that Wf (α) = −2WfH (α) + 2n ∆(α) for any α ∈ n , where ∆(α) = 1 if
2
α = 0, and zero otherwise.
The values of Walsh and Hadamard spectra of f ∈ n are easily obtained through Wf =
Hn f T , respectively, WfH = Hn (−1f )T , where f T denotes the transpose of the truth table
of f and Hn is the Hadamard matrix of size 2n × 2n defined recursively,
H1 = 11 , Hn = Hn−1 Hn−1 .
1 −1 Hn−1 −Hn−1
It is easy to show that H H T = 2n I and also H T H = 2n I , where I is the identity matrix
whose diagonal elements are ones.
The nonlinearity of f (x ) can be obtained via the Walsh transform as,
= 2n−1 − 1 max | ( f + ϕα)|. (4.5)
f 2 α∈ n
2
Lemma 4.2.11 [13] Let f ∈ n and let t be some positive integer. The function f is said to
be correlation immune (CI) of order t if and only if ( f + ϕα) = 0 for any a ∈ n such that
2
1 ≤ w t (α) ≤ t .
An important property of the Walsh spectra, referred to as Parseval’s equality [4],
states that for any Boolean function f ∈ n, α∈ n 2( f + ϕα) = 22n .
2
Exercise 4.2.12 Use a similar technique as in the proof of Proposition 4.2.14 to show Par-
seval’s equality. Consider the sum u∈ n Wf (u )Wf (u ⊕ v ) and show it is 22n if v = 0 and
2
zero otherwise.
We illustrate the cryptographic criteria discussed above with a detailed examination of
the nonlinear combining function used in the Geffe generator, see also Example 4.2.5.
Example 4.2.13 Consider the function f (x1, x2, x3) = x1x2 + x2x3 + x3 used in the Geffe
generator. The truth table and the Walsh spectra are given in Table 4.1. Note that the linear
functions ϕα are determined by x values. For instance the entry (x1, x2, x3) = (1, 0, 0) will
yield ϕα = (x1, x2, x3) · (1, 0, 0) = x1. Then, the nonlinearity f = 2n −1 − 1 maxα∈ n| (f +
2
2
ϕα)| = 2. The function is balanced but not correlation immune since ( f + x1) = ( f +
x3) = 0.
Notice that the Walsh spectra, constrained by Parseval’s equality, is integer valued and
obviously we cannot design cryptographically strong Boolean functions by specifying
