Anne Canteaut
email: anne.canteaut@inria.fr

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

On the behaviors of affine equivalent Sboxes regarding differential and linear attacks

Keywords: Sboxes, affine equivalence, differential cryptanalysis, linear cryptanalysis, AES

This paper investigates the effect of affine transformations of the Sbox on the maximal expected differential probability MEDP and linear potential MELP over two rounds of a substitution-permutation network, when the diffusion layer is linear over the finite field defined by the Sbox alphabet. It is mainly motivated by the fact that the 2-round MEDP and MELP of the AES both increase when the AES Sbox is replaced by the inversion in F 2 8 . Most notably, we give new upper bounds on these two quantities which are not invariant under affine equivalence. Moreover, within a given equivalence class, these new bounds are maximal when the considered Sbox is an involution. These results point out that different Sboxes within the same affine equivalence class may lead to different two-round MEDP and MELP. In particular, we exhibit some examples where the basis chosen for defining the isomorphism between F m 2 and F2m affects these values. For Sboxes with some particular properties, including all Sboxes of the form A(x s ) as in the AES, we also derive some lower and upper bounds for the 2-round MEDP and MELP which hold for any MDS linear layer.

Introduction

Cryptographic functions, including the so-called Sboxes, are usually classified up to affine equivalence (see e.g. [START_REF] Biryukov | A Toolbox for Cryptanalysis: Linear and Affine Equivalence Algorithms[END_REF][START_REF] Leander | On the Classification of 4 Bit S-Boxes[END_REF][START_REF] Brinkmann | On the classification of APN functions up to dimension five[END_REF]) since many of the relevant cryptographic properties are invariant under affine transformations. Indeed, both Sboxes S and A 2 • S • A 1 , where A 1 and A 2 are two affine permutations, have the same algebraic degree, the same non-linearity (even the same square Walsh spectrum) and the same differential uniformity (even the same differential spectrum), which are the usual criteria measuring the resistance of an Sbox against higher-order differential attacks [START_REF] Knudsen | Truncated and higher order differentials[END_REF][START_REF] Lai | Higher order derivatives and differential cryptanalysis[END_REF], linear cryptanalysis [START_REF] Tardy-Corfdir | A known plaintext attack of FEAL-4 and FEAL-6[END_REF][START_REF] Matsui | Linear cryptanalysis method for DES cipher[END_REF] and differential cryptanalysis [START_REF] Biham | Differential cryptanalysis of DES-like cryptosystems[END_REF] respectively. However, it is well-known that equivalent Sboxes may have different implementation costs and may also provide different security levels. For instance, the number of terms in their polynomial representations may highly vary within an equivalent class. This has motivated the choice of the AES Sbox: it corresponds to the inversion in F 2 8 , which is a power permutation with the best known resistance against the previously mentioned attacks; but this power permutation is then composed with an F 2 -affine permutation of F 8 2 which makes its polynomial representation much more complex. Composing the inverse function with an affine permutation then thwarts potential attacks exploiting a simple algebraic representation of the Sbox, like an extremely sparse polynomial. Some other relevant properties (usually of minor importance) are also affected by composition with affine transformations, like the number of fixed points and the bitwise branch number [START_REF] Saarinen | Cryptographic analysis of all 4 × 4-bit sboxes[END_REF].

But, when focusing on statistical attacks, especially on differential and linear cryptanalyses, the Sboxes within the same equivalence class are often considered to have similar behaviors. The main reason is that all known upper bounds on the maximal expected differential probability, and on the maximal expected square correlation (aka maximum expected linear potential) [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 the affine transformations of the Sbox. However, the exact values of these two quantities for two rounds of the AES have been computed by Keliher and Sui with a sophisticated pruning algorithm [START_REF] Keliher | Exact maximum expected differential and linear probability for two-round Advanced Encryption Standard[END_REF], and it appears that the values obtained for the multiplicative inverse in F 2 8 and for the original AES Sbox are different, while these two Sboxes belong to the same equivalence class. Going further in the analysis, Daemen and Rijmen have then determined the expected probabilities of all two-round differentials with 5 or 6 active Sboxes in the AES for both Sboxes [START_REF] Daemen | Understanding Two-Round Differentials in AES[END_REF]. After this analysis, they have even conjectured that, for any number of rounds, the maximal expected differential probability of the AES is always higher with the inversion in F 2 8 than with the AES Sbox [START_REF] Daemen | Computational aspects of the expected differential probability of 4-round AES and AES-like ciphers[END_REF]. The aim of this paper is then to have a better understanding of this phenomenon. For instance, we would like to determine whether these different behaviors originate from the Sboxes only, independently of the choice of the diffusion layer, or not. One of our main motivations is to help the designers choose an Sbox within a given equivalence class. Indeed, in most situations, some appropriate equivalence classes are known (e.g. 4-bit permutations are classified up to affine equivalence [START_REF] Leander | On the Classification of 4 Bit S-Boxes[END_REF]) and the search is often restricted to these classes.

Our contribution. In this paper, we investigate the maximal expected differential probability MEDP and linear potential MELP over two rounds of an SPN. We focus on diffusion layers which are linear over the field of size 2 m , where m is the number of bits of the Sbox, exactly as in the AES and several other ciphers like LED [START_REF] Guo | The LED Block Cipher[END_REF], KLEIN [START_REF] Gong | KLEIN: A New Family of Lightweight Block Ciphers[END_REF], mCrypton [START_REF] Lim | mCrypton -A Lightweight Block Cipher for Security of Low-Cost RFID Tags and Sensors[END_REF], Prøst [START_REF] Kavun | Prøst v1.1[END_REF]... We give a new upper bound on the two-round MEDP and MELP which supersedes the best previous result [START_REF] Park | Improving the Upper Bound on the Maximum Differential and the Maximum Linear Hull Probability for SPN Structures and AES[END_REF], and which is not invariant under affine equivalence. This result is combined with the lower bounds corresponding to some minimum-weight differentials (or linear masks). We are then able to exhibit different behaviors regarding differential and linear attacks on two rounds depending on the choice of the Sbox within a given equivalence class. This includes some unexpected differ-ences since we point out that, for a given m-bit Sbox, the choice of the basis used for defining the finite field in the description of the linear layer may also affect the value of the two-round MEDP or MELP. This is due to the F 2 m -linearity of the mixing layer.

More interestingly from the designers' viewpoint, for some classical families of Sboxes including all functions of the form A(x s ) or (A(x)) s where A is an affine function, like the AES Sbox, our results yield some lower and upper bounds on the two-round MEDP and MELP which are independent of the choice of the MDS linear layer. In other words, we show that, for these families of Sboxes, the two-round MEDP and MELP are two quantities which essentially depend on the Sbox only. Therefore, the designer can choose an Sbox and get a precise estimation of the corresponding two-round MEDP and MELP, while all previous methods [START_REF] Keliher | Exact maximum expected differential and linear probability for two-round Advanced Encryption Standard[END_REF] involved the specifications of both the Sbox and the diffusion layer together. As an illustration, we prove that the previously known upper bounds on MEDP 2 and MELP 2 due to Park et al. [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 always tight for the multiplicative inverse over F 2 m and for any MDS linear layer. In other words, the inversion is the mapping within its equivalence class which has the highest two-round MEDP and MELP, independently of the choice of the MDS linear layer. This situation mainly originates from the fact that this Sbox is an involution.

Maximum Expected Differential Probability and Linear

Potential for 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] (aka iterated Even-Mansour construction), which consists of an alternation of key-independent (usually similar) permutations and of round-key additions. The round permutation usually follows the principles introduced by Shannon. It is decomposed into a nonlinear substitution function Sub which provides confusion, and a linear permutation which provides diffusion 1 . 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. Differential [START_REF] Biham | Differential cryptanalysis of DES-like cryptosystems[END_REF] and linear [START_REF] Tardy-Corfdir | A known plaintext attack of FEAL-4 and FEAL-6[END_REF][START_REF] Matsui | Linear cryptanalysis method for DES cipher[END_REF] cryptanalyses are 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.,

) = A • ϕ -1 ϕ(x)
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. This probability may highly vary with the key especially when a small number of rounds is considered (see e.g. [START_REF] Lai | Markov ciphers and differential cryptanalysis[END_REF], [START_REF] Daemen | The Design of Rijndael: AES -The Advanced Encryption Standard[END_REF]Section 8.7.2], [START_REF] Daemen | Probability distributions of correlation and differentials in block ciphers[END_REF], [START_REF] Daemen | New criteria for linear maps in AES-like ciphers[END_REF] and [START_REF] Blondeau | Bounds in Shallows and in Miseries[END_REF]). But computing the whole distribution of the probability of a differential is a very difficult task, and 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. It is worth noticing that the MEDP is relevant for estimating the resistance against classical differential cryptanalysis, not against its variants like truncated differential attacks (which provide better attacks on the AES since the AES resists differential cryptanalysis by design).

Similarly, the resistance of a cipher against linear cryptanalysis can be evaluated by determining the distribution over the keys of the correlation of each r-round mask (u, v):

