Christina Boura
email: christina.boura@prism.uvsq.fr

Anne Canteaut
email: anne.canteaut@inria.fr

Lars R Knudsen

Gregor Leander
email: gregor.leander@rub.de

Reflection Ciphers

Keywords: Reflection ciphers, Involutions, Related-key distinguishers, PRINCE

published or not. The documents may come   L'archive ouverte pluridisciplinaire

Introduction

Among all design strategies used for reducing the implementation cost of a cipher, one option consists in minimizing the overhead of decryption on top of encryption. This feature was essential when encryption was performed by heavy cipher machines since having two different machines, one for encryption and a different one for decryption was unthinkable. This issue was then solved a century ago by Arthur Scherbius who introduced a reflector into the Enigma machine, that means an involutive transformation M which is applied to the initial permutation and which is followed by the inverse permutation. Then, for any key, the encryption function has the form E k = F -1 • M • F , implying that it is an involution. However, involutive ciphers present serious flaws, including the fact that any involution can be easily distinguished from a randomly permutation by the number of its fixed points. This type of weaknesses has been exploited for cryptanalyzing Enigma. Instead, a classical solution consists in constructing a cipher based on involutive building-blocks. For instance, the different round permutations can be chosen within a family of involutions parameterized by a round key, i.e., E (k1,...,kr) = F kr • . . . • F k2 • F k1 where all F x are involutions. Then, the decryption function under the round-key sequence (k 1 , . . . , k r ) is equal to the encryption function under the same round-key sequence but in reverse order, i.e. Rev(k 1 , . . . , k r ) = (k r , . . . , k 1 ). Feistel ciphers with independent round-keys are the most prominent examples of this construction [START_REF] Feistel | Some Cryptographic Techniques for Machine-To-Machine Data Communications[END_REF]. But, since the round key sequence is usually derived from a master key, i.e., (k 1 , . . . , k r ) = KS(k), the choice of the key expansion KS has a major influence both on the security and on the implementation cost of the cipher. Indeed, KS should obviously be chosen such that KS(k) does not provide any palindromic round-key sequence. Otherwise, the cipher would have some weak keys under which the encryption is an involution. Moreover, computing Rev(KS(k)) requires either the storage of the whole round-key sequence, or the implementation of the reverse key expansion function, like in the DES, for instance.

The implementation overhead due to the reverse key schedule can be avoided by designing a cipher such that the family of decryption functions obtained for all master keys is exactly the same as the family of all encryption functions. In other words, for any master key k, there exists another key k such that decryption with key k corresponds to encryption with k . This has been used in [START_REF] Borghoff | PRINCE -A Low-latency Block Cipher for Pervasive Computing Applications[END_REF] for the block cipher PRINCE, more precisely for its core cipher PRINCE core , where k = k ⊕ α for some constant α. However, we could think of a more general setting where there exists some permutation P of the key space such that, for any key k,

(E k ) -1 = E P (k) (1)
Such ciphers will be called reflection ciphers and the permutation P the coupling permutation. As previously explained, reflection ciphers obviously include all constructions with involutive round functions, like Feistel ciphers. RSA is also a reflection cipher and in this case, the coupling permutation is secret: P is the permutation of the set {x ∈ {2, . . . , (p-1)(q -1)-1} : gcd(x, (p-1)(q -1)) = 1} corresponding to inversion modulo (p -1)(q -1), where p and q are two distinct prime numbers.

Our Contribution. In this work we study the properties of reflection ciphers and derive several universal conditions on how the coupling permutation P should be constructed. We start by exhibiting very general properties, showing for example that a coupling permutation should be an involution and that fixed points should be avoided (cf. Section 2). Obviously, reflection ciphers are not ideal in the related-key setting since the relation (E k ) -1 = E P (k) allows to easily distinguish them from an ideal cipher. We therefore explicitly exclude related-key attacks here. However, an important observation is that some relatedkey distinguishers may have a practical impact since they provide attacks in the single-key model, in a scenario where an attacker has access to both the encryption and the decryption operations. Therefore we study the influence of the choice of P on such attacks, in particular on differential related-key distinguishers. We elaborate on the trade-off between the size of (possibly weak) key classes and the minimal Hamming weight of the difference P (k) ⊕ k introduced by comparing the encryption with the decryption process. We investigate different kinds of coupling permutations such as affine permutations, including functions based on bit permutations, nonlinear permutations and some combinations of those by analyzing for each case the impact of related-key distinguishers (cf. Section 3). We show in particular, that each family of functions can offer different trade-offs between the two above quantities. In Section 4 we focus on key-alternating block ciphers by emphasizing on ciphers with n-bit block size and 2n-bit key size. The block cipher PRINCE [START_REF] Borghoff | PRINCE -A Low-latency Block Cipher for Pervasive Computing Applications[END_REF] is an example of this family of ciphers. In the approach followed by its designers, the key size is a priori limited to the block size, and the solution chosen for doubling the key size is not optimal and raises security questions [START_REF] Dinur | Cryptanalytic Time-Memory-Data Tradeoffs for FX-Constructions with Applications to PRINCE and PRIDE[END_REF]. We try here to answer this question by presenting some variants that offer a better security, corresponding to different coupling permutations.

Because of the limited number of pages, most proofs are omitted in this extended abstract.

General Criteria For the Coupling Mapping

In this section we derive criteria for the coupling mapping P . These criteria are general and can be applied to different settings. For the rest of this paper, κ denotes the key size and n the block size of the cipher. Therefore, the coupling mapping is a function from F κ 2 into F κ 2 .

Cycle structure of the coupling mapping

It is clear that Relation (1) makes sense only when the coupling mapping P is a permutation: otherwise, there exists a subset of the key space which leads to the same family of encryption functions. Moreover, Relation [START_REF] Albrecht | On Cipher-Dependent Related-Key Attacks in the Ideal-Cipher Model[END_REF] implies that

E k = E P 2i (k) , ∀i ≥ 1,
for any key k. Then, if P is not an involution, several keys again lead to the same encryption function, implying that the effective size of the key space is reduced. Therefore, we focus on the case where P is an involution.

Fixed points of the coupling mapping. Fixed points of P correspond to weak keys for the cipher, since the corresponding encryption functions are involutive. Indeed, random involutions can be distinguished from random permutations by using the fact that such involutions over F κ 2 have 2 κ a randomly chosen permutation has O(1) fixed points [START_REF] Flajolet | Analytic Combinatorics[END_REF]Page 596]. This weakness is well-known and has been exhibited in several works, including [START_REF] Youssef | A New Class of Substitution-Permutation Networks[END_REF]. It is worth noticing that, in the particular case of an iterative construction of the form E k = F -1 • M • F , E k has exactly the same number of fixed points as the middle round M (and more general the exact same cycle structure). This fact has been exploited for weak keys in DES where the middle round is the swapping of the two halves, which has exactly 2 32 fixed points [START_REF] Coppersmith | The Real Reason for Rivest's Phenomenon[END_REF], and also in Enigma where the reflector has no fixed points. Fixed points of the coupling mapping also introduce weaknesses when E is not used directly as an encryption function, but is modified by the F Xconstruction [START_REF] Biryukov | DES-X (or DESX)[END_REF][START_REF] Kilian | How to protect DES against exhaustive key search (an analysis of DESX)[END_REF]. This construction (aka the Even-Mansour construction [START_REF] Even | A Construction of a Cipher From a Single Pseudorandom Permutation[END_REF]) extends a block cipher E with a κ-bit key to a block cipher with a (κ + 2n)-bit key by XORing two n-bit secret whitening keys to the input and the output of the cipher respectively. If the reflection cipher E is used as inner cipher in the F X-construction, fixed points in the coupling mapping can be exploited by the attacker to recover some information on the whitening keys (see Section 4.2 in [START_REF] Borghoff | PRINCE -A Low-latency Block Cipher for Pervasive Computing Applications[END_REF]).

Affine coupling mappings

In this section, we focus on the case where P is an affine mapping, which is of particular interest as affine functions permit efficient implementations. By elementary linear algebra, we obtain the following simple characterization of affine involutions without fixed points. To avoid any ambiguity, we draw attention to the fact that elements in F κ 2 are seen as row vectors, and that linear permutations are written x → xM for some matrix M . Proposition 1. Let P be an affine function of F κ 2 . Then, P is an involution without any fixed points if and only if φ : x → P (x) + P (0) + x satisfies Im φ ⊂ Ker φ and P (0) belongs to Ker φ \ Im φ.

It is worth noticing that the condition Im φ ⊂ Ker φ implies that dim Ker φ > κ/2. Also, the previous proposition recovers the result from [17, Lemma 1]: any linear involution over F κ 2 has at least 2 κ/2 fixed points, since we have proved that P is a linear involution if and only if Im φ ⊆ Ker φ.

When L : x → P (x) + P (0) corresponds to a bit permutation, we can derive a very simple characterization of the mappings which satisfy the conditions of the previous proposition.

Proposition 2. Let π be a permutation of {1, . . . , κ} and M the corresponding κ × κ permutation matrix. Then, there exists α such that x → xM + α is an involution without fixed points if and only if π is an involution with at least one fixed point.

In Section 4.2 of [START_REF] Borghoff | PRINCE -A Low-latency Block Cipher for Pervasive Computing Applications[END_REF] the authors explain that the coupling mapping P (k 1 , k 2 ) = (k 2 , k 1 ) + (α, α) should be avoided for any choice of the constant α. Indeed, this mapping presents an obvious class of weak keys, that can be easily detected: all keys (k 1 , k 2 ) with k 2 = k 1 + α are fixed points of P . Then, the corresponding encryption function is an involution. This unwanted behavior can now be explained by Proposition 2. Indeed, the bit permutation π in the above coupling mapping is only composed of cycles of length 2.

Impact of related-key distinguishers

The class of ciphers considered here has trivial related-key distinguishers. However, any class of related-key distinguishers for a reflection cipher involving both E k and its inverse, i.e., E P (k) , provides a distinguisher in the single-key setting. So, at least in scenarios where an attacker can be assumed to have access to both the encryption and the decryption operations, the existence of some related-key distinguisher must be investigated with care. There are at least two different approaches (and a trade-off between both):

