Extended Affine (EA) equivalence is the equivalence relation between two vectorial Boolean functions$F$and$G$such that there exist two affine permutations$A$,$B$, and an affine function$C$satisfying$G = A \circ F \circ B + C$. While the problem has a simple formulation, it is very difficult in practice to test whether two functions are EA-equivalent. This problem has two variants:EA-partitioningdeals with partitioning a set of functions into disjoint EA-equivalence classes, andEA-recoveryis about recovering the tuple$(A,B,C)$if it exists. In this paper, we present a new algorithm that efficiently solves the EA-recovery problem for quadratic functions. Although its worst-case complexity occurs when dealing with APN functions, it supersedes, in terms of performance, all previously known algorithms for solving this problem for all quadratic functions and in any dimension, even in the case of APN functions. This approach is based on the Jacobian matrix of the functions, a tool whose study in this context can be of independent interest. The best approach for EA-partitioning in practice mainly relies on class invariants. We provide an overview of the known invariants along with a new one based on theortho-derivative. This new invariant is applicable to quadratic APN functions, a specific type of functions that is of great interest, and of which tens of thousands need to be sorted into distinct EA-classes. Our ortho-derivative-based invariant is very fast to compute, and it practically always distinguishes between EA-inequivalent quadratic APN functions.

A growing number of connected objects, with their high performance and low-resources constraints, are embedding lightweight ciphers for protecting the confidentiality of the data they manipulate or store. Since those objects are easily accessible, they are prone to a whole range of physical attacks, one of which are fault attacks against which countermeasures are usually expensive to implement, especially on off-the-shelf devices. For such devices, we propose a new generic software countermeasure, using SIMD instructions available in almost any off-the-shelf devices, to thwart most fault attacks while preserving the performances of the targeted cipher.

The existence of almost perfect nonlinear (APN) permutations operating on an even number of variables was a long-standing open problem, until an example with six variables was exhibited by Dillon et al. in 2009. However it is still unknown whether this example can be generalized to any even number of inputs. In a recent work, Perrin et al. described an infinite family of permutations, named butterflies, operating on (4k+2) variables and with differential uniformity at most 4, which contains the Dillon APN permutation. In this paper, we generalize this family, and we completely solve the two open problems raised by Perrin et al. Indeed we prove that all functions in this larger family have the best known nonlinearity. We also show that this family does not contain any APN permutation besides the Dillon permutation, implying that all other functions have differential uniformity exactly four.

We present a study on the algebraic degree of iterated permutations seen as multivariate polynomials. The main result shows that this degree depends on the algebraic degree of the inverse of the permutation which is iterated. This result is also extended to noninjective balanced vectorial functions where the relevant quantity is the minimal degree of the inverse of a permutation expanding the function. This property has consequences in symmetric cryptography since several attacks or distinguishers exploit a low algebraic degree, like higher order differential attacks, cube attacks, and cube testers, or algebraic attacks. Here, we present some applications of this improved bound to a higher degree variant of the block cipherKN, to the block cipher Rijndael-256 and to the inner permutations of the hash functions ECHO and JH.

A divide-and-conquer cryptanalysis can often be mounted against some keystream generators composed of several (possibly nonlinear) independent devices combined by a Boolean function. In particular, any parity-check relation derived from the periods of some constituent sequences usually leads to a distinguishing attack whose complexity is determined by the bias of the relation. However, estimating this bias is a difficult problem since the piling-up lemma cannot be used. Here, we give two exact expressions for this bias. Most notably, these expressions lead to a new algorithm for computing the bias of a parity-check relation, and they also provide some simple formulas for this bias in some particular cases which are commonly used in cryptography, namely resilient functions and plateaued functions. We also show how to build parity-check relations with the highest possible bias in some particularly relevant cases.

We provide an extensive study of the differential properties of the functionsx→x2t-1 over \BBF2n, for 1tn. We notably show that the differential spectra of these functions are determined by the number of roots of the linear polynomialsx2t+bx2+(b+1)xwherebvaries in \BBF2n. We prove a strong relationship between the differential spectra ofx→x2t-1 andx→x2s-1 fors=n-t+1. As a direct consequence, this result enlightens a connection between the differential properties of the cube function and of the inverse function. We also determine the complete differential spectra ofx→x7by means of the value of some Kloosterman sums, and ofx→x2t-1 fort∈ {[n/2], [n/2]+1,n-2}.

Some properties of the differential spectra of power functions, i.e., monomials mappings on F2n, are investigated. We focus in particular on functions with a small differential uniformity and on some infinite families of power functions.

A new type of distinguishing property, named the zero-sum property has been recently presented by Aumasson and Meier. It has been applied to the inner permutation of the hash function KECCAK and it has led to a distinguishing property for the KECCAK-f permutation up to 16 rounds, out of 24 in total. Here, we additionally exploit some spectral properties of the KECCAK-f permutation and we improve the previously known upper bounds on the degree of the inverse permutation after a certain number of rounds. This result enables us to extend the zero-sum property to 18 rounds of the KECCAK-f permutation, which was the number of rounds in the previous version of KECCAK submitted to the SHA-3 competition.

