Daniel Augot
email: daniel.augot@inria.fr

Pierre-Alain Fouque
email: pierre-alain.fouque@irisa.fr

Pierre Karpman
email: pierre.karpman@inria.fr

Diffusion Matrices from Algebraic-Geometry Codes with Efficient SIMD Implementation ⋆

Keywords: Diffusion matrix, algebraic-geometry codes, algebraic curves, SIMD, vector implementation, SHARK

This paper investigates large linear mappings with very good diffusion and efficient software implementations, that can be used as part of a block cipher design. The mappings are derived from linear codes over a small field (typically F 2 4 ) with a high dimension (typically 16) and a high minimum distance. This results in diffusion matrices with equally high dimension and a large branch number. Because we aim for parameters for which no MDS code is known to exist, we propose to use more flexible algebraicgeometry codes. We present two simple yet efficient algorithms for the software implementation of matrix-vector multiplication in this context, and derive conditions on the generator matrices of the codes to yield efficient encoders. We then specify an appropriate code and use its automorphisms as well as random sampling to find good such matrices. We provide concrete examples of parameters and implementations, and the corresponding assembly code. We also give performance figures in an example of application which show the interest of our approach.

Introduction

The use of MDS matrices over finite fields as a linear mapping in block cipher design is an old trend, followed by many prominent algorithms such as the AES/Rijndael family [START_REF] Daemen | The Design of Rijndael: AES -The Advanced Encryption Standard[END_REF]. These matrices are called MDS as they are derived from maximum distance separable linear error-correcting codes, which achieve the highest minimum distance possible for a given length and dimension. This notion of minimum distance coincides with the one of branch number of a mapping [START_REF] Daemen | The Design of Rijndael: AES -The Advanced Encryption Standard[END_REF], which is a measure of the effectiveness of a diffusion layer. MDS matrices thus have an optimal diffusion, in a cryptographic sense, which makes them attractive for cipher designs.

The good security properties that can be derived from MDS matrices are often counter-balanced by the cost of their computation. The standard matrix-vector product is quadratic in the dimension of the vector, and finite field operations are not always efficient. For that reason, there is often a focus on finding matrices allowing efficient implementations. For instance, the AES matrix is circulant and has small coefficients. More recently, the PHOTON hash function [START_REF] Guo | The PHOTON Family of Lightweight Hash Functions[END_REF] introduced the use of matrices that can be obtained as the power of a companion matrix, which sparsity may be useful in lightweight hardware implementations. The topic of finding such so-called recursive diffusion layers has been quite active in the past years, and led to a series of papers investigating some of their various aspects [START_REF] Sajadieh | Recursive Diffusion Layers for Block Ciphers and Hash Functions[END_REF][START_REF] Wu | Recursive Diffusion Layers for (Lightweight) Block Ciphers and Hash Functions[END_REF][START_REF] Augot | Exhaustive Search for Small Dimension Recursive MDS Diffusion Layers for Block Ciphers and Hash Functions[END_REF]. One of the most recent developments shows how to systematically construct some of these matrices from BCH codes [START_REF] Augot | Direct Construction of Recursive MDS Diffusion Layers using Shortened BCH Codes[END_REF]. This allows in particular to construct very large recursive MDS matrices, for instance of dimension 16 over F 2 8 . This defines a linear mapping over a full 128-bit block with excellent diffusion properties, at a moderate hardware implementation cost.

As interesting as it may be in hardware, the cost in software of a large linear mapping tends to make these designs rather less attractive than more balanced solutions. An early attempt to use a large matrix was the block cipher SHARK, a Rijndael predecessor [START_REF] Rijmen | The Cipher SHARK[END_REF]. It is a 64-bit cipher which ⋆ A shorter version of this paper is to appear in the proceedings of SAC 2014.

uses an MDS matrix of dimension 8 over F 2 8 for its linear diffusion. The usual technique for implementing such a mapping in software is to rely on a table of precomputed multiples of the matrix rows. However, table-based implementations now tend to be frown upon as they may lead to timing attacks [START_REF] Tromer | Efficient Cache Attacks on AES, and Countermeasures[END_REF], and this could leave ciphers with a structure similar to SHARK's without reasonable software implementations when resistance to these attacks is required. Yet, such designs also have advantages of their own; their diffusion acts on the whole state at every round, and therefore makes structural attacks harder, while also ensuring that many S-Boxes are kept active. Additionally, the simplicity of the structure makes it arguably easier to analyze than in the case of most ciphers.

Our contributions. In this work, we revisit the use of a SHARK structure for block cipher design and endeavour to find good matrices and appropriate algorithms to achieve both a linear mapping with very good diffusion and efficient software implementations that are not prone to timing attacks. To be more specific on this latter point, we target software running on 32 or 64-bit CPUs featuring an SIMD vector unit.

An interesting way of trying to meet both of these goals is to decrease the size of the field from F 2 8 to F 2 4 . However, according to the MDS conjecture, there is no MDS code over F 2 4 of length greater than 17, and no such code is known [START_REF] Macwilliams | The Theory of Error-Correcting Codes[END_REF]. Because a diffusion matrix of dimension n is typically obtained from a code of length 2n, MDS matrices over F 2 4 are therefore restricted to dimensions less than 8. Hence, the prospect of finding an MDS matrix over F 2 4 diffusing on more than 8 × 4 = 32 bits is hopeless. Obviously, 32 bits is not enough for a large mapping à la SHARK. We must therefore search for codes with a slightly smaller minimum distance in the hope that they can be made longer.

Our proposed solution to this problem is to use algebraic-geometry codes [START_REF] Van Lint | Introduction to Coding Theory[END_REF], as they precisely offer this tradeoff. One way of defining these codes is as evaluation codes on algebraic curves; thus our proposal brings a nice connection between these objects and symmetric cryptography. Although elliptic and hyperelliptic curves are now commonplace in public-key cryptography, we show a rare application of an hyperelliptic curve to the design of block ciphers. We present a specific code of length 32 and dimension 16 over F 2 4 with minimum distance 15, which is only 2 less than what an MDS code would achieve. This lets us deriving a very good diffusion matrix on 16 × 4 = 64 bits in a straightforward way. Interestingly, this matrix can also be applied to vectors over an extension of F 2 4 such as F 2 8 , while keeping the same good diffusion properties. This allows for instance to increase the diffusion to 16 × 8 = 128 bits.

We also study two simple yet efficient algorithms for implementing the matrix-vector multiplication needed in a SHARK structure, when a vector permute instruction is available. From one of these, we derive conditions on the matrix to make the product faster to compute, in the form of a cost function; we then search for matrices with a low cost, both randomly, and by using automorphisms of the code and of the hyperelliptic curve on which it is based. The use of codes automorphisms to derive efficient encoders is not new [START_REF] Heegard | Systematic Encoding via Gröbner Bases for a Class of Algebraic-Geometric Goppa Codes[END_REF][START_REF] Chen | A Serial-In-Serial-Out Hardware Architecture for Systematic Encoding of Hermitian Codes via Gröbner Bases[END_REF], but it is not generally applied to the architecture and dimensions that we consider in our case.

We conclude this paper by presenting examples of performance figures of assembly implementations of our algorithms when used as the linear mapping of a block cipher.

