Idempotent Boolean functions form a highly structured subclass of Boolean functions that is closely related to rotation symmetry under a normal-basis representation and to invariance under a fixed linear map in a polynomial basis. These functions are attractive as candidates for cryptographic design, yet their additional algebraic constraints make the search for high nonlinearity substantially more difficult than in the unconstrained case. In this work, we investigate evolutionary methods for constructing highly nonlinear idempotent Boolean functions for dimensions n = 5 up to n = 12 using a polynomial basis representation with canonical primitive polynomials. Our results show that the problem of evolving idem-potent functions is difficult due to the disruptive nature of crossover and mutation operators. Next, we show that idempotence can be enforced by encoding the truth table on orbits, yielding a compact genome of size equal to the number of distinct squaring orbits.

Code-Based Masking (CBM) has been introduced to enhance high-order Boolean masking by increasing its resistance order via further decorrelating the coordinates of each symbol involved in the computation. Additionally, CBM enables cost amortization and fault detection. Notably, as demonstrated at CHES 2024, CBM facilitates the computation of provably masked operations under the Strong Non-Interference (SNI) security assumption with quasi-linear complexity. On the other hand, Threshold Implementation (TI) serves as an extension of Boolean masking, armoring it against combinational hazards. In this article, we show that merits of CBM and TI can be combined, paving the way to more secure hardware (high-order) masked implementations. We demonstrate CBM-TI, which is proven secure as well under SNI assumption and security when glitches worsen the leakage model.The security of CBM-TI is studied in a n-share setting, where n = 3 (minimal random splitting order required for TI). We analyzed CBM-TI in simulation and in real hardware (FPGA) to validate its security property. Leveraging high-order T-test leakage detection tool, we show that CBM-TI is endowed with higher-order security. Namely, TI leaks at order d = 3, whereas CBM-TI does not. We study several CBM-TI variants and show that the smallest leaking order of CBM-TI can be tuned to be as high as 7. This represents a significant progress over TI as each marginally improved order translates into exponentially more traces to attack the implementation.

Abstract We study the behavior of the multiplicative inverse function (which plays an important role in cryptography and in the study of finite fields), with respect to a recently introduced generalization of almost perfect nonlinearity (APNness), called kth-order sum-freedom, that extends a classic characterization of APN functions, and has also some relationship with integral attacks. This generalization corresponds to the fact that a vectorial function $$F:\mathbb {F}_2^n\mapsto \mathbb {F}_2^m$$ F : F 2 n ↦ F 2 m sums to a nonzero value over every k-dimensional affine subspace of $$\mathbb {F}_2^n$$ F 2 n , for some $$k\le n$$ k ≤ n (APNness corresponds to $$k=2$$ k = 2 ). The sum of the values of the inverse function $$x\in \mathbb {F}_{2^n}\mapsto x^{2^n-2}\in \mathbb {F}_{2^n}$$ x ∈ F 2 n ↦ x 2 n - 2 ∈ F 2 n over any affine subspace A of $$\mathbb {F}_{2^n}$$ F 2 n not containing 0 (i.e. being not a vector space) has been addressed, thanks to a simple expression of such sum, which shows that it never vanishes. We study in the present paper the case of vector (i.e. linear) subspaces, which is much less simple to handle. The sum depends on a coefficient in subspace polynomials. We study for which values of k the multiplicative inverse function can sum to nonzero values over all k-dimensional vector subspaces. We show that, for every k not co-prime with n, it sums to zero over at least one k-dimensional $$\mathbb {F}_2$$ F 2 -subspace of $$\mathbb {F}_{2^n}$$ F 2 n . We study the behavior of the inverse function over direct sums of vector spaces and we deduce that the property of the inverse function to be kth-order sum-free happens for k if and only if it happens for $$n-k$$ n - k . We derive several other results and we show that the set of values k such that the inverse function is not kth-order sum-free is stable when adding two values of k whose product is smaller than n (and when subtracting two values under some conditions). We clarify the case of dimension at most 4 (equivalently, of co-dimension at most 4) and this allows to address, for every n, all small enough values of k of the form $$3a+4b$$ 3 a + 4 b .

Abstract We study the n -variable Boolean functions which keep their algebraic degree unchanged when they are restricted to any (affine) hyperplane, or more generally to any affine space of a given co-dimension k . For cryptographic applications it is of interest to determine functions f which have a relatively high algebraic degree and also maintain this degree when restricted to all affine spaces of co-dimension k for k ranging from 1 to as high a value as possible. This highest value will be called the restriction degree stabilityof f , denoted by $$\mathrm{deg\_stab}(f)$$ deg _ stab ( f ) . We give several necessary and/or sufficient conditions for f to maintain its degree on spaces of co-dimension k ; we show that this property is related to the property of having “fast points” as well as to other properties and parameters. The value of $$\mathrm{deg\_stab}(f)$$ deg _ stab ( f ) is determined for functions which are direct sums of monomials, as well as for functions of algebraic degrees $$1,2,n-2,n-1$$ 1 , 2 , n - 2 , n - 1 and n ; we also determine the symmetric functions which maintain their degree on any hyperplane. Furthermore, we give an explicit formula for the number of functions which maintain their degree on all hyperplanes. Finally, using our previous results and some computer assistance, we determine the behaviour of all the functions in up to 8 variables, therefore determining the optimal ones (i.e. with highest value of $$\mathrm{deg\_stab}(f)$$ deg _ stab ( f ) ) for each degree.

Abstract In two papers entitled “Two generalizations of almost perfect nonlinearity” and “On the vector subspaces of $$\mathbb F_{2^n}$$ F 2 n over which the multiplicative inverse function sums to zero”, the first author has introduced and studied the notion of sum-freedom of vectorial functions, which expresses that a function sums to nonzero values over all affine subspaces of $$\mathbb {F}_{2^n}$$ F 2 n of a given dimension $$k\ge 2$$ k ≥ 2 , and he then focused on the k th order sum-freedom of the multiplicative inverse function $$x\in \mathbb {F}_{2^n}\mapsto x^{2^n-2}$$ x ∈ F 2 n ↦ x 2 n - 2 . Some general results were given for this function (in particular, the case of affine spaces that do not contain 0 was solved positively), and the cases of $$k\in \{3,4,n-4,n-3\}$$ k ∈ { 3 , 4 , n - 4 , n - 3 } and of k not co-prime with n were solved as well (negatively); but the cases of those linear subspaces of dimension $$k\in \llbracket 5;n-5\rrbracket $$ k ∈ 〚 5 ; n - 5 〛 , co-prime with n , were left open. The present paper is a continuation of the previous work. After studying, from two different angles, the particular case of those linear subspaces that are stable under the Frobenius automorphism, we deduce from the second approach that, for k small enough (approximately, $$3\le k\le n/10$$ 3 ≤ k ≤ n / 10 ), the multiplicative inverse function is not k th order sum-free. Finally, we deduce from results previously obtained in the second paper mentioned above, that for any even n and every $$2\le k\le n-2$$ 2 ≤ k ≤ n - 2 , the multiplicative inverse function is not k th order sum-free.