A divide-and-conquer cryptanalysis can often be mounted against some keystream generators composed of several (nonlinear) independent devices combined by a Boolean function. In particular, any parity-check relation derived from the periods of some constituent sequences usually leads to a distinguishing attack whose complexity is determined by the bias of the relation. However, estimating this bias is a difficult problem since the piling-up lemma cannot be used. Here, we give two exact expressions for this bias. Most notably, these expressions lead to a new algorithm for computing the bias of a parity-check relation, and they also provide some simple formulae for this bias in some particular cases which are commonly used in cryptography.

We study the Boolean functions on F2En, n = 6r, of the form x rarr Tr (lambdaxd) with d = 22r+ 2r+ 1. Our main result is the characterization of those lambda for which they are bent

We investigate some open problems on almost perfect nonlinear (APN) functions over a finite field of characteristic$2$. We provide new characterizations of APN functions and of APN permutations by means of their component functions. We generalize some results of Nyberg (1994) and strengthen a conjecture on the upper bound of nonlinearity of APN functions. We also focus on the case of quadratic functions. We contribute to the current works on APN quadratic functions by proving that a large class of quadratic functions cannot be APN.

We investigate some open problems on almost perfect nonlinear (APN) functions over a finite field of characteristic 2. We provide a new characterization of APN mappings and of APN permutations by means of their component functions. We also focus on the case of quadratic functions. Most notably, we prove that a class of quadratic functions cannot be APN. Our result strengthens the conjecture that all quadratic APN functions are power functions, up to equivalence

We present an extensive study of symmetric Boolean functions, especially of their cryptographic properties. Our main result establishes the link between the periodicity of the simplified value vector of a symmetric Boolean function and its degree. Besides the reduction of the amount of memory required for representing a symmetric function, this property has some consequences from a cryptographic point of view. For instance, it leads to a new general bound on the order of resiliency of symmetric functions, which improves Siegenthaler's bound. The propagation characteristics of these functions are also addressed and the algebraic normal forms of all their derivatives are given. We finally detail the characteristics of the symmetric functions of degree at most 7, for any number of variables. Most notably, we determine all balanced symmetric functions of degree less than or equal to 7.

In a recent paper , it was shown that the restrictions of bent functions to subspaces of codimension 1 and 2 are highly nonlinear. Here, we present an extensive study of the restrictions of bent functions to affine subspaces. We propose several methods which are mainly based on properties of the derivatives and of the dual of a given bent function. We solve an open problem due to Hou . We especially describe the connection, for a bent function, between the Fourier spectra of its restrictions and the decompositions of its dual. Most notably, we show that the Fourier spectra of the restrictions of a bent function to the subspaces of codimension 2 can be explicitly derived from the Hamming weights of the second derivatives of the dual function. The last part of the paper is devoted to some infinite classes of bent functions which cannot be decomposed into four bent functions.

The Hamming distance of a Boolean function to the functions having many linear structures is an important cryptographic parameter. Most notably, the accuracy of the approximation of the combining function by a function of fewer variables is a major issue in most attacks against combination generators. Here, we show that the distance of a function to the functions having a k-dimensional linear space is highly related to its nonlinearity. In particular, we prove that there is no accurate approximation of any highly nonlinear function by a function depending on a small subset of its input variables.

We study the weight distributions of cosets of the first-order Reed-Muller code R(1,m) for odd m, whose minimum weight is greater than or equal to the so-called quadratic bound. Some general restrictions on the weight distribution of a coset of R(1,m) are obtained by partitioning its words according to their weight divisibility. Most notably, we show that there are exactly five weight distributions for optimal cosets of R(1,7) in R(5,7) and that these distributions are related to the degree of the function generating the coset. Moreover, for any odd m/spl ges/9, we exhibit optimal cubic cosets of R(1,m) whose weights take on exactly five values.

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 study [2m-1,2m]-binary linear codes whose weights lie between w0 and 2m-w0, where w0 takes the highest possible value. Primitive cyclic codes with two zeros whose dual satisfies this property actually correspond to almost bent power functions and to pairs of maximum-length sequences with preferred crosscorrelation. We prove that, for odd m, these codes are completely characterized by their dual distance and by their weight divisibility. Using McEliece's theorem we give some general results on the weight divisibility of duals of cyclic codes with two zeros; specifically, we exhibit some infinite families of pairs of maximum-length sequences which are not preferred.

We prove the long-standing conjecture of Welch stating that for odd n=2m+1, the power function x/sup d/ with d=2/sup m/+3 is maximally nonlinear on GF(2/sup n/) or, in other terms, that the crosscorrelation function between a binary maximum-length linear shift register sequence of degree n and a decimation of that sequence by 2/sup m/+3 takes on precisely the three values -1, -1/spl plusmn/2/sup m+1/.

An algorithm for finding minimum-weight words in large linear codes is developed. It improves all previous attacks on the public-key cryptosystems based on codes and it notably points out some weaknesses in McEliece's (1978) cipher. We also determine with it the minimum distance of some BCH codes of length 511.