Structure of the paper. We start with a few background notions in §2. We then present our algorithms for matrix-vector multiplication and their context in §3, and derive a cost function for the implementation of matrices. This is followed by the definition of the algebraic-geometry code used in our proposed linear mapping, and a discussion of how to derive efficient encoders in §4. We conclude with insights into the performance of the mapping when used over both F 2 4 and F 2 8 in §5.

Preliminaries

We note F 2 m the finite field with 2 m elements. We often consider F 2 4 , and implicitly use this specific field if not mentioned otherwise. W.l.o.g. we use the representation F 2 4 ∼ = F 2 [α]/(α 4 + α + 1). We freely use "integer representation" for elements of F 2 4 by writing n ∈ {0 . . . 15} = 3 i =0 a i 2 i to represent the element x ∈ F 2 4 = 3 i =0 a i α i . Bold variables denote vectors (in the sense of elements of a vector space), and subscripts are used to denote their i th coordinate, starting from zero. For instance, x = (1, 2, 7) and x 2 = 7. If M is a matrix of n columns, we call m i = (M i , j , j = 0 . . . n -1) the row vector formed from the coefficients of its i th row. We use angle brackets "〈" and "〉" to write ordered sets.

Arrays, or tables, (in the sense of software data structures) are denoted by regular variables such as x or T , and their elements are accessed by using square brackets. For instance, T [i ] is the i th element of the table T , starting from zero.

We conclude with two definitions.

Definition 2 (Branch number [6])

Let A be the matrix of a linear mapping over F 2 m , and w m (x) be the number of non-zero positions of the vector x over F 2 m . Then the differential branch number of A is equal to min x =0 (w m (x) + w m (A(x))), and the linear branch number of A is equal to

min x =0 (w m (x) + w m (A t (x))).
Note that if A is such that (I k A) is a generator matrix of a code of minimum distance d which dual code has minimum distance d ′ , then A has a differential (resp. linear) branch number of d (resp. d ′ ).

Efficient algorithms for matrix-vector multiplication

This section presents software algorithms for matrix-vector multiplication over F 2 4 . We focus on square matrices of dimension 16. This naturally defines linear operations on 64 bits, which can also be extended to 128 bits, as it will be made clear in §5. Both cases are a common block size for block ciphers.

Targeted architecture. The algorithms in this section target CPUs featuring vector instructions, including in particular a vector shuffle instruction such as Intel's pshufb from the SSSE3 instruction set extension [START_REF]Intel® 64 and IA-32 Architectures Software Developer's Manual[END_REF]. These instructions are now widespread and have already been used successfully in fast cryptographic implementations, see e.g. [START_REF] Hamburg | Accelerating AES with Vector Permute Instructions[END_REF][START_REF] Suzaki | TWINE: A Lightweight Block Cipher for Multiple Platforms[END_REF][START_REF] Benadjila | Implementing lightweight block ciphers on x86 architectures[END_REF]. We mostly considered SSSE3 when designing the algorithms, but other processor architectures do feature vector instructions. This is for instance the case of ARM's NEON extensions, which may also yield efficient implementations, see e.g. [START_REF] Bernstein | NEON Crypto[END_REF]. We do not consider these explicitly in this paper, however.

Because it plays an important role in our algorithms, we briefly recall the semantics of pshufb. The pshufb instruction takes two 128-bit inputs 1 . The first (the destination operand) is an xmm SSE vector register which logically represents a vector of 16 bytes. The second (the source operand) is either a similar xmm register, or a 128-bit memory location. The result of calling pshufb x y is to overwrite the input x with the vector x ′ defined by:

x ′ [i ] = x[⌊y[i ]⌋ 4 ] if the most significant bit of y[i ] is not set 0 otherwise
where ⌊•⌋ 4 denotes truncation to the 4 least significant bits. This instruction allows to arbitrarily shuffle a vector according to a mask, with possible repetition and omission of some of the vector values 2 . Notice that this instruction can also be used to perform 16 parallel 4-to-8-bit table lookups:

let us call T this table; take as first operand to pshufb the vector x = (T [i ], i = 0 . . . 15), as second operand the vector y = (a, b, c, d , . . .) on which to perform the lookup; then we see that the first byte of the result is

x[y[0]] = T [a], the second is x[y[1]] = T [b], etc.
Finally, there is a three-operand variant of this instruction in the more recent AVX instruction set and onward [START_REF]Intel® 64 and IA-32 Architectures Software Developer's Manual[END_REF], which allows not to overwrite the first operand.

Targeted properties. In this paper we focus solely on algorithms that can easily be implemented in a way that makes them immune to timing-attacks [START_REF] Tromer | Efficient Cache Attacks on AES, and Countermeasures[END_REF]. Specifically, we consider the matrix as a known constant but the vector as a secret, and we wish to perform the multiplication without secret-dependent branches or memory accesses. It might not always be important to be immune (or even partially resistant) to this type of attacks, but we consider that it should be important for any cryptographic primitive or structure to possibly be implemented in such a way. Hence we try to find efficient such implementations for the SHARK structure and therefore for dense matrix-vector multiplications.

We now go on to describe the algorithms. In all of the remainder of this section, x and y are two (column) vectors of F 16 2 4 , and M a matrix of M 16 (F 2 4 ). We first briefly recall the principle of table implementations, which are unsatisfactory when timing attacks are taken into account.

Table implementation

We wish to compute y = M • x. The idea behind this algorithm is to use table lookups to perform the equivalent multiplication y t = x t • M t , i.e. y t = 15 i =0 x i • (m t ) i (where (m t ) i is the i th row of M t ). This can be computed efficiently by tabulating beforehand the products λ • (m t ) i , λ ∈ F 2 4 (resulting in 16 tables, each of 16 entries of 64 bits), and then for each multiplication by accessing the table for (m t ) i at the index x i and summing all the retrieved table entries together. This only requires 16 table lookups per multiplication. However, the memory accesses depend on the value of x, which makes this algorithm inherently vulnerable to timing attacks.

Note that there is a more memory-efficient alternative implementation of this algorithm which consists in computing each term λ • (m t ) i with a single pshufb instruction instead of using a tablelookup. In that case, only the 16 multiplication tables need to be stored, but their accesses still depend on the secret value x.

A generic constant-time algorithm

We now describe our first algorithm, which can be seen as a variant of table multiplication that is immune to timing attacks. The idea consists again in computing the right multiplication

y t = x t •M t , i.e. y t = 15 i =0 x i •(m t ) i .
However, instead of tabulating the results of the scalar multiplication of the matrix rows (m t ) i , those are always recomputed, in a way that does not explicitly depend on the value of the scalar.

Description of algorithm 1. We give the full description of Alg. 1 in appendix A.1, and focus here on the intuition. We want to perform the scalar multiplication λ • z for an unknown scalar λ and a known, constant vector z, over F 2 4 . Let us write λ as the polynomial

λ 3 • α 3 + λ 2 • α 2 + λ 1 • α + λ 0 with coefficients in F 2 . Then, the result of λ • z is simply λ 3 • (α 3 • z) + λ 2 • (α 2 • z) + λ 1 • (α • z) + λ 0 • z.
Thus we just need to precompute the products α i • z, select the right ones with respect to the binary representation of λ, and add these together. This can easily be achieved thanks to a broadcast function defined as:

broadcast(x, i ) n = 1 n if the i th bit of x is set 0 n otherwise
where 1 n and 0 n denote the n-bit binary string made all of one and all of zero respectively. The full algorithm then just consists in using this scalar-vector multiplication 16 times, one for each row of the matrix.

Implementation of algorithm 1 with SSSE3 instructions. We now consider how to efficiently implement algorithm 1 in practice. The only non-trivial operation is the broadcast function, and we

show that this can be performed with only one or two pshufb instructions.

To compute broadcast(λ, i ) 64 , with λ a 4-bit value, we can use a single pshufb with first operand

x, such that x[ j ] = 11111111 2 if the i th bit of j is set and 0 otherwise, and with second operand

y = (λ, λ, λ, . . .). The result of pshufb x y is indeed (x[λ], x[λ], . . .) which is 1 64 if the i th bit of λ is set,
and 0 64 otherwise, that is broadcast(λ, i ) 64 .

In practice, the vector x can conveniently be constructed offline and stored in memory, but the vector y might not be readily available before performing this computation 3 . However, it can easily be computed thanks to an additional pshufb. Alternatively, if the above computation is done with a vector y = (λ, ?, ?, . . .) instead (with ? denoting unknown values) and call z its result (x[λ], ?, ?, . . .), then we have broadcast(λ, i ) n = pshufb z (0, 0, . . .).

In the specific case of matrices of dimension 16 over F 2 4 , one can take advantage of the 128-bit wide xmm registers by interleaving, say, 8•x with 4•x, and 2•x with x, and by computing a slightly more complex version of the broadcast function broadcast(x, i , j ) 2n which interleaves broadcast(x, i ) n with broadcast(x, j ) n . In that case, an implementation of one step of algorithm 1 only requires two broadcast calls, two logical and, folding back the interleaved vectors (which only needs a couple of logical shift and exclusive or), and adding the folded vectors together. We give a snippet of such an implementation in appendix B.1.

A faster algorithm exploiting matrix structure

The above algorithm is already reasonably efficient, and has the advantage of being completely generic w.r.t. the matrix. Yet, better solutions may exist in more specific cases. We present here an alternative that can be much faster when the matrix possesses a particular structure.

The idea behind this second algorithm is to take advantage of the fact that in a matrix-vector product, the same constant values may be used many times in finite-field multiplications. Hence, we try to take advantage of this fact by performing those in parallel. The fact that we now focus on multiplications by constants (i.e. matrix coefficients) allows us to compute these multiplications with a single pshufb instead of using the process from algorithm 1.

Description of algorithm 2. We give the full description of Alg. 2 in appendix A.2, and focus here on the intuition. Let us first consider a small example, and compute M • x defined as:

     1 0 2 2 3 1 2 3 2 3 3 2 0 2 3 1      •      x 0 x 1 x 2 x 3      . ( 1
)
It is obvious that this is equal to:

     x 0 x 1 0 x 3      + 2 •      x 2 x 2 x 0 x 1      + 2 •      x 3 0 x 3 0      + 3 •      0 x 0 x 1 x 2      + 3 •      0 x 3 x 2 0     
, where both the constant multiplications of the vector (x 0 x 1 x 2 x 3 ) t and the shuffles of its coefficients can be computed with a single pshufb instruction each, while none of these operations directly depends on the value of the vector. This type of decomposition can be done for any matrix, but the number of operations depends on the value of its coefficients.

We now sketch one way of obtaining an optimal decomposition as above. We consider a matrix product M • x with M constant and x unknown, where x is seen as the formal arrangement of variables x i . Let us define S (M , γ) as one of the minimal sets of shuffles of coefficients of x, such that there exists a unique vector z ∈ S (M , γ) with z i = x j iff M i , j = γ. For instance, in the above example, we have S (M , 2) = {(x 2 x 2 x 0 x 1 ) t , (x 3 0 x 3 0) t }. Equivalently, we could have taken S (M , 2) = {(x 3 x 2 x 3 0) t , (x 2 0 x 0 x 1 ) t }. These sets are straightforward to compute from this particular matrix, and so are they in the general case.

From the definition of S , it is clear that we have

M • x = γ∈F * 2 4 s∈S (M ,γ) γ • s.
Once the values of the sets S have been determined, it is clear that we only need to compute this sum to get our result, and this is precisely what this second algorithm does.

Cost of algorithm 2. The cost of computing a matrix-vector product with algorithm 2 depends on the coefficients of the matrix, since the size of the sets S (M , γ) depends both on the density of the matrix and of how its coefficients are arranged.

If we assume that a vector implementation of this algorithm is used, and if the dimension and the field of the matrix are well chosen, we can assume that both the scalar multiplication of x by a constant and its shuffles can be computed with a single pshufb and a few ancillary instructions.

Hence, we can define a cost function for a matrix with respect to its implementation with algorithm 2 to be cost2

(M ) = γ∈F 2 4 * 1(S (M , γ)) + # S (M , γ) -1(S (M , 1)
), where 1(E ) with E a set is one if E = , and zero otherwise. We may notice that # S (M , γ) is equal to the maximum number of occurrence of γ in a single row of M , and the cost2 function is therefore easy to compute. As an example the cost of the matrix M from equation 1 is 7.

In order to find matrices that minimize the cost2 function, we would like to minimize the sum of the maximum number of occurrence of γ for every γ ∈ F * 2 4 . A simple observation is that for matrices with the same number of non-zero coefficients, this amount is minimal when every row can be deduced by permutation of a single one; an important particular case being the one of circulant matrices. More generally, we can heuristically hope that the cost of a matrix will be low if all of its rows can be deduced by permutation of a small subset thereof.

We can try to estimate the minimum cost for an arbitrary dense circulant matrix of dimension 16 over F 2 4 . It is fair to assume that nearly all of the values of F 2 4 should appear as coefficients of such a matrix, 14 of them needing a multiplication. Additionally, 15-16 permutations are needed if all the rows are to be different. Hence we can assume that the cost2 function of such a matrix is about 30.

Finally, let us notice that special cases of this algorithm have already been used for circulant matrices, namely in the case of the AES MixColumn matrix [START_REF] Hamburg | Accelerating AES with Vector Permute Instructions[END_REF][START_REF] Benadjila | Implementing lightweight block ciphers on x86 architectures[END_REF].

Implementation of algorithm 2 with SSSE3 instructions. The implementation of algorithm 2 is quite straightforward. We give nonetheless a small code snippet in appendix B.2.

Performance

In Table 2 of §5, we give a few performance figures for ciphers with a SHARK structure using assembly implementations of algorithms 1 and 2 for their linear mapping. From there it can be seen without surprise that algorithm 2 is more efficient if the matrix is well chosen. However, algorithm 1 still performs reasonably well, without imposing any condition on the matrix.

Diffusion matrices from algebraic-geometry codes

In this section, we present so-called algebraic-geometry codes and show how they can give rise to diffusion matrices with interesting parameters. We also focus on implementation aspects, and investigate how to find matrices with efficient implementations with respect to the algorithms of §3, and in particular algorithm 2.

A short introduction to algebraic-geometry codes

