## CryptoDB

### Claude Carlet

#### Affiliation: University of Paris 8

#### Publications

**Year**

**Venue**

**Title**

2017

TOSC

Boolean functions with restricted input and their robustness; application to the FLIP cipher
Abstract

We study the main cryptographic features of Boolean functions (balancedness, nonlinearity, algebraic immunity) when, for a given number n of variables, the input to these functions is restricted to some subset E of

2009

EPRINT

CCZ-equivalence and Boolean functions
Abstract

We study further CCZ-equivalence of $(n,m)$-functions. We prove that
for Boolean functions (that is, for $m=1$), CCZ-equivalence coincides
with EA-equivalence. On the contrary, we show that for $(n,m)$-
functions, CCZ-equivalence is strictly more general than EA-equivalence when $n\ge5$ and $m$ is greater or equal to the smallest
positive divisor of $n$ different from 1.
Our result on Boolean functions allows us to study the natural
generalization of CCZ-equivalence corresponding to the CCZ-equivalence
of the indicators of the graphs of the functions. We show that it
coincides with CCZ-equivalence.

2009

EPRINT

On CCZ-equivalence and its use in secondary constructions of bent functions
Abstract

We prove that, for bent vectorial functions, CCZ-equivalence coincides with EA-equivalence.
However, we show that CCZ-equivalence can be used for constructing bent functions which are new up to CCZ-equivalence. Using this approach we construct classes of nonquadratic bent Boolean and bent vectorial functions.

2008

EPRINT

New balanced Boolean functions satisfying all the main cryptographic criteria
Abstract

We study an infinite class of functions which provably achieve an optimum algebraic immunity, an optimum algebraic degree and a good nonlinearity.
We checked that it has also a good behavior against fast algebraic attacks.

2008

ASIACRYPT

2007

EPRINT

Constructing new APN functions from known ones
Abstract

We present a method for constructing new quadratic APN functions from known ones. Applying this method to the Gold power functions we construct an APN function $x^3+\tr(x^9)$ over $\F_{2^n}$. It is proven that in general this function is CCZ-inequivalent to the Gold functions (and therefore EA-inequivalent to power functions), to the inverse and Dobbertin mappings, and in the case $n=7$ it is CCZ-inequivalent to all power mappings.

2007

EPRINT

Classes of Quadratic APN Trinomials and Hexanomials and Related Structures
Abstract

A method for constructing differentially 4-uniform quadratic hexanomials has been recently introduced by J. Dillon. We give various generalizations of this method and we deduce the constructions of new infinite classes of almost perfect nonlinear quadratic trinomials and hexanomials from $\mathbb{F}_{2^{2m}}$ to $\mathbb{F}_{2^{2m}}$. We check for $m=3$ that some of these functions are CCZ-inequivalent to power functions.

2007

EPRINT

FURTHER PROPERTIES OF SEVERAL CLASSES OF BOOLEAN FUNCTIONS WITH OPTIMUM ALGEBRAIC IMMUNITY
Abstract

Thanks to a method proposed by Carlet, several classes of balanced
Boolean functions with optimum algebraic immunity are obtained. By
choosing suitable parameters, for even $n\geq 8$, the balanced
$n$-variable functions can have nonlinearity
$2^{n-1}-{n-1\choose\frac{n}{2}-1}+2{n-2\choose\frac{n}{2}-2}/(n-2)$,
and for odd $n$, the functions can have nonlinearity
$2^{n-1}-{n-1\choose\frac{n-1}{2}}+\Delta(n)$, where the function
$\Delta(n)$ is describled in Theorem 4.4. The algebraic
degree of some constructed functions is also discussed.

2007

EPRINT

On an Improved Correlation Analysis of Stream Ciphers Using Muti-Output Boolean Functions and the Related Generalized Notion of Nonlinearity
Abstract