C(u, v) = 2 -n x∈F n 2 (-1) u•x+v•E k (x) ,
where n is the block-size. For a key-alternating cipher with independent round keys, the average over all keys of the correlation C(u, v) is zero for any nonzero mask (u, v) (see e.g. [START_REF] Daemen | The Design of Rijndael: AES -The Advanced Encryption Standard[END_REF]Section 7.9] or [START_REF] Abdelraheem | On the Distribution of Linear Biases: Three Instructive Examples[END_REF]Prop. 1]). Then, the major parameter investigated in this paper is the variance of the distribution of the correlation, which corresponds to the average square correlation. The way it affects the complexity of linear cryptanalysis is discussed for instance in [START_REF] Nyberg | Linear Approximation of Block Ciphers[END_REF][START_REF] Daemen | The Design of Rijndael: AES -The Advanced Encryption Standard[END_REF][START_REF] Murphy | The effectiveness of the linear hull effect[END_REF][START_REF] Leander | On linear hulls, statistical saturation attacks, PRESENT and a cryptanalysis of PUFFIN[END_REF][START_REF] Abdelraheem | On the Distribution of Linear Biases: Three Instructive Examples[END_REF].

Definition 3. Let (E k ) k∈F κ
2 be an r-round iterated cipher with block-size n and key-size κ. Then, the expected square correlation (aka linear potential [START_REF] Nyberg | Linear Approximation of Block Ciphers[END_REF]) of an r-round mask (u, v) is

ELP E r (u, v) = 2 -2n-κ k∈F κ 2   x∈F n 2 (-1) u•x+v•E k (x)   2 .
The maximum expected square correlation for r rounds is

MELP E r = max u,v =0 ELP E r (u, v).

Known results on two-round MEDP and MELP

Computing the MEDP and MELP for an SPN, even for a small number of rounds, is usually non-trivial. An easier task consists in computing the expected probability of an r-round differential characteristic (i.e., a collection of (r+1) differences), or the expected square correlation of a linear trail (i.e., a collection of (r + 1) linear masks). In particular, a simple upper bound on this quantity can be derived from the differential uniformity [START_REF] Nyberg | Differentially uniform mappings for cryptography[END_REF] (resp. the nonlinearity) of the Sbox, and from the differential (resp. linear) branch number of the linear layer. We will then extensively use the following notation for these quantities. -For any u and v in F m 2 , we define

W S (u, v) = x∈F m 2 (-1) u•x+v•S(x) ,
where • is the usual scalar product in

F m 2 . The multi-set {W S (u, v), u ∈ F m 2 , v ∈ F m 2 }
is the Walsh spectrum of S, and its highest magnitude

L(S) = max u,v =0 W S (u, v) is the linearity of S.
The branch number of the diffusion layer then determines the minimum number of active Sboxes within a differential or linear trail. Definition 5. [START_REF] Daemen | Cipher and hash function design strategies based on linear and differential cryptanalysis[END_REF] Let M be an F 2 -linear permutation of (F m 2 ) t . We associate with M the codes C M and 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 } and C ⊥ M = {(M * (c), c), c ∈ (F m 2 ) t } ,
where M * is the adjoint of M , i.e., the linear map such that x • M (y) = M * (x) • y for any (x, y). The differential branch number (resp. linear branch number) of M is the minimum distance of the code C M (resp. of C ⊥ M ). From Singleton's bound, the maximum branch number of M is (t + 1) and is achieved when C M is MDS. Since the codes C M and C ⊥ M are dual to each other, M has optimal differential branch number if and only if it has optimal linear branch number. A simple upper bound for both the two-round MEDP and MELP can then be derived from the branch numbers of M , and from the differential uniformity and the linearity of the Sbox (see [START_REF] Hong | Provable Security against Differential and Linear Cryptanalysis for the SPN Structure[END_REF] and [START_REF] Daemen | The Design of Rijndael: AES -The Advanced Encryption Standard[END_REF]Section B.2]):

MEDP 2 ≤ 2 -m ∆(S) t and MELP 2 ≤ 2 -m L(S) 2t . (1)
This result has then be 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].

Theorem 1 (FSE 2003 bounds). [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] Chun | Differential and linear cryptanalysis for 2-round SPNs[END_REF] Let E be a block cipher of the form SPN(m, t, S, M ) where M is a linear permutation with differential (resp. linear) branch number d (resp. d ⊥ ). Then, we have

MEDP E 2 ≤ 2 -md max   max a∈(F m 2 ) * γ∈(F m 2 ) * δ S (a, γ) d , max b∈(F m 2 ) * γ∈(F m 2 ) * δ S (γ, b) d   , MELP E 2 ≤ 2 -2md ⊥ max   max u∈(F m 2 ) * γ∈(F m 2 ) * W S (u, γ) 2d ⊥ , max v∈(F m 2 ) * γ∈(F m 2 ) * W S (γ, v) 2d ⊥  
It is worth noticing that the FSE 2003 bounds always supersede [START_REF] Abdelraheem | On the Distribution of Linear Biases: Three Instructive Examples[END_REF].

The main question is now to determine the gap between the FSE 2003 bounds and the exact values of MEDP 2 and MELP 2 for a given cipher. An interesting property is that the FSE 2003 bound is invariant under affine equivalence, i.e., under left or right composition of the Sbox with an affine permutation. Actually, the following well-known property holds.

Lemma 1. Let S be permutation of F m 2 and A 1 and A 2 be two affine permutations of

F m 2 . Then S = A 2 • S • A 1 satisfies δ S (a, b) = δ S (L 1 (a), L -1 2 (b)) and W S (u, v) 2 = W S ((L -1 1 ) * (u), L * 2 (v)) 2
where L 1 and L 2 correspond to the linear parts of A 1 and A 2 , and L * denotes the adjoint of L.

However, while the previous bounds are invariant under affine equivalence, it appears that the exact values of MEDP 2 and MELP 2 may vary when the Sbox is composed with an affine permutation. For instance, for the AES with its original Sbox, the exact values of the two-round MEDP 2 and MELP 2 have been computed by a pruning search algorithm [START_REF] Keliher | Exact maximum expected differential and linear probability for two-round Advanced Encryption Standard[END_REF]:

MEDP 2 = 53×2

SPNs over F 2 m

A special case of affine equivalent Sboxes corresponds to the mappings over F m 2 which are derived from the same function over the finite field F 2 m , but from different correspondences between F 2 m and the vector space F m 2 . Such equivalent Sboxes appear in several situations. Indeed, a simple construction for an optimal linear layer consists in choosing for M a permutation of F mt 2 associated with a code C M which is linear over the field F 2 m , where m is the size of the Sbox. Then, this diffusion layer has to be defined over F t 2 m , instead of F mt 2 . To this end, we need to identify the vector space F m 2 with the finite field F 2 m by the means of an isomorphism ϕ associated to a basis (α 0 , . . . , α m-1 ), namely:

ϕ : F m 2 → F 2 m (x 0 , . . . , x m-1 ) → m-1 i=0 x i α i .
Then, both the Sbox and the diffusion layer can be represented as functions over the field F 2 m by

S = ϕ • S • ϕ -1 and M = ϕ • M • ϕ -1 ,
where ϕ is the concatenation of t copies of ϕ. In this case, as noticed in [START_REF] Daemen | The Design of Rijndael: AES -The Advanced Encryption Standard[END_REF]Section A.5], any r rounds of SPN(m, t, S, M ) can be written as ϕ

-1 •Add kr • . . .• R • Add k1 •R • Add k0 • ϕ where the round function R = M • (S, . . . , S
) is a permutation of (F 2 m ) t and Add x denotes the addition of x in (F 2 m ) t . Obviously, composing by ϕ at the beginning and by ϕ -1 at the end changes neither the MEDP nor the MELP. This implies that MEDP E r and MELP E r depend on M and S only, i.e., on the representations of the Sbox and of the diffusion layer over F 2 m . In particular, the choice of the basis (α 0 , . . . , α m-1) has no influence on the differential and linear properties of the cipher. For this reason, we use the following alternative notation for defining an SPN from these representations. 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.

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. As pointed out in [START_REF] Daemen | Advanced Linear Cryptanalysis of Block and Stream Ciphers, chap[END_REF], the differential and linear properties of any SPN(m, t, S, M ) can be equivalently studied by considering the alternative representation SPN F (m, t, S, M). This alternative analysis then involves the differential spectrum and the Walsh spectrum of the Sbox S over F 2 m , which are related to the spectra of the corresponding function S over F m 2 as follows.

Proposition 1. (see e.g. [START_REF] Daemen | Advanced Linear Cryptanalysis of Block and Stream Ciphers, chap[END_REF]) 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 (β)) W S F (α, β) = x∈F 2 m (-1) Tr(αx+βS(x)) = W S (ψ -1 (α), ψ -1 (β))
where ψ is the isomorphism from F m 2 into F 2 m defined by the dual basis, i.e., the basis (β 0 , . . . , β m-1 ) such that Tr(α i β j ) = 0 if i = j and Tr(α i β i ) = 1.

3 New upper bounds on the 2-round MEDP and MELP Now, we study the exact values of the two-round MEDP and MELP for any cipher of the form SPN(m, t, S, M ) where the diffusion layer M is linear over F 2 m , like in the AES. We aim at obtaining a better approximation of the MEDP 2 and MELP 2 by finding some improved lower and upper bounds. In particular, we would like to be able to differentiate affine equivalent Sboxes.

The new upper bounds

From now on, when considering a cipher of the form SPN F (m, t, S, M), δ F (α, β) and W F (α, β) will denote the differential and Walsh spectra of the Sbox S. The considered Sbox will be mentioned in the notation in case of ambiguity only.

Theorem 2. Let E be a block cipher of the form SPN F (m, t, S, M) where M is linear over F 2 m and has differential (resp. linear) branch number d (resp. d ⊥ ). For µ ∈ F 2 m and u > 0, we define

B u (µ) = max α,β,λ∈F * 2 m γ∈F * 2 m δ F (α, γ) u δ F (γλ + µ, β) (d-u) , (2)
B ⊥ u (µ) = max α,β,λ∈F * 2 m γ∈F * 2 m W F (α, γ) 2u W F (γλ + µ, β) 2(d ⊥ -u) , (3)
B(µ) = max 1≤u<d B u (µ) and B ⊥ (µ) = max 1≤u<d ⊥ B ⊥ u (µ) .
Then,

MEDP E 2 ≤ 2 -md max µ∈F 2 m B(µ) and MELP E 2 ≤ 2 -2md ⊥ max µ∈F 2 m B ⊥ (µ) .
The proof is given in Appendix A. It mainly exploits the special form of the codewords in an F 2 m -linear code (see Lemma 2 in Appendix A). In the whole paper, the proofs in the context of differential attacks and of linear attacks are similar. Actually, all results can be written in a more generic way, by replacing the

2 m × 2 m matrix with coefficients 2 -m δ F (α, β), α, β ∈ F 2 m , or with coefficients 2 -2m W F (α, β) 2 , by any matrix (Λ(α, β)) α,β∈F 2 m
, such that the coefficients Λ(α, β) lie between 0 and 1 and satisfy Λ(α, 0) = Λ(0, α) = 0 for any nonzero α and

β∈F 2 m Λ(α, β) = β∈F 2 m Λ(β, α) = 1 for all α ∈ F 2 m .
Clearly, both normalized differential and Walsh spectra satisfy these conditions.

Computing this new bound is obviously more expensive than computing the FSE 2003 bound since we have to take the maximum of a similar quantity over all λ and µ. We will see in Section 4 that this bound simplifies in some cases, for instance for all Sboxes corresponding to the composition of a power permutation with an affine mapping, like the AES Sbox. Also, we will show that this refined bound may enable us to deduce the exact values of the MEDP 2 and MELP 2 in a much more efficient way than the ad hoc search algorithm presented in [START_REF] Keliher | Exact maximum expected differential and linear probability for two-round Advanced Encryption Standard[END_REF].

In the case of the AES Sbox over F 2 8 and d = d ⊥ = 5, these new bounds lead to MEDP 2 ≤ 55.5×2 -34 instead of MEDP 2 ≤ 79×2 -34 for the FSE 2003 bound, and MELP 2 ≤ 31, 231, 767 × 2 -52 instead of MELP 2 ≤ 48, 193, 441 × 2 -52 . This seems to be a minor improvement since there is only a factor ρ 0.7 between the two bounds. However, in AES-like constructions, the 2-round MEDP and MELP correspond to the average differential uniformity and linearity of the average superbox. Upper-bounds on the 4-round MEDP and MELP can then be derived from these values using [START_REF] Abdelraheem | On the Distribution of Linear Biases: Three Instructive Examples[END_REF]. Then, we get a factor ρ d-1 (resp. ρ d ⊥ -1 ) between the bounds on MEDP 4 and MELP 4 .

While the FSE 2003 bound corresponds to the highest d-th power moment of a row or a column in the difference table of the Sbox (or in the square correlation table), our new bound involves together a row and a column in the table. In other words, this new bound depends on the link between some quantity (e.g. a derivative or the squared Walsh transform of a component) for S, and the same quantity for the inverse permutation S -1 . This clearly appears when S has a two-valued differential spectrum, since the expression of B(µ) simplifies to

B(µ) = ∆(S) d max α,β,λ∈F * 2 m # Im(D α S) ∩ λIm(D β S -1 ) + µ ,
where D α S denotes the derivative of S at point α, i.e., the function x → S(x + α) + S(x). Similarly, if S is a plateaued function [START_REF] Zheng | Plateaued functions[END_REF], i.e., a function whose Walsh spectrum contains the values 0 and ±L(S) only, we get

B ⊥ (µ) = L(S) 2d ⊥ max α,β,λ∈F * 2 m # Supp( S -1 α ) ∩ λSupp( S β ) + µ ,
where S α denotes the Boolean function x → Tr(αS(x)), and f denotes the Walsh transform of f , i.e., α → x∈F 2 m (-1) Tr(f (x)+αx) . It appears from these formulas that the cardinality of the intersection of such sets cannot exceed the cardinality of each set (equal to 2 m /∆(S) and 2 2m /L(S) 2 respectively), and that this maximum is obviously tight when S is an involution, i.e., S -1 = S. But when the Sbox is composed with a randomly chosen affine permutation, the two sets can be considered as independent. Then, the expected cardinality of their intersection is about 4 ) where π ∆ = 1/∆(S) is the proportion of nonzero elements within a row or a column of the difference table, and π L = 2 m /L(S) 2 is the proportion of nonzero elements within a row or a column of the square correlation table. For instance, for an almost bent Sbox, i.e., with m odd, ∆(S) = 2 and L(S) = 2 (m+1)/2 , the expected cardinality of the two sets involved in the previous formulas is 2 m-2 , while it is equal to 2 m-1 when S is an involution. More generally, our new upper bound is always smaller than or equal to the corresponding FSE 2003 bound, with equality when S is an involution, as stated in the following proposition (see the proof in Appendix A).

2 m π 2 ∆ = 2 m /∆(S) 2 (resp. 2 m π 2 L = 2 3m /L(S)
Proposition 2. Let S be a permutation of F 2 m and d be some positive integer. Then, each of the two upper bounds defined in Theorem 2 is less than or equal to the corresponding FSE 2003 bound. Moreover, equality holds if S is an involution, since for any integer u < d,

max µ∈F 2 m B u (µ) = B u (0) = max a∈F * 2 m γ∈F * 2 m δ F (a, γ) d = max b∈F * 2 m γ∈F * 2 m δ F (γ, b) d
and max

µ∈F 2 m B ⊥ u (µ) = B ⊥ u (0) = max a∈F * 2 m γ∈F * 2 m W F (a, γ) 2d = max b∈F * 2 m γ∈F * 2 m W F (γ, b) 2d .

Some lower bounds

An interesting question is to determine whether these new bounds are optimal, in the sense that, for a given Sbox, there exists a linear layer such that the bounds are tight. Here, we exhibit some functions M with optimal branch number such that the EDP (resp. ELP) of some minimum-weight differential (resp. linear mask) over two rounds is related to the upper bound of Theorem 2. This lower bound results from the fact that the minimum-weight codewords with a given support in an F 2 m -linear MDS code form a set of the form {λc, λ ∈ F * 2 m } for some fixed codeword c. Such a set is named a bundle in [START_REF] Daemen | Understanding Two-Round Differentials in AES[END_REF]. It is not difficult to observe that B(0) (resp. B ⊥ (0)) corresponds to the maximum EDP (resp. to the maximum ELP) of some particular minimum-weight bundles. Moreover, for any such particular bundle, a function M such that C M contains this bundle can be constructed from some Generalized Reed-Solomon code.

Proposition 3. Let S be a permutation of F 2 m and t be any integer such that t ≤ 2 m-1 . Then, there exist two F 2 m -linear diffusion layers M 1 and M 2 over F t 2 m with maximal branch number d = t + 1 such that any block cipher E 1 of the form SPN F (m, t, S, M 1 ) and E 2 of the form SPN F (m, t, S, M 2 ) satisfy

MEDP E1 2 ≥ 2 -m(t+1) B(0) and MELP E2 2 ≥ 2 -2m(t+1) B ⊥ (0)
where B(0) and B ⊥ (0) are defined as in Theorem 2.

Proof. We give here the proof for MEDP 2 only, but it is similar for MELP 2 . Actually, the proposition can be formulated in a generic way as the results in Appendix A. Let α, β, λ ∈ F * 2 m and 1 ≤ u ≤ t be some values such that

γ∈F * 2 m δ F ( α, γ) u δ F (γ λ, β) t+1-u = B(0). Let a ∈ F t 2 m
be the input difference whose first u coordinates equal α and whose last (t-u) coordinates equal 0. Similarly, b ∈ F t 2 m denotes the output difference whose first (t + 1 -u) coordinates equal β and whose last ( u -1) coordinates equal 0. Since

EDP 2 (a, M (b)) = c∈C M t i=1 δ F (a i , c i )   t j=1 δ F (c t+j , b j )   , it is equal to B(0) if the words of the form γ(1, . . . , 1 u , 0, . . . , 0 t-u , λ, . . . , λ t+1-u , 0, . . . , 0 u-1 ) (4)
are the codewords in C M having the same support as (a, b). Therefore, we aim at finding a linear MDS diffusion layer M such that C M contains these codewords. Since t ≤ 2 m-1 , we can choose 2t distinct elements x 1 , . . . , x 2t in F 2 m . For any choice of 2t elements v 1 , . . . , v 2t , we define the t × t matrix

R =       1 1 ... 1 x 1 v 1 x 2 v 2 ... x t v t x 2 1 v 1 x 2 2 v 2 ... x 2 t v t . . . x t-1 1 v 1 x t-1 2 v 2 ... x t-1 t v t       -1 ×       1 1 ... 1 x t+1 v t+1 x t+2 v t+2 ... x 2t v 2t x 2 t+1 v t+1 x 2 t+2 v t+2 ... x 2 2t v 2t . . . x t-1 t+1 v t+1 x t-1 t+2 v t+2 ... x t-1 2t v 2t       .
Then, the code [START_REF] Macwilliams | The theory of error-correcting codes[END_REF]Page 303] that this code is MDS and is composed of all words of the form (v 1 F (x 1 ), . . . , v 2t F (x 2t )) where F ranges over all polynomials in F 2 m [X] of degree strictly less than t. Then, the codewords in C M having the same support as (a, b) correspond to the polynomials of degree at most (t -1) which vanish at all (t -1) points x i for i ∈ Supp((a, b)). Then, these polynomials can be written as γ F (x), γ ∈ F * 2 m , and F (x i ) = 0 for i ∈ Supp((a, b)) since F cannot have more than (t -1) roots. Therefore, we can choose for v a vector such that

C M = {(x, xR), x ∈ F t 2 m } is the generalized Reed-Solomon code GRS t (x 1 , . . . , x 2t ; v). It is well-known
v i = 1/ F (x i ) for 1 ≤ i ≤ u and v i = λ/ F (x i ) for t + 1 ≤ i ≤ 2t + 1 -u.
This guarantees that the words in C M having the same support as (a, b) are the words of the form (4). It follows that

EDP 2 (a, M (b)) = γ∈F * 2 m u i=1 δ F ( α, γv i F (x i ))   t+1-u j=1 δ F (γv t+j F (x t+j ), β)   = γ∈F * 2 m δ F ( α, γ) u δ F (γ λ, β) t+1-u .
Remark 1. In some particular cases, we can find a generalized Reed-Solomon code corresponding to a linear layer M for which the two bounds hold together. Indeed, we want to construct a code C M which contains the words (4) and whose dual C ⊥ M contains the words γ(0, . . . , 0

t-ū , λ, . . . , λ ū , 0, . . . , 0 ū-1 , 1, . . . , 1 t+1-ū )
for some given λ and ū. But the dual of GRS t (x 1 , . . . , x 2t ; v) is another generalized Reed-Solomon code, GRS t (x 1 , . . . , x 2t ; w) with w -1 i = v i j =i (x i + x j ). In particular, if ū + u = t, we can find a vector (v 1 , . . . , v 2t ) such that both conditions hold together. This situation occurs for instance when S is an involution since B(0) (resp. B ⊥ (0)) is attained for all u < d (resp. for all ū < d ⊥ ).

An interesting situation is the case where the maximum over all µ ∈ F 2 m of B(µ) (resp. of B ⊥ (µ)) is attained for µ = 0. Then there exists some M for which the upper bound from Theorem 2 is tight for SPN F (m, t, S, M), implying that it is impossible to find a general better bound which depends on S and t only. This situation occurs in particular for any involutional Sbox. Indeed, by combining Prop. 2 and 3, we deduce that, for any involutional Sbox and any t ≤ 2 m-1 , there exists a linear layer over F t 2 m such that the exact values of MEDP 2 and of MELP 2 are equal to the FSE 2003 bounds.

Corollary 1. Let S be an involution of F 2 m and t be any integer with t ≤ 2 m-1 . Then, there exist an F 2 m -linear diffusion layer M over F t 2 m with maximal branch number such that SPN F (m, t, S, M) satisfies

MEDP 2 = max a∈F * 2 m γ∈F * 2 m δ F (a, γ) 2 m (t+1) = max b∈F * 2 m γ∈F * 2 m δ F (γ, b) 2 m (t+1)
and

MELP 2 = max a∈F * 2 m γ∈F * 2 m W F (a, γ) 2 m 2(t+1) = max b∈F * 2 m γ∈F * 2 m W F (γ, b) 2 m 2(t+1)
.

Proof. We know from Prop. 2 that for any u, max µ∈F 2 m B u (µ) = B u (0) = B(0), and max µ∈F 2 m B u (µ) ⊥ = B u (0) ⊥ = B(0). Moreover, all these values are equal to the FSE 2003 bounds. By combining Th. 2 and Prop. 3, we deduce the existence of some linear layers for which MEDP 2 (resp. MELP 2 ) are lower-and upperbounded by B(0) (resp. B ⊥ (0)). Moreover, we have proved in Prop. 2 that B(0) (resp. B ⊥ (0)) is attained for all values of u. This is a case where we can construct a GRS code satisfying the conditions for MEDP 2 and MELP 2 together.

Example 1. The Prøst permutation over F 16d 2 , d ≥ 1, is the core function of several AEAD-schemes submitted to the CAESAR competition [START_REF] Kavun | Prøst v1.1[END_REF]. This permutation is of the form SPN(4, 4d, S, M ) where S is a 4-bit involution named SubRows and M corresponds to the composition of two linear permutations, MixSlices and ShiftPlanes. The round-constant addition is omited here since it does not have any impact in our context. Similarly to the AES, two consecutive rounds of the Prøst permutation can be seen as the parallel application of d copies of a superbox defined over F 16 . This superbox corresponds to two SubRows layers separated by a MixSlices transformation. Moreover, even if it is not mentioned in the design rationale, it can be checked that MixSlices is linear over F 16 if F 16 is identified with F 4 2 by the following isomorphism:

ϕ : (x 0 , . . . , x 3 ) → x 1 + αx 2 + α 2 x 3 + α 3 x 0
where α is a root of X 4 + X 3 + 1. Indeed, the function defined over F 4 16 by M = φ • MixSlices • φ-1 corresponds to the multiplication by

    1 α α + α 2 α 2 α 1 α 2 α + α 2 α + α 2 α 2 1 α α 2 α + α 2 α 1     .
The previous framework then directly applies2 . In particular, since the Sbox is an involution, our bounds are equal to the FSE 2003 bounds (Prop. 2): the Prøst permutation with any F 2 -linear MDS MixSlices transformation satisfies

MEDP 2 ≤ 2 -8 and MELP 2 ≤ 2 -8 .
These bounds are tight as stated in Corollary 1: using the construction described in the proof of Prop. 3, we obtain that the following matrix over F 16 (with the previously described representation) leads to a variant of the Prøst permutation with MEDP 2 = MELP 2 = 2 -8 :

    α 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     .
This implies that, for this particular Sbox, the MixSlices transformation must be chosen with care to guarantee small MEDP 2 and MELP 2 . Instead, for some Sboxes within the same equivalence class as SubRows, we can guarantee that, for any F 16 -linear MDS MixSlices, MEDP 2 ≤ 3 × 2 -10 . This does not make a big difference in the case of Prøst since the alphabet is small and the exact MEDP 2 and MELP 2 can be easily computed. For instance, for the MixSlices transformation chosen by the designers, we have MEDP 2 = 3 × 2 -11 and MELP 2 = 81 × 2 -16 . However, for Sboxes over F 2 8 , computing the exact MEDP 2 and MELP 2 is rather expensive and obtaining a better upper bound is very helpful.

Influence of the field representation

Clearly, there is no reason why the two-round MEDP or MELP should be the same for affine equivalent Sboxes in general. Then, it makes sense that our new bounds are not invariant under affine equivalence. More surprisingly, by combining the upper bound from Theorem 2 with the lower bound provided by Prop. 3, we can exhibit some examples showing that the choice of the field F 2 m , i.e., the choice of the isomorphism ϕ between F m 2 and F 2 m , may influence the value of the MEDP and MELP.

Example 2. Let us consider 2 rounds of a cipher of the form SPN(4, 4, S, M ), where S is one of the permutations of F 4 2 used in the PRINCE-family [START_REF] Borghoff | PRINCE -A Low-Latency Block Cipher for Pervasive Computing Applications -Extended Abstract[END_REF], namely permutation S 6 in [10, Table 3]:

x 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 S(x) 0 1 2 13 4 7 15 6 8 14 11 10 9 3 12 5 where each element in F 4 2 is here represented as an integer between 0 and 15. This Sbox is differentially 4-uniform and has linearity L(S) = 8. For this Sbox, the FSE 2003 bound gives MEDP E 2 ≤ 34 × 2 -14 , for any F 2 -linear diffusion layer M over F 16 2 with branch number 5. If we now consider a diffusion layer M with branch number 5 which is linear over F 2 4 where F 2 4 is identified with F 4 2 by the basis {1, α, α 2 , α 3 } where α is a root of the irreducible polynomial X 4 + X 3 + X 2 + X + 1, we get from Theorem 2 that

MEDP E 2 ≤ 33 × 2 -14 ,
and this inequality holds for any such function M. However, we can now consider a permutation M which is linear over F 2 4 , but where the isomorphism between F 4 2 and F 2 4 is defined by a different basis, namely {1, β, β 2 , β 3 } where β is a root of the primitive polynomial X 4 + X + 1. Then, the value B(0) involved in Prop. 3 equals 17×2 7 , implying that there exists an F 2 4 -linear function M with branch number 5 such that MEDP E 2 = 34 × 2 -14 , which is strictly higher that the upper bound we have for any MDS diffusion layer F 2 4 -linear where F 2 4 is defined with the basis {1, α, α 2 , α 3 }.

There is no contradiction here since the two theorems apply to the representations of the Sbox and of the diffusion function over F 2 4 only. Here, we have proved that there is a particular M such that SPN(4, 4, S, ψ -1 • M • ψ) has MEDP 2 = 34×2 -14 , where ψ is the concatenation of 4 copies of the isomorphism ψ from F 4 2 into F 2 4 defined by the basis {1, β, β 2 , β 3 }. But if we consider the basis {1, α, α 2 , α 3 } and the corresponding isomorphism ϕ, Th. 2 provides a bound for all SPN F (4, 4, ϕ • S • ϕ -1 , M) which does not include the previous case because the permutation defined by

