<<

. 9
( 11 .)



>>

A similar polynomial representation, called the
of length n to the ¬eld F2 = {0, 1}. The number n of
Numerical Normal Form, in which the coef¬cients
variables is rarely large in practice. In the case
and the operation of summation take place in the
of stream ciphers, it is most often less than 10;
group of integers instead of F2 , can also be used
and the S-boxes used in most block ciphers are
for studying Boolean functions.
concatenations of sub S-boxes on at most eight
The ANF of every Boolean function exists and
variables. But determining and studying those
is unique.
Boolean functions which satisfy some conditions
Two simple relations relate the truth table and
needed for cryptographic uses (see below) is not
the ANF:
feasible through an exhaustive computer inves-
tigation, since the number of n-variable Boolean ∀x ∈ F2 , f(x) = aI ,
n
(1)
functions is too large when n ≥ 6. However, clever I⊆supp(x)
computer investigations are useful for imagining
or testing conjectures, and sometimes for generat-
∀I ⊆ {1, . . . , n}, aI = f(x), (2)
ing interesting functions.
x∈F2 /
n
supp(x)⊆I
The Hamming weight w H ( f) of a Boolean func-
tion f on F2 is the size of its support {x ∈ where supp(x) denotes the support {i ∈
n

F2 / f (x) = 0}. The Hamming distance d H ( f, g) be- {1, . . . , n}/ xi = 1} of x. Thus, the function is
n

tween two functions f and g is the size of the the image of its ANF by the binary M¨ bius o
set {x ∈ F2 / f (x) = g(x)}. Thus it equals the Ham-
n
transform, and vice versa.
The degree of the ANF is denoted by d —¦ f and is
ming weight w H ( f • g) of the sum (modulo 2) of the
functions. called the algebraic degree of the function (some
Every n-variable Boolean function can be repre- authors use also the term nonlinearity order). The
sented with its truth table. But the representation algebraic degree is an af¬ne invariant in the fol-
of Boolean functions, which is most usually used lowing sense: two functions f and g are called
in cryptography, is the n-variable polynomial rep- af¬nely (resp. linearly) equivalent if there exists
resentation over F2 of the form an af¬ne (resp. a linear) automorphism (i.e., in-
vertible homomorphism) A of F2 such that g =
n

f —¦ A. A mapping is called af¬ne invariant if it is
f (x) = xi ,
aI
invariant under af¬ne equivalence.
I⊆{1,...,n} i∈I
The af¬ne functions are those Boolean func-
where • denotes the binary sum. The variables tions with degrees 0 or 1 (thus, with the simplest
x1 , . . . , xn appear in this polynomial with expo- ANFs). Denoting by a · x the usual inner product
a · x = a1 x1 • · · · • an xn in F2 , the general form
nents smaller than or equal to 1 because, repre- n

of an n-variable af¬ne function is a · x • a0 , with
senting bits, they are equal to their own squares.
a ∈ F2 ; a0 ∈ F2 .
This polynomial representation is called the Al- n
gebraic Normal Form, in brief, ANF (see also Another representation of Boolean functions
Reed“Muller codes). can be used: the trace representation. The vector
n
space F2 is endowed with the structure of the ¬eld
EXAMPLE: The three-variable function f whose F2n . Let us denote by tr the trace function from
2 n’1
F2n to F2 : tr(x) = x + x 2 + x 2 + · · · + x 2 . Every
truth table equals
54 Boolean functions