We first briefly present the concept of algebraic-geometry codes (or AG codes for short), which are linear codes, and how to compute their generator matrices. Because the codes are linear, these encoders are matrices. We do not give a complete description of AG codes, and refer to e.g. [START_REF] Van Lint | Introduction to Coding Theory[END_REF] for a more thorough treatment. We present a class of AG codes as a generalization of Reed-Solomon (RS) codes. We give a quick presentation of RS codes in appendix C for the reader not familiar with them.

We see AG codes as evaluation codes: to build the codeword for a message w, we consider w as a function, and the codeword as a vector of values of this function evaluated on some "elements". In our case, the elements are points of the two-dimensional affine space A 2 (F 2 m ), and the functions are polynomials in two variables, that is elements of F 2 m [x, y]. The core idea of AG codes is to consider points of a (smooth) projective curve of the projective space P 2 (F 2 m ) and functions from the curve's function space. Points at infinity are never included in the (ordered) set of points. However, points of the curve at infinity are useful in defining the curve's function (sub)-space, which is why we do consider the curve in the projective space instead of the affine one.

We first give the definition of the Riemann-Roch space in the special case where it is defined from a divisor made of a single point at infinity. We refer to e.g. [START_REF] Stichtenoth | Algebraic Function Fields and Codes[END_REF] or [START_REF] Van Lint | Introduction to Coding Theory[END_REF] for a more complete and rigorous definition. Definition 3 (Riemann-Roch space) Let X be a smooth projective curve of P 2 (F 2 m ) defined by the homogeneous polynomial p(x, y, z), and let p ′ (x, y) be the dehomogenized of p. We define F 2 m [X ] = F 2 m [x, y]/p ′ as the coordinate ring of X , and its corresponding quotient field F 2 m (X ) as the function field of X . Assume Q is the only point of X at infinity, and let r be a positive integer. The Riemann-Roch space L (r Q) is the set of all functions of F 2 m (X ) with poles only at Q of order less than r . This is a finite-dimensional F 2 m -vector-space. Furthermore, let o Q (x) and o Q (y) be the order of the poles of x and y in Q 4 , then a basis of L (r Q) is formed by all the monomial functions x i y j that are such that i

• o Q (x) + j • o Q (y) ≤ r .
This space is particularly important because of the following theorem, which links its dimension with the genus of X [START_REF] Stichtenoth | Algebraic Function Fields and Codes[END_REF].

Theorem 1 (Riemann and Roch) Let L (r Q) be a Riemann-Roch space defined on X , and g be the genus of X . We have dim(L (r Q)) ≥ r + 1 -g , with equality when r > 2g -2.

We have also mentioned earlier that a basis for a space L (r Q) can be computed as soon as the order of the poles of x and y in Q are known, and the dimension of the space can obviously be computed from the basis. In practice, computing o Q (x) and o Q (y) can be done from a local parameterization of x and y in Q. Both this parameterization and the values o Q (x) and o Q (y) can easily be obtained from a computational algebra software such as Magma. Again, we refer to [START_REF] Van Lint | Introduction to Coding Theory[END_REF] for more details.

We are now ready to define a simple class of AG codes.

Definition 4 (Algebraic-Geometry codes) Let X be a smooth projective curve of P 2 (F 2 m ) with a unique point Q at infinity, and call #X its number of affine points (that is not counting Q). Assume that #X ≥ n and let r be s.t. dim(L (r Q)) = k, and call ( f 0 , . . . , f k-1 ) one basis of this space. We define the codeword of the [n, k, d ] F 2 m algebraic-geometry code C AG associated with the message m as the vector i =0...k-1 (m i • f i (p j ), j = 0 . . . n -1), where P = 〈p 0 , . . . , p n-1 〉 is an ordered set of points of X /{Q}. The code C AG is the set of all such codewords.

These codes have the following properties: for fixed parameters n and k and a curve X , there are #X n • n! equivalent codes, which corresponds to the number of possible ordered sets P ; it is also obvious that the maximal length of a code over X is #X . We also have the following proposition [START_REF] Van Lint | Introduction to Coding Theory[END_REF]:

Proposition 1 Let C AG

be a code of length n and dimension k, and let r be an integer such that

dim(L (r Q)) = k. Then the minimum distance of C AG is at least n-r . If X is of genus g and r > 2g -2, this is equal to n -((k -1) + g ) = n -k -g + 1.
Therefore, the "gap" between this code and an MDS code of the same length is g . The same holds for the dual code.

The minimum distance of AG codes thus depends on the genus of the curves used to define them. Because the maximal number of points on a curve increases with its genus, there is a tradeoff between the length of a code and its minimum distance.

Construction of a generator matrix of an AG code.

Once the parameters of a code have been fixed, including the ordered set P , one just has to specify a basis of L (r Q), and to form the encoding matrix M ∈ M k,n (F 2 m ) obtained by evaluating this basis on . A useful basis is one such that the encoding matrix is in systematic form, but it does not necessarily exist for any P . Note however that in the case of MDS codes (such as RS codes) this basis always exists whatever the parameters and the choice of P : this is because in this case every minor of M is of full rank [START_REF] Macwilliams | The Theory of Error-Correcting Codes[END_REF]. When such a basis exists, it is easy to find as one just has to start from an arbitrary basis and to compute the reduced row echelon form of the matrix thus obtained.

Example 1: An AG code from an elliptic curve. We give parameters for a code built from the curve defined on P 2 (F 2 4 ) by the homogeneous polynomial x 2 z+xz 2 = y 3 +y z 2 , or equivalently defined on A 2 (F 2 4 ) by x 2 + x = y 3 + y. It is of genus 1, and hence it is an elliptic curve. It has 25 points, including one point at infinity, the point Q = [1 : 0 : 0]; the order of the poles of x and y in Q are respectively 3 and 2. From this, a basis for the space L (12Q) can easily be obtained. This space has dimension 12 + 1 -g = 12, and can be used to define a [24, 12, 12] F 2 4 code by evaluation over the affine points of the curve. This allows to define a matrix of dimension 12 over F 2 4 , which diffuses over 12×4 = 48 bits and has a differential and linear branch number of 12.

Example 2: An AG code from an hyperelliptic curve. We increase the length of the code by using a curve with a larger genus. We give parameters for a rather well-known code, built from the curve defined on P 2 (F 2 4 ) by the homogeneous polynomial x 5 = y 2 z + y z 4 . This curve has 33 points, including one point at infinity, the point Q = [0 : 1 : 0]; the order of the poles of x and y in Q are respectively 2 and 5. From this, a basis for the space L (17Q) can easily be defined. This space has dimension 17 + 1 -g = 16, and can be used to define a [32, 16, 15] F 2 4 code by evaluation over the affine points of the curve. This code has convenient parameters for defining diffusion matrices: from a generator matrix in systematic form (I 16 A), we can extract the matrix A, which naturally diffuses over 64 bits and has a differential and linear branch number of 15. Furthermore, the code is self-dual, which means that A is orthogonal: A • A t = I 16 . The inverse of A is therefore easy to compute.

We give the right matrix of two matrices of this code in systematic form in appendices D.1 and D.2, the latter further including an example of a basis of L (17Q) and the order of the points used to construct the matrix.

The problem for the rest of the section is now to find good point orders P for the hyperelliptic code of Ex. 2 such that efficient encoders can be constructed thanks to algorithm 2 of §3.3. For convenience, we name C H E any of the codes equivalent to the one of Ex. 2.

