This article examines the security of symmetric cryptographic primitives, focusing on the resistance against differential and commutative cryptanalysis. It begins by discussing the wide-trail strategy, a method used to argue the security of key-alternating substitution-permutation-networks (SPNs) like the Advanced Encryption Standard (AES). The text then delves into the concept of differential uniformity, a measure of resistance against differential attacks, and its generalizations, such as c-differential uniformity. The article explores the relationships between these concepts and commutative cryptanalysis, a unifying framework that encompasses various attack vectors, including differential, rotational, and rotational-differential attacks. It provides a detailed analysis of the applicability of commutative attacks, the vulnerability of S-boxes to such attacks, and the generation of affine permutations with specific cycle types. Furthermore, the article discusses the generalization of differential cryptanalysis using alternative group operations and presents links between these generalized attacks, differential cryptanalysis of conjugate ciphers, and the commutative cryptanalysis framework. The text includes a comprehensive survey of the theory behind the classification of linear and affine permutations sharing the same cycle type, as well as detailed examples and proofs to illustrate the concepts discussed. The article concludes with a discussion on the implications of the order of affine permutations not being a power of p and the relationship between commutative cryptanalysis and differential cryptanalysis of conjugates.
AI Generated
This summary of the content was generated with the help of AI.
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\) of permutations on a finite vector space G, commutative cryptanalysis exploits the existence of affine permutations \(A,B :G \rightarrow G\), \(I \notin \{A,B\}\) such that \(E_k \circ A (x) = B \circ E_k(x)\) holds with high probability, taken over inputs x, for a significantly large set of weak keysk. 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.
Notes
Parts of the results were presented by the second author as an invited talk at WCC 2024.
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
1 Introduction
Symmetric cryptography is a crucial building block for protecting our everyday communication. The security of symmetric cryptographic primitives is measured by the absence of any discovered attack through years of public scrutiny by the scientific community and should be supported by arguments why known classes of attacks do not apply. One of the most promising and widely-studied attack vectors is differential cryptanalysis [8], a statistical attack that aims to break a cipher by tracing the propagation of pairs of inputs \((x,x+\alpha )\) for a fixed input difference \(\alpha \). In a nutshell, a family of permutations \((E_{k})_k\) is considered broken by differential cryptanalysis if there exists a non-zero input difference \(\alpha \) and an output difference \(\beta \) for which the probability (originally taken over all keys k and inputs x) that \(E_k(x+\alpha ) = E_k(x) + \beta \) holds is higher than one would expect for a permutation chosen uniformly at random.
Strictly speaking, the probability does not have to be taken over the whole key space and an empirical estimation of this probability could already give information about the key. Moreover, a cipher would already be broken if the probability is higher than expected for a significant subset of all possible keys. This case, that is much harder to analyze in general, is referred to as the weak-key model and keys for which the probability is large are called weak keys. As we will see below, weak-key attacks are, inherently, of interest in the more general setting of commutative cryptanalysis that we study in this work.
Advertisement
Because differential cryptanalysis poses a serious threat to cryptographic primitives, designers are expected to provide sufficient arguments for the resistance of their proposed ciphers against these attacks. For key-alternating substitution-permutation-networks (SPNs), one of the most employed arguments is the so-called wide-trail strategy [17] that estimates the security of a cipher from a security analysis of its building blocks, i.e., their S-boxes (that are functions on a small input size) and linear layer. The Advanced Encryption Standard (AES) [18] is the most prominent example of a symmetric cryptographic primitive employing the wide-trail strategy for arguing its security.
At EUROCRYPT 1993, Nyberg introduced the notion of differential uniformity of a function between two finite Abelian groups as a measure for the resistance against differential attacks.
[Style2 Style1 Style3 Style3]Definition 1
[35] Let \(S :G_1 \rightarrow G_2\) be a function between two finite Abelian groups \(G_1\) and \(G_2\). The differential uniformity of S is defined as
The wide-trail strategy suggests that choosing an S-box with low differential uniformity together with a “suitable” linear layer provides sufficient resistance against differential cryptanalysis. This motivates the study of the differential uniformity (and more general the differential spectrum, i.e., the multiset of values \(|\{x \in G_1 \mid S(x+\alpha ) = S(x) + \beta \} |\) over all \(\alpha \ne 0\) and \(\beta \)) of S-boxes in a kind of isolated manner. Indeed, the definition of differential uniformity triggered a significant amount of research in mathematics and cryptography. The most prominent line of research focuses on functions with optimal values for their differential uniformity in case of \(G_1\) and \(G_2\) being elementary Abelian p-groups. From a cryptographic point of view, the case of \(p= 2\) is the most important (as most of the ciphers are defined over an \(\mathbb {F}_2\)-vector space),1 In that case, the optimal value on the differential uniformity \(\Delta _S\) is 2 and in the case of \(G_1 = G_2=\mathbb {F}_2^n\), functions achieving this optimal value are called almost perfect nonlinear (APN) functions. In the case of odd p and \(G_1 = G_2\), the optimal value on \(\Delta _S\) is 1 and functions achieving this optimum are called perfect nonlinear or planar functions. APN and planar functions are also of interest in finite geometry and combinatorics. We refer to the book by Carlet [13, Chapter 11] and the survey by Pott [36] for more information on the significant amount of research conducted in this area. Within the recent years, the notion of differential uniformity was generalized in various ways and studied from a mathematical point of view. A particular kind of generalization, attracting lots of interest, is the notion of c-differential uniformity.
Advertisement
[Style2 Style1 Style3 Style3]Definition 2
[20] Let \(S :G \rightarrow G\) be a function on a finite field G and let \(c \in G\). The c-differential uniformity of S is defined as
$$\begin{aligned} \phantom {a}_c\Delta _S {:}{=} \max _{\alpha \in G, \beta \in G, \alpha \ne 0 \text{ if } c = 1} |\{x \in G \mid S(x+\alpha ) = c \cdot S(x) + \beta \} |. \end{aligned}$$
The notion of differential uniformity corresponds to the notion of c-differential uniformity for \(c = 1\). Quite some papers appeared studying the general notion of c-differential uniformity (and more generally the c-differential spectrum) of functions, see e.g., [34, Sect. 5] for a survey. However, to the best of our knowledge, the notion of c-differential uniformity (with \(c \ne 1\)) was never successfully applied to attack a cryptographic primitive and an application of the framework of c-differentials to cryptography is yet to be shown. The work [2] already questioned its applicability for building cryptographic attacks due to a non-deterministic propagation of c-differentials through a linear layer and a key addition within a cipher.
c-differentials, as well as other existing cryptographic attacks such as rotational cryptanalysis [27] and rotational-differential cryptanalysis [1] can be formulated within the unifying framework of commutative cryptanalysis [4, 37]. In a nutshell, if \((E_k)_k\) is a family of permutations on a finite Abelian group G, commutative cryptanalysis exploits the existence of functions \(A,B :G \rightarrow G\) such that \(E_k \circ A (x) = B \circ E_k(x)\) holds with high probability (taken over inputs x) for a significantly large set of weak keys k. In this framework, it is crucial to impose further restrictions on the choice of A and B to avoid trivial properties (e.g., both A and B being the identity). Besides differential attacks, as well as rotational attacks and rotational-differential attacks, we have examples of commutative attacks (with probability 1) in the weak-key model, when A and B are restricted to be affine permutations on a finite vector space G, see [4].
Our contribution In this work, we discuss the relations between a general commutative attack and differential cryptanalysis. Our results are grouped into four parts:
1.
In Sect. 3, we discuss the applicability of the general framework of commutative cryptanalysis with respect to conducting an attack against a cryptographic primitive. Under some simplifying assumptions, we outline why a commutative attack more general than a differential attack is necessarily in the weak-key model, and is not applicable in the case of independent whitening keys. In particular, we see that c-differentials with \(c \ne 1\) belong to the class of distinguishers from this framework that has the least potential for an attack. The main results of this section are stated in Corollaries 1 and 2.
2.
Motivated by applications of the commutative framework and the existing examples in the fixed/weak key model, in Sect. 4 we then study S-boxes that are vulnerable to commutative attacks and show lower bounds on the differential uniformity of such S-boxes. These bounds link the number of inputs for which a commutative property holds to the number of weak-keys in a trail-based attack and to the differential uniformity. As the most important special case, the focus is on commutative properties with affine permutations A, B (in which case G is a finite vector space). In a nutshell, we show that an S-box possessing a non-trivial deterministic affine commutative property (i.e., a non-trivial affine self-equivalence) that allows for many weak keys necessarily has high differential uniformity.
3.
We discuss in Sect. 5 the mathematically interesting question of how to generate affine permutations A, B of \(\mathbb {F}_p^n\) having the same cycle type and from this the question how to generate all S-boxes S for which \(S \circ A = B \circ S\). The first question is a classical problem studied in a series of papers and our contribution is to give an, as far as we know, first comprehensive survey on this topic. We close this section by analyzing the effect on the self-equivalence if the order of A and thus B is not a power of p.
4.
As the last part, we discuss in Sect. 6 a generalization of differential cryptanalysis using alternative group operations (see [15]) and present links between these kind of generalized attacks, differential cryptanalysis of conjugate ciphers, and the commutative cryptanalysis framework. We show in particular that the “alternative differential” trails considered in [15] can be interpreted as commutative trails, or as regular differential trails of a conjugate cipher. We then provide a detailed analysis of some of the toy ciphers illustrating those earlier results using our own framework.
2 Preliminaries
Throughout this work, let \((G,+)\) be a finite Abelian group. For an element \(\alpha \in G\), we denote by \(T_\alpha :G \rightarrow G\) the translation \(x \mapsto x + \alpha \). As an important and relevant special case, we will focus on G having the additional structure of a vector space, i.e., \(G = \mathbb {F}_p^n\) for a prime p. We denote by \(\textrm{GL}(n,\mathbb {F}_p)\) the general linear group of degree n over \(\mathbb {F}_p\). By \(\textrm{AGL}(n,\mathbb {F}_p)\), we denote the set of all affine bijections over \(\mathbb {F}_p^n\) and by I the identity in \(\textrm{AGL}(n,\mathbb {F}_p)\). With \(e_1,\dots ,e_n\) we denote the canonical unit vectors in \(\mathbb {F}_p^n\), i.e. \(e_1=(1,0\dots ,0)^t, e_2=(0,1,0,\dots ,0)^t, \dots \).
A function \(S :\mathbb {F}_p^n \rightarrow \mathbb {F}_p^n\) can be uniquely expressed in its algebraic normal form, i.e., a multivariate polynomial expression of the form
where \(x^u {:}{=} \prod _{i=0}^{n-1}x_i^{u_i}\) and \(a_u \in \mathbb {F}_p^n\). The algebraic degree of S is defined as the degree of its algebraic normal form, i.e., \(\max \{\sum _{i=0}^{n-1}u_i \mid a_u \ne 0\}\). The affine functions are exactly those of algebraic degree at most 1. A function of algebraic degree 2 is called quadratic.
For a function \(S:G \rightarrow G\) and functions \(A, B :G \rightarrow G\), let
$$\begin{aligned} \Gamma _S(A,B) {:}{=} |\left\{ x \in G \mid S \circ A(x) = B \circ S(x)\right\} |. \end{aligned}$$
The notion of differential uniformity then corresponds to the maximum taken over translations A, B of \(\Gamma _S(A,B)\), i.e., \(\Delta _S = \max _{\alpha \in G {\setminus } \{0\}, \beta \in G} \Gamma _S(T_\alpha ,T_\beta )\). If G is a finite field \(\mathbb {F}_q\) and \(m_c :G \rightarrow G, x \mapsto cx\) the multiplication by \(c \in G\), for the c-differential uniformity \(\phantom {a}_c\Delta _S\) of S, we have
For a mapping \(A :G \rightarrow G\), we denote by \(\textrm{Fix}(A)\) the set of fixed points of A, i.e., \(\{x \in G \mid A(x) = x\}\). For \(C \in \textrm{AGL}(n,\mathbb {F}_p)\), we have
where \(C = L_C + c_C\) with \(L_C = C + C(0)\) being linear and \(c_C = C(0)\). In case \(\textrm{Fix}(C)\) is non-empty, it forms an affine subspace of \(\mathbb {F}_p^n\). By \(\textrm{ord}(C)\), we denote the order of C, i.e.,
A block cipher over G is a finite family of permutations on G, indexed by a key from a finite key space \(\kappa \). The notion of pseudorandom permutation security is formalized as follows (see e.g., [33]).
[Style2 Style1 Style3 Style3]Definition 3
(Pseudorandom permutation distinguisher) Let \(E = (E_k)_{k \in \kappa }\) be a finite family of permutations on G (indexed by a key k from the finite key space \(\kappa \)). A PRP-distinguisher against E is an algorithm \(\mathcal {A}\) that interacts with an oracle \(\mathcal {O} :G \rightarrow G\) and outputs a bit \(b \in \{0,1\}\).
The CPA-security game works as follows:
1.
With probability \(\frac{1}{2}\), the oracle \(\mathcal {O}\) is instantiated with \(E_k\) for a uniformly random choice \(k \in \kappa \). With probability \(\frac{1}{2}\), the oracle \(\mathcal {O}\) is instantiated with a permutation \(P :G \rightarrow G\) chosen uniformly at random from the set of all permutations on G, denoted \(\textrm{Perm}(G)\).
2.
\(\mathcal {A}\) runs with oracle access to \(\mathcal {O}\) and outputs \(b \in \{0,1\}\).
3.
\(\mathcal {A}\) wins the security game if
$$\begin{aligned} b = {\left\{ \begin{array}{ll} 1 & \text { if } \mathcal {O} = E_k \\ 0 & \text { if } \mathcal {O} = P \end{array}\right. }. \end{aligned}$$
We write \(\mathcal {A}^{\mathcal {O}} = b\) for indicating the event that \(\mathcal {A}\) interacts with \({\mathcal {O}}\) and outputs b.
[Style2 Style1 Style3 Style3]Definition 4
(Advantage) Let \(E = (E_k)_{k \in \kappa }\) be a finite family of permutations on G. The advantage of the PRP-distinguisher \(\mathcal {A}\) against E is defined as
where k is chosen uniformly at random from \(\kappa \) and P is chosen uniformly at random from \(\textrm{Perm}(G)\).
The PRP-security of a block cipher is then specified by an upper bound on the advantage over all PRP-distinguishers \(\mathcal {A}\) against it, where \(\mathcal {A}\) is only allowed a limited amount of computational resources (like number of computation steps, number of oracle queries, or memory).
In the commutative cryptanalysis framework, we focus on one special kind of PRP-distinguisher.
[Style2 Style1 Style3 Style3]Definition 5
(Commutative distinguisher) Let \(A,B :G \mapsto G\). A commutative distinguisher is a PRP-distinguisher \(\mathcal {C}(A,B)\) that operates the following way:
1.
\(\mathcal {C}(A,B)\) encrypts x and A(x) for a uniformly random choice of \(x \in G\).
2.
\(\mathcal {C}(A,B)\) returns 1 if \(\mathcal {O}(A(x)) = B(\mathcal {O}(x))\) and 0 otherwise.
In other words, a commutative distinguisher test for a uniformly random choice of plaintext, whether A commutes with B over \(\mathcal {O}\) for this particular input. We stress that for a simplified analysis, a commutative distinguisher is only allowed one choice for \(x \in G\), i.e., only two queries to \(\mathcal {O}\). The benefit is that we can ignore the data complexity of the distinguisher in the analysis and that we obtain a simple expression of the advantage, as discussed in the next section.
3 On the advantage of a commutative distinguisher
For a permutation P over G and \(A,B :G \mapsto G\), we denote by \(\textrm{Pr}[A \overset{P}{\rightarrow }\ B]\) the probability that \(P(A(x)) = B(P(x))\) over uniform random choices of \(x \in G\), i.e.,
For a commutative distinguisher \(\mathcal {C}(A,B)\), we then have \(\textrm{Pr}[\mathcal {C}(A,B)^{P} = 1] = \textrm{Pr}[A \overset{P}{\rightarrow }\ B]\), so that
The term \(\textrm{Pr}_{P \in \textrm{Perm}(G), x \in G}[P \circ A(x) = B \circ P(x)]\) can be given explicitly based on the fixed points of A and B, as we show in the following lemma.
where the last step comes from the fact that \(A(x) \ne x\) and \(P(x) = y\), which means that \(P \circ A(x)\) is drawn uniformly at random from \(G \setminus \{y\}\). In total, this means that
Because the distinguishing advantage of a commutative distinguisher \(\mathcal {C}(A,B)\) depends on the cardinality of the sets of fixed points of A and B, the notion of affine uniformity as defined in [4] is only meaningful if we take the maximum restricted to sets \(\mathcal {A} \subseteq \textrm{AGL}(n,\mathbb {F}_p)^2\) such that for all \((A, B), (C, D) \in \mathcal {A}\), we have \(|\textrm{Fix}(A)|= |\textrm{Fix}(C)|\), and \(|\textrm{Fix}(B)|= |\textrm{Fix}(D)|\). This is consistent with the notions of differential uniformity and c-differential uniformity (except for the cases where \(\alpha =0\) or \(\beta = 0\), which have to be analyzed separately).
3.1 Commutative distinguishers over iterated permutations
In the following, we consider the permutation \(F :G \rightarrow G\), where \(F = F_3 \circ F_2 \circ F_1\) for permutations \(F_1,F_2,F_3 :G \rightarrow G\). Let \(A,B :G \mapsto G\). We now study how the the quantity \(\Gamma _{F}(A,B)\) can be expressed by means of commutative trails. For \(C_1,C_2 :G \rightarrow G\), we define
as the number of inputs x following the commutative trail\(A \rightarrow C_1 \rightarrow C_2 \rightarrow B\). Since for any \(P :G \rightarrow G\), we have \(G = \bigcup _{\gamma \in G} \{ x \mid P \circ A(x) = P(x) + \gamma \}\), we obtain that \(\Gamma _F(A,B)\) can be expressed as a sum over \(\Gamma _{F_1,F_2,F_3}(A,T_\gamma , T_\delta ,B)\) for all translations \(T_\gamma , T_\delta \), i.e.,
If we consider the keyed permutation \(F^{(k_1,k_2)} :G \rightarrow G\), where \(F^{(k_1,k_2)} = F_3 \circ T_{k_2} \circ F_2 \circ T_{k_1} \circ F_1\), see Fig. 1, we can generalize the well-known trail formula from [29] on the expected differential probability over iterated ciphers (with independent round keys) as follows.
Fig. 1
A commutative distinguisher over an iterated cipher containing commutative trails
Proposition 1
(Trail formula) Let \(F = (F^{k})_{k \in G \times G}\) be the family of permutations defined by \(F^{(k_1,k_2)} = F_3 \circ T_{k_2} \circ F_2 \circ T_{k_1} \circ F_1\) for permutations \(F_1,F_2,F_3 :G \rightarrow G\) and let \(A,B :G \rightarrow G\). We have
For the case of \(F_1 = F_3 = \textrm{id}_G\) we get the following result, which gives an upper bound on the advantage of a commutative distinguisher against an Even-Mansour construction.
Corollary 1
Let \(F = (F^{k})_{k \in G \times G}\) be the family of permutations defined by \(F^{(k_1,k_2)} = T_{k_2} \circ R \circ T_{k_1}\) for a permutation \(R :G \rightarrow G\) and let \(\mathcal {C}(A,B)\) be a commutative distinguisher against F. Then,
where the second equality holds because \(\textrm{Pr}[T_\gamma \overset{R}{\rightarrow }\ T_\delta ] = 1\) if \(\gamma = \delta = 0\) and \(\textrm{Pr}[T_\gamma \overset{R}{\rightarrow }\ T_\delta ] = 0\) if exactly one of \(\gamma \) or \(\delta \) is zero. We can bound above \(\textrm{Pr}[T_\gamma \overset{R}{\rightarrow }\ T_\delta ]\) by \(\frac{\Delta _R}{|G |}\), which yields
Let us define \(K {:}{=} \frac{(|G |- |\textrm{Fix}(A) |) (|G |- |\textrm{Fix}(B) |)}{|G |^2 (|G |- 1)}\). We obtain for the advantage
$$\begin{aligned} \textrm{Adv}_{\mathcal {C}(A,B)}&= \left|-K + J \right|= {\left\{ \begin{array}{ll} J-K & \text { if } J \ge K \\ K-J & \text { if } J < K. \end{array}\right. } \end{aligned}$$
In the first case, \(\textrm{Adv}_{\mathcal {C}(A,B)} = J-K \le \frac{(|G |- |\textrm{Fix}(A) |) (|G |- |\textrm{Fix}(B) |)}{|G |^2 } \cdot \left( \frac{\Delta _R}{|G |} - \frac{1}{|G |-1}\right) \le \frac{\Delta _R}{|G |} - \frac{1}{|G |-1}\). In the second case, \(\textrm{Adv}_{\mathcal {C}(A,B)} = K-J \le K \le \frac{1}{|G |-1}\).
Suppose now that one of \(A- \textrm{id}_A\) or \(B - \textrm{id}_G\) is invertible. Without loss of generality, let us assume \(B - \textrm{id}_G\) is invertible. Then, \(\textrm{Pr}_{x \in G}[(B-\textrm{id}_G)(x) = \delta ]\) is equal to \(1/|G |\) independently of \(\delta \) and we get
and thus \(\textrm{Adv}_{\mathcal {C}(A,B)} = 0\). \(\square \)
If we assume R in Corollary 1 to be a keyed permutation as well, we can take F as being a key-alternating block cipher (with independent round keys). We then obtain the following bounds on the advantage.
Corollary 2
Let \(\kappa = G \times \kappa _m \times G\) and let \(E = (E_k)_{k \in \kappa }\) be a finite family of permutations defined by \(E_{(k_1,k_m,k_2)} = T_{k_2} \circ E_m^{k_m} \circ T_{k_1}\) for a finite family of permutations \((E_m^{k_m})_{k_m \in \kappa _m}\). Let \(\mathcal {C}(A,B)\) be a commutative distinguisher against E. Then,
and for \(\gamma \ne 0, \delta \ne 0\), we have \(\frac{1}{|\kappa _m |} \sum _{k_m \in \kappa _m}\textrm{Pr}[T_\gamma \overset{E_m^{k_m}}{\rightarrow } T_\delta ]\le \max _{\gamma ,\delta \in \mathbb {F}_p^n, \gamma \ne 0} \textrm{ECP}[T_\gamma \overset{E_m}{\rightarrow }\ T_\delta ]\). \(\square \)
Those bounds show that the security of a key-alternating block cipher (on average over all round keys) against commutative attacks is the same as the security against differential attacks. This fact is caused by the addition of the whitening keys and is not surprising, as a similar result has been shown in the context of t-wise independence [31, Lemma 2] (the proof is found in the full version [32]). However, that result uses the probability distribution of all differentials with fixed input difference—a quantity that is typically infeasible to compute. In contrast, the adversary we consider makes use of one differential only—an assumption which is in line with most differential attacks in current literature.
What we showed further is that, using c-differentials with \(c \ne 1\), a block cipher cannot be distinguished from a random permutation at all (because the advantage would be zero since \(T_\beta \circ m_c - I\) has full rank).
To summarize, under the (standard) assumption of independent round keys, a commutative cryptanalysis attack more general than a differential attack only makes sense when considering the fixed-key or weak-key model.
4 Relations between \(\Gamma _S(A,B)\) and \(\Delta _S\)
As outlined in [4], for the case of \(G = \mathbb {F}_2^n\) and \(A,B \in \textrm{AGL}(n,\mathbb {F}_2)\), there exist examples of commutative attacks over SPNs in the weak-key model, i.e., if the round keys of the cipher fulfill certain properties. Our goal now is to study more generally what a high value of \(\Gamma _S(A,B)\), where A, B allow many weak keys, means for the differential uniformity of S.
4.1 On the number of weak keys
We first analyze the commutative property over a key addition, as already studied for the case of \(G = \mathbb {F}_2^n\) in [4, Sect. 4.1]. Here, we put a slightly different focus and consider the more general case of \(G = \mathbb {F}_p^n\) for a prime p.
Let \(A,B \in \textrm{AGL}(n,\mathbb {F}_p)\). For cryptanalytic attacks, we would like that \(\Gamma _{T_k}(A,B)\) is large for as many keys (or constants) k as possible, so that we can build an iterative commutative trail for many keys. Let us denote \(A = L_A + c_A\) and \(B = L_B + c_B\), where \(L_A\) and \(L_B\) are linear maps and \(c_A,c_B\) constants. Note that we have
independently of the key k. Hence, for the choice of \(c_A = c_B\), the transition over the key addition holds with probability 1 for all keys k. This is the best situation from an attacker’s point of view.
In the case where \(L_A = I\) and \(L_B\) corresponds to multiplication with an element \(c \in \mathbb {F}_{p^n} \setminus \{0,1\}\), i.e., c-differentials, this corresponds to \((1-c) \cdot x = (c-1) \cdot k + c_B - c_A\), i.e., \(x = \frac{c-1}{1-c} \cdot k + \frac{c_B-c_A}{1-c}\). Hence, we have \(\Gamma _{T_k}(A,B) = 1\) for each key k, so c-differentials are on the opposite side of the spectrum and cannot be used to construct exploitable iterative trails over the key addition.
Intuitively, what we require in order to build a potential attack is that Eq. (1) has a high number of solutions \((x,k) \in (\mathbb {F}_{p}^n)^2\), i.e., the matrix
is of low rank. Indeed, if \(L_A-L_B\) is of low rank, we obtain that \(\Gamma _{T_k}(A,B)\) is large for some suitable k (and appropriate \(c_A,c_B\)). If \(L_B-I\) is of low rank, then we can control \(\Gamma _{T_k}(A,B)\) for many keys k.
The only case in which \(M_{A,B}\) is of rank 0 is if \(L_A = L_B = I\), i.e., the case of differential attacks. In case of c-differentials, we have \(\textrm{rank}(M_{A,B}) = n\), which is maximally unfortunate from the attacker’s point of view.
Now, we restrict to the case where \(\Gamma _{T_k}(A,B) = p^n\), i.e., if k is a weak key, we want that the commutative property holds over the key addition with probability one. From Eq. (1), we obtain that there exists k such that \(\Gamma _{T_k}(A,B) = p^n\) if and only if \(L_A = L_B\). In that case, k is a weak key if and only if \((L_B-I)(k) = c_A -c_B\), which implies that the number of weak keys equals \(p^{n-d_B}\), where \(d_B {:}{=} \textrm{rank}(L_B-I)\). Hence, to maximize the number of weak keys, we want \(d_B\) to be low. This observation is precisely what was already shown in [4, Corollary 1] for the case of \(p=2\).
4.2 Bounds on \(\Gamma _S(A,B)\) with respect to \(\Delta _S\)
Suppose we are given a function \(S :G \rightarrow G\) (e.g., an S-box, a cryptographic permutation, or a fixed-key instance of a block cipher) and mappings \(A,B :G \rightarrow G\), one can deduce an upper bound on the quantity \(\Gamma _S(A,B)\) based on the differential uniformity of S.
Proposition 2
Let \((G,+)\) be a finite Abelian group. Let \(S,A,B :G \rightarrow G\). Then,
Let \((G,+)\) be a finite Abelian group. Let us denote by \(A'\) the mapping \(A - \textrm{id}_G\) and by \(B'\) the mapping \(B - \textrm{id}_G\). Further, for \(a,b \in G\), we define the sets \(\mu _a {:}{=} \{x \in G \mid A'(x) = a\}\) and \(\nu _b {:}{=} \{x \in G \mid B'(S(x))=b\}\). We then have
In case that \(0 \notin \textrm{Im}(A')\), i.e., \(\textrm{Fix}(A) = \emptyset \), we immediately get \(\Gamma _S(A,B) \le |\textrm{Im}(A') |\cdot |\textrm{Im}(B')|\cdot \Delta _S\). Otherwise, we get
and the result follows since \(|\mu _0 \cap \nu _0 |\le |\textrm{Fix}(A)|\). \(\square \)
For the case of G being a finite vector space and A, B affine mappings, we get the following corollary by applying the rank-nullity theorem.
Corollary 3
Let p be a prime and let \(S :\mathbb {F}_p^n \rightarrow \mathbb {F}_p^n\) and \(A,B \in \textrm{AGL}(n,\mathbb {F}_p)\), where \(A = L_A + c_A, B = L_B + c_B\) with \(L_A,L_B\) linear. Let \(d_A\) and \(d_B\) denote the rank of \(L_A-I\) and \(L_B-I\), respectively. We then have
Suppose \(S :\mathbb {F}_p^n \rightarrow \mathbb {F}_p^n\) has a non-trivial affine self-equivalence \(S \circ A = B \circ S\), plugging \(\Gamma _S(A,B) = p^n\) into Eq. (2) yields \(p^{n-(d_A+d_B)} \le \Delta _S\) in both cases. If we want to allow many weak keys, \(d_A\) and \(d_B\) should be rather small, as discussed in Sect. 4.1. Hence, the differential uniformity of such S would be relatively high (unless n is very small).
Remark 1
Suppose \(S :\mathbb {F}_p^n \rightarrow \mathbb {F}_p^n\) has a non-trivial affine self-equivalence \(S \circ A = B \circ S\). For \(\Delta _S \le p\) we obtain \(d_A + d_B \ge n-1\). In [5], it was shown that if \(S :\mathbb {F}_2^8 \rightarrow \mathbb {F}_2^8\) is an APN permutation with a non-trivial linear self equivalence \(S \circ L_A = L_B \circ S\), then there are essentially only two possible classes of \((L_A,L_B)\) to consider [5, Theorem 4]. With our argument, we can exclude the second class from consideration, as \(d_A = d_B = 3\), which is a contradiction to \(d_A + d_B \ge n-1 = 7\).
Example 1
If we identify \(\mathbb {F}_{p}^n\) by the finite field \(\mathbb {F}_{p^n}\) and take L as the mapping \(x \mapsto x^{p^i}\), where i divides n, we get \(\ker (L-I) = \mathbb {F}_{p^i}\), hence \(\textrm{rank}(L-I) = n-i\). If \(S :\mathbb {F}_{p^n} \rightarrow \mathbb {F}_{p^n}\) is such that its interpolating polynomial in \(\mathbb {F}_{p^n}[X]\) only has coefficients in the subfield \(\mathbb {F}_{p^i}\), we have \(\Gamma _S(L,L) = p^n\). There are examples of such S with \(\Delta _S \le p\) (e.g., \(x \mapsto x^2\) fulfills \(\Delta _S = 1\) for p odd, for \(p=2\), the mapping \(x \mapsto x^3\) fulfills \(\Delta _S = 2\)). If n is even, we can take \(i = n/2\), in which case \(\textrm{rank}(L-I) + \textrm{rank}(L-I) = n > n-1\).
4.2.1 The differential-affine case
The case where only one of A or B is a translation and the other an arbitrary affine bijection was discussed in [7, Example 1]. We now want to study this special case in more detail.
Let \(A = T_\alpha \) for \(\alpha \ne 0\) and \(B = L_B + c_B \in \textrm{AGL}(n,\mathbb {F}_p)\) with \(L_B\) linear and \(d_B = \textrm{rank}(L_B-I)\). For \(S :\mathbb {F}_p^n \rightarrow \mathbb {F}_p^n\), Eq. (2) yields that \(\Gamma _S(A,B) \le p^{d_B} \cdot \Delta _S\). In the case that (A, B) defines a self-equivalence of S, i.e., \(\Gamma _S(A,B) = p^n\), we obtain \(\Delta _S \ge p^{n-d_B}\). In case S is a permutation, this lower bound on the differential uniformity of S can be improved, as we show in the following.
First, we observe the following properties of the order of the linear parts of affine bijections.
Lemma 2
Let \(A \in \textrm{AGL}(n,\mathbb {F}_p)\), let \(L_A\) be the linear part of A, as well as \(c_A = A(0)\). Then \(A^{\textrm{ord}(L_A)} = T_c\) for \(c {:}{=} \sum _{i=0}^{{\textrm{ord}(L_A)}-1} L_A^i(c_A)\) and
for all \(x \in \mathbb {F}_p^n\) and that the order of \(T_c\) is either 1 (if \(c=0\)) or p (if \(c \ne 0\)). \(\square \)
This directly implies that if \(\textrm{ord}(A) \ne \textrm{ord}(L_A)\) we can consider \(S \circ T_c = S \circ A^{\textrm{ord}(L_A)} = B^{\textrm{ord}(L_A)} \circ S\), instead of \(S \circ A = B \circ S\), and arrive in the differential-affine case.
Focusing on the case in which A is a translation, again, this implies that the order of the linear part \(L_B\) of B needs to divide p.
Lemma 3
Let \(S :\mathbb {F}_p^n \rightarrow \mathbb {F}_p^n\) be bijective. Let \(A,B \in \textrm{AGL}(n,\mathbb {F}_p)\) such that \(S \circ A = B \circ S\). Then, \(\textrm{ord}(A) = \textrm{ord}(B)\). Especially, if \(A = T_{\alpha }\) for \(\alpha \in \mathbb {F}_p^n {\setminus } \{0\}\), and denoting by \(L_B\) the linear map \(B - B(0)\), then \(L_B^{p} = I\).
Proof
From \(S \circ T_\alpha = B \circ S\) it follows that \(S \circ A \circ S^{-1} = B\) holds for all \(x \in \mathbb {F}_p^n\). We then have \(S \circ A^r \circ S^{-1} = B^r\), which implies \(\textrm{ord}(A) = \textrm{ord}(B)\). If \(A = T_{\alpha }\) then Lemma 2 implies that \(\textrm{ord}(L_B)\) is either \(p = \textrm{ord}(T_{\alpha })\) or 1. In both cases, we get that \(L_B^{p} = I\). \(\square \)
We then obtain an upper bound on \(d_B\).
Lemma 4
Let \(S :\mathbb {F}_p^n \rightarrow \mathbb {F}_p^n\) be bijective. Let \(\alpha \in \mathbb {F}_p^n {\setminus } \{0\}\) and \(B \in \textrm{AGL}(n,\mathbb {F}_p)\) with \(B = L_B + c_B\) for a linear mapping \(L_B\) and \(c_B \in \mathbb {F}_p^n\), such that \(S \circ T_\alpha = B \circ S\). Then, \(d_B = \textrm{rank}(L_B - I) \le \left\lfloor \frac{n(p-1)}{p} \right\rfloor \).
Proof
By Lemma 3, we obtain \((L_B-I)^p = L_B^p - I = 0\), hence \(\textrm{rank}((L_B-I)^p) = 0\). By Sylvester’s rank inequality, this yields
The result follows by rearranging terms and the fact that \(\textrm{rank}(L_B-I)\) is an integer value. \(\square \)
Plugging this upper bound on \(d_B\) into \(\Delta _S \ge p^{n-d_B}\) yields \(\Delta _S \ge p^{n-\lfloor \frac{np-n}{p}\rfloor } = p^{\lceil n - \frac{np-n}{p}\rceil } = p^{\lceil \frac{n}{p}\rceil }\). In summary, we obtain the following corollary which can be seen as a generalization of [7, Item 1 of Lemma 10].2
Corollary 4
Let \(S :\mathbb {F}_p^n \rightarrow \mathbb {F}_p^n\). Let \(A,B \in \textrm{AGL}(n, \mathbb {F}_p^n)\), where \(A = L_A + c_A\) and \(B = L_B + c_B\) for linear mappings \(L_A\), \(L_B\) and \(c_A, c_B \in \mathbb {F}_p^n\), respectively, such that \(\textrm{ord}(A) \ne \textrm{ord}(L_A)\) and \(S \circ A = B \circ S\). Then, \(\Delta _S \ge p^{n-\textrm{rank}\left( L_B^{\textrm{ord}(L_A)}-I\right) }\). If S is bijective, then \(\Delta _S \ge \max \left\{ p^{\lceil \frac{n}{p} \rceil },p^{n-\textrm{rank}\left( L_B^{\textrm{ord}(L_A)}-I\right) }\right\} \).
Example 2
The (bijective) 5-bit S-box \(S :\mathbb {F}_2^5 \rightarrow \mathbb {F}_2^5\) given in [7, Example 1] is an example of an S-box for which exists \(\alpha \ne 0\) and \(B \in \textrm{AGL}(n,\mathbb {F}_p)\) with \(d_B = 1\) such that \(\Gamma _S(T_\alpha ,B) = 2^5\), but differential uniformity strictly lower than \(2^5\) and having no affine component.
4.2.2 Tightness and application
Let m be a positive integer and \(f_1, f_2 :\mathbb {F}_p^m \rightarrow \mathbb {F}_p^m\). Let \(n {:}{=} 2\,m\). We study the permutation on \(\mathbb {F}_p^{n}\) defined as \(S :\mathbb {F}_p^{n} \rightarrow \mathbb {F}_p^{n}, (l,r) \mapsto (l',r')\) with \(l' = \ell + f_1(r)\), \(r' = r + f_2(l')\). Such a form of S is known as the 2-round Feistel construction, see Fig. 2. As we explain now, by suitable choices for the functions \(f_1\) and \(f_2\), we can guarantee the existence of \(A,B \in \textrm{AGL}(n,\mathbb {F}_p)\) with A being a translation such that \(\Gamma _S(A,B)\) takes the maximal value \(p^n\) on the one hand, but fulfilling \(\Delta _S < p^n\) on the other hand.
Proposition 3
Let \(f_1,f_2 :\mathbb {F}_p^m \rightarrow \mathbb {F}_p^m\) and \(S :\mathbb {F}_p^n \rightarrow \mathbb {F}_p^n\) be the 2-round Feistel construction defined by \(f_1\) and \(f_2\) (with \(n = 2m\)). Let \(\alpha \in \mathbb {F}_p^m\). If \(f_2\) has algebraic degree 2, then the mapping \(B_\alpha :\mathbb {F}_p^n \rightarrow \mathbb {F}_p^n, (x,y) \mapsto (x+\alpha ,y+f_2(x+\alpha ) -f_2(x))\) is in \(\textrm{AGL}(n,\mathbb {F}_p)\) and we have
The fact that \(B_\alpha \) is affine follows because \(x \mapsto f_2(x+\alpha ) - f_2(x)\) is affine if \(f_2\) is of algebraic degree 2. Because \(B_\alpha \) is a permutation, we have \(B_\alpha \in \textrm{AGL}(n,\mathbb {F}_p)\). Statement 1 then follows from a simple computation (see also Fig. 2 for the propagation of the difference \((\alpha ,0)\) through the Feistel construction). Statement 2 follows since the two-round Feistel construction defined by \(f_1\) and \(f_2\) is CCZ-equivalent to a parallel application of \(f_1\) and \(f_2\). We recall that \(S :\mathbb {F}_p^n \rightarrow \mathbb {F}_p^n\) and \(T :\mathbb {F}_p^n \rightarrow \mathbb {F}_p^n\) are called CCZ-equivalent [14] if there exists \(A \in \textrm{AGL}(2n,\mathbb {F}_p)\) such that \(\{(x,T(x)) \mid x \in \mathbb {F}_p^n\} = A(\{(x,S(x)) \mid x \in \mathbb {F}_p^n\})\) and that CCZ-equivalence preserves the differential uniformity. \(\square \)
Example 3
Let \(p = 2\) and identify \(\mathbb {F}_2^m\) by \(\mathbb {F}_{2^m}\). For \(f_1\) and \(f_2\) take the APN function \(x \mapsto x^3\) over \(\mathbb {F}_{2^m}\). Then, \(\textrm{rank}(L_{B_\alpha }- I) = \textrm{rank}(x \mapsto \alpha x^2 + \alpha ^2 x) = m-1\) and \(\Delta _S = 2^{m+1} = 2^{n - \textrm{rank}(L_{B_\alpha }- I)}\).
Example 4
Let p be odd and identify \(\mathbb {F}_p^m\) by \(\mathbb {F}_{p^m}\). For \(f_1\) and \(f_2\) take the planar function \(x \mapsto x^2\) over \(\mathbb {F}_{p^m}\) (from the planarity property, we have \(\Delta _{f_1} = \Delta _{f_2} = 1\)). Then, \(\textrm{rank}(L_{B_\alpha }- I) = \textrm{rank}(x \mapsto 2\alpha x) = m\) and \(\Delta _S = p^{m} = p^{n - \textrm{rank}(L_{B_\alpha }- I)}\).
These examples show the tightness of the bound given in Corollary 4. Instead of using APN, resp., planar functions for \(f_1\) and \(f_2\), one can construct S with various tradeoffs between low differential uniformity and low rank of \(L_{B_\alpha }-I\).
If we allow having an arbitrary mapping \(A \in \textrm{AGL}(n,\mathbb {F}_p)\) in the input instead of a translation, we could extend the 2-round Feistel by one more round in the input, to get a 3-round Feistel construction. This way, it is possible to obtain a permutation S with \(\Gamma _S(A,B) = p^n\) for some \(A,B \in \textrm{AGL}(n,\mathbb {F}_p)\), but differential uniformity lower than \(2^{m+1}\), resp, \(p^m\), as is the limit for the 2-round Feistel construction.
Several ciphers from the literature use S-boxes based on 3-round Feistel networks, and those indeed have non-trivial commutants. It is the case of the S-box of iScream [25], as pointed out in [4], as well as the ZUC stream cipher (that is part of the 3GPP standard) [22].
Fig. 2
A 2-round Feistel construction
5 Classification of linear and affine permutations sharing the same cycle type
Computing a bijective S-Box S with \(\Gamma _S(A,B)=p^n\) and A, B affine permutations can be done as follows. Choose two affine permutations A, B which share the same cycle type. Then determine the cycle structure and compute the corresponding S-boxes via Algorithm 1.
Algorithm 1
S-box Generation
One question arising in this context is how to construct all affine bijective mappings which share the same cycle type. Once this question is settled, all S-Boxes with the desired property can in principle be computed. Indeed those kind of affine mappings exist and its classification has been studied since the late 50’s / early 60’s at least. For instance Elspas [21] and Crowell [16] studied the linear case, while Wang [38] and Fripertinger [23] focused on the affine one. Proposition 9 and 10, and their proofs appear in [9, Prop. 2.1]. We give a survey about the whole theory, which has not been done before, to our best knowledge. Here, we put a focus on concrete constructions. To do so we rewrote the above two propositions and add some details to the proofs. Moreover, we apply these results to generate A, B with the desired property. We first recall some definitions and results on matrices and polynomials.
[Style2 Style1 Style3 Style3]Definition 6
Let \(P(X)\in \mathbb {F}_p[X]\) be a nonzero polynomial. If \(P(0)\not =0\), then the least positive integer e for which P(X) divides \(X^e-1\) is called the order of P(X) and denoted by \(\textrm{ord}(P(X))\). If \(P(0)=0\) then \(P(X)=X^hG(X), G(0)\not =0\), where \(h\in \mathbb {N}\) and G(X) are uniquely determined; \(\textrm{ord}(P(X))\) is then defined to be \(\textrm{ord}(G(X))\).
Remark 2
If P(X) is an irreducible polynomial of order e then \(P(X)^d\) has order \(p^te\), where t is smallest integer s.t. \(p^t\ge d\) (see e.g. [30], Theorem 3.8, p. 86). Hence if two irreducible polynomials have the same order then also any power of them. In the sequel we will denote with e instead of \(\textrm{ord}(P(X))\) if P(X) is clear from the context for ease of notation.
[Style2 Style1 Style3 Style3]Definition 7
Given \(A\in GL(n,\mathbb {F}_p).\) The characteristic polynomial\(\chi _A(X)\) is defined as \(\det (XI-A).\) The minimal polynomial \(m_A(X)=X^d+m_{d-1}X^{d-1}+\dots +m_0\) is the polynomial of lowest positive degree with the property that \(m_A(A)=0\).
is called the companion matrix of the polynomial \(P(X)=X^n+\sum _{i=0}^{n-1}a_iX^i.\)
Proofs for the following theorem and proposition can be found in e.g. [24, pp. 190–192].
Theorem 1
Given \(A\in GL(n,\mathbb {F}_p)\) with characteristic polynomial \(\chi _A(X).\) If \(\chi _A(X)\) decomposes into the product \(\prod _{i=1}^{r'}P_i(X)^{e_i}\) of prime factors \(P_i(X)\) then A is similar to
Thereby \(A_{j}\) is the companion matrix of a \(P_i^{t_j}(X), t_j\le e_i.\) Moreover for each \(P_i(X)\) the powers \(t_j\) sum up to \(e_i\) for the corresponding companion matrices \(A_j\) of \(P_i(X)^{t_j}\). This matrix is unique for A apart from the order of the blocks and called Weierstraß normal form.
Proposition 4
Given \(A\in GL(n,\mathbb {F}_p)\) where \(\chi _A(X)\) is equal to the minimal polynomial \(m_A(X)\). Then there exists a vector v s.t. \(A^{0}v,\dots , A^{n-1}v\) forms a basis of \(\mathbb {F}_p^n\). Such a vector is called cyclic. If A is a companion matrix of P(X) with \(P(0)\not =0\) then \(e_1\) is cyclic.
A direct consequence of Theorem 1 is the following.
Corollary 5
Given \(A\in GL(n,\mathbb {F}_p)\) where \(\chi _A(X)=\prod _{i=1}^{r}P_i(X)^{e_i}=m_A(X)\). Then we have the following isomorphisms of algebras:
and the latter is maximal. Hence the invertible elements \(\mathbb {F}_p[X]/(P(X)^{e})^{*}\) are exactly those not lying in (P(X)) and any element \(U(X)\in \mathbb {F}_p[X]/(P(X)^{e})\) has a representation of the form \(E(X)P(X)^t,1\le t\le e\) with \(E(X)\in \mathbb {F}_p[X]/(P(X)^{e})^{*}.\)
Proposition 5
Given \(A\in \textrm{GL}(n,\mathbb {F}_p)\) with \(\chi _A(X)=m_A(X).\) The linear map \(\psi _{A,v}: \mathbb {F}_p[X]/(\chi _A(X)) \rightarrow \mathbb {F}_p^n, P(X) \mapsto P(A)v\) for a cyclic vector v is a bijection.
Proof
By Proposition 4 and Corollary 5 the mapping \(\varphi _{A,v}:\mathbb {F}_p[A] \rightarrow \mathbb {F}_p^n,\quad P(A)\mapsto P(A)v\) is a bijection and \(\mathbb {F}_p[A]\) isomorphic to \(\mathbb {F}_p[X]/(\chi _A(X))\). \(\square \)
[Style2 Style1 Style3 Style3]Definition 9
Given an affine mapping \(A=T_a\circ L_{A}\in \textrm{AGL}(n,\mathbb {F}_p)\) with \(L_A\) linear.
1.
For polynomials \(P(X),U(X)\in \mathbb {F}_p[X]\) we define the mappings \(\varphi _{P(X)}: \mathbb {F}_p[X]/(P(X))\rightarrow \mathbb {F}_p[X]/(P(X))\), \(Q(X)\mapsto XQ(X)\) and \(\varphi _{P(X),U(X)}: \mathbb {F}_p[X]/(P(X))\rightarrow \mathbb {F}_p[X]/(P(X)), Q(X)\mapsto XQ(X)+U(X).\)
2.
We also set \(\varphi _{A}:\mathbb {F}_p^n\rightarrow \mathbb {F}_p^n, v\mapsto Av = L_Av + a\).
3.
If additionally \(\chi _{L_A}(X)=m_{L_A}(X)\) then for \(u\in \mathbb {F}_p^n\) and a cyclic vector v of \(L_A\), we have \(u = \left( \sum _{i=0}^{n-1}u_i L_A^i\right) v\) for uniquely determined \(u_0,\dots ,u_{n-1} \in \mathbb {F}_p\). We denote with \(U_{L_A}(X)\) the polynomial \(\sum _{i=0}^{n-1}u_iX^i.\) Vice Versa given \(U(X)=\sum _{i=0}^{n-1}u_iX^i\in \mathbb {F}_p[X]\) we denote with \(u_{L_A,v}=\left( \sum _{i=0}^{n-1}u_iL_A^i\right) v\). If \(L_A\) and v is clear from the context we just write U(X) or u respectively.
Item 2 is introduced to ease notation in the sequel.
Corollary 6
Given \(A\in \textrm{GL}(n,\mathbb {F}_p)\) with \(\chi _A(X)=m_A(X)\). Then \(\varphi _{\chi _A}(U(X))=\psi _{A,e_1}^{-1}\circ \varphi _{A}\circ \psi _{A,e_1}(U(X))\).
[Style2 Style1 Style3 Style3]Definition 10
Let \(A\in GL(n,\mathbb {F}_p)\) as in Theorem 1 with \(\chi _{A}(X) = \prod _{i=1}^{r'}P_i(X)^{e_i}\). Let \(\mathbb {F}_p^n\) be decomposed as \(\mathbb {F}_p^n = \bigoplus _{i=1}^r \mathbb {X}_i\) so that each block \(A_i\) has \(\mathbb {X}_i\) as domain and codomain. Let \(j \in \{1, \cdots , r\}\). We define the \(P_j(X)\)-primary component\(\mathbb {Y}_j\) as the direct sum \(\bigoplus _{i\in J_j} \mathbb {X}_i \) where \(J_j = \{i \mid \chi _{A_i}(X)=P_j^{t_j}(X) \text {for some } t_j\}\). Let \(x \in \mathbb {F}_2^n\) be decomposed as \(x = (x_1, \dots , x_r)\) with \(x_i \in \mathbb {X}_i\). We similarly say that x belongs to \(\mathbb {Y}_j\) if:
It is well known that \(\mathbb {F}_p^n=\bigoplus _{i=1}^m \mathbb {X}_i\).
5.1 The linear case
Proposition 6
Given \(A,B \in \textrm{GL}(n,\mathbb {F}_p)\) where the characteristic polynomials of A and B have the prime factor decomposition \(\chi _A(X)=\prod _{i=1}^{r}P_i(X)^{e_i}\) and \(\chi _{B}(X)=\prod _{i=1}^{l}Q_i(X)^{h_i}\) respectively. A and B share the same cycle type if and only if \(r = l\) and there is a 1-to-1 correspondence between \(P_i(X)\) and \(Q_j(X)\) with \(e_i=h_j\) and \(\textrm{ord}(P_i(X))=\textrm{ord}(Q_j(X))\).
Proof
Let us first consider the case that \(\chi _A(X)=P(X)^{e}\) with P(X) irreducible, \(\deg (P(X))=d\) and \(\chi _A(X)\) is equal to the minimal polynomial of A. By assumption the matrix A is similar to the companion matrix of \(P(X)^e\). Thus, without loss of generality, we can assume that A is already the companion matrix as the similarity relation preserves the cycle structure. From Proposition 4 we have that \(A^{0}e_1,\dots , A^{n-1}e_1\) forms a basis of \(\mathbb {F}_p^n\), where \(n:=de\). Given \(u\in \mathbb {F}_p^n\), then \(u=\sum _{i=0}^{n-1}u_iA^ie_1 =\left( \sum _{i=0}^{n-1}u_iA^i\right) e_1\) for uniquely determined \(u_0,\dots ,u_{n-1} \in \mathbb {F}_p\). Computing the cycle of u, i.e. computing \(A^0u,\dots ,A^du\) until \(A^iu=u\) is equivalent to compute
Note, that since A is bijective we do not have to deal with preperiods. Computing the cycle of u is equivalent to compute the cycle of U(X) among the mapping \(\varphi _{P^e(X)}\) due to Proposition 5 and Corollary 6. This boils down to considering when \(X^i\left( U(X)\right) =U(X).\) If \(U(X)\in \mathbb {F}[X]/(P(X)^{e})^{*}\) then the length of its cycle is the order X which is the order of \(P(X)^{e}.\) If U(X) is not invertible, then \(U(X)=E(X)(P(X))^t, 1\le t\le e\) with \(E(X)\in \mathbb {F}[X]/(P(X)^{e})^{*}\) by Remark 3. Thus the cycle length of U(X) is equal to the order of X in \(\mathbb {F}[X]/(P(X)^{e-t})\), which is the order of \(P(X)^{t-e}.\) Indeed since \(E(X)\in \mathbb {F}_p[X]/(P(X)^e)^{*}\), it holds that \(X^i\left( U(X)\right) =U(X) \) if and only if \((X^i-1)P(X)^t=0\) in \(\mathbb {F}_p[X]/(P(X)^{e-t}),\) i.e. \(P(X)^{e-t}\) divides \((X^i-1)\). Hence if P(X) and Q(X) have the same order then any matrix B similar to the companion matrix of \(Q(X)^e\) will share the same cycle type with A by Remark 2.
Now consider the general case, i.e. matrices with Weierstraß normal form
where \( \chi _A(X)=\prod _{i=1}^{r} P_i(X)^{e_i}\). Any \(u\in \mathbb {F}_p^n\) can uniquely be written as \(u=\sum _{i=1}^{r} u_i\), where \(u_i \in \mathbb {X}_i\) according to Definition 10. Hence the length of the cycle of u is equal to \(\textrm{lcm}(l_1,\dots ,l_{r})\), where \(l_i\) is the length of the cycle of \(u_i\) with respect to \(A_i\). Thus this case boils down to Case 1 as each \(A_i\) can be treated independently. This proves the statement for Case 2 and finally the proposition. \(\square \)
In order to construct two \(A, B\in \textrm{GL}(n,\mathbb {F}_p)\) with the same cycle type, but not similar, one can start with a matrix A in Weierstraß normal form, where \(m_A(X)=\chi _A(X)\). Then some or all irreducible polynomials \(P_i(X)\) of \(\chi _A(X)\) are exchanged by some polynomials \(Q_i(X)\) with \(Q_i(X)\not =P_i(X)\) and \(\textrm{ord}(P_i(X))= \textrm{ord}(Q_i(X))\). The corresponding Weierstraß normal form B is computed based on A by modifying some of the blocks \(A_j\) according to the change of the irreducible factors. Then, any pair \((A',B') = (SAS^{-1},TBT^{-1}),S, T\in \textrm{GL}(n, \mathbb {F}_p)\) is a solution.
5.2 The affine case
Proposition 7
[26] Given an affine mapping \(A=T_a\circ L_{A}\in \textrm{AGL}(n,\mathbb {F}_p)\) with \(L_A\) linear. Let \(L_A\) be similar to
where w.l.o.g. the \((X-1)\)-primary component, if it exists, corresponds to the last blocks. Then there exists a \(w \in \mathbb {F}_p^n\) s.t. \(T_{-w}\circ A\circ T_{w}=T_u\circ L_A,\) where u belongs to the \((X-1)-\)primary component.
Proof
According to Remark 4, we decompose \(\mathbb {F}_p^n\) as \(\mathbb {F}_p^n=V\oplus U,\) where U is the \((X-1)-\)primary component or \(U=\{0\}\). Thus \(a=v+u, v\in V, u\in U.\) It is \(\chi (L_A)(X)=\prod _{i=1}^{r} P_i(X)^{e_i}(X-1)^e\) and \(\chi (L_A\vert _V)(X)=\prod _{i=1}^{r} P_i(X)^{e_i}.\) Therefore \(L_A-I\) is invertible over V and there exists an element \(w\in V\) with \((L_A-I)(w)=-v.\) It follows that \(T_{-w}\circ A\circ T_{w}(X)=L_A(X)+L_A(w)-w+u+v=T_{u}\circ L_A(X)\) as requested. \(\square \)
Corollary 7
[38] Given \(A\in \textrm{AGL}(n,\mathbb {F}_p)\), where \((X-1)\not \mid \chi (L_A)\). Then the cycle structure of A equals the one of \(L_A\).
Proof
In this case \(U=\{0\}\) and thus \(u=0.\)\(\square \)
Hence, to generalize Proposition 6 to the affine case it is sufficient to consider affine mappings of the form \(T_u\circ L_A,\) where u is an element of the \((X-1)-\) primary component or 0. The parts not affected by the \((X-1)\)-primary component are covered by Proposition 6. Therefore we can restrict to consider the subcase \(A=T_u\circ L_A\) where \(L_A\) is a companion matrix with minimal polynomial \((X-1)^e.\) Let \(A\in \textrm{GL}(n,\mathbb {F}_p)\) a matrix with cyclic vector \(e_1 \in \mathbb {F}_p^n\). To prove the linear case we used that \(\varphi _{\chi _A(X)}\) and \(\varphi _{A}\) share the same cycle structure. We will generalize this fact to the affine case.
Proposition 8
Let P(X) be a polynomial of degree n, \(a \in \mathbb {F}_p^n\) and \(A = T_u \circ L_A\), where \(L_A\) is the companion matrix of P(X). Then \(\varphi _{P(X),U(X)}\) and \(\varphi _A\) share the same cycle type.
Proof
By Proposition 5, \(\psi _{A,e_1}\) is bijective and thus \(\psi _{A,e_1}^{-1}\) exists. It is
and therefore \(\psi ^{-1}_{L_A,e_1}\circ \varphi _A\circ \psi _{L_A,e_1}(Q(X))=XQ(X)+U(X).\) It follows that \(\psi ^{-1}_{A,e_1}\circ \varphi _A\circ \psi _{A,e_1}=\varphi _{P(X),U(X)}\) and eventually that \(\varphi _A\) and \(\varphi _{P(X), U(X)}\) share the same cycle structure. \(\square \)
We will now show that \(L_A+u\) and \(B=L_B+u'\in \textrm{AGL}(n,\mathbb {F}_p)\) share the same cycle structure only if \(m_{L_B}(X)\) is also equal to \((X-1)^e\) and \(u'\) fulfills certain conditions depending on u.
Corollary 8
Let \(u \in \mathbb {F}_p^n\). Then u belongs to a cycle of length \(\ell \) of A if and only if U(X) belongs to a cycle of length \(\ell \) of \(\varphi _{A,e_1}\).
Proposition 9
[9, 21] Let \(q>1\) be a power of prime p. Let \(e \ge 1\) and s be its size (in base p) \(s := \lceil \log _p(e)\rceil \). Let \(G(X) = P(X)^e\) be a power of an irreducible polynomial \(P(X)\ne X-1\) of degree d. Then the permutation \(\varphi _{G(X)}\) has the following cycle count:
Cycle length
1
\(\textrm{ord}(P(X))\)
\(\textrm{ord}(P(X))p^i, \ i \in \llbracket 1, s -1 \rrbracket \)
so the least i verifying this equation is precisely \(\textrm{ord}(P(X)^{e-j})\). With \(e-j = 1\), we conclude that the elements lying on cycles of length \(\textrm{ord}(P(X))\) are the ones belonging to \(\left( P(X)^{e-1}\right) \setminus \{0\}\); there are \(q^d-1\) of them. Otherwise, \(e-j > 1 \) and \(\textrm{ord}(P(X)^{e-j}) = p^{\lceil \log _p(e-j)\rceil }\textrm{ord}(P(X))\). In that case, the elements on cycles of length \(p^{k}\textrm{ord}(P(X))\) with \(1\le k < s\) correspond to the elements of \((P(X)^{e-p^k}) {\setminus } (P(X)^{e-p^{k-1}})\). There are \(q^{dp^k} - q^{dp^{k-1}}\) of them. Elements on cycles of length \(p^s\textrm{ord}(P(X))\) are the remaining ones, that is elements of \(\mathbb {F}_q[X]/(Q(X)) {\setminus } \left( P(X)^{e-{p^{s-1}}}\right) \); there are \(q^{de} - q^{dp^{s-1}}\) of them. \(\square \)
Proposition 10
[9, 23] Let \(1<q\) be a power of prime p. Let \(e \ge 1\) and s be its size (in base p) \(s := \lceil \log _p(e)\rceil \). Let \(G(X) = (X-1)^e\). Then the cycle structure of \(\varphi _{G(X),U(X)}\) depends on the nature of U(X) as follows:
1.
if \(X-1 \mid U\) then its cycle count is as given in the following table
Cycle length
1
\(p^i, \ i \in \llbracket 1, s -1 \rrbracket \)
\(p^s\)
Cardinality
q
\(\frac{q ^{p^{i}} -q ^{p^{i-1}}}{p^i} \)
\(\frac{q ^{e} - q^{p^{s - 1}}}{p^{s}} \)
2.
if \( X- 1 \not \mid U\) and:
(a)
e is a power of p then all cycles are of length \(p^{s + 1}\) (and there are \(q^e/p^{s+1}\) of them),
(b)
e is not a power of p then all cycles are of length \(p^{s}\) (and there are \(q^e/p^{s}\) of them).
Proof
With \(\nu (Q(X))\) we denote the \((X-1)\)-valuation of \(Q(X)\in \mathbb {F}_p[X]\), i.e. the maximal \(l\ge 0\) with \((X-1)^l\vert Q\) and \(\nu (0)=\infty \).
Let \(i \ge 0\) and consider the equation \(\varphi ^{p^i}(Q(X)) = Q(X) \) in \(\mathbb {F}[X]/(G(X))\). It follows
which has either none or all Q(X) as solutions, depending on whether \(U(X)S(X)_{p^{i}} \ne 0 \) or not, that is, whether \(\nu (U(X)S(X)_{p^{i}}) < e\) or not.
Case (1)\(X-1 \mid U\) With \(i = s\), we get \(\nu (US_{p^s}) = \nu (U) + \nu (S(X)_{p^s}) \ge 1 + (p^s - 1) \ge e \) so \(U(X)S(X)_{p^{i}} = 0\) and all Q(X) are solutions of Eq. (7). Therefore all Q(X) lies on cycles of length dividing \(p^s\).
For \(i \in \llbracket 0, s-1 \rrbracket \), by decomposing \(U(X)S(X)_{p^i} = (X-1)^{\nu (U(X)S(X)_{p^i})}Z\) with \(X-1 \not \mid Z\), Eq. (6) becomes:
where \(\mathcal {I}\) is the ideal generated by \((X-1)^{e - p^i}\). So there are exactly \(|\mathcal {I}| = q ^{p^i}\) elements located on cycles whose length divides \(p^i\). Therefore for any \(i \in \llbracket 0, s-1 \rrbracket \), there are \(q^{p^i} - q^{p^{i-1}}\) elements on cycles of length \(p^i\) and \(q^e - q^{s-1}\) elements on cycles of length \(p^s\).
Case (2b)\(X-1 \not \mid U(X)\), enot a power ofp In that case, \(\nu (U(X)S(X)_{p^s}) = \nu (U(X)) + \nu (S(X)_{p^s}) = 0 + (p^s - 1) \ge e.\) Therefore, every Q(X) is solution of Eq. (7) (with \(i = s\)) and thus every Q(X) lies on cycles of length dividing \(p^s\). However for \(i < s\), Eq. (6) becomes
but the left-hand side belongs to the ideal \(\left( (X-1)^{p^i}\right) \) while on the right-hand side we have \(S(X)_{p^i} \in \left( (X-1)^{p^i - 1}\right) {\setminus } \left( (X-1)^{p^i}\right) \) which means that no Q(X) lies on cycles of length \(p^i\) for \(i < s\).
Case (2a)\(X-1 \not \mid U\), \(e = p^s\) In that case, \(\nu (S(X)_{p^{s+1}}) = p^{s+1} - 1 \ge p^s = e\) so Eq. (7) with \(i = s+1\) admits all Q(X) as solutions. Thus, all Q(X) lie on cycles of length divisible by \(p^{s+1}\). But for \(i \le s\), Eq. (8) has no solution for the same reasons as above, so all Q(X) lie on cycles of length \(p^{s+1}\). \(\square \)
So from Propositions 9 and 10 it follows that \(L_A\) and \(L_B+u\) with \(\chi _{L_A}=(P(X))^l\) and \(\chi (L_B)=(X-1)^{l\text {deg}(P(X))}\) cannot have the same cycle structure.
Thus given an affine mapping \(A=T_u\circ L_{A}\in \textrm{AGL}(n,\mathbb {F}_p)\)
where w.l.o.g. \(A_i\) are companion matrices, the \((X-1)\)-primary component, if exists, is made of the last blocks and u belongs to the \((X-1)\)-primary component. To get another affine mapping B with the same cycle structure one just has to exchange all blocks \(A_i\) conforming to Proposition Proposition 6. The blocks belonging to the \((X-1)\)-primary component stay the same. Here u can be exchanged by \(u'\), where U(X) and \(u'(X)\) fulfill the same condition of Proposition 10. The pairs (\(A'\),\(B'\)), where \(A' = MAM^{-1}, B' = NBN^{-1},M,N\in \textrm{GL}(n,\mathbb {F})\) cover the sought for general case.
In the next section we will prove some facts about the Weierstraß normal form depending on the order of A. This has interesting implications for the self-equivalence \(S\circ A=B\circ S.\)
5.3 Affine and linear self-equivalences: orders not a power of p
We will now assume that \(S \circ A=B \circ S\) (i.e., \(\Gamma _S(A,B) = p^n\)) and take a deeper look at the implications of \(\textrm{ord}(A)\) not being a power of p. Hence, let us write \(\textrm{ord}(A) = p^m \cdot d\) with m maximal. Without loss of generality, we can assume that \(m = 0\), as we can simply consider \(A^{p^m}\) instead of A. Thus, we will assume that \(\textrm{ord}(A) = d\) is not divisible by p. Then, we note that by Lemma 2, \(\textrm{ord}(A) \in \{\textrm{ord}(L_A), p \cdot \textrm{ord}(L_A)\}\), implying that \(\textrm{ord}(A) = \textrm{ord}(L_A)\). But then \(\textrm{ord}(L_A)\) is not a multiple of p, implying that \(L_A\) is similar to a certain block-diagonal matrix. The next lemma is a well-known consequence on the theory given before. Still we give the proof to ease following the results.
Lemma 5
Let L be a linear permutation of \(\mathbb {F}_p^n\) and let \(k = \dim (\textrm{Fix}(L))\). If \(\textrm{ord}(L)\) is not a multiple of p, then L is similar to
where I is the \(k \times k\) identity matrix and \(L'\) a linear permutation on \(\mathbb {F}_p^{n - k}\) without any non-trivial fixed points.
Proof
By Remark 2 we have that \(m_L(X)\) is the product of distinct irreducible polynomials of multiplicity 1. Moreover in case of \(k\ge 1\), we have \(m_L(X)=(X-1)G(X)\) with \(G(1)\not =0\). Hence in the Weierstraß normal form the Blocks \(A_i\) belonging to the \((X-1)\)-primary component are \(1\in \textrm{GL}(1,\mathbb {F}_p)\). This ends the proof. \(\square \)
This similarity can easily be translated to affine maps.
Proposition 11
Let \(A \in \textrm{AGL}(n, \mathbb {F}_p)\) and let \(A = L_A + c_A\) with \(L_A\) linear and \(c_A \in \mathbb {F}_p^n\). If \(\textrm{ord}(A)\) is not a multiple of p, then there exist \(Q \in \textrm{AGL}(n, \mathbb {F}_p)\) such that
where I is the \(k \times k\) identity matrix (\(k = \dim (\textrm{Fix}(L_A))\)) and \(L'\) a linear permutation on \(\mathbb {F}_p^{n - k}\) without any non-trivial fixed points. Additionally, \(\textrm{Fix}(A) = \textrm{Fix}(L_A) + c_Q\) with \(c_Q = Q(0)\).
Proof
We know from Lemma 2 that \(\textrm{ord}(A) \in \{\textrm{ord}(L_A), p \cdot \textrm{ord}(L_A)\}\). Since \(\textrm{ord}(A)\) is not a multiple of p, this implies that \(\textrm{ord}(A) = \textrm{ord}(L_A)\), and \(\textrm{ord}(L_A)\) cannot be a multiple of p. Hence, we know from the previous lemma that there exists a linear permutation \(L_Q\) such that
where I is the \(k \times k\) identity matrix and \(L'\) a linear permutation on \(\mathbb {F}_p^{n - k}\) without any non-trivial fixed points. Hence, \(L_Q^{-1}AL_Q\) is the affine map defined by
$$\begin{aligned} x \mapsto \begin{pmatrix}I & 0\\ 0 & L'\end{pmatrix} \cdot x + L_Q^{-1}(c_A). \end{aligned}$$
But \(\textrm{ord}(A) = \textrm{ord}(L_A)\) also implies that
Hence, the first k coordinates of \(L_Q^{-1}(c_A)\) need to be zero. Since \(L'\) has no non-trivial fixed points, meaning that \(L' - I\) has full rank, there needs to exist a \(c_Q' \in 0^k \times \mathbb {F}_p^{n-k}\) such that
At last, we note that \(0 = Q^{-1}AQ(0)\) has to hold, which implies that \(0 = A(c_Q) - c_Q\). In other words, \(c_Q\) is a fixed point of A, and therefore \(\textrm{Fix}(A) = \textrm{Fix}(L_A) + c_Q\). \(\square \)
Since \(\textrm{ord}(A) = \textrm{ord}(B)\) has to hold if S is bijective, and the argument applies for both, A and B, we get the following corollary.
Corollary 9
Let \(S:\mathbb {F}_p^n \rightarrow \mathbb {F}_p^n\) be bijective and \(A, B \in \textrm{AGL}(n, \mathbb {F}_p)\) with \(S \circ A = B \circ S\). Let \(L_A = A - A(0)\) be the linear part of A. If \(\textrm{ord}(A) = dp^m\) for d not a multiple of of p, there exist affine maps \(Q_A, Q_B \in \textrm{AGL}(n, \mathbb {F}_p)\) such that for \(\hat{S}\) defined as \(Q_B \circ S \circ Q_A\) it holds that
where I is the \(k \times k\) identity matrix (\(k = \dim (\textrm{Fix}(L_A^{p^m}))\)) and \(L_A', L_B'\) are linear permutations on \(\mathbb {F}_p^{n - k}\) without any non-trivial fixed points.
Proof
The result follows from the previous proposition and the fact that, if \(\textrm{ord}(A) = dp^m\), then \(\textrm{ord}(A^{p^m}) = d\) and a self-equivalence \(S \circ A = B \circ S\) implies the self-equivalence \(S \circ A^{p^m} = B^{p^m} \circ S\). \(\square \)
In other words, if (A, B) is an affine self-equivalence of S with \(\textrm{ord}(A) = \textrm{ord}(B)\) not being a multiple of p then S is affine equivalent to \(S'\) with a linear self-equivalence, and the mappings belonging to the linear self-equivalences are similar to the block-diagonal matrix described above.
6 Differential attacks against conjugate ciphers
As hinted in [4, Appendix A], commutative cryptanalysis has an intricate relationship with differential cryptanalysis, but also with differential cryptanalysis of conjugate ciphers. Such a methodology consists in studying a function \(F :\mathbb {F}_{2}^{n}\rightarrow \mathbb {F}_{2}^{n}\) by considering equations of form
$$\begin{aligned} {H}\circ F \circ {H}^{-1}(x + {\Delta ^{\textrm{in}}}) = {H}\circ F \circ {H}^{-1}(x) + {\Delta ^{\textrm{out}}}; \end{aligned}$$
where \({H}:\mathbb {F}_{2}^{n}\rightarrow \mathbb {F}_{2}^{n}\) is a well-chosen bijection. This is in line with the work of Beierle et al. [6] which first investigated the relationship between non-linear invariants/approximations of F and the linear invariants/approximations of \({H}\circ F \circ {H}^{-1}\).
Standard differential cryptanalysis naturally corresponds to \({H}= I\) and such a generalization is actually interesting only if \({H}\) is non-linear as the differential properties of a function are preserved by affine equivalence.
Another line of papers [10‐12, 15] tackles a similar problem from a group-theoretic perspective. In particular, Civino et al. [15] consider equations of a vectorial Boolean function \(F :\mathbb {F}_{2}^{n}\rightarrow \mathbb {F}_{2}^{n}\) of the form
where \(\diamond :\mathbb {F}_{2}^{n}\times \mathbb {F}_{2}^{n}\rightarrow \mathbb {F}_{2}^{n}\) is an Abelian group operation for \(\mathbb {F}_{2}^{n}\). This generalizes the usual case which corresponds to the case where \(\diamond \) is the bitwise addition.
The objective of this section is to bridge the gap between these three cryptanalysis approaches. The link between commutative cryptanalysis and differential cryptanalysis of conjugates is recalled in Sect. 6.1. In Sect. 6.2, we precisely depict the group laws that are considered in [15] and which are based on elementary regular subgroups of the symmetric group. In particular, we present an important conjugation property (Proposition 16) between their groups of translations and the one of the usual bitwise modulo-2 addition. Based on this conjugation property, we present in Sect. 6.3 the relationship between differential cryptanalysis of conjugates and differential cryptanalysis with alternative group laws. Finally, we provide examples extracted from [3, 4, 10, 15] to illustrate these intricate links. In the following, for any bijection \({H}:\mathbb {F}_{2}^{n}\rightarrow \mathbb {F}_{2}^{n}\) and any function \(F :\mathbb {F}_{2}^{n}\rightarrow \mathbb {F}_{2}^{n}\), we denote by \(F^{{H}}\) the conjugate of F by \({H}\), that is, \(F^{{H}} := {H}\circ F \circ {H}^{-1}\).
6.1 Differential cryptanalysis of conjugates and commutative cryptanalysis
Let us recall the link between commutation and conjugation that is shown in [4, Appendix A]. Let \( F, {H}:\mathbb {F}_{2}^{n}\rightarrow \mathbb {F}_{2}^{n}\) with \({H}\) a bijection and \({\Delta ^{\textrm{in}}}, {\Delta ^{\textrm{out}}}\in \mathbb {F}_{2}^{n}\). A probability-1 differential corresponds to a constant derivative of \(F^{{H}}\), i.e.:
$$\begin{aligned} \forall x \in \mathbb {F}_{2}^{n}, \quad {H}\circ F \circ {H}^{-1} (x+{\Delta ^{\textrm{in}}}) - {H}\circ S \circ {H}^{-1} (x) = {\Delta ^{\textrm{out}}}. \end{aligned}$$
(9)
Equation (9) can equivalently be written as \( T_{{\Delta ^{\textrm{out}}}} \circ {H}\circ F \circ {H}^{-1} = {H}\circ F \circ {H}^{-1} \circ T_{{\Delta ^{\textrm{in}}}}\), but also as \( \quad T_{{\Delta ^{\textrm{out}}}}^{{H}^{-1}} \circ F = F \circ T_{{\Delta ^{\textrm{in}}}}^{{H}^{-1}} \), by conjugating the latter expression by \({H}^{-1}\).
This proves that the differentials with probability 1 of the conjugate function \(F^{{H}}\) correspond to commutation relations with probability 1 through the original function F. In the probabilistic case, the same reasoning proves that:
(Conjugation and commutation) Let \(F, {H}:\mathbb {F}_{2}^{n}\rightarrow \mathbb {F}_{2}^{n}\), with \({H}\) a bijection. Studying the differential properties of \(F^{{H}}\) is equivalent to studying the commutative properties of F with respect to commutants among the group \( \{T_{c}^{{H}^{-1}} \mid c \in \mathbb {F}_{2}^{n}\} = {H}^{-1}T{H}\); where the group of translations is denoted by \(T := \{T_{c} \mid c \in \mathbb {F}_{2}^{n}\}\).
Proposition 12 is the differential counterpart of the work of Beierle, Canteaut & Leander [6]. Indeed, commutative properties of a block cipher are related to differential properties of its conjugates, in the same way as non-linear approximations (and in particular invariants) are related to linear properties of the conjugates.
However, Proposition 12 also points out that the considered class of commutants is really restrictive. Indeed, \({H}^{-1}T{H}\) is a conjugate of the group T and this implies that, like T, \({H}^{-1}T{H}\) is an Abelian 2-elementary regular group.
A group G is said to be 2-elementary if each non-zero element is of order 2. A group G of permutations over a set \(\Omega \) is said to be regular if it satisfies
$$\begin{aligned} \forall (x, y) \in \Omega , \quad \exists ! \ g \in G, \ g(x) = y. \end{aligned}$$
The conjugation of T (or the regularity) in particular implies that \({H}^{-1}T{H}\setminus \{I\}\) contains only involutions without fixed points.
For these reasons, differential cryptanalysis of a conjugate cipher can only provide exact results about (either deterministic or probabilistic) commutations relations where \(A, B :\mathbb {F}_{2}^{n}\rightarrow \mathbb {F}_{2}^{n}\) are strongly constrained. For instance, it cannot exactly handle pairs (A, B) where one of the commutants is not a fixed-point-free involution (because of the 2-elementarity) or pairs for which there exists \(x \in \mathbb {F}_{2}^{n}\), such that \(A(x) = B(x)\) (because of the regularity). Nonetheless, for any of these situations, it is still possible to approximateA and B by two elements of a given \({H}^{-1}T{H}\) to obtain an approximation on the number of solutions of a given relation .
6.2 Elementary regular subgroups of the symmetric group
In the following, 0 always stands for the identity element of the group \((\mathbb {F}_{2}^{n}, +)\). In their paper [15], Civino, Blondeau & Sala present a cryptanalysis framework based on alternative group laws. laws. The group laws that are considered in their work are heavily related to the usual bitwise modulo-2 addition. Indeed, for any of the considered group laws \(\diamond \), the corresponding group of translations \(\mathcal {T}\) is not only isomorphic to the group of translations T for the usual addition, they are also conjugate (see Proposition 16). Thanks to this conjugation property, we will be able to study in Section 6.3 the relationship between differential cryptanalysis of conjugate ciphers for the usual addition and differential cryptanalysis of the original cipher for alternative laws. This section is therefore dedicated to presenting the group laws used in [15] (which are based on the study of elementary regular subgroups) and the conjugation property between groups of translations. The group laws studied by Civino, Blondeau & Sala are built by first considering a regular 2-elementary Abelian subgroup \(G \subseteq \textrm{Perm}(\mathbb {F}_{2}^{n})\) of the symmetric group. In particular, if G is regular, then \( \{g(0) \mid g \in G\}\) is the full space \( \mathbb {F}_{2}^{n}\). We can then enumerate G as \(G = \{g_{a} \mid a \in \mathbb {F}_{2}^{n}\}\) where \(g_{a}\) is the unique function \(g \in G\) that satisfies \(g(0) = a\). Such a group mimics the group of translations \(T:= \{T_{a} :x \mapsto x + a\}\) which is indeed made of fixed-point-free involutions (except \(T_{0} = I\)), which commute one with the others, and where the only one that satisfies \(T_{a}(x) = y\) is \(T_{x + y}\). For these reasons, we reserve the notation \(\mathcal {T}= \{\mathcal {T}_{a} \mid a \in \mathbb {F}_{2}^{n}\}\) to regular subgroups of \(\textrm{Perm}(\mathbb {F}_{2}^{n})\) where for any \(a \in \mathbb {F}_{2}^{n}\), we have \(\mathcal {T}_{a}(0) = a\).
Let us clarify this mimicry. First, it is possible to build a group law \(\diamond \) for which the group of translations is any regular 2-elementary (Abelian) subgroup of \(\textrm{Perm}(\mathbb {F}_{2}^{n})\). The following proposition is the keystone of [15].
Proposition 13
(Group law based on a regular subgroup) Let \(\mathcal {T}\subseteq \textrm{Perm}(\mathbb {F}_{2}^{n})\) be a regular Abelian subgroup of the symmetric group. Let us define the operator \(\diamond :\mathbb {F}_{2}^{n}\times \mathbb {F}_{2}^{n}\rightarrow \mathbb {F}_{2}^{n}\) as:
$$\begin{aligned} \forall x, y \in \mathbb {F}_{2}^{n}, \quad x \diamond y := \mathcal {T}_{x}(y). \end{aligned}$$
Then \((\mathbb {F}_{2}^{n}, \diamond )\) is an Abelian group whose identity element \(0_\diamond \) satisfies \(0_\diamond = 0\). Furthermore \(\mathcal {T}\) coincides with its group of translations.
Proof
Let us first observe that \(\diamond \) is well-defined. It is a commutative operator because for any \(x, y \in \mathbb {F}_{2}^{n}\) we have:
$$\begin{aligned} x \diamond y = \mathcal {T}_{x}(y) = \mathcal {T}_{x}(\mathcal {T}_{y}(0)) = \mathcal {T}_{y} (\mathcal {T}_{x}(0)) = \mathcal {T}_{y}(x) = y \diamond x. \end{aligned}$$
Furthermore, for any \(x \in \mathbb {F}_{2}^{n}\), we have by definition \(x \diamond 0 = \mathcal {T}_{x}(0) = x\) so 0 is the identity element. As \(\mathcal {T}_{x}^{-1} \in \mathcal {T}\), there exists y such that \(\mathcal {T}_{x}^{-1} = \mathcal {T}_{y}\). We then observe that
$$\begin{aligned} x \diamond y = \mathcal {T}_{x}(y) = \mathcal {T}_{x}(\mathcal {T}_{y}(0)) = \mathcal {T}_{x}(\mathcal {T}_{x}^{-1}(0)) = 0; \end{aligned}$$
which makes y the inverse of x. Finally for any \(x, y, z \in \mathbb {F}_{2}^{n}\), we observe that:
$$\begin{aligned} x \diamond (y \diamond z) = \mathcal {T}_{x}(\mathcal {T}_{y}(z)), \quad \text {and} \quad (x \diamond y ) \diamond z = \mathcal {T}_{x}(y) \diamond z = \mathcal {T}_{\mathcal {T}_{x}(y)}(z). \end{aligned}$$
But \(\mathcal {T}_{\mathcal {T}_{x}(y)}\) satisfies \(\mathcal {T}_{\mathcal {T}_{x}(y)}(0) = \mathcal {T}_{x}(y)\) and \(\mathcal {T}_{x} \circ \mathcal {T}_{y}\) belongs to \(\mathcal {T}\) and also satisfies \(\mathcal {T}_{x}\circ \mathcal {T}_{y} (0) = \mathcal {T}_{x}(y)\). By the regularity of \(\mathcal {T}\), we necessarily have that \(\mathcal {T}_{\mathcal {T}_{x}(y)} = \mathcal {T}_{x} \circ \mathcal {T}_{y}\) and therefore \(\diamond \) is associative. So \((\mathbb {F}_{2}^{n}, \diamond )\) is indeed an Abelian group. Furthermore, for any \(a \in \mathbb {F}_{2}^{n}\), the function \(x \mapsto x \diamond a\) coincides by construction with \(\mathcal {T}_{a}\). \(\square \)
Remark 5
The previous proposition is stated without supposing that \(\mathcal {T}\) is 2-elementary. If it is the case, then for any \(x \in \mathbb {F}_{2}^{n}\), we have \(\mathcal {T}_{x}^{-1} = \mathcal {T}_{x}\) and therefore x is its own inverse for the group law \(\diamond \). In the following, this will always be the case. Furthermore, by construction we have \(0_\diamond = 0\). Therefore, we no longer make a distinction between the two identity elements and always use the notation 0 for the identity element.
We can also go further in the parallel between such a group \(\mathcal {T}\) and the group of translations thanks to the following well-known result.
Proposition 14
Up to isomorphism, there exists a single 2-elementary group of order \(2^{n}\), which is \((\mathbb {F}_2^n,+)\).
So any 2-elementary regular subgroup \(\mathcal {T}\) of \(\textrm{Perm}(\mathbb {F}_{2}^{n})\) is isomorphic to the group of translations T. But due to a result of Dixon [19, proof of Lemma 1], we can be even more precise as two isomorphic regular subgroups of \(S_{n}\) are necessarily conjugate.
Proposition 15
(Isomorphic and conjugate regular subgroups [19]) Let \(n \ge 1\) and let \(S_{n}\) be the symmetric group of \( \llbracket 0, n-1 \rrbracket \). Let G, K be two regular subgroups of \(S_{n}\) such that there exists a group isomorphism \(\phi :G \rightarrow K\). Then there exists \(\sigma \in S_{n}\) such that \(\sigma K \sigma ^{-1} = G\).
Proof
(Adapted from [19, Proof of Lemma 1]) Let us define the bijection \(\sigma : \llbracket 0, n-1 \rrbracket \rightarrow \llbracket 0, n-1 \rrbracket \) as:
The bijection \(\sigma \) is well-defined. Indeed, G is regular so \( \{g(0) \mid g \in G\} = \llbracket 0, n-1 \rrbracket \), but we also have \( \{\phi (g)(0) \mid g \in G\} = \{k(0) \mid k \in K\} = \llbracket 0, n-1 \rrbracket \) because \(\phi \) is bijective and K is regular. By definition we also note that:
Let us enumerate K as \(K = \{k_{i} \mid i \in \llbracket 0, n-1 \rrbracket \}\) where \(k_{i} \in K\) is the unique \(k \in K\) such that \(k(0) = i\).
Let \(g \in G\) and let us consider \(\sigma \circ g \circ \sigma ^{-1}\). Let \(i \in \llbracket 0, n-1 \rrbracket \) and let us denote \(\widetilde{g} = \phi ^{-1}(k_{i})\) and observe that by construction we have:
Eq. (14) comes from Eq. (13); Eq. (15) from Eq. (12); Eq. (16) is only a different bracket grouping; Eq. (17) comes from Eq. (11); Eq. (18) is due to the morphism property of \(\phi \) and finally Eq. (19) is again due to Eq. (13).
All in all, it holds that \(\sigma g \sigma ^{-1} = \phi (g)\), and this implies that \(\sigma G \sigma ^{-1} = K\). \(\square \)
Let \(\mathcal {T}= \{\mathcal {T}_{a} \mid a \in \mathbb {F}_{2}^{n}\}\) be a 2-elementary regular subgroup of \(\textrm{Perm}(\mathbb {F}_{2}^{n})\) and \(T = \{T_{a} :x \mapsto x + a \mid a \in \mathbb {F}_{2}^{n}\}\) be the group of translations for the usual addition law.
There therefore exists \(\sigma \) such that \(\sigma \mathcal {T}\sigma ^{-1} = T\). This also implies that there exists a bijection \(\psi :\mathbb {F}_{2}^{n}\rightarrow \mathbb {F}_{2}^{n}\) which satisfies:
By evaluating the previous equations at point \(\sigma (0)\), we obtain:
$$\begin{aligned} \forall a \in \mathbb {F}_{2}^{n}, \quad \sigma \circ \mathcal {T}_{\psi (a)} (0) = \sigma (0) + a, \quad \iff \quad \sigma (\psi (a)) = \sigma (0) + a. \end{aligned}$$
In other words, for a given \(\sigma \) such that \(\sigma \mathcal {T}\sigma ^{-1} = T\), there exists a single \(\psi \) satisfying Eq. (20) and it is defined as:
Let \(c, a \in \mathbb {F}_{2}^{n}\). The group \(\mathcal {T}\) being Abelian, it holds that \(\mathcal {T}_{c} \circ \mathcal {T}_{\psi (a)} = \mathcal {T}_{\psi (a)} \circ \mathcal {T}_{c}\), i.e., \(\mathcal {T}_{c} \circ \mathcal {T}_{\psi (a)} \circ \mathcal {T}_{c}^{-1} = \mathcal {T}_{\psi (a)} \). But as \(\mathcal {T}\) is also 2-elementary, any element is its own inverse so \(\mathcal {T}_{c} \circ \mathcal {T}_{\psi (a)} \circ \mathcal {T}_{c} = \mathcal {T}_{\psi (a)} \).
This implies that for any \(\sigma , \psi \) satisfying Eq. (20), it also holds that for any \(c \in \mathbb {F}_{2}^{n}\):
In other words, \(\sigma \) can be replaced by \(\sigma \circ \mathcal {T}_{c}\) for any \(c \in \mathbb {F}_{2}^{n}\). In particular, with \(c = \sigma ^{-1}(0)\), we observe that \(\sigma \circ \mathcal {T}_{\sigma ^{-1}(0)}(0) = \sigma (\sigma ^{-1}(0)) = 0\), so without loss of generality, we can always consider \(\sigma \) such that \(\sigma (0) = 0\). In that case \(\psi = \sigma ^{-1}\) and Eq. (20) can be simplified into:
Let \(\mathcal {T}= \{\mathcal {T}_{a} \mid a \in \mathbb {F}_{2}^{n}\}\) be a 2-elementary regular subgroup of \(\textrm{Perm}(\mathbb {F}_{2}^{n})\) and \(T = \{T_{a} :x \mapsto x + a \mid a \in \mathbb {F}_{2}^{n}\}\) be the group of translations for the usual addition law. Then there exists \(\sigma \in \textrm{Perm}(\mathbb {F}_{2}^{n})\) such that:
6.3 Differential cryptanalysis of conjugates and \(\diamond \)-differential cryptanalysis
6.3.1 Comparative study
As already explained, the authors of [15], but also the ones of [10], consider equations of a Boolean function \(F :\mathbb {F}_{2}^{n}\rightarrow \mathbb {F}_{2}^{n}\) of the form:
where \(\diamond :\mathbb {F}_{2}^{n}\times \mathbb {F}_{2}^{n}\rightarrow \mathbb {F}_{2}^{n}\) is an Abelian group operation defined as in Proposition 13 for a 2-elementary regular subgroup \(\mathcal {T}\subseteq \textrm{Perm}(\mathbb {F}_{2}^{n})\). This is equivalent to saying that they only consider group laws \(\diamond \) that are commutative and for which each element \(x \in \mathbb {F}_{2}^{n}\) is its own inverse. In the following, we translate the framework of [10, 15] into the differential cryptanalysis of some conjugate function.
Remark 6
We stress that the relation between alternative group laws and conjugation is beyond any doubt well-known by the authors of [10‐12, 15] and mentioned at multiple times in these papers. The novelties of the following formulation is that it relates this technique to commonly-used tools and notions of standard cryptanalysis. Furthermore, this dictionary used in one way or the other provides more examples to each approach.
The notion of \(\diamond \)-differential probability is defined in [15] for any ordered pair \(({\Delta ^{\textrm{in}}}, {\Delta ^{\textrm{out}}}) \in (\mathbb {F}_{2}^{n})^{2}\) as:
We can introduce the size of the associated set of solutions \(\Gamma ^{\diamond }_{F}({\Delta ^{\textrm{in}}}, {\Delta ^{\textrm{out}}})\) that we define as:
Combined with Eq. (10), we obtain the following proposition.
Proposition 17
(\(\diamond \)-Differential, conjugation & commutation) Let \((\mathbb {F}_{2}^{n}, \diamond )\) be an Abelian group such that \(\mathcal {T}:= \{ x \mapsto x \diamond c \mid c \in \mathbb {F}_{2}^{n}\}\) is 2-elementary and regular. Let \({H}:\mathbb {F}_{2}^{n}\rightarrow \mathbb {F}_{2}^{n}\) such that: \( \forall a \in \mathbb {F}_{2}^{n}, \quad {H}\circ \mathcal {T}_{{H}^{-1}(a)} \circ {H}^{-1} = T_{a}.\) Then, it holds that
In other words, Proposition 17 states that studying the \(\diamond \)-differential properties of F is equivalent to either studying the differential properties of its conjugate \(F^{{H}}\) or the commutation with commutants among the group \(T^{{H}^{-1}}\).
Stated otherwise, the two methodologies from [10, 15] and from [4] coincide: despite the clear difference of flavors, they both study the differential properties of a conjugate cipher \(E^{{H}}_{k}\) decomposed as
by leveraging weaknesses of the conjugate round functions \((F^{(r)}_{k})^{{H}}\) for any r. We also note that both approaches are nourished from the other point-of-view.
In order to use this dictionary in both ways, we clarify that such \({H}\) is in practice easy to build.
Lemma 6
(Characterization of \({H}\)) Let \((\mathbb {F}_{2}^{n}, \diamond )\) be an Abelian group such that \(\mathcal {T}:= \{ x \mapsto x \diamond c \mid c \in \mathbb {F}_{2}^{n}\}\) is 2-elementary and regular. Let \({H}:\mathbb {F}_{2}^{n}\rightarrow \mathbb {F}_{2}^{n}\). Then \({H}\) satisfies \( \forall a \in \mathbb {F}_{2}^{n}, \quad {H}\circ \mathcal {T}_{{H}^{-1}(a)} \circ {H}^{-1} = T_{a}\) if and only if \({H}\) is a group isomorphism from \((\mathbb {F}_{2}^{n}, \diamond )\) to \((\mathbb {F}_{2}^{n}, +)\).
Proof
The mapping \({H}\) satisfies the first condition if and only if it holds that:
$$\begin{aligned} \forall \ x, y \in \mathbb {F}_{2}^{n}, \quad x \diamond y = \mathcal {T}_{y}(x) = {H}^{-1} \circ T_{{H}(y)} \circ {H}(x). \end{aligned}$$
Because \((\mathbb {F}_{2}^{n}, \diamond )\) is actually an n-dimensional \(\mathbb {F}_2\)-vector space, we can fix ourselves a basis \((b_{1},\dotsc , b_{n})\) such that any element \(x \in \mathbb {F}_{2}^{n}\) can be uniquely decomposed as \( x = y_{1}b_{1} \diamond y_{1}b_{1} \diamond \dotsc \diamond y_{n}b_{n}\), with \(y_{i} \in \mathbb {F}_{2}\) for all i. By Lemma 6, an isomorphism \({H}\) must therefore satisfy:
Building such a \({H}\) is therefore equivalent to selecting a basis \((B_{1}, \dotsc , B_{n})\) of \((\mathbb {F}_{2}^{n}, +)\), defining \({H}(b_{i}) = B_{i}\) for any i, and expanding the definition by linearity.
The set \(W^{\diamond }\) is defined as \(W^{\diamond } = \{ k \in \mathbb {F}_{2}^{n}\mid T_{k} \in \mathcal {T}\}\) in [11]. Both definitions coincide because \(\mathcal {T}\) is regular, so the condition \(T_{k} \in \mathcal {T}\) necessarily implies that \(T_{k}\) and \(\mathcal {T}_{k}\) must coincide because \(T_{k}(0) = k = \mathcal {T}_{k}(0)\).
From the conjugate point-of-view, \(W^{\diamond }\) can be described as:
In other words, \(W^{\diamond }\) is the set of k for which the conjugate of \(T_{k}\) is still a constant addition, with a possibly different constant. However, a function \(F :\mathbb {F}_{2}^{n}\rightarrow \mathbb {F}_{2}^{n}\) is affine with L as linear part if and only if it satisfies:
We thus obtain the following definition of \(W^{\diamond }\).
Lemma 7
(\(W^{\diamond }\) as a weak-key space) Let \((\mathbb {F}_{2}^{n}, \diamond )\) be an Abelian group such that \(\mathcal {T}:= \{ x \mapsto x \diamond c \mid c \in \mathbb {F}_{2}^{n}\}\) is 2-elementary and regular. Let \({H}:\mathbb {F}_{2}^{n}\rightarrow \mathbb {F}_{2}^{n}\) such that: \( \forall a \in \mathbb {F}_{2}^{n}, \quad {H}\circ \mathcal {T}_{{H}^{-1}(a)} \circ {H}^{-1} = T_{a}.\) Then,
where \(\textbf{1}_{x}(y) = 1 \) if \(x = y\) and 0 otherwise.
The description of \(W^{\diamond }\) in Lemma 7 explains the fact that it is indeed a weak-key space: whenever k belongs to \(W^{\diamond }\), any differential transition through \(T_{k}^{{H}}\) is deterministic. Stated otherwise, such a transition only depends on the differences and is independent of the actual values of the considered pair.
While Lemma 7 clearly outlines the importance of the set \(W^{\diamond }\) in such a study, its structure can still be clarified. This is the purpose of Lemma 8, which relies on the notion of linear structures. In the following, we denote by \(D_{{\Delta }}F\) the derivative of a function \(F :\mathbb {F}_{2}^{n}\rightarrow \mathbb {F}_{2}^{n}\) with respect to \({\Delta }\in \mathbb {F}_{2}^{n}\) for the usual addition law, i.e.\(D_{{\Delta }}F(x) = F(x + {\Delta }) - F(x)\).
[Style2 Style1 Style3 Style3]Definition 11
(Linear structure). Let \(F :\mathbb {F}_{2}^{n}\rightarrow \mathbb {F}_{2}^{n}\). Let \({\Delta }\in \mathbb {F}_{2}^{n}\). The difference \({\Delta }\) is said to be a linear structure of F if the derivative \(D_{{\Delta }}F\) is a constant function. The set of linear structures of F is denoted by \(\mathcal {E}_{F}\), that is:
(\(W^{\diamond }\) as linear space of \({H}\)) Let \((\mathbb {F}_{2}^{n}, \diamond )\) be an Abelian group such that \(\mathcal {T}:= \{ x \mapsto x \diamond c \mid c \in \mathbb {F}_{2}^{n}\}\) is 2-elementary and regular. Let \({H}:\mathbb {F}_{2}^{n}\rightarrow \mathbb {F}_{2}^{n}\) such that: \( \forall a \in \mathbb {F}_{2}^{n}, \quad {H}\circ \mathcal {T}_{{H}^{-1}(a)} \circ {H}^{-1} = T_{a}.\) Then, \(W^{\diamond } = \mathcal {E}_{{H}}\).
Proof
Starting from the first definition of \(W^{\diamond }\), we observe that:
where we use the fact that commutations with constant addition corresponds to differential transitions. The last equality holds because the value of a constant derivative \(D_{k}{H}\) is necessary \({H}(k) - {H}(0)\) but we have by construction that \({H}(0) = 0\). \(\square \)
In the light of the following standard results, see for instance [28], the notion of linear structure is relatively well understood and gives new insight on this set of weak keys.
Lemma 9
(Standard properties of linear structures) Let \(F :\mathbb {F}_{2}^{n}\rightarrow \mathbb {F}_{2}^{n}\). Then:
1.
\(\mathcal {E}_{F}\) is a linear space and the restriction of F to \(\mathcal {E}_{F}\) is affine.
2.
If F is bijective then \(\mathcal {E}_{F^{-1}} = F(0) + F(\mathcal {E}_{F})\) and in particular \(\dim (\mathcal {E}_{F}) = \dim (\mathcal {E}_{F^{-1}}) \).
3.
[28, Theorem 3] Let \(r = \dim (\mathcal {E}_{F})\). Then there exists a linear bijection A such that \(F \circ A \) can be decomposed as:
where \(L :\mathbb {F}_{2}^{r} \rightarrow \mathbb {F}_{2}^{n}\) is linear and \(\widetilde{F} :\mathbb {F}_{2}^{n-r} \rightarrow \mathbb {F}_{2}^{n}\) satisfies \(\mathcal {E}_{\widetilde{F}} = \{0\}\).
Corollary 10
(Dimension of \(\mathcal {E}_{F}\)) Let \(F :\mathbb {F}_{2}^{n}\rightarrow \mathbb {F}_{2}^{n}\). Then, \(\deg (F) \le n - \dim (\mathcal {E}_{F})\). If F is not affine, then \(\dim (\mathcal {E}_{F}) \le n-2\). In particular, if \(\dim (\mathcal {E}_{F}) = n-2\), we have \(\deg (F) = 2\).
Proof
The fact that for any F, it holds that \(\deg (F) \le n - \dim (\mathcal {E}_{F})\) is a consequence of the third item of Lemma 9: F is equivalent to a function which can only be non-linear in its \(n- \dim (\mathcal {E}_{F})\) last variables. If \(\dim (\mathcal {E}_F) = n-2\), then F is of degree at most 2. However, it must be of degree exactly 2 because the linear space of an affine function is the full space \(\mathbb {F}_{2}^{n}\). \(\square \)
Upper bound on\(\varvec{W^{\diamond } =\mathcal {E}_{{H}}}\). This understanding of linear structures can then be applied to our case. Recall that in order to be an interesting change of variables, \({H}\) must be non-linear. In light of Corollary 10, it then satisfies \(\dim (\mathcal {E}_{{H}}) \le n-2\). The fact that \(\dim (W^{\diamond }) \le n-2\) that is stated in [11, Proposition 4.1] can then be seen as a consequence of this more general case.
Lower bound on\(\varvec{W^{\diamond } =\mathcal {E}_{{H}}}\). Civino, Blondeau & Sala actually choose \({H}\) with at least one non-trivial linear structure. This is guaranteed whenever \(\mathcal {T}\) is a subgroup of the affine group. The following proposition is adapted from the work of Caranti, Dalla Volta & Sala [12] where it is stated in a more general context.
Proposition 18
(Non-trivial weak-key space [12]) Let \(\mathcal {T}\) be a 2-elementary regular subgroup of the affine group \(\textrm{AGL}(n,\mathbb {F}_2)\). Then \(\mathcal {T}\cap T \ne \{I\}\), and thus \(W^{\diamond } = \{k \in \mathbb {F}_{2}^{n}\mid T_{k} \in \mathcal {T}\cap T\} \ne \{0\}\).
Proof
(Adapted from [12]) For any x, we can by hypothesis decompose \(\mathcal {T}_{x}\) as \(\mathcal {T}_{x} = T_{x} \circ L_{x}\) where \(L_{x}\) is linear. Because \(\mathcal {T}_{x}^{2} = I\), it holds for any \(z \in \mathbb {F}_{2}^{n}\) that:
$$\begin{aligned} z = L_{x}(L_{x}(z) + x) + x = L_{x}^{2}(z) + L_{x}(x) + x. \end{aligned}$$
In particular with \(z = 0\), we observe that \(L_{x}(x) = x\). Therefore, we also get \(L_{x}^{2} = I\). Let \(x, y \in \mathbb {F}_{2}^{n}\). Then:
where we successively use the decomposition of \(\mathcal {T}_{x}\), the fact that \(T_{y}T_{x} = T_{y + x}\), the fact that \(L_{x}T_{y+x} = T_{L_{x}(y+x)}L_{x}\) because \(L_{x}\) is linear, then \(L_{x}^{2} = I\) and finally \(x = L_{x}(x)\) and the linearity of \(L_{x}\) again. In particular, we observe that \(\mathcal {T}_{x}T_{y}\mathcal {T}_{x} \in T\) for any \(x, y \in \mathbb {F}_{2}^{n}\). This implies that the function \(F :\mathcal {T}\times T \rightarrow T\) that is defined as:
$$\begin{aligned} F :(\mathcal {T}_{x}, T_{y}) \mapsto \mathcal {T}_{x}T_{y}\mathcal {T}_{x}; \end{aligned}$$
is actually well-defined. It corresponds to the action by conjugation of \(\mathcal {T}\) on the set T as \(\mathcal {T}_{x}^{-1} = \mathcal {T}_{x}\) for any x in our case. As for any action of a p-group H on a set Z, the orbit-stabilizer theorem states that the number of elements that are H-invariants is equal to \(|Z |\) modulo p. In our case, the set Z of \(\mathcal {T}\)-invariants is defined by:
$$\begin{aligned} Z := \{T_{y} \mid \mathcal {T}_{x}T_{y}\mathcal {T}_{x} = T_{y} \forall x \in \mathbb {F}_{2}^{n}\} \end{aligned}$$
and it must be of even cardinality. As it contains \(T_{0} = I\), it must contain at least a non-trivial element. To conclude, we now show that Z is actually equal to \(\mathcal {T}\cap T\). Indeed, we have:
$$\begin{aligned} Z&= \{T_{y} \mid T_{L_{x}(y)} = T_{y}, \ \forall \ x \in \mathbb {F}_{2}^{n}\}\\&= \{T_{y} \mid L_{x}(y) + y = 0, \ \forall \ x \in \mathbb {F}_{2}^{n}\}\\&= \{T_{y} \mid L_{y}(x) + x = 0, \ \forall \ x \in \mathbb {F}_{2}^{n}\}\\&= \{T_{y} \mid L_{y} = I\}\\&= \{T_{y} \mid \mathcal {T}_{y} = T_{y}\}\\&= \mathcal {T}\cap T. \end{aligned}$$
The third equality holds because for any \(x, y \in \mathbb {F}_{2}^{n}\), we have:
$$\begin{aligned} L_{x}(y) + y = \mathcal {T}_{x}(y) + y + x = \mathcal {T}_{y}(x) + y + x = L_{y}(x) + x. \end{aligned}$$
\(\square \)
Corollary 11
Let \({H}:\mathbb {F}_{2}^{n}\rightarrow \mathbb {F}_{2}^{n}\) be bijective. Let us suppose that \({H}\circ T_{c} \circ {H}^{-1}\) is affine for any \( c\in \mathbb {F}_{2}^{n}\). Then \(\dim (\mathcal {E}_{{H}}) \ge 1\).
The case\(\varvec{\dim (W^{\diamond }) = \dim (\mathcal {E}_{{H}}) = n-2}\). Civino, Blondeau & Sala [15] finally studies the case \(\dim (W^{\diamond }) = n-2\) in more detail. Let \({H}\) be a bijection such that \(\dim (\mathcal {E}_{{H}}) = n-2\). Because of the third item of Lemma 9, \({H}\) can be written as \({H}= H' \circ A^{-1}\), where A is a linear bijection and \(H' :\mathbb {F}_{2}^{n}\rightarrow \mathbb {F}_{2}^{n}\) a function whose components are made only of constant terms, affine terms and the quadratic term \(x_{1}x_{2}\). Note that \(x_{1}x_{2}\) must appear in at least one coordinate, but not necessarily all of them. In particular there exists a bijective linear mapping B such that \(B \circ H'\) has a single coordinate containing \(x_{1}x_{2}\) while all others are affine. However, the differential properties of \(F^{{H}}\) and the ones of \(F^{B \circ {H}}\) are identical as \(F^{B \circ {H}} = B \circ F^{{H}} \circ B^{-1}\). This implies that the choices of change of variables \({H}\) made by the authors of [10, 15] are similar to the choices made by the authors of [3, 4] for the analysis of conjugate Midori.
Note that, because of Lemma 9, the specific case \(\dim (\mathcal {E}_{{H}}) = n-2\) implies that \(\dim (\mathcal {E}_{{H}^{-1}}) = n-2\), and due to Corollary 10, both \({H}\) and \({H}^{-1}\) are quadratic.
Examples where both \(\mathcal {T}\subseteq \textrm{AGL}(n,\mathbb {F}_2)\) and \(\dim (W^{\diamond }) = n-2\) are given in [10, 15]. Another one based on [4] is given in Sect. 6.4.
As shown in Lemma 7, whenever a key belongs to \(W^{\diamond }\), the actual key used does not matter anymore as the behavior is deterministic and independent of the key, and the actual differences. This enables to launch any kind of differential attack as it is done in the classical way.
However, contrary to the standard case, the fraction of the keys cannot exceed one quarter of the key space. In the setting where the change of variable is a parallel application of a non-linear change of variables of the size of the S-box, this fraction is in practice way smaller.
But \(W^{\diamond }\) is a conservative choice of weak-key space in the sense that it enables any differential attack. On the contrary, if we are instead interested in a specific attack taking advantage of some specific transition, we can hope for a bigger set of weak keys. Let \({\Delta ^{\textrm{in}}}, {\Delta ^{\textrm{out}}}\in \mathbb {F}_{2}^{n}\), and let us consider . In that case, we actually want to consider the set \(W({\Delta ^{\textrm{in}}}, {\Delta ^{\textrm{out}}})\) that is defined as:
In other words, we would like to consider linear structures shared by multiple \(T_{k}^{{H}}\), for which the corresponding constant derivatives are equal. A direct corollary of Lemma 7 is that for a given \({\Delta }\in \mathbb {F}_{2}^{n}\) we have:
However, in practice \(\mathcal {E}_{{H}}\) can be a strict subset of \(W({\Delta }, {\Delta })\). An example is given in Sect. 6.4. Furthermore, while transitions with probability 1 imitate the standard differential case for the bitwise addition, there might exist \({\Delta ^{\textrm{in}}}\ne {\Delta ^{\textrm{out}}}\) such that \(W({\Delta ^{\textrm{in}}}, {\Delta ^{\textrm{out}}}) \ne \emptyset \). Therefore, transitions with probability 1 can also be considered in a weak-key setting. This is in particular important in the case where \(T_{k}^{{H}}\) is affine for any k. In that specific case, \(W({\Delta ^{\textrm{in}}}, {\Delta ^{\textrm{out}}})\) becomes
because any derivative of any \(T_{k}^{{H}}\) is constant. This also means that for a fixed \({\Delta ^{\textrm{in}}}\in \mathbb {F}_{2}^{n}\), the sets \(W({\Delta ^{\textrm{in}}}, {\Delta ^{\textrm{out}}})\) for all \({\Delta ^{\textrm{out}}}\in \mathbb {F}_{2}^{n}\) partition the set of round keys:
6.4 Complementing some examples from [3, 4, 10, 15]
6.4.1 A conjugate of the block cipher Midori
Let us take a closer look at the analysis of conjugate Midori that is addressed in [4, Appendix A] and in more detail in [3]. As a reminder of these works, there exists a change of variables \({H}:\mathbb {F}_{2}^{4} \rightarrow \mathbb {F}_{2}^{4}\) for which holds with probability 1 for \({\Delta }= \texttt {0xd}\). This can be easily verified from the look-up tables given in Table 1.
Table 1
A specific change of variables for the S-box of Midori64
x
0
1
2
3
4
5
6
7
8
9
a
b
c
d
e
f
\({H}(x)\)
0
3
4
7
2
1
6
5
8
a
c
e
b
9
f
d
\(S^{{H}}(x)\)
b
e
f
c
9
5
d
7
8
4
a
0
3
6
1
2
\(S^{{H}}(x + {\Delta })\)
6
3
2
1
4
8
0
a
5
9
7
d
e
b
c
f
Furthermore the 16-time parallel application of \({H}\), that we denote by \({\mathcal {H}}:(\mathbb {F}_{2}^{4})^{16} \rightarrow (\mathbb {F}_{2}^{4})^{16}\), naturally satisfies with probability 1 where \(\mathcal {S}:(\mathbb {F}_{2}^{4})^{16} \rightarrow (\mathbb {F}_{2}^{4})^{16}\) is the full S-box layer, and where \({\nabla }= ({\Delta }, \dotsc , {\Delta })\). It can also be verified that holds with probability 1 for the linear layer of Midori. Let us then take a closer look at the constant addition. The ANF of \({H}\) and of \(T^{{H}} :(x, k) \mapsto T_{k}^{{H}}(x)\) are given by:
where the input bits are listed from the LSB \(x_{1}\) to the MSB \(x_{4}\) and the output coordinates are listed top to bottom from the least significant one to the most significant one.
In particular, we are here studying properties of conjugate functions of the form \(F^{{H}}\). By Proposition 17, this is equivalent to studying the \(\diamond \)-differential properties for the law \(\diamond \) whose group of translations is \(\mathcal {T}= {H}^{-1} T {H}\). For this reason, we can also look at all \(T_{k}^{{H}^{-1}}\). Their ANFs, as well as the ANF of \(\diamond \) are given by:
Because of Lemma 8, we can determine \(W^{\diamond }\) without this explicit formula for \(\diamond \). Indeed, it suffices to look at the linear structures of \({H}\). From the ANF of \({H}\), it is clear that:
The derivative \(D_{{\Delta }}{H}\) is therefore constant if and only if \({\Delta }_{1} = {\Delta }_{3}\) and \({\Delta }_{4} = 0\), and, as expected, the same set \(W^{\diamond }\) is obtained.
However, when focusing on the specific transition for a given \({\Delta }\in \mathbb {F}_{2}^{4}\), we can compute \(W({\Delta }, {\Delta })\). Let \(k \in \mathbb {F}_{2}^{4}\). Because \(T_{k}^{{H}}\) is affine, its derivative is constant and equal to:
We then conclude in that case that \(D_{{\Delta }}T_{k}^{{H}} = {\Delta }\) if and only if \(k_{1} + k_{3} = 0\) and therefore \(W({\Delta }, {\Delta })\) is equal to:
In particular, \(W({\Delta }, {\Delta })\) is strictly bigger than \(W^{\diamond }\) and the differential trail holds with probability 1 if all nibbles of all rounds keys and round constants belong to \(W({\Delta }, {\Delta })\).
Finally in this case, because of Proposition 17, the differential transition that holds with probability 1, can equivalently be considered as a probability-1 \(\diamond \)-differential transition \({H}^{-1}({\Delta })\rightarrow {H}^{-1}({\Delta })\) for the law \(\diamond \) given above (where \(H^{-1}(\Delta ) = \texttt {0xf}\) as shown in Table 1), or as probability-1 commutation with the affine function \(A :=T^{{H}^{-1}}_{{\Delta }}\) where \({\Delta }= \texttt {0xd}\). Its ANF can easily be deduced from Eq. (25) using \(k = {H}^{-1}({\Delta }) = \texttt {0xf} = \texttt {0b1111}\) and is given below:
The toy cipher of [15]. In [15], a block cipher with a 15-bit state is proposed to illustrate \(\diamond \)-differential cryptanalysis. It has a standard SPN structure where the S-box layer is the 5-time parallel application of a single 3-bit S-box \(S :\mathbb {F}_{2}^{3} \rightarrow \mathbb {F}_{2}^{3}\).
The S-box used in [15] and a suitable change of variables \({H}\)
x
0
1
2
3
4
5
6
7
S(x)
0
6
2
1
5
7
4
3
x
0
1
2
3
4
5
6
7
\({H}(x)\)
0
1
2
3
6
7
5
4
In order to study this S-box, the authors introduced the law \(\diamond :\mathbb {F}_{2}^{3} \times \mathbb {F}_{2}^{3} \rightarrow \mathbb {F}_{2}^{3}\) that is defined as:
$$\begin{aligned} \forall x, y \in \mathbb {F}_{2}^{3}, \quad x \diamond y := \left( \begin{array}{c} x_{1} + y_{1} + x_{2}y_{3} + x_{3}y_{2}\\ x_{2} + y_{2}\\ x_{3} + y_{3} \end{array}\right) . \end{aligned}$$
We can computationally verify that this S-box is APN, however it has a probability-1 \(\diamond \)-differential transition \({\Delta ^{\textrm{in}}}\xrightarrow [\diamond ]{S} {\Delta ^{\textrm{out}}}\), where \({\Delta ^{\textrm{in}}}= \texttt {0x6}, {\Delta ^{\textrm{out}}}= \texttt {0x4}\). This can be equivalently understood as probability-1 commutative property, or as a probability-1 differential of \(S^{{H}}\) for some \({H}\).
satisfies the equality \(x \diamond y = T_{{H}(y)}^{{H}^{-1}}(x)\) for any x, y. Because of Lemma 6, any isomorphism between \((\mathbb {F}_{2}^{3}, \diamond )\) and \((\mathbb {F}_{2}^{3}, +)\) actually works. We focus here on this arbitrary case. In particular, we consider \({A}\) and \({B}\) that we define as:
By Proposition 17, it holds that \(S \circ {A}= {B}\circ S\). This can be verified from the ANF of S that is given below, together with the one of \(S^{{H}}\).
We also easily observe that the differential holds with probability 1. This is again due to Proposition 17, because \({H}({\Delta ^{\textrm{in}}}) = \texttt {0x5}\) and \({H}({\Delta ^{\textrm{out}}}) = \texttt {0x6}\).
The toy cipher of [10]. The recent work of Calderini, Civino & Invernizzi [10] deals with the resistance against \(\diamond \)-differential cryptanalysis of S-boxes which are optimal with respect to standard differential cryptanalysis. They in particular show that such S-boxes have no reason to be optimal for other laws \(\diamond \), and among an affine equivalence class, two distinct S-boxes can have two distinct uniformities with respect to \(\diamond \).
To illustrate their work, they build a similar SPN than before, this time with a 16-bit block size that is decomposed into 4 cells of four bits. The used 4-bit S-box S is given in Table 3.
Its differential uniformity is 4, but, for a law \(\diamond \) built in the same way as before, it has a probability-1 \(\diamond \)-differential transition \({\Delta ^{\textrm{in}}}\xrightarrow [\diamond ]{S} {\Delta ^{\textrm{out}}}\), where \({\Delta ^{\textrm{in}}}= \texttt {0x7}, {\Delta ^{\textrm{out}}}= \texttt {0x6}\). The law is defined3 as:
This corresponds to a commutation with probability 1 from \({A}= \mathcal {T}_{\texttt {0x7}}\) to \({B}= \mathcal {T}_{\texttt {0x6}}\), or a probability-1 differential for a suitable \({H}\). We can for instance use:
Open Access funding enabled and organized by Projekt DEAL. This work was funded by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) under Germany’s Excellence Strategy—EXC 2092 CASA—390781972, by the ERC advanced grant 101097056 (SYMTRUST) and the ERC starting grant 101041545 (ReSCALE), and by ANR (French National Research Agency) grant ANR-20-CE48-0017 (SELECT).
Declarations
Conflict of interest
The authors declare no Conflict of interest.
Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Recently, there is a significant amount of research on so-called arithmetization-oriented primitives with many ciphers defined over a field of odd characteristic.
corresponds to a constant derivative of \(F^{{H}}\), i.e.:Equation (9) can equivalently be written as \( T_{{\Delta ^{\textrm{out}}}} \circ {H}\circ F \circ {H}^{-1} = {H}\circ F \circ {H}^{-1} \circ T_{{\Delta ^{\textrm{in}}}}\), but also as \( \quad T_{{\Delta ^{\textrm{out}}}}^{{H}^{-1}} \circ F = F \circ T_{{\Delta ^{\textrm{in}}}}^{{H}^{-1}} \), by conjugating the latter expression by \({H}^{-1}\).
where \(A, B :\mathbb {F}_{2}^{n}\rightarrow \mathbb {F}_{2}^{n}\) are strongly constrained. For instance, it cannot exactly handle pairs (A, B) where one of the commutants is not a fixed-point-free involution (because of the 2-elementarity) or pairs for which there exists \(x \in \mathbb {F}_{2}^{n}\), such that \(A(x) = B(x)\) (because of the regularity). Nonetheless, for any of these situations, it is still possible to approximate A and B by two elements of a given \({H}^{-1}T{H}\) to obtain an approximation on the number of solutions of a given relation
.
We thus obtain the following definition of \(W^{\diamond }\).
where \(\textbf{1}_{x}(y) = 1 \) if \(x = y\) and 0 otherwise.
. In that case, we actually want to consider the set \(W({\Delta ^{\textrm{in}}}, {\Delta ^{\textrm{out}}})\) that is defined as:
In other words, we would like to consider linear structures shared by multiple \(T_{k}^{{H}}\), for which the corresponding constant derivatives are equal. A direct corollary of Lemma 7 is that for a given \({\Delta }\in \mathbb {F}_{2}^{n}\) we have:However, in practice \(\mathcal {E}_{{H}}\) can be a strict subset of \(W({\Delta }, {\Delta })\). An example is given in Sect. 6.4. Furthermore, while transitions
with probability 1 imitate the standard differential case for the bitwise addition, there might exist \({\Delta ^{\textrm{in}}}\ne {\Delta ^{\textrm{out}}}\) such that \(W({\Delta ^{\textrm{in}}}, {\Delta ^{\textrm{out}}}) \ne \emptyset \). Therefore, transitions
with probability 1 can also be considered in a weak-key setting. This is in particular important in the case where \(T_{k}^{{H}}\) is affine for any k. In that specific case, \(W({\Delta ^{\textrm{in}}}, {\Delta ^{\textrm{out}}})\) becomesbecause any derivative of any \(T_{k}^{{H}}\) is constant. This also means that for a fixed \({\Delta ^{\textrm{in}}}\in \mathbb {F}_{2}^{n}\), the sets \(W({\Delta ^{\textrm{in}}}, {\Delta ^{\textrm{out}}})\) for all \({\Delta ^{\textrm{out}}}\in \mathbb {F}_{2}^{n}\) partition the set of round keys:
holds with probability 1 for \({\Delta }= \texttt {0xd}\). This can be easily verified from the look-up tables given in Table 1.
with probability 1 where \(\mathcal {S}:(\mathbb {F}_{2}^{4})^{16} \rightarrow (\mathbb {F}_{2}^{4})^{16}\) is the full S-box layer, and where \({\nabla }= ({\Delta }, \dotsc , {\Delta })\). It can also be verified that
holds with probability 1 for the linear layer of Midori. Let us then take a closer look at the constant addition. The ANF of \({H}\) and of \(T^{{H}} :(x, k) \mapsto T_{k}^{{H}}(x)\) are given by:where the input bits are listed from the LSB \(x_{1}\) to the MSB \(x_{4}\) and the output coordinates are listed top to bottom from the least significant one to the most significant one.
for a given \({\Delta }\in \mathbb {F}_{2}^{4}\), we can compute \(W({\Delta }, {\Delta })\). Let \(k \in \mathbb {F}_{2}^{4}\). Because \(T_{k}^{{H}}\) is affine, its derivative is constant and equal to:In the specific case where \({\Delta }= \texttt {0xd} = \texttt {0b1101}\), we obtain:We then conclude in that case that \(D_{{\Delta }}T_{k}^{{H}} = {\Delta }\) if and only if \(k_{1} + k_{3} = 0\) and therefore \(W({\Delta }, {\Delta })\) is equal to:In particular, \(W({\Delta }, {\Delta })\) is strictly bigger than \(W^{\diamond }\) and the differential trail
holds with probability 1 if all nibbles of all rounds keys and round constants belong to \(W({\Delta }, {\Delta })\).
that holds with probability 1, can equivalently be considered as a probability-1 \(\diamond \)-differential transition \({H}^{-1}({\Delta })\rightarrow {H}^{-1}({\Delta })\) for the law \(\diamond \) given above (where \(H^{-1}(\Delta ) = \texttt {0xf}\) as shown in Table 1), or as probability-1 commutation with the affine function \(A :=T^{{H}^{-1}}_{{\Delta }}\) where \({\Delta }= \texttt {0xd}\). Its ANF can easily be deduced from Eq. (25) using \(k = {H}^{-1}({\Delta }) = \texttt {0xf} = \texttt {0b1111}\) and is given below:
holds with probability 1. This is again due to Proposition 17, because \({H}({\Delta ^{\textrm{in}}}) = \texttt {0x5}\) and \({H}({\Delta ^{\textrm{out}}}) = \texttt {0x6}\).
for a suitable \({H}\). We can for instance use: