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-