Page 146 - 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. 146
4.2 LFSR based stream ciphers and basic definitions
x1 x2 x3 f (x ) ( f + ϕα)
0
000 0 -4
001 0 0
010 0 -4
011 1 -4
100 1 0
101 1 4
110 0 0
111 1
Table 4.1: The truth table and the Walsh spectra of the Boolean function f (x1, x2, x3) =
x1x2 + x2x3 + x3.
the values (placing zeros and controlling maximum values) in the Walsh spectra (even
though Parseval’s equality is satisfied). This means that the Boolean space is only a small
subspace of a more general mapping from n to .
Proposition 4.2.14 Given the Walsh spectra {Wf (α)} of f ∈ n the inverse Walsh trans-
formation can be computed as,
(−1)f (x ) = 2−n Wf (α)(−1)α·x for all x ∈ n . (4.6)
2
α∈ n
2
PROOF. Let us substitute Wf (α) = y∈ n (−1)f (y )+α·y in f (x ) so that,
2
Wf (α)(−1)α·x = (−1)f (y )+α·y (−1)α·x
α∈ n α∈ n y ∈ n
2 2 2
= (−1)f (y ) (−1)α·(x +y )
y∈ n α∈ n
2 2
= 2n (−1)f (x ),
since since the sum α∈ n (−1)α·(x+y ) is equal to zero unless x =y in which case it is equal
2
to 2n . The statement follows.
A special class of functions achieving the upper bound on nonlinearity is known as
bent functions. They exist only for even n and have a uniform spectra, that is, f is bent if
and only if Wf (α) = ±2n/2, for all α ∈ n . It is easily understood that since α∈ n Wf (α)2 =
2
2
22n , then {Wf (α) is minimized with respect to its maximum absolute value if the spectra
is flat. These functions are not balanced however, since Wf (0) = ±2n/2, but they posses
many other desirable properties and have several connections to difference sets, Kerdock
codes, symmetric design etc. (their modified balanced versions are also used in symmet-
ric key primitives). Bent functions correspond to strongly distance regular Cayley graphs,
this connection is discussed later.
x1 x2 x3 f (x ) ( f + ϕα)
0
000 0 -4
001 0 0
010 0 -4
011 1 -4
100 1 0
101 1 4
110 0 0
111 1
Table 4.1: The truth table and the Walsh spectra of the Boolean function f (x1, x2, x3) =
x1x2 + x2x3 + x3.
the values (placing zeros and controlling maximum values) in the Walsh spectra (even
though Parseval’s equality is satisfied). This means that the Boolean space is only a small
subspace of a more general mapping from n to .
Proposition 4.2.14 Given the Walsh spectra {Wf (α)} of f ∈ n the inverse Walsh trans-
formation can be computed as,
(−1)f (x ) = 2−n Wf (α)(−1)α·x for all x ∈ n . (4.6)
2
α∈ n
2
PROOF. Let us substitute Wf (α) = y∈ n (−1)f (y )+α·y in f (x ) so that,
2
Wf (α)(−1)α·x = (−1)f (y )+α·y (−1)α·x
α∈ n α∈ n y ∈ n
2 2 2
= (−1)f (y ) (−1)α·(x +y )
y∈ n α∈ n
2 2
= 2n (−1)f (x ),
since since the sum α∈ n (−1)α·(x+y ) is equal to zero unless x =y in which case it is equal
2
to 2n . The statement follows.
A special class of functions achieving the upper bound on nonlinearity is known as
bent functions. They exist only for even n and have a uniform spectra, that is, f is bent if
and only if Wf (α) = ±2n/2, for all α ∈ n . It is easily understood that since α∈ n Wf (α)2 =
2
2
22n , then {Wf (α) is minimized with respect to its maximum absolute value if the spectra
is flat. These functions are not balanced however, since Wf (0) = ±2n/2, but they posses
many other desirable properties and have several connections to difference sets, Kerdock
codes, symmetric design etc. (their modified balanced versions are also used in symmet-
ric key primitives). Bent functions correspond to strongly distance regular Cayley graphs,
this connection is discussed later.