-The coupling mapping P can be designed in such a way that the relation between k and P (k) is so complicated that any good related-key distinguisher can only be exploited for a very small number of keys. For instance, if almost all values k+P (k) differ when k varies, then any good related-key differential distinguisher (involving keys which differ by a constant) defines very few weak keys only.

-The coupling mapping P can be designed in a way that, for any k, a distinguisher involving both k and P (k) is unlikely to exist. For instance, choosing P (x) = x + α as in [START_REF] Borghoff | PRINCE -A Low-latency Block Cipher for Pervasive Computing Applications[END_REF], where α is a randomly chosen constant with a high Hamming weight, follows this approach. One may expect that there are no related-key distinguishers involving two keys with difference α, but, on the other hand, if such a distinguisher exists, then all keys will be weak.

Related-key differential distinguishers

It is well-known that a given block cipher cannot be secure against all types of related-key distinguishers. Indeed, there exist some sets of related-key derivation functions which allow to build a distinguisher with overwhelming advantage for any cipher [START_REF] Bellare | A Theoretical Treatment of Related-Key Attacks: RKA-PRPs, RKA-PRFs, and Applications[END_REF][START_REF] Harris | Critique of the Related-Key Attack Concept[END_REF][START_REF] Albrecht | On Cipher-Dependent Related-Key Attacks in the Ideal-Cipher Model[END_REF]. Here, we focus on the set of additions with a constant, which is one of the most relevant and sound families of related-key derivation functions [START_REF] Bellare | A Theoretical Treatment of Related-Key Attacks: RKA-PRPs, RKA-PRFs, and Applications[END_REF]. In other words, we investigate the existence of related-key distinguishers involving keys k and k = k + δ.

In this context, the mapping φ : x → P (x) + x + P (0) and the set Im(φ) = {x + P (x) + P (0), x ∈ F κ 2 } play an important role. Let N denote the size of this set. We have N ≤ 2 κ-1 since both x and P (x) have the same image under φ and are distinct because P has no fixed points. Then, φ defines an equivalence relation on the keys, namely the key space is partitioned into N equivalence classes K δ := {k : k + P (k) = δ}. Each of these classes corresponds to a potential class of weak keys that may result from the existence of a related-key distinguisher involving keys k and k = k + δ. All these key classes have size at least 2, and their average size is 2 κ /N . So, there is a trade-off between two quantities: the maximal size of a key class K δ and the minimum weight of the set {δ : K δ = ∅}. In the following, the relation between these two quantities is investigated from a theoretical point of view, first when P has degree 1, and then for some particular nonlinear mappings. Later, in Section 4, some concrete constructions of key-alternating reflection ciphers will be presented in which the minimum weight of {δ : K δ = ∅} affects the existence of efficient related-key distinguishers.

When P is affine

When P has degree 1, all non-empty key classes K δ are affine subspaces of F κ 2 of the same dimension p, since they are all cosets of Ker φ. Therefore, the minimal possible dimension for the key classes is (κ + 1)/2 (see Prop. 1). Moreover, the second quantity, the minimum weight of {x + P (x)} = P (0) + Im φ is equal to the Hamming distance between P (0) and Im φ, where P (0) ∈ Im φ. The highest possible value for d H (P (0), Im φ) then corresponds to the covering radius of Im φ, which is a linear code of length κ and dimension (κp). And, it is well-known that the covering radius of a linear code of length κ and dimension (κp) does not exceed κ -(κp) = p, see for example Proposition 2 in [START_REF] Cohen | Covering Radius -Survey and Recent Results[END_REF]. We then deduce the following result.

Proposition 3. Let P be an affine involution over F κ 2 without fixed points. Let p denote the dimension of the non-empty sets K δ = {x : x + P (x) = δ}. Then, p > κ/2, and min

x∈F κ 2 wt(x + P (x)) ≤ p .
Moreover, the affine involutions for which the previous upper-bound is tight can be characterized. if and only if, up to a permutation of the coordinates of x and of P (x),

P (x) = x + xM + P (0) with M =   ZB ZBZ 0 B BZ 0 C CZ 0   where Z is a (κ -p) × t matrix, 0 ≤ t ≤ κ -p, having t distinct nonzero rows, all of weight 1, B is a t × (κ -p) matrix, C is a (p -t) × (κ -p) matrix such that rank M = κ -p, 1B + 1C = 0 and P (0) = u, Zu, 1 with u ∈ F κ-p 2
, and 1 denotes the all-one word.

Example 1. Let κ and p be two integers with p > κ/2. We consider the mappings defined in the previous proposition with parameter t = 0. Then, we have

M = 0 0 C 0
where C is a p × (κp) matrix of full rank and with columns of even Hamming weight (i.e., 1C = 0). Let γ i be the i-th column of C. Then, up to a permutation of the coordinates of x and z, P is defined by P (x 1 , . . . , x κ ) = (z 1 , . . . , z κ ) with

z i = x i + γ i • (x κ-p+1 , . . . , x κ ) + α i for 1 ≤ i ≤ κ -p x i + 1 for κ -p < i ≤ κ ,
where α i ∈ F 2 for 1 ≤ i ≤ κp. It can be checked that, for any linearly independent vectors γ i ∈ F p 2 , 1 ≤ i ≤ κp, of even Hamming weight, this mapping is an involution, that all non-empty sets {x : x + P (x) = δ} have dimension p and all elements x + P (x) have Hamming weight at least p.

Coupling mappings based on bit permutations. In the particular case where the coupling mapping is defined by P (k) = kM + α, where M is a permutation matrix, we can show that the bound of Prop. 3 is not tight. However, we can precisely determine the minimal (and maximal) weight of {k+P (k), k ∈ F κ 2 }.

Proposition 5. Let π be an involution of {1, . . . , κ} with f ≥ 1 fixed points and M the corresponding κ × κ permutation matrix. Let α ∈ Ker(M + Id). Then,

∀k ∈ F κ 2 , wt(α F P ) ≤ wt(k + kM + α) ≤ κ -f + wt(α F P )
where α F P denotes the f -bit binary word equal to the restriction of α to the coordinates corresponding to the fixed points of π.

Then, when k → kM is a bit permutation with f ≥ 1 fixed points, all key classes have size 2 κ+f 2 , and the minimum weight of k + kM + α is equal to wt(α F P ) ≤ f . Therefore, the bound of Proposition 3 is not tight (except when π = Id and α = 1): the optimal trade-off between the two quantities cannot be achieved by bit permutations. However, the values of the two quantities obtained for some bit permutations may be considered as reasonable when a lightweight coupling mapping is required.

When P is nonlinear

If we want to reduce the size of all key classes to guarantee that any related-key distinguisher defines a very few weak keys only, we need to choose a nonlinear coupling mapping since the key classes for an affine coupling mapping have size at least 2 κ+1 2 . We then study the trade-offs between the maximal size of a key class and the minimal weight of (k + P (k)) achieved by some particular families of nonlinear coupling mappings. As we will see, some of these mappings are of theoretical interest only since their implementation cost is too high for a practical use within a lightweight block cipher. However, investigating nonlinear permutations permits to obtain a better idea of the bounds that can be in general achieved by coupling permutations.

Inverse mapping. The inverse mapping over the field with 2 κ elements provides a nice example of an involution where the size of the key classes is minimal. However, it has two fixed points (0 and 1) which must be excluded. Proposition 6. Let ψ be any isomorphism from F 2 κ into F κ 2 , and x 0 = ψ(1). Let P be the permutation of F κ 2 defined by

P (x) = ψ ψ -1 (x) 2 κ -2 .
Then, P is an involution without fixed points over F κ 2 \{0, x 0 }, and for any δ, the set K δ = {x : x + P (x) = δ} has size either 0 or 2. Moreover, for any κ ≥ 5, there exists some ψ such that

min x =0,x0 wt(x + P (x)) ≥ 2 .
Proof. P is an involution since (2 κ -2) 2 ≡ 1 mod (2 κ -1) (i.e., the inverse function is an involution). Moreover, any nonzero fixed point x of P should be such that y = ψ -1 (x) satisfies y 2 κ -2 = y which is equivalent to y 2 = 1. This equation does not have any solution when y ∈ F 2 (i.e., when x ∈ {0, x 0 }).

Similarly, any nonzero element x in the key class K δ = {x : x + P (x) = δ} should be such that y = ψ -1 (x) satisfies

y + y 2 κ -2 = ψ -1 (δ) .
Since y = 0, this is equivalent to y 2 + δ y + 1 = 0 where δ = ψ -1 (δ). Moreover, δ is nonzero because the class {x : x + P (x) = 0} is equal to {0, x 0 }. Then, this quadratic equation has 2 solutions if Tr(δ -1 ) = 0, and no solution otherwise. It follows that the minimal weight of x + P (x) when x ∈ F κ 2 \{0, x 0 } corresponds to the minimum weight of δ = 0 such that Tr( ψ -1 (δ)

-1 ) = 0. Then, we have that this minimum weight is at least 2 if and only if all vectors x ∈ F κ 2 of weight 1 are such that Tr( ψ -1 (x)

-1 ) = 1. An equivalent condition is that there exists a basis {b 1 , . . . , b κ } of F 2 κ such that Tr(b -1 i ) = 1 for all 1 ≤ i ≤ κ. In particular, if {b 1 , . . . , b κ } is a normal basis, i.e., b i = b 2 i-1 , then Tr(b -1 i ) takes the same value for all elements in the basis. Therefore, any normal basis {b, . . . , b 2 κ-1 } of F 2 κ such that Tr(b -1 ) = 1 leads to an isomorphism ψ for which the minimal weight of x + P (x) is at least two.

For any element α ∈ F * 2 κ , Tr(α) is the sum of all conjugates of α. Since the minimal polynomial m α of α is the product of all (X -α 2 i ), it is clear that Tr(α) is the coefficient of the monomial of degree (deg(m α ) -1) in m α . Moreover, the minimal polynomial of α -1 is the reciprocal of the minimal polynomial of α. We then deduce that Tr(α -1 ) is the coefficient of the monomial of degree 1 in m α . The existence of a normal basis satisfying the requirements is equivalent to the existence of a normal element b in F 2 κ such that the coefficient of degree 1 of its minimal polynomial is equal to 1. It has been proved in [START_REF] Fan | Primitive Normal Polynomials with the Specified Last Two Coefficients[END_REF] (see also [START_REF] Huczynska | Existence Results for Finite Field Polynomials with Specified Properties[END_REF]Theorem 2.20]) that such an element always exists for κ ≥ 5.

A general construction. Another technique consists in constructing an appropriate nonlinear involution by

P = S • M • S -1
where M is an affine involution without fixed points as described in the previous section, and S is a nonlinear permutation with good differential properties. More precisely, we focus on the differential uniformity of S, which is the maximal number of solutions x ∈ F κ Example 2. We choose

S(x) = ψ ψ -1 (x) 2 κ -2
where ψ is the isomorphism from F 2 κ into F κ 2 defined by a normal basis {a, a 2 , . . . , a 2 κ-1 } with Tr(a -1 ) = 1. Such a basis exists for any κ ≥ 5 as detailed in the proof of Proposition 6. For x 0 = ψ(1),

P (x) = S (S(x) + x 0 )
is an involution over F κ 2 without fixed points and satisfies max

δ∈F κ 2 #{x : x + P (x) = δ} = 2 if κ is odd 4 if κ is even and min x∈F κ 2 wt(x + P (x)) ≥ 2 .
The fact that P is an involution without fixed points and the maximal size of a key class are derived from the previous proposition, since the inverse function over F 2 κ is differentially 2-uniform (resp. 4-uniform) if κ is odd (resp. even) [START_REF] Nyberg | Differentially Uniform Mappings For Cryptography[END_REF]. Moreover, this bound is tight since there is a one-to-one correspondence between the elements in {x : x+P (x) = x 0 } and the solutions z of (z+1

) 2 κ -2 +z 2 κ -2 = 1.
The number of solutions of this last equation is 2 if κ is odd and 4 if κ is even. Also, the minimal weight of (x + P (x)) is the minimal weight of any element in the image set of the derivative D x0 S. Then, it corresponds to the minimal weight of ψ(y) for y ∈ {(z + 1) 2 κ -2 + z 2 κ -2 , z ∈ F 2 κ }. By using the same technique as in the proof of Proposition 6, we get that

{(z + 1) 2 κ -2 + z 2 κ -2 } = {x ∈ F 2 κ : Tr(x -1 ) = 0} .
By definition of ψ, the elements δ of weight 1 in F κ 2 satisfy y = ψ -1 (δ) = a 2 i for some 0 ≤ i ≤ κ -1, implying that Tr(y -1 ) = Tr(a -1 ) = 1. Therefore, these elements y = ψ -1 (δ) do not belong to {(z + 1) 2 κ -2 + z 2 κ -2 , z ∈ F 2 κ }, which equivalently means that the elements δ of weight 1 do not belong to the image set of the derivative D x0 S.

Some variants of PRINCE

We will see now how the coupling permutations investigated in the previous section can be used for constructing some variants of the block cipher PRINCE. Indeed, the design of PRINCE raised several questions. One such question is related to the key size of the cipher. In particular, the coupling mapping chosen in PRINCE limits the key size to the block size, which is too small in most lightweight ciphers. The approach used in PRINCE for doubling the key length consists in using a whitening key which is independent from the key of the inner cipher. However, this solution is not satisfactory because the resulting security level does not correspond to what is usually expected from the key size [START_REF] Dinur | Cryptanalytic Time-Memory-Data Tradeoffs for FX-Constructions with Applications to PRINCE and PRIDE[END_REF]. We then analyze alternative solutions for constructing a key-alternating reflection cipher whose key is twice as long as the block size.

Recall that the structure used in PRINCE is as follows: the cipher is composed of a number of round permutations, R 1 , . . . , R r (and their inverses) along with an unkeyed involution M in the middle of the structure. Now, we construct coupling permutations for reflection ciphers following this structure for the special situation of an n-bit block cipher with a 2n-bit key.

Construction 1. We split the 2n-bit master key into two halves k = (k 0 , k 1 ) and use as a coupling mapping the permutation

P (k 0 , k 1 ) = (F 0 (k 0 , k 1 ), F 1 (k 0 , k 1 )) .
In other words, F 0 and F 1 denote the restrictions of P to the first and second half of the output respectively. Then, we define the subkeys as follows:

R 1 m R 2 k 1 R r M R -1 r R -1 2 R -1 1 c k 0 k 0 k 1 F 1 (k 0 , k 1 ) F 0 (k 0 , k 1 ) F 0 (k 0 , k 1 ) F 1 (k 0 , k 1 )
Fig. 1. Construction 1: a reflection cipher with 2n-bit key and n-bit block with coupling mapping P (k0, k1) = (F0(k0, k1), F1(k0, k1)).

for 0 ≤ i ≤ r, k i = k 0 if i is even and

k i = k 1 if i is odd; -for r + 1 ≤ i ≤ 2r + 1, k i = F 1 (k) if i is even and k i = F 0 (k) if i is odd.
An important security parameter of this construction is the number of information bits corresponding to the first and the last-round keys: this is the number of key bits which need to be guessed in order to peel off one round at both ends. Then, a strategy for attacking the (2r + 1)-round cipher consists in guessing the first and last round keys and in attacking the (2r -1) middle rounds in order to recover the remaining key bits. Therefore, if the amount of key guessing corresponding to the extremal rounds is much smaller than the overall key size, we must ensure that attacking (2r -1) rounds is infeasible. Such a situation usually imposes to increase the number of rounds compared to the n-bit key variant, which is highly unsuitable in the context of unrolled implementations, for instance for low-latency ciphers. An example of such a situation is the lightweight cipher LED-128 for which the first and last round keys are similar and cover half of the key size. For this reason, LED-128 has 16 more rounds (i.e., four steps) than its 64-bit variant, as explained by the designers [START_REF] Guo | The LED Block Cipher[END_REF]Section 3.1].

We need therefore to determine the number of different values of the pair (k 0 , F 0 (k 0 , k 1 )), when the vector (k 0 , k 1 ) takes all the possible 2 2n values. This number corresponds to

k0∈F n 2 # Im(F 0 (k 0 , .))
where F 0 (k 0 , .) is the mapping k 1 → F 0 (k 0 , k 1 ). In particular, the amount of key-guessing for this pair of subkeys is maximal and equals to 2n bits if and only if k 1 → F 0 (k 0 , k 1 ) is a permutation of F n 2 for every possible k 0 ∈ F n 2 . At the other extreme, the amount of key-guessing is only n bits if and only if F 0 is independent from k 1 . This situation occurs for instance when the coupling mapping P operates on the two halves of its input separately: P (k 0 , k 1 ) = (P 0 (k 0 ), P 1 (k 1 )), where P 0 and P 1 are two permutations of F n 2 .

Construction 2. If P (k 0 , k 1 ) = (P 0 (k 0 ), P 1 (k 1 )), the amount of key-guessing for the first and last round keys corresponds to n bits only. But, the previous construction can be slightly modified in order to increase this number: the first subkey is replaced by (k 0 + k 1 ) and the last one is now replaced by (P 0 (k 0 ) + P 1 (k 1 )), as depicted below.

R 1 m R 2 k 1 R r M R -1 r R -1 2 R -1 1 c k 0 k 0 ⊕ k 1 k 1 P 1 (k 1 ) P 0 (k 0 ) ⊕ P 1 (k 1 ) P 0 (k 0 ) P 1 (k 1 )
Fig. 2. Construction 2: a reflection cipher with 2n-bit key and n-bit block with coupling mapping P (k0, k1) = (P0(k0), P1(k1)).

Then, we can prove that this second construction increases the amount of key-guessing, which is strictly greater than n bits in the following two cases: if P 0 = P 1 and P 0 is nonlinear, or if P 0 and P 1 are two distinct affine permutations. This is detailed in the following two propositions. Proposition 8. Let P 0 be an involution of F n 2 . Then, the number of different values of the pair (k 0 + k 1 , P 0 (k 0 ) + P 0 (k 1 )), when (k 0 , k 1 ) takes all the possible 2 2n values is

a∈F n 2 # Im(D a P 0 ) ,
where D a P 0 : x → P 0 (x + a) + P 0 (x). This number is strictly greater than 2 n if and only if deg P 0 > 1.

Proof. Let a = k 0 + k 1 . Then, we need to determine the number of different values of (a, P 0 (k 1 + a) + P 0 (k 1 )) = (a, D a P 0 (k 1 )) where (a, k 1 ) takes all possible values in F 2n 2 . For each a ∈ F n 2 , the number of values taken by D a P 0 (k 1 ) when k 1 varies is the cardinality of the image set of D a P 0 . Moreover, this number equals 2 n if and only if each D a P 0 is a constant function. It is well-known that a function having all its derivatives constant is a function of degree at most 1.

When both P 0 and P 1 are affine but distinct, the amount of key-guessing is given by the following proposition.

Proposition 9. Let P 0 and P 1 be two affine involutions of F n 2 . Then, the number of different values of the pair (k 0 + k 1 , P 0 (k 0 ) + P 1 (k 1 )), when (k 0 , k 1 ) takes all the possible 2 2n values is 2 n+ν where ν = rank(P 0 • P 1 + Id) = rank(P 0 + P 1 ) .

Proof. Obviously, the number of different values of the quantity (k 0 +k 1 , P 0 (k 0 )+ P 1 (k 1 )) is equal to the number of different values of its linear part, that is of (k

0 + k 1 , L 0 (k 0 ) + L 1 (k 1 )) where L i (x) = P i (x) + P i (0). Let a = k 0 + k 1 . The previous couple can then be written as (a, L 0 (a + k 1 ) + L 1 (k 1 )) = (a, L 0 (a) + (L 0 + L 1 )(k 1 )
). The number of values taken by this pair then corresponds to 2 n+ν where ν = rank(P 0 + P 1 ). Equivalently, it corresponds to the rank of k 1 → P 0 (P 0 (k 1 ) + P 1 (k 1 )) = k 1 + P 0 (P 1 (k 1 )) .

We now consider the particular case where the linear parts of P 0 and P 1 are defined by two bit permutations π 0 and π 1 . In order to guarantee that P is an involution, we need π 0 and π 1 to be involutions (cf. Corollary 2). Then, the amount of key-guessing is related to the number of fixed points of π 0 and of π 1 , as stated in the following lemma.

Lemma 1. Let π 0 and π 1 be two involutions of {1, . . . , n} and L 0 and L 1 be the corresponding permutations of F n 2 . Then, the rank of L 0 • L 1 + Id is upper bounded by n -(f 0 + f 1 )/2 where f i is the number of fixed points of π i .

Thus, in order to ensure a high cost for guessing the first and the last round keys, the number of fixed points of π 0 and of π 1 has to be minimal. However, given Proposition 5, this comes at the price that (k + P (k)) may have a low Hamming weight.

Based on the previous results, we can then define some variants of PRINCE which differ from their key schedule only. All these variants operate on 64-bit inputs with a 128-bit key, and follow Construction 2 with 5 rounds R i , 1 ≤ i ≤ 5, an unkeyed middle round M , and then the inverses of the five R i (see Figures 1 and 2). We define three different coupling mappings: a nonlinear permutation of the form P (k 0 , k 1 ) = (P 0 (k 0 ), P 0 (k 1 )) where P 0 is defined by the construction presented in Section 3.3; an affine coupling mapping of the form P (k 0 , k 1 ) = (P 0 (k 0 ), P 1 (k 1 )) where both affine involutions P 0 and P 1 are obtained as in Example 1 in Section 3; a coupling mapping based on a bit permutation. The respective properties of these three key-schedules are given in Table 1. The variant with the nonlinear key schedule has much smaller key classes but this variant is not realistic when a low-cost implementation is required. The two other key schedules can be implemented with very few resources since they correspond to very sparse affine permutations over F 64 2 . In particular, the key schedule based on bit permutations appears to be very efficient. These two key schedules then provide interesting variants of PRINCE at a marginal implementation overhead. In particular, their security level is not limited by the generic attack against the F X-construction.

Conclusion

In this work, we tried to answer some open questions related to the design of a family of ciphers, for which the set of encryption functions is identical to the set of decryption functions. In particular, we focused on the design of what we called the coupling permutation. A coupling permutation P applied to a master key k, makes, in our context, encryption with P (k) identical to decryption with k.

Questions on the design of the coupling permutation of reflection block ciphers were raised after the design of the lightweight block cipher PRINCE. Indeed, in PRINCE, the coupling permutation chosen by the designers doesn't seem optimal and its impact on the cipher's security is questioned. After presenting some general properties of coupling permutations, we analyzed the case of PRINCE and came up with some alternative key schedules for this cipher. Each key schedule presents a different trade-off of the studied security properties and the choice of which one to choose should depend on the security requirements settled by the designers and the target implementation cost.

Proposition 4 .

 4 Let κ and p be two integers, κ < 2p. The permutation P is an affine involution over F κ 2 such that min x∈F κ 2 wt(x + P (x)) = p and dim{x : x + P (x) = δ} = p, ∀δ ∈ Im(P + Id)

2Proposition 7 .κ 2 #κ 2 # 2 y

 7222 for an equation S(x + a) + S(x) = b, a, b ∈ F κ 2 and a = 0[START_REF] Nyberg | Differentially Uniform Mappings For Cryptography[END_REF]. Let M be an affine involution of F κ 2 without fixed points with dim Im(M + Id) = p. Let S be a permutation of F κ 2 with differential uniformity δ(S). Then, P = S • M • S -1 is an involution without fixed points and satisfiesmax δ∈F {x : x + P (x) = δ} ≤ 2 p δ(S)and min x∈F κ 2 wt(x + P (x)) ≥ min wt(x), x ∈ a∈Im(M +Id) Im(D a S) , where D a S : x → S(x + a) + S(x). Most notably, if M (x) = x + α for some α ∈ F κ 2 \{0}, we have max δ∈F {x : x+P (x) = δ} ≤ δ(S) and min x∈F κ 2 wt(x+P (x)) ≥ min wt(x), x ∈ Im(D α S) . Proof. It is clear that P is an involution without fixed points if and only if M is an involution without fixed points. Moreover, there is a one-to-one correspondence between both sets {x : x + P (x) = δ} and {y : S(y) + S • M (y) = δ}. The set {y : S(y) + S • M (y) = δ} is included within the set a∈F κ : (M + Id)(y) = a and S(y) + S(y + a) = δ . Then, we directly deduce the bounds on the cardinality of {y : S(y)+S •M (y) = δ}, and on the minimal weight of (S(y) + S • M (y)).

Table 1 .

 1 Summary of the studied quantities for the proposed alternative key-schedules.

		PRINCE nonlinear affine (p = 33) bit permutation
	key-guessing	128	119.9	126	112
	max size of K δ	2 128	2 32	2 66	2 80
	minimum number of active Sboxes		≥ 24	≥ 72	≥ 48


Anne Canteaut
email: anne.canteaut@inria.fr

Joëlle Roué
email: joelle.roue@inria.fr

Differential attacks against SPN: a thorough analysis

Keywords: . Differential cryptanalysis, linear layer, MDS codes, AES

published or not. The documents may come

Introduction

Since the design of the AES and the seminal related work [START_REF] Daemen | The Design of Rijndael: AES -The Advanced Encryption Standard[END_REF], it is known that the mixing layer which aims at providing diffusion within a block cipher must have a high differential branch number [START_REF] Daemen | Cipher and hash function design strategies based on linear and differential cryptanalysis[END_REF]. This quantity corresponds to the smallest number of active Sboxes within a two-round differential characteristic. Indeed, for a given choice of the Sbox, the maximal probability for an r-round differential characteristic decreases when the number of active Sboxes within r rounds increases. For this reason, many security analyses focus on the minimal number of active Sboxes within r consecutive rounds when r varies, not only for AES-like designs but for some other types of ciphers, including Present [START_REF] Bogdanov | PRESENT: an ultra-lightweight block cipher[END_REF] or Feistel ciphers [START_REF] Shibutani | Towards the optimality of feistel ciphers with substitution-permutation functions[END_REF]. This approach is rather natural since, in differential attacks, cryptanalysts usually start by searching for a differential characteristic with the fewest possible active Sboxes. Therefore, the construction of MDS diffusion layers with an efficient implementation has been investigated by several authors, e.g., [START_REF] Sajadieh | Efficient recursive diffusion layers for block ciphers and hash functions[END_REF][START_REF] Berger | Construction of recursive MDS diffusion layers from Gabidulin codes[END_REF][START_REF] Augot | Direct Construction of Recursive MDS Diffusion Layers using Shortened BCH Codes[END_REF].

However, the complexity of a differential attack depends on the probability of a differential, i.e., on the sum of the probabilities of all characteristics starting by a given input difference and ending by a given output difference. And, within two consecutive rounds of an SPN (Substitution-Permutation Networks), the number of constituent characteristics increases with the Hamming weight of the differential. Then, the maximum expected probability (MEDP) for a tworound differential may result from a differential which contains a huge number of characteristics each with a low but nonzero probability, rather than from a differential which contains a few characteristics having a high probability. In other words, for two rounds of an SPN, there is a priori no reason to believe that the best differential corresponds to a differential with the lowest number of active Sboxes. However, it appears to be the case for most known examples, including the AES [START_REF] Keliher | Exact maximum expected differential and linear probability for two-round Advanced Encryption Standard[END_REF]. This aim of this paper is then to determine whether this phenomenon is more general and whether there are some general situations where it can be proved that the two-round MEDP is achieved by a differential with the smallest number of active Sboxes.

Our contributions. After recalling the main definitions in Section 2, we show in Section 3 that the choice of the MDS diffusion layer may affect the tworound MEDP even if the Sbox is fixed. In particular, we show that the form of the minimum-weight codewords plays an important role. Also, we provide some upper bound on the number of characteristics with nonzero probability within a given differential for an MDS linear layer. Section 4 focuses on the case where the Sbox is APN: in this case, it appears that the two-round MEDP is usually achieved by minimum-weight differentials. We prove this result for any APN Sbox over F 8 and any F 8 -linear MDS diffusion layer. Finally, Section 5 exploits the previous analysis and exhibits some MDS mixing layers for which the maximum EDP over two rounds is achieved by a differential in which the number of active Sboxes exceeds the branch number.

2 Differential attacks against Substitution-Permutation Networks

Substitution-Permutation Networks

One of the most widely-used constructions for iterated block ciphers is the socalled key-alternating construction [START_REF] Daemen | Cipher and hash function design strategies based on linear and differential cryptanalysis[END_REF][START_REF] Daemen | The Wide Trail Design Strategy[END_REF], which consists of an alternation of key-independent (usually similar) permutations and of round-key additions. The round permutation is usually composed of a nonlinear substitution function Sub which provides confusion, and of a linear permutation which provides diffusion.

In order to reduce the implementation cost of the substitution layer, which is usually the most expensive part of the cipher in terms of circuit complexity, a usual choice for Sub consists in concatenating several copies of a permutation S which operates on a much smaller alphabet. In the whole paper, we will concentrate on such block ciphers, and use the following notation to describe the corresponding round permutation.

Definition 1. Let m and t be two positive integers. Let S be a permutation of F m 2 and M be a linear permutation of F mt 2 . Then, SPN(m, t, S, M ) denotes any substitution-permutation network defined over F mt 2 whose substitution function consists of the concatenation of t copies of S and whose diffusion function corresponds to M .

For instance, up to a linear transformation, two rounds of the AES can be seen as the concatenation of four similar superboxes [START_REF] Daemen | Understanding Two-Round Differentials in AES[END_REF]. The superbox, depicted on Fig. 1, is linearly equivalent to a two-round permutation of the form SPN(8, 4, S, M ) where the AES Sbox S corresponds to the composition of the inversion in F 2 8 with an affine permutation A. More precisely, S(x 254 where ϕ is the isomorphism from F 8 2 into F 2 8 defined by the basis {1, α, α 2 , . . . , α 7 } with α a root of X 8 + X 4 + X 3 + X + 1.

) = A • ϕ -1 ϕ(x)