Abstract Almost perfect nonlinear (in brief, APN) functions are vectorial functions $$F:{\mathbb {F}}_2^n\rightarrow {\mathbb {F}}_2^n$$ F : F 2 n → F 2 n playing roles in several domains of information protection, at the intersection of computer science and mathematics. Their definition comes from cryptography and is also related to coding theory. When they are used as substitution boxes (S-boxes, which are the only nonlinear components in block ciphers), APN functions contribute optimally to the resistance against differential attacks. This makes of course a strong cryptographic motivation for their study, which has been very active since the 90’s, and has posed interesting and difficult mathematical questions, some of which are still unanswered. Since the introduction of differential attacks, more recent types of cryptanalyses have been designed, such as integral attacks. No notion about S-boxes has been identified which would play a similar role with respect to integral attacks. In this paper, we study two generalizations of APNness that are natural from a mathematical point of view, since they directly extend classical characterizations of APN functions. We call these two notions strong non-normality and sum-freedom. The former existed already for Boolean functions (it had been introduced by Dobbertin), and the latter is new. We study how these two notions are related to cryptanalyses (the relation is weaker for strong non-normality). The two notions behave differently from each other, while they have similar definitions. They behave differently from differential uniformity, which is a well-known generalization of APNness. We study the different ways to define them. We prove their satisfiability, their monotonicity, and their invariance under classical equivalence relations, and we characterize them by the Walsh transform. We finally begin a study of the multiplicative inverse function (used as a substitution box in the Advanced Encryption Standard and other block ciphers) from the viewpoint of these two notions. In particular, we find a simple expression of the sum of the values taken by this function over affine subspaces of $$\mathbb F_{2^n}$$ F 2 n that are not vector subspaces. This formula shows that the sum never vanishes on such affine spaces. We also give a formula for the case of a vector space defined by one of its bases.

The weight spectra (i.e. the lists of all possible weights) of the Reed-Muller codesRM(r,m), of length 2mand orderr, are unknown forr∈ {3, … ,m- 5} (andmlarge enough). Those ofRM(m-4,m) andRM(m-3,m) have been determined very recently (but not the weight distributions, giving the number of codewords of each weight, which seem out of reach). We determine the weight spectrum ofRM(m-5,m) for everym≥ 10. We proceed by first determining the weights inRM(5, 10). To do this, we construct functions whose weights are in the set {62, 74, 78, 82, 86, 90}, and functions whose weights are all the integers between 94 and 29- 2 = 510 that are congruent with 2 modulo 4 (those weights that are divisible by 4 are easier to determine and they are indeed known). This allows us to determine completely the weight spectrum, thanks to the wellknown result due to Kasami, Tokura and Azumi, which precisely determines those codeword weights in Reed-Muller codes which lie between the minimum distancedand 2.5 timesd, and thanks to the fact the weight spectrum is symmetric with respect to 29. Then we use this particular weight spectrum for determining that ofRM(m-5,m), by an induction onm. We check that a recent conjecture (in which we correct a misprint) on the weight spectrum ofRM(m-c,m) is verified forc= 5, and we study the difficulties of trying to extend the results toc≥ 6.

Abstract In the independent works by Kalgin and Idrisova and by Beierle, Leander and Perrin, it was observed that the Gold APN functions over $$\mathbb {F}_{2^5}$$ F 2 5 give rise to a quadratic APN function in dimension 6 having maximum possible linearity of $$2^5$$ 2 5 (that is, minimum possible nonlinearity $$2^4$$ 2 4 ). In this article, we show that the case of $$n \le 5$$ n ≤ 5 is quite special in the sense that Gold APN functions in dimension $$n>5$$ n > 5 cannot be extended to quadratic APN functions in dimension $$n+1$$ n + 1 having maximum possible linearity. In the second part of this work, we show that this is also the case for APN functions of the form $$x \mapsto x^3 + \mu (x)$$ x ↦ x 3 + μ ( x ) with $$\mu $$ μ being a quadratic Boolean function.

Abstract It is known that correlation-immune (CI) Boolean functions used in the framework of side channel attacks need to have low Hamming weights. The supports of CI functions are (equivalently) simple orthogonal arrays, when their elements are written as rows of an array. The minimum Hamming weight of a CI function is then the same as the minimum number of rows in a simple orthogonal array. In this paper, we use Rao’s Bound to give a sufficient condition on the number of rows, for a binary orthogonal array (OA) to be simple. We apply this result for determining the minimum number of rows in all simple binary orthogonal arrays of strengths 2 and 3; we show that this minimum is the same in such case as for all OA, and we extend this observation to some OA of strengths 4 and 5. This allows us to reply positively, in the case of strengths 2 and 3, to a question raised by the first author and X. Chen on the monotonicity of the minimum Hamming weight of 2-CI Boolean functions, and to partially reply positively to the same question in the case of strengths 4 and 5.

Threshold implementation is a method based on secret sharing to secure cryptographic ciphers (and in particular S-boxes) against differential power analysis side-channel attacks which was proposed by Nikova, Rechberger, and Rijmen in 2006. Until now, threshold implementations were only constructed for specific types of functions and some small S-boxes, but no generic construction was ever presented. In this paper, we present the first universal threshold implementation with$t+2$shares that is applicable to any bijective S-box, where$t$is its algebraic degree (or is larger than the algebraic degree). While being universal, our construction is also optimal with respect to the number of shares, since the theoretically smallest possible number,$t+1$, is not attainable for some bijective S-boxes. Our results enable low latency secure hardware implementations without the need for additional randomness. In particular, we apply this result to find two uniform sharings of the AES S-box. The first sharing is obtained by using the threshold implementation of the inversion in$\mathbb {F}_{2^{8}}$and the second by using two threshold implementations of two cubic power permutations that decompose the inversion. Area and performance figures for hardware implementations are provided.

Finding balanced, highly nonlinear Boolean functions is a difficult problem where it is not known what nonlinearity values are possible to be reached in general. At the same time, evolutionary computation is successfully used to evolve specific Boolean function instances, but the approach cannot easily scale for larger Boolean function sizes. Indeed, while evolving smaller Boolean functions is almost trivial, larger sizes become increasingly difficult, and evolutionary algorithms perform suboptimally.

The six infinite families of power APN functions are among the oldest known instances of APN functions, and it has been conjectured in 2000 that they exhaust all possible power APN functions. Another long-standing open problem is that of the Walsh spectrum of the Dobbertin power family, which is still unknown. Those of Kasami, Niho and Welch functions are known, but not the precise values of their Walsh transform, with rare exceptions. One promising approach that could lead to the resolution of these problems is to consider alternative representations of the functions in questions. We derive alternative representations for the infinite APN monomial families. We show how the Niho, Welch, and Dobbertin functions can be represented as the composition$x^{i} \circ x^{1/j}$of two power functions, and prove that our representations are optimal, i.e. no two power functions of lesser algebraic degree can be used to represent the functions in this way. We investigate compositions$x^{i} \circ L \circ x^{1/j}$for a linear polynomial$L$, show how the Kasami functions in odd dimension can be expressed in this way with$i=j$being a Gold exponent and compute all APN functions of this form for$n \le 9$and for$L$with binary coefficients, thereby showing that our theoretical constructions exhaust all possible cases. We present observations and data on power functions with exponent$\sum _{i = 1}^{k-1} 2^{2ni} - 1$which generalize the inverse and Dobbertin families. We present data on the Walsh spectrum of the Dobbertin function for$n \le 35$, and conjecture its exact form. As an application of our results, we determine the exact values of the Walsh transform of the Kasami function at all points of a special form. Computations performed for$n\leq 21$show that these points cover about 2/3 of the field.

Designing Boolean functions whose output can be computed with light means at high speed, and satisfying all the criteria necessary to resist all major attacks on the stream ciphers using them as nonlinear components, has been an open problem since the beginning of this century, when algebraic attacks were invented. Functions allowing a good resistance are known since 2008, but their output is a little too complex to compute. Functions with fast and easy to compute output are known which have good algebraic immunity, such as majority functions and the so-called hidden weight bit (HWB) functions, but they all have the same cryptographic weakness: their too small nonlinearity. In the present paper, we introduce a generalization of the HWB functions into a construction of$n$-variable balanced functions$f$from$(n-1)$-variable Boolean functions$g$having some property held by a large number of functions. Function$f$is defined by its support, equal to the image set of a vectorial function depending on$g$. This makes the function complex enough for allowing good cryptographic parameters, while its output is light to compute. The HWB function is what we obtain with$f$when the initial function$g$equals constant 1. Other well chosen functions$g$provide functions$f$having good cryptographic parameters. We analyze the constructed functions$f$, we provide a fast way to compute their output, we determine their algebraic normal forms and we show that, most often, their algebraic degree is optimal. We study their Walsh transform and their nonlinearity and algebraic immunity. We observe with computer investigations that this generalization of the HWB function allows to keep its quality of being fast to compute and having good enough algebraic immunity, while significantly improving its nonlinearity. The functions already obtained in the investigations provide a quite good (and never reached before) trade-off between speed and security. Further (probably difficult) work should allow obtaining, among such generalized HWB functions whose number is huge, still better filter functions to be used in stream ciphers.

In this paper, we make a comprehensive study of two classes of Boolean functions whose interest originally comes from hybrid symmetric-FHE encryption (with stream ciphers like FiLIP), but which also present much interest for general stream ciphers. The functions in these two classes are cheap and easy to implement, and they allow the resistance to all classical attacks and to their guess and determine variants as well. We determine exactly all the main cryptographic parameters (algebraic degree, resiliency order, nonlinearity, algebraic immunity) for all functions in these two classes, and we give close bounds for the others (fast algebraic immunity, the dimension of the space of annihilators of minimal degree). This is the first time that this is done for all functions in large classes of cryptographic interest.

In the last few decades, evolutionary algorithms were successfully applied numerous times for creating Boolean functions with good cryptographic properties. Still, the applicability of such approaches was always limited as the cryptographic community knows how to construct suitable Boolean functions with deterministic algebraic constructions. Thus, evolutionary results so far helped to increase the confidence that evolutionary techniques have a role in cryptography, but at the same time, the results themselves were seldom used.

Abstract In this work we give several generalizations of the isotopic shift construction, introduced recently by Budaghyan et al. (IEEE Trans Inform Theory 66:5299–5309, 2020), when the initial function is a Gold function. In particular, we derive a general construction of APN functions which covers several unclassified APN functions for $$n=8$$ n = 8 and produces fifteen new APN functions for $$n=9$$ n = 9 .

Constructing S-boxes that are inherently resistant against side-channel attacks is an important problem in cryptography. By using an optimal distinguisher under an additive Gaussian noise assumption, we clarify how a defender (resp., an attacker) can make side-channel attacks as difficult (resp., easy) as possible, in relation with the auto-correlation spectrum of Boolean functions. We then construct balanced Boolean functions that are optimal for each of these two scenarios. Generalizing the objectives for an S-box, we analyze the auto-correlation spectra of some well-known S-box constructions in dimensions at most 8 and compare their intrinsic resiliency against side-channel attacks. Finally, we perform several simulations of side-channel attacks against the aforementioned constructions, which confirm our theoretical approach.

Masking is one of the most popular countermeasures to protect cryptographic implementations against side-channel analysis since it is provably secure and can be deployed at the algorithm level. To strengthen the original Boolean masking scheme, several works have suggested using schemes with high algebraic complexity. The Inner Product Masking (IPM) is one of those. In this paper, we propose a unified framework to quantitatively assess the side-channel security of the IPM in a coding-theoretic approach. Specifically, starting from the expression of IPM in a coded form, we use two defining parameters of the code to characterize its side-channel resistance. In order to validate the framework, we then connect it to two leakage metrics (namely signal-to-noise ratio and mutual information, from an information-theoretic aspect) and one typical attack metric (success rate, from a practical aspect) to build a firm foundation for our framework. As an application, our results provide ultimate explanations on the observations made by Balasch et al. at EUROCRYPT'15 and at ASIACRYPT'17, Wang et al. at CARDIS'16 and Poussier et al. at CARDIS'17 regarding the parameter effects in IPM, like higher security order in bounded moment model. Furthermore, we show how to systematically choose optimal codes (in the sense of a concrete security level) to optimize IPM by using this framework. Eventually, we present a simple but effective algorithm for choosing optimal codes for IPM, which is of special interest for designers when selecting optimal parameters for IPM.

We initiate a study, when F is a general APN function, of the Boolean function γFrelated to the differential spectrum of F (and which is known to be bent if and only if F is almost bent). We first list many open questions about it. We study its algebraic normal form and its bivariate representation. We characterize its linear structures and specify nonexistence cases; we show, for n even, their relation with the bent components of F. We pose three related open problems. We characterize further in terms of γFthe fact that a component function of F is bent and study if the number of bent components can be optimal. We consider in particular two classes, one of which is that of APN power functions. We study more deeply the relation between the Walsh transform of γFand the Walsh transform of F. By applying the Titsworth relation to the Walsh transform WγF, we deduce a new relation satisfied by WF2, which is as simple as Chabaud-Vaudenay's characterization by the fourth moment of the Walsh transform (which is in fact a particular case of the new relation), and provides more information. From this new relation, we deduce, for a sub-class of APN functions, a lower bound on the nonlinearity, which is significantly stronger than nl(F) > 0 (the only general known bound). This sub-class of APN functions includes all known APN functions. The question (which is another open problem that we state) arises whether this sub-class equals that of all APN functions, but our bound provides at least a beginning of explanation why all known APN functions have non-weak nonlinearity. We finally show how the nonlinearities of γFand F are related by a simple formula; this leads to a last open problem.

We revisit and take a closer look at a (not so well known) result of a 2017 paper, showing that the differential uniformity of any vectorial function is bounded from below by an expression depending on the size of its image set. We make explicit the resulting tight lower bound on the image set size of differentially$\delta $-uniform functions (which is the only currently known non-trivial lower bound on the image set size of such functions). We also significantly improve an upper bound on the nonlinearity of vectorial functions obtained in the same reference and involving their image set size. We study when the resulting bound is sharper than the covering radius bound. We obtain as a by-product a lower bound on the Hamming distance between differentially$\delta $-uniform functions and affine functions, which we improve significantly with a second bound. This leads us to study what can be the maximum Hamming distance between vectorial functions and affine functions. We provide an upper bound which is slightly sharper than a bound by Liu, Mesnager and Chen when$m < n$, and a second upper bound, which is much stronger in the case (happening in practice) where$m$is near$n$; we study the tightness of this latter bound; this leads to an interesting question on APN functions, which we address (negatively). We finally derive an upper bound on the nonlinearity of vectorial functions by means of their Hamming distance to affine functions and make more precise the bound on the differential uniformity which was the starting point of the paper.

Almost perfect nonlinear (APN) functions over fields of characteristic 2 play an important role in cryptography, coding theory and, more generally, mathematics and information theory. In this paper we deduce a new method for constructing APN functions by studying the isotopic equivalence, concept defined for quadratic planar functions in fields of odd characteristic. In particular, we construct a family of quadratic APN functions which provides a new example of an APN mapping over${\mathbb F}_{2^{9}}$and includes an example of another APN function$x^{9}+ \mathop {\mathrm {Tr}}\nolimits (x^{3})$over${\mathbb F}_{2^{8}}$, known since 2006 and not classified up to now. We conjecture that the conditions for this family are satisfied by infinitely many APN functions.

We investigate the differential properties of a vectorial Boolean function G obtained by modifying an APN function F . This generalizes previous constructions where a function is modified at a few points. We characterize the APN-ness of G via the derivatives of F, and deduce an algorithm for searching for APN functions whose values differ from those of F only on a given set U ⊆ F2n. We introduce a value ΠFassociated with any F, which is invariant under CCZ-equivalence. We express a lower bound on the distance between a given APN function F and the closest APN function in terms of ΠF. We show how ΠFcan be computed efficiently for F quadratic. We compute ΠFfor all known APN functions over F2n. up to n ≤ 8. his is the first new CCZ-invariant for APN functions to be introduced within the last ten years. We derive a mathematical formula for this lower bound for the Gold function F (x) = x3, and observe that it tends to infinity with n. Finally, we describe how to efficiently find all sets U such that, taking G(x) = F (x) + v for x ∈ U and G(x) = F (x) for x ∉ U,G(x) is APN.

We characterize the ANF and the univariate representation of any vectorial function as parts of the ANF and bivariate representation of the Boolean function equal to its graph indicator. We show how this provides, when F is bijective, the expression of F-1and/or allows deriving properties of F-1. We illustrate this with examples and with a tight upper bound on the algebraic degree of F-1by means of that of F. We characterize by the Fourier-Hadamard transform, by the ANF, and by the bivariate representation, that a given Boolean function is the graph indicator of a vectorial function. We also give characterizations of those Boolean functions that are affine equivalent to graph indicators. We express the graph indicators of the sum, product, composition and concatenation of vectorial functions by means of the graph indicators of the functions. We deduce from these results a characterization of the bijectivity of a generic (n,n)-function by the fact that some Boolean function, which appears as a part of the ANF (resp. the bivariate representation) of its graph indicator, is equal to constant function 1. We also address the injectivity of (n,m)-functions. Finally, we study the characterization of the almost perfect nonlinearity of vectorial functions by means of their graph indicators.

Given a vectorial function F : F2n→ F2m, the indicator 1GFof its graph GF= {(x,F(x));x ∈ F2n} allows to express the algebraic degree of F in a simple way. Exploiting the formula, obtained in a previous article, for the graph indicator of a composite function G o F, that involves only a sum of products of 1GFand 1GG, we deduce the exact expression as well as bounds on the algebraic degree of G o F, whose efficiency comes from the fact that the algebraic degree of the product of two Boolean functions is bounded above by the sum of their algebraic degrees, while for a composition, it is bounded above by their product. One of these bounds, that depends on the algebraic degrees of G and 1GF, is tight, general, simple, and most often efficient (for the case where it is not efficient, we give an improved bound, that is a little more complex). As far as we know, it is the first efficient upper bound ever found, that works without any condition on the vectorial functions. It provides a new criterion for the choice of S-boxes in block ciphers. It implies as a corollary a known bound assuming the divisibility of the Walsh transform values by a power of 2. It gives a better view why this latter bound works. All the bounds generalize to more than two functions and this represents also an improvement over the state of the art. When F is a permutation, our expression of the algebraic degree of G o F simplifies into a formula involving the algebraic degrees of the products of a coordinate function of G and coordinate functions of F-1. This implies another known bound showing that the algebraic degree of F-1has more impact on that of G o F than that of F itself. Our approach by graph indicators gives a more complete explanation to this interesting fact. Our results include all the known efficient bounds as particular cases, and clarify the reasons why they work. We also deduce the exact expression of the algebraic degree of the composition of any number of functions, leading to a bound that is much more efficient than what we obtain by applying the known bound several times. We also obtain two bounds on the algebraic degree of G o F, where F is a permutation, given the divisibility by powers of 2 of some Walsh transform values of component functions of F and their sums with a coordinate function of G. We compare all the bounds of this kind obtained so far and show how they are complementary, and we study the generalizations of all (known and new) bounds of this kind to the composition of more than two functions.