Compact encoders using code automorphisms

We consider matrices in systematic form (I 16 A). For dense matrices, Alg. 2 tends to be most efficient when all the rows of a matrix can be deduced by permutation of one of them, or more generally of a small subset of them. Our objective is thus to find matrices of this form.

The main tool we use to achieve this goal are automorphisms of C H E . Let us first give a definition. (In the following, S n denotes the group of permutations of n elements.)

Definition 5 (Automorphisms of a code) The automorphism group Aut

(C ) of a code C of length n is a subgroup of S n such that π ∈ Aut(C ) ⇒ (c ∈ C ⇒ π(c) ∈ C ).
Because we consider here the code C H E which is an evaluation code, we can equivalently define its automorphisms as being permutations of the points on which the evaluation is performed. If π is an automorphism of C H E , if {O 0 , . . . ,O l } are its orbits, and if the code is defined with a point order P such that for each orbit all of its points are neighbours in the order P , then the effect of π on a codeword of C H E is to cyclically permute its coordinates along each orbit.

To see that this is useful, assume that there is an automorphism π with two orbits O 0 and O 1 of size n/2 each. Then, if M = (I n/2 A) is obtained with point order P = 〈O 0 ,O 1 〉, each row of M can be obtained by the repeated action of π on, say, m 0 , and it follows that A is circulant (and therefore has a low cost w.r.t. algorithm 2). More generally, if an automorphism can be found such that it has orbits of size summing up to n/2, the corresponding matrix M can be deduced from a small set of rows. We give two toy examples with Reed-Solomon codes, which can easily be verified. π : F 2 4 → F 2 4 , x → 8x. This automorphism has O 0 = 〈1, 8, 12, 10, 15〉 and O 1 = 〈2, 3, 11, 7, 13〉 for orbits, among others. The systematic matrix for the [START_REF] Heegard | Systematic Encoding via Gröbner Bases for a Class of Algebraic-Geometric Goppa Codes[END_REF][START_REF] Chen | A Serial-In-Serial-Out Hardware Architecture for Systematic Encoding of Hermitian Codes via Gröbner Bases[END_REF][START_REF] Daemen | The Design of Rijndael: AES -The Advanced Encryption Standard[END_REF]] F 2 4 code obtained with the points in that order is then such that A is circulant and obtained from the cyclic permutation of the row (12, 10, 2, 6, 3). π : F 2 4 → F 2 4 , x → 7x. This automorphism has O 0 = 〈1, 7, 6〉, O 1 = 〈2, 14, 12〉, O 2 = 〈4, 15, 11〉, and O 3 = 〈8, 13, 5〉 for orbits, among others. The systematic matrix for the [START_REF]Selected Areas in Cryptography, 19th International Conference, SAC 2012[END_REF][START_REF] Daemen | The Design of Rijndael: AES -The Advanced Encryption Standard[END_REF][START_REF] Duursma | Weight distributions of geometric Goppa codes[END_REF] Application to C H E . Automorphisms of C H E are quite harder to find than ones of RS codes. They can however be found within automorphisms of the curve X on which it is based [START_REF] Stichtenoth | Algebraic Function Fields and Codes[END_REF]. This is quite intuitive, as these will precisely permute points on the curve, which are the points on which the code is defined. We mostly need to be careful to ensure that the point at infinity is fixed by these automorphisms. We considered the degree-one automorphisms of X described by Duursma [START_REF] Duursma | Weight distributions of geometric Goppa codes[END_REF].

They have two generators:

π 0 : F 2 2 4 → F 2 2 4 , (x, y) → (ζx, y) with ζ 5 = 1, and π 1 (a,b) : F 2 2 4 → F 2 2 4 , (x, y) → (x + a, y + a 8 x 2 + a 4 x + b 4 )
, with (a, b) an affine point of X . These generators span a group of order 160. When considering their orbit decomposition, the break-up of the size of the orbits can only be of one of five types, given in Table 1. From these automorphisms, it is possible to define a partitions of P in two sets of size 16, which are union of orbits. We may therefore hope to obtain systematic matrices of the type we are looking for. Unfortunately, after an extensive search 5 , it appears that ordering P in this fashion never results in obtaining a systematic matrix. We recall that indeed, because AG codes are not MDS, it is not always the case that computing the reduced row echelon form of an arbitrary encoding matrix yields a systematic matrix. Extending the automorphisms with the Frobenius mapping. We extend the previous automorphisms with the Frobenius mapping θ : F 2 2 4 → F 2 2 4 , (x, y) → (x 2 , y 2 ); this adds another 160 automorphisms for X . However, these will not anymore be automorphisms for the code C H E in general, and we will therefore obtain matrices of a form slightly different from what we first hoped to achieve.