Differential cryptanalysis

Differential [START_REF] Biham | Differential cryptanalysis of DES-like cryptosystems[END_REF] cryptanalysis is one of the most prominent statistical attacks. The complexity of differential attacks depends critically on the distribution over the keys k of the probability of the differentials (a, b), i.e.,

DP(a, b) = Pr X [E k (X) + E k (X + a) = b]
where E k corresponds to the (possibly round-reduced) encryption function under key k. Since computing the whole distribution of the probability of a differential is a very difficult task, cryptanalysts usually focus on its expectation.

Definition 2. Let (E k ) k∈F κ
2 be an r-round iterated cipher with key-size κ. Then, the expected probability of an r-round differential (a, b) is

EDP E r (a, b) = 2 -κ k∈F κ 2 Pr X [E k (X) + E k (X + a) = b] .
The maximum expected differential probability for r rounds is

MEDP E r = max a =0,b EDP E r (a, b) .
The index in MEDP E r will be omitted when the number of rounds is not specified.

Expected probability of a differential characteristic

Since computing the MEDP for most ciphers, even for a small number of rounds, is very difficult, most works focus on the expected probability of a differential characteristic.

Definition 3. An r-round differential characteristic Ω is a collection of (r + 1) differences, Ω = (a 0 , a 1 , . . . , a r ) where a i corresponds to the difference obtained after the i-th round when encrypting two inputs which differ from a 0 . The expected probability of the characteristic Ω is then defined as

EDCP r (Ω) = 2 -κ k∈F κ 2 Pr X0 [X 1 + X 1 = a 1 ; . . . ; X r + X r = a r | X 0 + X 0 = a 0 ] ,
where X i (resp. X i ) denotes the image of X 0 (resp. of X 0 ) after the i-th round of E k .

We here use the specific notation EDCP for the expected probability of a characteristic in order to avoid confusion between differentials and characteristics.

A simple upper-bound on the expected probability of 2-round characteristics can be derived from the differential branch number of the linear layer and from the differential uniformity of the Sbox, in the sense of the following definition.

Definition 4 (Differential uniformity). Let S be a function from F m 2 into F m 2 . For any a and b in F m 2 , we define

δ S (a, b) = #{x ∈ F m 2 , S(x + a) + S(x) = b} . The multi-set {δ S (a, b), a, b ∈ F m 2 } is the differential spectrum of S and its maximum ∆(S) = max a =0,b δ S (a, b) is the differential uniformity of S.
Then, for any two-round characteristic Ω = (a, M (b), M (c)), the Markov assumption [START_REF] Lai | Markov ciphers and differential cryptanalysis[END_REF] implies that

EDCP 2 (Ω) = DP E 1 (a, M (b)) × DP E 1 (M (b), M (c)) = t i=1 DP S 1 (a i , b i ) t i=1 DP S 1 (M (b) i , c i ) . (1)
Let Supp(x) and wt(x) denote the support and the weight of a vector x ∈ F mt 2 seen as an element in (F m 2 ) t . Then, the previous equation shows that .

It then appears that the lowest possible value for the weight of a nonzero word of the form (b, M (b)) plays a major role in the resistance against differential attacks. This criterion on the diffusion layer of the cipher corresponds to the notion of differential branch number.

Definition 5 (Differential branch number [START_REF] Daemen | Cipher and hash function design strategies based on linear and differential cryptanalysis[END_REF]). Let M be a permutation of (F m 2 ) t . We associate to M the code C M of length 2t and size 2 t over F m 2 defined by

C M = {(c, M (c)), c ∈ (F m 2 ) t } .
The differential branch number of M is the minimum distance of the code C M .

The following upper bound on the expected probability of any 2-round differential characteristic then follows:

max Ω EDCP 2 (Ω) ≤ 2 -m ∆(S) d , (2)
where d is the differential branch number of the linear layer.

It is worth noticing that a similar notion is considered in the case of linear cryptanalysis. The linear branch number is then the minimum distance of the dual code C ⊥ M but this quantity is out of the scope of this paper. For this reason, in the following, branch number always refers to the differential branch number.

. From Singleton's bound, the highest possible value for the branch number of a permutation of (F m 2 ) t is (t + 1) and it corresponds to the case where the associated code C M is an MDS (maximum distance separable) code.

From characteristics to differentials

The problem with the previous result is that differential cryptanalysis exploits differentials and not characteristics since the differences obtained after each intermediate round do not matter in the attack. The probability of a differential (a, M (b)) then corresponds to the sum of the probabilities of all characteristics with input difference a and output difference M (b). Then, the relevant quantity for two rounds is the maximum of

EDP 2 (a, M (b)) = x∈F mt 2 EDCP E 2 (a, x, M (b)) .
Determining the expected probability of a differential, rather than focusing on a single characteristic, is difficult in general.

Expected probability of a 2-round differential

From Equation (1), any element x of (F m 2 ) t verifies

EDCP 2 (a, M (x), M (b)) = t i=1 DP S 1 (a i , x i ) t i=1 DP S 1 (M (x) i , b i ) .
If this probability is different from zero, we have that Supp(a) = Supp(x) and

Supp(M (x)) = Supp(b), implying that (x, M (x)) ∈ (F m 2 )
2t is a word of C M having the same support as (a, b). Moreover, by definition of the differential spectrum, DP S 1 (α, β) = 2 -m δ S (α, β). Thus, the two-round probability of a differential is

EDP 2 (a, M (b)) = 2 -mwt(a,b) c∈C M : Supp(c)=Supp(a,b)   i∈Supp(a) δ S (a i , c i )     j∈Supp(b) δ S (c t+j , b j )   (3)
A simple upper bound for the two-round MEDP can then be derived from the branch number of M and from the differential uniformity of the Sbox (see [START_REF] Hong | Provable Security against Differential and Linear Cryptanalysis for the SPN Structure[END_REF] and [12, Section B.2]):

MEDP 2 ≤ 2 -m ∆(S) t .
This result has then been refined in [START_REF] Chun | Differential and linear cryptanalysis for 2-round SPNs[END_REF][START_REF] Park | Improving the Upper Bound on the Maximum Differential and the Maximum Linear Hull Probability for SPN Structures and AES[END_REF][START_REF] Canteaut | On the behaviors of affine equivalent sboxes regarding differential and linear attacks[END_REF]. The bounds in [START_REF] Hong | Provable Security against Differential and Linear Cryptanalysis for the SPN Structure[END_REF][START_REF] Chun | Differential and linear cryptanalysis for 2-round SPNs[END_REF][START_REF] Park | Improving the Upper Bound on the Maximum Differential and the Maximum Linear Hull Probability for SPN Structures and AES[END_REF] are invariant under affine equivalence, i.e., their values are the same for two Sboxes S and S when there exist two affine permutations A 1 and A 2 such that S = A 1 •S•A 2 . However, the exact values of MEDP 2 may differ for Sboxes in the same equivalent class, and there can be a gap between these bounds and the exact value of MEDP 2 . In [START_REF] Canteaut | On the behaviors of affine equivalent sboxes regarding differential and linear attacks[END_REF], a new upper bound is introduced, that enhances the previously known bounds in the sense that it may vary when the Sbox is composed by an affine permutation. This new bound only applies when the diffusion layer M is linear over the field F 2 m , where m is the size of the Sbox, exactly as in the AES. In this case, the linear layer and the Sbox can be represented as functions over the field F 2 m and the representation does not change the MEDP. In particular, the choice of the isomorphism that identifies the vector space F m 2 with the finite field F 2 m has no influence on the differential properties of the cipher. For this reason, we use the following alternative notation to define an SPN with this representation. Definition 6. Let m and t be two positive integers. Let S be a permutation of F 2 m and M be a permutation of (F 2 m ) t which is linear over F 2 m . Then, we denote by SPN F (m, t, S, M) a substitution-permutation network defined over (F 2 m ) t whose substitution function consists of the concatenation of t copies of S and whose diffusion function corresponds to M.

When the Sbox is defined over F 2 m , we equivalently define the differential spectrum as follows. Let (α 0 , . . . , α m-1 ) be a basis of F 2 m , and ϕ the corresponding isomorphism from F m 2 into F 2 m . Let S be a mapping over F m 2 , and

S = ϕ•S•ϕ -1 . Then, for any (α, β) ∈ F 2 m , δ S F (α, β) = #{x ∈ F 2 m , S(x + α) + S(x) = β} = δ S (ϕ -1 (α), ϕ -1 (β)) .
As the differential properties of any SPN(m, t, S, M ) can be equivalently studied by considering the alternative representation SPN F (m, t, S, M) [START_REF] Daemen | Advanced Linear Cryptanalysis of Block and Stream Ciphers, chap[END_REF], this paper focuses on the representation of an SPN F in the field F 2 m . For the sake of clarity, all quantities related to the representation in the field F 2 m will be indexed by F , and all functions defined over F 2 m will be denoted by calligraphic letters.

The new bounds on MEDP 2 presented in [START_REF] Canteaut | On the behaviors of affine equivalent sboxes regarding differential and linear attacks[END_REF] are derived from the particular structure of the set formed by all codewords in C M having a given support, when M is linear over F 2 m . These bounds are expressed in terms of the following quantities. For any Sbox S over F 2 m with differential spectrum (δ F (a, b)) a,b∈F 2 m and any branch number d, we define for any µ ∈ F 2 m and any integer u > 0,

B u (µ) = max α,β,λ∈F * 2 m γ∈F * 2 m δ F (α, γ) u δ F (γλ + µ, β) (d-u) and B(µ) = max 1≤u<d B u (µ) .
In the rest of the paper, we will restrict ourselves to the case where the diffusion layer is linear over F 2 m and MDS (i.e., with branch number (t + 1)). We also assume that the well-known MDS conjecture [START_REF] Macwilliams | The Theory of Error-Correcting Codes[END_REF] is valid, i.e., in our context, that t ≤ 2 m-1 for m > 3 and t ≤ 3 for m = 2. For such MDS diffusion layers, Theorem 2 and Proposition 3 in [START_REF] Canteaut | On the behaviors of affine equivalent sboxes regarding differential and linear attacks[END_REF] can be expressed as follows.