M = ϕ • ψ -1 • M • ψ • ϕ -1 is not linear over F 2 4 , since (ψ •ϕ -1
) is not a ring isomorphism. This unexpected result comes from the fact that the definitions of the Sbox and of the linear layer do not use the same representation: the Sbox is defined over F 4 2 while the linear layer is defined over F 2 4 . This is why the choice of the basis affects the MEDP while this is obviously not the case when the two functions are defined over the same alphabet. But, even if this does not correspond to a natural mathematical description, it may be relevant to use the binary representation for the Sbox (chosen to minimize the number of gates for instance), while the field representation is used for the mixing layer since it is F 2 m -linear (see e.g. [START_REF] Guo | The LED Block Cipher[END_REF]).

It is worth noticing that the previous situation is not related to the fact that one of the field representations is defined by a non-primitive polynomial. Indeed, the following example shows that even changing the primitive polynomial used for constructing F 2 m may affect the two-round MEDP and MELP.

Example 3. We now consider two rounds of a cipher SPN(5, 4, S, M ) where S is the following permutation of F 5 2 : x 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 S(x) 0 1 18 20 [START_REF] Guo | The LED Block Cipher[END_REF] When F 2 5 is identified with F 5 2 by the basis {1, α, α 2 , α 3 , α 4 } where α is a root of the primitive polynomial X 5 + X 2 + 1, Theorem 2 shows that any MDS diffusion layer linear over F 2 5 with this representation satisfies

MEDP E 2 ≤ 13 × 2 -20 and MELP E 2 ≤ 8407 × 2 -27 .
When F 2 5 is constructed from the primitive polynomial X 5 + X 3 + 1, the lower and upper bounds from Th. 2 and Prop. 3 are equal, and show that there exists some MDS layer linear over F 2 5 with this alternative representation such that

MEDP E 2 = 14 × 2 -20 and MELP E 2 = 8663 × 2 -27 .
The first primitive polynomial then guarantees lower two-round MEDP and MELP than the second one.

Another example is the LED block cipher. In [25, Section 3.2], the designers provide an upper bound on the four-round MEDP and MELP of a cipher of the form SPN F (4, 4, S, M) 3 where M is an F 2 4 -linear function with branch number 5, S corresponds to the Present Sbox and F 2 4 is defined by the basis (1, α, α 2 , α 3 ), with α a root of X 4 + X + 1. To this end, they use the FSE 2003 bound, which leads to MEDP 2 ≤ 2 -8 and MELP 2 ≤ 2 -8 , implying that MEDP 4 ≤ 2 -32 and MELP 4 ≤ 2 -32 . For this cipher, our new upper bound is equal to the FSE 2003 bound and then does not improve the result. However, if we consider the same Sbox, but modify the representation of F 2 4 and choose the basis defined by X 4 + X 3 + 1, Theorem 2 leads to MEDP 2 ≤ 3 × 2 -10 . Then, with this minor modification, the upper bound on MEDP 4 is improved by a factor (3/4) 4 = 0.3164 (while the bound on MELP 4 is unchanged).

Multiplicative invariance for Sboxes

Power permutations are often considered as suitable Sboxes since determining their differential and Walsh spectra is easier and also because they usually have a lower implementation cost. This family of Sboxes is also of great interest in our context since our bounds provide a very good approximation of the exact tworound MEDP and MELP which depends on the Sbox and on the branch number only. Indeed, for power permutations, we get a universal lower bound in the sense that the bound provided in Prop. 3 holds for any F 2 m -linear permutation M. This comes from the fact that all rows in the difference table (resp. in the correlation table) of a power permutation can be deduced from a single one. This is because any power function S is an endomorphism over the multiplicative group F * 2 m , i.e., S(xy) = S(x)S(y) for any pair of nonzero elements (x, y). Unfortunately, there is no hope to capture a larger family of Sboxes with a straightforward generalization of this property since it can be easily shown that any function S satisfying S(xy) = S(x)S (y) for some S is of the form S(x) = cx s . However, we can define this suitable multiplicative property on the difference table (resp. on the Walsh transform) of S, and not on the function itself. -S is said to have multiplicative-invariant 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 .
-S is said to have a multiplicative-invariant Walsh transform if, for any x ∈ F * 2 m there exists a permutation ψ x of F * 2 m such that

W F (α, xy) 2 = W F (ψ x (α), y) 2 , ∀y ∈ F * 2 m .
These definitions include all functions resulting from the composition on the right of a power permutation with an F 2 -linear permutation (cf. proof in Appendix B).

Proposition 4. Let S = S • L where L is an F 2 -linear permutation of F 2 m and S : x → x s is a power permutation over F 2 m . Then, both the derivatives of S and its Walsh transform are multiplicative-invariant.

It is worth noticing that the fact that a permutation has multiplicative-invariant derivatives (resp. Walsh transform) does not imply that a similar property holds for its inverse. In other words, Prop. 4 does not apply to the composition on the left of a power permutation with a linear permutation. The following proposition shows that the permutations with multiplicative-invariant derivatives (resp. Walsh transform) are not all affine equivalent to a power permutation.

Proposition 5. Let m be an odd integer and S be a quadratic permutation of F 2 m with ∆(S) = 2 (aka APN permutation). Then, S has multiplicativeinvariant derivatives and S -1 has a multiplicative-invariant Walsh transform.

This result actually applies to a (possibly) more general class of permutations known as crooked permutations, which includes all quadratic APN permutations (see details in Appendix B). Prop. 5 applies for instance to the infinite family of APN permutations of degree 2

x -→ x 2 i +1 + ux 2 j m 3 +2 (3-j) m 3 +i
with gcd(i, m) = 1 and j = im/3 mod 3 over F 2 m , m odd, divisible by 3 and not by 9, which is not affine equivalent to a power mapping [START_REF] Budaghyan | Two Classes of Quadratic APN Binomials Inequivalent to Power Functions[END_REF].

A universal lower bound for Sboxes with some multiplicative invariance

We now show that for Sboxes with multiplicative-invariant derivatives (resp. Walsh transform), the previously established bounds simplify.

Proposition 6. Let S be a permutation of F 2 m such that either S or S -1 has multiplication-invariant derivatives (resp. Walsh transform). For any integers d and d ⊥ , we define

B u (µ) = max α,β∈F * 2 m γ∈F * 2 m δ F (α, γ) u δ F (γ + µ, β) (d-u) , with 1 ≤ u < d, B ⊥ u (µ) = max α,β∈F * 2 m γ∈F * 2 m W F (α, γ) 2u W F (γ + µ, β) 2(d ⊥ -u) , with 1 ≤ u < d ⊥ .
Then, for any u, we have

B u (0) = B u (0) and max µ∈F * 2 m B u (µ) = max µ∈F * 2 m B u (µ) resp. B ⊥ u (0) = B ⊥ u (0) and max µ∈F * 2 m B ⊥ u (µ) = max µ∈F * 2 m B ⊥ u (µ) ,
where B u (µ) and B ⊥ u (µ) are defined as in Theorem 2.

It follows that the upper bounds defined by Theorem 2 simplify to

MEDP E 2 ≤ 2 -md max 1≤u<d max µ∈F 2 m B u (µ) and MELP E 2 ≤ 2 -2md ⊥ max 1≤u<d ⊥ max µ∈F 2 m B ⊥ u (µ).
More interestingly, we now get some universal lower bound on MEDP 2 and MELP 2 , i.e., which hold for any diffusion layer with maximal branch number.

Theorem 3. Let S be a permutation of F 2 m . Then, for any F 2 m -linear diffusion layer M over (F 2 m ) t with maximal branch number d = t + 1, the MEDP 2 and MELP 2 of any block cipher E of the form SPN F (m, t, S, M) satisfy the following.

-If both S and S -1 have multiplicative-invariant derivatives, then

MEDP E 2 ≥ 2 -m(t+1) max 1≤u<d B u (0);
if both S and S -1 have a multiplicative-invariant Walsh transform, then

MELP E 2 ≥ 2 -2m(t+1) max 1≤u<d B ⊥ u (0) ;
if S has multiplicative-invariant derivatives (resp. Walsh transform), then

MEDP E 2 ≥ 2 -m(t+1) B t (0), resp. MELP E 2 ≥ 2 -2m(t+1) B ⊥ t (0).
if S -1 has multiplicative-invariant derivatives (resp. Walsh transform), then

MEDP E 2 ≥ 2 -m(t+1) B 1 (0), resp. MELP E 2 ≥ 2 -2m(t+1) B ⊥ 1 (0).
Let us focus on all permutations of F 2 8 of the same form as the AES Sbox: S(x) = A(x 254 ), where A is an F 2 -affine permutation of F 2 8 . Since S -1 has multiplication-invariant derivatives and Walsh transform (cf. Prop. 4), we derive from Theorems 2 and 3, and Prop. 6 that, for t = 4,

2 -40 B 1 (0) ≤ MEDP 2 ≤ 2 -40 max 1≤u≤4 max µ∈F * 2 8 B u (µ) and 2 -80 B ⊥ 1 (0) ≤ MELP 2 ≤ 2 -80 max 1≤u≤4 max µ∈F * 2 8
B ⊥ u (µ) .

These bounds do not depend on the isomorphism between F 8 2 and F 2 8 since their expressions do not involve any multiplication in F 2 8 , while this was not the case of the more general bound in Theorem 2. Then, we get the following results for different choices of the affine permutation A.