The global strategy is still the same, however, and consists in ordering the points along orbits of the curve automorphisms. By using the Frobenius, new combinations of orbits are possible, notably 4 of size 8. We study below the result of ordering P along the orbits of one such automorphism. We take the example of σ = θ • σ 2 • σ 1 , with σ 1 : (x, y) → (x + 1, y + x 2 + x + 7), σ 2 : (x, y) → (12x, y), and θ the Frobenius mapping. The key observation is that in this case, only σ 0 and σ 4 are automorphisms of C H E . Note that not all orbits orderings of σ for P yield a systematic matrix. However, unlike as above, we were able to find some orders that do. In these cases, the right matrix "A" of the full generator matrix (I 16 A) is of the form: (a 0 , a 1 , a 2 , a 3 , σ 4 (a 0 ), σ 4 (a 1 ), σ 4 (a 2 ), σ 4 (a 3 ), a 8 , a 9 , a 10 , a 11 , σ 4 (a 8 ), σ 4 (a 9 ), σ 4 (a 10 ), σ 4 (a 11 )) t , with a 0 , . . . , a 3 , a 8 , . . . , a 11 row vectors of dimension 16. For instance, the first and fifth row of one such matrix are: a 0 = (5, 2, 1, 3, 8, 5, 1, 5, 12, 10, 14, 6, 7, 11, 4, 11) a 4 = σ 4 (a 0 ) = (8, 5, 1, 5, 5, 2, 1, [START_REF] Benadjila | Implementing lightweight block ciphers on x86 architectures[END_REF][START_REF] Duursma | Weight distributions of geometric Goppa codes[END_REF][START_REF]Intel® 64 and IA-32 Architectures Software Developer's Manual[END_REF][START_REF] Bernstein | NEON Crypto[END_REF][START_REF]Intel® 64 and IA-32 Architectures Software Developer's Manual[END_REF][START_REF]Selected Areas in Cryptography, 19th International Conference, SAC 2012[END_REF][START_REF] Heegard | Systematic Encoding via Gröbner Bases for a Class of Algebraic-Geometric Goppa Codes[END_REF][START_REF] Macwilliams | The Theory of Error-Correcting Codes[END_REF][START_REF] Daemen | The Design of Rijndael: AES -The Advanced Encryption Standard[END_REF].

We give the full matrix in appendix D.1. We have therefore partially reached our goal of being able to describe A from a permutation of a subset of its rows. However this subset a 0 , . . . , a 3 , a 8 , . . . , a 11 is not small, as it is of size 8 -half of the matrix dimension. Consequently, these matrices have a moderate cost according to the cost2 function, when implemented with algorithm 2, but it is not minimal. Interestingly, all the matrices of this form that we found have the same cost of 52.

Fast random encoders

We conclude this section by presenting the results of a very simple random search for efficient encoders of C H E with respect to algorithm 2. Unlike the above study, this one does not exploit any kind of algebraic structure. Indeed, the search only consists in repeatedly generating a random permutation of the affine points of the curve, building a matrix for the code with the corresponding point order, tentatively putting it in systematic form (I 16 A), and if successful evaluating the cost2 function from §3.3 on A. We then collect matrices with a minimum cost. Because there are 32! ≈ 2 117,7 possible point orders, we can only explore a very small part of the search space. However, matrices of low cost can be found even after a moderate amount of computation, and we found many matrices of cost 43, though none of a lower cost. We present in Table 3 from appendix E the number of matrices of cost strictly less than 60 that we found during a search of 2 38 encoders. We give an example of a matrix of cost 43 in appendix D.2, which is only about a factor 1.5 away from the estimate of the minimum cost of a circulant matrix given in §3.3. We observe that the transpose of this matrix also has a cost of 43.

Applications and performance

This last section presents the performance of straightforward assembly implementations of both of our algorithms when applied to a fast encoder of the code C H E from §4. More precisely, we consider the diffusion matrix "M H 16 " of appendix D.2; it is of dimension 16 over F 2 4 and has a differential and linear branch number of 15. We do this study in the context of block ciphers, by assuming that M H 16 is used as the linear mapping of two ciphers with a SHARK structure: one with 4-bit S-Boxes and a 64-bit block, and one with 8-bit S-Boxes and a 128-bit block. What we wish to measure in both cases is the speed in cycles per byte of such hypothetical ciphers, so as to be able to gauge the efficiency of this linear mapping and of the resulting ciphers. In order to do this, we need to estimate how many rounds would be needed for the ciphers to be secure.

Basic statistical properties of a 64-bit block cipher with 4-bit S-Boxes and M H 16 as a linear mapping. We use standard wide-trail considerations to study differential and linear properties of this cipher [START_REF] Daemen | The Design of Rijndael: AES -The Advanced Encryption Standard[END_REF]. This is very easy to do thanks to the simple structure of the cipher. The branch number of M H 16 is 15, which means that at least 15 S-boxes are active in any two rounds of a differential path or linear characteristic. The best 4-bit S-boxes have a maximum differential probability and a maximal linear bias of 2 -2 (see e.g. [START_REF] Saarinen | Cryptographic Analysis of All 4 × 4-Bit S-Boxes[END_REF][START_REF] Leander | On the Classification of 4 Bit S-Boxes[END_REF]). By using such S-boxes, one can upper-bound the probability of a single differential path or linear characteristic for 2n rounds by 2 -2•15n . This is smaller than 2 -64 as soon as n > 2. Hence we conjecture that 6 to 8 rounds are enough to make a cipher resistant to standard statistical attacks.

If one were to propose a concrete cipher, a more detailed analysis would of course be needed, especially w.r.t. more dedicated structural attacks. However, it seems reasonable to consider at a first glance that 8 rounds would indeed be enough to bring adequate security. It is only 2 rounds less than AES-128, which uses a round with comparatively weaker diffusion. Also, 6 rounds might be enough. Consequently, we present software performance figures for 6 and 8 rounds of such an hypothetical 64-bit cipher with 4-bit S-Boxes in Table 2, on the left. We include data both for a strict SSSE3 implementation and for one using AVX extensions, which can be seen to bring a considerable benefit. Note that the last round is complete and includes the linear mapping, unlike e.g. AES. Also, note that the parallel application of the S-Boxes can be implemented very efficiently with a single pshufb, and thus has virtually no impact on the speed.

Basic statistical properties of a 128-bit block cipher with 8-bit S-Boxes and M H 16 as a linear mapping. Although the code H E from which the matrix H 16 is built was initially defined with F 2 4 as an alphabet, this latter can be replaced by an algebraic extension of F 2 4 such as F 2 8 , to yield a code C H E ′ with the same parameters, namely a [32, 16, 15] F 2 8 code. Indeed, by using a suitable representation such as 6 , an element of F 2 8 is represented as a degree-one polynomial at + b over F 2 4 . It follows that the minimum weight of a codeword w = (a i t

F 2 4 ∼ = F 2 [α]/(α 4 + α 3 + α 2 + α + 1); F 2 8 ∼ = F 2 4 [t ]/(t 2 + t + α)
+ b i ), i ∈ {0 . . . 31} of C H E
′ is at least equal to the minimum weight of words (a i ), i = 0 . . . 31 and (b i ), i ∈ {0 . . . 31}. If those are taken among codewords of C H E , their minimum weight is 15, and thus so is the one of w. It is also possible to efficiently compute the multiplication by M H 16 over F 2 8 from two computations over F 2 4 : because the coefficients of M H 16 are in F 2 4 , we have

M H 16 • (a i t + b i ) = (M H 16 • (a i ) • t ) + (M H 16 • (b i )).
As a result, applying M H 16 to F 2 8 has only twice the cost of applying it to F 2 4 , while effectively doubling the size of the block.

From wide-trail considerations, the resistance of such a cipher to statistical attacks is comparatively even better than when using 4-bit S-Boxes, when an appropriate 8-bit S-Box is used. For instance, the AES S-box has a maximal differential probability and linear bias of 2 -6 [6]. This implies that the probability of a single differential path or linear characteristic for 2n rounds is upperbounded by 2 -6•15n which is already much smaller than 2 -128 as soon as n > 1. Again, 8 rounds of such a cipher should bring adequate security, and 6 rounds might be enough. We provide performance figures for both an SSSE3 and an AVX implementation in Table 2, on the right. However, in the case of 8-bit S-Boxes, the S-Box application is rather more complex and expensive a step than with 4-bit S-Boxes. In these test programs, we decided to use the efficient vector implementation of the AES S-Box from Hamburg [START_REF] Hamburg | Accelerating AES with Vector Permute Instructions[END_REF]. Discussion. The performance figures given in Table 2 are average for a block cipher. For instance, it compares favourably with the optimized vector implementations of 64-bit ciphers LED and Piccolo in sequential mode from [START_REF] Benadjila | Implementing lightweight block ciphers on x86 architectures[END_REF], which run at speeds between 70 and 90 cpb., depending on the CPU.

It is however slower than Hamburg's vector implementation of AES, with reported speeds of 6 to 22 cpb. (9 to 25 for the inverse cipher) [START_REF] Hamburg | Accelerating AES with Vector Permute Instructions[END_REF][START_REF] Suzaki | TWINE: A Lightweight Block Cipher for Multiple Platforms[END_REF].

Conclusion

We revisited the SHARK structure by replacing the MDS matrix of its linear diffusion layer by a matrix built from an algebraic-geometry code. Although this code is not MDS, it has a very high minimum distance, while being defined over F 2 4 instead of F 2 8 . This allows to reduce the size of the coefficients of the matrix from 8 to 4 bits, and has important consequences for efficient implementations of this linear mapping. We studied algorithms suitable for a vector implementation of the multiplication by this matrix, and how to find matrices that are most efficiently implemented with those algorithms. Finally, we gave performance figures for assembly implementations of hypothetical SHARK-like ciphers using this matrix as a linear layer. This work provided the first generalizations of SHARK that are not vulnerable to timing attacks as is the original cipher, and also the first generalization to 128-bit blocks. It also showed that even if not the fastest, such potential design could be implemented efficiently in software. As a future work, it would be interesting to investigate how to use the full automorphism group of the code to design matrices with a lower cost. In that case, we would not restrict ourselves to derive the rows from a single row and the powers of a single automorphism, but could use several independent automorphisms instead.

A.2 Shuffle-based algorithm

The shuffle-based algorithm for matrix-vector multiplication of §3.3 is given in Algorithm 2. ; shuffles ; 0 xff for not selected nibbles ( it will zero them ) pp10 : dq 0 x0005000507040d02 , 0 x 0f01040a 03060809 pp11 : dq 0 xffff0e0c0e0bffff , 0 x ff0b08ff 040cffff pp12 : dq 0 xffffff0eff0dffff , 0 x ffffffff ffffffff pp20 : dq 0 x050306070602040e , 0 x 0408010c 01000b04 pp21 : dq 0 x0c0e0909ff0307ff , 0 x 0bff020e ffff0dff pp22 : dq 0 xffffff0fff0affff , 0 x ffffffff ffffffff pp30 : dq 0 xffffff02ff09ff09 , 0 x 0affff04 ffffff02 pp31 : dq 0 xffffff04ff0eff0a , 0 x 0effff0f ffffff0f ; [ ... ] ; 2 useful macros ( nasm syntax ) ; 1 is the location of the vector , ; 2 is storage for the multiplied thingy , ; [START_REF] Benadjila | Implementing lightweight block ciphers on x86 architectures[END_REF] These codes have the following properties: for fixed parameters n and k, there are 2 m n •n! equivalent codes, which corresponds to the number of possible ordered sets P ; the minimal distance d of a code of parameters n and k is at least n -(k -1) = nk + 1. This is because a polynomial of degree k -1 has at most k -1 zeros, and hence any codeword except the all-zero word is non-zero on at least n -(k -1) positions. Because this bound reaches the Singleton bound, RS codes are MDS codes; finally, it is obvious that the maximal length of an RS code over F 2 m is 2 m .

Algorithm 2 Shuffle-based matrix-vector multiplication

F 2 4

 4 code obtained with the points in that order is then of the form I 3 0 3 A B 0 3 I 3 C D with A, B , C and D circulant matrices. It can thus be obtained by cyclic permutation of only two rows.

Input: x ∈ F 16 2 4 ,

 4 M ∈ M 16 (F 2 4 ) Output: y = M • x Offline phase 1: for i ∈ {1 . . . 15} do 2: s i [ ] ← S (M , i ) ⊲ Initialize the array s i with one of the possible sets of shuffles S (M , i ) 3: end for Online phase 4: y ← 0 64 5: for i ∈ {1 . . . 15} do 6: for j < #s i do 7: y ← y + i • s i [ j ] 8: end for 9: end for 10: return y B Excerpts of assembly implementations of matrix-vector multiplication B.1 Excerpt of an implementation of algorithm 1 ; cleaning mask cle : dq 0 x0f0f0f0f0f0f0f0f , 0 x0f0f0f 0f0f0f0f 0f ; mask for the selection of v , 2 v oe1 : dq 0 xff0ff000ff0ff000 , 0 xff0ff0 00ff0ff0 00 ; mask for the selection of 4v , 8 v oe2 : dq 0 xf0f0f0f000000000 , 0 xffffff ff0f0f0f 0f ; m0 and 2 m0 interleaved c01 : dq 0 x91a7efa76c126cb5 , 0 x9124fd 91cb3636 d9 ; 4 m0 and 8 m0 interleaved c02 : dq 0 x24efd9efb548b5a7 , 0 x248391 245acbcb 12 ; etc. c11 : dq 0 x249183244800cb6c , 0 x6cfd12 485a91b5 5a

Table 1 .

 1 Possible combination of orbit sizes of automorphisms of C H E spanned by π 0 and π 1 . A number n in col. c means that an automorphism of this type has n orbits of size c.

	Orbit size 1	2	4	5	10
	Type 1	32	0	0	0	0
	Type 2	0	16	0	0	0
	Type 3	0	0	8	0	0
	Type 4	2	0	0	6	0
	Type 5	0	1	0	0	3

Table 2 .

 2 Performance of software implementations of the hypothetical 64 and 128-bit cipher, in cycles per byte (cpb). Figures in parentheses are for an AVX implementation (when applicable).

	64-bit Block	128-bit Block

Algorithm 1

 1 Broadcast-based matrix-vector multiplication

	Input: x ∈ F 16 2 4 , M ∈ M 16 (F 2 4 ) Output: y = x t • M t
		Offline phase
	1: for i ∈ {0 . . . 15} do 2: 8m i ← α 3 • m i 3: 4m i ← α 2 • m i
	4:	2m i ← α • m i
	5: end for
		Online phase
	6: y ← 0 64
	7: for i ∈ {0 . . . 15} do 8: γ 8 i ← 8m i ∧ 64 broadcast(x i , 3) 64 9: γ 4 i ← 4m i ∧ 64 broadcast(x i , 2) 64 10: γ 2 i ← 2m i ∧ 64 broadcast(x i , 1) 64 11: γ 1 i ← m i ∧ 64 broadcast(x i , 0) 64 12: γ i ← γ 8 i + γ 4 i + γ 2 i + γ 1 i 13: y ← y + γ i
	14: end for
	15: return y

  of dimension k is defined as the vector (m(p i ), i = 0 . . . n -1), where m is seen as the polynomial i =0...k-1 m i • x i of F 2 m [x] of degree at most k -1, and where P = 〈p 0 , . . . , p n-1 〉 is an ordered set of n elements of F 2 m , n ≤ 2 m . The code is the set of all such codewords.

	is the constant index
	% macro vec_mul 3
	movdqa %2 , [ ttim2 + %3*16]
	pshufb %2 , %1
	movdqa %1 , %2
	% endmacro
	; 1 is the accumulator ,
	; 2 is the multiplied vector ,
	; 3 is storage for the shuffled thingy ,
	; 4 is the index for the shuffle
	% macro pp_accu 4
	movdqa %3 , %2
	pshufb %3 , [ pp10 + %4*16]
	pxor	%1 , %3
	% endmacro
	; the input is in xmm0 , with only the four lsb of each byte set
	_m64 :
	pxor xmm1 , xmm1 ; init the accumulator
	.mainstuff :
	; 1 .x
	pp_accu xmm1 , xmm0 , xmm2 , 0
	pp_accu xmm1 , xmm0 , xmm2 , 1
	pp_accu xmm1 , xmm0 , xmm2 , 2
	; 2 .x
	vec_mul xmm0 , xmm2 , 0
	pp_accu xmm1 , xmm0 , xmm2 , 3
	pp_accu xmm1 , xmm0 , xmm2 , 4
	pp_accu xmm1 , xmm0 , xmm2 , 5
	; 3 .x
	vec_mul xmm0 , xmm2 , 1
	pp_accu xmm1 , xmm0 , xmm2 , 6
	pp_accu xmm1 , xmm0 , xmm2 , 7
	; [ ... ]
	.fin :
	; the result is in xmm0 , and still of the same form
	movdqa xmm0 , xmm1
	ret

C A short introduction to Reed-Solomon codes Definition 6 (Reed-Solomon codes) Let C RS be an [n, k, d ] F 2 m Reed-Solomon code of length n, dimension k, and minimal distance d with symbols in F 2 m . The codeword C RS (m) corresponding to the message m

The instruction can actually also be used on 64-bit operands, but we do not consider this possibility here.

We will use the word shuffle with this precise meaning in the remainder of this paper.

And because it depends on what we assume to be a secret value, it cannot either be fetched from memory.

We slightly abuse the notations here and actually mean x/z and y/z. But we prefer manipulating their dehomogenized equivalents x and y. It is obvious that x/z and y/z indeed have poles in Q, which is at infinity and hence has a zero z coordinate.

Both on C H E and on the smaller elliptic code of Ex. 1. However, we are not as yet able to explain this fact.

This representation is used by Hamburg in[START_REF] Hamburg | Accelerating AES with Vector Permute Instructions[END_REF].

We omit the z coordinate for conciseness, as it is always 1.

Acknowledgments

Karpman is partially supported by the Direction générale de l'armement and by the Singapore National Research Foundation Fellowship 2012 (NRF-NRFF2012-06).

It can easily be obtained as follows. First, define a basis of L (17Q), for instance: (1, x, x 2 , y, x 3 , x y, x 4 , x 2 y, x 5 , x 3 y, x 6 , x 4 y, x 7 , x 5 y, x 8 , x 6 y). Then, arrange the affine points of the curve on which C H E is defined in the order 7 : 〈 (8, 7), (13, 2), (4, 5), (0, 0), [START_REF] Macwilliams | The Theory of Error-Correcting Codes[END_REF][START_REF] Chen | A Serial-In-Serial-Out Hardware Architecture for Systematic Encoding of Hermitian Codes via Gröbner Bases[END_REF], [START_REF] Rijmen | The Cipher SHARK[END_REF][START_REF] Daemen | The Design of Rijndael: AES -The Advanced Encryption Standard[END_REF], [START_REF] Duursma | Weight distributions of geometric Goppa codes[END_REF][START_REF] Benadjila | Implementing lightweight block ciphers on x86 architectures[END_REF], (1, 7), (2, 2), [START_REF]Intel® 64 and IA-32 Architectures Software Developer's Manual[END_REF][START_REF] Benadjila | Implementing lightweight block ciphers on x86 architectures[END_REF], [START_REF] Benadjila | Implementing lightweight block ciphers on x86 architectures[END_REF][START_REF] Benadjila | Implementing lightweight block ciphers on x86 architectures[END_REF], [START_REF] Heegard | Systematic Encoding via Gröbner Bases for a Class of Algebraic-Geometric Goppa Codes[END_REF][START_REF] Duursma | Weight distributions of geometric Goppa codes[END_REF], [START_REF] Daemen | The Design of Rijndael: AES -The Advanced Encryption Standard[END_REF][START_REF] Bernstein | NEON Crypto[END_REF], [START_REF] Chen | A Serial-In-Serial-Out Hardware Architecture for Systematic Encoding of Hermitian Codes via Gröbner Bases[END_REF][START_REF] Chen | A Serial-In-Serial-Out Hardware Architecture for Systematic Encoding of Hermitian Codes via Gröbner Bases[END_REF], [START_REF] Hamburg | Accelerating AES with Vector Permute Instructions[END_REF][START_REF] Chen | A Serial-In-Serial-Out Hardware Architecture for Systematic Encoding of Hermitian Codes via Gröbner Bases[END_REF], [START_REF]Selected Areas in Cryptography, 19th International Conference, SAC 2012[END_REF][START_REF] Daemen | The Design of Rijndael: AES -The Advanced Encryption Standard[END_REF], [START_REF] Benadjila | Implementing lightweight block ciphers on x86 architectures[END_REF][START_REF] Augot | Exhaustive Search for Small Dimension Recursive MDS Diffusion Layers for Block Ciphers and Hash Functions[END_REF], [START_REF]Intel® 64 and IA-32 Architectures Software Developer's Manual[END_REF][START_REF] Augot | Exhaustive Search for Small Dimension Recursive MDS Diffusion Layers for Block Ciphers and Hash Functions[END_REF], [START_REF]Selected Areas in Cryptography, 19th International Conference, SAC 2012[END_REF][START_REF] Duursma | Weight distributions of geometric Goppa codes[END_REF], [START_REF] Leander | On the Classification of 4 Bit S-Boxes[END_REF][START_REF] Benadjila | Implementing lightweight block ciphers on x86 architectures[END_REF], [START_REF] Bernstein | NEON Crypto[END_REF][START_REF] Bernstein | NEON Crypto[END_REF], (0, 1), [START_REF] Augot | Direct Construction of Recursive MDS Diffusion Layers using Shortened BCH Codes[END_REF][START_REF] Daemen | The Design of Rijndael: AES -The Advanced Encryption Standard[END_REF], [START_REF] Duursma | Weight distributions of geometric Goppa codes[END_REF][START_REF] Augot | Exhaustive Search for Small Dimension Recursive MDS Diffusion Layers for Block Ciphers and Hash Functions[END_REF], [START_REF] Hamburg | Accelerating AES with Vector Permute Instructions[END_REF][START_REF] Bernstein | NEON Crypto[END_REF], [START_REF] Daemen | The Design of Rijndael: AES -The Advanced Encryption Standard[END_REF][START_REF] Chen | A Serial-In-Serial-Out Hardware Architecture for Systematic Encoding of Hermitian Codes via Gröbner Bases[END_REF], [START_REF] Augot | Exhaustive Search for Small Dimension Recursive MDS Diffusion Layers for Block Ciphers and Hash Functions[END_REF][START_REF] Benadjila | Implementing lightweight block ciphers on x86 architectures[END_REF], [START_REF] Chen | A Serial-In-Serial-Out Hardware Architecture for Systematic Encoding of Hermitian Codes via Gröbner Bases[END_REF][START_REF] Bernstein | NEON Crypto[END_REF], [START_REF] Rijmen | The Cipher SHARK[END_REF][START_REF] Duursma | Weight distributions of geometric Goppa codes[END_REF], [START_REF] Heegard | Systematic Encoding via Gröbner Bases for a Class of Algebraic-Geometric Goppa Codes[END_REF][START_REF] Daemen | The Design of Rijndael: AES -The Advanced Encryption Standard[END_REF], [START_REF] Macwilliams | The Theory of Error-Correcting Codes[END_REF][START_REF] Bernstein | NEON Crypto[END_REF], [START_REF] Guo | The PHOTON Family of Lightweight Hash Functions[END_REF][START_REF] Daemen | The Design of Rijndael: AES -The Advanced Encryption Standard[END_REF] 〉. Finally, evaluate the basis of L (17Q) on these points (this defines a matrix of 16 rows and 32 columns), and compute the reduced row echelon form of this matrix; the right square matrix of dimension 16 of the result is the matrix above.

E Statistical distribution of the cost of matrices of C H E