Theorem 1. Let S be a permutation of F 2 m and t be any integer such that t ≤ 2 m-1 .

-For any F 2 m -linear diffusion layer M over F t 2 m with maximal branch number, the block cipher E of the form SPN F (m, t, S, M) satisfies

MEDP E 2 ≤ 2 -m(t+1) max µ∈F 2 m

B(µ)

.

-There exists an F 2 m -linear diffusion layer M over F t 2 m with maximal branch number such that

MEDP E 2 ≥ 2 -m(t+1) B(0) .
In most cases, the values of the two-round MEDP for two ciphers of the form SPN F (m, t, S, M 1 ) and SPN F (m, t, S, M 2 ) where M 1 and M 2 are different MDS linear layers differ. The minimum-weight codewords of C M have a large influence on this value, as shown in the following example.

Example 1. Let us study the two-round MEDP of the SPN with the same building blocks as the Prøst permutation, which is the core function of several AEADschemes submitted to the CAESAR competition [START_REF] Kavun | Prøst v1.1[END_REF]. It is worth noticing that the following results do not provide any direct information on the security of the Prøst permutation: indeed, we study the differential probabilities averaged over all keys while the key is fixed in the Prøst permutation. Two consecutive rounds of the Prøst permutation over F 16d 2 , d ≥ 1, can be seen as the parallel application of d copies of a superbox defined over F 16 . This superbox is of the form SPN(4, d, S, M ) where S is a 4-bit involution named SubRows and M corresponds the so-called MixSlices transformation. It has been shown in [START_REF] Canteaut | On the behaviors of affine equivalent sboxes regarding differential and linear attacks[END_REF] that MixSlices is linear over F 16 for some particular isomorphism between F 4 2 and F 16 . Then, Theorem 1 applies and we get that, for any F 16 -linear layer M, the block cipher E of the form SPN F (4, d, S, M) where S corresponds to the Prøst Sbox satisfies MEDP E 2 ≤ 2 -8 . But, when the diffusion layer corresponds to MixSlices, we have computed the exact value of the MEDP 2 and obtained that MEDP 2 = 3 × 2 -11 , which is smaller than the general upper bound.

However, since both lower and upper bounds in Theorem 1 are equal, we deduce that there exists another diffusion layer M such that

MEDP E 2 = 2 -8 .
An example of such a diffusion layer is

    α 2 + α + 1 α 3 + α α 3 + α + 1 1 α + 1 α 3 + α 2 + α α 2 + α + 1 1 α 2 + 1 α 3 + α 2 + 1 α 3 1 α 2 α 3 + α 2 α 3 + 1 1    
where α is a root of X 4 + X 3 + 1. Indeed, the set of codewords of the form {λ(0, 0, 0, 1, 1, 1, 1, 1), λ ∈ F * 16 } belongs to the code associated with this diffusion layer. Then, the differences a = (0, 0, 0, 1) and b = (1, 1, 1, 1) satisfy EDP 2 (a, M(b)) = 2 -8 .

Influence of the weight of the differential

The previous example shows that, in some cases, the form of the minimumweight codewords in C M plays an important role when determining the tworound MEDP. We observe from Equation (3) that these codewords are involved in the computation of EDP 2 (a, M(b)) when the weight of the corresponding pair (a, b) is equal to the branch number of M. We then call such a differential a minimum-weight differential. The role played by minimum-weight differentials appears in a more direct way when the Sbox S has the following additional property [8, Definition 7]. A mapping S of F 2 m is said to have multiplicativeinvariant derivatives if, for any x ∈ F * 2 m there exists a permutation

π x of F * 2 m such that δ F (α, xy) = δ F (π x (α), y), ∀y ∈ F * 2 m .
Power permutations, and more generally any function resulting from the composition on the right of a power permutation with an F 2 -linear permutation, has multiplicative-invariant derivatives. Another example of functions with multiplicative-invariant derivatives are the crooked permutations, which include all APN permutations of degree 2. When an Sbox has this property, the expression of B(µ) (including B(0)) simplifies but, more interestingly, we get some universal lower bound on MEDP 2 , i.e., which holds for any diffusion layer with maximal branch number. For instance, for all Sboxes S such that both S and S -1 have multiplicative-invariant derivatives, we obtain that, for any F 2 m -linear diffusion layer M with maximal branch number, the corresponding block cipher satisfies

2 -m(t+1) B(0) ≤ MEDP E 2 ≤ 2 -m(t+1) max µ∈F 2 m B(µ) . (4)
Moreover, MEDP E 2 = 2 -m(t+1) B(0) if and only if the maximum expected differential probability is achieved by a minimum-weight differential.

Since the probability of a characteristic decreases when the weight of the underlying differential increases, a natural question is to determine in which situations the two-round MEDP is achieved by a minimum-weight differential. This is an important information: computing the two-round MEDP for a given cipher becomes obviously much easier once it is known that only the minimumweight differentials need to be examined. Surprisingly enough, for all AES-like ciphers which have been investigated, the two-round MEDP is achieved by a minimum-weight differential. For instance, the bounds in [START_REF] Canteaut | On the behaviors of affine equivalent sboxes regarding differential and linear attacks[END_REF] applied to the AES Sbox show that for any F 2 8 -linear layer M, we have

53 × 2 -34 ≤ MEDP 2 ≤ 55.5 × 2 -34 , (5)
where the lower bound corresponds to some minimum-weight differentials. For the particular diffusion layer defined by MixColumns in the AES, the exact value of the two-round MEDP 2 computed by a pruning search algorithm [START_REF] Keliher | Exact maximum expected differential and linear probability for two-round Advanced Encryption Standard[END_REF], is MEDP 2 = 53 × 2 -34 . It then corresponds to the lower bound of [START_REF] Bogdanov | PRESENT: an ultra-lightweight block cipher[END_REF].

There also exist some SPN F for which the exact value of the two-round MEDP can be directly deduced from the bounds in [START_REF] Canteaut | On the behaviors of affine equivalent sboxes regarding differential and linear attacks[END_REF], for instance, when the Sbox S is an involution with multiplicative-invariant derivatives. In this case, the lower and upper bounds in (4) are equal and do not depend on the MDS diffusion layer. In other words, for any involution with multiplicative-invariant derivatives, the two-round MEDP is always achieved by a minimum-weight differential, for any choice of the MDS linear layer. This holds in particular for the so-called AES naive Sbox, i.e. the inversion in F 2 m , which satisfies these conditions.

A natural question then arises from these examples: does there exist any cipher of the form SPN F for which the two-round MEDP is not achieved by a minimum-weight differential? We now investigate this problem, and first exhibit some general families of ciphers for which this situation cannot occur.

Number of characteristics within a given 2-round differential

For the sake of simplicity, for any differential (a, M(b)), we denote by (a, c, M(b)) the corresponding characteristic where c is the codeword in C M defined by the concatenation of the input and output differences of the first diffusion layer. With this notation, we have

EDP 2 (a, M(b)) = c∈C M : Supp(c)=Supp(a,b) EDCP 2 (a, c, M(b)) .
In this differential, each characteristic having a nonzero probability is defined by a codeword in C M whose support is equal Supp(a, b). Therefore, we define the weight of the differential as the weight w = wt(a) + wt(b). Then, the number of characteristics within a given differential (a, M(b)) of weight w is defined by

A w (a, b) = #{c ∈ C M : Supp(c) = Supp(a, b) and EDCP 2 (a, c, M(b)) = 0} = #{c ∈ C M : Supp(c) = Supp(a, b), δ S F (a i , c i ) = 0, ∀i ∈ Supp(a) and δ S F (c t+j , b j ) = 0, ∀j ∈ Supp(b)} .
A first criterion to determine whether the two-round expected differential probability is maximized by a minimum-weight differential or not consists in estimating the number of characteristics involved in a differential having a given weight w. Since we only consider diffusion layers which are linear over F 2 m , the codewords in C M having a given support can be gathered in bundles as pointed out in [START_REF] Daemen | Understanding Two-Round Differentials in AES[END_REF]: if c belongs to C M , then the whole bundle P(c) = {γc, γ ∈ F * 2 m } is also included in C M . It follows that the number of codewords in C M having a given support is always divisible by (2 m -1). Moreover, for any pair (α, β) ∈ (F * 2 m ) 2 , the values δ S F (α, γβ), when γ varies in F * 2 m , correspond to a row of the difference table of S. Since these coefficients are all even and sum to 2 m , we deduce that, for any permutation S, at least 2 m-1 -1 coefficients among all (δ S F (α, γβ), γ ∈ F * 2 m ) vanish, with equality if and only if S is APN. It then follows that, for any c ∈ C M ,

#{c ∈ P(c) : EDCP 2 (a, c , M(b)) = 0} ≤ 2 m-1 .
Differentials of weight w = t + 1. Recall that we focus on the case where the diffusion layer has maximal branch number, i.e., where C M is MDS. It is well-known (e.g. [START_REF] Macwilliams | The Theory of Error-Correcting Codes[END_REF]Page 319]) that if C M is an MDS code of length 2t and dimension t over F 2 m , then for each support of size (t + 1), there exist exactly (2 m -1) codewords (i.e., one bundle) having this support. From the previous discussion, we deduce that, for any minimum-weight differential (a, b)

A t+1 (a, b) ≤ 2 m-1 .
Differentials of weight w = t + 2. We now provide a similar upper bound on the number of characteristics within a differential of weight (t + 2). Proposition 1. Let M be an F 2 m -linear MDS permutation of F t 2 m . Then, for any differential (a, b) of weight (t + 2), we have

