Information Technology Reference
In-Depth Information
On the Higher Order Nonlinearities of Boolean
Functions and S-Boxes, and Their
Generalizations
(Invited Paper)
Claude Carlet
University of Paris 8, Department of Mathematics (MAATICAH)
2 rue de la liberte, 93526 Saint-Denis Cedex, France
claude.carlet@inria.fr
n
2
→
F
2
is its minimum Hamming distance to all functions of algebraic degrees
at most
r
,where
r
is a positive integer. The
r
-th order nonlinearity of
an S-box
F
:
F
Abstract.
The
r
-th order nonlinearity of a Boolean function
f
:
F
n
2
→ F
m
2
is the minimum
r
-th order nonlinearity of its
m
2
\{
component functions
. The role of this cryptographic
criterion against attacks on stream and block ciphers has been illustrated
by several papers. Its study is also interesting for coding theory and is
related to the covering radius of Reed-Muller codes (i.e. the maximum
multiplicity of errors that have to be corrected when maximum likelihood
decoding is used on a binary symmetric channel). We give a survey of
what is known on this parameter, including the bounds involving the al-
gebraic immunity of the function, the bounds involving the higher order
nonlinearities of its derivatives, and the resulting bounds on the higher
order nonlinearities of the multiplicative inverse functions (used in the
S-boxes of the AES). We show an improvement, when we consider an
S-box instead of a Boolean function, of the bounds on the higher order
nonlinearity expressed by means of the algebraic immunity. We study a
generalization (for S-boxes) of the notion and we give new results on it.
v · F
,
v ∈ F
0
}
Keywords:
Block cipher, Boolean function, Covering radius, Cryptogra-
phy, Higher-order nonlinearity, Reed-Muller code, S-box, Stream cipher.
1
Introduction
The invention, in the late 70's, of public key cryptography (which has the im-
portant advantage that the sender and the receiver do not need to exchange a
private key on a secure channel before safely communicating) has not eliminated
conventional
1
cryptography because of the lower eciency of public key cryp-
tosystems and the much larger size of the encryption and decryption keys (some
public key cryptosystems are fast, but they have still larger keys and they also
have some additional drawbacks). Both techniques must then be combined to
1
Also called symmetric, or private key.