Boolean function on F2n can be represented in the gives:
form tr(P(x)), where x ∈ F2n , and where P(x) is a
f (u) = (’1) f (x)•x·u .
polynomial on one variable over F2n , of degree at n
x∈F2
most 2n ’ 1.
Almost all of the characteristics needed for We call f the Walsh transform of f. We shall use
Boolean functions in cryptography can be ex- only this transform of Boolean functions in the se-
pressed by means of the discrete Fourier trans- quel.
forms of the functions. The discrete Fourier trans- The discrete Fourier transform, as any other
form (also called Hadamard transform) of a Fourier transform, has numerous properties. The
Boolean function, or more generally of an integer- two most important ones are the inverse Fourier
valued function • on F2 , is the integer-valued func-
n
relation: • = 2n •, and Parseval™s relation:
tion • de¬ned on F2 by
n
• 2 (u) = 2n • 2 (x).
n n
u∈F2 x∈F2
• (u) = •(x) (’1)x·u . (3)
n
Parseval™s relation applied to the Walsh transform
x∈F2
of a Boolean function f gives:
There exists a simple divide-and-conquer butter-
¬‚y algorithm to compute •, whose complexity is f 2 (u) = 22n .
O(n2n ): n
u∈F2
1. Write the table of the values of • (its truth table
The resistance of the diverse cryptosystems
if • is Boolean), the binary vectors of length n
implementing Boolean functions to the known
being, say, in lexicographic order;
attacks can be quanti¬ed through some funda-
2. Let •0 be the restriction of • to {0} — F2 and
n’1
mental characteristics of the Boolean functions
•1 its restriction to {1} — F2 ; the table of •0
n’1
used in them. The design of cryptographic func-
(resp. •1 ) corresponds to the upper (resp. lower) tions then needs to consider various characteris-
half of the table of •; replace the values of •0 tics (depending on the choice of the cryptosystem)
by those of •0 + •1 and those of •1 by those of simultaneously. Of course, these criteria are par-
•0 ’ •1 ; tially in con¬‚ict with each other, and trade-offs are
3. Apply recursively step 2 to •0 and to •1 (these necessary.
(n ’ 1)-variable functions taking the place of •).
At each recursion, the number of variables of the Criteria and Cryptographic
functions decreases by 1. When the algorithm ends Characteristics
(i.e., when it arrives to functions on one variable
each), the global table gives the values of •. 1. Cryptographic functions must have high al-
gebraic degrees, since all cryptosystems using
EXAMPLE: This algorithm, applied for computing Boolean functions can be attacked if the func-
the Fourier transform of the three-variable func- tions have low degrees.
tion f already considered above, gives the follow- For instance, in the case of combin-
ing table. ing functions, if n LFSRs having lengths
L1 , . . . , Ln are combined by the function f (x) =
I⊆{1,...,n} a I i∈I xi , then the sequence pro-
x1 x2 x3 f (x) f (x)
duced by f can be obtained by a LFSR of length
0 0 0 0 0 0 3
L ¤ I⊆{1,...,n} a I i∈I Li . The degree of f has
’3
0 0 1 1 2 3 therefore to be high so that L can have a high
0 1 0 0 0 0 1 value (otherwise, the system does not resist the
’1
0 1 1 0 1 1 Berlekamp“Massey attack [2]). In the case of
’1
1 0 0 0 0 0 block ciphers, the use of Boolean functions of
’1
1 0 1 1 0 1 low degrees makes effective the “higher differ-
1 1 0 0 0 0 1 ential attack.”
’1 ’1
1 1 1 1 1 2. The output to any Boolean function f always
has correlation to certain linear functions of its
For a given Boolean function f, the discrete inputs. But this correlation should be small.
Fourier transform can be applied to f itself (no- In other words, the minimum Hamming dis-
tice that f (0) equals the Hamming weight of tance between f and all af¬ne functions must be
f ). It can also be applied to the function f (x) = high. Otherwise, an af¬ne approximation of the
(’1) f (x) (often called the sign function), which Boolean function can be used to build attacks on
Boomerang attack 55


any kind of system implementing the function quantify the global diffusion capability of
(see Linear cryptanalysis for block ciphers and the function (the lower they are, the better
Linear cryptanalysis for stream ciphers). The is the diffusion);
minimum distance between f and all af¬ne “ The maximum correlation between an
functions is called the nonlinearity of f and n-variable Boolean function f and a
denoted by N L( f) (see Nonlinearity of Boolean subset I of {1, . . . , n} equals C f (I) =
2’n max (’1) f (x)•g(x) , where F I is the
functions for more details). It can be quanti¬ed
x∈F n
g∈F I
through the Walsh transform: 2

set of all n-variable Boolean functions
whose values depend on {xi , i ∈ I} only. The
N L( f ) = 2n’1 ’ | f (u)|.
1
max
2 u∈F n
maximum correlation C f (I) must be low for
2