A t+2 (a, b) ≤ 2 m-1 (2 m -(t + 1)) .
Proof. From the previous discussion, we only have to prove that, for any support I of size (t + 2) there exist exactly (2 m -(t + 1)) distinct bundles having I for support. Let J = {i 1 , . . . , i t-2 } be the set formed by the 2t -(t + 2) = t -2 coordinates which do not belong to I. The codewords whose support is included in I then correspond to the codewords which vanish on J. Using that any t coordinates of C M is an information set [20, Page 321], we deduce that there are exactly (2 2m -1) nonzero codewords whose support is included in I. Since we count the number of codewords whose support is equal to I, we need to remove the codewords of weight (t + 1) from the previous set. As previously mentioned, for any support of size (t + 1), there exists one bundle having this support. Since I contains (t + 2) subsets of size (t + 1), we need to remove (t + 2)(2 m -1) codewords from the previous set. It follows that the number of codewords having I for support is

2 2m -1 -(t + 2)(2 m -1) = (2 m -1)(2 m -(t + 1)) .
Therefore, C M contains exactly (2 m -(t + 1)) bundles having I for support, implying that

A t+2 (a, b) ≤ 2 m-1 (2 m -(t + 1)) .
Most notably, we deduce from this formula that, when t = 2 m-1 , A t+2 may be limited by the maximal value of A t+1 . Some application of this result will be detailed in the next section.

SPN with an APN Sbox

In this section, we focus on the block ciphers SPN F which use an APN Sbox. These ciphers are of particular interest in our context since the whole differential spectrum of the Sbox is known. It follows that, for any characteristic within a differential of weight w has probability either 0 or 2 -w(m-1) . Then, we deduce that the expected probability of a differential of weight w only depends on the value of A w (a, b):

EDP 2 (a, M(b)) = 2 -w(m-1) A w (a, b) .
It follows that there exists a differential (a, b) of weight (t + 2) whose probability is higher than the probability of any minimum-weight differential if and only if, for any (α, β) of weight (t + 1),

2 -(t+2)(m-1) A t+2 (a, b) ≥ 2 -(t+1)(m-1) A t+1 (α, β) or equivalently A t+2 (a, b) ≥ 2 m-1 A t+1 (α, β) .
From Proposition 1, we know that A t+2 (a, b) ≤ 2 m-1 (2 m -(t+1)), implying that this situation can only occur if all minimum-weight differentials (α, β) satisfy

A t+1 (α, β) ≤ (2 m -(t + 1)) . (6)
For given parameters m and t, we can then directly deduce that, if the number of characteristics in a minimum-weight differential exceeds some bound, then the two-round MEDP cannot be achieved by a differential of weight (t + 2).

APN Sboxes over F 8

We now show that, if S is an APN permutation over F 2 3 (i.e., m = 3), then the maximum EDP is always achieved by a minimum-weight differential. This result is mainly due to the particular properties of 3-bit APN permutations.

Properties of APN Sboxes over F 8 . Since a permutation of F 2 m has degree at most (m -1), all APN Sboxes over F 8 are quadratic, and their inverses are also quadratic. Therefore, they are crooked [START_REF] Bending | Crooked Functions, Bent Functions, and Distance Regular Graphs[END_REF][START_REF] Kyureghyan | Crooked maps in F2n[END_REF], i.e., for any nonzero a ∈ F 2 3 , the set {b ∈ F 2 3 : δ S F (a, b) = 2} is an affine hyperplane of F 2 3 . Furthermore, it is known that all these affine hyperplanes are distinct [7, Lemma 5]. Since the inverse S -1 is also a crooked permutation, the same property holds for the columns of the difference table of S: for any nonzero b, the set {a ∈ F 2 3 : δ S F (a, b) = 2} is an affine hyperplane and all these hyperplanes are distinct.

Minimum-weight differentials. From this algebraic structure, we deduce the maximal value of the expected differential probability of the minimum-weight differentials.

Proposition 2. Let S be an APN permutation of F 2 3 . For any integer t and any F 2 3 -linear MDS diffusion layer M over (F 2 3 ) t , the block cipher of the form

SPN F (3, t, S, M) satisfies max a =0, b wt(a,b)=t+1 EDP 2 (a, M(b)) = 2 -2t .
Proof. Let I = {i 1 , . . . , i t+1 } be a subset of {1, . . . , 2t} of size (t + 1). Our aim is to exhibit a pair (a, b) whose support equals I and such that A t+1 (a, b) = 4. Such a differential leads to the result since A t+1 (a, b) = 4 is the highest value we can have for a minimum-weight differential. Let c be a codeword in C M with Supp(c) = I since such a codeword always exists. Let us choose some nonzero element a i1 ∈ F 2 3 . Then, we consider the set H = {β : δ S F (a i1 , β) = 2}. Then H is an affine hyperplane. We now define

Γ = {c -1 i1 λ, λ ∈ H} .
Obviously, Γ is also an affine hyperplane. Then, the four codewords in the bundle of c, c = γc with γ ∈ Γ , satisfy

δ S F (a i1 , c i1 ) = δ S F (a i1 , λc -1 i1 c i1 ) = 2.
Moreover, for any position i j in I with i j ≤ t, the coordinates of these four codewords at position i j vary in the set c ij Γ which is an affine hyperplane. Therefore, there exists some a ij such that this set corresponds to {β : δ S F (a ij , β) = 2}. Similarly, for any position i j ∈ I with i j > t, there exists some b ij such that the affine hyperplane c ij Γ corresponds to {α : δ(α, b ij ) = 2}. For this choice of (a, b), we get that, by construction,

A t+1 (a, b) = 4 , implying that EDP 2 (a, M(b)) = 4 × 2 -2(t+1) = 2 -2t .
It is worth noticing that we have proved a more general result: for any bundle, we can find a pair (a, b) such that the corresponding differential includes four characteristics from this bundle having a nonzero probability. However, this does not enable us to determine the maximum EDP for higher-weight differentials since the involved codewords correspond to several bundles, and we cannot control the different bundles together.

Higher-weight differentials. Since C M is an MDS code over F 8 , we have that t is at most 4. Moreover, we deduce from ( 6) that the maximum two-round EDP cannot be achieved by a differential of weight (t + 2) when t = 4 since it would imply that all minimum-weight differentials would satisfy A t+1 (a, b) ≤ 3 while we have proved that A t+1 (a, b) can be equal to 4.

Then, we need to examine all linear MDS codes of length 2t and dimension t over F 8 for t ∈ {2, 3}. For each of these codes, we have computed the highest value of A t+2 (a, b) we can get for all (a, b) of weight (t + 2). Since the difference tables of all crooked Sboxes over F 8 have the same structure, the maximal value of A t+2 (a, b) over all (a, b) having a given support I corresponds to the largest set Γ of codewords c with support I such that, for each i ∈ I, c i for all c ∈ Γ belong to the same affine hyperplane.

For t = 2, the previous quantity has been computed for all [4, 2, 3]-codes over F 8 . For all of them, we get that the maximal value for A 4 (a, b) is equal to 8. We then deduce that

max a =0, b wt(a,b)=3 EDP 2 (a, M(b)) = 2 -4 and max x =0, y wt(x,y)=4 EDP 2 (x, M(y)) = 2 -8 × 8 = 2 -5 .
Then, the two-round MEDP is achieved by a minimum-weight differential only.

For t = 3, we have computed the highest possible value of A 5 (a, b) for all [START_REF] Brinkmann | On the classification of APN functions up to dimension five[END_REF][START_REF] Berger | Construction of recursive MDS diffusion layers from Gabidulin codes[END_REF][START_REF] Biham | Differential cryptanalysis of DES-like cryptosystems[END_REF]-codes over F 8 , and we have obtained that for all these codes, the maximal

A 5 (a, b) is 4, implying that max a =0, b wt(a,b)=4 EDP 2 (a, M(b)) = 2 -6 and max x =0, y wt(x,y)=5 EDP 2 (x, M(y)) = 2 -10 ×4 = 2 -8 .
Moreover, it can be checked that, for all these codes, the maximal A 6 (a, b) is 32, implying that

max x =0, y wt(x,y)=6 EDP 2 (x, M(y)) = 2 -12 × 32 = 2 -7 .
We then deduce the following result. Proposition 3. Let S be an APN permutation of F 2 3 . For any integer t and any F 2 3 -linear MDS diffusion layer M over (F 2 3 ) t , the block cipher of the form SPN F (3, t, S, M) satisfies

MEDP 2 = 2 -2t ,
and this value is achieved by some minimum-weight differentials only.

APN Sboxes over F 32

APN permutations over F 32 have been classified in [START_REF] Brinkmann | On the classification of APN functions up to dimension five[END_REF] up to equivalence. But since APN permutations over F 32 do not have the same algebraic structure as APN permutations over F 8 , each function from this classification has to be studied. Moreover, the number of MDS codes with these parameters is also much higher than in the previous case.

We have then computed the maximal value for A t+1 for several APN permutations and MDS permutations with t = 2, 3. For t = 2, we have always observed that the maximal A t+1 is at least 10. We should then find some differential of weight 4 with A 4 ≥ 10 × 2 5-1 = 160 to reach the same EDP than the best minimum-weight differential. However, the highest values we have observed for A 4 are between 83 and 92. In other words, the maximum EDP for a differential of weight 4 is slightly higher than half of the maximum EDP for a minimum-weight differential.

For t = 3, we have observed that the maximal A t+1 is at least 9. We should then find some differential of weight 5 with A 5 ≥ 9 × 2 5-1 = 144, while the highest values we have observed for A 5 lie between 54 and 60.

MEDP 2 can be tight for a differential of non-minimal weight

It seems that the number A w of characteristics having a nonzero probability in a differential of weight w > t + 1 cannot be large enough to achieve a tworound EDP higher than the one which can be obtained with minimal-weight differentials. However, in the previously studied cases, the highest probability of a minimal-weight characteristic is always equal to the maximal value (∆(S)/2 m ) t+1 . If the probability EDP 2 is minimized for any minimal-weight differential, that is, if the number A t+1 is small and the probabilities of the constituent characteristics are different from (∆(S)/2 m ) t+1 , it should be possible to have a differential of weight w > t + 1 which has a higher probability than all minimal-weight differentials.

5.1

