Claude Carlet's publications and their abstracts
Books, Chapters in books and articles in an encyclopedia:
1) Special Issue on Coding and
Cryptography. Guest Editor: C. Carlet. Guest co-editors: P. Charpin, M. Girault, G. Kabatiansky
and J.H. Van Tilborg. Discrete
Applied Mathematics, vol.
111, nos 1-2, pp. 1-218 (2001).
2) Special Issue on Coding and
Cryptography (Proceedings of International Workshop on Coding and Cryptography 2001). Guest
Editor: C. Carlet. Guest co-editors: M. Girault, T. Helleseth, T. Hoehold, F.
Morain, N. Sendrier. Discrete
Applied Mathematics,
vol.
128, no 1, pp. 1-316 (2003).
3) C. Carlet, associate editor of the "Special Section on Sequence
Design and its Application in Communications" of the journal IEICE
Transactions on Fundamentals of Electronics, Communications and
computer sciences, 2006.
4) WAIFI, Proceedings of "First International Workshop on the
Arithmetic of
Finite Fields 2007", Lecture Notes in Computer Science 4547, 353 pages
(C.
Carlet and B. Sunar editors).
5) C. Carlet "Boolean
Functions for Cryptography and Error Correcting Codes", Chapter of
the monography ``Boolean
Models and Methods in Mathematics, Computer Science, and Engineering"
published by Cambridge
University Press,
Yves
Crama and Peter L. Hammer (eds.), pp. 257-397, 2010. Please
find here a preliminary
version.
6) C. Carlet, "Vectorial Boolean Functions for Cryptography". Idem, pp.
398-469, 2010. Please
find here a preliminary version
7) C. Carlet, Five articles in the Encyclopedia
of Cryptography and Security, Springer (Henk van Tilborg, Editor,
new version)
8) SETA, Proceedings of the "Sixth Conference on Sequences and their
Applications 2010", Lecture Notes in Computer Science 6338, 464 pages
(C.
Carlet and A. Pott editors)
9) C. Carlet and T. Helleseth, "Sequences, Boolean functions, and
Cryptography", chapter of the "Handbook
of Codes, Sequences and Their
Applications", published by CRC
Press,
Serdar Boztas (ed.), to
appear (?)
10) Special issue for Jacques Wolfmann of Cryptography and
Communications, 2011, Y. Aubry, C. Carlet, P. Langevin and P.
Véron eds.
11) C. Carlet, "Boolean functions", Section of the "Handbook of
Finite Fields", published by CRC
Press, Gary Mullen and Daniel Panario (eds.), pp. 241-252, 2013.
12) S. El Hajji, A. Nitaj, C. Carlet, El M. Souidi (Eds.); Codes,
Cryptology, and Information Security; First International Conference,
C2SI 2015 Rabat, Morocco, May 26–28, 2015, In Honor of Thierry Berger,
Lecture Notes in Computer Science 9084
13) Special issue ``Discrete Structures for Side Channel Attacks and
Their Counter-measures'' of Cryptography and Communications, C. Carlet
and P.-A. Fouque eds., 2015.
14) C. Carlet, M. A. Hasan and V. Saraswat (Eds). Security, Privacy, and
Applied Cryptography Engineering - 6th International Conference, SPACE
2016, Hyderabad, India, December 14-18, 2016, Proceedings. Lecture Notes
in Computer Science 10076, Springer 2016
15) Special Issue on ``Boolean functions and their applications 2017'',
Cryptography and Communications, L. Budaghyan, C. Carlet and T.
Helleseth, eds., 2018.
16) Special Issue on ``Boolean functions and their applications 2018'',
Cryptography and Communications 2017, L. Budaghyan, C. Carlet and T.
Helleseth, eds., 2019.
17) C. Carlet, S. Guilley, A. Nitaj, El M. Souidi (Eds.); Codes,
Cryptology, and Information Security; Third International Conference,
C2SI 2019 Rabat, Morocco, April 22–24, 2019, In Honor of Said El Hajji,
Lecture notes in computer science n$^\circ$ 11445, 2019.
18) Special Issue on ``Boolean functions and their applications 2020'',
Cryptography and Communications, L. Budaghyan, C. Carlet, T.
Helleseth and K. Nyberg, eds., 2021.
19) C. Carlet "Boolean
Functions for Cryptography and Coding Theory", Monograph, Cambridge
University Press, 562 pages, 2021. Please find here a preliminary version.
20) Special Issue on ``Boolean functions and their applications 2021'',
Cryptography and Communications, L. Budaghyan, C. Carlet, C. Ding and T.
Helleseth, eds., 2022.
21) Special Issue on ``Boolean functions and their applications 2022'',
Cryptography and Communications, L. Budaghyan, C. Carlet, W. Meidl and T.
Helleseth, eds., 2023.
Full papers in international journals:
1)"The Automorphism Groups of The Kerdock Codes", C. Carlet,
Journal of Information and Optimization Sciences" vol. 12 no. 3,
387-400 (1991)
Abstract:
We prove that the automorphism group of the Kerdock
code of length 2^m (m even at least 6) is the group of
permutations on
GF(2^m) = GF(2^{m-1}) x GF(2) generated by the automorphism group of
the field GF(2^{m-1}), the affine group of GF(2^{m-1}), and the
translations on GF(2).
2) "Partially-bent functions", C. Carlet, Designs Codes and
Cryptography, 3, 135-145 (1993) and Proceedings of CRYPTO 1992
Abstract:
We study a conjecture about the numbers of
non-zeros of, respectively, the auto-correlation function and the Walsh
transform of the function (-1)^{f(x)}, where f(x) is any boolean
function on {0,1}^n. The result that we obtain leads us to introduce
the class of partially-bent functions. We study within these functions
the propagation criterion. We characterize those partially-bent
functions which are balanced and prove a relation between their number
(which is unknown) and the number of non-balanced partially-bent
functions on {0,1}^{n-1}. Eventually, we study their correlation
immunity .
3) "The automorphism groups of the Delsarte-Goethals codes", C. Carlet,
Designs Codes and Cryptography, 3, 237-249 (1993)
Abstract:
We determine the automorphism groups of the
Delsarte-Goethals codes DG(m,d). The groups that we obtain are the same
as those of the Kerdock codes K(m) of the same length .
4)"A General Case of Formal Duality Between Binary Non-linear Codes",
C. Carlet, Discrete Mathematics 111, 77-85 (1993)
Abstract:
We give a general context in which a binary code C
admits at least one code whose weight enumerator is dual to that of C.
We study two examples of applications of this general result.The first
one is the formal duality between the Kerdock code and the generalized
Preparata codes of same length and the second one gives a new example
of dual weight enumerators.
5) "The divisors of x^{2^m} + x of constant derivatives and degree
2^{m-2}", C. Carlet, SIAM Journal on Discrete Math. vol 7, no. 2,
238-244 (1994)
Abstract:
We completely characterize those polynomials of
degree 2^m- 2 over the Galois field GF(2^m) which are fully reducible
and admit no multiple factor (i.e. which divide x^{2^m} + x), and whose
derivatives are constants. We show that this problem is connected with
a problem in algebraic coding theory.
6)"Generalized Partial Spreads", C. Carlet, IEEE Transactions on
Information Theory vol. 41 no 5 (correspondence) pages 1482-1487 (1995)
Abstract:
We exhibit a simple condition under which the sum
(modulo 2) of characteristic functions of n/2 - dimensional
vector-subspaces of (GF(2))^n (n even) is a bent function. The
"Fourier" transform of such a bent function is the sum of the
characteristic functions of the duals of these spaces. The class of
bent functions that we obtain contains the whole Partial Spreads class.
Any element of Maiorana-McFarland's class or of class D is equivalent
to one of its elements. Thus, this new class gives a unified insight of
both general classes of bent functions studied by J.F. Dillon in his
thesis. We deduce a way to construct new classes of bent functions and
exhibit an example.
7) "On Z_4-duality", C. Carlet, IEEE Transactions on Information
Theory vol 41 no. 5 (correspondence) pages 1487-1495 (1995)
Abstract:
Recently was introduced the new notion on binary
codes called Z_4-linearity. This notion explains why Kerdock codes and
Delsarte-Goethals codes admit formal duals in spite of their
nonlinearity. The "Z_4-duals" of these codes (called 'Preparata' and
'Goethals' codes) are new nonlinear codes which admit simpler decoding
algorithms than the previously known formal duals (the generalized
Preparata and Goethals codes).
We prove, by using the notion of exact weight enumerator, that the
relationship between any Z_4-linear code and its Z_4-dual is stronger
than the standard formal duality and we deduce the weight enumerators
of related generalized codes.
8) "A characterization of
binary bent functions", C. Carlet and Philippe Guillot, Journal of
Combinatorial Theory, Series A, Vol. 76,
No. 2, 328-335 (1996)
Abstract:
A recent paper by Carlet introduces a general class of binary bent
functions on (GF(2))^n (n even)
whose elements are expressed by means of characteristic
functions (indicators) of
{n/2}-dimensional vector-subspaces of (GF(2))^n.
An extended version of this
class is introduced in the same paper; it is conjectured
that this version is coinciding with the whole class of
bent functions.
In the present paper, we prove that this conjecture is true.
9) "An alternate characterization of the bentness of binary
functions, with uniqueness", C. Carlet and Philippe Guillot, Designs
Codes and Cryptography, Vol 14, no 2, p. 133-140 (may 1998)
Abstract:
In a previous paper, we have obtained a characterization
of the binary bent functions on (GF(2))^n (n even) as linear
combinations modulo 2^{n/2}, with integral coefficients, of
characteristic functions (indicators) of n/2-dimensional
vector-subspaces of (GF(2))^n.
There is no uniqueness of the representation of a given bent function
related to this
characterization.
We obtain now a new characterization for which there is uniqueness of
the representation.
10) "Z_{2^k}-linear codes", C. Carlet, IEEE Transactions on Information
Theory, Vol. 44, no 4 (correspondence), pages 1543-1547 (1998)
Abstract:
We introduce a generalization to Z_{2^k} of the Gray map and
generalized versions of Kerdock and Delsarte-Goethals codes.
11) "Codes, bent functions and permutations suitable for DES-like
cryptosystems", C. Carlet, P. Charpin and V. Zinoviev, Designs Codes
and
Cryptography, 15, p. 125-156 (1998)
Abstract:
Almost bent functions oppose an optimum resistance to
linear and differential cryptanalysis. We present basic properties
of almost bent functions; particularly we give an upper bound on
the degree.
We develop
the "coding theory" point of view for studying the
existence of almost bent functions, showing explicitly
the links with cyclic codes.
We also give new characterizations of almost bent functions
by means of associated Boolean functions.
12) "On Cryptographic Propagation Criteria for Boolean Functions",
C. Carlet, Special Issue on Cryptology of "Information and
Computation", in Honor of Professor Arto Salomaa on Occasion of His
65th Birthday (article invité) (1999)
Abstract:
We determine the functions on GF(2)^n which satisfy the propagation
criterion
of degree (n-2), PC(n-2).
We study subsequently the propagation criterion of degree
l and order k and its extended version EPC.
We determine those Boolean functions on GF(2)^n which satisfy PC(l) of
order greater than or equal to (n-l- 2). We show that none of them
satisfies EPC(l) of same order.
We finally give a general construction of nonquadratic functions
satisfying EPC(l) of order k. This construction uses the existence of
nonlinear,
systematic codes with good minimum
distances and dual distances (e.g. Kerdock codes and Preparata codes).
13) ``On cryptographic properties of the cosets of R(1,m)", A.
Canteaut, C. Carlet, P. Charpin and C. Fontaine, IEEE Transactions
on
Information Theory (regular paper) Vol. 47, no 4, pp. 1494-1513 (2001)
Abstract:
We introduce a new approach for the study of weight distributions
of cosets of the Reed-Muller code of order 1.
Our approach is based on the method introduced by Kasami, using Pless
identities.
By interpreting some equations, we obtain a necessary
condition for a coset to have a ``high'' minimum weight.
We next examine the impact of our results when
some cryptographic criteria of Boolean functions
are considered.
14) ``Spectral Domain Analysis of Correlation Immune and Resilient
Boolean Functions", C. Carlet and P. Sarkar, Finite fields and
Applications (revue) 8, pp. 120-130 (2002).
Abstract:
We use a general property of Fourier transform to obtain direct proofs
of recent divisibility results on the Walsh Transform of
correlation immune and resilient functions. Improved upper bounds on
the
nonlinearity of these functions are obtained from the divisibility
results. We deduce further information on correlation immune and
resilient
functions. In particular, we obtain
a necessary condition on the algebraic normal
form of correlation immune functions attaining the maximum possible
nonlinearity.
15) ``Covering sequences of Boolean functions and their cryptographic
significance", C. Carlet and Yu. Tarannikov, Designs, Codes and
Cryptography, 25, pp. 263-279 (2002).
Abstract:
We introduce the notion of covering sequence of a Boolean function,
related to the derivatives of the function.
We give complete characterizations of balancedness, correlation
immunity and
resiliency of Boolean functions by means of their covering sequences.
By considering
particular covering sequences, we define subclasses of
(correlation-immune) resilient functions. We derive upper bounds on
their algebraic degrees and on their nonlinearities. We give
constructions of
resilient functions belonging to these classes. We show that they
achieve the best known trade-off between order of resiliency,
nonlinearity
and
algebraic degree.
16) ``Spectral Methods for Cross-Correlations of Geometric Sequences",
A. Klapper and C. Carlet. IEEE Transactions on Information Theory, Vol.
50 (correspondence), pp. 229-232, 2004.
Abstract:
Families of sequences with low pairwise shifted cross-correlations are
desirable for applications such as CDMA communications. Often such
sequences must have additional properties for specific applications.
Several ad hoc constructions of such families exist in the literature,
but there are few systematic approaches to such sequence design. In
this paper we introduce a general method of constructing new families
of sequences with bounded pairwise shifted cross-correlations from old
families of such sequences. The bounds are obtained in terms
the maximum cross-correlation in the old family and the Walsh transform
of certain functions.
17) ``Highly Nonlinear Mappings". C. Carlet and C. Ding. Special
Issue
``Complexity Issues in Coding and Cryptography" du Journal of
Complexity, Edition spéciale pour les 60 ans de Harald
Niederreiter,
vol 20, numbers 2-3, pp. 205-244, 2004.
Abstract:
Functions with high nonlinearity have important applications in
cryptography, sequences and coding theory. The purpose of this paper is
to give a well-rounded treatment of non-Boolean functions with optimal
nonlinearity. We summarize and generalize known results, and prove a
number of new results. We also present open problems about functions
with high nonlinearity.
18) ``On the confusion and diffusion properties of
Maiorana-McFarland's and extended Maiorana-McFarland's functions". C.
Carlet. Special Issue ``Complexity Issues in Coding and Cryptography"
du Journal of Complexity, Special Issue in honour of
Harald
Niederreiter, vol 20, numbers 2-3, pp. 182-204, 2004.
Abstract:
A practical problem in symmetric cryptography is finding
constructions of Boolean functions leading to reasonably large
sets of functions satisfying some desired cryptographic
criteria. The main known construction, called
Maiorana-McFarland, has been recently extended. Some other
constructions exist, but lead to smaller classes of functions.
Here, we study more in detail the nonlinearities and the resiliencies
of the functions produced by all these constructions. Further we
see how to obtain functions satisfying the propagation criterion
(among which bent functions) with these methods, and we give a new
construction of bent functions based on the extended
Maiorana-McFarland's construction.
19) ``Concatenating indicators of flats for designing cryptographic
functions. C. Carlet. Designs, Codes and
Cryptography, volume 36, No 2, pp. 189 - 202, 2005.
Abstract:
Boolean functions with good cryptographic characteristics are
needed for the design of robust pseudo-random generators for
stream ciphers and of S-boxes for block ciphers. Very few general
constructions of such cryptographic Boolean functions are known.
The main ones correspond to concatenating affine or quadratic
functions. We introduce a general construction
corresponding to the concatenation of indicators of flats. We
show that the functions it permits to design can present very good
cryptographic characteristics.
20) ``On the degree, nonlinearity, algebraic thickness and
non-normality of Boolean functions, with developments on
symmetric
functions". C. Carlet. IEEE Transactions on Information Theory, vol.
50 (correspondence), pp.
2178-2185, 2004.
Abstract:
The two main criteria evaluating, from cryptographic viewpoint,
the complexity of Boolean functions are the nonlinearity and the
algebraic degree. Two other criteria can also be considered: the
algebraic thickness and the non-normality. We give simple proofs that,
asymptotically, almost all Boolean functions have high algebraic
thicknesses and are deeply non-normal, as well as they have
high algebraic degrees and high nonlinearities. We also study in detail
the relationship between non-normality and nonlinearity. We
derive simple proofs of known results on symmetric Boolean
functions and we prove several new and more general results on a
class containing all symmetric functions.
21) ``Normal Extensions of Bent Functions", C. Carlet, H. Dobbertin and
G. Leander. IEEE Transactions on Information Theory, vol. 50
(correspondence), pp.
2873-2879, 2004.
Abstract:
The notion of a normal extension is introduced for bent functions,
i.e. maximally non-linear Boolean functions. We apply this concept to
characterize when the direct sum of bent functions is normal, and we
prove that the direct sum of a normal and a non-normal bent function is
always non-normal.
22) ``Cubic Boolean functions with highest resiliency", C. Carlet, and
P. Charpin. IEEE Transactions on Information Theory, vol. 51 (regular
paper), pp.
562-571, 2005.
Abstract:
We classify those cubic m-variable Boolean functions which are
(m-4)-resilient. We prove that there are four types of such
functions, depending on the stucture of the support of their Walsh
spectra. We are able to determine, for each type, the Walsh spectrum
and, then, the nonlinearity of the corresponding functions. We
also give the dimension of their linear space. This dimension equals
m-k where k=3 for the first type, k=4 for the
second type, k=5 for the third type and 5<= k<= 9
for the fourth type.
23) "Hyper-bent functions and cyclic codes", C. Carlet and P. Gaborit.
Journal of Combinatorial Theory, Series A 113, no. 3, pp. 466-482, 2006.
Abstract:
Bent functions are those Boolean functions whose Hamming distance to
the Reed-Muller code of order 1 equals 2^{n-1}- 2^{n/2-1}
(where the number n of variables is even). These combinatorial
objects, with fascinating properties, are rare. Few constructions
are known, and it is difficult to know whether the bent functions they
produce are peculiar or not, since no way of generating at random bent
functions on 8 variables or more is known.
24) "Linear Codes from Perfect Nonlinear Mappings and their
Secret
Sharing Schemes", C. Carlet, C. Ding and J. Yuan.
IEEE
Transactions on Information Theory 51 (regular paper), pp.
2089-2103, 2005.
Abstract:
In this paper, error correcting codes from perfect nonlinear
mappings are constructed, and then employed to construct secret sharing
schemes. The error correcting codes obtained in this paper are
very good in general, and many of them are optimal or almost
optimal. The secret sharing schemes obtained in this paper have two
types of access structures. The first type is democratic in the sense
that every participant is involved in the same number of minimal access
sets. In the second type of access structures, there are a few
dictators who are in every minimal access set, while each of the
remaining participants is in the same number of minimal access
sets.
25) "Piecewise Constructions of Bent and Almost Optimal Boolean
Functions", C. Carlet and J. L. Yucas. Designs, Codes and Cryptography, vol. 37,
No 3, pp. 449-464, 2005.
Abstract:
The first aim of this work was to generalize the techniques used in
MacWilliams' and Sloane's presentation of the Kerdock code and develop
a theory of piecewise quadratic Boolean functions. This generalization
led us to construct large families of potentially new bent and
almost optimal functions from quadratic forms in this piecewise
fashion. We show how our motivating example, the Kerdock code, fits
into this setting. These constructions were further generalized to
non-quadratic bent functions. The resulting constructions design
n-variable bent (resp. almost optimal) functions from n-variable
bent or almost optimal functions.
26) ``Construction of bent functions via Niho power functions", H.
Dobbertin, G. Leander, A. Canteaut, C. Carlet, P. Felke and P. Gaborit.
Journal of Combinatorial Theory, Series A, Volume 113, Issue 5,
pp. 779-798, 2006.
Abstract:
A Boolean function with an even number $n=2k$ of variables is called
bent if it is maximally nonlinear. We present here a new construction
of bent functions. Boolean functions of the form $f(x) = \tr(\alpha_1
x^{d_1} + \alpha_2 x^{d_2})$, $\alpha_1, \alpha_2, x \in \F_{2^n}$, are
considered, where the exponents $d_i$ ($i=1, 2$) are of Niho type, i.e.
the restriction of $x^{d_i}$ on $\F_{2^k}$ is linear. We prove
for several pairs of $(d_1,d_2)$ that $f$ is a bent function, when
$\alpha_1$ and $\alpha_2$ fulfill certain conditions. To derive these
results we develop a new method to prove that certain rational mappings
on $\F_{2^n}$ are bijective.
27) Nonlinearities of S-boxes, C. Carlet and C. Ding. Finite Fields and
Their Applications, Vol. 13 Issue 1, pp. 121-135, January 2007.
Abstract:
We introduce an indicator of the non-balancedness of functions
defined over Abelian groups, and deduce a new indicator, denoted
by $NB$, of the nonlinearity of such functions. We prove an
inequality relating $NB$ and the classical indicator $NL$, introduced
by Nyberg and studied
by Chabaud and Vaudenay, of the nonlinearity of S-boxes. This
inequality results
in an upper
bound on $NL$ which unifies Sidelnikov-Chabaud-Vaudenay's bound and
the
covering radius bound. We also deduce from bounds on linear codes three
new bounds on
$NL$ that improve upon Sidelnikov-Chabaud-Vaudenay's bound and the
covering radius bound in many cases.
28) The Weight Distribution of a Class of Linear Codes from Perfect
Nonlinear Functions, J. Yuan, C. Carlet and C. Ding. IEEE
Transactions on Information Theory, vol. 52, no. 2 (correspondence),
pp. 712-717, 2006.
Abstract:
In this correspondence, the weight distribution of a class of linear
codes based on perfect nonlinear functions (also called planar
functions) is
determined. The class of linear codes under study are either optimal or
among the best
codes known, and have nice applications in cryptography.
29) Authentication Schemes from Highly Nonlinear Functions, C. Carlet,
C. Ding and H. Niederreiter. Designs, Codes and Cryptography 40, pp. 71
- 79, 2006.
Abstract:
We construct two families of authentication schemes using highly
nonlinear functions on finite fields of characteristic 2. This leads to
improvements on an earlier construction by Ding and Niederreiter
if one chooses, for instance, an almost bent function as the highly
nonlinear function.
30) New Classes of Almost Bent and Almost Perfect Nonlinear
Polynomials. L. Budaghyan, C. Carlet and A. Pott. IEEE
Transactions on Information Theory, vol. 52 (regular paper), pp.
1141-1152, 2006.
Abstract:
New infinite classes of almost bent and almost perfect nonlinear
polynomials are constructed. It is shown that they are affine
inequivalent to any sum of a power function and an affine function.
31) Algebraic Immunity for Cryptographically Significant Boolean
Functions: Analysis and Construction. C. Carlet, D. Dalai, K. Gupta and
S. Maitra. IEEE Transactions on Information Theory 52 (regular paper),
pp. 3105-3121,
2006.
Abstract:
Recently, algebraic attacks have received a lot of attention in
cryptographic literature. It has been observed that a Boolean function
$f$ used as a cryptographic primitive, and interpreted as a
multivariate polynomial over $F_2$, should not have low degree
multiples obtained by multiplication with low degree nonzero functions.
In this paper, we show that a Boolean function having low nonlinearity
is (also) weak against algebraic attacks, and we extend this result to
higher order nonlinearities. Next, we present enumeration results on
linearly independent annihilators. We also study certain classes of
highly nonlinear resilient Boolean functions for their
algebraic immunity. We identify that functions having low
degreesubfunctions are weak in terms of algebraic immunity, and we
analyse some existing constructions from this viewpoint. Further, we
present a
construction method to generate Boolean functions on $n$ variables with
highest possible algebraic immunity $\lceil \frac{n}{2} \rceil$ (this
construction, first presented at FSE 2005, has been originally the
first one producing such functions). These functions are obtained
through a doubly indexed recursive relation. We calculate their
Hamming weights and deduce their nonlinearities; we show that they have
very high algebraic degrees. We express them as the sums of two
functions which can be obtained from simple symmetric functions by a
transformation which can be implemented with an algorithm whose
complexity is linear in the number of variables. We deduce a very fast
way of computing the output to these functions, given their input.
32) Improving the upper bounds on the covering radii of binary
Reed-Muller codes. C. Carlet and S. Mesnager. IEEE
Transactions on Information Theory 53 (regular paper), pp. 162-173,
2007.
Abstract:
By deriving bounds on character sums of Boolean functions and by using
the characterizations, due to Kasami and Tokura, of those elements of
the Reed-Muller codes whose Hamming weights are smaller than twice and
a half the minimum distance, we derive an improved upper bound on the
covering radius of the Reed-Muller code of order $2$, and we deduce
improved upper bounds on the covering radii of the Reed-Muller codes of
higher orders.
33) On an Improved Correlation Analysis of Stream Ciphers Using
Muti-Output Boolean Functions and the Related Generalized Notion of
Nonlinearity. C. Carlet, K. Khoo, C.-W. Lim and C.-W. Loe. Advances in
Mathematics of Communications, Vol. 2, No. 2, pp. 201-221, May 2008.
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.
34) Recursive lower bounds on the nonlinearity profile of Boolean
functions and their applications. C. Carlet. IEEE Transactions on
Information Theory (regular paper). Volume 54, Issue 3, pp. 1262 -
1272, 2008.
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.
35) Classes of Quadratic APN Trinomials and Hexanomials and Related
Structures. L. Budaghyan and C. Carlet. IEEE Transactions on
Information Theory (regular paper) 54, Issue 5, pp. 2354-2357, 2008.
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 $F_{2^{2m}}$ to $F_{2^{2m}}$. We
check for $m=3$ that some of these functions are CCZ-inequivalent to
power functions.
36) Two classes of quadratic APN binomials inequivalent to power
functions. L. Budaghyan, C. Carlet and G. Leander. IEEE
Transactions on Information Theory, vol. 54 (regular paper), pp.
4218-4229, 2008.
Abstract:
This paper introduces the first found infinite classes of almost
perfect nonlinear (APN) polynomials which are CCZ-inequivalent to power
functions. These are two classes of APN binomials from $F_{2^n}$
to $F_{2^n}$ (for $n$ divisible by 3, resp. 4). We prove that these
functions are EA-inequivalent to any power
function and that they are CCZ-inequivalent to the Gold, Kasami,
inverse and Dobbertin functions when $n\ge12$. This means that for $n$
even they are CCZ-inequivalent to any known APN function. In particular
for $n=12,20,24$, they are therefore CCZ-inequivalent to any power
function.
37) Constructing new APN functions from known ones. L. Budaghyan, C.
Carlet and G. Leander. Finite Fields and Applications 15(2), Pages
150-159, 2009.
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 in the case $n=7$ it is CCZ-inequivalent to
any
power mapping (and, therefore, to any APN function from the
previously
known families of APN mappings).
38) Further properties of several
classes of Boolean functions with optimum algebraic immunity. C.
Carlet, X. Zeng, C. Li and L. Hu. Designs,
Codes and Cryptography, Volume 52 , Issue 3, pp. 303 - 338, 2009.
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 $\Delta(x)$ is a
polynomial described in Theorem \ref{thm8}. The algebraic of some
constructed functions is also discussed.
39) On the construction of bent vectorial
functions. C. Carlet. and S. Mesnager. Special Issue of the
International
Journal of Information and Coding Theory (IJICoT), Vol. 1, no 2,
dedicated to Vera
Pless, pp. 133-148, 2010.
Abstract:
This paper is devoted to the constructions of bent vectorial functions,
that is, maximally nonlinear multi-output Boolean functions. Such
functions contribute to an optimal resistance to both linear and
differential attacks of those cryptosystems in which they are involved
as substitution boxes (S-boxes). We survey, study more in details and
generalize the known primary and secondary constructions of bent
functions, and we introduce new ones.
40) Self-dual
bent
functions. C. Carlet, L. E. Danielsen, M. Parker and P.
Solé. Special Issue of the International Journal
of Information and Coding Theory (IJICoT) dedicated to Vera
Pless, Volume 1, No. 4, pp. 384-399, 2010 (a
preliminary version appeared in the proceedings of the BFCA'08
conference).
Abstract:
A bent function is called self-dual if it is equal to its
dual. It is called anti-self-dual if it is equal to the complement of
its dual. A spectral
characterization in terms of the Rayleigh quotient of the Sylvester
Hadamard matrix is derived. Bounds on the
Rayleigh quotient are given for Boolean functions in an odd number of
variables. An efficient search
algorithm based on the spectrum of the Sylvester matrix is derived.
Primary and secondary constructions
are given. All self-dual bent Boolean functions in $\le 6$
variables and all quadratic such functions in $8$ variables are
given, up to a restricted form of affine
equivalence.
41) Relating three nonlinearity parameters of vectorial
functions and building APN functions from bent. Designs,
Codes and Cryptography. C. Carlet. Vol. 59, No. 1, Page 89--109, 2011.
Abstract:
We survey the properties of two parameters introduced by C. Ding and
the author for quantifying the balancedness of vectorial functions and
of their derivatives. We give new results on the distribution of the
values of the first parameter when applied to $F+L$, where $F$ is a
fixed function and $L$ ranges over the set of linear functions: we show
an upper bound on the nonlinearity of $F$ by means of these values, we
determine the mean of the values and we show that their maximum is a
nonlinearity parameter as well, we prove that the variance of these
values is directly related to the second parameter. \\
We briefly recall the known constructions of bent vectorial functions
and introduce two new classes obtained with Gregor Leander. We show
that bent functions can be used to build APN functions by
concatenating the outputs of a bent $(n,n/2)$-function and of some
other $(n,n/2)$-function. We obtain this way a general infinite
class of quadratic APN functions. We show that this class contains the
APN trinomials and hexanomials introduced in 2008 by L. Budaghyan and
the author, and a class of APN functions introduced, in 2008 also, by
Bracken et al.; this gives an explanation of the APNness of these
functions and allows generalizing them. We also obtain this way the
recently found Edel-Pott cubic function. We exhibit a large number of
other sub-classes of APN functions. We eventually design with this same
method classes of quadratic and non-quadratic differentially 4-uniform
functions.
42) CCZ-equivalence of Bent Vectorial
Functions and Related Constructions. L. Budaghyan and C. Carlet.
Designs, Codes and Cryptography, Vol. 59, No. 1-3 , pp. 69-87, 2011.
Abstract:
We observe that the CCZ-equivalence of bent vectorial functions
over F_2^n (n even) reduces to their EA-equivalence. Then we show
that in spite of this fact, CCZ-equivalence can be used for
constructing bent functions which are new up to EA-equivalence and
therefore to CCZ-equivalence: applying CCZ-equivalence to a
non-bent vectorial function $F$ which has some bent components, we get
a function $F'$ which also has some bent components and whose bent
components are CCZ-inequivalent to the components of the original
function $F$. Using this approach we construct classes of nonquadratic
bent Boolean and bent vectorial functions.
43) Comment on ``Constructions of Cryptographically Significant Boolean
Functions Using Primitive Polynomials". C. Carlet. IEEE Transactions
on Information Theory Vol. 57, no. 7, pp. 4852 - 4853 , 2011
Abstract:
We show that the first of the two constructions by Q. Wang, J. Peng, H.
Kan and X. Xue in IEEE Trans. on Inf. Th., vol 56, no 6, 2010, of
Boolean functions provably satisfying the main criteria for filter
functions in stream ciphers, is the same as the construction studied by
the author and K. Feng at Asiacrypt 2008. We observe that the bounds
shown on the nonlinearities of the functions in this IEEE paper are
similar to those shown in the Asiacrypt paper. We point out that all
these functions can be implemented in a more efficient way than usually
believed.
44) X. Zeng, C. Carlet, L. Hu and J. Shan. More Balanced Boolean
Functions with Optimal Algebraic Immunity, and Good Nonlinearity and
Resistance to Fast Algebraic Attacks. IEEE Transactions on
Information Theory, Vol. 57, pp. 6310-6320, 2011.
Abstract:
In this paper, three constructions of balanced Boolean functions with
optimal algebraic immunity are proposed. It is checked that, at least
for small numbers of input variables, these functions have good
behavior against fast algebraic attacks as well. Other cryptographic
properties such as algebraic degree and nonlinearity of the constructed
functions are also analyzed. Lower bounds on the nonlinearity are
proved, which are similar to the best bounds obtained for known Boolean
functions resisting algebraic attacks and fast algebraic attacks.
Moreover, it is checked that for the number $n$ of variables with
$5\leq n\leq 19$, the proposed $n$-variable Boolean functions have in
fact very good nonlinearity.
45) C. Carlet and S. Mesnager. On Dillon's class H of bent functions,
Niho bent functions and o-polynomials. Journal of Combinatorial
Theory, Series A 118, pp. 2392-2410, 2011.
Abstract:
One of the classes of bent Boolean functions introduced by John Dillon
in his thesis is family $H$. While this class corresponds to a nice
original construction of bent functions in bivariate form, Dillon could
exhibit in it only functions which already belonged to the well-known
Maiorana-McFarland class. We first notice that $H$ can be extended to
a slightly larger class that we denote by ${\cal H}$. We observe
that the bent functions constructed via Niho power functions,
which four examples are known, due to Dobbertin et al. and to
Leander-Kholosha, are the univariate form of the functions of class
${\cal H}$. Their restrictions to the vector spaces $u\GF {n/2}$, $u\in
\GF n^\star$, are linear. We also characterize the bent functions
whose restrictions to the $u\GF {n/2}$'s are affine. We answer the open
question raised by Dobbertin et al. in JCT A 2006 on whether the duals
of the Niho bent functions introduced in the paper are affinely
equivalent to them, by explicitely calculating the dual of one of these
functions. We observe that this Niho function also belongs to the
Maiorana-McFarland class, which brings us back to the problem of
knowing whether $H$ (or ${\cal H}$) is a subclass of the
Maiorana-McFarland completed class. We then show that the condition for
a function in bivariate form to belong to class ${\cal H}$ is
equivalent to the fact that a polynomial directly related to its
definition is an o-polynomial (oval polynomial, a notion from finite
geometry)). Thanks to the existence in the literature of 8 classes of
nonlinear o-polynomials, we deduce a large number of new cases of bent
functions in ${\cal H}$, which are potentially affinely inequivalent to
known bent functions (in particular, to Maiorana-McFarland's functions).
46) C. Carlet. More vectorial Boolean functions with unbounded
nonlinearity profile. Special Issue on Cryptography of International
Journal of Foundations of Computer Science 22 (6), pp. 1259-1269, 2011.
Abstract:
The nonlinearity profile of Boolean functions is a generalization of
the most important cryptographic criterion, called the (first order)
nonlinearity. It is defined as the sequence of the minimum Hamming
distances $nl_r(f)$ between a given Boolean function $f$ and all
Boolean functions in the same number of variables and of degrees at
most $r$, for $r\geq 1$. This parameter, which has a close relationship
with the Gowers norm, quantifies the resistance to cryptanalyses by low
degree approximations of stream ciphers using the Boolean function $f$
as combiner or as filter. The nonlinearity profile can also be
defined for vectorial functions: it is the sequence of the
minimum Hamming distances between the component functions of the
vectorial function and all Boolean functions of degrees at most $r$,
for $r\geq 1$. The nonlinearity profile of the multiplicative inverse
functions has been lower bounded in a previous paper by the same
author. No other example of an infinite class of functions with
unbounded nonlinearity profile has been exhibited since then. In this
paper, we lower bound the whole nonlinearity profile of the (simplest)
Dillon bent function $(x,y)\mapsto xy^{2^{n/2}-2}$, $x,y\in
F_{2^{n/2}}$ and we exhibit another class of functions for which
bounding the whole profile of each of them comes down to bounding the
first order nonlinearities of all functions.
47) C. Carlet, J.C. Ku-Cauich and H. Tapia-Recillas. Bent Functions on a
Galois Ring and Systematic Authentication Codes. Advances
in Mathematics of Communications, Volume 6, Number 2, pp.
249–258, 2012.
Abstract:
A class of bent functions on a Galois ring is introduced and based on
these functions systematic authentication codes are presented.
48) C. Carlet and S. Mesnager. On Semi-bent Boolean Functions.
IEEE Transactions on Information Theory, Vol. 58, no. 5, pp. 3287-3292,
2012.
Abstract:
We show that any Boolean function, in even dimension, equal to the sum
of a Boolean function $g$ which is constant on each element of a spread
and of a Boolean function $h$ whose restrictions to these
elements are all linear, is semi-bent if and only if $g$ and $h$
are both bent. We deduce a large number of infinite classes
of semi-bent functions in explicit bivariate (resp. univariate)
polynomial form.
49) C. Carlet, J.-C. Faugère, C. Goyet and G. Renault.
Analysis of the Algebraic Side Channel Attack. Journal of
Cryptographic Engineering (JCEN) Vol. 2, no. 1, pp. 45-62, 2012.
Abstract:
At CHES 2009, Renauld, Standaert and Veyrat-Charvillon introduced a new
kind of attack called Algebraic Side-Channel Attacks (ASCA). They
showed that side-channel information leads to effective algebraic
attacks. These results are mostly experiments strongly based on a the
use of a SAT-solver. This article presents a theoretical study in order
to explain and to characterize the algebraic phase of these attacks. We
study more general algebraic attacks based on Gröbner methods. We
show that the complexity of the Gröbner basis computations in
these attacks depends on a new notion of algebraic immunity defined in
this paper, and on the distribution of the leakage information of the
cryptosystem. We also study two examples of common leakage models: the
Hamming weight and the Hamming distance models. For instance the study
in the case of the Hamming weight model gives that the probability of
obtaining at least 64 (resp. 130) linear relations is about 50% for the
substitution layer of PRESENT (resp. AES). Moreover if the S-boxes are
replaced by functions maximizing the new algebraic immunity criterion
then the algebraic attacks (Gröbner and SAT) are intractable. From
this theoretical study, we also deduce an invariant which can be easily
computed from a given S-Box and provides a sucient condition of
weakness under an ASCA. This new invariant does not require any
sophisticated algebraic techniques to be defined and computed. Thus,
for cryptographic engineers without an advanced knowledge in algebra
(e.g. Gröbner basis techniques), this invariant may represent an
interesting tool for rejecting weak S-boxes.
50) C. Carlet, F. Zhang and Y. Hu. Secondary constructions of
bent functions and their enforcement. Advances in
Mathematics of Communications (AMC) Volume 6,Number 3, pp. 305 - 314,
2012.
Abstract:
Thirty years ago, Rothaus introduced the notion of bent function and
presented a secondary construction (building new bent functions from
already defined ones), which is now called the Rothaus' construction.
This construction has a strict requirement for its initial functions.
In this paper, we first concentrate on the design of the initial
functions in the Rothaus construction. We show how to
construct Maiorana-McFarland's (M-M) bent functions, which can
then be used as initial functions, from Boolean permutations and
orthomorphic permutations. We deduce that at least $(2^n!\times
2^{2^n})(2^{2^n}\times2^{2^{n-1}})^2$ bent functions in $2n+2$
variables can be constructed by using Rothaus' construction. In the
second part of the note, we present a new secondary construction of
bent functions which generalizes the Rothaus construction. This
construction requires initial functions with stronger conditions; we
give examples of functions satisfying them. Further, we generalize the
new secondary construction of bent functions and illustrate it with
examples.
51) G. Gao, X. Zhang, W. Liu and C. Carlet.
Constructions of Quadratic and Cubic Rotation Symmetric Bent Functions.
IEEE Transactions on Information Theory, Vol. 58, no. 7, pp. 4908-4913,
2012.
Abstract:
In this paper, we consider constructions of quadratic and cubic
rotation symmetric bent functions, which are of the forms
f_{c}(x)=\sum_{i=1}^{m-1}c_{i}(\sum_{j=0}^{n-1}x_jx_{i+j})+c_m(\sum_{j=0}^{m-1}x_jx_{m+j})
and
f_t(x)=\sum_{i=0}^{n-1}(x_ix_{t+i}x_{m+i}+x_{i}x_{t+i})+\sum_{i=0}^{m-1}x_{i}x_{m+i},
where n=2m, c=(c_1, c_2,..., c_m) with c_i in {0,1} for
1\leq i \leq m and 0<t<m (the subscript u of x_u in the
expressions of f_c(x) and f_t(x) is taken as u modulo n).
For each case, a necessary and sufficient condition is obtained.
To the best of our knowledge, this class of cubic rotation symmetric
bent functions is the first example of an infinite class of
nonquadratic rotation symmetric bent functions.
52) C. Carlet, P. Gaborit, J.-L. Kim and P. Solé. A new class of
codes for Boolean masking of cryptographic computations. IEEE
Transactions on Information Theory, Vol. 58 No. 9, pp. 6000-6011,
2012.
Abstract:
We introduce a new class of rate one-half binary codes: complementary
information set codes. A binary linear code of length 2n and dimension
n is called a complementary information set code (CIS code for short)
if it has two disjoint information sets. This class of codes contains
self-dual codes as a subclass. It is connected to graph correlation
immune Boolean functions of use in the security of hardware
implementations of cryptographic primitives.
Such codes permit to improve the cost of masking cryptographic
algorithms against side channel attacks.
In this paper we investigate this new class of codes: we give optimal
or best known CIS codes of length <132. We derive general
constructions based on cyclic codes and on double circulant codes. We
derive a Varshamov-Gilbert bound for long CIS codes, and show that they
can all be classified in small lengths \le 12 by the building up
construction. Some nonlinear permutations are constructed by using
Z_4-codes, based on the notion of dual distance of a possibly nonlinear
code.
53) D. Tang, C. Carlet and X. Tang. On the Second-Order Nonlinearities
of Some Bent Functions. Information Sciences (Elsevier) 223; pp.
322-330, 2013.
Abstract:
The rth-order nonlinearity of Boolean functions plays a central role
against several known attacks on stream and block ciphers. It plays
also an important role in coding theory, since its maximum equals the
covering radius of the rth-order Reed-Muller code. But it is difficult to
calculate and even to bound. In this paper, we show lower bounds on the
second-order nonlinearity of two subclasses of well-known bent
functions. We first improve a known lower bound on the second-order
nonlinearity of the simplest partial spread bent functions, whose
nonlinearity profile has
been bounded from below by the second author. This improvement allows
improving the bound for the whole profile.
We subsequently give a lower bound on the second-order nonlinearity of
some infinite class of Maiorana-McFarland (M-M) bent functions, which
generalizes a result by Gangopadhyay et. al.
54) L. Budaghyan, C. Carlet, T. Helleseth, A. Kholosha and S. Mesnager.
Further Results on Niho Bent Functions. IEEE Transactions
on Information Theory 58 no. 11, pp. 6979-6985, 2012.
Abstract:
Computed is the dual of the Niho bent function consisting of $2^r$
exponents that was found by Leander and Kholosha. The algebraic degree
of the dual is calculated and it is shown that this new bent function
is not of the Niho type. Finally, the aforecited and two other infinite
classes of Niho bent functions are analyzed for their relation to the
completed Maiorana-McFarland class. In particular, it
is proven that two families of Niho bent functions do not belong to the
completed Maiorana-McFarland class. The latter result gives a positive
answer to an open problem whether one of the classes of bent functions
introduced by Dillon in his thesis of 1974, differs from the completed
Maiorana-McFarland class.
55) D. Tang, C. Carlet and X. Tang. Highly Nonlinear Boolean
Functions with Optimal Algebraic Immunity and Good Behavior
Against Fast Algebraic Attacks. IEEE Transactions on
Information Theory 59 (1), pp. 653-664, 2013.
Abstract:
Inspired by the previous work of Tu and Deng, we propose two infinite
classes of Boolean functions of 2k variables where k\ge 2. The first
class contains unbalanced functions having high algebraic degree and
nonlinearity. The functions in the second one are balanced and have
maximal algebraic degree and high nonlinearity (as shown by a lower
bound that we prove; as a by-product we also prove a better lower bound
on the nonlinearity of the Carlet-Feng function). Thanks to a
combinatorial fact, first conjectured by the authors and later proved
by Cohen and Flori, we are able to show that they both possess optimal
algebraic immunity. It is also checked that, at least for numbers of
variables n\leq 16, functions in both classes have a good behavior
against fast algebraic attacks. Compared with the known Boolean
functions resisting algebraic attacks and fast algebraic attacks, both
of them possess the highest lower bounds on nonlinearity. These bounds
are however not enough for ensuring a sufficient nonlinearity for
allowing resistance to fast correlation attack. Nevertheless, as for
previously found functions with the same features, there is a gap
between the bound that we can prove and the actual values computed for
bounded numbers of variables ($n\leq 38$). Moreover, these values are
very good. The infinite class of functions we propose in Construction 2
presents, among all currently known constructions, the best provable
trade-off between all the important cryptographic criteria.
56) C. Carlet. More constructions of APN and differentially 4-uniform
functions by concatenation. Science China Mathematics, Vol. 56
Issue (7), pp. 1373-1384, 2013.
Abstract:
We study further the method of concatenating the outputs of two
functions for designing an APN or a differentially 4-uniform
$(n,n)$-function for every even $n$. We deduce several specific
constructions of APN or differentially 4-uniform $(n,n)$-functions from
APN and differentially 4-uniform $(n/2,n/2)$-functions. We also give a
construction of quadratic APN functions which includes as particular
cases a previous construction by the author and a more recent
construction by Pott and Zhou.
57) C. Carlet and B. Merabet. Asymptotic lower bound on the algebraic
immunity of random balanced multi-output Boolean functions. Advances in
Mathematics of Communications, Vol. 7, Issue 2, pp. 197 -
217, May 2013.
Abstract:
This paper extends the work of F. Didier (IEEE Transactions on
Information Theory, Vol. 52(10): 4496–4503, October 2006) on the
algebraic immunity of random balanced Boolean functions, into an
asymptotic lower bound on the algebraic immunity of random balanced
multi-output Boolean functions.
58) C. Carlet, J.-L. Danger S. Guilley, H. Maghrebi and E.
Prouff.
Achieving side-channel high-order correlation immunity with Leakage
Squeezing. Journal of Cryptographic Engineering (JCEN) 4(2), pp. 107-121, 2014.
Abstract:
This article deeply analyses high-order (HO) Boolean masking
countermeasures against side-channel attacks in contexts where the
shares are manipulated simultaneously. The relationship between the
leakage characteristics and the attack efficiency is focused, leading
to the introduction of the notion of HO-CPA immunity as a metric to
characterize a leakage function. Our main contribution is to link the
minimum attack order (called HO-CPA immunity) to the amount of
information leaked. Interestingly, the HO-CPA immunity can be much
larger than the number of shares in the mask- ing scheme. This is made
possible by the leakage squeezing. It is an optimization of the
straightforward Boolean masking where masks are recoded relevantly by
bijections. This technique, and others from the state-of-the-art, are
overviewed, and put in perspective. We show that this notion intervenes
to assess both the resistance against HO-CPA attacks and the amount of
leakage. Then, we describe the technique of leakage squeezing. Our main
contribution is to show that this new technique enables to increase the
HO-CPA immunity of a masking countermeasure at the cost of a negligible
timing/memory overhead.
59) Q.Wang, C. Carlet, P. Stanica and Chik How Tan. Cryptographic
Properties of the Hidden Weighted Bit Function. Discrete Applied
Mathematics 174, pp. 1-10, 2014.
Abstract:
The hidden weighted bit function (HWBF), introduced by R. Bryant in
IEEE Trans. Comp. 40 and revisited by D. Knuth in Vol. 4 of The Art of
Computer Programming, is a function that seems to be the simplest
one with exponential Binary Decision Diagram (BDD) size. This
property is interesting from a cryptographic viewpoint since BDD based
attacks are receiving more attention in the cryptographic community.
But, to be usable in stream ciphers, the functions must also satisfy
all the other main criteria. In this paper, we investigate the
cryptographic properties of the HWBF and prove that it is balanced,
with optimum algebraic degree and satisfies the strict avalanche
criterion. We calculate its exact nonlinearity and give a lower bound
on its algebraic immunity. Moreover, we investigate its normality and
its resistance against fast algebraic attacks. The HWBF is simple, can
be implemented efficiently, has a high BDD size and rather good
cryptographic properties, if we take into account that its number of
variables can be much larger than for other functions with the same
implementation efficiency. Therefore, the HWBF is a good candidate for
being used in real ciphers. Indeed, contrary to the case of symmetric
functions, which allow such fast implementation but also offer to the
attacker some specific possibilities due to their symmetry, its
structure is not suspected to be related to such dedicated attacks.
60) C. Carlet and A. Klapper. On the Arithmetic Walsh Coefficients of
Boolean Functions. Designs, Codes and Cryptography, Volume 73, Issue 2, pp. 299-318, 2014.
Abstract:
We generalize to the arithmetic Walsh transform (AWT) some results
which were previously known for the Walsh Hadamard transform of Boolean
functions. We first generalize the classical Poisson summation formula
to the AWT. We then define a generalized notion of resilience
with respect to an arbitrary statistical measure of Boolean functions.
We apply the Poisson summation formula to obtain a condition equivalent
to resilience for one such statistical measure. Last, we
show that the AWT of a large class of Boolean functions can be
expressed in terms of the AWT of a Boolean function of algebraic
degree at most 3 in a larger number of variables.
61) J. Li, C. Carlet, X. Zeng and C. Li. Two constructions of balanced
Boolean functions with optimal algebraic immunity, high nonlinearity and
good behavior against fast algebraic attacks. Designs
Codes and
Cryptography 76 (2), pp. 279-305, 2015.
Abstract:
In this paper, two constructions of Boolean functions with optimal
algebraic immunity are proposed. They generalize previous ones
respectively given by Rizomiliotis and Zeng et al., and some new
functions with desired properties are obtained. The functions
constructed in this paper can be balanced and have optimal algebraic
degree. Further, a new lower bound on the nonlinearity of the proposed
functions is established, and as a special case, it gives a new lower
bound on the nonlinearity of the Carlet-Feng functions, which is
slightly better than the best previously known ones. For $n\leq 19$, the
numerical results reveal that among the constructed functions in this
paper, there always exist some functions with nonlinearity higher than
or equal to that of the Carlet-Feng functions. These functions are also
checked to have good behavior against fast algebraic attacks at least
for small numbers of input variables.
62) C. Carlet, J.-L. Danger, S. Guilley and H. Maghrebi. Leakage
Squeezing: Optimal Implementation and Security Evaluation. Journal of Mathematical Cryptology 8(3), pp. 249-295, 2014.
Abstract:
Hardware devices can be protected against side-channel at- tacks by
introducing one random mask per sensitive variable. The computation
throughout is unaltered if the shares (masked variable and mask) are
processed concomitantly, in two distinct registers. Nonetheless, this
setup can still be attacked if the side-channel is squared, because this
operation causes an interference between the two shares. This more so-
phisticated analysis is referred to as a zero-offset second-order
correla- tion power analysis (CPA) attack. When the device leaks in
Hamming distance, the countermeasure can be improved by the “leakage
squeezing”. It consists in manipulating the mask through a bijection,
aimed at reducing the dependency between the shares’ leakage. Thus
dth-order zero-offset attacks, that consist in applying CPA on the dth
power of the centered side-channel traces, can be thwarted for d ≥ 2 at
no extra cost. We denote by n the size in bits of the shares and call F
the trans- formation function, that is a bijection of F_2^n . In this
paper, we explore the functions F that thwart zero-offset high-order CPA
(HO-CPA) of maximal order d. We mathematically demonstrate that optimal
choices for F relate to optimal binary codes (in the sense of
communication theory). First, we exhibit optimal linear F functions.
They are suitable for masking schemes where only one mask is used
throughout the algo- rithm. Second, we note that for values of n for
which non-linear codes exist with better parameters than linear ones,
better protection levels can be obtained. This applies to
implementations in which each mask is randomly cast independently of the
previous ones. These results are exemplified in the case n = 8, where
the optimal F can be identified: it is derived from the optimal rate 1/2
binary code of size 2n, namely the Nordstrom-Robinson (16, 256, 6)
code. This example provides explicitly with the optimal protection that
limits to one mask of byte-oriented algo- rithms such as AES or
AES-based SHA-3 candidates. It protects against all zero-offset HO-CPA
attacks of order d ≤ 5. Eventually, the counter- measure is shown to be
resilient to imperfect leakage models, where the registers leak
differently than the sum of their toggling bits.
63) C. Carlet, G. Gao and W. Liu. A secondary construction and a
transformation on rotation symmetric functions, and their action on bent
and semi-bent functions. Journal of Combinatorial Theory, Series A, vol 127, issue 1, pp. 161 - 175, 2014.
Abstract:
We study more in details the relationship between rotation symmetric
(RS) functions and idempotents, in univariate and bivariate
representations, and deduce a construction of bent RS functions from
semi-bent RS functions. We deduce the first infinite classes found of
idempotent and RS bent functions of algebraic degree more than 3. We
introduce a transformation from any RS Boolean function $f$ over
$\GF(2)^n$ into the idempotent Boolean function $f'(z)=f(z,z^2,\ldots
,z^{2^{n-1}})$ over $\GF({2^n})$, leading to another RS Boolean
function. The trace representation of $f'$ is directly
deduced from the algebraic normal form of $f$, but we show that $f$ and
$f'$, which have same algebraic degree, are in general not affinely
equivalent to each other. We exhibit infinite classes of functions $f$
such that (1) $f$ is bent and $f'$ is not (2) $f'$ is bent and $f$ is
not (3) $f$ and $f'$ are both bent (we show that this is always the case
for quadratic functions and we also investigate cubic functions).
64) F. Zhang, C. Carlet, Y. Hu and T. Cao. Secondary constructions of
highly nonlinear Boolean functions and disjoint
spectra plateaued functions. Information Sciences 283, pp. 94-106, 2014.
Abstract:
In this paper, we modify a generalized indirect sum construction to
construct functions with high nonlinearity. By utilizing the
modified construction, highly nonlinear functions in $(n+m)$ variables
can be obtained from known bent functions in $n$ variables and
highly nonlinear functions in $m$ variables. It is possible to
obtain new $(n+15)$-variable functions with nonlinearity $
2^{n+15-1}-2^{(n+15-1)/2}+20\times 2^{n/2}$ and new $12$-variable
$2$-resilient functions with nonlinearity $2000$ and algebraic
degree $8$, which achieve optimal algebraic immunity. Moreover, the
modified construction can also be used as an iterative construction of a
quadruple of disjoint spectra plateaued functions. In
addition, we present sufficient conditions for a quadruple
of disjoint spectra plateaued functions to have no nonzero
linear structures.
65) C. Carlet, F. Freibert, S. Guilley, M. Kiermaier, J.-L. Kim and P.
Solé. Higher-order CIS codes. IEEE Transactions on Information
Theory 60(9), pp. 5283-5295, 2014.
Abstract:
We introduce complementary information set codes of higher-order. A
binary linear code of length $tk$ and dimension $k$ is called a
complementary information set code of order $t$ ($t$-CIS code for short)
if it has $t$ pairwise disjoint information sets. The duals of such
codes permit to reduce the cost of masking cryptographic algorithms
against side-channel attacks.
As in the case of codes for error correction, given the length and the
dimension of a $t$-CIS code, we look for the highest possible minimum
distance. In this paper, this new class of codes is investigated. The
existence of good long CIS codes of order $3$ is derived by a counting
argument. General constructions based on cyclic and quasi-cyclic codes
and on the building up construction are given. A formula similar
to a mass formula is given. A classification of 3-CIS codes of length
$\le 12$ is given. Nonlinear codes better than linear codes are derived
by taking binary images of $\Z_4$-codes. A general algorithm based on
Edmonds' basis packing algorithm from matroid theory is developed with
the following property: given a binary linear code of rate $1/t$ it
either provides $t$ disjoint information sets or proves that the code is
not $t$-CIS. Using this algorithm, all optimal or best known $[tk, k]$
codes where $t=3, 4, \dots, 256$ and $1 \le k \le \lfloor 256/t \rfloor$
are shown to be $t$-CIS for all such $k$ and $t$, except for $t=3$
with $k=44$ and $t=4$ with $k=37$.
66) D. Tang, C. Carlet and X. Tang. A class of 1-Resilient Boolean
Functions with Optimal Algebraic Immunity and Good Behavior
Against Fast Algebraic Attacks. International Journal of
Foundations of Computer Science (IJFCS), Vol. 25, No. 6, pp. 763-780,
2014.
Abstract:
Recently, Tang, Carlet and Tang presented a combinatorial conjecture
about binary strings, allowing proving that all balanced functions in
some infinite class they introduced have optimal algebraic immunity.
Later, Cohen and Flori completely proved that the conjecture is true.
These functions have good (provable or at least observable)
cryptographic properties but they are not 1-resilient, which represents a
drawback for their use as filter functions in stream ciphers. We
propose a construction of an infinite class of 1-resilient Boolean
functions with optimal algebraic immunity by modifying the functions in
this class. The constructed functions have optimal algebraic degree,
that is, meet the Siegenthaler bound, and high nonlinearity. We prove a
lower bound on their nonlinearity, but as for the Carlet-Feng functions
and for the functions mentioned above, this bound is not enough for
ensuring a nonlinearity sufficient for allowing resistance to the fast
correlation attack. Nevertheless, as for previously found functions with
the same features, there is a gap between the bound that we can prove
and the actual values computed for small
numbers of variables. Our computations show that the functions in
this class have very good nonlinearity and also good immunity to fast
algebraic attacks. This is the first time that an infinite class of
functions gathers all of the main criteria allowing these functions to
be used as filters in stream ciphers.
67) C. Carlet and D. Tang. Enhanced Boolean functions suitable for the
filter model of pseudo-random generator. Designs, Codes and
Cryptography 76 (3), pp. 571-587, 2015.
Abstract:
The filter model of pseudo-random generator (in stream ciphers) is
currently the only one for which are known infinite classes of Boolean
functions allowing to resist all the main known attacks. The combiner
model, which is another possible way of using Boolean functions,
requires the same properties as the filter model does, plus one extra
criterion the Boolean function must fulfil: high order resiliency. No
construction of functions is known which ensures all criteria for the
combiner model, even if resiliency is taken in a weakened form, while
such constructions are known for the filter model. But nonlinear
functions used in this model must be in the particular form
$x_n+f(x_1,\dots ,x_{n-1})$ to allow resistance to the distinguishing
attacks for any choice of the tapping sequence. Much work has been done
to construct and study Boolean functions allowing resistance to the main
known attacks (the Berlekamp-Massey and R\o njom-Helleseth attacks,
fast correlation attacks, algebraic attacks and fast algebraic attacks)
on stream ciphers using the filter model. None of the found functions
has the desired form above. Of course, we can take a function in $n-1$
variables and add the extra variable $x_n$ in order to obtain the
desired form, but the algebraic immunity of the resulting function can
be either equal that of the original function $f$ (and it cannot then be
optimal if $n$ is odd) or larger by 1. An increasement by 1
considerably impacts the complexity of algebraic attacks. Moreover,
taking the best known constructions of functions and adapting them to
the desired form result on functions which no longer ensure the best
possible algebraic degree. This represents a gap in the research for
Boolean functions usable in the filter model. In this paper we study the
behavior of the cryptographic characteristics of a function when it is
modified into the desired form and we study constructions of functions
ensuring an optimal or almost-optimal tradeoff between all the necessary
features in this form.
68) D. Tang, C. Carlet and X. Tang. Differentially 4-Uniform Bijections
by Permuting the Inverse Function. Designs, Codes and Cryptography 77(1), pp. 117-141, 2015.
Abstract:
Block ciphers use Substitution boxes (S-boxes) whose aim is to create
confusion into the cryptosystems. Functions used as S-boxes should have
low differential uniformity, high nonlinearity and algebraic degree
larger than 3 (preferably strictly larger). They should be fastly
computable; from this viewpoint, it is better when they are
in even number of variables. In addition, the functions should be
bijections in a Substitution-Permutation Network. Almost perfect
nonlinear (APN) functions have the lowest differential uniformity 2 and
the existence of APN bijections over $\F_{2^n}$ for even $n\ge 8$ is a
big open problem. In the present paper, we focus on constructing
differentially 4-uniform bijections suitable for designing S-boxes for
block ciphers. Based on the idea of permuting the inverse function, we
design a construction providing a large number of differentially
4-uniform bijections with maximum algebraic degree and high
nonlinearity. For every even $n\ge 12$, we mathematically prove that the
functions in a subclass of the constructed class are CCZ-inequivalent
to known differentially 4-uniform power functions and to quadratic
functions. This is the first mathematical proof that an infinite class
of differentially 4-uniform bijections is CCZ-inequivalent to known
differentially 4-uniform power functions and to quadratic functions. We
also get a naive lower bound on the nonlinearity of our functions, which
can be very high in some cases, and obtain three improved lower bounds
on the nonlinearity for three special subcases of functions which are
extremely large.
69) C. Carlet and Y. Al Salami. A New Construction of Differentially
4-uniform $(n,n-1)$-Functions. Advances in Mathematics of Communications, Vol. 9, no. 4, pp. 541 - 565, 2015.
Abstract:
In this paper, a new way to construct differentially 4-uniform
$(n,n-1)$-functions is presented. As APN $(n,n)$-functions, these
functions offer the best resistance against differential cryptanalysis
and they can be used as substitution boxes in block ciphers with a
Feistel structure. Constructing such functions is assumed to be as
difficult as constructing APN $(n,n)$-functions. A function in our
family of functions can be viewed as the concatenation of two APN
$(n-1,n-1)$-functions satisfying some necessary conditions. Then, we
study the special case of this construction in which the two APN
functions differ by an affine function. Within this construction, we
propose a family in which one of the APN functions is a Gold function
which gives the quadratic differentially 4-uniform $(n,n-1)$-function
$(x,x_n)\mapsto x^{2^i+1}+x_n x$ where $x\in F_{2^{n-1}}$ and $x_n\in
F_2$ with $\gcd(i,n-1)=1$. We study the nonlinearity of this function in
the case $i=1$ because in this case we can use results from Carlitz
which are unknown in the general case. We also give the Walsh spectrum
of this function and prove that it is CCZ-inequivalent to functions of
the form $LoF$ where $L$ is an affine surjective $(n,n-1)$-function and
$F$ is a known APN $(n,n)$-function for $n\leq 8$, or the Inverse APN
$(n,n)$-function for every $n$ odd, or any AB $(n,n)$-function for every
$n$ odd, or a {\em Dobbertin} $(n,n)$-function for every $n$ divisible
by 5.
70) C. Carlet. Boolean and vectorial plateaued functions, and APN
functions. IEEE Transactions on Information Theory Vol. 61 no. 11, pp. 6272-6289, 2015.
Abstract:
Boolean plateaued functions and vectorial functions with plateaued
components play a significant role in cryptography, sequences for
communications, and related combinatorics and designs. Our knowledge on
them is not at the level of their importance. We introduce new
characterizations of plateaued Boolean functions. We give
characterizations of vectorial functions whose components are all
plateaued (with possibly different amplitudes), that we simply call
plateaued, by means of the value distributions of their derivatives (we
characterize similarly those functions whose components are
partially-bent), of their autocorrelation functions and of the power
moments of their Walsh transform. This allows us to derive several
characterizations of APN functions in this framework. We prove that all
the main results known for quadratic APN functions extend to plateaued
functions, allowing the study of their APN-ness to be simplified. We
show that if, additionally, the component functions are all unbalanced,
the study is still simpler: the APN-ness of such functions depends only
on their value distribution. This allows proving for instance that any
plateaued $(n,n)$-function, $n$ even, having similar value
distribution as APN power functions, is APN and has same extended Walsh
spectrum as the APN Gold functions.
As by-products, we obtain a few other new results. For instance,
any plateaued function in even dimension which is CCZ-equivalent to a
Gold or Kasami APN function is necessarily EA-equivalent to it.
71) A. De Trano, N. Karimi, R. Karri, X. Guo, C. Carlet and S. Guilley.
Exploiting Small Leakages in Masks to Turn a Second-Order Attack into a
First-Order Attack. The Scientific World Journal, Sept, 2015. Hindawi
Publishing Corporation. DOI 10.1155/2015/743618
Abstract:
Masking countermeasures, used to thwart side-channel at- tacks, have
been shown to be vulnerable to mask-extraction attacks. State-of-the-art
mask-extraction attacks on the Ad- vanced Encryption Standard (AES)
algorithm target S-Box re-computation schemes, but have not been applied
to sce- narios where S-Boxes are precomputed offline. We propose an
attack targeting precomputed S-Boxes stored in non- volatile memory. Our
attack targets AES implemented in software protected by a low entropy
masking scheme and recovers the masks with 91% success rate. Recovering
the secret key requires fewer power traces (in fact, by at least two
orders of magnitude) compared to a classical second order attack.
Moreover, we show that this attack remains viable in a noisy
environment, or with a reduced number of leakage points.
72) C. Carlet, G. Gong and Y. Tan. Quadratic Zero-Difference Balanced
Functions, APN Functions and Strongly Regular Graphs. Designs, Codes and Cryptography Vol. 78 (3), pp. 629-654, 2016.
Abstract:
Let $F$ be a function from $\gf_{p^n}$ to itself and $\delta$ a positive
integer. $F$ is called zero-difference $\delta$-balanced if the
equation $F(x+a)-F(x)=0$ has exactly $\delta$ solutions for all nonzero
$a\in\gf_{p^n}$. As a particular case, all known quadratic planar
functions are zero-difference 1-balanced; and some quadratic APN
functions over $\gf_{2^n}$ are zero-difference 2-balanced. In this
paper, we study the relationship between this notion and differential
uniformity; we show that all quadratic zero-difference $\delta$-balanced
functions are differentially $\delta$-uniform and we investigate in
particular such functions with the form $F=G(x^d)$, where
$\gcd(d,p^n-1)=\delta +1$ and where the restriction of $G$ to the set of
all nonzero $(\delta +1)$-th powers in $\gf_{p^n}$ is an injection. We
introduce new families of zero-difference $p^t$-balanced functions. More
interestingly, we show that the image set of such functions is a
regular partial difference set, and hence yields strongly regular
graphs; this generalizes the constructions of strongly regular graphs
using planar functions by Weng et al. Using recently discovered
quadratic APN functions on $\gf_{2^8}$, we obtain $15$ new $(256, 85,
24, 30)$ negative Latin square type strongly regular graphs.
73) C. Carlet, D. Joyner, P. Stanica and D. Tang. Cryptographic
properties of monotone Boolean functions. J. Mathematical Cryptology Vol. 10 (1), pp. 1-14, 2016.
Abstract:
We prove various results on monotone Boolean functions. In particular,
we prove a conjecture proposed recently, stating that there are no
monotone bent Boolean functions. Further, we give an upper bound on the
nonlinearity of monotone functions, we describe the Walsh--Hadamard
spectrum and investigate some other cryptographic properties of monotone
Boolean functions.
74) C. Carlet and E. Prouff. Polynomial Evaluation and Side Channel
Analysis. Special Volume dedicated to David Kahn. Springer. Ryan, Peter
Y. A., Naccache, David, Quisquater, Jean-Jacques (Eds.) pp. 315-341,
2016.
Abstract:
Side Channel Analysis (SCA) is a class of attacks that exploits leakage
of information from a cryptographic implementation during execution. To
thwart it, masking is a common countermeasure. The principle is to
randomly split every sensitive intermediate variable occurring in the
computation into several shares and the number of shares, called the
{\em masking order}, plays the role of a security parameter. The
main issue while applying masking to protect a block cipher
implementation is to specify an efficient scheme to secure the s-box
computations. Several masking schemes, applicable for arbitrary orders,
have been recently introduced. Most of them follow a similar approach
originally introduced in the paper of Carlet \etal published at FSE
2012; the s-box to protect is viewed as a polynomial and strategies are
investigated which minimize the number of field multiplications which
are not squarings. This paper aims at presenting all these works in a
comprehensive way. The methods are discussed, their differences and
similarities are identified and the remaining open problems are listed.
75) C. Carlet and S. Mesnager. Four decades of research on bent
functions. Special Jubilee Issue of Designs, Codes and Cryptography, Vol. 78, pp. 5-50, 2016.
Abstract:
In this survey, we revisit the Rothaus paper and the chapter of Dillon's
thesis dedicated to bent functions, and we describe the main results
obtained on these functions during these last 40 years. We also
cover more briefly super-classes of Boolean functions, vectorial bent
functions and bent functions in odd characteristic.
76) F. Zhang, C. Carlet, Y. Hu and W. Zhang. New Secondary Constructions
of Bent Functions. AAECC (Journal), Volume 27, Issue 5, pp 413–434, 2016.
Abstract:
In this paper, we first present a novel secondary construction of bent
functions (building new bent functions from two already defined
ones). Furthermore, the algebraic degree and algebraic immunity of
the constructed functions are analysed.
Finally, we apply the construction using as initial
functions some specific bent functions and then specify sufficient
conditions for the resulting bent functions not to be
contained in the completed Maiorana-McFarland class. In the second part
of the paper, we present a corrigendum of ``Constructions of
Bent-Negabent Functions and Their Relation to the Completed
Maiorana-McFarland Class'' IEEE Trans. Inf. Theory, 61 (3),
1496--1506 (2015).
77) L. Budaghyan, A. Kholosha, C. Carlet and T. Helleseth. Univariate
Niho Bent Functions from o-Polynomials. IEEE Transactions
on Information Theory 62 (4), pp. 2254-2265, 2016.
Abstract:
In this paper, we discover that univariate form of a Niho bent function
is a sum of functions having the form of a Leander-Kholosha bent
function taken with particular coefficients from F_2^n for every term.
We know that Niho bent functions are related to o-polynomials. The power
terms in the univariate Niho bent function can be derived by working,
in a first step, on each monomial of the corresponding o-polynomial
separately, and in a second step, adding them to obtain the global
expression. This allows, knowing the monomials in an o-polynomial, to
obtain the power terms of the polynomial representing corresponding bent
function. However, the coefficients are not calculated explicitly. The
explicit form is given for the bent functions obtained from quadratic
and cubic o-polynomials. We also calculate the algebraic degree of any
bent function in the Leander-Kholosha class.
78) S. Picek, C. Carlet, S. Guilley, J. F. Miller and D. Jakobovic:
Evolutionary Algorithms for Boolean Functions in Diverse Domains of
Cryptography. Evolutionary Computation 24(4), pp. 667-694, 2016.
Abstract:
The role of Boolean functions is prominent in several areas like
cryptography, se- quences, and coding theory. Therefore, various methods
for the construction of Boolean functions with desired properties are
of direct interest. New motivations on the role of Boolean functions in
cryptography with attendant new properties have emerged during the
years. There are still many combinations of design criteria left
unexplored and in this matter evolutionary computation can play a
distinct role. This paper concentrates on two scenarios for use of
Boolean functions in cryptography. The first uses Boolean functions as
the source of the nonlinearity in filter and combiner generators.
Although relatively well explored using evolutionary algorithms, it
still presents an interesting goal in terms of the practical sizes of
Boolean functions. The second scenario appeared rather recently where
the objective is to find Boolean func- tions that have various orders of
the correlation immunity and minimal Hamming weight. In both those
scenarios we see that evolutionary algorithms are able to find high
quality solutions where genetic programming performs the best.
79) N. Bruneau, C. Carlet, S. Guilley, A. Heuser, E. Prouff and O.
Rioul. Stochastic Collision Attack. Transactions on Information
Forensics \& Security Vol. 12, Issue: 9, pp. 2090-2104, 2017.
Abstract:
On one side collision attacks have been introduced in the context of
side-channel analysis for attackers who exploit repeated code with the
same data without having any knowledge of the leakage model. On the
other side, stochastic attacks have been introduced to recover leakage
models of internally processed intermediate secret variables. Both
techniques have shown advantages and intrinsic limitations. Most
collision attacks, for instance, fail in exploiting all the leakages,
whereas stochastic attacks cannot involve linear regression with the
full basis (while the latter basis is the most informative one).
In this paper, we present an innovative attacking approach, which
combines the flavors of stochastic and collision attacks. Importantly,
our attack is derived from the optimal distinguisher, which maximizes
the success rate when the model is known. Notably, we develop an
original closed-form expression which shows many benefits by using the
full algebraic description of the leakage model. Using simulated data,
we show in the unprotected case that for low noise the stochastic
collision attack is superior to the state-of-the-art, whereas
asymptotically and thus for higher noise it becomes equivalent to the
correlation-enhanced collision attack. Our so-called stochastic
collision attack is extended to the scenario where the implementation is
protected by masking. In this case, our new stochastic collision attack
is more efficient in all scenarios, and remarkably, tends to the
optimal distinguisher. We confirm the practicability of the stochastic
collision attack thanks to experiments against a public data set (DPA
contest v4). Furthermore, we derive the stochastic collision attack in
case of zero-offset leakage that occurs in protected hardware
implementations and use simulated data for comparison. Eventually, we
underline the capability of the new distinguisher to improve its
efficiency when the attack multiplicity increases.
80) A. De Trano, N. Karimi, R. Karri, X. Guo, C. Carlet and S. Guilley.
Exploiting Small Leakages in Masks to Turn a Second-Order Attack into a
First-Order Attack. Proceedings of the Fourth Workshop on Hardware and
Architectural Support for Security and Privacy. 2015. p. 1-5. The
Scientific World Journal. Hindawi
Publishing Corporation.
Abstract:
Masking countermeasures, used to thwart side- channel attacks, have been
shown to be vulnerable to mask- extraction attacks. State-of-the-art
mask-extraction attacks on the Advanced Encryption Standard (AES)
algorithm target S-Box re-computation schemes, but have not been applied
to scenarios where S-Boxes are precomputed offline. We propose an
attack targeting precomputed S-Boxes stored in non-volatile memory. Our
attack targets AES implemented in software protected by a low entropy
masking scheme and recovers the masks with 91% success rate. Recovering
the secret key requires fewer power traces (in fact, by at least two
orders of magnitude) compared to a classical second order attack.
Moreover, we show that this attack remains viable in a noisy
environment, or with a reduced number of leakage points. Eventually, we
specify a method to enhance the countermeasure by selecting a suitable
coset of the masks set.
81) D. Tang, C. Carlet and Z. Zhou. Binary Linear Codes From Vectorial
Boolean Functions and Their Weight Distribution. Discrete Mathematics 340, no 12, pp. 3055-3072, 2017.
Abstract:
Binary linear codes with good parameters have important applications in
secret sharing schemes, authentication codes, association schemes, and
consumer electronics and communications. In this paper, we construct
several classes of binary linear codes from vectorial Boolean functions
and determine their parameters, by further studying a generic
construction developed by Ding et al. recently.
First, by employing perfect nonlinear functions and almost bent
functions, we obtain several classes of six-weight linear codes which
contain the all-one codeword.
Second, we investigate a subcode of any linear code mentioned above and consider its parameters.
When the vectorial Boolean function is a perfect nonlinear function or a
Gold function in odd dimension, we can completely determine the weight
distribution of this subcode.
Besides, our linear codes have larger dimensions than the ones by Ding \emph{et al.}'s generic construction.
82) D. Tang, C. Carlet, X. Tang and Z. Zhou. Construction of Highly
Nonlinear 1-Resilient Boolean Functions with Optimal Algebraic Immunity
and Provably High Fast Algebraic Immunity. IEEE Trans. Information Theory 63(9), pp. 6113-6125, 2017.
Abstract:
In 2013, Tang, Carlet and Tang [IEEE TIT 59(1): 653-664, 2013] presented
two classes of Boolean functions. The functions in the first class are
unbalanced and the functions in the second one are balanced. Both of
those two classes of functions have high nonlinearity, high algebraic
degree, optimal algebraic immunity, and high fast algebraic immunity.
However, they are not 1-resilient which represents a drawback for their
use as filter functions in stream ciphers. In this paper, we first
propose a large family of 1-resilient Boolean functions having high
lower bound on nonlinearity, optimal algebraic immunity, and optimal
algebraic degree, that is, meeting the Siegenthaler bound. Most notably,
we can mathematically prove that every functions in $n$ variables
belonging to this family has fast algebraic immunity no less than $n-6$,
which is the first time that an infinite family of 1-resilient
functions with provably high fast algebraic immunity has been invented.
Further, we exhibit a subclass of the family which has higher lower
bound on nonlinearity than for all known 1-resilient functions with
(potentially) optimal algebraic immunity and potentially high fast
algebraic immunity.
83) C. Carlet and S. Feukoua. Three basic questions on Boolean functions. Advances in
Mathematics of Communications Vol. 11, no. 4, pp. 837-855, 2017.
Abstract:
In a first part of this paper, we investigate those Boolean functions
satisfying two apparently related, but in fact distinct conditions
concerning the algebraic degree:\\1. we study those Boolean functions
$f$ whose restrictions to all affine hyperplanes have the same algebraic
degree (equal to $deg(f)$, the algebraic degree of $f$), \\2. we study
those functions whose derivatives $D_af(x)=f(x)+ f(x+a)$, $a\neq 0$,
have all the same (optimal) algebraic degree $deg(f)-1$. \\For
determining to which extent these two questions are related, we find
three classes of Boolean functions: the first class satisfies both
conditions, the second class satisfies the first condition but not the
second and the third class satisfies the second condition but not the
first. We also give for any fixed positive integer $k$ and for all
integers $n$, $p$, $s$ such that $p\geq k+1$, $s\geq k+1$ and
$n\geq ps$, a class $C_{n,p,s}$ of functions whose restrictions to all
$k$-codimensional affine subspaces of $F_2^n$ have the same
algebraic degree as the function.\\In a second part of the paper, we
introduce the notion of second-order-bent function, whose second order
derivatives $D_aD_bf(x)=f(x)+f(x+a)+f(x+b)+f(x+a+b)$, $a\neq 0, b\neq 0,
a\neq b$, are all balanced. We exhibit an example in 3 variables and we
prove that second-order-bent functions cannot exist if $n$ is not
congruent with 3 mod 4. We characterize second-order-bent functions by
the Walsh transform, state some of their properties and prove the non
existence of such functions for algebraic degree 3 when $n>3$. We
leave open the question whether second-order-bent functions can exist
for $n$ larger than $3$.
84) Y. Xu, C. Carlet, S. Mesnager, and C. Wu. Classification of bent
monomials, constructions of bent multinomials and upper bounds on the
nonlinearity of vectorial functions. IEEE Transactions on Information Theory 64, Issue:1, pp. 367-383, 2018.
Abstract:
The paper is composed of two main parts related to the nonlinearity of
vectorial functions. The first part is devoted to maximally
nonlinear $(n,m)$-functions (the so-called bent vectorial
functions) which contribute to an optimal resistance to both
linear and differential attacks on symmetric cryptosystems. They
can be used in block ciphers at the cost of additional
diffusion/compression/expansion layers, or as building blocks for the
construction of substitution boxes (S-boxes) and they are also useful
for constructing robust codes and algebraic manipulation detection
codes.
A main issue on bent vectorial functions is to characterize bent
monomial functions $Tr_{m}^n (\lambda x^d)$ from $\mathbb{F}_{2^n}$ to
$\mathbb{F}_{2^m}$ (where $m$ is a divisor of $n$) leading to a
classification of those bent monomials. We also treat the case of
functions with multiple trace terms involving general results and
explicit constructions. Furthermore, we investigate some open problems
raised by Pasalic et al. and Muratovi\'c-Ribi\'c et al. in a series of
papers on vectorial functions.
The second part is devoted to the nonlinearity of $(n,m)$-functions. No
tight upper bound is known when $\frac n2<m<n$. The covering
radius bound is the only known upper bound in this range (the
Sidelnikov-Chabaud-Vaudenay bound coincides with it when $m=n-1$ and it
has no sense when $m<n-1$). Finding better bounds is an open problem
since the 90's. Moreover, no bound has been found during the last 23
years which improve upon the covering radius bound for a large part of
$(n,m)$-functions. We derive such upper bounds for functions which
are sufficiently unbalanced or which satisfy some conditions. These
upper bounds imply some necessary conditions for vectorial functions to
have large nonlinearity.
85) C. Carlet. On the nonlinearity of monotone Boolean functions.
Proceedings of SETA 2016, Chengdu, China, 09-14 October 2016 and
Cryptography and Communications, 10(6), pp. 1051-1061, 2018.
Abstract:
We first prove the truthfulness of a conjecture on the nonlinearity of
monotone Boolean functions in even dimension, proposed in the recent
paper ``Cryptographic properties of monotone Boolean functions", by D.
Joyner, P. Stanica, D. Tang and the author (Journal of Mathematical
Cryptology, vol. 10, 2016). We prove then an upper bound on such
nonlinearity, which is asymptotically much stronger than the conjectured
upper bound and than the upper bound proved for odd dimension in
this same paper. Contrary to these two previous bounds, which were not
tight enough for allowing to clarify if monotone functions can have good
nonlinearity, this new bound shows that the nonlinearity of monotone
functions is always very bad, which represents a redhibitory weakness of
monotone Boolean functions; they are too closely approximated by affine
functions for being usable as nonlinear components in cryptographic
applications. We deduce a necessary criterion to be satisfied by a
Boolean (resp. vectorial) function for being nonlinear.
86) L. Budaghyan, C. Carlet, T. Helleseth, N. Li and B. Sun. On upper
bounds for algebraic degrees of APN functions. IEEE
Transactions on Information Theory 64(6), pp. 4399-4411, 2018.
Abstract:
We study the problem of existence of APN functions of algebraic
degree $n$ over $F_{2^n}$. We characterize such functions by means
of derivatives and power moments of the Walsh transform. We deduce
several non-existence results which imply, in particular, that for most
of the known APN functions $F$ over $F_{2^n}$ the function
$x^{2^n-1}+F(x)$ is not APN, and changing a value~of~$F$ in a single
point then results in non-APN functions. This leads us to conjectures
that an APN function modified in one point cannot remain APN and that
there exists no APN function of algebraic degree $n$.
87) C. Carlet. Characterizations of the differential uniformity of
vectorial functions by the Walsh transform. IEEE Transactions on Information Theory, Volume: 64, Issue:9, pp. 6443-6453, 2018.
Abstract:
For every positive integers $n$, $m$ and every even positive integer
$\delta$, we derive inequalities satisfied by the Walsh transforms of
all vectorial $(n,m)$-functions and prove that the case of equality
characterizes differential $\delta$-uniformity. This provides a
generalization to all differentially $\delta$-uniform functions of the
characterization of APN $(n,n)$-functions due to Chabaud and Vaudenay,
by means of the fourth moment of the Walsh transform. Such
generalization has been missing since the introduction of the notion of
differential uniformity by Nyberg in 1994 and since Chabaud-Vaudenay's
result the same year.
For each even $\delta\geq 2$, we find several such characterizations. In
particular, when $\delta=2$ and $\delta=4$, we have that, for any
$(n,n)$-function (resp. any $(n,n-1)$-function), the arithmetic
mean of $W_F^2(u_1,v_1)W_F^2(u_2,v_2)W_F^2(u_1+u_2,v_1+v_2)$ when
$u_1,u_2$ range independently over $F_2^n$ and $v_1,v_2$ are
nonzero and distinct and range independently over $F_2^m$,
is at least $2^{3n}$, and that $F$ is APN (resp. is differentially
4-uniform) if and only if this arithmetic mean equals $2^{3n}$ (which
is the value we would get with a bent function if such function could
exist).
These inequalities give more knowledge on the Walsh spectrum of
$(n,m)$-functions. We deduce in particular a property of the Walsh
support of highly nonlinear functions. We also consider the completely
open question of knowing if the nonlinearity of APN functions is
necessarily non-weak (as it is the case for known APN functions); we
prove new lower bounds which cover all power APN functions (and hence a
large part of known APN functions), which explain why their
nonlinearities are rather good, and we discuss the question of the
nonlinearity of APN quadratic functions (since almost all other known
APN functions are quadratic).
88) C. Carlet and X. Chen. Constructing low-weight $d$th-order
correlation-immune Boolean functions through the Fourier-Hadamard
transform. IEEE Transactions on Information Theory 64(4) (Special Issue in honor of Solomon Golomb), pp. 2969-2978, 2018.
Abstract:
The correlation immunity of Boolean functions is a property related to
cryptography, to error correcting codes, to orthogonal arrays (in
combinatorics, which was also a domain of interest of S. Golomb) and in a
slightly looser way to sequences. Correlation-immune Boolean functions
(in short, CI functions) have the property of keeping the same output
distribution when some input variables are fixed. They have been widely
used as combiners in stream ciphers to allow resistance to the
Siegenthaler correlation attack. Very recently, a new use of CI
functions has appeared in the framework of side channel attacks (SCA).
To reduce the cost overhead of counter-measures to SCA, CI functions
need to have low Hamming weights. This actually poses new challenges
since the known constructions which are based on properties of the
Walsh-Hadamard transform, do not allow to build unbalanced CI functions.
In this paper, we propose constructions of low-weight $d$th-order CI
functions based on the Fourier-Hadamard transform, while the known
constructions of resilient functions are based on the Walsh-Hadamard
transform. We first prove a simple but powerful result, which makes that
one only need to consider the case where $d$ is odd in further
research. Then we investigate how constructing low Hamming weight CI
functions through the Fourier-Hadamard transform (which behaves well
with respect to the multiplication of Boolean functions). We use the
characterization of CI functions by the Fourier-Hadamard transform and
introduce a related general construction of CI functions by
multiplication. By using the Kronecker product of vectors, we obtain
more constructions of low-weight $d$-CI Boolean functions. Furthermore,
we present a method to construct low-weight d-CI Boolean functions by
making additional restrictions on the supports built from the Kronecker
product.
89) C. Carlet and S. Guilley. Statistical properties of side-channel and
fault injection 1 attacks using coding theory. Cryptography and Communications 10(5), Special Issue: Statistics in Design and
Analysis of Symmetric Ciphers, S. Maitra Editor, pp. 909-933, 2018.
Abstract:
Naïve implementation of block ciphers are subject to side-channel
and fault injection attacks. To deceive side-channel attacks and to
detect fault injection attacks, the designer inserts specially crafted
error correcting codes in the implementation. The impact of codes on
protection against fault injection attacks is well studied: the number
of detected faults relates to their minimum distance. However, regarding
side-channel attacks, the link between codes and protection efficiency
is blurred. In this paper, we relate statistical properties of
code-based countermeasures against side-channel attacks to their
efficiency in terms of security, against uni- and multi-variate attacks.
90) C. Carlet, S. Mesnager, C. Tang, Y. Qi and R. Pellikaan.
Linear codes over F_q are equivalent to LCD codes for
q>3. IEEE Transactions on Information Theory 64(4) (Special
Issue in honor of Solomon Golomb), pp. 3010-3017, 2018.
Abstract:
Linear codes with complementary duals (abbreviated LCD) are linear codes whose intersection with their dual are trivial.
When they are binary, they play an important role in armoring
implementations against side-channel attacks and fault injection
attacks. Non-binary LCD codes in characteristic 2 can be transformed
into binary LCD codes by expansion. In this paper, we introduce a
general construction of LCD codes from any linear codes. Further, we
show that any linear code over
F_{q} (q>3) is equivalent to a Euclidean LCD code and any linear code
over F_{q^2} (q>2) is equivalent to a Hermitian LCD code.
Consequently an [n,k,d]-linear Euclidean LCD code over F_q with q>3
exists if there is an [n,k,d]-linear code over F_q and an [n,k,d]-linear
Hermitian LCD code over F_{q^2} with q>2 exists if there is an
[n,k,d]-linear code over F_{q^2}. Hence, when q>3 (resp.
q>2) q-ary Euclidean (resp. q^2-ary Hermitian) LCD codes
possess the same asymptotical bound as q-ary linear codes (resp.
q^2-ary linear codes). This gives a direct proof that every triple of
parameters [n,k,d] which is attainable by linear codes over F_{q} with
q>3 (resp. over F_{q^2} with q>2) is attainable by Euclidean LCD
codes (resp. by Hermitian LCD codes). In particular there exist
families of q-ary Euclidean LCD codes (q>3) and
q^2-ary Hermitian LCD codes (q>2) exceeding the asymptotical
Gilbert-Varshamov bound.
Further, we give a second proof of these results using the theory of Groebner bases.
Finally, we present a new approach of constructing LCD codes by extending linear codes.
91) C. Carlet, C. Guneri, F. Ozbudak, B. Ozkaya and P. Sole. On Linear
Complementary Pairs of Codes. IEEE Transactions on Information Theory 64, Issue:10, pp. 6583-6589, 2018.
Abstract:
We study linear complementary pairs (LCP) of codes (C,D), where both
codes belong to the same algebraic code family. We especially
investigate constacyclic and quasi-cyclic LCP of codes. We obtain
characterizations for LCP of constacyclic codes and LCP of quasi-cyclic
codes. Our result for the constacyclic complementary pairs extends the
characterization of linear complementary dual (LCD) cyclic codes given
by Yang and Massey. We observe that when $C$ and $D$ are complementary
and constacyclic, the codes $C$ and $D^\bot$ are equivalent to each
other. Hence, the security parameter $\min(d(C),d(D^\bot))$ for
LCP of codes is simply determined by one of the codes in this case. The
same holds for a special class of quasi-cyclic codes, namely 2D cyclic
codes, but not in general for all quasi-cyclic codes, since we have
examples of LCP of double circulant codes not satisfying this conclusion
for the security parameter. We present examples of binary LCP of
quasi-cyclic codes and obtain several codes with better parameters than
known binary LCD codes. Finally, a linear programming bound is obtained
for binary LCP of codes and a table of values from this bound is
presented in the case $d(C)=d(D^\bot)$. This extends the linear
programming bound for LCD codes.
92) C. Carlet, S. Mesnager, C. Tang and Y. Qi. Euclidean and Hermitian
LCD MDS codes. Designs, Codes and Cryptography 86(11), pp. 2605-2618, 2018.
Abstract:
Linear codes with complementary duals (abbreviated LCD) are linear codes whose intersection with their dual is trivial.
When they are binary, they play an important role in armoring
implementations against side-channel attacks and fault injection
attacks. Non-binary LCD codes in characteristic 2 can be transformed
into binary LCD codes by expansion. On the other hand, being optimal
codes, maximum distance separable codes
(abbreviated MDS) are of much interest from many viewpoints due to their
theoretical and practical properties. However, little work has
been done on LCD MDS codes.
In particular, determining the existence of $q$-ary $[n,k]$ LCD
MDS codes for various lengths $n$ and dimensions $k$ is a basic
and interesting problem. In this paper, we firstly study the
problem of the existence of $q$-ary $[n,k]$ LCD MDS codes and solve it for the
Euclidean case. More specifically, we show that for $q>3$ there
exists a $q$-ary $[n,k]$ Euclidean LCD MDS code, where $0\le k \le n\le
q+1$, or, $q=2^{m}$, $n=q+2$ and $k= 3 \text{ or } q-1$. Secondly, we
investigate several constructions of new Euclidean and Hermitian LCD
MDS codes. Our main techniques in
constructing Euclidean and Hermitian LCD MDS codes use some
linear codes with small dimension or codimension, self-orthogonal codes
and generalized Reed-Solomon codes.
93) C. Carlet, C. Guneri, F. Ozbudak and P. Sole. A new concatenated
type construction for LCD codes and isometry codes. Discrete Mathematics
341(3), pp. 830-835, 2018.
Abstract:
We give a new concatenated type construction for linear codes with
complementary dual (LCD) over small finite fields. In this construction
we need a special class of inner codes that we call {\it isometry
codes}. Our construction generalizes a recent construction of Carlet et
al.(2014-2016) and of G\"uneri et al. (2016). In particular it allows us
to construct LCD codes with improved parameters directly.
94) C. Carlet. Componentwise APNness, Walsh uniformity of APN functions,
and cyclic-additive difference sets. Finite Fields and Their
Applications, Volume 53, pp. 226-253, 2018.
Abstract:
In [Characterizations of the differential uniformity of vectorial
functions by the Walsh transform, IEEE Transactions on Information
Theory 2017], the author has characterized differentially
$\delta$-uniform functions by equalities satisfied by their Walsh
transforms. This generalizes the characterization of APN functions by
the fourth moment of the Walsh transform. We study two notions which are
related: (1) the componentwise APNness (CAPNness) of $(n,n)$-functions,
which is a stronger version of APNness, related to the characterization
by the fourth moment, in which the arithmetic mean of
$W_F^4(u,v)$ when $u$ ranges over $F_2^n$ and $v$ is fixed
nonzero in $F_2^n$ equals $2^{2n+1}$ (2) the componentwise Walsh
uniformity (CWU) of $(n,m)$-functions ($m=n$, resp. $m= n-1$), which is a
stronger version of APNness (resp. of differential 4-uniformity)
related to one of the new characterizations, in which the
arithmetic mean of $W_F^2(u_1,v_1)W_F^2(u_2,v_2)W_F^2(u_1+u_2,v_1+v_2)$
when $u_1,u_2$ range independently over $F_2^n$ and $v_1,v_2$ are
fixed nonzero and distinct in $F_2^m$, equals $2^{3n}$.
Concerning the first notion, it is known from Berger, Canteaut, Charpin
and Laigle-Chapuy that any plateaued function is CAPN if and only if it
is AB and that APN power permutations are CAPN. We prove that CAPN
functions can exist only if $n$ is odd; this solves an eleven year old
open problem by these authors. Concerning the second notion, we
show that any crooked function (and in particular any quadratic APN
function) is CWU, but we observe also that other APN functions like
Kasami functions and the inverse of one of the Gold APN permutations are
CWU for $n\leq 11$. We show that the CWUness of APN power permutations
is equivalent to a property of $\Delta_F=\{F(x)+F(x+1)+1; x\in
F_{2^n}\}$. This new property, that we call cyclic-additive difference
set property, is more complex than the cyclic difference set property
(proved in the case of Kasami APN functions by Dillon and Dobbertin). We
prove it in the case of the inverse of Gold function. In the case of
Kasami functions, we observe that the cyclic-additive property is also
true for $n\leq 10$ even and we leave the proof of the CWUness and the
cyclic-additive property as open problems.
95) C. Carlet, S. Mesnager, C. Tang and Y. Qi. New
characterization and parametrization of LCD Codes. IEEE
Transactions on Information Theory 65(1), pp. 39-49, 2019.
Abstract:
Linear complementary dual (LCD) cyclic codes were referred historically
to as reversible cyclic codes, which had applications in data storage.
Due to a newly discovered application in cryptography, there has been
renewed interest in LCD codes.
In particular, it has been shown that binary LCD codes play an
important role in implementations against side-channel attacks and
fault injection attacks. In this paper, we first present a new
characterization of binary LCD codes in terms of their symplectic
basis. Using such a characterization,we solve a conjecture proposed by
Galvez et al. on the minimum distance of binary LCD codes. Next,
we consider the action of the orthogonal group on the set of all LCD
codes, determine all possible orbits of this action, derive simple
closed formulas of the size of the orbits, and present some
asymptotic results of the size of the corresponding orbits. Our results
show that almost all binary LCD codes are odd-like codes with odd-like
duals,
and about half of $q$-ary LCD codes have orthonormal basis, where $q$ is a power of an odd prime.
96) C. Carlet, S. Mesnager, C. Tang and Y. Qi. On sigma-LCD
codes. IEEE Transactions on Information Theory 65(3), pp. 1694-1704, 2019.
Abstract:
Linear complementary pairs (LCP) of codes play an important role in
armoring implementations against side-channel attacks and fault
injection attacks. One of the most common ways to construct LCP of codes
is to use Euclidean linear complementary dual (LCD) codes. In this
paper, we first introduce the concept of linear codes with $\sigma$
complementary dual ($\sigma$-LCD), which includes known Euclidean LCD
codes, Hermitian LCD codes, and Galois LCD codes. As Euclidean LCD
codes, $\sigma$-LCD codes can also be used to construct LCP of codes. We
show that, for $q > 2$, all q-ary linear codes are $\sigma$-LCD and
that, for every binary linear code $\mathcal C$, the code $\{0\}\times
\mathcal C$ is $\sigma$-LCD. Further, we study deeply $\sigma$-LCD
generalized quasi-cyclic (GQC) codes. In particular, we
provide characterizations of $\sigma$-LCD GQC codes,
self-orthogonal GQC codes and self-dual GQC codes, respectively.
Moreover, we provide constructions of asymptotically good $\sigma$-LCD
GQC codes. Finally, we focus on $\sigma$-LCD Abelian codes and prove
that all Abelian codes in a semi-simple group algebra are $\sigma$-LCD.
The results derived in this paper extend those on the classical LCD
codes and show that $\sigma$-LCD codes allow the construction of
LCP of codes more easily and with more flexibility.
97) C. Carlet, A. Daif, S. Guilley and C. Tavernier. Polynomial direct
sum masking to protect against both SCA and FIA. Journal of Cryptographic Engineering (JCEN) 9, no. 3, pp. 303-312, 2019.
Abstract:
Side Channel Attacks (SCA) and Fault Injection Attacks (FIA) allow an
opponent to have partial access to the internal behavior of the
hardware. Since the end of the nineties, many works have shown that this
type of attacks constitute a serious threat to cryptosystems
implemented in embedded devices. In the state of the art, there exist
several countermeasures to protect symmetric encryption (especially
AES-128). Most of them protect only against one of these two attacks
(SCA or FIA). A method called ODSM has been proposed to withstand SCA
and FIA , but its implementation in the whole algorithm is a big open
problem when no particular hardware protection is possible. In the
present paper, we propose a practical masking scheme specifying ODSM
which makes it possible to protect the symmetric encryption against
these two attacks.
98) C. Carlet, X. Chen and L. Qu. Constructing Infinite Families of Low
Differential Uniformity $(n,m)$-Functions with $m>n/2$. Designs, Codes and Cryptography 87(7), pp.1577-1599, 2019.
Abstract:
Little theoretical work has been done on $(n,m)$-functions when $\frac
{n}{2}<m<n$, even though these functions can be used in Feistel
ciphers, and actually play an important role in several block ciphers.
Nyberg has shown that the differential uniformity of such functions is
bounded below by $2^{n-m}+2$ if $n$ is odd or if $m>\frac {n}{2}$.
In this paper, we first characterize the differential uniformity of
those $(n,m)$-functions of the form $F(x,z)=\phi(z)I(x)$, where $I(x)$
is the $(m,m)$-inverse function and $\phi(z)$ is an $(n-m,m)$-function.
Using this characterization, we construct an infinite family of
differentially $\Delta$-uniform $(2m-1,m)$-functions with $m\geq 3$
achieving Nyberg's bound with equality, which also have high
nonlinearity and not too low algebraic degree.
We then discuss an infinite family of differentially $4$-uniform
$(m+1,m)$-functions in this form, which leads to many differentially
$4$-uniform permutations.
We also present a method to construct infinite families of
$(m+k,m)$-functions with low differential uniformity and construct an
infinite family of $(2m-2,m)$-functions with
$\Delta\leq2^{m-1}-2^{m-6}+2$ for any $m\geq 8$.
The constructed functions in this paper may provide more choices for the design of Feistel ciphers.
99) S. Fu, X. Feng, Q. Wang and C. Carlet. On the Derivative Imbalance
and Ambiguity of Functions. IEEE Transactions on
Information Theory 65 (9), pp. 5833-5845, 2019.
Abstract:
In 2007, Carlet and Ding introduced two parameters Nb_F and NB_F to
quantify the balancedness of a vectorial Boolean function F and its
derivatives in the study of nonlinearity of S-boxes. They also provided
an inequality relating NB_F and the nonlinearity NL(F), and an upper
bound on nonlinearity which unifies Sidelnikov-Chabaud-Vaudenay's bound
and the covering radius bound. Independently, motivated by the study of
Costas arrays, another two parameters of a given bijective mapping F
over a finite abelian group G, ambiguity and deficiency, were introduced
by Panario et al. in 2010 to measure the injectivity and surjectivity
of the derivatives D_a F(x)=F(x+a)-F(x) for all a\in G\{0}$
respectively. They also studied some fundamental properties and
cryptographic significance of these two measures. In this paper, we
investigate the balancedness for derivatives of arbitrary functions
between any two finite abelian groups G_1 and G_2 with possible
different orders, and systematically study both parameters NB_F and
ambiguity in this generic setting. Although the motivation of the
parameter ambiguity is very different from that of NB_F, it is actually
equivalent to NB_F up to additive and multiplicative constants. As
consequences, we unify many previous known results and obtain several
new results on these two parameters.
100) C. Carlet, C. Li and S. Mesnager. Some (almost) optimally
extendable linear codes. Designs, Codes and Cryptography, Volume 87, Issue 12, pp. 2813-2834, 2019.
Abstract:
Side-channel attacks (SCA) and fault injection attacks (FIA) are
nowadays important cryptanalysis methods on the implementations of block
ciphers, which represent huge threats. Direct sum masking (DSM) has
been proposed to protect the sensitive data stored in registers against
both SCA and FIA. It uses two linear codes C and D whose sum is direct
and equals F_q^n . The resulting security parameter is the pair (d(C) -
1, d(D^\perp) - 1). For being able to protect not only the sensitive
input data stored in registers against SCA and FIA but the whole
algorithm (which is required at least in software applications), it is
necessary to change C and D into C′, which has the same minimum distance
as C, and D′, which may have smaller dual distance than D. Precisely,
D′ is the linear code obtained by appending on the right of its
generator matrix the identity matrix with the same number of rows. It is
then highly desired to construct linear codes D such that d(D′⊥) is
very close to d(D⊥). In such case, we say that D is almost optimally
extendable (and is optimally extendable if d(D′⊥) = d(D⊥)). In general,
it is notoriously difficult to determine the minimum distances of the
codes D^\perp and D'^\perp simultaneously.
In this paper, we mainly investigate constructions of (almost) optimally
extendable linear codes from irreducible cyclic codes and from the
first-order Reed-Muller codes. The minimum distances of the codes D, D′,
D^\perp, and D'^\perp are determined explicitly and their weight
enumerators are also given. Furthermore, several families of optimally
extendable codes are found (for the second time) among such linear
codes.
101) C. Carlet and S. Feukoua. Three parameters of Boolean functions
related to their constancy on affine spaces. Advances in
Mathematics of Communications 2020, vol. 14, no 4, p. 651.
Abstract:
The k-normality of Boolean functions is an important notion
initially introduced by Dobbertin and studied in several papers. The
parameter related to this notion is the maximal dimension of those
affine spaces contained in the support supp(f) of the function or in its
co-support cosupp(f). We denote it by norm(f) and call it the norm of
f.
The norm concerns only the affine spaces contained in either the support
or the co-support; the information it provides on f is then somewhat
incomplete (for instance, two functions constant on a hyperplane will
have the same very large parameter value, while they can have very
different complexities). A second parameter which completes the
information given by the first one is the minimum between the maximal
dimension of those affine spaces contained in supp(f) and the maximal
dimension of those contained in cosupp(f) (while norm(f) equals the
maximum between these two maximal dimensions). We denote it by cons(f)
and call it the (affine) constancy of f.
The value of cons(f) gives global information on f, but no information
on what happens around each point of supp(f) or cosupp(f). We define
then its local version, equal to the minimum, when a ranges over F_2^n,
of the maximal dimension of those affine spaces which contain a and on
which f is constant. We denote it by stab(f) and call it the stability
of f.
We study the properties of these three parameters.
102) C. Carlet, C. Li and S. Mesnager. Linear codes with small
hulls in semi-primitive case. Designs, Codes and
Cryptography, Volume 87, Issue 12, pp. 3063-3075, 2019.
Abstract:
The hull of a linear code is defined to be the intersection of the code
and its dual, and was originally introduced to classify finite
projective planes. The hull plays an important role in determining the
complexity of algorithms for checking permutation equivalence of two
linear codes and computing the automorphism group of a linear code. It
has been shown that these algorithms are very effective in general if
the size of the hull is small. It is clear that the linear codes with
the smallest hull are LCD codes and with the second smallest hull are
those with one-dimensional hull. In this paper, we employ character sums
in semi-primitive case to construct LCD codes and linear codes with
one-dimensional hull from cyclotomic fields and multiplicative subgroups
of finite fields. Some sufficient and necessary conditions for these
codes are obtained, where prime ideal decompositions of prime $p$ in
cyclotomic fields play a key role. In addition, we show the
non-existence of these codes in some cases.
103) L. Budaghyan, C. Carlet, T. Helleseth and N. S. Kaleyski. On the
Distance Between APN Functions. IEEE Transactions on Information Theory
66(9): 5742-5753, 2020.
Abstract:
We investigate the differential properties of a vectorial Boolean
function $G$ obtained by modifying $K \in \mathbb{N}$ values of an APN
function $F$. This is motivated by the question of determining the
minimum Hamming distance between APN functions, and generalizes
previously studied constructions in which a given function is modified
at a small number of points. We characterize the APN-ness of the $G$ in
terms of the derivatives of $F$, and deduce a filtering algorithm
allowing us to search for APN functions whose values differ from those
of a given APN function $F$ over $\mathbb{F}_{2^n}$ on a given set $U
\subseteq \mathbb{F}_{2^n}$.
We introduce a quantity $m_F$ associated with any given $F :
\mathbb{F}_{2^n} \rightarrow \mathbb{F}_{2^n}$ and demonstrate that it
is invariant under CCZ-equivalence and that a lower bound on the
distance between a given APN $F$ and the closest APN function can be
expressed in terms of $m_F$. Furthermore, we show how $m_F$ can be
computed more efficiently in the case of quadratic functions.
We derive a mathematical formula for $m_F$ in the case of the Gold
function $F(x) = x^3$ over any finite field $\mathbb{F}_{2^n}$, and
observe that the lower bound on the distance to the closest APN
functions tends to infinity with $n$. We compute the value of $m_F$ and
give a lower bound on the distance to the closest APN function for
representatives from all known switching classes of APN functions (as
described in ``A new almost perfect nonlinear function which is not
quadratic'' by Y. Edel and A. Pott) for $4 \le n \le 8$.
Additionally, we describe an efficient method for finding all sets $U$
such that setting $G(x) = F(x) + v$ for $x \in U$ and $G(x) = F(x)$ for
$x \notin U$ is APN, for any given $F$ and $v \in \mathbb{F}_{2^n}$.
104) L. Budaghyan, M. Calderini, C. Carlet, R. Coulter and I. Villa.
Constructing APN Functions Through Isotopic Shifts. IEEE Transactions on
Information Theory 66(8): 5299-5309, 2020.
Abstract:
Almost perfect nonlinear (APN) functions over fields of
characteristic 2 play an important role in cryptography, coding theory
and, more generally, mathematics and information theory. In this paper
we deduce a new method for constructing APN functions by studying the
isotopic equivalence concept defined for quadratic planar functions in
fields of odd characteristic. In particular, we construct a family of
quadratic APN functions which provides a new example of an APN mapping
over $F_{2^9}$ and includes an example of another APN function
$x^9+\Tr(x^3)$ over $F_{2^8}$ known since 2006 and not classified up to
now. We conjecture that the conditions for this family are satisfied by
infinitely many APN functions.
105) C. Carlet. Handling
vectorial functions by means of their graph indicators. IEEE
Transactions on Information Theory 66 (10), pp. 6324-6339, 2020.
Abstract:
We
characterize the ANF and the univariate representation of any vectorial
function as parts of the ANF and bivariate representation of the
Boolean function equal to its graph indicator. We show how this
provides, when $F$ is bijective, the expression of $F^{-1}$ and/or
allows deriving properties of $F^{-1}$. We illustrate this with examples
and with a tight upper bound on the algebraic degree of $F^{-1}$ by
means of that of $F$. We characterize by the Fourier-Hadamard transform,
by the ANF, and by the bivariate representation, that a given Boolean
function is the graph indicator of a vectorial function. We also give
characterizations of those Boolean functions that are affine equivalent
to graph indicators. We express the graph indicators of the sum,
product, composition and concatenation of vectorial functions by means
of the graph indicators of the functions. We deduce from these results a
characterization of the bijectivity of a generic $(n,n)$-function by
the fact that some Boolean function, which appears as a part of the ANF
(resp. the bivariate representation) of its graph indicator, is equal to
constant function 1. We also address the injectivity of
$(n,m)$-functions. Finally, we study the characterization of the almost
perfect nonlinearity of vectorial functions by means of their graph
indicators.
106) W. Cheng, C. Carlet, K. Goli, JL.Danger, S. Guilley. Detecting
Faults in Inner Product Masking Scheme IPM-FD: IPM with Fault Detection.
Journal of Cryptographic Engineering (JCEN), Vol 11, Issue 2, pp.
119–133, 2021.
Abstract:
Side-channel analysis and fault injection attacks are two
typical threats to cryptographic implementations, especially in modern
embedded devices. Thus there is an insistent demand for dual
side-channel and fault injection protections. As it is known, masking is
a kind of provable countermeasure against side-channel attacks.
Recently, inner product masking (IPM) was proposed as a promising
higher-order masking scheme against side-channel analysis, but not for
fault injection attacks.
In this paper, we devise a new masking scheme named IPM-FD. It is built
on IPM, which enables fault detection. This novel masking scheme has
three properties:
the security orders in the word-level probing model, bit-level probing
model, and the number of detected faults. IPM-FD is proven secure both
in the word-level and in the bit-level probing models, and allows for
end-to-end fault detection against fault injection attacks.
Furthermore, we illustrate its security order by interpreting IPM-FD as a
coding problem then linking it to one defining parameters of linear
code, and show its implementation cost by applying IPM-FD to AES-128.
107) L. Budaghyan, M. Calderini, C. Carlet, R. Coulter and I.
Villa. Generalized Isotopic Shift construction for APN functions.
Designs, Codes and Cryptography 89 (1), pp. 19-32, 2021 (extended
version of a paper published in the Proceedings of WCC 2019).
Abstract:
In this work we give several generalizations of the isotopic
shift construction, introduced recently by Budaghyan et al. (2018), when
the initial function is a Gold function. In particular, we derive a
general construction of APN functions which \corr{produces one new APN
function for $n=8$}{permits to cover several unclassified APN functions
for $n=8$ and produces} fifteen new APN functions for $n=9$.
108) C. Carlet, E. de Chérisey, S. Guilley, S. Kavut and
D. Tang. Intrinsic Resiliency of S-boxes Against Side-Channel Attacks -
Best And Worst Scenarios. Transactions on Information
Forensics \& Security 16, pp. 203-218, 2021.
Abstract:
Constructing S-boxes that are inherently resistant against
side-channel attacks is an important problem in cryptography. By using
an optimal distinguisher under an additive Gaussian noise assumption, we
clarify how a defender (resp., an attacker) can make side-channel
attacks as difficult (resp., easy) as possible, in relation with the
auto-correlation spectrum of Boolean functions. We then construct
balanced Boolean functions that are optimal for each of these two
scenarios. Generalizing the objectives for an S-box, we analyze the
auto-correlation spectra of some well-known S-box constructions in
dimensions at most $8$ and compare their intrinsic resiliency against
side-channel attacks. Finally, we perform several simulations of
side-channel attacks against the aforementioned constructions, which
confirm our theoretical approach.
109) W. Cheng, S. Guilley, C. Carlet, S. Mesnager, J.-L.
Danger. Optimizing Inner Product Masking Scheme by A Coding Theory
Approach. Transactions on Information
Forensics \& Security 16, pp. 220-235, 2021.
Abstract:
Masking is one of the most popular countermeasures to protect
cryptographic implementations against side-channel analysis since it is
provably secure and can be deployed at the algorithm level. To
strengthen the original Boolean masking scheme, several works have
suggested using schemes with high algebraic complexity. The Inner
Product Masking (IPM) is one of those. In this paper, we propose a
unified framework to quantitatively assess the side-channel security of
the IPM in a coding-theoretic approach. Specifically, starting from the
expression of IPM in a coded form, we use two defining parameters of the
code to characterize its side-channel resistance. In order to validate
the framework, we then connect it to two leakage metrics (namely
signal-to-noise ratio and mutual information, from an
information-theoretic aspect) and one typical attack metric (success
rate, from a practical aspect) to build a firm foundation for our
framework.
As an application, our results provide ultimate explanations on the
observations made by Balasch \textit{et al.} at EUROCRYPT'15 and at
ASIACRYPT'17, Wang \textit{et al.} at CARDIS'16 and Poussier \textit{et
al.} at CARDIS'17 regarding the parameter effects in IPM, like higher
security order in \emph{bounded moment model}. Furthermore, we show how
to systematically choose optimal codes (in the sense of a concrete
security level) to optimize IPM by using this framework. Eventually, we
present a simple but effective algorithm for choosing optimal codes for
IPM, which is of special interest for designers when selecting optimal
parameters for IPM.
110) C. Carlet. Graph indicators of vectorial functions and
bounds on the algebraic degree of composite functions. IEEE
Transactions on Information Theory 66 (12), pp. 7702-7716, 2020.
Abstract:
Given a vectorial function $F:\mathbb{F}_2^n \mapsto
\mathbb{F}_2^m$, the indicator $1_{{\cal G}_F}$ of its graph ${\cal
G}_F=\{(x,F(x)); x\in \mathbb{F}_2^n\}$ allows to express the algebraic
degree of $F$ in a simple way. Exploiting the formula, obtained in a
previous paper, for the graph indicator of a composite function $G\circ
F$, that involves only a sum of products of $1_{{\cal G}_F}$ and
$1_{{\cal G}_G}$, we deduce the exact expression as well as bounds on
the algebraic degree of $G\circ F$, whose efficiency comes from the fact
that the algebraic degree of the product of two Boolean functions is
bounded above by the sum of their algebraic degrees, while for a
composition, it is bounded above by their product. One of these bounds,
that depends on the algebraic degrees of $G$ and $1_{{\cal G}_F}$, is
tight, general, simple, and most often efficient (for the case where it
is not efficient, we give an improved bound, that is a little more
complex). As far as we know, it is the first efficient upper bound ever
found, that works without any condition on the vectorial functions. It
provides a new criterion for the choice of S-boxes in block ciphers. It
implies as a corollary a known bound assuming the divisibility of the
Walsh transform values by a power of 2. It gives a better view why this
latter bound works. All the bounds generalize to more than two functions
and this represents also an improvement over the state of the art.
When $F$ is a permutation, our expression of the algebraic degree of
$G\circ F$ simplifies into a formula involving the algebraic degrees of
the products of a coordinate function of $G$ and coordinate functions of
$F^{-1}$. This implies and improves another known bound showing that
the algebraic degree of $F^{-1}$ has more impact on that of $G\circ F$
than that of $F$ itself. Our approach by graph indicators gives an
explanation to this interesting fact. Our results include all the known
efficient bounds as particular cases, and clarify the reasons why they
work. We also deduce the exact expression of the algebraic degree of the
composition of any number of functions, leading to a bound that is much
more efficient than what we obtain by applying the known bound several
times. We also obtain two bounds on the algebraic degree of $G \circ F$,
where $F$ is a permutation, given the divisibility by powers of 2 of
some Walsh transform values of component functions of $F$ and their sums
with a coordinate function of $G$. We compare all the bounds of this
kind obtained so far and show how they are complementary, and we study
the generalizations of all (known and new) bounds of this kind to the
composition of more than two functions.
111) C. Carlet, K. H. Kim and S. Mesnager. A direct proof of
APN-ness of the Kasami functions. Designs, Codes and
Cryptography, 89 (3), pp. 441-446, 2021.
Abstract:
Using recent results on solving the equation $X^{2^k+1}+X+a=0$ over a
finite field $\GF{2^n}$ provided by the second and the third authors, we
address an open question raised by the first author in WAIFI 2014
concerning the APN-ness of the Kasami functions $x\mapsto
x^{2^{2k}-2^k+1}$ with $\gcd(k,n)=1$, $x\in\GF{2^n}$.
112) D. Davidova, L. Budaghyan, C. Carlet, T. Helleseth, F. Ihringer and
T. Penttila. Relation between o-equivalence and EA-equivalence for Niho
bent functions. Finite Fields and their Applications 72: 101834, 2021.
Abstract:
Boolean functions, and bent functions in particular, are considered up
to so-called EA-equivalence, which is the most general known equivalence
relation preserving bentness of functions. However, for a special type
of bent functions, so-called Niho bent functions there is a more general
equivalence relation called o-equivalence which is induced from the
equivalence of o-polynomials. In the present work we study, for a given
o-polynomial, a general construction which provides all possible
o-equivalent Niho bent functions, and we considerably simplify it to a
form which excludes EA-equivalent cases. That is, we identify all cases
which can potentially lead to pairwise EA-inequivalent Niho bent
functions derived from o-equivalence of any given Niho bent function.
Furthermore, we determine all pairwise EA-inequivalent Niho bent
functions arising from all known o-polynomials via o-equivalence.
113) C. Carlet and S. Mesnager. On those multiplicative subgroups of
$F_{2^n}^*$ which are Sidon sets and/or sum-free sets. Journal of
Algebraic Combinatorics Volume 55 Issue 1, pp 43–59, 2022.
Abstract:
We study those multiplicative subgroups of ${\mathbb F}_{2^n}^*$ which
are Sidon sets and/or sum-free sets in the group $({\mathbb
F}_{2^n},+)$. These Sidon and sum-free sets play an important role
relative to the exponents of APN power functions, as shown by a paper
co-authored by the first author.
114) C. Carlet. On the Properties of the Boolean Functions Associated to
the Differential Spectrum of General APN Functions and Their
Consequences. IEEE Transactions on Information Theory 67 (10), pp.
6926-6939, 2021.
Abstract:
We initiate a study, when $F$ is a general APN function, of the Boolean
function $\gamma_F$ related to the differential spectrum of $F$ (and
which is known to be bent if and only if $F$ is almost bent). We first
list many open questions about it. We study its algebraic normal form
and its bivariate representation. We characterize its linear structures
and specify nonexistence cases; we show, for $n$ even, their relation
with the bent components of $F$. We pose three related open problems. We
characterize further in terms of $\gamma_F$ the fact that a component
function of $F$ is bent and study if the number of bent components
can be optimal. We consider in particular two classes, one of which is
that of APN power functions. We study more deeply the relation between
the Walsh transform of $\gamma_F$ and the Walsh transform of $F$. By
applying the Titsworth relation to the Walsh transform $W_{\gamma_F}$,
we deduce a new relation satisfied by $W_F^2$, which is as simple as
Chabaud-Vaudenay's characterization by the fourth moment of the
Walsh transform (which is in fact a particular case of the new
relation), and provides more information. From this new relation, we
deduce, for a sub-class of APN functions, a lower bound on the
nonlinearity, which is significantly stronger than $nl(F)>0$ (the
only general known bound). This sub-class of APN functions includes all
known APN functions. The question (which is another open problem that we
state) arises whether this sub-class equals that of all APN functions,
but our bound provides at least a beginning of explanation why all known
APN functions have non-weak nonlinearity. We finally show how the
nonlinearities of $\gamma_F$ and $F$ are related by a simple formula;
this leads to a last open problem.
115) C. Carlet. Bounds on the nonlinearity of differentially uniform
functions by means of their image set size, and on their distance to
affine functions. IEEE Transactions on Information Theory 67 (12), pp. 8325-8334, 2021.
Abstract:
We revisit and take a closer look at a (not so well known) result of a
2017 paper, showing that the differential uniformity of any vectorial
function is bounded from below by an expression depending on the size of
its image set. We make explicit the resulting tight lower bound on the
image set size of differentially $\delta$-uniform functions (which is
the only currently known non-trivial lower bound on the image set size
of such functions).
We also significantly improve an upper bound on the nonlinearity of
vectorial functions obtained in the same reference and involving their
image set size. We study when the resulting bound is sharper than the
covering radius bound. We obtain as a by-product a lower bound on the
Hamming distance between differentially $\delta$-uniform functions and
affine functions, which we improve significantly with a second bound.
This leads us to study what can be the maximum Hamming distance
between vectorial functions and affine functions. We provide an upper
bound which is slightly sharper than a bound by Liu, Mesnager and Chen
when $m< n$, and a second upper bound, which is much stronger in the
case (happening in practice) where $m$ is near $n$; we study the
tightness of this latter bound; this leads to an interesting question on
APN functions, which we address (negatively). We finally derive an
upper bound on the nonlinearity of vectorial functions by means of their
Hamming distance to affine functions and make more precise the bound on
the differential uniformity which was the starting point of the paper.
116) C. Carlet. Revisiting some results on APN and algebraic immune functions. To
appear in Advances in Mathematics of Communications (AMC).
Abstract:
We push a little further the study of two recent characterizations of
almost perfect nonlinear (APN) functions. We state open problems about
them, and we revisit in their perspective a well-known result from
Dobbertin on APN exponents. This leads us to a new result about
APN power functions and more general APN polynomials with coefficients
in a subfield $\mathbb{F}_{2^k}$, which eases the research of such
functions. It also allows to construct automatically many differentially
uniform functions from them (this avoids calculations for proving their
differential uniformity as done in a recent paper, which are tedious
and specific to each APN function). In a second part, we give simple
proofs of two important results on Boolean functions, one of which
deserves to be better known but needed clarification, while the other
needed correction.
117) C. Carlet and P. Méaux. A complete study of two classes of
Boolean functions: direct sums of monomials and threshold functions.
IEEE Transactions on Information Theory 68(5), pp. 3404-3425,
2022.
Abstract:
In this paper, we make a comprehensive study of two classes of Boolean
functions whose interest originally comes from hybrid symmetric-FHE
encryption (with stream ciphers like FiLIP), but which also present much
interest for general stream ciphers. The functions in these two classes
are cheap and easy to implement, and they allow the resistance to all
classical attacks and to their guess and determine variants as well. We
determine exactly all the main cryptographic parameters (algebraic
degree, resiliency order, nonlinearity, algebraic immunity) for all
functions in these two classes, and we give close bounds for the others
(fast algebraic immunity, the dimension of the space of annihilators of
minimal degree). This is the first time that this is done for all
functions in large classes of cryptographic interest.
118) C. Carlet. A wide class of Boolean functions generalizing the
hidden weight bit function. IEEE Transactions on Information Theory 68 (2), pp. 1355-1368, 2022.
Abstract:
Designing Boolean functions whose output can be computed with light
means at high speed, and satisfying all the criteria necessary to resist
all major attacks on the stream ciphers using them as nonlinear
components, has been an open problem since the beginning of this
century, when algebraic attacks were invented. Functions allowing a good
resistance are known since 2008, but their output is a little too
complex to compute. Functions with fast and easy to compute output
are known which have good algebraic immunity, such as majority
functions and the so-called hidden weight bit (HWB) functions, but they
all have the same cryptographic weakness: their too small nonlinearity.
\\In the present paper, we introduce a generalization of the HWB
functions into a construction of $n$-variable balanced functions $f$
from $(n-1)$-variable Boolean functions $g$ having some property held by
a large number of functions. Function $f$ is defined by its support,
equal to the image set of a vectorial function depending on $g$. This
makes the function complex enough for allowing good cryptographic
parameters, while its output is light to compute. The HWB function is
what we obtain with $f$ when the initial function $g$ equals constant 1.
Other well chosen functions $g$ provide functions $f$ having good
cryptographic parameters. \\We analyze the constructed functions
$f$, we provide a fast way to compute their output, we determine their
algebraic normal forms and we show that, most often, their algebraic
degree is optimal. We study their Walsh transform and their nonlinearity
and algebraic immunity. We observe with computer investigations
that this generalization of the HWB function allows to keep its quality
of being fast to compute and having good enough algebraic immunity,
while significantly improving its nonlinearity. The
functions already obtained in the investigations provide a quite good
(and never reached before) trade-off between speed and security. Further
(probably difficult) work should allow obtaining, among such
generalized HWB functions whose number is huge, still better filter
functions to be used in stream ciphers.
119) C. Carlet and S. Picek. On the exponents of APN power functions and
Sidon sets, sum-free sets and Dickson polynomials. To appear in
Advances in Mathematics of Communications.
Abstract:
We derive necessary conditions related to the notions, in additive
combinatorics, of Sidon sets and sum-free sets, on those exponents d ∈
Z/(2^n − 1)Z, which are such that F(x) = x^d is an APN function over
F_{2^n} (which is an important cryptographic property). We study to what
extent these new conditions may speed up the search for new APN
exponents d. We summarize all the necessary conditions that an exponent
must satisfy for having a chance of being an APN, including the new
conditions presented in this work. Next, we give results up to n = 48,
providing the number of exponents satisfying all the conditions for a
function to be APN.
We also show a new connection between APN exponents and Dickson poly-
nomials: F (x) = xd is APN if and only if the reciprocal polynomial of
the Dick- son polynomial of index d is an injective function from {y ∈
F_{2^n}; tr_n(y) = 0} to F_{2^n}\{1}. This also leads to a new and
simple connection between Reversed Dickson polynomials and reciprocals
of Dickson polynomials in characteristic 2 (which generalizes to every
characteristic thanks to a small modification): the squared Reversed
Dickson polynomial of some index and the reciprocal of the Dickson
polynomial of the same index are equal.
120) L. Budaghyan, M. Calderini, C. Carlet, D. Davidova, and N.
Kaleyski. On two fundamental problems on APN power functions. IEEE
Transactions on Information Theory 68(5), pp. 3389-3403 , 2022.
Abstract:
The six infinite families of power APN functions are among the oldest
known instances of APN functions, and it has been conjectured in 2000
that they exhaust all possible power APN functions. Another
long-standing open problem is that of the Walsh spectrum of the
Dobbertin power family, which is still unknown. We derive alternative
representations for the infinite APN monomial families. We show how the
Niho, Welch, and Dobbertin functions can be represented as the
composition x^i ◦ x^{1/j} of two power functions, and prove that our
representations are optimal, i.e. no two power functions of lesser
algebraic degree can produce the same composition. We investigate
compositions x^i ◦ L ◦ x^{1/j} for a linear polynomial L, show how
Kasami functions in odd dimension can be expressed this way with i = j
being a Gold exponent and compute all APN functions of this form for n ≤
9 and for L with binary coefficients, thereby confirming that our
theoretical constructions exhaust all possible cases. We present
observations and data on power functions with exponent \sum_{i=1}^{k−1}
2^{2ni} − 1 which generalize the inverse and Dobbertin families. We
present data on the Walsh spectrum of the Dobbertin function for n ≤ 35,
and conjecture its exact form. As an application of our results, we
determine the exact values of the Walsh transform of the Kasami function
at all points of a special form. Computations performed for n ≤ 21 show
that these points cover about 2/3 of the field.
121) C. Carlet. Parameterization of Boolean functions by vectorial
functions and associated constructions. To appear in Advances in
Mathematics of Communications.
Abstract:
Too few general constructions of Boolean functions satisfying all
cryptographic criteria are known. We investigate the construction in
which the support of $f$ equals the image set of an injective vectorial
function $F$, that we call a parameterization of $f$. Every
balanced Boolean function can be obtained this way. We study five
illustrations of this general construction. The three first correspond
to known classes (Maiorana-McFarland, majority functions and
balanced functions in odd numbers of variables with optimal algebraic
immunity). The two last correspond to new classes:
- the sums of indicators of disjoint graphs of $(k,n-k$)-functions,
- functions parameterized through $(n-1,n)$-functions due to Beelen and Leander.
We study the cryptographic parameters of balanced Boolean
functions, according to those of their parameterizations: the
algebraic degree of $f$, that we relate to the algebraic degrees of $F$
and of its graph indicator, the nonlinearity of $f$, that we relate by a
bound to the nonlinearity of $F$, and the algebraic immunity (AI),
whose optimality is related to a natural question in linear algebra, and
which may be approached (in two ways) by using the graph indicator of
$F$. We revisit each of the five classes for each criterion. The fourth
class is very promising, thanks to a lower bound on the nonlinearity by
means of the nonlinearity of the chosen $(k,n-k$)-functions. The
sub-class of the sums of indicators of affine functions, for which we
prove an upper bound and a lower bound on the nonlinearity, seems
also interesting. The fifth class includes functions with an optimal
algebraic degree, good nonlinearity and good AI.
122) C. Beierle, C. Carlet, G. Leander, L. Perrin. A Further Study of
Quadratic APN Permutations in Dimension Nine. To appear in Finite Fields
and their Applications 81 (2022).
Abstract:
Recently, Beierle and Leander found two new sporadic quadratic APN
permutations in dimension 9. Up to EA-equivalence, we present a single
trivariate representation of those two permutations as $C_u \colon
(\F_{2^m})^3 \rightarrow (\F_{2^m})^3, (x,y,z) \mapsto (x^3+uy^2z,
y^3+uxz^2,z^3+ux^2y)$, where $m=3$ and $u \in \F_{2^3}\setminus\{0,1\}$
such that the two permutations correspond to different choices of
$u$. We then analyze the differential uniformity and the
nonlinearity of $C_u$ in a more general case. In particular, for $m \geq
3$ being a multiple of 3 and $u \in \F_{2^m}$ not being a 7-th power,
we show that the differential uniformity of $C_u$ is bounded above by 8,
and that the linearity of $C_u$ is bounded above by $8^{1+\lfloor
\frac{m}{2} \rfloor}$. Based on numerical experiments, we conjecture
that $C_u$ is not APN if $m$ is greater than $3$. We also analyze the
CCZ-equivalence classes of the quadratic APN permutations in dimension 9
known so far and derive a lower bound on the number of their
EA-equivalence classes. We further show that the two sporadic APN
permutations share an interesting similarity with Gold APN permutations
in odd dimension divisible by 3, namely that a permutation
EA-inequivalent to those sporadic APN permutations and their inverses
can be obtained by just applying EA transformations and inversion to the
original permutations.
123) C. Carlet, R. Kiss and G. P. Nagy. Simplicity conditions for binary
orthogonal arrays. To appear in Designs, Codes and Cryptography.
Abstract:
It is known that correlation-immune (CI) Boolean functions used in the
framework of side channel attacks need to have low Hamming weights. The
supports of CI functions are (equivalently) simple orthogonal arrays,
when their elements are written as rows of an array. The minimum Hamming
weight of a CI function is then the same as the minimum number of rows
in an simple orthogonal array. In this paper, we use Rao's Bound to give
a sufficient condition on the number of rows, for a binary orthogonal
array (OA) to be simple. We apply this result for determining the
minimum number of rows in all simple binary orthogonal arrays of
strengths 2 and 3; we show that this minimum is the same in such
case as for all OA, and we extend this observation to some OA of
strengths $4$ and $5$. This allows us to reply positively, in the case
of strengths 2 and 3, to a question raised by the first author and X.
Chen on the monotonicity of the minimum Hamming weight of 2-CI Boolean
functions, and to partially reply positively to the same question in the
case of strengths 4 and 5.
Full papers in proceedings of
international conferences, published by journals:
1) ``A General Case of Formal Duality Between Binary
Non-linear
Codes", C. Carlet, Discrete Mathematics 111, pp. 77-85
(1993)
Abstract:
We give a general context in which a binary code C admits at least one
code whose weight enumerator is dual to that of C. We study two
examples of applications of this general result.The first one is the
formal duality between the Kerdock code and the generalized Preparata
codes of same length and the second one gives a new example of dual
weight enumerators.
2) ``A construction of bent functions", C. Carlet, Finite
Fields and
Applications, London Mathematical Society, Lecture Series 233,
Cambridge University Press, pp. 47-58 (1996)
Abstract:
We introduce a general way to construct new bent functions from known
ones and deduce several classes of binary bent functions, given under
explicit forms (algebraic normal
forms).
3) ``On Kerdock codes", C. Carlet, American Mathematical
Society
(Proceedings of Finite Fields and Applications) Contemporary
Mathematics 225, pp. 155-163 (1999).
Abstract:
The Kerdock codes have been characterized as Z4-linear codes by A. R.
Hammons Jr., P. V. Kumar, A. R. Calderbank, N. J. A.
Sloane and P. Solé. We show how their weight distribution can be
derived by connecting sums over the Teichmuller set to sums over the
full Galois ring. We show also how the best known upper bound on their
covering radius can be simply deduced from the
computation of higher moments. We finally generalize a result from A.R.
Calderbank and Gary McGuire concerning their projections on hyperplanes.
4) ``One-weight Z_4-linear codes", C. Carlet, Proceedings
of
``International conference on Coding Theory, Cryptography and Related
Areas", Buchmann, Hoholdt, Stichtenoth et Tapia-Recillas
Eds,
Springer, pp. 57-72 (1999).
Abstract:
For every ordered pair of nonnegative integers (k_1,k_2), there exists
a unique (up to equivalence) one-weight Z4-linear code of type 4^k_1
2^k_2.
We derive an upper bound and a lower bound on the greatest minimum
distance between some one-weight Z4-linear codes of type 4^k and
the Reed-Muller code of order 1 and same length.
5) ``Recent results on binary bent functions", C. Carlet,
Proceedings of
International Conference on Combinatorics, Information Theory and
Statistics; Journal of Combinatorics, Information and System Sciences,
Vol. 24, Nos. 3-4, pp. 275-291 (1999)
Abstract:
The notion of bent function and the ability to produce large classes of
bent functions are relevant to cryptography
and to algebraic coding theory. We give an overview of the
constructions obtained since the introduction of the notion,
in the middle of the 70's. We describe also the recent
characterizations of bent functions that
lead to equivalent definitions in terms of finite geometries.
We finally give examples of related topics concerning Boolean functions.
6) "On generalized bent and q-ary perfect nonlinear
functions", C.
Carlet and S. Dubuc, Springer, D. Jungnickel and H. Niederreiter
Eds. Proceedings of Finite Fields and Applications,
pp. 81-94
(2000)
Abstract:
The notion of bent function has been generalized by Kumar et al. to the
alphabet Zq=Z/(qZ) and studied by Nyberg. The classical equivalent
definitions of binary bent
functions lead, through this generalization, to the notions of
generalized bent functions and of q-ary perfect nonlinear functions. We
show in this paper
that a q-ary function f
is perfect nonlinear if and only if, for every
u in Zq*, the function uf is generalized bent. We check that, among all
known constructions
of generalized bent functions, only one (due to Hou) can produce
perfect nonlinear functions. This construction works for n even
(n>2) and the question of knowing whether there exist
perfect nonlinear functions for n odd arises. We introduce a
construction of perfect nonlinear
functions on Z4^n, for every n>1.
7) ``Bent, resilient Functions and the Numerical Normal Form", C.
Carlet and P. Guillot, DIMACS Series in Discrete Mathematics and
Theoretical Computer Science, pp. 87-96 (2001)
Abstract:
We introduce a representation of Boolean functions which
yields more information on the combinatorial, spectral and
cryptographic
properties
of the functions than the representations which are currently used
in coding and cryptology.
We obtain formulae relating this representation to the classical ones.
We deduce an improvement of Mc Eliece theorem
on the divisibility of weights of some Boolean functions.
We finally relate this representation to an affine invariant on Boolean
functions.
This invariant is more precise than the algebraic degree and alows to
lead to a new characterization of bent functions.
8) ``On the coset weight divisibility and nonlinearity of
resilient
and correlation-immune functions", C. Carlet, Proceedings of
SETA'01
(Sequences and their Applications, Bergen, Norway, May 2001),
Discrete Mathematics and Theoretical Computer Science, Springer,
pp.
131-144 (2001).
Abstract:
Sarkar and Maitra have recently shown that, given any m-resilient
function f on F_2^n, the Hamming distance between f and any affine
function on F_2^n is divisible by 2^{m+1}. We show that their result is
a
simple consequence of a recent characterization of resilient functions
by means of their numerical normal forms. This characterization
allows us to obtain a better divisibility bound, involving n, m
and the algebraic degree d of the function.
Smaller is d and/or m,
stronger is our improvement. We show that our divisibility bound is
tight for every positive n, every non-negative m<= n-2 and every
positive d<= n-m-1.
We deduce a bound on the nonlinearity of resilient functions involving
n, m and d. This bound improves
upon those given recently and independently by Sarkar and Maitra and by
Tarannikov.
We finally show that the same bound stands in the more general
framework of m-th order correlation-immune functions, for sufficiently
large
m.
9) ``On cryptographic complexity of Boolean functions", C.
Carlet Proceedings of Fq6 (congrès Finite Fields and
Applications, may 2001,
Oaxaca, Mexique), Springer, edts G.L. Mullen, H. Stichtenoth et
H.
Tapia Recillas, pp. 53-69, 2002.
Abstract:
Cryptographic Boolean functions must be complex to satisfy Shannon's
principle
of confusion.
Two main criteria evaluating, from crytpographic viewpoint, the
complexity of Boolean functions
on F_2^n have been studied
in the literature: the nonlinearity (the minimum Hamming distance to
affine functions) and the algebraic degree. We consider two other
criteria: the minimum number of terms in the algebraic normal forms of
all affinely equivalent functions
(we call it the algebraic thickness) and the
non-normality. We show that, asymptotically, almost all Boolean
functions have
high algebraic
degrees, high nonlinearities, high algebraic thicknesses and are highly
non-normal.
10) ``Upper bounds on the numbers of resilient functions and of
bent
functions", C. Carlet and A. Klapper. Proceedings of "23rd
Symposium on
Information Theory in the Benelux", Louvain-La-Neuve, Belgique,
may 2002. Publié par "Werkgemeeschap voor Informatie- en
Communicatietheorie, Enschede, The Nederlands, pp. 307-314, 2002.
Abstract:
Bent and resilient functions play significant roles in cryptography,
coding theory, and combinatorics. However, the numbers of bent and
resilient functions on a given number of variables are not known. Even
a reasonable bound on the number of bent functions is not known and the
best known bound
on the number of resilient functions seems weak for functions of high
orders. In this paper we present new bounds which significantly improve
upon those
which can be directly deduced from the restrictions on the degrees
of these functions. In the case of bent functions, it is the first one
of this type. In
the case of m-resilient functions, it improves upon the known bounds
for m large.
11) "On the secondary constructions of resilient and bent functions",
C. Carlet, Proceedings of the conference "Coding, Cryptography
and
Combinatorics", Progress in Computer
Science and Applied Logic, Vol. 23,
Birkhauser Verlag, Basel, pp. 3-28, 2004.
Abstract:
We first give a survey of the known secondary constructions of Boolean
functions, permitting to obtain resilient functions achieving the best
possible trade-offs between resiliency order, algebraic degree
and
nonlinearity (that is, achieving Siegenthaler's bound and Sarkar et
al.'s bound). We introduce then, and we study, a general secondary
construction of Boolean functions. This construction includes as
particular cases the known secondary constructions previously
recalled. We apply this construction to design more numerous functions
achieving optimum trade-offs between the three characteristics (and
additionally having no linear structure). We conclude the paper by
indicating generalizations of our construction to Boolean and vectorial
functions, and by relating it to a known secondary construction of bent
functions.
12) ``Partial covering sequences: a method for
designing classes of
cryptographic functions". C.
Carlet.
Proceedings of the conference ``The first Symposium on Algebraic
Geometry and its Applications" (SAGA'07), Tahiti, 2007, published by
the journal "Algebraic geometry and its applications", vol. 5, World
Scientific, pp. 366-387, 2008.
Abstract:
Few general constructions of cryptographic Boolean functions have
been obtained so far.
They have been found in empirical ways, and no general method for
designing such constructions is known.
Weakening a notion, called covering sequence and originally introduced
for studying resilient functions, we show that, astonishingly enough,
the knowledge of such ``partial covering sequence" can give more
information on the function. We deduce a method for designing
constructions of Boolean functions with efficiently computable weights
and Walsh
spectra. The nonlinearity is then easier to handle for these
functions. We illustrate this method with examples.
13) ``A method of construction of balanced functions with optimum
algebraic immunity". C. Carlet. Proceedings of the conference
IWCC, Wuyishan,
Chine,
published by World Scientific, series of Coding and Cryptology, pp.
25-43, 2008.
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. 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, valid for any even number
of variables, for constructing functions with optimum (or, if
this can
be useful, with high but not optimal) algebraic immunity and which can
be balanced if we wish. We also introduce a new example of an
infinite
class of such functions. We study their Walsh transforms. We finally
give similar algorithm and infinite class in the case $n$ is odd (which
is different).
14) ``On almost perfect nonlinear functions" (invited paper), C.
Carlet. Proceedings of the Third International Workshop on Signal
Design and Its Applications in Communications, Chengdu, China. IEICE,
Vol. E91-A, No.12, pp. 3665-3678, 2008.
Abstract:
A function $F:F_2^n\rightarrow F_2^n$ is almost perfect nonlinear (APN)
if, for every $a\neq 0$, $b$ in $F_2^n$, the equation $F(x)+F(x+a)=b$
has at most two solutions in $F_2^n$. When used as an S-box in a block
cipher, it contributes optimally to the resistance to differential
cryptanalysis. The function $F$ is {\em almost bent} (AB) if the
minimum Hamming distance between all its {\em component} functions
$v\cdot F$, $v\in \F_2^n \setminus \{0\}$ (where ``$\cdot$" denotes any
inner product in $F_2^n $) and all affine Boolean functions on
$F_2^n $ takes the maximal value $2^{n-1}-2^{\frac{n-1}{2}}$. AB
functions exist for $n$ odd only and contribute optimally to the
resistance to the linear cryptanalysis. Every AB function is APN, and
in the $n$ odd case, any quadratic APN function is AB.
The APN and AB properties are preserved by affine equivalence: $F\sim
F'$ if $F'=A_1\circ F\circ A_2$, where $A_1,A_2$ are affine
permutations. More generally, they are preserved by CCZ-equivalence,
that is, affine equivalence of the graphs of $F$: $\{(x,F(x)) \ | \
x\in \F_{2^n}\}$ and of $F'$. Until recently, the only known
constructions of APN and AB functions were CCZ-equivalent to power
functions $F(x)=x^d$ over finite fields ($F_{2^n}$ being identified
with $F_2^n$ and an inner product being $x\cdot y=tr(xy)$ where $tr$ is
the trace function). Several recent infinite classes of APN functions
have been proved CCZ-inequivalent to power functions.
In this paper, we describe the state of the art in the domain and we
also present original results.
We indicate what are the most important open problems and make some new
observations about them.
Many results presented are from joint works with Lilya Budaghyan,
Gregor Leander and Alexander Pott.
15) C. Carlet. On the algebraic immunities and higher order nonlinearities of
vectorial Boolean functions. NATO Science for Peace
and
Security Series, D: Information and Communication Security - Vol 23;
Enhancing Cryptographic Primitives with Techniques from Error
Correcting Codes, pp. 104-116, 2009. Invited paper.
Abstract:
We recall the two different notions of algebraic immunity of vectorial
functions: the basic algebraic immunity and the graph algebraic
immunity. We introduce a new one, the component algebraic immunity,
which helps studying the two others. We study the tightness of the
bounds on the two first notions and prove bounds between them three. We
recall the known bounds on the $r$-th order nonlinearity of a vectorial
function, given its basic algebraic immunity. We recall why the basic
algebraic immunity is not a relevant parameter when the number of
output bits of the vectorial function is not small enough and/or when
the S-box is used in a block cipher. This leads us to showing bounds on
the $r$-th order nonlinearity, given the graph algebraic immunity, that
we deduce from similar bounds involving the component algebraic
immunity.
16) L. Budaghyan and C. Carlet. CCZ-equivalence of single and multi
output Boolean functions. AMS Contemporary
Math. 518, Post-proceedings of the
conference Fq9, pp. 43-54, 2010.
Abstract:
It is known that CCZ-equivalence of $(n,n)$-functions is strictly more
general than their EA-equivalence (even when considering only APN
functions), and that these two notions of equivalence coincide for bent
$(n,m)$-functions. In the present paper we study CCZ-equivalence of
general $(n,m)$-functions. We prove that, for Boolean
functions (that is, when $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 (for any
$m\geq 2$ if $n$ is even, then). Our result on Boolean functions allows
us to study a potential generalization of CCZ-equivalence
corresponding to the CCZ-equivalence of the indicators of
the graphs of functions. We show that it coincides with CCZ-equivalence.
17) C. Carlet. A Survey on Nonlinear Boolean Functions with Optimal
Algebraic Immunity suitable for Stream Ciphers. Proceedings of the
SMF-VMS conference, Hué, Vietnam, August 20-24, 2012. Special
issue
of the Vietnam Journal
of Mathematics, Volume 41, Issue 4, Page 527-541, 2013.
Abstract:
This paper is devoted to Boolean functions for cryptography; more
precisely those which can be used for filtering linear feedback shift
registers, in the pseudo random generators of stream ciphers, for
allowing resistance to the main cryptanalyses (algebraic, fast
algebraic, Berlekamp-Massey, R\o njom-Helleseth and fast correlation
attacks).
18) C. Carlet and Y. Tan. On Group Rings and some of their Applications to
Combinatorics and Cryptography. Proceeding of the conference ``Groups,
Group Rings and Related Topics'', UAEU, Al Ain, October 2013.
International Journal of group Theory (IJGT), Volume 4, Issue 4,
December 2015, Page 61-74, 2015.
Abstract:
We give a survey of recent applications of group rings to combinatorics
and to cryptography, including their use in the differential
cryptanalysis of block ciphers.
19) C. Carlet and S. Guilley. Correlation-immune Boolean functions for
easing counter-measures to side channel attacks. Proceedings of the
Workshop "Emerging Applications of Finite Fields" (part of the semester
program on Applications of Algebra and Number Theory, Linz, 9-13
December, 2013), Algebraic Curves and Finite Fields, Radon Series on
Computational and Applied Mathematics, published by de Gruyter,
pp. 41-70, 2014.
Abstract:
Correlation-immune Boolean functions (in short, CI functions) have the
property to keep the same output distribution if some input variables
are fixed. They allow resisting the Siegenthaler correlation attack
when they are used as combiners in stream ciphers. Their study (more
precisely, the study of balanced CI functions, called resilient, since
combiner functions need to have uniformly distributed output) was very
active at the end of the last century. However, the security of stream
ciphers has been challenged in 2003 by the fast algebraic attack and in
2007 by the Ronjom-Helleseth attack. These attacks are very powerful
when the combiner function has low algebraic degree. %does not have
very high algebraic degree. CI functions are then weak because of the
Siegenthaler bound.
Incidentally, trade-offs between CI order and algebraic degree were
already required before 2003, because of the Berlekamp-Massey attack.
But very recently, a new use of CI functions has appeared in the
framework of side channel attacks. These attacks on the implementations
of block ciphers in embedded systems like smart cards, FPGA or ASIC
assume an attacker model different from classical attacks, and are in
practice extremely powerful. These implementations need then to include
counter-measures, which slow down the cryptosystems and require
additional memory. CI functions allow reducing this cost overhead. They
need either to have low Hamming weights or to be the indicators
of so-called CIS codes, equal to the graphs of permutations. In
both cases, the CI functions are unbalanced and this actually poses new
challenges since the known constructions happen to be more efficient
for designing resilient functions. We review what is known in this new
framework and investigate constructions.
20) C. Carlet. Open problems on binary bent functions. Proceeding of the
conference ``Open problems in mathematical and computational sciences",
September 18-20, 2013, in Istanbul, Turkey, pp. 203-241, Springer, 2014.
Abstract:
This paper gives a survey of the recent results on Boolean bent
functions and lists some open problems in this domain. It includes also a
few new results. We recall the definitions and basic results, describe
the constructions (primary and secondary) and give the known infinite
classes, in multivariate representation and in trace representation
(univariate and bivariate).
We also focus on the particular class of rotation symmetric (RS)
bent functions and on the related notion of bent idempotent: we give the
known infinite classes and secondary constructions of such
functions, and we describe the properties of a recently introduced
transformation of RS functions into idempotents.
21) C. Carlet and S. Guilley. Complementary Dual Codes for
Counter-measures to Side-Channel Attacks. Post-proceedings of the 4th International Castle Meeting, Palmela
Castle, Portugal, September 15-18, 2014, published by the journal
"Advances in Mathematics of Communications" (AMC) Vol. 10, no. 1, pp. 131-150, 2016. A preliminary version
has appeared in the proceedings published by the CIM Series in
Mathematical Sciences, Vol. 3, 2015.
Abstract:
We recall why linear codes with complementary duals (LCD codes) play a
role in counter-measures to passive and active side-channel analyses on
embedded cryptosystems. The rate and the minimum distance of such LCD
codes must be as large as possible. We recall the known primary
construction of such codes with cyclic codes, and investigate other
constructions, with expanded Reed-Solomon codes and generalized residue
codes, for which we study the idempotents. These constructions do not
allow to reach all the desired parameters. We study then those secondary
constructions which preserve the LCD property, and we characterize
conditions under which codes obtained by direct sum, direct product,
puncturing, shortening, extending codes, or obtained by the Plotkin sum,
can be LCD.
22) C. Carlet, P. Méaux and Yann Rotella. Boolean functions with
restricted input and their robustness; application to the FLIP cipher. FSE 2018.
IACR Trans. Symmetric Cryptol. 2017, no 3, pp. 192-227, 2017.
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 $\mathbb{F}_2^n$. We study in particular the case
when $E$ equals the set of vectors of fixed Hamming weight, which plays a
role in the FLIP stream cipher and we study the robustness of the
Boolean function in this cipher.
23) C. Carlet. On APN exponents, characterizations of differentially
uniform functions by the Walsh transform, and related
cyclic-difference-set-like structures. Proceedings of WCC 2017. Designs,
Codes and Cryptography 87 (2) (Postproceedings of WCC 2017), pp.
203-224, 2018.
Abstract:
In this paper, we summarize the results obtained recently in three
papers on differentially uniform functions in characteristic 2, and
presented at the workshop WCC 2017 in Saint-Petersburg, and we give new
results on these functions. Firstly, we recall the recent connection
between Almost Perfect Nonlinear (APN) power functions and the two
notions in additive combinatorics of Sidon sets and sum-free sets; we
also recall a recent characterization of APN exponents which leads to a
property of Dickson polynomials in characteristic 2 previously
unobserved, which is generalizable to all finite fields. We also give a
new characterization of APN exponents in odd dimension by Singer sets.
Secondly, after recalling the recent generalization to
differentially $\delta$-uniform functions of the Chabaud-Vaudenay
characterization of APN functions by their Walsh transforms, we
generalize the method to all criteria on vectorial functions dealing
with the numbers of solutions of equations of the form $\sum_{i\in
I}F(x+u_{i,a})+L_a(x)+u_a=0$, with $L_a$ linear; we give the examples of
injective functions and of o-polynomials; we also deduce a
generalization to differentially $\delta$-uniform functions of the
Nyberg characterization of APN functions by means of the Walsh
transforms of their derivatives. Thirdly, we recall the two
notions of componentwise APNness (CAPNness) and componentwise
Walsh uniformity (CWU). We recall why CAPN functions can exist only if
$n$ is odd and why crooked functions (in particular, quadratic APN
functions) are CWU. We also recall that the inverse of one of the Gold
permutations is CWU and not the others. Another potential class of CWU
functions is that of Kasami functions. We consider the difference sets
with Singer parameters equal to the complement of
$\Delta_F=\{F(x)+F(x+1)+1; x\in F_{2^n}\}$ where $F$ is a Kasami
function. These sets have another potential property, called the
cyclic-additive difference set property, which is related to the
CWU property in the case of power permutations ($n$ odd). We study
cyclic-additive difference sets among Singer sets. We recall the main
properties of Kasami functions and of the related set $\Delta_F$ shown
by Dillon and Dobbertin and we observe and prove new expressions for
$\Delta_F$.
24) M. Calderini, L. Budaghyan and C. Carlet. On Known Constructions of
APN and AB Functions and their Relation to Each Other. Proceedings of
the 20th Central European Conference on Cryptology. Matematicke znanosti
Vol. 25, pp. 79-105, 2021.
Abstract:
This work is dedicated to APN and AB functions which are optimal against
differential and linear cryptanlysis when used as S- boxes in block
ciphers. They also have numerous applications in other branches of
mathematics and information theory such as coding theory, sequence
design, combinatorics, algebra and projective geometry. In this paper we
give an overview of known constructions of APN and AB func- tions, in
particular, those leading to infinite classes of these functions. Among
them, the bivariate construction method, the idea first introduced in
2011 by the third author of the present paper, turned out to be one of
the most fruitful. It has been known since 2011 that one of the families
de- rived from the bivariate construction contains the infinite
families derived by Dillon’s hexanomial method. Whether the former
family is larger than the ones it contains has stayed an open problem
which we solve in this paper. Further we consider the general bivariate
construction from 2013 by the third author and study its relation to the
recently found infinite families of bivariate APN functions.
25) W. Cheng, S. Guilley, C. Carlet, J.-L. Danger and S. Mesnager.
Information Leakages in Code-based Masking: A Unified Quantification
Approach. IACR Trans. Cryptogr. Hardw. Embed. Syst. (TCHES) 2021 (3), pp.
465-495, 2021.
Abstract:
This paper presents a unified approach to quantifying the information
leakages in the most general code-based masking schemes. Specifically,
by utilizing a uniform representation, we highlight first that all
code-based masking schemes’ side-channel resistance can be quantified by
an all-in-one framework consisting of two easy-to- compute parameters
(the dual distance and the number of conditioned codewords) from a
coding-theoretic perspective. In particular, we use signal-to-noise
ratio (SNR) and mutual information (MI) as two complementary metrics,
where a closed-form expression of SNR and an approximation of MI are
proposed by connecting both metrics to the two coding-theoretic
parameters. Secondly, considering the connection between Reed-Solomon
code and SSS (Shamir’s Secret Sharing) scheme, the SSS- based masking is
viewed as a particular case of generalized code-based masking. Hence as
a straightforward application, we evaluate the impact of public points
on the side-channel security of SSS-based masking schemes, namely the
polynomial masking, and enhance the SSS-based masking by choosing
optimal public points for it. Interestingly, we show that given a
specific security order, more shares in SSS-based masking leak more
information on secrets in an information-theoretic sense. Finally, our
approach provides a systematic method for optimizing the side-channel
resistance of every code-based masking. More precisely, this approach
enables us to select optimal linear codes (parameters) for the
generalized code-based masking by choosing appropriate codes according
to the two coding-theoretic parameters. Summing up, we provide a
best-practice guideline for the application of code-based masking to
protect cryptographic implementations.
26) C. Carlet, S. Guilley and S. Mesnager. Structural Attack (and
Repair) of Diffused-Input-Blocked-Output White Box Cryptography. IACR
Trans. Cryptogr. Hardw. Embed. Syst. (TCHES) 2021 (4), pp. 57-87, 2021.
Abstract:
In some practical enciphering frameworks, operational constraints may
require that a secret key be embedded into the cryptographic algorithm.
Such implementations are referred to as White Box Cryptography (WBC).
One technique consists of the algorithm’s tabulation specialized for its
key, followed by obfuscating the resulting tables. The obfuscation
consists of the application of invertible diffusion and confusion layers
at the interface between tables so that the analysis of input/output
does not provide exploitable information about the concealed key
material.
Several such protections have been proposed in the past and already
cryptanalyzed thanks to a complete WBC scheme analysis. In this article,
we study a particular pattern for local protection (which can be
leveraged for robust WBC); we formalize it as DIBO (for
Diffused-Input-Blocked-Output). This notion has been explored (albeit
without having been nicknamed DIBO) in previous works. However, we
notice that guidelines to adequately select the invertible diffusion φ
and the blocked bijections B were missing. Therefore, all choices for φ
and B were assumed as suitable. Actually, we show that most
configurations can be attacked, and we even give mathematical proof for
the attack. The cryptanalysis tool is the number of zeros in a Walsh-
Hadamard spectrum. This “spectral distinguisher” improves on top of the
previously known one (Sasdrich, Moradi, Güneysu, at FSE 2016). However,
we show that such an attack does not work always (even if it works most
of the time).
Therefore, on the defense side, we give a straightforward rationale for
the WBC implementations to be secure against such spectral attacks: the
random diffusion part
φ shall be selected such that the rank of each restriction to bytes is full. In AES’s
case, this seldom happens if φ is selected at random as a linear bijection of F32. Thus, 2
specific care shall be taken. Notice that the entropy of the resulting φ
(suitable for WBC against spectral attacks) is still sufficient to
design acceptable WBC schemes.
Other full papers in proceedings
of international conferences, published by Lecture Notes in Computer
Science:
1) C. Carlet. ``A Simple Description of Kerdock Codes", Coding
Theory and Applications, 3rd International Colloquium, 1988,
Lecture
notes in Computer Science no 388, Springer-Verlag, pp. 202-208,
(1989)
Abstract:
In a paper published in IEEE Transactions on
Information Theory, R.D. Baker et al. give a convenient
characterization of Preparata codes. We here give a proof of their
description and a similar one for Kerdock codes.
2) C. Carlet. ``A transformation on Boolean Functions, its Consequences on
some
Problems Related to Reed-Muller Codes", EUROCODES'90,
Lecture Notes in Computer Science no 514, pp. 42-50,
Springer-Verlag
(1991)
Abstract:
We introduce a transformation defined on the set
of all boolean functions defined on Galois fields GF(2^m), which
changes their weights in a way easy to be followed, and which, when we
iterate it, reduces their degrees down to 2 or 3. We deduce that it is
as difficult to find a general characterization of the weights in the
Reed-Muller codes of order 3 as it is to obtain one in the Reed-Muller
codes of any orders. We also use this transformation to characterize
the existence of some affine sets of bent functions, and to obtain bent
functions of degree 4 from bent functions of degree 3.
3) Paul Camion, C. Carlet,
Pascale Charpin and Nicolas Sendrier. ``On Correlation-immune Functions", CRYPTO' 91, Santa Barbara,
USA,
Advances in Cryptology, Lecture Notes in Computer Science, Springer
Verlag no 576, pp. 86-100 (1992).
Abstract:
In a general type of running-key generator, the
output sequences of m linear Feedback Shift Register are taken as
arguments of a single non linear combining function f. If the function
is not properly chosen, it can happen that the generator structure is
not resistant to a correlation attack : there is a statistical
dependence between any small subset of the m subgenerator sequences and
the keystream sequence .
A function f which provides an imunity to a correlation attack is
called a correlation immune function .We show that Algebraic Coding
Theory provides an alternative point of view for the concept of
correlation-immunity. We present new definitions of the correlation
immune functions, related to coding theory, deduce a number of new
constructions, and characterize the quadratic correlation immune
functions of maximal order.
4) C. Carlet. ``Two new classes of bent functions",
Proceedings of
EUROCRYPT'93, Advances in Cryptology, Lecture Notes in
Computer
Science, no 765, pp. 77-101 (1994)
Abstract:
We introduce a new class of bent functions on
(GF(2))n ( n even). We prove that this class is not included in one of
the known classes of bent functions, and that, when n equals 6, it
covers the whole set of bent functions of degree 3. This class is
obtained by using a result from J.F. Dillon. We generalize this result
and deduce a second new class of bent functions which we checked was
not included in one of the preceding ones.
5) C. Carlet. ``More correlation-immune and resilient functions over
Galois
fields and Galois rings", Proceedings of EUROCRYPT'97,
Advances in
Cryptology, Lecture Notes in Computer Science no 1233, pp.
422-433
(1997)
Abstract:
We show that the usual constructions of bent functions, when they are
suitably modified,
allow constructions of correlation-immune and resilient functions over
Galois fields
and, in some cases, over Galois rings.
6)
C.
Carlet. ``On the propagation criterion of degree l and order k", Proceedings of EUROCRYPT'98, , Advances in
Cryptology,
Lecture
Notes in Computer Science no 1403, pp. 462-474 (1998)
Abstract:
We determine those Boolean functions on GF(2)^n which satisfy the
propagation criterion of degree
l and of orders at least equal to n-l- 2. All of theses functions are
quadratic. We design nonquadratic Boolean functions satisfying the
criterion
PC(l) of order k by using
the Maiorana-McFarland construction involving nonlinear mappings
derived from
nonlinear codes.
7) C. Carlet and P.
Guillot. ``A new representation of Boolean functions", Proceedings of AAECC'13, Lecture Notes in Computer
Science 1719,
pp. 94-103 (1999).
Abstract:
We study a representation of Boolean functions (and more generally of
integer-valued / complex-valued functions), not used until now in
coding
and
cryptography, which
yields more information than the currently used representations,
on the combinatorial, spectral and cryptographic properties
of the functions.
8) A. Canteaut, C. Carlet, P. Charpin and C.
Fontaine. "Propagation characteristics and correlation-immunity of
highly
nonlinear Boolean functions", Proceedings of EUROCRYPT 2000, Advances in
Cryptology,
Lecture
Notes in Computer Science, no 187, pp. 507-522 (2000)
Abstract:
We investigate the link between the nonlinearity of a Boolean function
and its propagation characteristics. We prove that highly nonlinear
functions usually have good propagation properties regarding different
criteria. Conversely, any Boolean function satisfying the propagation
criterion with respect to a linear subspace of codimension~1 or~2 has
a high nonlinearity. We also point out that most highly nonlinear
functions with a three-valued Walsh spectrum can be transformed into
1-resilient functions.
9) C. Carlet. "A larger class of cryptographic Boolean functions via a
study of
the Maiorana-McFarland construction", CRYPT0 2002,
Advances
in Cryptology, Lecture Notes in Computer Science 2442, pp.
549-564
(2002)
Abstract:
Thanks to a new upper bound, we study more precisely the nonlinearities
of Maiorana-McFarland's resilient functions. We characterize those
functions with optimum nonlinearities and we give examples of functions
with high nonlinearities.
But these functions have a peculiarity which makes them potentially
cryptographically weak.
We study a natural super-class of Maiorana-McFarland's class whose
elements do not have the same drawback and we give examples of such
functions achieving high nonlinearities.
10) C. Carlet and A. Gouget. "An upper bound on the number of m-resilient Boolean
functions", ASIACRYPT 2002, Advances in
Cryptology,
Lecture Notes in Computer Science 2501, pp. 484-496, 2002.
Abstract:
The enumeration of m-resilient Boolean functions in n variables would
be a quite useful information for cryptography. But it seems to be an
intractable open problem. Upper and lower bounds have appeared in the
literature in the mid 80's. Since then, improving them has been the
goal of several papers. In this paper, we give a new upper bound which
partially improves upon all the known bounds.
11) C. Carlet
and E. Prouff. "On plateaued Boolean functions and their constructions". Proceedings of "Fast Software Encryption 2003",
Lecture Notes in Computer Science 2887, pp. 54-73, 2003.
Abstract:
We use the notion of covering sequence, introduced by C. Carlet and Y.
Tarannikov, to give a simple characterization of bent functions. We
extend it into a characterization of plateaued functions (that is bent
and three-valued functions). After recalling why the class of plateaued
functions provides good candidates to be used in cryptosystems, we
study the known families of plateaued functions and their drawbacks. We
show in particular that the class given as new by Zhang and Zheng is in
fact a subclass of Maiorana-McFarland's class. We introduce a new class
of plateaued functions and prove its good cryptographic properties.
12) C. Carlet and E. Prouff. "On a new notion of nonlinearity relevant to multi-output
pseudo-random generators", Proceedings of
"Selected Areas in Cryptography" 2003, Mitsuru Matsui et Robert J.
Zuccherato Eds., Lecture Notes in Computer Science 3006,pp. 291--305,
2004.
Abstract:
Vectorial functions (i.e. mappings from F_2^n into F_2^m,
also called S-boxes) can be used in pseudo-random generators with
multiple outputs. The notion of maximum correlation of these
S-boxes to linear functions, introduced by Zhang and
Chan, plays a central role in the resistance of the resulting
stream
ciphers to correlation attacks. It can be related to a notion of
``unrestricted nonlinearity''. We obtain a new lower bound on the
overall maximum correlation to linear functions of vectorial functions
which results in an upper bound on the unrestricted nonlinearity.
We compare it with the known upper bounds on the nonlinearity
(which are also valid for the unrestricted nonlinearity of balanced
functions). We study its tightness and we exhibit a class of
balanced functions whose nonlinearity and unrestricted nonlinearity are
high relatively to the upper-bounds.
13) W.
Meier, E. Pasalic and C. Carlet. ``Algebraic attacks and
decomposition of Boolean functions". Advances in
Cryptology,
EUROCRYPT
2004, Lecture Notes in Computer Science 3027, pp. 474-491, 2004.
Abstract:
Algebraic attacks on LFSR-based stream ciphers recover the secret key
by solving an overdefined system of multivariate algebraic equations.
They exploit multivariate relations involving key bits and output bits
and become very efficient if such relations of low degree may be found.
Low degree relations have been shown to exist for several well known
constructions of stream ciphers immune to all previously known attacks.
Such relations may be derived by multiplying the output function of a
stream cipher by a well chosen low degree function such that the
product function is again of low degree. In view of algebraic attacks,
low degree multiples of Boolean functions are a basic concern in the
design of stream ciphers as well as of block ciphers.
This paper investigates the existence of low degree multiples of
Boolean functions in several directions: The known scenarios under
which low degree multiples exist are reduced and simplified to two
scenarios, that are treated differently in algebraic attacks. A new
algorithm is proposed that allows to successfully decide whether a
Boolean function has low degree multiples. This represents a
significant step towards provable security against algebraic
attacks. Furthermore, it is shown that the Maiorana-McFarland class of
Boolean functions immanently has low degree multiples. Finally, the
probability that a random Boolean function has a low degree
multiple is estimated.
14) C.
carlet and E. Prouff. "Vectorial Functions and Covering Sequences", Proceedings of
Finite Fields and Applications, may 2003, Toulouse, Fq7, Lecture Notes in Computer Science 2948, G. L.
Mullen, A. Poli and H. Stichtenoth edts, pp. 215-248, 2004.
Abstract:
The design of large classes of highly nonlinear resilient vectorial
functions (mappings from F_2^n into F_2^m, also called
S-boxes) is needed for iterated block ciphers and for
pseudo-random
generators with multiple output. In this paper, we recall the
diverse
known constructions of such S-boxes, and we show that those which
provide good candidate functions are, in fact, all in the same class.
This class corresponds to a generalization of a well known construction
due to Maiorana and MacFarland. We study in detail this
construction
and we specify it to obtain good S-boxes. In a second part, we
generalize to S-boxes the notion of covering sequence. We show
that
this generalization has the same properties as for Boolean functions,
and that it has nice additional properties of
stability. We study how this notion can be used to design
attacks, and
we explain why some functions, including the elements of the new
class, cannot be involved in the construction of iterated
block
ciphers.
15) C. Carlet. ``On highly nonlinear S-boxes and their inability to thwart DPA
attacks", Indocrypt 2005, Lecture Notes in Computer Science
3797, pp. 49-62, 2005. See the completed version in IACR e-print
archive.
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).
16) C. Carlet. ``On bent and highly nonlinear balanced/resilient functions and
their algebraic immunities", AAECC 16, Lecture Notes in Computer Science 3857, pp.
1-28, 2006.
Abstract:
Since the introduction of the notions of nonlinearity in the mid-70's
(the term has been in fact introduced later), of correlation immunity
and resiliency in the mid-80's, and of algebraic immunity
recently,
the problem of efficiently constructing Boolean functions
satisfying, at high levels, one or several of these criteria has
received much attention. Only few primary constructions are known, and
secondary constructions are also necessary to obtain functions
achieving or approaching the best possible
cryptographic characteristics.
After recalling the background on cryptographic criteria and making
some general observations, we try to give a survey of all these
constructions and their properties.
We then show that a nice and simple property of Boolean functions leads
to a general secondary construction building an $n$-variable function
from three known $n$-variable functions. This construction generalizes
secondary constructions recently obtained for Boolean bent functions
and also leads to secondary constructions of highly nonlinear balanced
or resilient functions, with potentially better algebraic immunities
than the three functions used as building blocks.
17) F. Armknecht, C. Carlet, P. Gaborit, S. Kuenzli, W. Meier and O.
Ruatta. ``Efficient Computation of Algebraic Immunity for Algebraic and
Fast Algebraic Attacks".
Advances in Cryptology, EUROCRYPT 2006, Lecture Notes in
Computer Science 4004 , pp. 147-164, 2006.
Abstract:
In this paper we propose several efficient algorithms for assessing the
resistance of Boolean functions against algebraic and fast algebraic
attacks when implemented in LFSR-based stream ciphers.
An algorithm is described which permits to compute the algebraic
immunity $d$ of a Boolean function with $n$ variables in
$\mathcal{O}(D^2)$ operations, for $D \approx \binom{n}{d}$, rather
than in $\mathcal{O}(D^3)$ operations necessary in all previous
algorithms. Our algorithm is based on multivariate polynomial
interpolation.
For assessing the vulnerability of arbitrary Boolean functions with
respect to fast algebraic attacks, an efficient generic algorithm is
presented that is not based on interpolation. This algorithm is
demonstrated to be particularly efficient for symmetric Boolean
functions. As an application it is shown that large classes of
symmetric functions are very vulnerable to fast algebraic attacks
despite their proven resistance against conventional algebraic attacks.
18) C. Carlet, P. Guillot
and S. Mesnager. ``On immunity profile of Boolean functions". SETA (International Conference on Sequences and
their Applications) 2006. Lecture Notes in Computer Science 4086, pp.
364-375, 2006.
Abstract:
The notion of resilient function has been recently weakened to
match more properly the features required for Boolean functions
used in stream ciphers. We introduce and we study an alternate
notion of almost resilient function. We show that it corresponds more
closely to the requirements that make the cipher more resistant to
precise attacks.
19) C. Carlet. ``On the higher order nonlinearities of algebraic immune
functions". CRYPTO 2006. Lecture Notes in
Computer Science 4117, pp. 584-601, 2006.
Abstract:
One of the most basic requirements concerning Boolean
functions used in cryptosystems is that they must have high algebraic
degrees. This simple criterion is not always well adapted to the
concrete situation in which Boolean functions are used in
symmetric cryptography, since changing one or several output bits of a
Boolean function considerably changes its algebraic degree while it may
not change its robustness. The proper characteristic is the $r$-th
order nonlinearity profile (which includes the first-order
nonlinearity). However, studying it is difficult and almost no paper,
in the literature, has ever been able to give general effective results
on it. The values of the nonlinearity profile are known for very few
functions and these functions have little cryptographic interest. A
recent paper has given a lower bound on the nonlinearity profile of
functions, given their algebraic immunity. We improve upon it, and we
deduce that it is enough, for a Boolean function, to have high
algebraic immunity, for having non-weak low order nonlinearity profile
(even when it cannot be evaluated), except maybe for the first order.
20) C. Carlet, K. Khoo, C.-W. Lim and C.-W. Loe. ``Generalized Correlation Analysis of Vectorial Boolean Functions".
Proceedings of "Fast
Software Encryption 2007", Lecture Notes in Computer Science 4593,
Springer-Verlag, pp. 382-398, 2007.
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)$. Based on experimental results, we observe that the new
generalized correlation attack gives linear approximation with much
higher bias than the Zhang-Chan and usual correlation attacks. Thus it
can be more effective than previous methods.
First, the complexity for computing the generalized nonlinearity for
this new attack is reduced from $2^{2^m \times n+n}$ to $2^{2n}$.
Second, we prove a theoretical upper bound for generalized nonlinearity
which is much lower than the unrestricted nonlinearity (for
Zhang-Chan's attack) or usual nonlinearity. This again proves that
generalized correlation attack performs better than previous
correlation attacks. Third, we introduce a generalized
divide-and-conquer correlation attack and prove that the usual notion
of resiliency is enough to protect against it. Finally, we deduce the
generalized nonlinearity of some known secondary constructions for
secure vector Boolean functions.
21) C. Carlet and
K. Feng. ``An infinite
class of balanced functions with optimal algebraic immunity, good
immunity to fast algebraic attacks and good nonlinearity". Proceedings
of ASIACRYPT 2008, Lecture Notes in Computer Science} 5350, pp.
425-440, 2008.
Abstract:
After the improvement by Courtois and Meier of the algebraic attacks on
stream ciphers and the introduction of the related notion of algebraic
immunity, several constructions of infinite classes of Boolean
functions with optimum algebraic immunity have been proposed. All of
them gave functions whose algebraic degrees are high enough for
resisting the Berlekamp-Massey attack and the recent R\o njom-Helleseth
attack, but whose nonlinearities either achieve the worst possible
value (given by Lobanov's bound) or are slightly superior to it. Hence,
these functions do not allow resistance to fast correlation attacks.
Moreover, they do not behave well with respect to fast algebraic
attacks.
In this paper, we study an infinite class of functions which achieve an
optimum algebraic immunity. We prove that they have an optimum
algebraic degree and a much better nonlinearity than all the previously
obtained infinite classes of functions.
We check that, at least for small values of the number of variables,
the functions of this class have in fact a very good nonlinearity and
also a good behavior against fast algebraic attacks.
22) C. Carlet and K. Feng. An infinite class of balanced vectorial Boolean functions with
optimum algebraic immunity and good nonlinearity.
Proceedings of IWCC 2009, Lecture Notes in Computer Science 5557,
pp.
1-11, 2009.
Abstract:
In this paper, we study the cryptographic properties of an infinite
class of balanced vectorial Boolean functions recently introduced by
Feng, Liao and Yang. These functions provably achieve an optimum
algebraic immunity. We give a simpler proof of this fact and we prove
that these functions have also an optimum algebraic degree and a
non-weak nonlinearity.
23) C. Carlet. On known and new differentially uniform functions.
Proceedings of the 16th Australasian Conference on Information Security
and Privacy ACISP 2011, Lecture Notes in Computer Science 6812, pages
1-15, 2011.
Abstract:
We give a survey on the constructions of APN and differentially
4-uniform functions suitable for designing S-boxes for block ciphers.
We recall why the search for more of such functions is necessary. We
propose a way of designing functions which can possibly be APN or
differentially 4-uniform and be bijective. We illustrate it with an
example of a differentially 4-uniform $(n,n)$-permutation for $n$ odd,
based on the power function $x^3$ over the second order Galois
extension of $F_{2^{n+1}}$, and related to the Dickson
polynomial $D_3$ over this field. These permutations have optimal
algebraic degree and their nonlinearity happens to be rather good (but
worse than that of the multiplicative inverse functions).
24) C. Carlet, L. Goubin, E.
Prouff, M. Quisquater et M. Rivain. Higher-Order Masking Schemes for S-Boxes. Fast Software
Encryption FSE 2012, Lecture Notes in Computer Science 7549 , pp.
366-384, 2012.
Abstract:
Masking is a widely used countermeasure to protect block cipher
implementations against side-channel attacks. The principle is to
randomly split every sensitive intermediate vari- able occurring
in the computation into d + 1 shares, where d is called the masking
order and plays the role of security parameter. Indeed, it has
been shown that under certain assumptions, the difficulty of
carrying out a side-channel attack grows exponentially with the masking
order. The main issue while applying masking to protect a block
cipher implementation is to design an efficient scheme for the
s-box computations. Actually, higher-order masking schemes with
arbitrary order as security parameter only exist for Boolean
circuits and for the AES s-box. Although any s-box can be
represented as a Boolean circuit, applying such a strategy leads to
inefficient implementation in software. The design of an efficient and
generic higher-order scheme is hence until now an open problem.
In this paper, we introduce the first masking scheme which can be
ap- plied in software to efficiently protect any s-box at any
order. We first describe a general masking method and we introduce
a new criterion for an s-box that relates to the best efficiency
achievable with this method. Then we propose concrete schemes
that aim to approach the criterion. Specif- ically, we give
optimal methods for the set of power functions, and we give efficient
heuristics for the general case. As an illustration we apply our
scheme to the DES and PRESENT s-boxes and we provide
implementation results.
25) H. Maghrebi, C. Carlet, S.
Guilley et J.-L. Danger. Optimal First-Order Masking with Linear and Non-Linear
Bijections. AFRICACRYPT 2012, Lecture Notes in Computer Science 7374, pp.
360-377, 2012.
Abstract:
Hardware devices can be protected against side-channel attacks by
introducing one random mask per sensitive variable. The computation
throughout is unaltered if the shares (masked variable and mask)
are processed concomitantly, in two distinct registers. Nonetheless,
this setup can be attacked by a zero-offset second-order CPA attack. The
countermeasure can be improved by manipulating the mask through a
bijection F , aimed at reducing the dependency between the shares. Thus
dth-order zero-offset attacks, that consist in applying CPA on the dth
power of the centered side-channel traces, can be thwarted for d ≥
2.
We denote by n the size in bits of the shares and call F the
transformation function, that is a bijection of Fn2 . In this paper, we
explore the functions F that thwart zero-offset HO-CPA of maximal order
d. We mathematically demonstrate that optimal choices for F relate to
optimal binary codes (in the sense of communication theory). First, we
exhibit optimal linear F functions. Second, we note that for n values
where non-linear codes exist, better non-linear F can be found. These
results are exemplified in the case n = 8, where we identify the optimal
F : it is derived from the optimal rate 1/2 binary code of size 2n,
namely the Nordstrom-Robinson (16, 256, 6) code. This example provides
explicitly with the optimal protection that limits to one mask of
byte-oriented algorithms such as AES or AES-based SHA-3 candidates. It
protects against all zero-offset HO-CPA attacks of order d ≤ 5.
Eventually, the countermeasure is shown to be resilient to imperfect
leakage models.
26) G. Piret, T. Roche and C. Carlet. PICARO -- A Block Cipher Allowing
Efficient Higher-Order Side-Channel Resistance. Proceedings of ACNS 2012, Lecture Notes in Computer Science 7341,
pp. 311-328, 2012.
Abstract:
Many papers deal with the problem of constructing an efficient masking
scheme for existing block ciphers. We take the reverse approach: that
is, given a proven masking scheme (Rivain and Prouff, CHES 2010) we
design a block cipher that fits well the masking constraints. The most
important step is to choose an adequate S-box. We then discuss the
design and security problems that come from the fact that the S-box we
chose is not bijective. A complete design of the cipher is given, as
well as some implementation results.
27) C. Carlet, J.-L. Danger, S. Guilley and H. Maghrebi. Leakage
Squeezing of Order Two. Proceedings of INDOCRYPT 2012, Lecture Notes in Computer Science 7668, pp.
120-139, 2012.
Abstract:
In masking schemes, leakage squeezing is the study of the optimal
shares’ representation, that maximizes the resistance order
against high-order side-channel attacks. Squeezing the leakage of
first-order Boolean masking has been problematized and solved
previously in [8]. The solution consists in finding a bijection F that
modifies the mask, in such a way that its graph, seen as a code, be of
greatest dual distance. This paper studies second-order leakage
squeezing, i.e. leakage squeezing with two independent random masks. It
is proved that, compared to first-order leakage squeezing, second-order
leakage squeezing at least increments (by one unit) the resistance
against high-order attacks, such as high order correlation power
analyses (HO-CPA). Now, better improvements over first-order leakage
squeezing are possible by relevant constructions of squeezing
bijections. We provide with linear bijections that improve by strictly
more than one (instead of one) the resistance order. Specifically, when
the masking is applied on bytes (which suits AES), resistance against
1st-order (resp. 2nd-order) attacks is possible with one (resp. two)
masks. Optimal leakage squeezing with one mask resists HO-CPA of orders
up to 5. In this paper, with two masks, we provide resistance against
HO-CPA not only of order 5 + 1 = 6, but also of order 7.
28) C. Carlet. Correlation-Immune Boolean Functions for Leakage
Squeezing and Rotating S-Box Masking against Side Channel Attacks.
Proceedings of SPACE 2013, Lecture Notes in Computer Science 8204, pp. 70-74, 2013.
(Extended abstract)
29) C. Carlet, D.
Tang, X. Tang and Q. Liao. New Construction of Differentially 4-Uniform
Bijections. Proceedings of INSCRYPT 2013, 9th International Conference,
Guangzhou, China, November 27-30, 2013, Lecture Notes in Computer
Science 8567, pp. 22-38, 2014.
Abstract:
Block ciphers use Substitution boxes (S-boxes) to create confusion into
the cryptosystems. For resisting the known attacks on these
cryptosystems, the following criteria for functions are mandatory: low
differential uniformity, high nonlinearity and not low algebraic degree.
Bijectivity is also necessary if the cipher is a
Substitution-Permutation Network, and balancedness makes a Feistel
cipher lighter.
It is well-known that almost perfect nonlinear (APN) functions have the
lowest differential uniformity 2 (the values of differential uniformity
being always even) and the existence of APN bijections over $\F_{2^n}$
for even $n\ge 8$ is a big open problem.
In real practical applications, differentially 4-uniform bijections can
be used as S-boxes when the dimension is even. For example, the AES
uses a differentially 4-uniform bijection over $\F_{2^8}$.
In this paper, we first propose a method for constructing a large
family of differentially 4-uniform bijections in even dimensions.
This method can generate at least
$\big(2^{n-2}-\lfloor2^{n/2-1}\rfloor-1\big)\cdot 2^{2^{n-1}}$ such
bijections having maximum algebraic degree $n-1$.
Furthermore, we exhibit a subclass of functions having high
nonlinearity and being CCZ-inequivalent to all known differentially
4-uniform power bijections and to quadratic functions.
30) J. Bringer, C. Carlet, H. Chabanne, S. Guilley and H. Maghrebi.
Orthogonal Direct Sum Masking, A Smartcard Friendly Computation Paradigm
in a Code, with Builtin Protection against Side-Channel and Fault
Attacks. Proceedings of WISTP 2014. Lecture Notes in Computer Science 8501, pp. 40-56, 2014.
Abstract:
Secure elements, such as smartcards or trusted platform modules (TPMs),
must be protected against implementation-level attacks. Those include
side-channel and fault injection attacks. We in- troduce ODSM,
Orthogonal Direct Sum Masking, a new computation paradigm that achieves
protection against those two kinds of attacks. A large vector space is
structured as two supplementary orthogonal sub- spaces. One subspace
(called a code C) is used for the functional computa- tion, while the
second subspace carries random numbers. As the random numbers are
entangled with the sensitive data, ODSM ensures a protection against
(monovariate) side-channel attacks. The random numbers can be checked
either occasionally, or globally, thereby ensuring a detec- tion
capability. The security level can be formally detailed: it is proved
that monovariate side-channel attacks of order up to dC − 1, where d is
the minimal distance of C, are impossible, and that any fault of Ham-
ming weight strictly less than dC is detected. A complete instantiation
of ODSM is given for AES. In this case, all monovariate side-channel at-
tacks of order strictly less than 5 are impossible, and all fault
injections perturbing strictly less than 5 bits are detected.
31) C. Carlet, G. Gao, W. Liu. Results on Constructions of Rotation
Symmetric Bent and Semi-bent Functions. Proceedings of SETA 2014. Lecture Notes in Computer Science
8865, pp. 21-33, 2014.
Abstract:
In this paper, we introduce a class of cubic rotation symmetric
(RotS) functions and prove that it can yield bent and semi-bent
functions. To the best of our knowledge, this is the second primary
construction of an infinite class of nonquadratic RotS bent
functions which could be found and the first class of nonquadratic
RotS semi-bent functions. We also study a class of idempotents (giving
RotS functions through the choice of a normal basis of $GF(2^n)$ over
$GF(2)$). We derive a characterization of the bent functions among these
idempotents and we relate their precise determination to a problem
studied in the framework of APN functions. Incidentally, the proofs of
bentness given here are useful for a paper studying a construction of
idempotents from RotS functions, entitled ``A secondary construction and
a transformation on rotation symmetric functions, and their action on
bent and semi-bent functions'' by the same authors, to appear in the
journal JCT series A.
32) C. Carlet. Open Questions on Nonlinearity and on APN
Functions. Proceedings of Arithmetic of Finite Fields 5th
International Workshop, WAIFI 2014, Gebze, Turkey, September 27-28,
2014, Lecture Notes in Computer Science 9061, pp. 83-107, 2015.
Abstract:
In a first part of the paper, we recall some known open questions
on the nonlinearity of Boolean and vectorial functions and on the
APN-ness of vectorial functions. All of them have been extensively
searched and seem quite difficult. We also indicate related less
well-known open questions. In the second part of the paper, we introduce
four new open problems (leading to several related sub-problems) and
the results which lead to them. Addressing these problems may be less
difficult since they have not been much worked on.
33) L. Budaghyan, C. Carlet, T. Helleseth, A. Kholosha. On
o-Equivalence of Niho Bent Functions. Proceedings of Arithmetic of
Finite Fields 5th International Workshop, WAIFI 2014, Gebze, Turkey,
September 27-28, 2014, Lecture Notes in Computer Science 9061, pp.
155-168, 2015.
Abstract:
As observed recently by the second author and S. Mesnager, the
projective equivalence of o-polynomials defines, for Niho bent
functions, an equivalence relation called o-equivalence. These authors
also observe that, in general, the two o-equivalent Niho bent functions
defined from an o-polynomial $F$ and its inverse $F^{-1}$ are
EA-inequivalent. In this paper we continue the study of o-equivalence.
We study a group of order 24 of transformations preserving o-polynomials
which has been studied by Cherowitzo 25 years ago. We point out that
three of the transformations he included in the group are not correct.
We also deduce two more transformations preserving
o-equivalence but providing potentially EA-inequivalent bent functions.
We exhibit examples of infinite classes of o-polynomials for which at
least three EA-inequivalent Niho bent functions can be derived.
34) C. Carlet. On the properties of vectorial functions with plateaued
components and their consequences on APN functions. Proceedings of the First International Conference, C2SI 2015, Rabat,
Morocco, May 26–28, 2015, In Honor of Thierry Berger. Lecture Notes in Computer Science 9084, pp. 63-73.
Abstract:
Boolean plateaued functions and vectorial functions with plateaued
components, that we simply call plateaued, play a significant role in
cryptography, but little is known on them. We give here, without proofs,
new characterizations of plateaued Boolean and vectorial functions, by
means of the value distributions of derivatives and of power moments of
the Walsh transform. This allows us to derive several
characterizations of APN functions in this framework, showing that all
the main results known for quadratic APN functions extend to plateaued
functions. Moreover, we prove that the APN-ness of those plateaued
vectorial functions whose component functions are unbalanced
depends only on their value distribution. This proves that any
plateaued $(n,n)$-function, $n$ even, having same value
distribution as APN power functions, is APN and has same extended Walsh
spectrum as the APN Gold functions.
35) C. Carlet, E. Prouff, M. Rivain and T. Roche. Algebraic
Decomposition for Probing Security. Proceedings of CRYPTO 2015, Lecture
Notes in Computer Science 9215, pp. 742-763, 2015.
Abstract:
The probing security model is very popular to prove the side- channel
security of cryptographic implementations protected by masking. A common
approach to secure nonlinear functions in this model is to rep- resent
them as polynomials over a binary field and to secure their nonlin- ear
multiplications by involving the Ishai-Sahai-Wagner (ISW) scheme.
Several schemes based on this approach have been published, leading to
the recent proposal of Coron, Roy, and Vivek (CRV) which is cur- rently
the best known method when no particular assumption is made on the
algebraic structure of the function. In the present paper, we revisit
this issue by trading nonlinear multiplications for low-degree
evaluations. Specifically, we introduce an algebraic decomposition
approach in which a nonlinear function is represented as a sequence of
functions with low algebraic degrees. We therefore focus on the
probing-secure evaluation of such low-degree functions and we introduce
three novel methods to tackle this particular issue. The paper concludes
with a comparative analysis of the proposals, which shows that our
algebraic decomposition method outperforms CRV in several realistic
contexts.
36) C. Carlet. S-boxes, Boolean functions and codes for the resistance
of block ciphers to cryptographic attacks, with or without side
channels. Proceedings of SPACE 2015, Lecture Notes in Computer Science 9354, pp. 151-171, 2015.
Abstract:
The choice of functions $S: \gf_2^n\mapsto \gf_2^m$ to be used as
substitution boxes (S-boxes), fastly implementable and contributing to
resisting attacks is a crucial question for the design of block ciphers.
We summary the state of the art in this domain, considering also
the case $m<n$ which has been less studied. We also recall the method
for protecting block ciphers against side channel attacks (SCA) by
masking, and how the S-boxes can be processed in order to ensure this
protection. We state a related open problem, also interesting for its
own sake. We eventually see how Boolean functions, vectorial functions
and error correcting codes can be used in different ways for reducing
the cost of masking while keeping the same resistance to some SCA and
also for allowing resisting fault injection attacks (FIA).
37) S. Picek, S. Guilley, C. Carlet, D. Jakobovic, and J. F. Miller.
Evolutionary Approach for Finding Correlation Immune Boolean Functions
of Order t with Minimal Hamming Weight. Proceedings of TPNC 2015.
Lecture Notes in Computer Science 9477, pp. 71-82, 2015
Abstract:
The role of Boolean functions is prominent in several ar- eas like
cryptography, sequences and coding theory. Therefore, various methods to
construct Boolean functions with desired properties are of direct
interest. When concentrating on Boolean functions and their role in
cryptography, we observe that new motivations and hence new proper- ties
have emerged during the years. It is important to note that there are
still many design criteria left unexplored and this is where
Evolutionary Computation can play a distinct role. One combination of
design criteria that has appeared recently is finding Boolean functions
that have various orders of correlation immunity and minimal Hamming
weight. Surpris- ingly, most of the more traditionally used methods for
Boolean function generation are inadequate in this domain. In this
paper, we concentrate on a detailed exploration of several evolutionary
algorithms and their applicability for this problem. Our results show
that such algorithms are a viable choice when evolving Boolean functions
with minimal Hamming weight and certain order of correlation immunity.
This approach is also successful in obtaining Boolean functions with
several values that were known previously to be theoretically optimal,
but no one succeeded in finding actual Boolean functions with such
values.
38) P. Méaux, A. Journault, F.-X. Standaert and C. Carlet.
Towards Stream Ciphers for Efficient FHE with Low-Noise Ciphertexts.
Proceedings of EUROCRYPT 2016, Lecture Notes in Computer Science 9665, pp. 311-343, 2016.
Abstract:
Symmetric ciphers purposed for Fully Homomorphic Encryption (FHE) have
recently been proposed for two main reasons. First, minimizing the
implementation (time and memory) overheads that are inherent to current
FHE schemes. Second, improving the homomorphic capacity, i.e. the amount
of operations that one can perform on homomorphic ciphertexts before
boot- strapping, which amounts to limit their level of noise. Existing
solutions for this purpose suggest a gap between block ciphers and
stream ciphers. The first ones typically allow a constant but small
homomorphic capacity, due to the iteration of rounds eventually leading
to complex Boolean functions (hence large noise). The second ones
typically allow a larger homomorphic capacity for the first ciphertext
blocks, that decreases with the number of ciphertext blocks (due to the
increasing Boolean complexity of the stream ciphers’ output). In this
paper, we aim to combine the best of these two worlds, and propose a new
stream cipher construction that allows constant and small(er) noise.
Its main idea is to apply a Boolean (filter) function to a public bit
permutation of a constant key register, so that the Boolean complexity
of its outputs is constant. We then propose an instantiation of filter
that is designed to exploit recent (3rd-generation) FHE schemes, where
the error growth is quasi-additive when adequately multiplying
ciphertexts with the same amount of noise. We finally analyze the
cryptanalytic security and noise of a couple of instances of this new
stream cipher, and conclude by highlighting its excellent properties
regarding the other goal of minimizing time and memory overheads.
39) C. Carlet, S. Mesnager, F. Ozbudak and A. Sinak. Explicit
Characterizations for Plateaued-ness of p-ary (Vectorial)
Functions. Proceedings of C2SI 2017, LNCS volume 10194, pp. 328-345, 2017.
Abstract:
Plateaued (vectorial) functions have an important role in the sequence
and cryptography frameworks. Given their importance, they
have not been studied in detail in general framework. Several
researchers found recently results on their characterizations and
introduced new tools to understand their structure and to design such
functions
In this work, we mainly extend some of the observations made in
characteristic $2$ and given in [C. Carlet, IEEE T INFORM THEORY 61(11),
2015] to arbitrary characteristic.
We first extend to arbitrary characteristic the characterizations
of plateaued (vectorial) Boolean functions by the autocorrelation
functions, next their characterizations in terms of the
second-order derivatives, and finally their characterizations via the
moments of the Walsh transform.
\keywords{Vectorial functions, $p$-ary functions, bent functions, plateaued functions.
40) C. Carlet, A. Heuser and S. Picek. Trade-offs for S-boxes:
Cryptographic Properties and Side-channel Resilience. Proceedings of
ACNS 2017, Lecture Notes in Computer Science 10355, pp. 393-414, 2017.
Abstract:
When discussing how to improve side-channel resilience of a cipher, an
obvious direction is to use various masking or hiding countermeasures.
However, such schemes come with a cost, e.g. an increase in the area
and/or reduction of the speed. When considering lightweight cryptography
and various constrained environments, the situation becomes even more
difficult due to numerous implementation restrictions.
However, some options are possible like using S-boxes that are easier to
mask or (more on a fundamental level), using S-boxes that possess
higher inherent side-channel resilience.
In this paper we investigate what properties should an S-box possess in
order to be more resilient against side-channel attacks. Moreover, we
find certain connections between those properties and cryptographic
properties like nonlinearity and differential uniformity. Finally, to
strengthen our theoretical findings, we give an extensive experimental
validation of our results.
41) R. Poussier, Q. Guo, F.-X. Standaert, C. Carlet and S. Guilley.
Connecting and Improving Direct Sum Masking and Inner Product Masking.
Proceedings of CARDIS 2017, Lecture Notes in Computer Science 10728, pp.
123-141, 2017.
Abstract:
Direct Sum Masking (DSM) and Inner Product (IP) masking are two types of
countermeasures that have been introduced as alternatives to simpler
(e.g., additive) masking schemes to protect cryptographic
implementations against side-channel anal- ysis. In this paper, we first
show that IP masking can be written as a particular case of DSM. We
then analyze the improved security properties that these (more complex)
encodings can provide over Boolean masking. For this purpose, we
introduce a slight variation of the probing model, which allows us to
provide a simple explanation to the “security order amplification” for
such masking schemes that was put forward at CARDIS 2016. We then use
our model to search for new instances of masking schemes that optimize
this security order amplification. We finally discuss the relevance of
this security order amplification (and its underlying assumption of
linear leakages) based on an experimental case study.
42) C. Carlet, C. Guneri, S. Mesnager and F. Ozbudak. Construction of
Some Codes Suitable for Both Side Channel and Fault Injection Attacks.
Proceedings of WAIFI 2017, Lecture Notes in Computer Science 11321, pp.95-107, 2018.
Abstract:
Using algebraic curves over finite fields, we construct some codes
suitable for being used in the countermeasure called Direct Sum Masking
which allows, when properly implemented, to protect the whole cryptographic block cipher algorithm
against side channel attacks and fault injection attacks,
simultaneously. These codes address a problem which has its own interest
in coding theory.
43) P. M\'eaux, C. Carlet, A. Journault and F.-X. Standaert. Improved
Filter Permutators for Efficient FHE: Better Instances and
Implementations. Proceedings of INDOCRYPT 2019, Lecture Notes in Computer Science 11898, pp. 68-91, 2019.
Abstract:
We revisit the design of filter permutators as a general approach to
build stream ciphers that can be efficiently evaluated in a fully
homomorphic manner. We first introduce improved filter permutators that
allow better security analyses, instances and implementations than the
previously proposed $\FLIP$ family of stream ciphers. We also put
forward the similarities between these improved constructions and a
popular PRG design by Goldreich. We then propose a methodology to
evaluate the performance of such symmetric cipher designs in a FHE
setting, which primarily focuses on the noise level of the symmetric
ciphertexts (hence on the amount of operations on these ciphertexts that
can be homomorphically evaluated). Evaluations performed with HElib
show that instances of improved filter permutators using direct sums of
monomials as filter outperform all existing ciphers in the literature
based on this criteria. We also discuss the (limited) overheads of these
instances in terms of latency and throughput. Finally, and motivated by
the similarity between improved filter permutators and Goldreich's PRG,
we investigate the use of $\XORMAJ$ functions as an alternative to
filters based on direct sums of monomials. We develop new Boolean
functions' techniques and refine Goldreich's locality bound for this
purpose (which is of independent interest). We conclude the paper with
an asymptotic analysis of the noise level of improved filter permutators
instances using $\XORMAJ$ functions, and recommend them as good
candidates for evaluation with a third-generation FHE scheme.
44) C. Carlet, M. Djurasevic, D. Jakobovic and S. Picek. A Search for
Additional Structure: The Case of Cryptographic S-boxes. PPSN (2) 2020,
Lecture notes in Computer Science 12270, pp. 343-356, 2020.
Abstract:
We ask a question whether it is possible to evolve cryptographically
strong S-boxes that have additional constraints on their structure. We
investigate two scenarios: where S-boxes additionally have a specific
sum of values in rows or columns and the scenario where we check that
the difference between the Hamming weights of inputs and outputs is
minimal. The first case represents an interesting benchmark problem,
while the second one has practical ramifications as such S-boxes could
offer better resilience against side-channel attacks.
We investigate three solution representations by using the permutation,
integer, and cellular automata-based encoding. Our results show that it
is possible to find S-boxes with excellent cryptographic properties
(even optimal ones) and reach the required sums of rows and columns.
Unfortunately, for the most promising S-box representation based on
trees and cellular automata rules, we did not succeed in finding S-boxes
with small differences in the Hamming weights between the inputs and
outputs, which opens an interesting future research direction. Finally,
our results for this scenario and different encodings enabled us to
observe a property of S-boxes that was not known before, where we
mathematically proved that the values reached by evolutionary algorithms
are the best possible ones.
45) C. Carlet. On APN functions whose graphs are maximal Sidon
sets. Latin American Symposium on Theoretical Informatics 2022,
Lecture Notes in Computer Science 13568, pp. 243-254, Springer, 2022.
Abstract:
The graphs ${\cal G}_F=\{(x,F(x)); x\in \mathbb{F}_2^n\}$ of those
$(n,n)$-functions $F:\mathbb{F}_2^n\mapsto \mathbb{F}_2^n$ that are
almost perfect nonlinear (in brief, APN; an important notion in
symmetric cryptography) are, equivalently to their original definition
by K. Nyberg, those Sidon sets (an important notion in
combinatorics) $S$ in $({\Bbb F}_2^n\times {\Bbb F}_2^n,+)$ such that,
for every $x\in {\Bbb F}_2^n$, there exists a unique $y\in {\Bbb F}_2^n$
such that $(x,y)\in S$. Any subset of a Sidon set being a Sidon set, an
important question is to determine which Sidon sets are maximal
relatively to the order of inclusion. In this paper, we study whether
the graphs of APN functions are maximal Sidon sets. We show that this
question is related to the problem of the existence / non-existence of
APN functions of algebraic degree $n$ and we revisit the conjectures
that have been made on this latter problem.
Other full papers in proceedings
of international conferences:
1) ``Boolean functions on finite fields of characteristic 2", C.
Carlet, EUROCODES'92, CISM Courses and Lectures no 339, pp.
121-133
(1993).
Abstract:
The boolean functions on the finite fields of
characteristic 2 play a central part in two important topics of the
algebraic coding theory : the Reed-Muller codes (and their subcodes)
and the primitive BCH codes. They also are of a great interest in
cryptography.
Astonishingly enough, the field structure is not much used in the known
results of these topics and in their proofs, since the boolean
functions are generally expressed as polynomials in several variables
(the field being considered as a GF(2)-space, the variables are the
coordinates relatively to a base of that space).
It happens that nice properties may be pointed out and used.
We obtain as a corollary a new proof of a recent result on BCH codes.
2) ``Hyperbent functions", C. Carlet, Proceedings of
PRAGOCRYPT'96,
Czech
Technical University Publishing House, Prague, pp. 145-155 (1996).
Abstract:
We determine those Boolean functions on (GF(2))^m (m even) such that,
for a given even integer k, any of the Boolean functions on
(GF(2))^{m-k} obtained by fixing k coordinates of the variable is bent.
3) "On the algebraic thickness and non-normality of Boolean function",
C. Carlet, Proceedings of "2003 IEEE Information Theory
Workshop",
Paris,
France, pp. 147-150, 2003.
Abstract:
Cryptographic Boolean functions must be complex to satisfy Shannon's
principle of confusion. The two main criteria evaluating, from
cryptographic viewpoint, the complexity of Boolean functions on
F_2^n are the nonlinearity and the algebraic degree. Two other
criteria have also been considered: the algebraic thickness and the
non-normality. It is known that, asymptotically, almost all
Boolean functions have high algebraic thicknesses and are
deeply non-normal, as well as they have high algebraic degrees
and high nonlinearities. We improve upon this result and,
recalling a relationship between non-normality and nonlinearity, we
prove a new result on symmetric functions, which implies as a
direct consequence the known results on their nonlinearities (this
gives some new insight on the reasons of their behavior).
4) "On the supports of the Walsh transforms of Boolean functions", C.
Carlet and S. Mesnager. Proceedings of BFCA (First Workshop on Boolean
Functions : Cryptography and Applications), Rouen, March 2005,
Publications des Universités de Rouen et du Havre, pp. 65-82,
2005.
Abstract:
In this paper, we study, in relationship with covering sequences, the
structure of those subsets of F_2^n which can be the
Walsh supports of Boolean functions.
5) "On the construction of balanced Boolean functions with a good
algebraic immunity", C. Carlet and P. Gaborit. Proceedings of BFCA
(First Workshop on Boolean
Functions : Cryptography and Applications), Rouen, March 2005,
Publications des Universités de Rouen et du Havre, pp. 1-20,
2005.
Abstract:
In this paper we study the algebraic immunity of Boolean functions and
consider in particular the problem of constructing Boolean functions
with a good algebraic immunity. We
first give heuristic arguments to prove that the algebraic immunity of
a random Boolean function on n variables is at least the integer part
of n/2 with a very high probability (while the upper
bound is the ``ceiling" of
n/2). We give an upper bound, under a reasonable assumption,
on the algebraic immunity of Boolean functions constructed through
Maiorana-MacFarland construction. We give a construction which strictly
increases the algebraic immunity of a Boolean function by adding a
certain number of new variables and deduce the first infinite family of
functions with a non trivial proven algebraic immunity. At last we give
examples of balanced functions with optimal algebraic immunity and a
good nonlinearity and of balanced functions with a good algebraic
immunity, a good nonlinearity and a good correlation immunity, which
can be used for cryptographic purposes.
6) "New Classes of Almost Bent and Almost Perfect Nonlinear
Polynomials", L. Budaghyan, C. Carlet and A. Pott. Proceedings of WCC,
pp. 306-315, Bergen, 2005.
Abstract:
We construct infinite classes of almost bent and almost perfect
nonlinear polynomials, which are affinely inequivalent to power
functions.
7) ``The complexity of Boolean
functions from cryptographic
viewpoint", C. Carlet. Dagstuhl Seminar ``Complexity of Boolean
Functions" 2006, M. Krause, P. Pudlak, R. Reischuk and D.
van Melkebeek Eds. http://drops.dagstuhl.de/portals/06111/
Abstract:
Cryptographic Boolean functions must be complex to satisfy Shannon's
principle of confusion. But the cryptographic viewpoint on complexity
is not the same as in circuit complexity.
The two main criteria evaluating the cryptographic complexity of
Boolean functions on $F_2^n$ are the nonlinearity (and more generally
the $r$-th order nonlinearity, for every positive $r< n$) and the
algebraic degree. Two other criteria have also been considered: the
algebraic thickness and the non-normality. After recalling the
definitions of these criteria and why, asymptotically, almost all
Boolean functions are deeply non-normal and have high algebraic
degrees, high ($r$-th order) nonlinearities and high algebraic
thicknesses, we study the relationship between the $r$-th order
nonlinearity and a recent cryptographic criterion called the algebraic
immunity. This relationship strengthens the reasons why the algebraic
immunity can be considered as a further cryptographic complexity
criterion.
8) ``Another class of quadratic APN binomials over F_{2^n}: the case n
divisible by 4", with L. Budaghyan and G. Leander, Workshop on Coding
and Cryptography, pp. 49-58, 2007.
Abstract:
We exhibit an infinite class of almost perfect nonlinear quadratic
binomials from F_{2^{n}} to F_{2^{n}} with n=4k and k odd. We
prove
that these functions are CCZ-inequivalent to known APN power functions
when k is not equal to 1. In particular it means that for n=12,20,28,
they are CCZ-inequivalent to any power function.
9) ``Constructing balanced functions with optimum
algebraic immunity, IEEE International Symposium on Information
Theory 2007.
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, valid for any even number
of variables, for constructing functions with optimum (or, if
this can
be useful, with high but not optimal) algebraic immunity and which can
be balanced if we wish. We also give a new example of an infinite
class of such functions. We study their Walsh transforms.
10) ``On inequivalence between known power APN functions". L.
Budaghyan, C. Carlet and G. Leander. Proceedings of BFCA 2008, pp.
151-165, 2009.
Abstract:
There are six known cases of power APN functions. We investigate an
open question whether these cases are pairwise CCZ-inequivalent.
We prove that, except in particular cases, the Gold
mappings are CCZ-inequivalent to the Kasami and Welch functions and
that different cases of Gold mappings are pairwise CCZ-inequivalent.
11) ``On a construction of quadratic APN functions". L.
Budaghyan, C. Carlet and G. Leander. Proceedings of IEEE Information
Theory Workshop 2009.
Abstract:
In a recent paper, the authors introduced a method for
constructing new quadratic APN functions from known ones. Applying this
method, they obtained the function $x^3+\tr_n(x^9)$ which is APN
over $\F_{2^n}$ for any positive integer $n$.
The present paper is a continuation of this work. We give sufficient
conditions on linear functions $L_1$ and $L_2$ from $\F_{2^n}$ to
itself such that the function $L_1(x^3)+L_2(x^9)$ is APN over
$\F_{2^n}$. We show that this can lead to many new cases of APN
functions. In particular, we get two families of APN functions
$x^3+a^{-1}\tr_{n}^3(a^3x^9+a^6x^{18})$ and
$x^3+a^{-1}\tr_{n}^3(a^6x^{18}+a^{12}x^{36})$ over $\F_{2^n}$ for any
$n$ divisible by 3 and $a\in\F_{2^n}^*$. We prove that for $n=9$, these
families are pairwise different and differ from all previously known
families of APN functions, up to the most general equivalence
notion, the CCZ-equivalence. We also investigate further sufficient
conditions under which the conditions on the linear functions $L_1$ and
$L_2$ are satisfied.
12) ``On the Dual of Bent Functions with $2^r$ Niho Exponents'' with T.
Helleseth, S. Kholosha and S. Mesnager. Proceedings of ISIT 2011, Saint
Petersburg, 2011.
Abstract:
We compute the dual function of the Niho bent function having $2^r$
exponents proposed by Leander and Kholosha.
13) ``On Bent Functions Associated to AB Functions'', with L. Budaghyan
and T. Helleseth. Proceedings of IEEE Information Theory Workshop 2011.
Abstract:
In 1998, the second author, Charpin and Zinoviev characterized APN and
AB $(n,n)$-functions by means of associated $2n$-variable Boolean
functions. In particular, they proved that a function $F$ is AB if and
only if the associated Boolean function $\gamma_F$ is bent. This
observation leads to potentially new bent functions associated to the
known AB functions, or at least gives new insight on known bent
functions.
However, up to now, representations of $\gamma_F$ are known only for
Gold AB power functions and determining $\gamma_F$ for the rest of AB
functions is an open problem.
In the present paper we determine $\gamma_F$ for most of the known
families of APN and AB functions.
14) On Dillon’s class H of Niho bent functions and
o-polynomials,with C. Carlet. Symposium on Artificial Intelligence and
Mathematics (ISAIM 2012), Fort Lauderdale, Floride, USA, January 2012.
15) Generalized Bent Functions and their Relation to
Maiorana-McFarland Class. L. Budaghyan, C. Carlet, T. Helleseth
et A. Kholosha. Proceedings of ISIT 2012.
16) On the Arithmetic Walsh Coefficients of Boolean Functions. C.
Carlet and A. Klapper. Proceedings of the International Workshop on
Coding and Cryptography 2013, April 2013, Bergen.
Abstract:
We generalize to the Arithmetic Walsh Transform (AWT) some results
which were previously known for the Walsh Hadamard transform of Boolean
functions. We firstly generalize the classical Poisson summation
formula to the AWT. We secondly show that the AWT of a large
class of Boolean functions can be expressed in terms of the AWT of a
Boolean function of algebraic degree at most 3 in a larger number of
variables.
17) C. Carlet and S. Guilley, Side-Channel Indistinguishability,
HASP,Tel Aviv, Israël, June 2013. Published by ACM (Association
for
Computing Machinery)
Abstract:
We introduce a masking strategy for hardware that prevents any
side-channel attacker from recovering uniquely the secret key of a
cryptographic device. In this masking scheme, termed homomorphic, the
sensitive data is exclusive-ored with a random value that belongs to a
given set. We show that if this masking set is concealed, then no
information about the cryptographic key leaks. If the masking set is
public (or disclosed), then any (high-order) attack reveals a group of
equiprobable keys. Those results are applied to the case of the AES,
where sensitive variables are bytes. To any mask corresponds a masked
substitution box. We prove that there exists a homomorphic masking with
$16$ masks (hence a number of substitution boxes equal to that of the
same algorithm without masking) that resists mono-variate first-,
second-, and third-order side-channel attacks. Furthermore, even if the
masking set is public, each byte of the correct key is found only ex
aequo with $15$ incorrect ones, making the side-channel analysis
insufficient alone -- the remaining key space shall be explored by
other means (typically exhaustive search). Thus, our homomorphic
masking strategy allows both to increase the number of side-channel
measurements and to demand for a final non negligible brute-forcing (of
complexity $16^{N_B}=2^{64}$ for AES, that has $N_B=16$ substitution
boxes). The hardware implementation of the Rotating Substitution boxes
Masking (RSM) is a practical instantiation of our homomorphic masking
countermeasure.
18) L. Budaghyan, A. Kholosha, C. Carlet, T. Helleseth. Niho Bent
Functions from Quadratic o-Monomials. Proceedings of ISIT 2014.
Abstract:
In this paper, we extend the class of Niho bent function consisting of
$2^r$ terms discovered by Leander and Kholosha. The extension is
achieved by inserting coefficients of the power terms in the original
function. Doing this, we obtain relation to all the known quadratic
o-monomials (up to equivalence). These new bent functions are not
EA-equivalent to any of the known classes. We also calculate the
algebraic degree of any function in the extended class.
19) C. Carlet, A. Daif, J.-L. Danger, S. Guilley, Z. Najm, X. T. Ngo, T.
Porteboeuf and C. Tavernier. Optimized Linear Complementary Codes
Implementation for Hardware Trojan Prevention. Proceedings of the 22nd
European Conference on Circuit Theory and Design, ECCTD 2015, pp. 1-4, 2015.
Abstract:
Block codes have been shown to be a tool to thwart hardware trojan
horses. The state of the electronic circuits is encoded thanks to a pair
of complementary codes: one code prevents a purported hardware trojan
horses from triggering, while the other one detects any kind of payload.
The feasibility and the actual implementation of such defense has be
presented thanks to LCD (Linear Complementary Dual) codes and to LCP
(Linear Complementary Pair) of codes. In this paper, we optimize the
representation of such codes in order to reduce the hardware overhead of
the countermeasure.
20) S. Picek, C. Carlet, D. Jakobovic and J. Miller, L. Batina.
Correlation Immunity of Boolean Functions: An Evolutionary Algorithms
Perspective. Proceedings of the Genetic and Evolutionary Computation
Conference (GECCO 2015), Jul 11-15, Madrid, Spain, pp. 1095-1102, 2015.
Abstract:
Boolean functions represent an essential primitive in many stream
ciphers. They are used in order to add confusion, in other words, they
represent the nonlinear part of the stream algorithm. When used in
combiner generators, Boolean functions need to have sufficiently high
value of correla- tion immunity, alongside the other properties. On the
other side, correlation-immune functions allow reducing the cost of the
masking countermeasure to side-channel attacks when they have small
Hamming weight. There has been a number of papers examining the
applicability of evolutionary algo- rithms when evolving Boolean
functions for cryptographic usages. In some of those papers, authors
checked the cor- relation immunity property, but never gave the property
the highest priority. In this paper we examine the effec- tiveness of
three different EAs, namely, Genetic Algorithm, Genetic programming and
Cartesian Genetic Programming when evolving balanced Boolean functions
that are corre- lation immune. Besides the aforementioned properties of
balancedness and correlation immunity, we consider several other
relevant cryptographic properties while maintaining the optimal
trade-offs among them. Our results show that evolving Boolean functions
that are correlation immune (un- balanced or resilient) is an even
harder objective than the more traditional one where the goal is the
maximization of the nonlinearity property.
21) C. Carlet. On the nonlinearity of monotone Boolean functions. Proceedings of SETA 2016, Chengdu, China, 09-14 October 2016.
Abstract:
We first prove the truthfulness of a conjecture on the nonlinearity of
monotone Boolean functions in even dimension, proposed in the recent
paper ``Cryptographic properties of monotone Boolean functions", by D.
Joyner, P. Stanica, D. Tang and the author (Journal of Mathematical
Cryptology, vol. 10, 2016). We prove then an upper bound on such
nonlinearity, which is asymptotically much stronger than the conjectured
upper bound and than the upper bound proved for odd dimension in
this same paper. This bound shows a deep weakness of monotone Boolean
functions; they are too closely approximated by affine functions for
being usable as nonlinear components in cryptographic applications. We
deduce a necessary criterion to be satisfied by a Boolean (resp.
vectorial) function for being nonlinear.
22) L. Budaghyan, C. Carlet, T. Helleseth and N. Li. . On the
(non-)existence of APN functions of algebraic degree $n$ over $F_2^n$.
Proceedings of ISIT 2016, pp. 480-484, 2016.
Abstract:
In this paper, we study the problem of existence of almost perfect
nonlinear (APN) functions of algebraic degree $n$ over $F_{2^n}$.
We characterize such functions by means of derivatives and power
moments of the Walsh transform. We deduce some non-existence results
which imply, in particular, that for most of the known APN functions $F$
over $F_{2^n}$ the function $x^{2^n-1}+F(x)$ is not APN.
23) S. Picek, K. Knezevic, D. Jakobovic and C. Carlet. A Search for
Differentially-6 Uniform (n, n-2) Functions. Proceedings of IEEE CEC
2018, pp. 1-7, 2018.
Abstract:
Finding cryptographic primitives satisfying certain properties is a
difficult problem. In this domain, besides the algebraic constructions,
researchers often use heuristics.
There exists a set of interesting problems related to the notion of
differential uniformity for a function $F: F_2^n \to F_2^m$. When $n =
m$, then the best obtainable differential uniformity equals 2, since it
is necessarily positive and even, and since examples of differentially
2-uniform functions are known. Heuristics are able to reach such
functions; there is then some intuition that heuristics can be used for
other open problems related to differential uniformity.
When $n > m>n/2$, differential uniformity is bounded by
$2^{n-m}+2$ from below (when $m = n - 2$, by 6). Unfortunately, we
know such functions only for dimensions equal to $n = 4, 5$.
In this paper, we explore several evolutionary algorithms and problem
sizes in order to find functions having differential uniformity equal to
6. Our results show that several solution encodings are able to find
such functions but only in dimensions $(4, 2)$ and $(5, 3)$. Since
differentially 6-uniform functions were known for those sizes before,
our results can be used as a source of new functions in those dimensions
and as an indicator that for $(6,4)$ such functions either do not exist
or that it is extremely difficult to find them.
24) L. Budaghyan, M. Calderini, C. Carlet, R. Coulter and I. Villa. On
Isotopic Shift Construction for Planar Functions. Proceedings of ISIT
2019.
Abstract:
In this paper, we discuss possible extensions for the case of planar
functions over fields of odd characteristic of the idea of isotopic
shift construction of APN functions over fields of even characteristic.
We show that some of the known planar functions are actually isotopic
shifts of each other. This confirms practically the pertinence of the
notion of isotopic shift.
25) W. Cheng, S. Guilley, C. Carlet, J.-L. Danger and A. Schaub. Optimal
Codes for Inner Product Masking. Cryptographic architectures embedded
in logic devices 2019.
Abstract:
Masking is the most popular countermeasure to protect cryptographic
implementations against side-channel analysis, since it is provable
secure and can be deployed at algorithm level. To strengthen the
original Boolean masking scheme, several works have suggested to use
more complicated schemes with high algebraic complexity, like affine
masking and polynomial masking. Therefore, the Inner Product Masking
(IPM) was proposed to be a better alternative with its intrinsic
algebraic complexity. In this work, we express the security order of
generalized IPM schemes from the viewpoint of coding theory, which
allows us to optimize it. Specifically, we highlight first that the IPM
scheme is not optimal by showing different security order in byte- and
bit-level, respectively. In particular, this result confirms the
previous observations made by Balasch et al. at EUROCRYPT’ 15 and at
ASIACRYPT’ 17 and Poussier et al. at CARDIS’ 17 regarding the parameters
effect in IPM.
More importantly, we characterize this parameter effect by linking the
side-channel resistance of IPM to the concept of minimum distance and
one coefficient in weight enumeration polynomial of a linear code. The
closed-form expression is proposed for depicting the connection, also
allows us to systemically choose optimal codes for IPM. As the last
contribution, we present the optimal linear code in several scenarios
for IPM with two and three shares. The experiments are in perfect
accordance with our theoretic analysis and finely demonstrate the
optimality of the codes chosen by our method. Our results also present a
solid explanation on parameters effect found by Balasch et al. and
Poussier et al.
26) W. Cheng, C. Carlet, K. Goli, S. Guilley and J.-L. Danger. Detecting
Faults in Inner Product Masking Scheme. IACR Cryptology ePrint Archive
(http://eprint.iacr.org/) 2019/919. Presented at PROOFS 2019, 8th
International Workshop on Security Proofs for Embedded Systems, Atlanta,
USA, 2019. https://easychair.org/publications/paper/HTzP
Abstract:
Side-channel analysis and fault injection attacks are two typical
threats to cryptographic implementations, especially in modern embedded
devices. Thus there is an insistent demand for dual side-channel and
fault injection protections. As it is known, masking scheme is a kind of
provable countermeasures against side-channel attacks. Recently, inner
product masking (IPM) was proposed as a promising higher-order masking
scheme against side-channel analysis, but not for fault injection
attacks. In this paper, we devise a new masking scheme named IPM-FD. It
is built on IPM, which enables fault detection. This novel masking
scheme has three properties: the security orders in the word-level
probing model, bit-level probing model, and the number of detected
faults. IPM-FD is proven secure both in the word-level and in the
bit-level probing models, and allows for end-to-end fault detection
against fault injection attacks.
27) C. Carlet and P. Méaux. Boolean Functions for
Homomorphic-Friendly Stream Ciphers. International Conference on
Algebra, Codes and Cryptology. Springer, p. 166-182, 2019.
Abstract:
The proliferation of small embedded devices having growing but still
limited computing and data storage facilities, and the related
development of cloud services with extensive storage and computing
means, raise nowadays new privacy issues because of the outsourcing of
data processing. This has led to a need for symmetric
cryptosystems suited for hybrid symmetric-FHE encryption protocols,
ensuring the practicability of the FHE solution. Recent ciphers meant
for such use have been introduced, such as LowMC, Kreyvium, FLIP, and
Rasta. The introduction of stream ciphers devoted to symmetric-FHE
frameworks such as FLIP and its recent modification has in its turn
posed new problems on the Boolean functions to be used in them as
filter functions. We recall the state of the art in this matter and
present further studies (without proof).
28) C. Carlet, D. Jakobovic and S. Picek. Evolutionary
Algorithms-assisted Construction of Cryptographic Boolean Functions.
Proceedings of GECCO'21, pp. 565-573, 2021.
Abstract:
In the last few decades, evolutionary algorithms were successfully
applied numerous times for creating Boolean functions with good
cryptographic properties. Still, the applicability of such approaches
was always limited as the cryptographic community knows how to construct
suitable Boolean functions with deterministic algebraic constructions.
Thus, evolutionary results so far helped to increase the con dence that
evolutionary techniques have a role in cryptog- raphy, but at the same
time, the results themselves were seldom used.
This paper considers a novel problem using evolutionary algo- rithms to
improve Boolean functions obtained through algebraic constructions. To
this end, we consider a recent generalization of Hidden Weight Boolean
Function construction, and we show that evolutionary algorithms can
signi cantly improve the cryp- tographic properties of the functions.
Our results show that the genetic algorithm performs by far the best of
all the considered algorithms and improves the nonlinearity property in
all Boolean function sizes. As there are no known algebraic techniques
to reach the same goal, we consider this application a step forward in
accept- ing evolutionary algorithms as a powerful tool in the
cryptography domain.
29) C. Carlet, M. Djurasevic, D. Jakobovic, L. Mariot and S. Picek.
Evolving Constructions for Balanced, Highly Nonlinear Boolean Functions.
Proceedings of the Genetic and Evolutionary Computation Conference
GECCO '22, pp. 1147-1155.
Abstract:
Finding balanced, highly nonlinear Boolean functions is a diffi- cult
problem where it is not known what nonlinearity values are possible to
be reached in general. At the same time, evolution- ary computation is
successfully used to evolve specific Boolean function instances, but the
approach cannot easily scale for larger Boolean function sizes. Indeed,
while evolving smaller Boolean functions is almost trivial, larger
sizes become increasingly difficult, and evolutionary algorithms perform
suboptimally.
In this work, we ask whether genetic programming (GP) can evolve
constructions resulting in balanced Boolean functions with high
nonlinearity. This question is especially interesting as there are only a
few known such constructions. Our results show that GP can find
constructions that generalize well, i.e., result in the required
functions for multiple tested sizes. Further, we show that GP evolves
many equivalent constructions under different syntactic representations.
Interestingly, the simplest solution found by GP is a particular case
of the well-known indirect sum construction.
30) C. Carlet, D. Jakobovic and S. Picek. On generalizing the power
function exponent constructions with genetic programming. GECCO '22:
Proceedings of the Genetic and Evolutionary Computation Conference
CompanionJuly 2022. pp. 691–694
Abstract:
Many works are investigating Almost Perfect Nonlinear (APN) functions
and, in particular, APN power functions. Such functions are of the form
𝐹 (𝑥) = 𝑥^𝑑 , and they have practical relevance as they reach in
characteristic 2 the best possible differential uniformity. This work
investigates whether genetic programming (GP) can “reinvent” the known
expressions used to obtain exponent values 𝑑 resulting in APN
functions. The ultimate goal is to find classes of exponents that would
be “transversal” to the known infinite classes of APN exponents, and
would contain new APN exponents (for values of 𝑛 necessarily larger
than those for which an exhaustive search could be made so far). This
would be already a breakthrough, and our hope is to find this way new
infinite classes of APN exponents. Our results show this is possible but
difficult, and a careful trade-off between finding new values and
skipping known values is required.
Popular papers:
Claude Carlet. Fonctions booléennes et tableaux orthogonaux au
secours des contre-mesures aux attaques par canaux auxiliaires. Gazette
de l'Institut Galilée, 2013.
A. Gorodilova, S. Agievich, C. Carlet, E. Gorkunov,
V. Idrisova, N. Kolomeec, A. Kutsenko, S. Nikova,
A. Oblaukhov, S. Picek, B. Preneel, V. Rijmen and
N. Tokareva.
Problems and solutions of the Fourth International Students' Olympiad in
Cryptography NSUCRYPTO. Cryptologia 43 (2), pp. 138-174, 2019.
A. Gorodilova, S. Agievich, C. Carlet, X.-D. Hou, V. Idrisova, N.
Kolomeec, A. Kutsenko, L. Mariot, A. Oblaukhov, S. Picek, B. Preneel, R.
Rosie and
N. Tokareva. The Fifth International Students’ Olympiad in
cryptography—NSUCRYPTO: Problems and their solutions, Cryptologia 44
(3), to appear.
Claude Carlet (claude.carlet@univ-paris8.fr, claude.carlet@gmail.com)
Last modification: October 2022