every nonempty set I of small size, to avoid
Parseval™s relation then implies that for every
nonlinear correlation attacks (note that mth
n-variable Boolean function f :
order correlation immunity corresponds to
N L( f ) ¤ 2n’1 ’ 2n/2’1 . an optimum maximum correlation to every
subset I of size at most m, if we consider only
3. Cryptographic functions must be balanced af¬ne approximations instead of all Boolean
(their output must be uniformly distributed) for approximations).
avoiding statistical dependence between the in-
put and the output, which can be used in at- Claude Carlet
tacks. Note that f is balanced if and only if
f (0) = 0. References
Moreover, any combining function f(x) must
stay balanced if we keep constant some coor- [1] Evertse, J.H. (1988). “Linear structures in block ci-
dinates xi of x (at most m of them, where m phers.” Advances in Cryptology”EUROCRYPT™87,
is as large as possible). We say that f is then Lecture Notes in Computer Science, vol. 304, eds.
m-resilient. More generally, a (non necessarily David Chaum and Wyn L. Price. Springer-Verlag,
balanced) Boolean function, whose output dis- Berlin, 249“266.
tribution probability is unaltered when any m [2] Massey, J.L. (1969). “Shift-register analysis and
BCH decoding.” IEEE Trans. Inform. Theory, 15,
of the input bits are kept constant, is called
122“127.
mth order correlation-immune (see Correlation
[3] Menezes, A., P. van Oorschot, and S. Vanstone
immune and resilient Boolean functions).
(1996). Handbook of Applied Cryptography. CRC
4. The propagation criterion (PC), generalizing
Press Series on Discrete Mathematics and its Ap-
the strict avalanche criterion (SAC), quanti-
plications. http://www.cacr.math.uwaterloo.ca/hac
¬es the level of diffusion put in a cipher by a
Boolean function. This criterion is more rele-
vant to block ciphers. An n-variable Boolean
function satis¬es the propagation criterion
BOOMERANG ATTACK
PC(l) of degree l if, for every vector x of Ham-
ming weight at most l, the derivative Da f (x) =
The boomerang attack is a chosen plaintext and
f (x) • f (x + a) is balanced (see Propagation
adaptive chosen ciphertext attack discovered by
characteristics of Boolean functions).
Wagner [5]. It is an extension of differential at-
By de¬nition, SAC is equivalent to PC(1).
tack to two-stage differential“differential attack
5. A vector e ∈ F2 is called a linear structure of an
n
which is closely related to impossible differential
n-variable Boolean function f if the derivative
attack as well as to the meet-in-the middle ap-
De f is constant. Boolean functions used in block
proach. The attack may use characteristics, dif-
ciphers should avoid nonzero linear structures
ferentials as well as truncated differentials. The
(see [1]). A Boolean function admits a nonzero
attack breaks constructions in which there are
linear structure if and only if it is linearly equiv-
high-probability differential patterns propagating
alent to a function of the form f (x1 , . . . , xn ) =
half-way through the cipher both from the top and
g(x1 , . . . , xn’1 ) • µ xn where µ ∈ F2 .
from the bottom, but there are no good patterns
6. Other characteristics of Boolean functions have
that propagate through the full cipher.
been considered in the literature:
The idea of the boomerang attack is to ¬nd
“ The sum-of-squares indicator V( f ) =
good conventional (or truncated) differentials that
2
(’1) Da f (x) and the abso-
n n
cover half of the cipher but cannot necessarily be
a∈F2 x∈F2
lute indicator maxa∈F2n , a=0 | |
Da f (x)
x∈F2 (’1) concatenated into a single differential covering the
n
56 Broadcast encryption


whole cipher. The attack starts with a pair of plain- [4] Vaudenay, S. (1998). “Provable security for block ci-
phers by decorrelation.” STACS, Lecture Notes in
texts P and P with a difference which goes
— Computer Science, vol. 3404, eds. M. Morvan, C.
to difference through the upper half of the ci-
Meinel, and D. Krob. Springer-Verlag, Berlin, 249“
pher. The attacker obtains the corresponding ci-
275.
phertexts C and C , applies the difference ∇ to ob-

<<

. 9
( 11 .)



>>