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) 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.

11) 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

12) 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

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. 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) 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.

72) 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. To appear in The Scientific World Journal. Hindawi Publishing Corporation.
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.

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. To appear in IEEE Transactions on Information Forensics & Security, Vol. 12, No. 7, 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.


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) ``On the algebraic immunities and higher order nonlinearities of vectorial Boolean functions". C. Carlet.  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) CCZ-equivalence of single and multi output Boolean functions. L. Budaghyan and C. Carlet. 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.

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 ${\Bbb 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 Claude 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 **, 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.


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.


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.


Claude Carlet(Claude.Carlet@univ-paris8.fr)
Last modification: June 2017