-For the affine function A used in the AES, SPN F (8, 4, S, M) satisfies 53×2 -34 ≤ MEDP 2 ≤ 55.5×2 -34 and 1.638×2 -28 ≤ MELP 2 ≤ 1.86×2 -28 for any F 2 8 -linear MDS diffusion layer M and any isomorphism between F 2 8 and F 8 2 . The exact values for the diffusion layer used in the AES correspond to the lower bounds in both cases. But, we have exhibited in Prop. 3 an MDS diffusion layer for which MELP 2 ≥ 1.66 × 2 -28 . Then, the choice of the MDS linear layer affects the value of MELP 2 within this interval.

-For the affine function A used in SHARK [START_REF] Rijmen | The Cipher SHARK[END_REF] and Square [START_REF] Daemen | The Block Cipher Square[END_REF] which are two predecessors of the AES, SPN F (8, 4, S, M) satisfies

53×2 -34 ≤ MEDP 2 ≤ 56×2 -34 and 1.7169×2 -28 ≤ MELP 2 ≤ 1.9847×2 -28
for any F 2 8 -linear MDS diffusion layer M. Then, the affine function chosen in the AES Sbox offers a slightly better guarantee than the one chosen in Square. Indeed, it is impossible with the Square affine function to obtain a two-round MELP which is as small as the one of the AES. Note that the isomorphism between F 8 2 and F 2 8 is different in Square and in the AES [START_REF] Barreto | Implementation of the SQUARE block cipher[END_REF]. -We have exhibited a linear permutation A of F 8 2 for which the corresponding Sbox is such that SPN F (8, 4, S, M) satisfies

MEDP 2 = 56 × 2 -34 and 1.8354 × 2 -28 ≤ MELP 2 ≤ 1.8684 × 2 -28
for any F 2 8 -linear MDS diffusion layer M. Then, this Sbox always provides a higher two-round MEDP than the AES Sbox.

Even if we are not able to explicitly construct an affine permutation A which minimizes the values of MEDP 2 and MELP 2 , our results clearly simplify the task of the designer. Indeed, the affine permutation A and the diffusion layer M can be chosen separately since a very good estimate of MEDP 2 and MELP 2 is obtained independently of the diffusion layer. This is more efficient than computing these values for many pairs (A, M ).

Involutions with some multiplicative invariance

A particular case of interest is when S is an involution with multiplicativeinvariant derivatives (or Walsh transform). Then, the lower bound in the previous theorem corresponds to the upper bound in Theorem 2, and both values are equal to the FSE 2003 bound.

Corollary 2. Let S be an involution of F 2 m with multiplicative-invariant derivatives (resp. Walsh transform). Then, for any t and any F 2 m -linear diffusion layer M over F t 2 m with branch number t + 1, any block cipher of the form SPN F (m, t, S, M) satisfies

MEDP E 2 = 2 m(t+1) max α∈F * 2 m γ∈F * 2 m δ F (α, γ) t+1 , resp. MELP E 2 = 2 2m(t+1) max α∈F * 2 m γ∈F * 2 m W F (α, γ)

Conclusions

We have improved the general upper bounds on the two-round MEDP and MELP for a given Sbox over F m 2 and any F 2 m -linear diffusion layer with given branch numbers. One of the main properties of these new bounds is that they are not invariant under affine equivalence, and then they enable the designers to choose an appropriate Sbox within an equivalence class, independently of the diffusion layer. These bounds point out the importance of some interactions between the Sbox and its inverse. In particular, the involutions play a special role since there always exists some diffusion layer for which both MEDP 2 and MELP 2 achieve the highest possible value we can obtain for an Sbox in the same equivalence class. Also, we have shown that, for the Sboxes with multiplicative-invariant derivatives or Walsh transform, we can compute a lower bound on MEDP 2 and MELP 2 independently of the choice of the MDS diffusion layer. This result applies for instance to all Sboxes of the form x → A(x s ), as in the AES. In particular, we have proved that, independently of the specifications of the MDS diffusion layer, the naive Sbox leads to the highest possible MEDP 2 and MELP 2 . The exact MEDP 2 and MELP 2 may even vary with the basis used for defining F 2 m . Our work then raises several open questions. We have shown that involutional power permutations are the weakest Sboxes in their equivalence class whatever MDS linear layer is chosen. For involutions which do not have any multiplicativeinvariant property, this result holds but for some MDS layers only. Then, it would be interesting to determine whether this weakness is more general, and whether an involution is always the worst choice within an equivalent class. This issue is of practical interest since involutional Sboxes are a natural choice for minimizing the implementation overhead of decryption on top of encryption. Another open question is whether the use of an involutional Sbox, especially of the naive Sbox, introduces a similar weakness for a higher number of rounds, in the sense of the conjecture in [START_REF] Daemen | Computational aspects of the expected differential probability of 4-round AES and AES-like ciphers[END_REF]. The difficulty comes from the fact that, exactly as for the FSE 2003 bound, applying our upper bound twice successively requires the knowledge of the whole difference table of the superbox. Our new bound can then be combined with (1) only, to get a bound of the 4-round MEDP and MELP.

A Proofs of Theorem 2, Prop. 2 and 6, and Theorem 3

The new upper bounds on MEDP 2 and MELP 2 exploit the particular structure of the codewords in an F 2 m -linear code, which is related to the notion of bundle introduced in [START_REF] Daemen | Understanding Two-Round Differentials in AES[END_REF]. In particular, we use the structure of the subsets of the code of the following form. Definition 8. Consider a word c of length n and a subset I ⊆ {1, . . . , n}. The decomposition of c with respect to I is denoted by (x, y) I : x corresponds to the restriction of c to I, and y corresponds to the restriction of c to the complement subset Ī. For the sake of simplicity, the |I| coordinates of x (resp. the coordinates of y) will be indexed by the elements of I (resp. of Ī), i.e., x i = c i for all i ∈ I and y j = c j for all j ∈ Ī. either Z(I, 0) is empty or there exists some y 0 ∈ (F * 2 m ) d such that Z(I, 0) = {γy 0 , γ ∈ F 2 m }; -For any x = 0, either Z(I, x) is empty or there exist some y 0 ∈ (F * 2 m ) d and some y 1 ∈ (F 2 m ) d such that Z(I, x) ⊆ {y 1 + γy 0 , γ ∈ F 2 m }.

Proof. -Assume that Z(I, 0) is not empty. Since C is F 2 m -linear, for any y 0 ∈ Z(I, 0), (0, y 0 ) I belongs to C, implying that all γ(0, y 0 ) I with γ ∈ F 2 m belong to C too. -Let x = 0. Since the result obviously holds if |Z(I, x)| ≤ 1, we suppose that |Z(I, x)| ≥ 2. For any distinct y and y in Z(I, x), we get that both c = (x, y) I and c = (x, y ) I belong to C, implying that (y + y ) ∈ Z(I, 0). From the previous result, there exists some y 0 such that y+y = γy 0 for some γ ∈ F 2 m . It follows that y is of the form y = y + γy 0 . Since wt(c + c ) = wt(y + y ) cannot be less than d, all coordinates of y 0 should be nonzero.

A.1 Proofs of Theorem 2 and Proposition 2

As in [START_REF] Park | Improving the Upper Bound on the Maximum Differential and the Maximum Linear Hull Probability for SPN Structures and AES[END_REF], we will use the following generalized version of Hölder inequality. Theorem 4. Let m and t be two positive integers. Let Λ be a 2 m × 2 m matrix with coefficients Λ(α, β), (α, β) ∈ (F 2 m ) 2 in [0; 1] such that Λ(α, 0) = Λ(0, α) = 0 for any α = 0, and

β∈F 2 m Λ(α, β) = β∈F 2 m Λ(β, α) = 1, for all α ∈ F 2 m .
Then, for any F 2 m -linear code C of length (2t) with minimum distance d and for any nonzero a and b in F t 2 m , we have:

Λ a,b = c∈C t i=1 Λ(a i , c i )   t j=1 Λ(c t+j , b j )   ≤ max 1≤u<d max µ∈F 2 m B u (µ) where B u (µ) = max α,β,λ∈F * 2 m γ∈F * 2 m Λ(α, γ) u Λ(γλ + µ, β) d-u .
Proof. Let a, b be nonzero elements of (F 2 m ) t . For any codeword c such that Supp

I 1 ∪ {t + j, j ∈ I 2 }). Then, for Z(I, y) = {x : (y, x) I ∈ C}, Λ a,b = y∈F n-d 2 m   i ∈I1 Λ(a i , y i )     j ∈I2 Λ(y t+j , b j )   Q a,b (I, y) (5)
where

Q a,b (I, y) = x∈Z(I,y) i∈I1 Λ(a i , x i )   j∈I2 Λ(x t+j , b j )   .
We aim at finding an upper bound on Q a,b (I, y).

Let u = |I 1 |. From Lemma 3, Q a,b (I, y) = x∈Z(I,y) i∈I1   Λ(ai, x i )   j∈I2 Λ(x t+j , b j )   1 u    ≤ i∈I1   x∈Z(I,y) Λ(a i , x i ) u   j∈I2 Λ(x t+j , b j )     1 u
.

For any i ∈ I 1 , we apply Lemma 3 again:

x∈Z(I,y) Λ(a i , x i ) u   j∈I2 Λ(x t+j , b j )   = x∈Z(I,y) j∈I2 Λ(a i , x i ) u d-u Λ(x t+j , b j ) ≤ j∈I2   x∈Z(I,y) Λ(a i , x i ) u Λ(x t+j , b j ) d-u   1 d-u Now, we know from Lemma 2 that, if Z(I, y) = ∅, there exist α ∈ (F * 2 m ) d and β ∈ (F 2 m ) d such that Z(I, y) ⊆ {γα + β, γ ∈ F 2 m }.
Then, for any pair (i, j) ∈ I 1 × I 2 , we can write:

x∈Z(I,y) Λ(a i , x i ) u Λ(x t+j , b j ) d-u ≤ γ∈F 2 m Λ(a i , γα i + β i ) u Λ(γα t+j + β t+j , b j ) d-u = γ ∈F * 2 m Λ(a i , γ ) u Λ(γ λ + µ, b j ) d-u ,
where the last equality is obtained by replacing γα i + β i by γ since α i = 0, and by setting λ = α t+j α -1 i and µ = β t+j + α t+j α -1 i β i . Moreover the sum can be taken over all nonzero γ since Λ(a i , γ ) = 0 for γ = 0. Let

B u = max a,b,λ∈F * 2 m max µ∈F 2 m γ∈F * 2 m Λ(a, γ) u Λ(γλ + µ, b) d-u .
Then, we get

Q a,b (I, y) ≤ i∈I1 j∈I2   x∈Z(I,y) Λ(a i , x i ) u Λ(x t+j , b j ) d-u   1 u(d-u) ≤ B u(d-u) u(d-u) u = B u . Using (5) and β∈F 2 m Λ(α, β) = α∈F 2 m Λ(α, β) = 1, we eventually deduce Λ a,b = y∈F n-d 2 m   i ∈I1 Λ(a i , y i )     j ∈I2 Λ(y t+j , b j )   Q a,b (I, y) ≤ B u y∈F n-d 2 m   i ∈I1 Λ(a i , y i )     j ∈I2 Λ(y t+j , b j )   ≤ B u .
B u (µ) ≤ max   max a∈F * 2 m γ∈F * 2 m Λ(a, γ) d , max b∈F * 2 m γ∈F * 2 m Λ(γ, b) d   . Moreover, if Λ(α, β) = Λ(β, α) for any (α, β) ∈ (F 2 m ) 2 , we have that, for any 1 ≤ u < d, max µ∈F 2 m B u (µ) = B u (0) = max a∈F * 2 m γ∈F * 2 m Λ(a, γ) d = max b∈F * 2 m γ∈F * 2 m Λ(γ, b) d .
Proof. Lemma 2 implies that, for any set of p sequences {x We now prove that for any mapping S = S • A where A is an F 2 -affine permutation of F 2 m and S : x → x s , both the derivatives of S and its Walsh transform are multiplicative-invariant.

Proof. From Lemma 1, it is known that It is known that all crooked permutations are APN and almost bent [START_REF] Bending | Crooked Functions, Bent Functions, and Distance Regular Graphs[END_REF], and exist for m odd only. Clearly, any quadratic APN permutation is crooked. And it is highly conjectured that the crooked functions exactly correspond to the quadratic APN functions. This has been proved in [START_REF] Kyureghyan | Crooked maps in F2n[END_REF] in the case of monomial functions and in [START_REF] Bierbrauer | Crooked binomials. Designs[END_REF] in the case of binomials. Now we can prove the following. Proposition 9. Let S be a crooked permutation. Then, S has multiplicativeinvariant derivatives and S -1 has a multiplicative-invariant Walsh transform.

Proof. Since S is a permutation, for any nonzero a, D a S cannot vanish implying that Im(D a S) is an affine hyperplane. Moreover, it is known that the (2 m -1) affine hyperplanes corresponding to Im(D a S) for all a = 0 are distinct [START_REF] Canteaut | Decomposing bent functions[END_REF]Lemma 5]. Therefore, there exists a permutation ϕ of F 2 m with ϕ(0) = 0 such that Im(D a S) = F 2 m \ ϕ(a) ⊥ for any nonzero a. Moreover, it is known (see e.g. [START_REF] Blondeau | New Links between Differential and Linear Cryptanalysis[END_REF]) that, for u, v ∈ F * where the last equality uses the fact that ϕ -1 (v) = 0 when v = 0. It follows that W 2 F (xy, v) = 2 m -2 m (-1) Tr(xyϕ -1 (v)) = 2 m -2 m (-1) Tr(yϕ -1 (πx(v))) where π x (v) = ϕ(xϕ -1 (v)). Moreover, for any nonzero x, π x is a permutation.

Fig. 1 .

 1 Fig. 1. The AES superbox.

Definition 4 .

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

4. 1

 1 Generalizing the multiplicative property Definition 7. Let S be a mapping of F 2 m .

Lemma 2 .

 2 Let C be a linear code of length n, dimension k and minimum distance d over F 2 m . For any subset I ⊂ {1, . . . , n} of size (n -d), and any x ∈ (F 2 m ) n-d , we define Z(I, x) = {y : (x, y) I ∈ C} . Then, for any I of size (n -d),

Lemma 3 .

 3 [41, Lemma 1] Let {x (j) i } n i=1 , 1 ≤ j ≤ p,be p sequences of n real numbers. prove the following generic version of Theorem 2.

  (c) = Supp(a, b), there exists ∈ {1, . . . , t} such that Λ(a , c ) = 0 or Λ(c t+ , b ) = 0. Then, Λ a,b = c∈C:Supp(c)=Supp(a,b) We assume that wt(a) + wt(b) ≥ d, otherwise the value Λ a,b is equal to zero, as there is no c ∈ C such that Supp(c) = Supp(a, b). Then we can choose a pair of subsets I 1 and I 2 of {1, . . . , t} such that I 1 ⊆ Supp(a), I 2 ⊆ Supp(b) and |I 1 | + |I 2 | = d. We decompose any codeword c whose support equals Supp((a, b)) into two parts: c = (y, x) I where I = ({1, . . . , t} \ I 1 ) ∪ {t + j, j ∈ I 2 }. In other words, y corresponds to the restriction of c to the positions outside I 1 and I 2 , while x corresponds to the other d positions. Recall that, following Definition 8, the coordinates of y (resp. of x) are indexed by the elements of I (resp. of

Theorem 2 Proposition 7 .

 27 is derived by observing that, up to a constant factor, Λ a,b = EDP 2 (a, M(b)) for Λ(α, β) = 2 -m δ F (α, β) and C is the code C M defined in Definition 5, while Λ a,b = ELP 2 (a, (M * ) -1 (b)) for Λ(α, β) = 2 -2m W F (α, β) 2 when C is the code C ⊥ M and M * denotes the adjoint of M. In the same way, we now prove the following generic version of Prop. 2. Let m and d be two positive integers and Λ be a 2 m ×2 m matrix satisfying the same hypotheses as in Theorem 4. Then, for any 1 ≤ u < d and any µ ∈ F 2 m , we have

- 1 cic - 1 t+1(- 1 ct+j c - 1 1(

 1111 C any F 2 m -linear code of length 2t, dimension t and d min = t + 1. Then, If both (i) and (ii) hold, then M Λ ≥ max 1≤u<d B u (0).-If (i) holds, then M Λ ≥ B t (0). -If (ii) holds, then M Λ ≥ B 1 (0).Proof. For any fixed u, 1 ≤ u ≤ t, we consider α, β ∈ F * 2 m some values for whichγ∈F * 2 m Λ( α, γ) u Λ(γ, β) (d-u) = B u (0) .Since C is MDS, any set of (t + 1) positions is the support of a minimum-weight codeword[START_REF] Macwilliams | The theory of error-correcting codes[END_REF] Page 319]. Let then c ∈ C with support I = {1, . . . , u} ∪ {t + 1, . . . , 2t + 1 -u}. From Lemma 2, we know that the codewords with support I are the elements γc, γ ∈ F * 2 m . We now examine the 3 cases. -If both (i) and (ii) hold, then for any pair (a, b), we haveΛ a,b =We choose a and b as a i = π -1 ci ( α) for 1 ≤ i ≤ u, a i = 0 otherwise, and b j = ψ -1 ct+j ( β) for 1 ≤ j ≤ t + 1 -u, b j = 0 otherwise. Then, for these values, u (0) .Since such a pair (a, b) can be defined for any 1 ≤ u < d, we deduce that M Λ ≥ max 1≤u<d B u (0). -If only (i) holds, then we consider u = t and we define a and b by a i = π -α) for 1 ≤ i ≤ t, b 1 = β and b j = 0 for j > 1. Then, we getΛ a,b = i , γc i ) Λ(γc t+1 , b 1 ) = i , γ c i c -1 t+1 ) Λ(γ , b 1 ) γ ) t Λ(γ , β) = B t(0) . If only (ii) holds, then we choose u = 1 and define a and b by a 1 = α, a i = 0 for i > 1, and b j = ϕ -β) for 1 ≤ j ≤ t. Then we get that Λ a,b = B 1 (0) B Proofs of Propositions 4 and 5

