Abstract Recently, Baudrin et al. analyzed a special case of Wagner’s commutative diagram cryptanalysis, referred to as commutative cryptanalysis. For a family $$(E_k)_k$$ ( E k ) k of permutations on a finite vector space G, commutative cryptanalysis exploits the existence of affine permutations $$A,B :G \rightarrow G$$ A , B : G → G , $$I \notin \{A,B\}$$ I ∉ { A , B } such that $$E_k \circ A (x) = B \circ E_k(x)$$ E k ∘ A ( x ) = B ∘ E k ( x ) holds with high probability, taken over inputs x, for a significantly large set of weak keys k. Several attacks against symmetric cryptographic primitives can be formulated within the framework of commutative cryptanalysis, most importantly differential attacks, as well as rotational and rotational-differential attacks. Besides, the notion of c-differentials on S-boxes can be analyzed as a special case within this framework. We discuss the relations between a general notion of commutative cryptanalysis, with A and B being arbitrary functions over a finite Abelian group, and differential cryptanalysis, both from the view of conducting an attack on a symmetric cryptographic primitive, as well as from the view of a theoretical study of cryptographic S-boxes.

Abstract In this work, we study functions that can be obtained by restricting a vectorial Boolean function $$F :\mathbb {F}_{2}^n \rightarrow \mathbb {F}_{2}^n$$ F:F2n→F2n to an affine hyperplane of dimension $$n-1$$ n-1 and then projecting the output to an $$n-1$$ n-1 -dimensional space. We show that a multiset of $$2 \cdot (2^n-1)^2$$ 2·(2n-1)2 EA-equivalence classes of such restrictions defines an EA-invariant for vectorial Boolean functions on $$\mathbb {F}_{2}^n$$ F2n . Further, for all of the known quadratic APN functions in dimension $$n < 10$$ n<10 , we determine the restrictions that are also APN. Moreover, we construct 6368 new quadratic APN functions in dimension eight up to EA-equivalence by extending a quadratic APN function in dimension seven. A special focus of this work is on quadratic APN functions with maximum linearity. In particular, we characterize a quadratic APN function $$F :\mathbb {F}_{2}^n \rightarrow \mathbb {F}_{2}^n$$ F:F2n→F2n with linearity of $$2^{n-1}$$ 2n-1 by a property of the ortho-derivative of its restriction to a linear hyperplane. Using the fact that all quadratic APN functions in dimension seven are classified, we are able to obtain a classification of all quadratic 8-bit APN functions with linearity $$2^7$$ 27 up to EA-equivalence.

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.

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, for the first time, a general strategy for designing ARX symmetric-key primitives with provable resistance against single-trail differential and linear cryptanalysis. The latter has been a long standing open problem in the area of ARX design. The wide-trail design strategy (WTS), that is at the basis of many S-box based ciphers, including the AES, is not suitable for ARX designs due to the lack of S-boxes in the latter. In this paper we address the mentioned limitation by proposing the long trail design strategy (LTS) – a dual of the WTS that is applicable (but not limited) to ARX constructions. In contrast to the WTS, that prescribes the use of small and efficient S-boxes at the expense of heavy linear layers with strong mixing properties, the LTS advocates the use of large (ARX-based) S-Boxes together with sparse linear layers. With the help of the so-called long-trail argument , a designer can bound the maximum differential and linear probabilities for any number of rounds of a cipher built according to the LTS. To illustrate the effectiveness of the new strategy, we propose Sparx – a family of ARX-based block ciphers designed according to the LTS. Sparx has 32-bit ARX-based S-boxes and has provable bounds against differential and linear cryptanalysis. In addition, Sparx is very efficient on a number of embedded platforms. Its optimized software implementation ranks in the top 6 of the most software-efficient ciphers along with Simon , Speck , Chaskey, LEA and RECTANGLE. As a second contribution we propose another strategy for designing ARX ciphers with provable properties, that is completely independent of the LTS. It is motivated by a challenge proposed earlier by Wallén and uses the differential properties of modular addition to minimize the maximum differential probability across multiple rounds of a cipher. A new primitive, called LAX , is designed following those principles. LAX partly solves the Wallén challenge.