We investigate the security of $n$-bit to $m$-bit vectorial Boolean functions in stream ciphers. Such stream ciphers have higher throughput than those using single-bit output Boolean functions. However, as shown by Zhang and Chan at Crypto 2000, linear approximations based on composing the vector output with any Boolean functions have higher bias than those based on the usual correlation attack. In this paper, we introduce a new approach for analyzing vector Boolean functions called generalized correlation analysis. It is based on approximate equations which are linear in the input $x$ but of free degree in the output $z=F(x)$. The complexity for computing the generalized nonlinearity for this new attack is reduced from $2^{2^m \times n+n}$ to $2^{2n}$. Based on experimental results, we show that the new generalized correlation attack gives linear approximation with much higher bias than the Zhang-Chan and usual correlation attack. We confirm this with a theoretical upper bound for generalized nonlinearity, which is much lower than for the unrestricted nonlinearity (for Zhang-Chan's attack) and {\em a fortiori} for usual nonlinearity. We also prove a lower bound for generalized nonlinearity which allows us to construct vector Boolean functions with high generalized nonlinearity from bent and almost bent functions. We derive the generalized nonlinearity of some known secondary constructions for secure vector Boolean functions. Finally, we prove that if a vector Boolean function has high nonlinearity or even a high unrestricted nonlinearity, it cannot ensure that it will have high generalized nonlinearity.

2006

EPRINT

A method of construction of balanced functions with optimum algebraic immunity
Abstract

Because of the recent algebraic attacks, a high algebraic immunity is now an absolutely necessary (but not sufficient) property for Boolean functions used in stream ciphers. A difference of only 1 between the algebraic immunities of two functions can make a crucial difference with respect to algebraic attacks. Very few examples of (balanced) functions with high algebraic immunity have been found so far. These examples seem to be isolated and no method for obtaining such functions is known. In this paper, we introduce a general method for proving that a given function, in any number of variables, has a prescribed algebraic immunity. We deduce an algorithm for generating balanced functions in any odd number of variables, with optimum algebraic immunity. We also give an algorithm, valid for any even number of variables, for constructing (possibly) balanced functions with optimum (or, if this can be useful, with high but not optimal) algebraic immunity. We also give a new example of an infinite class of such functions. We study their Walsh transforms. To this aim, we completely characterize the Walsh transform of the majority function.

2006

EPRINT

Another class of quadratic APN binomials over $\F_{2^n}$: the case $n$ divisible by 4
Abstract

We exhibit an infinite class of almost perfect nonlinear quadratic binomials from $\mathbb{F}_{2^{n}}$ to $\mathbb{F}_{2^{n}}$ with $n=4k$ and $k$ odd. We prove that these functions are CCZ-inequivalent to known APN power functions when $k\ne 1$. In particular it means that for $n=12,20,28$, they are CCZ-inequivalent to any power function.

2006

EPRINT

A class of quadratic APN binomials inequivalent to power functions
Abstract

We exhibit an infinite class of almost perfect nonlinear quadratic binomials from $\mathbb{F}_{2^n}$ to $\mathbb{F}_{2^n}$ ($n\geq 12$, $n$ divisible by 3 but not by 9). We prove that these functions are EA-inequivalent to any power function and that they are CCZ-inequivalent to any Gold function and to any Kasami function. It means that for $n$ even they are CCZ-inequivalent to any known APN function, and in particular for $n=12,24$, they are therefore CCZ-inequivalent to any power function.
It is also proven that, except in particular cases, the Gold mappings are CCZ-inequivalent to the Kasami and Welch functions.

2006

EPRINT

Recursive lower bounds on the nonlinearity profile of Boolean functions and their applications
Abstract

The nonlinearity profile of a Boolean function (i.e. the sequence of its minimum Hamming distances $nl_r(f)$ to all functions of degrees at most $r$, for $r\geq 1$) is a cryptographic criterion whose role against attacks on stream and block ciphers has been illustrated by many papers. It plays also a role in coding theory, since it is related to the covering radii of Reed-Muller codes. We introduce a method for lower bounding its values and we deduce bounds on the second order nonlinearity for several classes of cryptographic Boolean functions, including the Welch and the multiplicative inverse functions (used in the S-boxes of the AES). In the case of this last infinite class of functions, we are able to bound the whole profile, and we do it in an efficient way when the number of variables is not too small. This allows showing the good behavior of this function with respect to this criterion as well.

2005

EPRINT

An infinite class of quadratic APN functions which are not equivalent to power mappings
Abstract

We exhibit an infinite class of almost
perfect nonlinear quadratic polynomials from $\mathbb{F}_{2^n}$ to
$\mathbb{F}_{2^n}$ ($n\geq 12$, $n$ divisible by 3 but not by 9).
We prove that these functions are EA-inequivalent to any power
function. In the forthcoming version of the present paper we will
proof that these functions are CCZ-inequivalent to any Gold
function and to any Kasami function, in particular for $n=12$,
they are therefore CCZ-inequivalent to power functions.

2005

EPRINT

On highly nonlinear S-boxes and their inability to thwart DPA attacks (completed version)
Abstract

Prouff has introduced recently, at FSE 2005, the notion of transparency order of S-boxes. This new characteristic is related to the ability of an S-box, used in a cryptosystem in which the round keys are introduced by addition, to thwart single-bit or multi-bit DPA attacks on the system. If this parameter has sufficiently small value, then the S-box is able to withstand DPA attacks without that ad-hoc modifications in the implementation be necessary (these modifications make the encryption about twice slower). We prove lower bounds on the transparency order of highly nonlinear S-boxes. We show that some highly nonlinear functions (in odd or even numbers of variables) have very bad transparency orders: the inverse functions (used as S-box in the AES), the Gold functions and the Kasami functions (at least under some assumption).

2005

EPRINT

A lower bound on the higher order nonlinearity of algebraic immune functions
Abstract

We extend the lower bound, obtained by M. Lobanov, on the first order nonlinearity of functions with given algebraic immunity, into a bound on the higher order nonlinearities.

2004

EPRINT

On the supports of the Walsh transforms of Boolean functions
Abstract

In this paper, we study, in relationship with covering sequences, the structure of those subsets of $\V {n}$ which can be the Walsh supports of Boolean functions.

2004

EPRINT

Improving the algebraic immunity of resilient and nonlinear functions and constructing bent functions
Abstract

The currently known constructions of Boolean functions with
high nonlinearities, high algebraic degrees and high resiliency
orders do not seem to permit achieving
sufficiently high algebraic
immunities.
We introduce a construction of Boolean functions, which builds a new function from three
known ones. Assuming that the three functions have some
resiliency order, nonlinearity and algebraic degree, as well as their sum modulo 2, the constructed function
has the same resiliency order and can have the same nonlinearity, but
has potentially better
algebraic degree and algebraic immunity. The set of classical constructions together
with this new one (and with a simpler derived one, having the same advantages) permit now to obtain functions achieving all necessary criteria
for being used in the pseudo-random generators in stream ciphers.\\
We also apply this construction to obtain bent functions from known ones.

2002

CRYPTO

2000

EUROCRYPT

#### Program Committees

- Asiacrypt 2010
- Asiacrypt 2009
- FSE 2008
- Asiacrypt 2008
- FSE 2007
- FSE 2004

#### Coauthors

- Frederik Armknecht (1)
- Lilya Budaghyan (7)
- Paul Camion (1)
- Anne Canteaut (1)
- Pascale Charpin (2)
- Patrick Felke (1)
- Keqin Feng (2)
- Caroline Fontaine (1)
- Philippe Gaborit (1)
- Louis Goubin (1)
- Aline Gouget (1)
- Sylvain Guilley (1)
- Lei Hu (1)
- Anthony Journault (1)
- Khoongming Khoo (2)
- Simon Künzli (1)
- Gregor Leander (4)
- Chunlei Li (1)
- Chu-Wee Lim (2)
- Chuan-Wen Loe (2)
- Pierrick Méaux (2)
- Willi Meier (2)
- Sihem Mesnager (1)
- Enes Pasalic (1)
- Emmanuel Prouff (3)
- Michaël Quisquater (1)
- Matthieu Rivain (2)
- Thomas Roche (1)
- Yann Rotella (1)
- Olivier Ruatta (1)
- Nicolas Sendrier (1)
- François-Xavier Standaert (1)
- Xiangyong Zeng (1)