CCZ-equivalence is the most general currently known equivalence relation for functions over finite fields preserving planarity and APN properties. However, for the particular case of quadratic planar functions isotopic equivalence is more general than CCZ-equivalence. A recent construction method for APN functions over fields of even characteristic, so-called isotopic shift construction, was instigated by the notion of isotopic equivalence. In this paper we discuss possible applications of the idea of isotopic shift for the case of planar functions. We show that, surprisingly, some of the known planar functions are actually isotopic shifts of each other. This confirms practically the pertinence of the notion of isotopic shift not only for APN functions but also for planar maps.

Linear complementary dual (LCD) cyclic codes were referred historically to as reversible cyclic codes, which had applications in data storage. Due to a newly discovered application in cryptography, there has been renewed interest in LCD codes. In particular, it has been shown that binary LCD codes play an important role in implementations against side-channel attacks and fault injection attacks. In this paper, we first present a new characterization of binary LCD codes in terms of their orthogonal or symplectic basis. Using such a characterization, we solve a conjecture proposed by Galvez et al. on the minimum distance of binary LCD codes. Next, we consider the action of the orthogonal group on the set of all LCD codes, determine all possible orbits of this action, derive simple closed formulas of the size of the orbits, and present some asymptotic results on the size of the corresponding orbits. Our results show that almost all binary LCD codes are odd-like codes with odd-like duals, and about half of q-ary LCD codes have orthonormal basis, where q is a power of an odd prime.

Linear complementary pairs (LCPs) of codes play an important role in armoring implementations against sidechannel attacks and fault injection attacks. One of the most common ways to construct LCP of codes is to use Euclidean linear complementary dual (LCD) codes. In this paper, we first introduce the concept of linear codes with o complementary dual (σ-LCD), which includes known Euclidean LCD codes, Hermitian LCD codes, and Galois LCD codes. Like Euclidean LCD codes, σ-LCD codes can also be used to construct LCP of codes. We show that for q 2, all q-ary linear codes are σ-LCD, and for every binary linear code C, the code {0} × C is σ-LCD. Furthermore, we study deeply σ-LCD generalized quasi-cyclic (GQC) codes. In particular, we provide the characterizations of σ-LCD GQC codes, self-orthogonal GQC codes, and self-dual GQC codes, respectively. Moreover, we provide the constructions of asymptotically good σ-LCD GQC codes. Finally, we focus on σ-LCD abelian codes and prove that all abelian codes in a semisimple group algebra are σ-LCD. The results derived in this paper extend those on the classical LCD codes and show that σ-LCD codes allow the construction of LCP of codes more easily and with more flexibility.

In 2007, Carlet and Ding introduced two parameters, denoted by NbF and NBF, quantifying respectively the balancedness of general functions F between finite Abelian groups and the (global) balancedness of their derivatives DaF(x) = F(x + a) - F(x), a ∈ G \ {0} (providing an indicator of the nonlinearity of the functions). These authors studied the properties and cryptographic significance of these two measures. They provided inequalities relating the nonlinearity NL(F) to NBF for S-box and specifically obtained an upper bound on the nonlinearity that unifies Sidelnikov-Chabaud-Vaudenay's bound and the covering radius bound. At the Workshop WCC 2009 and in its postproceedings in 2011, a further study of these parameters was made; in particular, the first parameter was applied to the functions F + L, where L is affine, providing more nonlinearity parameters. In 2010, motivated by the study of Costas arrays, two parameters called ambiguity and deficiency were introduced by Panario et al. for permutations over finite Abelian groups to measure the injectivity and surjectivity of the derivatives, respectively. These authors also studied some fundamental properties and cryptographic significance of these two measures. Further studies followed without comparing the second pair of parameters to the first one. In this paper, we observe that ambiguity is the same parameter as NBF up to additive and multiplicative constants (i.e., up to rescaling). We perform the necessary work of comparison and unification of the results on NBF and on ambiguity, which have been obtained in the five papers devoted to these parameters. We generalize some known results to any finite Abelian groups. More importantly, we derive many new results on these parameters.

Finding cryptographic primitives satisfying certain properties is a difficult problem. In this domain, besides the algebraic constructions, researchers often use heuristics. There exists a set of interesting problems related to the notion of differential uniformity for a function F:\mathbbF2n→ \mathbbF2m. When n=m, then the best obtainable differential uniformity equals 2, since it is necessarily positive and even, and since examples of differentially 2-uniform functions are known. Heuristics are able to reach such functions; there is then some intuition that heuristics can be used for other open problems related to differential uniformity. When , differential uniformity is bounded by 2n-m+2 from below (when m=n-2, by 6). Unfortunately, we know such functions only for dimensions equal to n=4,5. In this paper, we explore several evolutionary algorithms and problem sizes in order to find functions having differential uniformity equal to 6. Our results show that several solution encodings are able to find such functions but only in dimensions (4, 2) and (5, 3). Since differentially 6-uniform functions were known for those sizes before, our results can be used as a source of new functions in those dimensions and as an indicator that for (6, 4) such functions either do not exist or that it is extremely difficult to find them.

We study the problem of existence of APN functions of algebraic degree n over F2n. We characterize such functions by means of derivatives and power moments of the Walsh transform. We deduce several non-existence results which imply, in particular, that for most of the known APN functions F over F2n. the function x2n-1+ F(x) is not APN, and changing a value of F in a single point then results in non-APN functions. This leads us to conjectures that an APN function modified in one point cannot remain APN and that there exists no APN function of algebraic degree n.

For every positive integers n and m and every even positive integer δ, we derive inequalities satisfied by the Walsh transforms of all vectorial (n, m)-functions and prove that the case of equality characterizes differential δ-uniformity. This provides a generalization to all differentially δ-uniform functions of the characterization of Almost Perfect Nonlinear (APN) functions due to Chabaud and Vaudenay, by means of the fourth moment of the Walsh transform. Such generalization has been missing since the introduction of the notion of differential uniformity by Nyberg in 1994 and since Chabaud-Vaudenay's result in the same year. Moreover, for each even δ ≥ 2, we find several (in fact, an infinity of) such characterizations. In particular, when δ = 2 and δ = 4, we have that, for any (n, n)function [resp. any (n, n - 1)-function)], the arithmetic mean of WF2(u1, v1)WF2(u2, v2)WF2(u1+ u2, v1+ v2) when u1, u2range independently over F2nand v1, v2are nonzero and distinct and range independently over F2mis at least 23n, and that F is APN (resp. is differentially 4-uniform) if and only if this arithmetic mean equals 23n(which is the value we would get with a bent function if such function could exist). These inequalities give more knowledge on the Walsh spectrum of (n, m)-functions. We deduce in particular a property of the Walsh support of highly nonlinear functions. We also consider the completely open question of knowing if the nonlinearity of APN functions is necessarily non-weak (as it is the case for known APN functions); we prove new lower bounds which cover all power APN functions (and hence a large part of known APN functions), which explain why their nonlinearities are not bad, and we discuss the question of the nonlinearity of APN quadratic functions (since almost all other known APN functions are quadratic).