(- 1 )(- 1 )

 11 δ S F (a, b) = δ S F (L(a), b) and W S F (a, b) 2 = W S F ((L -1 ) * (a), b) 2 , where L : x → A(x) + A(0). Since S (x) = x s , we have δ S F (a, bc) = #{x ∈ F 2 m , (x + a) s + x s = bc} = #{x ∈ F 2 m , c -e x + c -e a s + (c -e x) s = b} = δ S F (c -e a, b) where x → x e is the compositional inverse of S , i.e., e is the inverse of s modulo (2 m -1), and W S F (a, bc) = x∈F 2 m Tr(bcx s +ax) = x∈F 2 m Tr(by s +ac -e y) = W S F (c -e a, b) . Therefore, it follows that δ S F (a, bc) = δ S F (c -e L(a), b) = δ S F (π c (a), b) with π c (a) = L -1 (c -e L(a)) , and W S F (a, bc) = W S F (c -e (L -1 ) * (a), b) 2 = W S F (ψ c (a), b) with ψ c (a) = L * (c -e (L -1 ) * (a)), since (L -1 ) * = (L * ) -1 . Clearly, both π c and ψ c are permutations for any nonzero c. Now, we prove a generalized version of Prop. 5, which applies to a (possibly) larger family of mappings named crooked permutations. Definition 9. [3] A function S from F 2 m into F 2 m is said to be crooked if, for any nonzero α ∈ F 2 m , Im(D α S) is a linear or affine subspace of codimension 1, where D α S : x → S(x + α) + S(x).

2 m , W 2 F(- 1 )(- 1 ) 2 F(- 1 )= 2 m

 211212 (u, v) = a,b∈F 2 m Tr(au+bv) δ F (a, b) = 2 m + a,b∈F 2 m ,a =0 Tr(au+bv) δ F (a, b).The differential spectrum of S is determined by ϕ: for any a = 0, δ F (a, b) = 1 -(-1) Tr(ϕ(a)b) . Then, for any v = 0, we getW (u, v) = 2 m + a,b∈F 2 m ,a =0 (-1) Tr(au+bv)a,b∈F 2 m ,a =0 (-1) Tr(au+bv+ϕ(a)b) Tr(b(v+ϕ(a)))   -2 m (-1) Tr(uϕ -1 (v))

  -34 and MELP 2 = 109, 953, 193 × 2 -54 ≈ 1.638 × 2 -28 . But, if the AES Sbox is replaced by the socalled naive Sbox[START_REF] Daemen | Computational aspects of the expected differential probability of 4-round AES and AES-like ciphers[END_REF], obtained by removing the affine permutation from the AES Sbox, MEDP 2 = 79 × 2 -34[START_REF] Daemen | Understanding Two-Round Differentials in AES[END_REF] which corresponds to the FSE 2003 bound. To our best knowledge, the exact value of MELP 2 for the naive Sbox has not been computed, but we will deduce from our results in Section 4.3 that, for the multiplicative inverse over F 2 m and any MDS F 2 m -linear layer, the FSE 2003 bound is always tight. In particular, for m = 8, MELP 2 = 192, 773, 764 × 2 -54 ≈ 2.873×2 -28 . Then, the AES Sbox provides a better resistance against differential and linear cryptanalyses for two rounds of the AES than the naive Sbox. More generally, it has been conjectured in[17, Conjecture 1] that, for any number of rounds r, MEDP r is smaller for the AES Sbox than for the naive Sbox.

  2(t+1) . naive Sbox, i.e. the inversion in F 2 m , satisfies all hypotheses of the previous corollary. The exact values of MEDP 2 and MELP 2 for an SPN combining the naive Sbox over F 2 m and any F 2 m -linear layer with maximal branch number are then always equal to the FSE 2003 bounds. For instance, for the two-round AES with the naive Sbox, we have MEDP 2 = 79 × 2 -34 and MELP 2 = 48, 193, 409 × 2 -52 , and this is independent of the F 2 8 -linear MDS layer. In particular, the exact MEDP 2 and MELP 2 do not depend on the field representation since Coro. 2 provides the same value for any basis. Also, this explains why, among all Sboxes in the same equivalence class, the naive Sbox is the one which leads after two rounds both to the highest MEDP and to the highest MELP for any F 2 m -linear diffusion layer with maximal branch number. And this situation is independent of the size of the Sbox, and of the choice of the F 2 m -linear MDS layer.

	The

Here, the terminology substitution-permutation has to be understood in a broad sense without any restriction on the linear permutation, while in some other papers, it is limited to the class of bit permutations.

We here focus on the MEDP and MELP of the SPN with the same building blocks as the Prøst permutation, but these expectations do not provide any direct information on the security of the Prøst permutation in which the key is fixed.

As for Prøst, this result does not directly apply to LED since the round keys are inserted every four rounds only.

Acknowledgments. The authors would like to thank Daniel Augot, Matthieu Finiasz, María Naya Plasencia for valuable discussions, and the reviewers for their constructive comments.

Partially supported by the French Agence Nationale de la Recherche through the BLOC project under Contract ANR-11-INS-011. c IACR 2015. This article is the final version submitted by the authors


Herbert Bruderer
email: bruderer@retired.ethz.ch

Keywords: History of computing, pocket-sized mechanical parallel calculator, discovery

The Austrian engineer Curt Herzstark invented the world-renowned mechanical pocket calculator Curta. The books and the papers on the history of computing mention two models, Curta 1 and Curta 2. In November 2015 original drawings and patent documents on a multiple Curta were discovered in Switzerland. This device is supposed to be the world's smallest mechanical parallel calculator.

Herzstark's Legacy: Discovery of Unknown Machine

On 14 November 2015 I examined the legacy of Curt Herzstark. It is located at the typewriter museum Beck at Pfäffikon near Zurich. To my great surprise I found original drawings and patent documents of an unknown multiple calculating machine: the world's smallest mechanical parallel calculator. Curt Herzstark, a highly gifted Austrian engineer, was forced by the Nazis to design the construction drawings for the world-famous Curta at the concentration camp of Buchenwald. The Curta is the smallest and most successful mechanical calculating machine which is able to perform all four basic arithmetic operations. Today, these pretty "pepper mills" are still working. They inspire specialists as well as laymen. From 1947 to 1971 this engineering marvel was produced in large quantities at Mauren (Liechtenstein). Up to now we knew two marks of the stepped drum machine, the Curta 1 and the Curta 2.

According to the patent documents recently turned up any number of mechanical cylindrical calculators may be combined. Herzstark describes the following forms:  two Curtas side by side,  two Curtas one upon another,  four Curtas side by side,  five Curtas in a circle.

Characteristic Features of the Multiple Calculating Machine

The parallel calculator excels in the following properties:

 All machines are driven by one single, common crank.  All devices may be switched (by axial shifting of the driving shaft) in common or alone to another basic arithmetic operation. This is possible even if the individual machines are set up for different arithmetic operations.  All registers may be shifted (decade by decade) in common or alone in both rotating directions.  All result registers and/or revolution counters may be cleared in common or alone.  The multiple calculation machine can be equipped with an electric drive.

Double, Fourfold and Fivefold Curta

The extraordinary find proves that the Viennese inventor did not only design single but also multiple Curtas.

Acceleration of the Arithmetic Operations

The high-precision Curta masters all four elementary arithmetic operations. Thanks to the linkage of several devices computations are considerably speeded up. For instance, if you use a fourfold Curta you input the values 137, 263, 389 and 491. Then you multiply all factors with 7. The four multiplications are carried out at the same time (with 7 rotations of the crank). The numbers 623, 511, 301 and 259 can be divided by 7 all at once. Potential applications are the simultaneous conversion of a price list referring to various rates of exchange, the determination of the coordinates x and y in surveying at one blow, and computing at the same time the prices by the piece of goods.

The World's Smallest Mechanical Parallel Calculator

To my knowledge the multiple Curta is the smallest mechanical calculating machine in the world, the first pocket-sized mechanical parallel calculator.

The patent documentation contains comprehensive descriptions. Curt Herzstark presumably built some prototypes. I conducted several oral history interviews with six elderly eye witnesses in Liechtenstein, Austria, Germany and Switzerland. Unfortunately they do not remember the inventor's corresponding research work. The multiple calculating machine was not mass-produced. Herzstark who was defrauded of his lifework by the Nazis had already left his manufacturing firm Contina AG at this time. There is a plans to rebuild the multiple Curta. In order to simplify the handling the Austrian engineer designed another type of construction for of the double Curta with a base plate (additional patent). The patent application does not mention the following variation with four cylindrical machines.

Fig. 1 .

 1 Fig. 1. Double Curta 1. The drawing shows a rigid rod-shaped connection of both machines. According to the patent application more than two devices may be piled up (© Österreichisches Patentamt, Wien, Stammpatent 1954/57).

Fig. 2 .

 2 Fig. 2. Double Curta 2. The original drawing presents two mechanical pocket calculators situated side by side. The crank moves the main driving shafts of both devices through bevel and spur wheels. An alternative is a chain drive (© Schreibmaschinenmuseum Beck, Pfäffikon ZH/Bruderer Informatik, CH-9401 Rorschach 2016).

Fig. 3 .

 3 Fig. 3. Fourfold Curta. This original drawing depicts four removable Curtas mounted on a pedestal. The latter is provided with coupling, drive and control organs. The common crank is connected to the stepped drum shafts by a chain drive (© Schreibmaschinenmuseum Beck, Pfäffikon ZH/Bruderer Informatik, CH-9401 Rorschach 2016).

Fig. 4 .

 4 Fig. 4. Fivefold Curta. The five pocket calculating machines stand on a revolving pedestal which is attached on a circular base plate. Thus the setting mechanisms of the five devices can be comfortably manipulated. The principal driving shaft (in the middle) with the crank is connected through spur wheels with the five stepped drum shafts (© Österreichisches Patentamt, Wien, Stammpatent 1954/57).

Acknowledgment. The author is very grateful to Stefan Beck from the typewriter museum in Pfäffikon near Zurich.