Examples where MEDP 2 is tight for a differential of weight (t + 2)

Sboxes such that only a few entries in the difference table are equal to ∆(S) are a good choice to avoid the existence of characteristics with probability (∆(S)/2 m ) t+1 within any given minimum-weight differential. But for differentials of weight t + 2, the probability of a characteristic also needs to be high. An Sbox with 4 to 6 entries in the difference table equal to ∆(S) seems to be a good tradeoff, as shown in the following examples. Note that the Sboxes are defined over the vectorial space F m 2 while the diffusion layer is defined over the field F 2 m , as it is done in many concrete specifications (using the binary representation may be relevant to choose the Sbox, for instance in order to minimize the number of gates).

Let S be a permutation of F 3 2 defined by x 0 1 2 3 4 5 6 7 S(x) 0 1 2 3 4 6 7 5

Its differential uniformity is ∆(S) = 4 and there are 6 coefficients equal to 4 in its difference table. Then there exist some F 8 -linear permutations with maximal branch number such that there are differentials of weight (t + 2) having a higher probability than all minimum-weight differentials. An example of such a diffusion layer with t = 2 is

M = α α + 1 α 2 α 2 + 1
where α is a root of X 3 + X + 1. We compute the exact value of EDP 2 for all minimum-weight differentials first and then for differentials with weight d+1 = 4.

We obtain:

max a =0, b wt(a,b)=3 EDP 2 (a, M(b)) = 2 -4
as there is only one characteristic of probability 2 -4 in the differentials having the highest probability, and

max x =0, y wt(x,y)=4 EDP 2 (x, M(y)) = 2 -3
as there are some differentials of weight 4 composed of two characteristics of probability 2 -4 .

Let S be a permutation of F 4 2 defined by x 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 S(x) 0 2 1 5 4 9 15 8 12 11 6 7 3 14 10 13 Its differential uniformity is ∆(S) = 6 and there are 4 coefficients equal to 6 in its difference table. Then there exist some F 16 -linear permutations with maximal branch number such that there exist some differentials of weight (t + 2) having a higher probability than all minimum-weight differentials. An example of such a diffusion layer with t = 4 is

M =     1 1 α 3 α 3 α 2 + α + 1 1 1 α 2 + α α 2 α 3 + 1 1 α 3 + α 2 + 1 α 2 + 1 α 3 + α 2 + α α 3 + α 1    
where α is a root of X 4 + X + 1.

We compute the exact value of EDP 2 for all differentials of a given weight. We obtain It has differential uniformity ∆(S) = 8 and has 4 coefficients equal to 8 in its difference table. An example of an MDS diffusion layer with t = 3 such that there are differentials of weight t + 3 = 6 having a higher probability than all differentials of weight (t + 1) or (t + 2) is

M =   1 α α 3 + α 2 + α α 2 α + 1 α 3 + α 2 + α + 1 α 2 + 1 α 2 + 1 α 2 + 1  
where α is a root of X 4 + X + 1.

By computing the exact value of EDP 2 for differentials with the same weight, we obtain: In these two examples, the Sboxes are such that there are only a few entries in their difference table which reach the maximum value ∆(S). Conversely, in the previous section, we have proved that the two-round MEDP is achieved by minimum-weight differentials when the Sbox is an APN permutation, that is, when all the nonzero coefficients of the difference table achieve the maximal value. Then we can wonder whether, when the number of entries in the difference table of the Sbox which are equal to the differential uniformity exceeds some bound, we can deduce that the two-round MEDP is tight for some minimumweight differential only.

In this work, we have shown that the form of the minimum-weight codewords associated to the diffusion layer in an SPN F affects the two-round MEDP. Moreover, we have exhibited for the first time some SPN such that the two-round MEDP is achieved by some differentials of weight higher than the branch number. On the other hand, we have also proved that this situation cannot occur in some cases, for instance when the Sbox is an APN permutation of F 8 . But, we give some concrete examples of round functions for which the highest differential probability is not achieved when the number of active Sboxes is minimized. This observation means that, while the branch number provides an upper bound on the two-round MEDP in any AES-like cipher [START_REF] Hong | Provable Security against Differential and Linear Cryptanalysis for the SPN Structure[END_REF][START_REF] Daemen | The Design of Rijndael: AES -The Advanced Encryption Standard[END_REF], an attacker searching for the best two-round differential has to consider all possible number of active Sboxes.

Fig. 1 .

 1 Fig. 1. The AES superbox.

EDCP 2 (

 2 Ω) = 0 unless Supp(a) = Supp(b) and Supp(M (b)) = Supp(c). Using this relation, we deduce that EDCP 2 (Ω) ≤ 2 -m ∆(S) wt(b)+wt(M (b))

maxa

  =0, b wt(a,b)=5 EDP 2 (a, M(b)) = 1, 2656 × 2 -8 , max a =0, b wt(a,b)=6 EDP 2 (a, M(b)) = 1, 4238 × 2 -8 , max a =0, b wt(a,b)=7 EDP 2 (a, M(b)) = 1, 0942 × 2 -10 and max a =0, b wt(a,b)=8 EDP 2 (a, M(b)) = 1, 292 × 2 -12 .5.2 Examplewhere MEDP 2 is tight for a differential of weight (t + 3) Similarly, we can exhibit an SPN whose two-round MEDP is achieved by some differentials of weight (t + 3) only. Let S be a permutation of F 4 2 defined by x 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 S(x) 0 4 3 7 9 14 11 12 10 13 15 8 6 5 2 1

  max a =0, b wt(a,b)=4 EDP 2 (a, M(b)) = max a =0, b wt(a,b)=5 EDP 2 (a, M(b)) = 2 -6 and max a =0, b wt(a,b)=6 EDP 2 (a, M(b)) = 524288 × 2 -24 = 2 -5 .

Acknowledgments. The authors want to thank Thierry Berger for many stimulating discussions, including the discussions around the relevance of the rank minimum distance of the diffusion layer, which have initiated our work.

Partially supported by the French Agence Nationale de la Recherche through the BLOC project under Contract ANR-11-INS-011.


Fran De Aquino

Nuclear Fission by means of Terahertz Sonic Waves

Keywords: Nuclear Fission, Terahertz Sonic waves, Sasers, Sonic Waves

It is shown here that when terahertz sonic waves strike on an atomic nucleus they can produce the fission of the nucleus. This fact can be now checked in practice since recently it was developed an acoustic device called a SASER that is the first to emit sonic waves in the terahertz range.

The quantization of gravity shows that the gravitational mass m g and inertial mass m i are not equivalents, but correlated by means of a factor χ , i.e., ( )

1 0 i g m m χ =
where is the rest inertial mass of the particle. The expression of 0 i m χ can be put in the following form [START_REF] De Aquino | Mathematical Foundations of the Relativistic Theory of Quantum Gravity[END_REF]:

( ) 2 1 1 2 1 2 2 0 ⎪ ⎭ ⎪ ⎬ ⎫ ⎪ ⎩ ⎪ ⎨ ⎧ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎣ ⎡ - ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ + - = = r i g n c W m m ρ χ
where is the density of electromagnetic energy on the particle W ( )

/ m J

; ρ is the matter density of the particle; is the speed of light, and is its index of refraction of the particle. which are respectively given by ( )

3 1 2 2 c v v m q g - = r r ( ) 4 1 2 2 2 c v c m E g g - =
Since q r has always the same direction of v r , then the coefficient

2 2 1 c v m g - cannot be
negative as occurs in the case of be negative. For this coefficient always be positive the unique way is take in modulus, rewriting Eq. ( 3) as follows:

g m g m ( ) 5 1 2 2 c v v m q g - = r r
This is not necessary in Eq. (4) because the energy can be both positive as negative. Then substitution of given by Eq.(1) into Eqs.

(4) and (5) gives g m ( )

6 1 1 2 0 2 2 2 0 2 2 2 c M c v c m c v c m E i i g g χ χ = - = - = and ( ) 7 1 1 0 2 2 0 2 2 v M c v v m c v v m q i i g r r r r χ χ = - = - = By substituting by 0 i M 2 c hf
into equation ( 6) and (7), it is possible to transform these equations for the case of particles with null mass as photons and phonons, etc. The result is ( )

8 hf E g χ = and λ χ h c v q ⎟ ⎠ ⎞ ⎜ ⎝ ⎛ = r r
In the case of photons ( )

c v =
the equations are the followings ( )

10 λ χ χ h q and hf E g = = r
Note that the energy and the momentum of the photons depend on the factor χ , which depends on the medium where the photons propagate, and the local energy density.

Only for

1 = χ
is that the equations (10) are reduced to the well-known expressions of Einstein ( and DeBroglie ) hf ( )

λ h q = .
For phonons ( and

s v v = s λ λ = ) Eq.
(9) tells us that ( )

11 c hf h c v q s s s χ λ χ = ⎟ ⎠ ⎞ ⎜ ⎝ ⎛ = r r
Thus, when a sonic wave strikes on an atomic nucleus, the total momentum transferred for the nucleus in 1second, for example, is given by ( ) ( )

12 1 1 2 sec 1 c hf f s q q s ond s χ = ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ = r
We can express ( ond s q sec 1 ) r , as a function of the kinetic energy absorbed in one second, by means of the following equation:

k E ( ) ( ) 13 2 sec 1 s k ond s v E q = r
Nuclear fission can occur in a heavy nucleus when it acquires sufficient excitation energy ( )

J Mev E k 13 10 8 5 - × = >
[2]. Thus, comparing Eq. ( 12) and (13), we can conclude that the frequency of a phonon, necessary to produce nuclear fission, is given by f ( ) In 2009, it was developed an acoustic device called SASER that is the first to emit sonic waves in the terahertz range [START_REF] Walker | Terahertz acoustic oscillations by stimulated phonon emission in an optically pumped superlattice[END_REF]. While a laser uses packets of electromagnetic vibrations called photons, the SASER uses sonic waves composed of sonic vibrations called phonons.

The advent of the sasers is highly relevant mainly because it will be possible to check the theoretical predictions made here.

  shows that χ can be positive or negative. This fact affect fundamentally the expressions for the momentum and energy