The correlation immunity of Boolean functions is a property related to cryptography, to error correcting codes, to orthogonal arrays (in combinatorics), and in a slightly looser way to sequences. Correlation-immune Boolean functions (in short, CI functions) have the property of keeping the same output distribution when some input variables are fixed. They have been widely used as combiners in stream ciphers to allow resistance to the Siegenthaler correlation attack. Very recently, a new use of CI functions has appeared in the framework of side channel attacks (SCA). To reduce the cost overhead of counter-measures to SCA, CI functions need to have low Hamming weights. This actually poses new challenges since the known constructions which are based on properties of the Walsh-Hadamard transform, do not allow to build unbalanced CI functions. In this paper, we propose constructions of low-weight d th-order CI functions based on the Fourier-Hadamard transform, while the known constructions of resilient functions are based on the Walsh-Hadamard transform. These two transforms are closely related but the resulting constructions are very different. We first prove a simple but powerful result, which makes that one only need to consider the case where d is odd in further research. Then, we investigate how constructing low Hamming weight CI functions through the Fourier-Hadamard transform (which behaves well with respect to the multiplication of Boolean functions). We use the characterization of CI functions by the Fourier-Hadamard transform and introduce a related general construction of CI functions by multiplication. By using the Kronecker product of vectors, we obtain more constructions of low-weight d-CI Boolean functions. Furthermore, we present a method to construct low-weight d-CI Boolean functions by making additional restrictions on the supports built from the Kronecker product.

We study linear complementary pairs (LCP) of codes (C, D), where both codes belong to the same algebraic code family. We especially investigate constacyclic and quasicyclic LCP of codes. We obtain characterizations for LCP of constacyclic codes and LCP of quasi-cyclic codes. Our result for the constacyclic complementary pairs extends the characterization of linear complementary dual (LCD) cyclic codes given by Yang and Massey. We observe that when C and D are complementary and constacyclic, the codes C and D⊥are equivalent to each other. Hence, the security parameter min(d(C), d(D⊥)) for LCP of codes is simply determined by one of the codes in this case. The same holds for a special class of quasi-cyclic codes, namely 2D cyclic codes, but not in general for all quasi-cyclic codes, since we have examples of LCP of double circulant codes not satisfying this conclusion for the security parameter. We present examples of binary LCP of quasi-cyclic codes and obtain several codes with better parameters than known binary LCD codes. Finally, a linear programming bound is obtained for binary LCP of codes and a table of values from this bound is presented in the case d(C) = d(D⊥). This extends the linear programming bound for LCD codes.

Linear codes with complementary duals (LCD) are linear codes whose intersection with their dual are trivial. When they are binary, they play an important role in armoring implementations against side-channel attacks and fault injection attacks. Nonbinary LCD codes in characteristic 2 can be transformed into binary LCD codes by expansion. In this paper, we introduce a general construction of LCD codes from any linear codes. Further, we show that any linear code over Fq(q > 3) is equivalent to a Euclidean LCD code and any linear code over Fq2(q > 2) is equivalent to a Hermitian LCD code. Consequently an [n, k, d]-linear Euclidean LCD code over Fqwith q > 3 exists if there is an [n, k, d]-linear code over Fqand an [n, k, d]-linear Hermitian LCD code over Fq2with q > 2 exists if there is an [n, k, d]-linear code over Fq2. Hence, when q > 3 (resp. q > 2) q-ary Euclidean (resp. q2-ary Hermitian) LCD codes possess the same asymptotical bound as q-ary linear codes (resp. q2-ary linear codes). This gives a direct proof that every triple of parameters [n, k, d] which is attainable by linear codes over Fqwith q > 3 (resp. over Fq2with q > 2) is attainable by Euclidean LCD codes (resp. by Hermitian LCD codes). In particular there exist families of q-ary Euclidean LCD codes (q > 3) and q2-ary Hermitian LCD codes (q > 2) exceeding the asymptotical Gilbert-Varshamov bound. Further, we give a second proof of these results using the theory of Gröbner bases. Finally, we present a new approach of constructing LCD codes by extending linear codes.

This paper is composed of two main parts related to the nonlinearity of vectorial functions. The first part is devoted to maximally nonlinear (n, m) functions (the so-called bent vectorial functions), which contribute to an optimal resistance to both linear and differential attacks on symmetric cryptosystems. They can be used in block ciphers at the cost of additional diffusion/compression/expansion layers, or as building blocks for the construction of substitution boxes (S-boxes), and they are also useful for constructing robust codes and algebraic manipulation detection codes. A main issue on bent vectorial functions is to characterize bent monomial functions Trmn(λxd) from F2nto F2m(where m is a divisor of n) leading to a classification of those bent monomials. We also treat the case of functions with multiple trace terms involving general results and explicit constructions. Furthermore, we investigate some open problems raised by Pasalic et al. and Muratovic-Ribic et al. in a series of papers on vectorial functions. The second part is devoted to the nonlinearity of (n, m)-functions. No tight upper bound is known when n/2 <; m <; n. The covering radius bound is the only known upper bound in this range (the Sidelnikov- Chabaud-Vaudenay bound coincides with it when m = n - 1 and it has no sense when m <; n - 1). Finding better bounds is an open problem since the 1990s. Moreover, no bound has been found during the last 23 years, which improve upon the covering radius bound for a large part of (n, m)-functions. We derive such upper bounds for functions, which are sufficiently unbalanced or which satisfy some conditions. These upper bounds imply some necessary conditions for vectorial functions to have large nonlinearity.

On the one hand, 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 hand, 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 (e.g., only a subset of matching samples are analyzed), 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.

In 2013, Tang, Carlet, and Tang [IEEE TIT 59(1): 653-664, 2013] presented two classes of Boolean functions. The functions in the first class are unbalanced and the functions in the second one are balanced. Both of those two classes of functions have high nonlinearity, high algebraic degree, optimal algebraic immunity, and high fast algebraic immunity. However, they are not 1-resilient which represents a drawback for their use as filter functions in stream ciphers. In this paper, we first propose a large family of 1-resilient Boolean functions having high lower bound on nonlinearity, optimal algebraic immunity, and optimal algebraic degree, that is, meeting the Siegenthaler bound. Most notably, we can mathematically prove that every function in n variables belonging to this family has fast algebraic immunity no less than n - 6, which is the first time that an infinite family of 1-resilient functions with provably high fast algebraic immunity has been invented. Furthermore, we exhibit a subclass of the family which has higher lower bound on nonlinearity than all the known 1-resilient functions with (potentially) optimal algebraic immunity and potentially high fast algebraic immunity.

We study the problem of existence of APN functions of algebraic degree n over F2n. We characterize such functions by means of derivatives and power moments of the Walsh transform. We deduce some non-existence results which mean, in particular, that for most of the known APN functions F over F2nthe function x2n-1+ F(x) is not APN, and changing a value of F in a single point results in non-APN functions.

The role of Boolean functions is prominent in several areas including cryptography, sequences, 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 over the years. There are still many combinations of design criteria left unexplored and in this matter evolutionary computation can play a distinct role. This article concentrates on two scenarios for the 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 functions that have various orders of the correlation immunity and minimal Hamming weight. In both these scenarios we see that evolutionary algorithms are able to find high-quality solutions where genetic programming performs the best.

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*(2n) for every term. We know that the 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.

Boolean functions are essential in many stream ciphers. When used in combiner generators, they need to have sufficiently high values of correlation immunity, alongside other properties. In addition, correlation immune functions with small Hamming weight reduce the cost of masking countermeasures against side-channel attacks. Various papers have examined the applicability of evolutionary algorithms for evolving cryptographic Boolean functions. However, even when authors considered correlation immunity, it was not given the highest priority. Here, we examine the effectiveness of three different EAs, namely, Genetic Algorithms, Genetic Programming (GP) and Cartesian GP for evolving correlation immune Boolean functions. Besides the properties of balancedness and correlation immunity, we consider several other relevant cryptographic properties while maintaining the optimal trade-offs among them. We show that evolving correlation immune Boolean functions is an even harder objective than maximizing nonlinearity.

Boolean plateaued functions and vectorial functions with plateaued components play a significant role in cryptography, sequences for communications, and the related combinatorics and designs. Our knowledge on them is not at a level corresponding to their importance. We introduce new characterizations of plateaued Boolean functions. We give the 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) and autocorrelation functions, and of the power moments of their Walsh transform. This allows us to derive several characterizations of almost perfect nonlinear (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, this 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 the APN power functions, is APN, and has the 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 Carlet-Charpin-Zinoviev (CCZ)-equivalent to a Gold or Kasami APN function, is necessarily extended affine (EA)-equivalent to it.

In this paper, we extend the class of Niho bent function consisting of 2rterms 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 existing quadratic o-monomials. We also calculate the algebraic degree of any function in the extended class.

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 ≤ 12 is given. Nonlinear codes better than linear codes are derived by taking binary images of Z4-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, . . . , 256 and 1≤ k ≤⌊256/t⌋ 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.

Inspired by the previous work of Tu and Deng, we propose two infinite classes of Boolean functions of 2kvariables wherek≥ 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 byproduct 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 variablesn≤ 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≤ 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 tradeoff between all the important cryptographic criteria.

In this paper, most of the known infinite classes of generalized bent functions are analyzed for their relation to the completed Maiorana-McFarland class. This is done using the criterion based on second-order derivatives of a function. In particular, it is shown that, unlike in the binary case, not all quadratic bent functions are EA-equivalent to a function of the Maiorana-McFarland type. This is the first attempt to rise this problem for the generalized bent functions.

This paper consists of two main contributions. First, the Niho bent function consisting of 2rexponents (discovered by Leander and Kholosha) is studied. The dual of the function is found and it is shown that this new bent function is not of the Niho type. Second, all known univariate representations of Niho bent functions are analyzed for their relation to the completed Maiorana-McFarland classM. In particular, it is proven that two families do not belong to the completed classM. The latter result gives a positive answer to an open problem whether the classHof bent functions introduced by Dillon in his thesis of 1974 differs from the completed classM.

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 vectorial 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$\leq 12$by the building up construction. Some nonlinear permutations are constructed by using${\BBZ}_{4}$-codes, based on the notion of dual distance of a possibly nonlinear code.

We show that any Boolean function, in even dimension, equal to the sum of a Boolean functiongwhich is constant on each element of a spread and of a Boolean functionhwhose restrictions to these elements are all linear, is semibent if and only ifgandhare both bent. We deduce a large number of infinite classes of semibent functions in explicit bivariate (respectively, univariate) polynomial form.

In this paper, we consider constructions of rotation symmetric bent functions, which are of the forms: fc(x) = Σi=1m-1ci(Σj=0n-1xjxi+j) + cm(Σj=0m-1xjxm+j) and ft(x) = Σi=0n-1(xixt+ixm+i+ xixt+i) + Σi=0m-1xixm+i, where n = 2m, ciϵ {0,1} (the subscript u of xuin the previous expressions 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.

Computed is the dual of the Niho bent function consisting of 2rexponents 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. This note is a follow-up of the recent paper by Carlet and Mesnager.

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 γFis 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 γFare known only for Gold AB power functions and determining γFfor the rest of AB functions is an open problem. In the present paper we determine γFfor most of the known families of APN and AB functions.

We observe that the CCZ-equivalence of bent vectorial functions over $${{\bf 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.

We show that the first of the two constructions by Q. Wang, J. Peng, H. Kan, and X. Xue, IEEE Transactions on Information Theory, vol. 56, no. 6, pp. 3048-3053, 2010, of Boolean functions satisfying the main criteria for filter functions in stream ciphers, is the same as the construction studied by K. Feng and the author at Asiacrypt 2008, LNCS 5350, pp. 425-440. 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 these kinds of functions can be implemented in a more efficient way than usually believed.

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 numbernof variables with 5 ≤n≤ 19, the proposedn-variable Boolean functions have in fact very good nonlinearity.

This talk will be devoted to symmetric cryptography and more precisely to the Boolean functions it uses for making the systems as nonlinear as possible, allowing them to resist known attacks and hopefully future attacks. These are central objects for the design and the security of symmetric cryptosys- tems (stream ciphers and block ciphers).

The nonlinearity profile of a Boolean function (i.e. the sequence of its minimum Hamming distances nlr(f) to all functions of degrees at most r, for r ges 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 higher order nonlinearities of the multiplicative inverse functions (used in the S-boxes of the AES).

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 F22mto F22m. We check for m = 3 that some of these functions are CCZ-inequivalent to power functions.

This paper introduces the first found infinite classes of almost perfect nonlinear (APN) polynomials which are not Carlet-Charpin-Zinoviev (CCZ)-equivalent to power functions (at least for some values of the number of variables). These are two classes of APN binomials from F2nto F2n(for n divisible by 3, resp., 4). We prove that these functions are extended affine (EA)-inequivalent to any power function and that they are CCZ-inequivalent to the Gold, Kasami, inverse, and Dobbertin functions when n ges 12. 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.

The nonlinearity profile of a Boolean function (i.e., the sequence of its minimum Hamming distances nlr(f) to all functions of degrees at most r, for r ges 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 Advanced Encryption Standard (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.

Because of the 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.

By deriving bounds on character sums of Boolean functions and by using the characterizations, due to Kasami , 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

We exhibit an infinite class of almost perfect nonlinear quadratic polynomials from F2nto F2n(n ges 12, n divisible by 3 but not by 9). We prove that these functions are EA-inequivalent to any power function and that they are CCZ-inequivalent to any Gold function. In a forthcoming full paper, we shall also prove that at least some of these functions are CCZ-inequivalent to any Kasami function

Studying Boolean functions with high algebraic immunity (i.e., which can provide some kind of resistance against algebraic attack) has attracted much attention recently. In FSE 2005, Dalai, Gupta and Maitra presented the first construction of Boolean functions achieving maximum possible algebraic immunity. However, the important cryptographic properties, such as algebraic degree and nonlinearity, of the Boolean functions constructed using that method could not be answered, except (by experiment) when the number of variables was small (at most 16). In this paper we solve this problem for every number of variables. Further we study the structure of the construction in detail, and we deduce an algorithm for fast evaluation of the functions, which is crucial for a practical use in stream ciphers

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

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

Recently, algebraic attacks have received a lot of attention in the cryptographic literature. It has been observed that a Boolean function f used as a cryptographic primitive, and interpreted as a multivariate polynomial over F/sub 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-degree subfunctions are weak in terms of algebraic immunity, and we analyze some existing constructions from this viewpoint. Further, we present a construction method to generate Boolean functions on n variables with highest possible algebraic immunity /spl lceil/n/2/spl rceil/ (this construction, first presented at the 2005 Workshop on Fast Software Encryption (FSE 2005), has been 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.

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.

We observe a property on Boolean functions which explains how work some secondary constructions recently obtained for Boolean bent functions. It leads to a generalization and to a unification of these constructions. It also permits to design highly nonlinear resilient functions from known ones. This construction does not increase the number of variables, contrary to the known general secondary constructions, and it permits to improve some cryptographic characters of the functions (e.g. their algebraic immunity) while keeping good the other characteristics

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 which seem to indicate that the algebraic immunity of a random Boolean function on n variables is at least lfloorn/2rfloor with a very high probability (while the upper bound is lceiln/2rceil, 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. 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

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

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 structure 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/spl les/k/spl les/9 for the fourth type.

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.

Important necessary properties of Boolean functions used as combining functions in stream cipher systems are balancedness, high order correlation immunity, high algebraic degree and high nonlinearity. We give a general secondary construction of functions meeting these constraints.

We classify those cubic m-variable Boolean functions which are (m $4)-resilient. Our main result is that there are four types of such functions, depending on the structure of the support of their Walsh spectra.

The class of bent functions has strong properties and its elements are rare. It contains a subclass of functions which properties are still stronger and which elements are still rarer. Youssef and Gong have proved the existence of such hyper-bent functions in (A. M. Youssef et al. 2001), for every even n. We show that the hyper-bent functions they exhibit are exactly those elements of the well-known /spl Pscr//spl Sscr//sub ap/ class, up to the linear transformations x /spl rarr/ /spl delta/x, /spl delta/ /spl isin/ F/sub 2n/*. We show that hyper-bent functions can all be obtained from some codewords of an extended cyclic code H/sub n/ with small dimension and we deduce from the study of the nonzeroes of H/sub n/ that the algebraic degree of hyper-bent functions is exactly n/2. We also prove that the functions of class /spl Pscr//spl Sscr//sub ap/ are some codewords of weight 2/sup n-1/ - 2/sup n/2-1/ of a subcode of H/sub n/ and we deduce that for some n, depending on the factorization of 2/sup n/ - 1, the only hyper-bent functions on n variables are the elements of the class /spl Pscr//spl Sscr//sub ap//sup #/, obtained from /spl Pscr//spl Sscr//sub ap/ by composing the functions by the transformations x /spl rarr/ /spl delta/x, /spl delta//spl ne/0, and by adding constant functions.

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 nonnormality. Simple proofs are given that, asymptotically, almost all Boolean functions have high algebraic thicknesses and are deeply nonnormal, as well as they have high algebraic degrees and high nonlinearities. We also study in detail the relationship between nonnormality 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.

In this paper, the notion of normal extension is introduced for bent functions, i.e., maximally nonlinear 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 bent function and a nonnormal bent function is always nonnormal.

Families of sequences with low pairwise shifted cross correlations are desirable for applications such as code-division multiple-access (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. 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 of the maximum cross correlation in the old family and the Walsh transform of certain functions.

Cryptographic Boolean functions must be complex to satisfy Shannon's principle of confusion. From the cryptographic viewpoint, the two main criteria in evaluating the complexity of Boolean functions on F/sub 2//sup 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, and, as well, 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 for their behavior).

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 (1968), using Pless (1963) identities. By interpreting some equations, we obtain a necessary condition for a coset to have a "high" minimum weight. Most notably, we are able to distinguish such cosets which have three weights only. We then apply our results to the problem of the nonlinearity of Boolean functions. We particularly study the links between this criterion and the propagation characteristics of a function.

We introduce a generalization to Z/sub 2/k of the Gray map and generalized versions of Kerdock and Delsarte-Goethals codes.

We exhibit a simple condition under which the sum (modulo 2) of characteristic functions of (n/2)-dimensional vector subspaces of (GF(2))/sup 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 Dillon (1974) in his thesis. We deduce a way to construct new classes of Bent functions and exhibit an example.>

Recently the notion on binary codes called Z/sub 4/-linearity was introduced. This notion explains why Kerdock codes and Delsarte-Goethals codes admit formal duals in spite of their nonlinearity. The "Z/sub 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/sub 4/-linear code and its Z/sub 4/-dual is stronger than the standard formal duality and we deduce the weight enumerators of related generalized codes.>

This paper provides a new proof of the fact that the polynomials of degree $2^{m - 2 } $ over the Galois field GF$(2^m)(m > 2)$, which are fully reducible and admit no multiple factor (i.e., which divide $x^{2m} + x$) and whose derivatives are constant are affine polynomials. The author determines explicitly these polynomials, which are related to a problem in coding theory that is recounted.

We prove that the conjecture on Bent sequences stated in the paper written by Kumar, Scholtz and Welch (see J. Combinatorial Theory, Ser A, vol.40, p.90-107, 1985) is false.>