Thomas Debris-Alazard

Nicolas Sendrier
email: nicolas.sendrier@inria.fr

Jean-Pierre Tillich
email: jean-pierre.tillich@inria.fr

Wave: A New Code-Based Signature Scheme

. It uses the family of ternary generalized (U, U + V ) codes. We prove that Wave achieves existential unforgeability under adaptive chosen message attacks (EUF-CMA) in the random oracle model (ROM) with a tight reduction to two assumptions from coding theory: one is a distinguishing problem that is related to the trapdoor we insert in our scheme, the other one is DOOM, a multiple target version of syndrome decoding. The algorithm produces uniformly distributed signatures through a suitable rejection sampling. Our scheme enjoys efficient signature and verification algorithms. For 128 bits of classical security, signature are 8 thousand bits long and the public key size is slightly smaller than one megabyte. Furthermore, with our current choice of parameters, the rejection rate is limited to one rejection every 3 or 4 signatures.

Introduction

Code-Based Signature Schemes. It is a long standing open problem to build an efficient and secure digital signature scheme based on the hardness of decoding a linear code which could compete with widespread schemes like DSA or RSA. Those signature schemes are well known to be broken by quantum computers and code-based schemes could indeed provide a valid quantum resistant replacement. A first answer to this question was given by the CFS scheme proposed in [START_REF] Courtois | How to achieve a McEliece-based digital signature scheme[END_REF]. It consisted in signing with the Niederreiter public-key decryption primitive [START_REF] Niederreiter | Knapsack-type cryptosystems and algebraic coding theory[END_REF]. This requires a linear code for which there exists an efficient decoding algorithm, able to find the closest codeword for a non-negligible proportion of all words. This means that if H is an r ×n parity-check matrix of the code, there exists for a non-negligible proportion of all s in F r 2 an efficient procedure to decode, that is find a word e in F n 2 of smallest Hamming weight such that

eH = s. (1)
In such a case we say that s, which is generally called a syndrome in the literature, can be decoded. [START_REF] Courtois | How to achieve a McEliece-based digital signature scheme[END_REF] achieved this task by using high rate Goppa codes. This signature scheme followed a relaxed form of the "hash-and-sign" paradigm. To sign a message m, a hash function h is used to produce a sequence s 0 , . . . , s of elements of F r 2 . For instance s 0 = h(m) and s i = h(s 0 , i) for i > 0. The first s i that can be decoded defines the signature of m as the word e of smallest Hamming weight such that eH = s i . This signature scheme has however two drawbacks: (i) for high rates Goppa codes the indistinguishability assumption used in its security proof has been invalidated in [FGO + 11], (ii) it scales poorly with respect to security. Indeed, a crude extrapolation of parallel CFS [START_REF] Finiasz | Parallel-CFS -strengthening the CFS McEliece-based signature scheme[END_REF] and its implementations [START_REF] Landais | Implementing CFS[END_REF][START_REF] Daniel | Mcbits: Fast constant-time code-based cryptography[END_REF] yields for 128 bits of classical security a public key size of several gigabytes and a signature time of several seconds. Those figures even grow to terabytes and hours for quantum-safe security levels, making the scheme unpractical.

Other Code-Based Signature Schemes. Instead of trying to solve a conventional decoding problem, meaning that we want to find an error of minimum weight satisfying (1), it is enough to require in this cryptographic context to solve (1) for an error e whose weight w is not necessarily minimal but just sufficiently low, so that problem (1) stays hard for someone whose does not know the secret structure of the code that is used. This approach has been followed in [BBC + 13] with LDGM codes, in [START_REF] Gligoroski | McEliece in the world of Escher[END_REF] with (essentially) convolutional codes and in the NIST proposal pqsigRM [START_REF] Lee | Post quantum signature scheme based on modified Reed-Muller code pqsigRM[END_REF] with modified Reed-Muller codes. The LDGM scheme was broken in [START_REF] Phesso | An efficient attack on a code-based signature scheme[END_REF], [START_REF] Gligoroski | McEliece in the world of Escher[END_REF] has been broken in [START_REF] Moody | Vulnerabilities of "McEliece in the World of Escher[END_REF] (and there are still some doubts that there is a way to choose the parameters of the scheme [START_REF] Gligoroski | McEliece in the world of Escher[END_REF] in order to avoid the attack [START_REF] Landais | An efficient attack of a McEliece cryptosystem variant based on convolutional codes[END_REF] on the McEliece cryptosystem based on convolutional codes [START_REF] Löndahl | A new version of McEliece PKC based on convolutional codes[END_REF]).

Other signature schemes based on codes were also given in the literature such as for instance the KKS scheme [START_REF] Kabatianskii | A digital signature scheme based on random error-correcting codes[END_REF][START_REF] Kabatianskii | Error Correcting Coding and Security for Data Networks: Analysis of the Superchannel Concept[END_REF] or its variants [START_REF] Paulo | One-time signature scheme from syndrome decoding over generic error-correcting codes[END_REF][START_REF] Gaborit | Efficient code-based one-time signature from automorphism groups with syndrome compatibility[END_REF]. But they can be considered at best to be one-time signature schemes in the light of the attack given in [START_REF] Cayrel | On Kabatianskii-Krouk-Smeets signatures[END_REF] and great care has to be taken to choose the parameters of these schemes as shown by [START_REF] Otmani | An efficient attack on all concrete KKS proposals[END_REF] which broke all the parameters proposed in [KKS97, [START_REF] Kabatianskii | Error Correcting Coding and Security for Data Networks: Analysis of the Superchannel Concept[END_REF][START_REF] Paulo | One-time signature scheme from syndrome decoding over generic error-correcting codes[END_REF]. There was also the proposal RaCoSS to the NIST that was based on a public matrix whose columns are formed by syndromes of low weight errors. It was broken in [START_REF] Huelsing | Official NIST comments made for RaCoSS[END_REF]. Another possibility is to use the Fiat-Shamir heuristic to turn a zero-knowledge authentication scheme into a signature scheme. When based on the Stern code-based authentication scheme [START_REF] Stern | A new identification scheme based on syndrome decoding[END_REF] this leads however to a signature scheme with really large signature sizes (of the order of hundred(s) of kilobits). This represents a complete picture of code-based signature schemes based on the Hamming metric.

There has been some recent progress in this area for another metric, namely the rank metric [START_REF] Gaborit | New results for rank-based cryptography[END_REF] with the RankSign scheme. This scheme enjoys remarkably small key sizes, it is of order tens of thousands bits for 128 bits of security. Unfortunately it got broken in [START_REF] Debris | Two attacks on rank metric code-based schemes: Ranksign and an identity-based-encryption scheme[END_REF]. In summary, it is still a very challenging and open question to come up with an efficient and secure signature scheme based on error-correcting codes.

Our Contribution: a "Hash-and-Sign" Signature Scheme Based on the GPV Approach.

Our scheme is based on the hash-and-sign approach and the GPV strategy [START_REF] Gentry | Trapdoors for hard lattices and new cryptographic constructions[END_REF] to devise such signature schemes. Recall that the notions put forward in that paper allowed to build the first identity based encryption scheme based on hard problems on lattices. This strategy has also been adopted in Falcon [FHK + ], a lattice based signature submission to the NIST call for post-quantum cryptographic primitives. It is based on the notion of preimage sampleable function. Roughly speaking, this is a family of trapdoor one-way functions (f a ) a such that with overwhelming probability over the choice of the function f a (i) the distribution of the images f a (x) is very close to the uniform distribution over the set of possible outputs (ii) the distribution of the output of the algorithm inverting f a using the trapdoor is very close to the uniform distribution over the inputs to f a . In [START_REF] Gentry | Trapdoors for hard lattices and new cryptographic constructions[END_REF] such functions are based on a's that are matrices over Z n×m q , whereas the input to f a is a subset of elements e ∈ Z m that are of euclidean norm bounded by some quantity W and f A (e) = eA mod q.

Our preimage sampleable function is of the same kind, i.e.

f H (e) = eH .

with the only difference that we perform matrix multiplication in the finite field F q and the inputs e will be restricted to have Hamming weight exactly w, where w is chosen such that it is hard to solve (1) for e's of such a Hamming weight.

In [START_REF] Gentry | Trapdoors for hard lattices and new cryptographic constructions[END_REF] a signature scheme based on preimage sampleable functions is given that is shown to be strongly existentially unforgeable under a chosen-message attack if in addition the preimage sampleable functions are also collision resistant. With our choice of w and F q , our preimage sampleable functions are not collision resistant. However, as observed in [START_REF] Gentry | Trapdoors for hard lattices and new cryptographic constructions[END_REF], collision resistance allows a tight security reduction but is not necessary : a security proof could also be given when the function is "only" preimage sampleable. We will also get a tight security reduction in our case by choosing carefully the difficult problems we use in the security : one is a distinguishing problem that is related to the trapdoor we insert in our scheme, the other one is a "multiple instancesonly one solution required" version of the decoding problem (1). This is the so called "Decoding One Out of Many" problem (DOOM in short) [START_REF] Sendrier | Decoding one out of many[END_REF].

Our Trapdoor: Generalized (U, U + V ) Codes. In [START_REF] Gentry | Trapdoors for hard lattices and new cryptographic constructions[END_REF] the trapdoor consists in a short basis of the lattice considered in the construction. Our trapdoor will be of a different nature, it consists in choosing parity-check matrices of generalized (U, U + V ) codes. Not every parity-check matrix is a parity-check matrix of a generalized (U, U + V ) code, however there are really plenty of such codes. The U and V codes can namely be chosen at random in this construction and the number of such codes of dimension k and length n is of order q Θ(n 2 ) when k = Θ (n). A generalized (U, U + V ) code of length n over F q has 6 ingredients -Two codes U and V of length n/2 -Four n/2 × n/2 diagonal matrices D 1 , . . . , D 4 over F q such that D = D 1 D 2 D 3 D 4 is invertible.

The generalized (U, U + V ) code, which we denote by (U D 1 + V D 2 , U D 3 + V D 4 ) is defined by

(U D 1 + V D 2 , U D 3 + V D 4 ) ={(uD 1 + vD 2 , uD 3 + vD 4 ) : u ∈ U, v ∈ V }.
Standard (U, U + V ) codes correspond to D 1 = D 3 = D 4 = 1 n/2 and D 2 = 0 n/2 , where 1 n/2 stands for the identity matrix of size n/2 and 0 n/2 is the n/2 × n/2 zero matrix. It is not the first time that (U, U + V ) codes or generalized (U, U + V ) codes are suggested for a cryptographic use. (U, U + V ) codes were already considered for constructing a McEliece cryptosystem in [START_REF] Kabatianskii | Error Correcting Coding and Security for Data Networks: Analysis of the Superchannel Concept[END_REF] and generalized (U, U + V ) codes in [START_REF] Puchinger | Code-based cryptosystems using generalized concatenated codes[END_REF]. However both papers did not consider the improvement in the error correction performance that comes with the (U, U + V )-construction (generalized or not) if a decoder that uses soft information is used. This was first observed in the very same cryptographic context in [START_REF] Márquez | Using Reed-Solomon codes in the (u|u + v) construction and an application to cryptography[END_REF]. Having codes with a better error correction in this context results in being able to reduce the key sizes of the scheme. The (generalized) (U, U + V )-construction also potentially allows to use in this context codes for U and V that would be insecure in this context if used alone, such as for instance generalized Reed-Solomon codes. This allows for instance to thwart the key attacks [SS96, CGG + 14] on the McEliece or Niederreiter scheme based on generalized Reed-Solomon code [START_REF] Niederreiter | Knapsack-type cryptosystems and algebraic coding theory[END_REF].

We push this idea further here, by allowing U and V to be completely random and by decoding them with a very simple decoder, namely a variation of the Prange decoder [START_REF] Prange | The use of information sets in decoding cyclic codes[END_REF] that is able to produce for any parity-check matrix H at will a solution of (1) when w is in the range q-1 q r, n-r q . Note that this algorithm works in polynomial time and that outside this range of weights the complexity of the best known algorithms is exponential in n for weights w of the form w = ωn where ω is a constant that lies outside the interval [ q-1 q ρ, 1 -ρ q ] where ρ = r n . In the case of a parity-check matrix of a generalized (U, U + V ) codes, a small tweak in the decoder is able to take advantage of the generalized (U, U + V ) structure to obtain smaller or larger weights for w outside this regime. This is in essence the trapdoor of our signature scheme. A further tweak in the decoder consisting in performing only a small amount of rejection sampling (with our choice of parameters one rejection every 3 or 4 signatures) allows to obtain solutions that are uniformly distributed over the words of weight w. Furthermore we also show that syndromes eH associated to this kind of codes are statistically indistinguishable from random syndromes when errors e are drawn uniformly at random among the words of weight w. These are the two key properties for obtaining a function f H that is preimage sampleable in our signature scheme. Finally, a variation of the proof decoding technique of [START_REF] Gentry | Trapdoors for hard lattices and new cryptographic constructions[END_REF] allows to give a tight security proof of our signature scheme that relies only on the hardness of two problems, namely Decoding Problem: Solving at least one instance of the decoding problem (1) out of multiple instances for a certain relative weight w/n that is outside the range [ω - easy , ω + easy ], where ω - easy = q-1 q r n and ω + easy = n-r n + ω - easy Distinguishing Problem: Deciding whether a linear code is a permuted generalized (U, U + V ) code or not.

Interestingly, some recent work [START_REF] Chailloux | Tight security reduction in the quantum random oracle model for code-based signature schemes[END_REF] has shown that these two properties (namely statistical indistinguishability of the signatures and the syndromes associated to the code family chosen in the scheme) are also enough to obtain a tight security proof in the Quantum Random Oracle Model (QROM) for generic code-based signatures under the assumption that the Decoding Problem remains hard against a quantum computer and that the code family which is used is computationally indistinguishable from generic linear codes. In other words, this can be used to give a tight security proof of our generalized (U, U + V ) codes in the QROM.

The Hardness of the Decoding Problem. All code-based cryptography relies upon that problem. The problem of solving (1) for a q-ary r × n matrix H is well known to be hard when we seek a word e of relative weight w/n < ω - easy = q-1 q r n . Beyond this point the problem is easily solved with linear algebra until we reach ω + easy = n-r n + ω - easy = 1 -1 q r n , and the problem becomes hard again, a fact which is not as widely spread and which we will use in this work. Furthermore, here we are in a case where the decoding problem has multiple solutions and the adversary may produce any number of instances of (1) with the same matrix H and various syndromes s and is interested in solving only one of them. This relates to the so called Decoding One Out of Many (DOOM) problem. This problem was first considered in [START_REF] Johansson | On the complexity of some cryptographic problems based on the general decoding problem[END_REF]. It was shown there how to adapt the known algorithms for decoding a linear code in order to solve this modified problem. This modification was later analysed in [START_REF] Sendrier | Decoding one out of many[END_REF]. The parameters of the known algorithms for solving (1) can be easily adapted to this scenario where we have to decode simultaneously multiple instances which all have multiple solutions.

The Hardness of the Distinguishing Problem. This problem might seem at first sight to be ad-hoc. However, even in the very restricted case where the generalized (U, U + V )-code is just a (U, U + V )-code and when the permutation is restricted to leave globally stable the right and left part, detecting whether the resulting code is a permuted (U, U + V )-code is NP-complete problem (see [DST17b, §7.1, Thm. 4]). Therefore the Distinguishing Problem is also NP-complete for generalized (U, U + V )-code. This theorem is proved in the case of binary (U, U + V )-codes in [DST17b, §7.1, Thm 3]). The proof given there carries over directly to an arbitrary finite field F q . However as observed in [DST17b, p. 3], these NP-completeness reductions hold in the particular case where the dimensions k U and k V of the code U and V satisfy k U < k V . If we stick to the binary case, i.e. q = 2, then in order that our (U, U + V ) decoder works outside the integer interval

r 2 , n -r 2 it is necessary that k U > k V .
Unfortunately in this case there is an efficient probabilistic algorithm solving the distinguishing problem that is based on the fact that in this case the hull of the permuted (U, U + V )-code is typically of large dimension, namely k U -k V (see [START_REF] Debris-Alazard | A new signature scheme based on (U |U + V ) codes[END_REF][1][2]). This problem can not be settled in the binary case by considering generalized (U, U + V ) codes instead of just plain (U, U + V )-codes, since it is only for the restricted class of (U, U + V ) codes that the (U, U + V ) decoder considered in [START_REF] Debris-Alazard | A new signature scheme based on (U |U + V ) codes[END_REF] is able to work properly outside the critical interval r 2 , n -r 2 . This is really related to the polarization phenomenon that lead to the famous construction of polar codes [START_REF] Arıkan | Channel polarization: a method for constructing capacity-achieving codes for symmetric binary-input memoryless channels[END_REF]: in the binary case, there is only one 2 × 2 kernel that polarizes, namely the kernel that corresponds to (U, U + V )-codes. This situation changes drastically when we move to larger finite fields. There are already several different 2 × 2-kernels that polarize over F 3 . In our cryptographic setting, this translates into the fact that it is not only for (U, U + V )-codes that we can solve the problem (1) efficiently. This holds for a very large of choices of the D i 's. The fact that there is a very large choice of matrices of D i is clearly a very powerful phenomenon that makes the distinguishing problem much harder. In terms of simplicity of the decoding procedure used in the signing process, it seems that defining our codes over the finite field F 3 is particularly attractive. In such a case, there is a big gain for the generalized (U, U + V ) codes that we have chosen and their decoding algorithm to choose the signature weight w to be very large, i.e. significantly above the upper-limit n -r 3 below which the decoding problem becomes polynomial as long as w is also above 2r 3 . We will discuss this situation in depth in §7. In this case, it seems that the best approach for solving the distinguishing problem is based on the following observation. This code has namely codewords of a weight slightly smaller than the minimum distance of a random code of the same length and dimension. It is very tempting to conjecture that the best algorithms for solving the Distinguishing Problem come from detecting such codewords. This approach can be easily thwarted by choosing the parameters of the scheme in such a way that the best algorithms for solving this task are of prohibitive complexity. Notice that the best algorithms that we have for detecting such codewords are in essence precisely the generic algorithms for solving the Decoding Problem. In some sense, it seems that we might rely on the very same problem, namely solving the Decoding Problem, even if our proof technique does not show this.

All in all, we propose to instantiate our signature scheme in the finite field F 3 which gives the first practical signature scheme based on ternary codes which comes with a security proof and which scales well with the parameters: it can be shown that if one wants a security level of 2 λ , then signature size is of order O(λ), public key size is of order O(λ 2 ), signature generation is of order O(λ 3 ), whereas signature verification is of order O(λ 2 ). It should be noted that contrarily to the current thread of research in code-based or lattice-based cryptography which consists in relying on structured codes or lattices based on ring structures in order to decrease the key-sizes we did not follow this approach here. This allows for instance to rely on the NP-complete Decoding Problem which is generally believed to be hard on average rather that on decoding in quasi-cyclic codes for instance whose status is still unclear with a constant number of circulant blocks. Despite the fact that we did not use the standard approach for reducing the key sizes relying on quasi-cyclic codes for instance, we obtain acceptable key sizes (less than one megabyte for 128 bits of security) which compare very favourably to unstructured lattice-based signature schemes such as TESLA for instance [ABB + 17]. This is due in part to the tightness of our security reduction.

Organization of the Paper. The paper is organized as follows, we present the outline of our scheme in §3 as well as the properties which are asked to reach the GPV strategy, namely the definition of one-way preimage sampleable functions. In §4 we give the trapdoor that we consider and in §5 we firstly show that it achieves the domain sampling with uniform output of preimage sampleable functions and then we explain how to produce uniformly distributed signatures with some rejection sampling. In §6 we prove it is secure under existential unforgeability under an adaptive chosen message attack (EUF-CMA) in the random oracle model (ROM), in relation with this proof we respectively examine in §7 and §8 the best messages and key attacks. Finally we give some set of parameters on par with the security reduction and with the current state-of-the-art for decoding techniques.

Notation

We provide here some notation that will be used throughout the paper.

General Notation. The notation x = y means that x is defined to be equal to y. We denote by F q the finite field with q elements and by S w,n the subset of F n q of words of weight w (q will be clear from the context). n will also be generally clear from the context. In such a case we just write S w .

Vector Notation. Vectors will be written with bold letters (such as e) and uppercase bold letters are used to denote matrices (such as H). Vectors are in row notation. Let x and y be two vectors, we will write (x, y) to denote their concatenation. We also denote by x I the vector whose coordinates are those of x = (x i ) 1≤i≤n which are indexed by I, i.e.

x I = (x i ) i∈I .

Sometimes we denote for a vector x by x(i) its i-th entry, or for a matrix A, by A(i, j) its entry in row i and column j.

We define the support of x = (x i ) 1≤i≤n as

Supp(x) ={i ∈ {1, • • • , n} such that x i = 0}
The Hamming weight of x is denoted by |x|. By some abuse of notation, we will use the same notation to denote the size of a finite set: |S| stands for the size of the finite set S. It will be clear from the context whether |x| means the Hamming weight or the size of a finite set. Note that

|x| = | Supp(x)|.
By extension the support Supp(M) of a matrix M is the union of its rows supports. For a vector x in F n q and a ∈ F q we denote by |x| a its number of entries in it that are equal to a:

|x| a = |{i : x i = a}|.
Probabilistic Notation. Let S be a finite set, then x ← S means that x is assigned to be a random element chosen uniformly at random in S. For a distribution D we write ξ ∼ D to indicate that the random variable ξ is chosen according to D. The uniform distribution on a certain discrete set is denoted by U. The set will be specified in the text. We denote the uniform distribution on S w by U w . When we have probability distributions D 1 , D 2 , . . . , D n over discrete sets E 1 , E 2 , . . . , E n , we denote by

D 1 ⊗ D 2 ⊗ • • • ⊗ D n the product probability distribution, i.e D 1 ⊗ • • • ⊗ D n (x 1 , . . . , x n ) = D 1 (x 1 ) . . . D n (x n ) for (x 1 , . . . , x n ) ∈ E 1 × • • • × E n . The n-th power product of a distribution D is denoted by D ⊗n , i.e. D ⊗n = D ⊗ • • • ⊗ D n times .
The statistical distance between two discrete probability distributions over a same space E is defined as:

ρ(D 0 , D 1 ) = 1 2 x∈E |D 0 (x) -D 1 (x)|.
For two random variables X and Y ranging over the same space, we will also denote by ρ(X, Y ) the statistical distance between the distribution D X of X and the distribution

D Y of Y , that is ρ(X, Y ) = ρ(D X , D Y ).
Recall that a function f (n) is said to be negligible if for all polynomials p(n), |f (n)| < p(n) -1 for all sufficiently large n that we will denote by f ∈ negl(n). Sometimes when we wish to emphasize on which probability space the probabilities or the expectations are taken, we denote by a subscript the random variable specifying the associated probability space over which the probabilities or expectations are taken. For instance the probability P X (E) of the event E is taken over Ω the probability space over which the random variable X is defined, i.e. if X is for instance a real random variable, X is a function from a probability space Ω to R, and the aforementioned probability is taken according to the probability chosen for Ω.

Coding Theory. For any matrix M we denote M the vector space spanned by its rows. A q-ary linear code C of length n and dimension k is a subspace of F n q of dimension k and is often defined by a parity-check matrix H over F q of size r × n as

C = H ⊥ = x ∈ F n q : xH = 0 .
When H is of full rank (which is usually the case) we have r = n -k. A generator matrix of C is a k × n full rank matrix G over F q such that G = C. The code rate, usually denoted by R, is defined as the ratio k/n. An information set of a code C of length n is a set of k coordinate indices I ⊂ {1, . . . , n} which indexes k independent columns on any generator matrix. Its complement indexes n -k independent columns on any parity check matrix. For any s ∈ F n-k q , H ∈ F (n-k)×n q , and any information set I of C = H ⊥ , for all x ∈ F n q there exists a unique e ∈ F n q such that eH = s and x I = e I .

We will also consider here the notion of punctured code. For a subset I ⊂ {1, . . . , n} and a code C of length n, we denote by Punc I (C), the code C punctured in I. This is defined as the set {cĪ = (c j ) j∈{1,...,n}\I : c ∈ C}, in other words the set of vectors obtained by deleting in the codewords of C the positions that belong to I.

3 The Wave-Signature Scheme

Outline of the Scheme

We define a probabilistic full domain hash (FDH) signature scheme, as in [START_REF] Bellare | The exact security of digital signatures-how to sign with rsa and rabin[END_REF][START_REF] Coron | Optimal security proofs for PSS and other signature schemes[END_REF]. We replace RSA with a trapdoor function based upon the hardness of the Decoding Problem. Let C be a linear of dimension k and length n over F q defined by a parity-check matrix H of size (n -k) × n. The one way function f H we consider is given by

f H : S w -→ F n-k q e -→ eH
Inverting this function on an input s amounts to solve the Decoding Problem. We are ready now to give the general scheme we consider. Let us assume that we have a family of codes which is defined by a set F of parity-check matrices of size (n -k) × n over F q such that for all H sk ∈ F we have an algorithm D H sk which on input s computes e ∈ f -1 H sk (s) (it will be the family of generalized admissible (U, U + V ) codes which are defined in §4.2). Then we pick uniformly at random H sk ∈ F, an n × n permutation matrix P, a non-singular matrix S ∈ F (n-k)×(n-k) q which define the secret and public key as: sk ← (H sk , P, S) ; pk ← H pk where H pk = SH sk P Remark 1. Let C sk be the code defined by H sk , then H pk defines the following code:

C pk = {cP : c ∈ C sk }.
We also select a cryptographic hash function Hash : {0, 1} * → F n-k q and a parameter λ 0 for the random salt r. The algorithms Sgn sk and Vrfy pk are defined as follows Sgn sk (m):

Vrfy pk (m, (e , r)): r ← {0, 1} λ0 s ← Hash(m, r) s ← Hash(m, r)

if e H pk = s and |e | = w return 1 e ← D H sk (s(S -1 ) )

else return 0 return(eP, r) Remark 2. We add a salt in the scheme in order to have a tight security proof.

Proof (Correction of the verification step). The pair (eP, r) passes the verification step because by definition of D H sk (s(S -1 ) ) we have eH sk = s(S -1 ) . Therefore (eP)H pk = e(H pk P ) = e(H pk P -1 ) = e(SH sk ) = eH sk S = s(S -1 ) S = s. We also have |eP| = |e| = w.

To summarize, a valid signature of a message m consists of a pair (e, r) such that eH pk = Hash(m, r) with e of Hamming weight w.

One-way Preimage Sampleable Code-based Functions

Classically, FDH signature schemes such as DSA are based on a trapdoor one-way function f : D → A which is a permutation. In this case the trapdoor permits to compute for any a ∈ A the unique d ∈ D (the signature of a) which verifies f (d) = a. Therefore, in the random oracle model when a follows the uniform distribution, signatures d which are produced are uniform too. In this way, the nice property to be a permutation for the trapdoor one-way function offers a first level of security for the signature scheme. Nevertheless, for the trapdoor one way function f H which is used in our code-based scheme, this condition to be a permutation is too strong to be met in an interesting way. This situation does not only arise for code-based trapdoor FDH signatures, it appears in lattice-based cryptography too. In this context, authors of [START_REF] Gentry | Trapdoors for hard lattices and new cryptographic constructions[END_REF] gave additional properties to be verified by the one way function. One of the crucial property that is asked for is that the algorithm that inverts f H based on the trapdoor is close to the uniform distribution on the inputs. In the following we will speak of GPV strategy. Authors of [START_REF] Gentry | Trapdoors for hard lattices and new cryptographic constructions[END_REF] summarized this in the definition of preimage sampleable function (see [GPV08, Definition 5.3.1]). To simplify the definition, we will directly express this notion for a restricted (and simplified) class of code-based trapdoor function.

Definition 1 (One-way preimage sampleable code-based functions). It is a pair of probabilistic polynomial-time algorithm (Trapdoor, InvertAlg) together with a triple of functions (n(λ), k(λ), w(λ)) growing polynomially with the security parameter λ and giving the length and dimension of the codes and the signature weight we consider, such that -Trapdoor when given λ, outputs (H, T ) where H is an (n -k) × n matrix over F q and T the trapdoor corresponding to H. Here and elsewhere we drop the dependence in λ of the functions n, k and w. -InvertAlg is a probabilistic algorithm which takes as input T and an element s ∈ F n-k q and outputs an e ∈ S w,n such that eH = s.

The following properties have to hold for all but a negligible fraction of H output by Trapdoor.

1. Domain Sampling with uniform output:

ρ(eH , s) ∈ negl(λ)
where e and s are two random variables, with e being uniformly distributed over S w,n and s being uniformly distributed over F n-k q . 2. Preimage Sampling with trapdoor: for every s ∈ F n-k q , we have

ρ (InvertAlg(s, T ), e) ∈ negl(λ),
where e is uniformly distributed in S w,n . 3. One wayness without trapdoor: for any probabilistic poly-time algorithm A outputting an element e ∈ S w,n when given H ∈ F

(n-k)×n q and s ∈ F n-k q , the probability that eH = s is negligible, where the probability is taken over the choice of H, the target value s chosen uniformly at random, and A's random coins.

It will turn out that by choosing the parameters appropriately and by choosing H such that it is a parity-check matrix of a permuted generalized (U, U + V ) code, we will be able to solve eH = s by using the underlying generalized (U, U + V ) structure in a regime of parameters where solving this problem for generic linear codes is thought to be hard. Moreover, by a suitable rejection technique we will show how the decoding algorithm using the trapdoor can be made oblivious of the underlying trapdoor. This is the preimage sampling condition of the previous definition.This mimics in a sense what has been achieved in the lattice setting of [START_REF] Gentry | Trapdoors for hard lattices and new cryptographic constructions[END_REF] where the inversion algorithm is oblivious to the particular geometry of the trapdoor basis. Similarly to what has been achieved in [START_REF] Gentry | Trapdoors for hard lattices and new cryptographic constructions[END_REF], we will also show that our construction based on permuted generalized (U, U + V ) codes also verifies the domain sampling condition.

Under the assumption that the Distinguishing and Decoding Problems are hard, we could have shown that the coding theoretic function f H that we consider here is one way. This would show that our code-based construction is a preimage sampleable function. However, the proof technique for showing the security of the signature scheme based on a preimage sampleable function given in [START_REF] Gentry | Trapdoors for hard lattices and new cryptographic constructions[END_REF] relies on a stronger version of a preimage sampleable function, it should namely also be collision resistant. Our code-based construction will not meet this condition for the particular choice we will make for our scheme. This comes from the fact that we will focus on a ternary alphabet q = 3 and very large values of w. We will proceed in a slightly different way in our case. We namely give a security reduction relying on the assumptions that the Distinguishing and Decoding Problems are hard and on the preimage sampling property on one hand and the domain sampling property on the other hand. The preimage sampling condition of the previous definition is here to ensure that signatures which are produced do not leak any information whereas the domain sampling condition may seem more surprising. As we will see, it naturally appears in the security reduction as it enables to inject a hard instance of the Decoding Problem to which we reduce.

Inverting the Syndrome Function

This section is devoted to the inversion of f H . It amounts to solve the following problem Problem 1 (Syndrome Decoding with fixed weight). Given H ∈ F (n-k)×n q , s ∈ F n-k q , and an integer w, find e ∈ F n q such that eH = s and |e| = w.

Here

we recall for which interval w -, w + of values for w we may hope to invert f H on any possible output; we recall in which interval of values w - easy , w + easy ⊂ w -, w + it is easy to invert f H for any parity-check matrix H without using any trapdoor: this is the well-known Prange decoder; we then explain how in the particular case of a generalized (U, U + V ) code we can invert f H by tweaking the Prange decoder for a significantly larger range w - UV , w + UV of w than w - easy , w + easy . This is the key that shows how to exploit the underlying (U, U + V ) structure as a trapdoor for inverting f H . Any solver of Problem 1 will be called decoding algorithm, whatever is the weight w. For small weights there is at most one solution and it relates to error-correction. For larger weight we may have exponentially many solutions and the problem relates to source-distortion theory in which it is also referred to as decoding.

Generic Solutions

Surjective Domain of the Syndrome Function The issue is here for which value of w we may expect that f H is surjective. This clearly implies that |S w | ≥ q n-k . In other words we have the following simple fact.

Fact 1 If f H is surjective, then necessarily w ∈ w -, w + with w -= min w ∈ 0, n , n w (q -1) w ≥ q n-k w + = max w ∈ 0, n , n w (q -1) w ≥ q n-k .

For a fixed rate R = k/n, it is readily verified that the asymptotic (in n) behaviour of w -and w + is given by

w - n = g - q (1 -R) + o(1) (2)
w + n = g + q (1 -R) + o(1) if R ≤ log q q q -1
(3)

w + n = 1 otherwise. ( 4
)
where h q (x) = -(1 -x) log q (1 -x) -x log q x q-1 and g - q its inverse ranging over [0, (q -1)/q], whereas g + q is its inverse ranging over [(q-1)/q, 1], but whose domain is restricted to [log q (q-1), 1]. This motivates the definition of ω -and ω + as

ω -= g - q (1 -R) (5)
ω + = g + q (1 -R) if R ≤ log q q q -1 (6) ω + = 1 otherwise. (7)
The Gilbert-Varshamov distance corresponds to the smallest radius of a ball in F n q centred around 0 whose volume is above q n-k . Since the volume of a ball is well approximated by the area of the sphere, w -is actually very close (if not equal) to the Gilbert-Varshamov distance and ω - is precisely the asymptotic relative Gilbert-Varshamov distance. A straightforward computation of the expected number of errors e of weight w such that eH = s when H is random shows that we expect an exponential number of solutions when w/n lies in (ω -, ω + ):

Proposition 1. Let n, k, w be integers with k ≤ n and s ∈ F n-k q . The expected number of solutions of eH = s in e of weight w when H is chosen uniformly at random in F (n-k)×n q is given by: n w (q -1) w q n-k .

When n tends to infinity but w and k are such that w = ωn and k = Rn with ω fixed in (ω -, ω + ) and R fixed in (0, 1), then this expected number of solutions behaves like e αn(1+o(1)) for a certain α > 0.

However, even the exponential number of solutions to our problem, coding theory has never come up with an efficient algorithm for finding a solution to this problem in the whole range (ω -, ω + ). An efficient solution is only known for a subrange by using the Prange decoder.

Easy Domain of the Syndrome Function

The subrange of (ω -, ω + ) for which we know how to solve efficiently Problem 1 is given by the condition w/n ∈ [ω - easy , ω + easy ] where

ω - easy = q -1 q (1 -R) (8) ω + easy = q -1 q (1 -R) + R, (9)
where R = k n . This is achieved by a sightly generalized version of the Prange decoder [START_REF] Prange | The use of information sets in decoding cyclic codes[END_REF]. To explain how it works, consider a linear code C over F q of length n and dimension k defined by a parity-check matrix H. We want to find for a given s and error e of weight w such that eH = s. Roughly speaking, the subspace structure of C offers k bits of e that can be arbitrarily chosen and the other n -k bits are uniquely determined. Indeed, H is a full-rank matrix and it therefore contains an invertible submatrix A of size (n -k) × (n -k). We choose a set of positions I of size n -k for which H restricted to these positions is a full rank matrix. For simplicity assume that this matrix is in the first n -k positions: H = A|B . We look for an e of the form e = (e , e ) where e ∈ F k q and e ∈ F n-k q . We should therefore have s = eH = e A + e B , that is e = (s -e B )(A -1 ) . In this way we can arbitrarily choose the error e of length k. Therefore, if we look for an error of low weight, we can set these k positions to 0. For the remaining part we expect to get about q-1 q (n -k) positions that are non zero. On the other hand, to get an error of largest possible weight, the best strategy seems to set the k positions to non-zero values. We also get in this case in the remaining part about q-1 q (n -k) positions that are non zero. The weights that are easily attainable by this strategy are therefore q-1 q (n -k) = nω - easy and k + q-1 q (n -k) = nω + easy . We can get all intermediate weights in this interval by choosing the appropriate number of zeros in the k positions of e . For reasons that will appear when we consider a decoder for generalized (U, U + V )-codes it will be convenient to choose the weight of e to be a random variable. In other words, the generalized Prange decoder looks as given in Algorithm 1.

Algorithm 1 PrangeOne(H, s) -One iteration of the Prange decoder Ensure: the returned value I is an information set of H ⊥ An information set of a k-dimensional code is a set of k coordinate indices such that, on any k×n generator matrix, it indexes a non singular k × k submatrix. Its complement indexes a non singular

Parameters: q, n, k, D a distribution over 0, k Require: H ∈ F (n-k)×n q , s ∈ F n-k q Ensure: eH = s 1: t ← D 2: I ← InfoSet(H) 3: x ← {x ∈ F n q | |xI| = t} 4: e ← PrangeStep(
(n -k) × (n -k) submatrix on any (n -k) × n parity check matrix. function PrangeStep(H, s, I, x) -Prange vector completion Require: H ∈ F (n-k)×n q , s ∈ F n-k q , I an information set of H ⊥ , x ∈ F n q Ensure: eH = s and eI = xI P ← any n × n permutation matrix sending I on the last k coordinates (A | B) ← HP A ∈ F (n-k)×(n-k) q (0 | e ) ← x e ∈ F k q e ← s -e B A -1 , e P return e
This algorithm represents one step of the Prange decoder and it is called as many times are needed to produce an error e of weight w. The probability distribution of the weights of the e's output by this function is readily seen to be given by Proposition 2. When H is chosen uniformly at random in F (n-k)×n q and s uniformly at random in F n-k q , we can write the weight of the e's output by PrangeOne(H, s) as

|e| = S + T
where S and T are independent random variables, S ∈ 0, n -k , T ∈ 0, k , S is the Hamming weight of a vector that is uniformly distributed over F n-k q and P(T = t) = D(t). The distribution of |e| is given by

P (|e| = w) = w t=0 n-k w-t (q -1) w-t q n-k D(t) (10)
E(|e|) = D + q -1 q (n -k) = D + nω - easy , (11)
where D = k t=0 tD(t). From this proposition, we deduce immediately that any weight w in ω - easy n, ω + easy n can be reached by this Prange decoder with a probabilistic polynomial time algorithm that uses a distribution D such that D = w -ω - easy n. It will be helpful in what follows to be able to choose a probability distribution D as this gives a rather large degree of freedom in the distribution of |e| that will come come very handy to simulate an output distribution that is uniform over the words of weight w in the generalized (U, U + V ) code decoder that we will consider in what follows.

To summarize this discussion we have shown that when we want to build a code-based signature scheme, w has to verify w -≤ w ≤ w + to ensure that f H is surjective but with an expected exponential number of solutions for a given syndrome (see Proposition 1 ). However, in a cryptographic setting w/n cannot lie in [ω - easy , ω + easy ] ⊆ [ω -, ω + ] otherwise anybody that uses the generalized Prange algorithm would be able to invert f H . All of this is summarized in Figure 2 where we draw the above different areas asymptotically in n of w/n when k/n is fixed. Enlarging the Easy Domain w - easy , w + easy Inverting the syndrome function f H is the basic problem upon which all code-based cryptography relies. This problem has been studied for a long time for weights w ≤ w - easy and despite many efforts the best algorithms [Ste88, Dum91, Bar97, MMT11, BJMM12, MO15, DT17] for solving this problem are all exponential. In other words, after a thorough fifty years of research, none of those algorithms came up with a polynomial complexity for weights w < w - easy . Furthermore, by adapting all the previous algorithms beyond this point we observe for them the same behaviour: they are all polynomial in the range of weights w - easy , w + easy and become exponential once again when w > w + easy . Therefore, it seems to be an hard problem to enlarge the range where inverting f H is easy. In the following subsection we present a trapdoor on the matrices H which enables to invert in polynomial time f H by tweaking the Prange decoder on a larger range than w - easy , w + easy .

Solution with Trapdoor

Let us introduce the family of codes (this is the trapdoor) that we consider to invert f H . As we will see in what follows, this family comes with a simple algorithm which enables to invert f H with errors of weight which belongs to w - UV , w + UV ⊂ w -, w + but with w - easy , w + easy w - UV , w + UV . We summarize this situation in Figure 3. Definition 2 (Generalized admissible (U, U + V )-codes). Let n be an integer and four diagonal matrices D 1 , • • • , D 4 over F q such that:

D = D 1 D 2 D 3 D 4 is invertible and ∀i ∈ 1, n/2 , D 1 (i, i)D 3 (i, i) = 0 (12)
Let U , V be linear q-ary codes of length n/2 and dimension k U , k V . We define the subset of F n q :

(U D 1 + V D2, U D 3 + V D 4 ) ={(uD 1 + vD 2 , uD 3 + vD 4 ) such that u ∈ U and v ∈ V }
which is a linear code of length n and dimension k = k U + k V . A parity-check matrix of such a code is given by

H U D 4 M -H U D 2 M H V D 3 M -H V D 1 M where M =(D 1 D 4 -D 3 D 2 ) -1 , H U ∈ F (n/2-k U )×n/2 q (resp. H V ∈ F (n/2-k V )×n/2 q
) is a parity-check matrix of U (resp. V ).

For a sake of simplicity in the description of the algorithm to invert f H when H is a paritycheck matrix of a generalized admissible (U, U + V ) code, we will restrict our study to the case of D 1 = D 3 = D 4 = 1 n/2 and D 2 = 0 n/2 which corresponds to standard (U, U + V )-codes. However, all our discussion (especially this subsection and the following) can be generalized.

It turns out now that in the case of a (U, U +V ) code, a simple tweak of the Prange decoder will be able to reach relative weights w/n outside the "easy" region [ω - easy , ω + easy ]. Let us first explain how the idea works in the case of a (U, U + V )-code. It exploits the fundamental leverage of the Prange decoder : it consists in choosing the error e satisfying eH = s as we want in k positions when the code that we decode is of dimension k. When we want an error of low weight, we put zeroes on those positions, whereas if we want an error of large weight, we put non-zero values. This idea can be adapted in the case of a (U, U + V )-code. The parity-check matrix of such a code can be chosen to be

H = H U 0 -H V H V (13)
Solving eH = s with H as (13) amounts to solve

e U H U = s U (14) e V H V = s V ( 15
)
where we split s = (s U , s V ) and we have e = (e U , e U + e V ). Performing the two decoding ( 14) and ( 15) independently with Prange algorithm gains nothing. However if we first solve (15) with Prange algorithm, and then seek a solution of (15) which properly depends of e V we increase the easy range of weights accessible for e. It then turns out that the range [ω - UV , ω + UV ] of relative weights w/n for which the (U, U + V ) decoder is easy is larger than the generic easy domain [ω - easy , ω + easy ], see Fig. 3. This will provides an advantage to the trapdoor owner.

Tweaking the Prange decoder For Reaching Low Weights. In this case, we first look, with the help of the Prange decoder, for the e V of lowest possible weight satisfying (15). We can attain a weight for e V of q-1 q (n/2 -k V ). In a second step we have to find e U satisfying ( 14). The point is now that we will not look for e U of lowest possible weight satisfying (14), we will instead use the knowledge of e V to do better. To understand this point, what we want to do now is to minimize the weight of e = (e U , e U + e V ) given e V and e U H U = s U . The strategy of Prange is to choose the value of e U in k U positions (the "information set") and to complete the rest of the values with the help of the equation e U H U = s U . For this, we consider the set of positions i for which e V (i) = 0. Without loss of generality, we may assume that these are the first n/2 -q-1 q (n/2 -k V ) = n 2q + q-1 q k V positions of e V and that e U and e V split as

e U = (e U , e U ) e V = (0, e V )
where e U is in

F n 2q + q-1 q k V q and e U , e V are in F q-1 q (n/2-k V ) q
. The error e we are looking for is therefore of the form e = (e U , e U , e U , e U + e V ). This is also represented in Figure 4. To get an error of smallest weight for e it really makes sense to choose as many zeros as we can in e U : they are doubled in e. Choosing a position of e U to be 0 is less helpful, since the corresponding position in e U + e V is non-zero in this case. There are two cases to consider:

e U e U e U e U + e V e V 0 eV = n 2q + q-1 q kV q-1 q (n/2 -kV )
Case 1 : k U ≤ n 2q + q-1 q k V .
Here we choose an information set for the Prange decoder among the positions in e U and ask in the Prange step applied to H U and s U that e U is zero on these positions. Here, the expected weight of e is given by

E(|e|) = 2 q -1 q n 2q + q -1 q k V -k U + 2 q -1 q q -1 q (n/2 -k V ) = q -1 q n -2 q -1 q k U (16)
Case 2 : k U > n 2q + q-1 q k V . In the Prange step applied to H U and s U , we choose the information set for U , so that it contains all the n 2q + q-1 q k V first positions (i.e. those of e U ) and choose e U to be zero on these positions. In this case, we have

E(|e|) = k U - n 2q - q -1 q k V + 2 q -1 q (n/2 -k U ) = 1 - 3 2q n - q -2 q k U - q -1 q k V (17)
It is readily seen that if we want to minimize the expected weight of |e| for a given dimension

k = k U + k V of the (U, U + V )-code
, it is always better to use the first strategy. From this it can be verified that as long k ≤ n 2q the best we can do is to choose k U = k and k V = 0. This leads in this regime to an expected weight given by ( 16) with k U = k:

E(|e|) = q -1 q n -2 q -1 q k. (18)
For larger values of k, it can be verified that the best we can do is to enforce

k U = n 2q + q-1 q k V , which together with the relation k = k U + k V implies that k U = n 2(2q -1) + (q -1)k 2q -1 . ( 19
)
Plugging this expression into (16) leads to

E(|e|) = 2(q -1) 2 (2q -1)q (n -k). (20)
Tweaking the Prange Decoder for Reaching Large Weights. When q = 2, small and large weights play a symmetrical role. This is not the case anymore for q ≥ 3. Indeed, in this case the best Prange strategy does not take into account the weight of e V . Assume here that we have chosen any e satisfying e V H = s V . How does the second decoding for e U take into account this? We want here to find e U that maximizes the weight of (e U , e U + e V ) given that e U H = s U . Recall that the Prange strategy consists in choosing the value of e U in k U positions and to complete the rest of the values with the help of the equation e U H = s U . Here for any position i, it is always possible to choose e U (i) such that both e U (i) and e U (i) + e V (i) are non-zero. By using this strategy, we see that the expected weight of e becomes fro q ≥ 3

E(|e|) = 2k U + (n -2k U ) q -1 q = q -1 q n + 2k U q (21)
The best choice for k U is to take k U = k up to the point where q-1 q n + 2k q = n, that is k = n/2. for larger values of k we choose k U = n/2 and k

V = k -k U .
Trapdoor Pseudocode. The decoder for (U, U + V ) codes that we just described when we want to reach large weights is given in details in Algorithm 2. We name it DecodeUV(•) and it parses its first argument H as a parity check matrix of some (U, U + V ) code. The decoding consists in two elementary steps, each using the basic Prange information set decoding. The second step is repeated in order to ensure that the final weight is w, the target for a valid signature. As it is described this algorithm may have a biased output and is susceptible to leak information on the secret key. Avoiding this is mandatory to obtain a proof in the GPV model. In the sequel we will show how to adapt the algorithm, in particular by adding rejection sampling, to avoid this leakage and complete the security proof.

Algorithm 2 DecodeUV(H, s) -Main signature building block

Parameters: n, k, kU , kV = k -kU , w Require: H = HU 0 -HV HV ∈ F (n-k)×n 3 , HU ∈ F (n/2-k U )×n/2 3 , s = (sU , sV ) ∈ F n-k 3 , sU ∈ F n/2-k U 3
Ensure: eH = s and |e| = w implicit: All of this discussion is summarized in Figure 5 where we draw ω - UV and ω + UV which are the highest and the smallest relative distances that our decoder can reach asymptotically in n when k/n is fixed and q = 3.

HV ∈ F (n/2-k V )×n/2 3 and sV ∈ F n/2-k V 3 1: eV ← DV (HV , sV

Obtaining a Preimage Sampleable Scheme

We restrict here our study to the case q = 3 but it can be generalized to larger values of q.

Achieving the Domain Sampling with the Generalized Admissible (U, U + V ) Code Family

We will denote in the rest of the article by H pk the random matrix chosen as the public parity-check matrix of our scheme S code which is defined in §3.1. Such a public-key is defined as:

H pk = SH sk P with H sk = H U D 4 M -H U D 2 M H V D 3 M -H V D 1 M where D 1 , • • • , D 4 are four diagonal matrices which verify (12) and M =(D 1 D 4 -D 3 D 2 ) -1 , S
is chosen uniformly at random among the invertible ternary matrices of size (n -k) × (n -k), H U is chosen uniformly at random among the ternary matrices of size (n/2 -k U ) × n/2, H V is chosen uniformly at random among the ternary matrices of size (n/2 -k V ) × n/2 and P is chosen uniformly at random among the permutation matrices of size n × n. Thanks to the knowledge of

n I = |{1 ≤ i ≤ n/2 : D 2 (i, i)D 4 (i, i) = 0}| .
Remark 3. n I can be viewed as the number of positions in which a codeword of the form (vD 2 , vD 4 ) is necessarily equal to 0: this comes from the fact that on a position where either D 2 (i, i) = 0 or D 4 (i, i) = 0, the other one is necessarily different from 0 as

D 1 D 3 D 2 D 4 is invertible.
In other words we also have

n I = |{1 ≤ i ≤ n/2 : D 2 (i, i) = 0}| + |{1 ≤ i ≤ n/2 : D 4 (i, i) = 0}| .
The random structure of such matrices H pk (by choosing uniformly at random matrices H U and H V ) makes that the syndromes associated to matrices H pk are indistinguishable in a very strong sense from random syndromes as the following proposition shows. In this way, our scheme achieves the Domain Sampling property of Definition 1.

Proposition 3. Let D H

w be the distribution of the syndromes eH when e is drawn uniformly at random among the ternary vectors of weight w and U be the uniform distribution over the syndrome space F n-k 3 . We have

E H pk ρ(D H pk w , U) ≤ 1 2 √ ε with ε = 3 n-k 2 w n w + w j=0 3 n/2-k V 2 j n/2 j 2 2w n/2 w 2    j p=0 w+p≡0 mod 2 j p n/2 w+p 2 w+p 2 j 2 w+3p 2    2 + 3 n/2-k U n I l=0 nI l 2 l n-n I w-l 2 w-l n w 2 w 2 n/2-n I j=0 1 2 j n/2-n I j   1 n w 2 w j h=0 n/2-n I -j p=0 n/2 -nI h n/2 -nI -h j -h n/2 -nI -j p 2nI w -j -h -2p 2 w-j-h-2p   2 (22)
Remark 4. In the paradigm of our code-based signatures we have w greater than the Gilbert-Varshamov bound, which gives 3 n-k 2 w n w and for the set of parameters we present in §9, log 2 (ε) = -1034.

The proof of this proposition is given in Appendix §B and relies among other thing on the following lemma which is a variation of the leftover hash lemma (see [BDK + 11]) and which can be expressed as follows.

Lemma 1. Consider a finite family H = (h i ) i∈I of functions from a finite set E to a finite set F . Denote by ε the bias of the collision probability, i.e. the quantity such that

P h,e,e (h(e) = h(e )) = 1 |F | (1 + ε)
where h is drawn uniformly at random in H, e and e are drawn uniformly at random in E. Let U be the uniform distribution over F and D(h) be the distribution of the outputs h(e) when e is chosen uniformly at random in E. We have

E h {ρ(D(h), U)} ≤ 1 2 √ ε.
Remark 5. In the leftover hash lemma, there is the additional assumption that H is a universal family of hash functions, meaning that for any e and e distinct in F , we have

P h (h(e) = h(e )) = 1 |F | .
This assumption allows to have a general bound on the bias ε. In our case, where the h's are hash functions defined as h(e) = eH pk , H does not form a universal family of hash functions (essentially because the distribution of the H pk 's is not the uniform distribution over F

(n-k)×n 3

). However in our case we can still bound ε by a direct computation. This lemma is proved in Appendix B.

Achieving a Uniformly Distributed Output

To be a one-way preimage sampleable function, we have to enforce that the outputs are very close to be uniformly distributed over S w . Algorithm 2 using directly the Prange decoder, does not meet this property. However, by changing it slightly, we will achieve this task by still keeping the property to output errors of weight w for which it is hard to solve the decoding problem for this weight. We summarize the situation in Figure 6.

The template remains the same but the functions D U and D V will be modified to included some rejection sampling. The Prange decoders that are used here achieve in a natural way some kind of uniformity on the output. The Prange decoder used for producing e U does not have such a nice property, its output depends in a crucial way on e V . The following notation will be useful.

Definition 4 (uniform decoder)

. A V -decoder D(H V , s V ) taking as input H V in F (n/2-k V )×n 3 , s V in F n/2-k V 3 and outputting e V in F n/2 3 satisfying e V H V = s V is uniform with respect to H V if P(e V = D(H V , s V )) is just a function of |e| when s V is chosen uniformly at random in F n/2-k V 3 .
Notation 1 For x ∈ F n 3 with n even, let x U and x V be in F n/2 3 such that x = (x U , x U + x V ).
We also denote by 1 (x) and -1 (x) the following quantities:

1 (x) = |{i | x V (i) = 1, x U (i) = 1}| -1 (x) = |{i | x V (i) = -1, x U (i) = -1}| .
Definition 5 (weakly uniform decoder). Let D be a decoder with input

H U in F (n/2-k U )×n 3 , s U in F n/2-k U 3 and e V in F n/2 3 and that outputs an e = (e U , e U + e V ) in F n 3 such that e U H U = s U . Let f (e) =(|e V | 1 , |e V | -1 , 1 (e), -1 (e), |e|). D is weakly uniform with respect to H U if P(e = D(H U , s U , e V )
) is a function of f (e) when s U and e V are chosen uniformly at random in their range.

Our U -decoder based on the Prange decoder meets this property in a natural way. With such decoders, it is rather easy to obtain a uniformly distributed output for the combined (U, U + V )decoder. The uniform distribution of our decoder follows at once from Lemma 2. Let e = (e U , e U + e V ) be the output of Algorithm 2 when s V and s U were chosen uniformly at random in

F n/2-k V 3 and F n/2-k U 3
respectively. Assume that D U is weakly uniform whereas D V is uniform. Let e unif = (e unif U , e unif U + e unif V ) be a uniformly distributed error of weight w. Let

g(e V ) =(|e V | 1 , |e V | -1
) and h(e) =( 1 (e), -1 (e), |e|).

If ρ(|e V |, |e unif

V |) = 0 and P(h(e) = z|g(e V ) = y) = P(h(e unif ) = z|g(e unif V ) = y) for any possible y and z, then ρ(e, e unif ) = 0.

Proof. Let x be in S w , H U be the matrix used in D U and f (e) =(g(e), h(e)). We have

P s U ,s V (e = x) = P s U ,s V (e = x|f (e) = (y, z))P s U ,s V (f (e) = (y, z)),
where f (x) = (y, z). Observe now that

P s U ,s V (f (e) = (y, z)) = P s U ,s V (h(e) = z|g(e V ) = y)P s V (g(e V ) = y) = P(h(e unif ) =
z|g(e unif V ) = y)P(g(e unif V ) = y). where P s V (g(e) = y) = P(g(e unif ) = y) because e V and e unif V have the same distribution. This follows from the uniformity of D V and ρ(|e V |, |e unif V |) = 0. Since e V is uniformly distributed conditioned on its weight, we have

P s U ,s V (e = x|f (e) = (y, z)) = P s U ,e V (e = D U (H U , s U , e V )|f (e) = f (x)) = P(e unif = x|f (e unif ) = f (x)).
where the last equality follows from the weak uniformity of D U . Using all these equations, we get P s U ,s V (e = x) = P(e unif = x|f (e unif ) = (y, z))P(h(e unif ) = z|g(e unif V ) = y)P(g(e unif V ) = y) = P e unif = x which concludes the proof.

The rationale of our algorithm is then to ensure that D U and D V behave as required by Lemma 2 by some mild rejection sampling. We summarize how we perform the decoding in Figure 7. It relies here among other thing on the crucial notion of information set in the Prange algorithm. The rejection sampling will be over the weight of e V which is the output of D V and over 1 (e), -1 (e) which are functions of the output of D U .

Information set in the U -decoding

e = 0 0 1 1 -1 -1 eV = = 0 1 1 -1 0 1 -1 -1 -1 0 1 = 0 -1 -1 0 1 -1 1(e) 1 1 1 -1 0 -1(e) eU eU = = 0 1 1 -1 0 1 -1 -1 -1 0 1 + Fig. 7. Summary of the decoding
The pseudo-code of D V is given in Algorithm 3. The algorithm for the U -decoder is slightly Algorithm 3 D V the V -decoder outputting an e V such that e V H V = s V .

Parameters: n, kV n/2 is the length of the code we decode, kV its dimension DV a distribution over 0, kV (rV )i rejection sampling vector, taking values in [0, 1], accept(i, r) is true with probability ri function DV (HV , sV

) repeat I ← InfoSet(HV ) t ← DV x ← {x ∈ F k V 3 | |x| = t} eV ← PrangeStep(HV , sV , I, x) until accept(|eV |, rV ) return eV
more involved and is given in Algorithm 4. By setting up the rejection vector r U and r V appropriately, we can reach the uniform distribution over S w in Algorithm 2. Rejection sampling on D V is here to meet the first condition in Lemma 2: ρ(|e V |, |e unif V |) = 0, whereas rejection sampling on D U ensures that the conditional distribution of h(e) given g(e) is the same as the distribution of h(e unif ) given g(e unif ). This is shown in Theorem 1.

Theorem 1. Let e unif be a vector chosen uniformly at random over S w . Let r V be defined as for

any i ∈ {0, • • • , n/2} as r V (i) = 1 M rs V q unif 1 (i) q 1 (i)
Algorithm 4 D U the U -decoder outputting an e U such that e U H U = s U .

Parameters: n, kU n/2 is the length of the code we decode, kU its dimension (D

t 1 ,t -1 U ) 0≤t 1 ≤n/2 0≤t -1 ≤n/2 a family of probability distribution over {(j1, j-1)|0 ≤ j1 ≤ t1, 0 ≤ j-1 ≤ t-1, 0 ≤ j1 + j-1 ≤ ku} (r t 1 ,t -1 U ) 0≤t 1 ≤n/2 0≤t -1 ≤n/2
a family of rejection sampling vectors, taking values in [0, 1], accept((i, j), r) is true with probability r(i, j) function DU (HU , sU , eV )

t1, t-1 ← |eV |1, |eV |-1 repeat j1, j-1 ← D t 1 ,t -1 U I ← InfoSetW(HU , eV , j1, j-1) InfoSetW() is defined below x ← {x ∈ F n/2 3 | Supp(x) = I and xJ = (eV )J , J = I ∩ Supp(eV )} eU ← PrangeStep(HU , sU , I, x) 1, -1 ← |{i | eV (i) = 1, eU (i) = 1}| , |{i | eV (i) = -1, eU (i) = -1}| until accept(( 1, -1), rU ) return eU
function InfoSetW(H, e, j1, j-1) -weighted information set

Require: H ∈ F (n-k)×n 3 , e ∈ F n
3 , j1, j-1 positive integers such that j1 + j-1 ≤ k Ensure: the returned value I is an information set of H ⊥ such that the number of positions i in I for which ei = b is equal to j b for b in {1, -1}.

with q unif 1 (i) = P(|e unif V | = i), q 1 (i) = P(|D V (H V , s V )| = i), and
M rs V = sup 0≤i≤n/2 q unif 1 (i)
q1(i) . The norejection probability vector r t1,t-1 U is chosen for any i ∈ 0, t 1 and j ∈ 0, t -1 as

r t1,t-1 U (i, j) = 1 M rs U (t 1 , t -1 ) q unif 2 (i, j|t 1 , t -1 ) q 2 (i, j|t 1 , t -1 ) with q unif 2 (i, j|t 1 , t -1 ) = P 1 (e unif ) = i, -1 (e unif ) = j |e unif V | b = t b , b = -1, 1} q 2 (i, j|t 1 , t -1 ) = P( 1 (ẽ) = i, -1 (ẽ) = j |ẽ V | b = t b , b = -1, 1) M rs U (t 1 , t -1 ) = sup 0≤i≤t1 0≤j≤t-1 q unif 2 (i, j|t 1 , t -1 ) q 2 (i, j|t 1 , t -1 )
,

where ẽ = (ẽ U , ẽU + e unif V ) with ẽU being the output of PrangeStep(H U , s U , I, x) in Algorithm 4 and (H U , s U , e unif V ) is its input, where s U is uniformly distributed. Then if D U is weakly uniform and D V uniform, we have that the output e of Algorithm 2 satisfies ρ(e, e unif ) = 0.

To have an efficient algorithm, it is essential that M rs (1) and the M rs (t 1 , t -1 )'s are as small as possible. These numbers represent the average number of times the repeat loops in those algorithms are performed. This is achieved by a particular choice of the parameters w, k U , k V . Roughly speaking, the idea for having M rs (1) and the M rs (t 1 , t -1 )'s to be small is that the output ẽV of PrangeStep(H V , s V , I, x) in Algorithm 3 and the output ẽU of PrangeStep(H U , s U , I, x) in Algorithm 4 satisfy

E(| ẽV |) = E(|e unif V |) and E(| ẽU |) = E(|e unif U |). We also require that E(|( ẽU , ẽU + e unif V )|) = E(|e unif |). Set α by (1 -α)k V = E(T ),
where T is a random variable distributed like D V . These requirements lead to the following choice of parameters

w = n 1 -α + 1 3 (3α -1) 3α + 4 k n -1 (23) k V = n 2 3 3α -1 1 - w n 2 + 1 2 w n 2 - 1 3 (24) k U = n 2 -2 + 3 w n ( 25
)
Figure 8 gives the relative error weight ω = w/n as a function of R for α = 0.7 of Algorithm 2 with rejection sampling and the previous choice of parameters asymptotically in n when k/n is fixed.

Security Proof

We give in this section a security proof of the signature scheme S code . This proof is extremely close in spirit of the security proof of [START_REF] Gentry | Trapdoors for hard lattices and new cryptographic constructions[END_REF]. However we do not reduce the security of S code to a problem of collision as the scheme imposes to be in a range of parameters where this problem becomes easy (for more details see §7.3) .

Furthermore, we would like to stress that this section is a slightly different version of the unpublished paper [DST17b, Section 3]. We added in order to have a self-contain paper and not to refer many times to results of [START_REF] Debris-Alazard | The problem with the surf scheme[END_REF].

Basic Tools

Basic Definitions. Recall that the statistical distance ρ is defined in Section §2. We will need the following well known property for the statistical distance which can be easily proved by induction.

Proposition 4. Let (D 0 1 , . . . , D 0 n ) and (D 1 1 , . . . , D 1 n ) be two n-tuples of discrete probability distributions where D 0 i and D 1 i are distributed over a same space E i . We have for all positive integers n:

ρ D 0 1 ⊗ • • • ⊗ D 0 n , D 1 1 ⊗ • • • ⊗ D 1 n ≤ n i=1 ρ(D 0 i , D 1 i ).
A distinguisher between two distributions D 0 and D 1 over the same space E is a randomized algorithm which takes as input an element of E that follows the distribution D 0 or D 1 and outputs b ∈ {0, 1}. It is characterized by its advantage:

Adv D 0 ,D 1 (A) = P ξ∼D 0 (A(ξ) outputs 1) -P ξ∼D 1 (A(ξ) outputs 1) .
We call this quantity the advantage of A against D 0 and D 1 .

Definition 6 (Computational Distance and Indistinguishability). The computational distance between two distributions D 0 and D 1 in time t is:

ρ c D 0 , D 1 (t) = max |A|≤t Adv D 0 ,D 1 (A)
where |A| denotes the running time of A on its inputs. The ensembles

D 0 = (D 0 n ) and D 1 = (D 1 n ) are computationally indistinguishable in time (t n ) if their computational distance in time (t n ) is negligible in n.
In other words, the computational distance is the best advantage that any adversary could get in bounded time.

Digital Signature and Games. Let us recall the concept of signature schemes, the security model that will be considered in the following and to recall in this context the paradigm of games in which we give a security proof of our scheme.

Definition 7 (Signature Scheme). A signature scheme S is a triple of algorithms Gen, Sgn, and Vrfy which are defined as:

-The key generation algorithm Gen is a probabilistic algorithm which given 1 λ , where λ is the security parameter, outputs a pair of matching public and private keys (pk, sk); -The signing algorithm is probabilistic and takes as input a message m ∈ {0, 1} * to be signed and returns a signature σ = Sgn sk (m); -The verification algorithm takes as input a message m and a signature σ. It returns Vrfy pk (m, σ)

which is 1 if the signature is accepted and 0 otherwise. It is required that

Vrfy pk (m, σ) = 1 if σ = Sgn sk (m).
For this kind of scheme, one of the strongest security notion is existential unforgeability under an adaptive chosen message attack (EUF-CMA). In this model the adversary has access to all signatures of its choice and its goal is to produce a valid forgery. A valid forgery is a message/signature pair (m, σ) such that Vrfy pk (m, σ) = 1 whereas the signature of m has never been requested by the forger. More precisely, the following definition gives the EUF-CMA security of a signature scheme:

Definition 8 (EUF-CMA Security). Let S be a signature scheme.

A forger A is a (t, q hash , q sign , ε)-adversary in EUF-CMA against S if after at most q hash queries to the hash oracle, q sign signatures queries and t working time, it outputs a valid forgery with probability at least ε. We define the EUF-CMA success probability against S as:

Succ EUF-CMA

S

(t, q hash , q sign ) = max (ε|it exists a (t, q hash , q sign , ε)-adversary) .

The signature scheme S is said to be (t, q hash , q sign )-secure in EUF-CMA if the above success probability is a negligible function of the security parameter λ.

The Game Associated to Our Code-Based Signature Scheme. The modern approach to prove the security of cryptographic schemes is to relate the security of its primitives to well-known problems that are believed to be hard by proving that breaking the cryptographic primitives provides a mean to break one of these hard problems. In our case, the security of the signature scheme is defined as a game with an adversary that has access to hash and sign oracles. It will be helpful here to be more formal and to define more precisely the games we will consider. They are games between two players, an adversary and a challenger. In a game G, the challenger executes three kind of procedures:

an initialization procedure Initialize which is called once at the beginning of the game.

oracle procedures which can be requested at the will of the adversary. In our case, there will be two, Hash and Sign. The adversary A which is an algorithm may call Hash at most q hash times and Sign at most q sign times. a final procedure Finalize which is executed once A has terminated. The output of A is given as input to this procedure.

The output of the game G, which is denoted G(A), is the output of the finalization procedure (which is a bit b ∈ {0, 1}). The game G with A is said to be successful if G(A) = 1. The standard approach for obtaining a security proof in a certain model is to construct a sequence of games such that the success of the first game with an adversary A is exactly the success against the model of security, the difference of the probability of success between two consecutive games is negligible until the final game where the probability of success is the probability for A to break one of the problems which is supposed to be hard. In this way, no adversary can break the claim of security with non-negligible success unless it breaks one of the problems that are supposed to be hard.

Definition 9 (challenger procedures in the EUF-CMA Game). The challenger procedures for the EUF-CMA Game corresponding to S code are defined as:

proc Initialize(λ) proc Hash(m, r) proc Sign(m) proc Finalize(m, e, r) (pk, sk) ← Gen(1 λ ) return Hash(m, r) r ← {0, 1} λ0 s ← Hash(m, r) H pk ← pk s ← Hash(m, r) return (H sk , P, S) ← sk e ← D Hsk,w (s(S -1 ) ) eH pk = s ∧ |e| = w return H pk return (eP, r)

Code-Based Problems

We introduce in this subsection the code-based problems that will be used in the security proof. The first is Decoding One Out of Many (DOOM) which was first considered in [START_REF] Johansson | On the complexity of some cryptographic problems based on the general decoding problem[END_REF] and later analysed in [START_REF] Sendrier | Decoding one out of many[END_REF]. We will come back to the best known algorithms to solve this problem as a function of the distance w in §7.

Problem 2. (DOOM -Decoding One Out of Many

). Given H ∈ F (n-k)×n q , s 1 , • • • , s N ∈ F n-k q
, and an integer w, find e ∈ F n q and i, 1 ≤ i ≤ N such that such that eH = s i and |e| = w.

Definition 10 (One-Wayness of DOOM). We define the success of an algorithm A against DOOM with the parameters n, k, N, w as:

Succ n,k,N,w DOOM (A) = P A (H, s 1 , • • • , s N ) solution of DOOM
where H is chosen uniformly at random in F

(n-k)×n q

, the s i 's are chosen uniformly at random in F n-k q and the probability is taken over these choices of H, the s i 's and the internal coins of A. The computational success in time t of breaking DOOM with the parameters n, k, N, w is then defined as:

Succ n,k,N,w DOOM (t) = max |A|≤t Succ n,k,N,w DOOM (A) .
Another problem will appear in the security proof: distinguish random codes from a code drawn uniformly at random in the family used for public keys in the signature scheme. The public-keys, namely matrices H pk , follow a distribution over the parity-check matrices of size (n -k U -k V ) × n which is described in §5.1. In the following we will denote by D pub this distribution. On the other hand D rand will denote the uniform distribution over the parity-check matrices of all [n, k]-codes with k = k U + k V . We will discuss about the difficulty of the task to distinguish D pub and D rand in §8. Let us recall that the syndromes associated to matrices H pk are indistinguishable in a very strong sense from random syndromes as the proposition 3 (see §5.1) shows in the case of q = 3.

EUF-CMA Security Proof

This subsection is devoted to our security reduction and its proof. We give it in the case of q = 3. Let us first introduce some notations that will be used. We will denote by D w the output distribution of Algorithm 2. Furthermore, we will denote Algorithm 2 by D H sk ,w (•) for a secret key H sk . Recall that U w is the uniform distribution over S w (which is the set of words of weight w in F n 3 ), D pub is the distribution of public keys, D rand is the uniform distribution over parity-check matrices of all [n, k]-codes and S code is our signature scheme defined in §3.1 with the family of generalized admissible (U, U + V )-codes (Definition 2 in §4.2).

Theorem 2 (Security Reduction). Let q hash (resp. q sign ) be the number of queries to the hash (resp. signing) oracle. We assume that λ 0 = λ + 2 log 2 (q sign ) where λ is the security parameter of the signature scheme. We have in the random oracle model (ROM) for all time t: Succ EUF-CMA S code (t, q hash , q sign ) ≤ 2Succ n,k,q hash ,w

DOOM (t c ) + ρ c (D rand , D pub ) (t c ) + q sign ρ (D w , U w ) + 1 2 q hash √ ε + 1 2 λ
where t c = t + O q hash • n 2 and ε given in Proposition 3.

Proof. Let A be a (t, q sign , q hash , ε)-adversary in the EUF-CMA model against S code and let (H 0 , s 1 , • • • , s q hash ) be drawn uniformly at random among all instances of DOOM for parameters n, k, q hash , w. We stress here that syndromes s j are random and independent vectors of F n-k 3 . We write P (S i ) to denote the probability of success for A of game G i . Let Game 0 is the EUF-CMA game for S code .

Game 1 is identical to Game 0 unless the following failure event F occurs: there is a collision in a signature query (i.e. two signatures queries for a same message m lead to the same salt r). By using the difference lemma (see for instance [Sho04, Lemma 1]) we get: P (S 0 ) ≤ P (S 1 ) + P (F ) .

The following lemma (see A.2 for a proof) shows that in our case as λ 0 = λ + 2 log 2 (q sign ), the probability of the event F is negligible. Lemma 3. For λ 0 = λ + 2 log 2 (q sign ) we have:

P (F ) ≤ 1 2 λ .
Game 2 is modified from Game 1 as follows:

proc Hash(m, r) proc Sign(m) if r ∈ L m r ← L m .next() e m,r ← S w
s ← Hash(m, r) return e m,r H pk e ← D Hsk,w (s(S -1 ) ) else return (eP, r) j ← j + 1 return s j

To each message m we associate a list L m containing q sign random elements of F λ0 2 . It is constructed the first time it is needed. The call r ∈ L m returns true if and only if r is in the list. The call L m .next() returns elements of L m sequentially. The list is large enough to satisfy all queries.

The Hash procedure now creates the list L m if needed, then, if r ∈ L m it returns e m,r H pk with e m,r ← S w . Although we do not use it in this game, we remark that (e m,r , r) is a valid signature for m. The error value is stored. If r ∈ L m it outputs one of s j of the instance (H 0 , s 1 , . . . , s q hash ) of the DOOM problem. The Sign procedure is unchanged, except for r which is now taken in L m . The global index j is set to 0 in proc Initialize.

We can relate this game to the previous one through the following lemma.

Lemma 4. P(S 1 ) ≤ P(S 2 ) + q hash 2 √ ε where ε is given in Proposition 3.

The proof of this lemma is given at the end of Appendix B and relies among other things on the following points:

-Proposition 4; -Syndromes produced by matrices H pk with errors of weight w have average statistical distance from the uniform distribution over F n-k

3 at most 1 2 √ ε (see Proposition 3).
Game 3 differs from Game 2 by changing in proc Sign calls "e ← D H sk ,w (s(S -1 ) )" by "e ← e m,r " and "return (eP, r)" by "return (e, r)". Any signature (e, r) produced by proc Sign is valid. The error e is drawn according to the uniform distribution U w while previously it was drawn according to Algorithm 2 distribution, that is D w . By using Proposition 4 it follows that P (S 2 ) ≤ P (S 3 ) + q sign ρ (U w , D w ) .

Game 4 is the game where we replace the public matrix H pk by H 0 . In this way we will force the adversary to build a solution of the DOOM problem. Here if a difference is detected between games it gives a distinguisher between distributions D rand and D pub :

P (S 3 ) ≤ P (S 4 ) + ρ c (D pub , D rand ) (t c ) .
We show in appendix how to emulate the lists L m in such a way that list operations cost, including its construction, is at most linear in the security parameter λ. Since λ ≤ n, it follows that the cost to a call to proc Hash cannot exceed O(n 2 ) and the running time of the challenger is t c = t + O q hash • n 2 . Game 5 differs in the finalize procedure.

proc Finalize(m, e, r) s ← Hash(m, r) b ← eH pk = s ∧ |e| = w return b ∧ r / ∈ L m
We assume the forger outputs a valid signature (e, r) for the message m. The probability of success of Game 5 is the probability of the event "S 4 ∧ (r ∈ L m )".

If the forgery is valid, the message m has never been queried by Sign, and the adversary never had access to any element of the list L m . This way, the two events are independent and we get:

P (S 5 ) = (1 -2 -λ0 ) qsign P (S 4 ) .
As we assumed λ 0 = λ + 2 log 2 (q sign ) ≥ log 2 (q 2 sign ), we have:

1 -2 -λ0 qsign ≥ 1 - 1 q 2 sign qsign ≥ 1 2 . Therefore P (S 5 ) ≥ 1 2 P (S 4 ) . (26)
The probability P (S 5 ) is then exactly the probability for A to output e j ∈ S w such that e j H 0 = s j for some j which gives

P (S 5 ) ≤ Succ n,k,q hash ,w DOOM (t c ). (27)
(26) together with (27) imply that

P(S 4 ) ≤ 2 • Succ n,k,q hash ,w DOOM (t c ).
This concludes the proof of Theorem 2 by combining this together with all the bounds obtained for each of the previous games.

Hardness of Finding Errors of Large Weight with Prescribed Syndrome

We consider the syndrome decoding problem

Problem 3 (Syndrome Decoding). Given H ∈ F (n-k)×n q , s ∈ F n-k q
, and an integer w, find e ∈ F n q such that eH = s and |e| = w.

This problem is NP-hard [START_REF] Berlekamp | On the inherent intractability of certain coding problems[END_REF], even when the weight w is fixed to any proportion of n [START_REF] Stern | Approximating the number of error locations within a constant ratio is NPcomplete[END_REF]. We discuss here the best solvers with a focus on non binary alphabets and weights close to n. In the sequel, we will denote SD(H, s, w) an instance of this problem.

Solving Syndrome Decoding for High Weights

In code-based cryptography, Problem 3 is usually considered for "small" values of w. The best known solvers derive from Algorithm 5 [START_REF] Prange | The use of information sets in decoding cyclic codes[END_REF], often referred to as Information Set Decoding (ISD). As it is described here, it runs repeatedly a polynomial time step, until it outputs e of Algorithm 5 Prange(H, s)

Parameters (q, n, k, w)

Require: H ∈ F (n-k)×n q
, s ∈ F n-k q Ensure: eH = s and |e| = w 1: repeat 2: I ← InfoSet(H)

3:

x ← {x ∈ F n q | |xI| = t} t = min k, max 0, w -q-1 q (n -k) 4:

e ← PrangeStep(H, s, I, x) 5: until |e| = w 6: return e The functions InfoSet() and PrangeStep() are defined in Algorithm 1. weight w. On input M ∈ F a×b q , the call GaussElim(M) returns an a × b matrix M starting with an a × a identity block and such that for some non singular matrix S, we have SM = M . If M doesn't exist, the call fails. The | denotes matrix concatenation.

Dumer's variant of ISD [START_REF] Dumer | On minimum distance decoding of linear codes[END_REF] is very similar to Stern's variant [START_REF] Stern | A method for finding codewords of small weight[END_REF]. We will limit the description and analysis to instances of Problem 3 with q ≥ 3 and w > k + q-1 q (n -k). On input M ∈ F a×b q , the call GaussElimPartial (M) returns an a × b matrix M whose first a -rows start with an (a -) × (a -) identity block, whose last rows start with a × (a -) zero block, and such that for some non singular matrix S, we have SM = M . If M doesn't exist, the call fails. The call CollisionSearch(H , s , E 1 , E 2 ) returns the set

E = {e ∈ E 1 × E 2 | eH = s }.

Complexity Analysis

We want to estimate the expected running time of Algorithm 5 and Algorithm 6 when its input (H, s) is drawn uniformly at random in

I q,n,k,w = (H, s) ∈ F (n-k)×n q × F n-k q rank(H) = n -k, s ∈ {eH | e ∈ F n q , |e| = w} .
Algorithm 6 Dumer(H, s)

Parameters (q, n, k, w), q ≥ 3, w ≥ k + q-1 q (n -k) Additional parameters p, , and L, tuned for each (q, n, k, w) such that 0 ≤ p ≤ n -w, 0 ≤ ≤ w -k + p, and 1

≤ L ≤ (k+ )/2 p/2 (q -1) (k+ -p)/2 Require: H ∈ F (n-k)×n q , s ∈ F n-
Require: H ∈ F (n-k)×n q , I contains an information set of H ⊥ and |I| = k + Ensure: returns S, H , H ∈ F (n-k)×(n-k) q ×F (n-k-)×n q ×F ×n q such that S is non singular, Supp(H ) ⊂ I, and H H = SH.
The space H is a shortened code, it consists of all words of H whose support is included in I. The space H supplements H in H . The fact that I is an information set of H ⊥ guaranties the existence of S, H , H .

function BirthdaySD(H, s, w, I, L) -birthday syndrome decoding Require: H ∈ F ×n q , s ∈ F q , w an integer, 0 ≤ w ≤ |I|, Supp(H) ⊂ I a set of coordinate indices, L an integer, 1 ≤ L ≤ |I|/2 w/2 (q -1) w/2 Ensure: E ⊂ {e ∈ F n q | |e| = w, eH = s, Supp(e) ⊂ I} 1: I1 ∪ I2 ← I disjoint union, split I evenly 2:

for i = 1, 2 do Ei ← subset of L elements of {e ∈ F n q | |e| = w/2, Supp(e) ⊂ Ii} 3: E ← {e ∈ E1 × E2 | eH = s} 4: return E
We do not detail instruction 3:. We will admit in the analysis that E has cardinality L 2 q -on average and can be obtained for a cost max(|E1|, |E2|, |E|) = max(L, L 2 q -) up to a polynomial factor.

This forces the problem to admit a solution and corresponds to the typical situation in cryptanalysis.

Proposition 5 (Complexity of Prange's Algorithm). We consider Algorithm 5 with parameters (q, n, k, w) and an input (H, s) drawn uniformly at random in I q,n,k,w . Up to a polynomial factor, the algorithm has an expected running time equal to WF 0 (q, n, k, w) = 1/P 0 where

P 0 = n-k w-t (q -1) w-t min q n-k , n w (q -1) w with t =      0 if w ≤ q-1 q (n -k) k if w ≥ k + q-1 q (n -k) w -q-1 q (n -k) else , ( 28
)
is the probability, up to a constant factor, that the instruction 5: produces a word of weight w.

Lemma 5. For any E ⊂ F n q , we have, on average over all H ∈ F

(n-k)×n q 1 2 ≤ |{eH | e ∈ E}| min (q n-k , |E|) ≤ 1.
Proof (Proof of Proposition 5). We use the notation of Algorithm 5. The proof is similar to the proof of Proposition 2. The main difference is that we choose (H, s) in I q,n,k,w instead of

F (n-k)×n q × F n-k q
. Choosing H of full rank has a negligible impact on the probabilities. The choice of s has an impact as we choose it in the set {eH | e ∈ F n q , |e| = w} which might differ significantly from F n-k q . From the above lemma, its size is equal to min q n-k , n w (q -1) w up to a factor at most 2. In formula (11) of Proposition 2, we replace the denominator q n-k by min q n-k , n w (q -1) w . Also, in Algorithm 5 the weight t has a fixed value depending on the parameters q, n, k, w and finally the probability to reach |e| = w is, from (11), equal to

P 0 = P (|e| = w) = n-k w-t (q -1) w-t min q n-k , n w (q -1) w
up to a small constant. We will thus iterate on average 1/P 0 times an elementary step of polynomial cost, dominated by the linear algebra in PrangeStep(•). This concludes the proof.

When t = w -q-1 q (n -k) in (28) the probability P 0 is proportional to 1/ √ n -k in all other cases it is exponentially small in n. For a fixed code rate R = k/n and error rate ω = w/n, the following limit is defined and is called the asymptotic exponent

c q (R, ω) = lim n→∞ 1 n log 2 WF 0 (q, n, Rn, ωn).
We give this exponent for R = 1/2 and q ∈ {2, 3} in Figure 9. The exponent is null for middle values of ω, this means that the corresponding error weights can be obtained in polynomial time in n. We remark that for q = 2 the problem is symmetric with respect to the error weight w. In that case, finding a word of weight w with prescribed syndrome is exactly as hard as finding a word of weight n -w with prescribed syndrome. Indeed, for q = 2, solving the instance (H, s, w) of Problem 3 is the same thing as solving the instance (H, s+1H , n-w). For larger q, the symmetry disappears. The singular points correspond to the solutions of n w (q -1) w = q n-k . On left-hand side it is the Gilbert-Varshamov distance. On the right hand side it exists only if n-k n > log(q-1) log q . For instance for q = 3, only if k/n < 1 -1/ log 2 3 ≈ 0.37.

c q (R, ω) R = 1/2, q = 2 R = 1/2, q = 3 R = 1/4, q = 2 R = 1/4, q = 3
In the sequel, low weight will refer to the left-hand side of Figure 9, with w ≤ q-1 q (n -k) which corresponds to the traditional syndrome decoding parameters while high weight will refer to the right-hand side of Figure 9, with w > k + q-1 q (n -k), corresponding to the parameters of interest in this work.

Proposition 6 (Complexity of Dumer Algorithm). We consider Algorithm 6 with parameters (q, n, k, w, p, , L) and an input (H, s) drawn uniformly at random in I q,n,k,w . Up to a polynomial factor, the algorithm has an expected running time equal to WF p, ,L (q, n, k, w) = max 1, q P p, L 2 max L,

L 2 q , ( 29
)
where

P p, = q n-k- w-k-+p (q -1) w-k-+p min q n-k , n w (q -1) w . ( 30
)
is the probability, up to a constant factor, that the instruction 7: produces a word of weight w.

Proof. Any e ∈ E has weight t = k + -p and it is completed by PrangeStep(•) with n -krandom coordinates. We want to estimate the probability that this completion give a word of weight w. We apply Proposition 2, H ∈ F

(n-k-)×n q and s ∈ F n-k- q with a distribution of |e | which is concentrated on t = k + -p. The denominator is the number of possible input syndrome s divided by q because s ∈ F q is fixed, that is q -min q n-k , n w (q -1) w . We obtain

P p, = q n-k- w-t (q -1) w-t min q n-k , n w (q -1) w with t = k -+ p.
The instruction 7: will be executed 1/P p, times on average. We have |E| = L 2 q -on average, thus the main loop is executed 1/(P p, |E|) times, rounded up. Instructions 2: to 5: will cost max(L, |E|) up to a polynomial factor. In total, up to a polynomial factor, we thus have (29).

In the sequel, we will denote WF Dumer (q, n, k, w) = min (p, ,L)∈P WF p, ,L (q, n, k, w)

where P = (p, , L) | 0 ≤ p ≤ n -w, 0 ≤ ≤ w -k + p, 1 ≤ L ≤ k+ p (q -1) (k+ -p)
is the set of admissible optimization parameters.

Corollary 1. For any (q, n, k, w), let 0 denote the solution of P 0, 0 = q -0 . We have max 1, q 0 (q -1) (k+ 0 )/2 ≥ WF Dumer (q, n, k, w) q 0 ≥ 1 (31) up to a polynomial factor.

Proof. (Sketch) We will minimize the formula (29

) over P = {(p, , L) | 0 ≤ p ≤ n -w, 0 ≤ ≤ w -k + p, L ≥ 1}
, that is we ignore the upper bound for L. Since P ⊂ P , this will give us a lower bound for the work factor (whose tightness is discussed later). When q > 2 and w ≥ k + q-1 q (n -k), and L is not upper bounded, an easy analysis shows the following, up to a polynomial factor.

-It is best to choose 1 = q P p, L 2 and L = L 2 q . Thus parameters such that L = q = P -1 p, are optimal.

-The function p → P p, is decreasing with p in the neighbourhood of the optimal parameters. It follows that p = 0 is optimal. -The equation q P 0, = 1 has a single solution 0 ∈ [0, w -k].

It follows that (p, , L) = (0, 0 , q 0 ) minimizes (29) over P , and the right-hand side inequality of the statement holds. Let L 0 = min(q 0 , (q -1) (k+ 0)/2 ), we have (0, 0 , L 0 ) ∈ P. The evaluation of the work factor for this set of parameter provides the left-hand side upper bound. Tightness of Corollary 1. Every time q 0 ≤ (q -1) (k+ 0)/2 the bound (31) is tight. For high weights and non-binary alphabet, this happens for many system parameters of interest. It corresponds to situations where (q -1) (k+ )/2 is large enough, and allows the choice of a list size L large enough to succeed in a constant number of iterations even with p = 0.

In contrast, in the low weight case, the upper bound for L is k+ p (q -1) p and p = 0 correspond to an irrelevant degenerated case where L = 1.

The bound of Corollary 1 is tight when k/n ≥ 1 -log q (q -1) and all w k/n < 1 -log q (q -1) and

w ≤ k + (n -k)ω -(1 -λ)ω where λ = log(q-1)
2 log q-log(q-1) and ω is the solution3 of H q (ω) = n-(1+2λ)k n-(1+λ)k larger than q-1 q . Note that ω exists only if k < 1 -log q (q -1).

For q = 3, the bound is tight when k/n > 0.369. In the current work we will never use smaller code rates. As for Prange's algorithm, we may define the asymptotic exponent for a given R = k/n and ω = w/n as

c q (R, ω) = lim n→∞ 1 n log 2 WF Dumer (q, n, Rn, ωn).
Exponents are plotted for Prange and Dumer (bound) for q = 3, R ∈ {1/2, 1/4}, and large values of ω.

c 3 (R, ω) Prange, R = 1/2 Dumer, R = 1/2 Prange, R = 1/4 Dumer, R = 1/4
Further Improvement The Algorithm 6 for high error weights and q > 2 has an interesting feature when the code rate is large enough (k/n ≥ 1 -log q (q -1), see Corollary 1). The optimal value for parameter p is zero and the optimal value of the list size L is below its upper bound (q-1) (k+ )/2 . It corresponds to a situation where the algorithm requires a single or a few iterations, and increasing L would simply increase the cost of each iteration without the benefit of reducing the number of iterations. For low weights, Dumer's algorithm performs an exponential number of loop iterations and the list size L meets its upper bounded k+ p (q -1) p . The best improvements [MMT11, BJMM12] are using the representation technique, they essentially improve the CollisionSearch to allow a larger upper bound for L. Those algorithms perform a smaller, but still exponential, number of iterations, each having a larger list size and thus an improved "birthday effect". This won't happen in the high weight situation when k/n ≥ 1 -log q (q -1) (k/n ≥ 0.369 for q = 3). The nearest neighbour approach [START_REF] May | On computing nearest neighbors with applications to decoding of binary linear codes[END_REF] might still allow some improvement but needs to be thoroughly revisited.

Previous Works In the binary case, we have seen earlier that the syndrome decoding problem is equally hard for low and high weights. For larger alphabets there is no obvious reduction one way or the other between low and high weights problems and the high weight syndrome decoding does not seem easier than its low weight counterpart.

Except for the "Furthest neighbour" algorithm mentioned in [START_REF] Indyk | Better algorithms for high-dimensional proximity problems via asymmetric embeddings[END_REF], we are not aware in the literature of any algorithm related to decoding far from the received word.

Indeed, more research is needed to improve the understanding of high weight syndrome decoding.

Application to the Proposed Signature

In the current work, we will focus on the case q = 3 with high weight w ≥ k + q-1 q (n -k), and a large enough code rate k/n ≥ 1 -log q (q -1) = 0.369. This corresponds to a situation where Problem 3 has an exponentially large number of solutions and the best known solver is Dumer's algorithm with p = 0 and a constant number of iterations.

DOOM vs. Collisions

Problem 4 (Syndrome Collision). Given H ∈ F (n-k)×n q and an integer w, find e, e distinct in F n q such that eH = e H and |e| = |e | = w.

When q ≥ 3 the above problem is not harder than finding a non-zero word x ∈ F n q of weight ≤ 2w such that xH = 0. Indeed, given x = 0 it is a simple matter to find e, e such that ee = x and |e| = |e | = w for any w ≥ |x|/2. It follows that for high weights and a non binary alphabet the Syndrome Collision problem is always easy.

The key primitive in our design is the syndrome e → eH with |e| = w. In the GPV setting [START_REF] Gentry | Trapdoors for hard lattices and new cryptographic constructions[END_REF], one of the feature needed for designing a secure signature scheme is collision-freeness. From the above remark, this cannot be achieved for syndromes with high w. Instead, our reduction will require the primitive to be resistant to multi-target preimage, namely the Decoding One Out of Many (DOOM) problem.

Problem 2. (DOOM -Decoding One Out of Many

). Given H ∈ F (n-k)×n q , s 1 , • • • , s N ∈ F n-k q
, and an integer w, find e ∈ F n q and i, 1 ≤ i ≤ N such that such that eH = s i and |e| = w. In DOOM, the adversary considers an arbitrary large number of instances of syndrome decoding in which only syndrome s varies, and needs to solve only one of them.

What the DOOM variant of ISD [START_REF] Sendrier | Decoding one out of many[END_REF] does to deal with N instances consists essentially in (i) multiplying the cost of the iteration, in fact the list size by √ N , and (ii) dividing the number of iteration by N . The number iterations cannot be lower than 1, and this limits in practice the number of instances that can be efficiently treated simultaneously. In our case, Dumer's algorithm is already reduced to a single iteration and no improvement is possible with this method. With the current state-of-the-art the DOOM problem for high weights does not appear easier to solve than the Syndrome Decoding problem.

Distinguishing a Permuted Admissible Generalized (U, U + V ) Code

A permissible generalized (U, U + V ) code where U and V are random seems very close to a random linear code. We assume in the whole section that such a code is defined from a 4-tuple of matrices that we denote by (D 1 , D 2 , D 3 , D 4 ). There is for instance only a very slight difference between the weight distribution of a random linear code and the weight distribution of a random admissible generalized (U, U + V )-code of the same length and dimension. This slight difference happens for small and large weights and is due to codewords where v = 0 or u = 0 which are of the form (uD 1 , uD 3 ) where u belongs to U or codewords of the form (vD 2 , vD 4 ) where v belongs to V . This weight distribution will depend on the matrices D i 's. The definition of number of V blocks (see Definition 3 in §5.1) is helpful for describing the codewords of the form (vD 2 , vD 4 ). With this definition at hand, we have the following proposition Proposition 7. Assume that we choose an admissible generalized (U, U + V ) code over F 3 with a number n I of linear combinations of type I by picking the parity-check matrices of U and V uniformly at random among the ternary matrices of size (n/2 -k U ) × n/2 and (n/2 -k V ) × n/2 respectively. Let a (u,v) (w), a (u,0) (w) and a (0,v) (w) be the expected number of codewords of weight w that are respectively in the admissible generalized (U, U +V ) code, of the form (uD 1 , uD 3 ) where u belongs to U and of the form (vD 2 , vD 4 ) where v belongs to V . These numbers are given for even w in {0, . . . , n} by

a (u,0) (w) = n/2 w/2 2 w/2 3 n/2-k U ; a (0,v) (w) = 1 3 n/2-k V w j=0 j even n I j n/2 -n I w-j 2 2 (w+j)/2 a (u,v) (w) = a (u,0) (w) + a (0,v) (w)+ 1 3 n-k U -k V     n w 2 w - n/2 w/2 2 w/2 - w j=0 j even n I j n/2 -n I w-j 2 2 (w+j)/2     and for odd w ∈ {0, • • • , n} by a (u,0) (w) = 0 ; a (0,v) (w) = 1 3 n/2-k V w j=0 j odd n I j n/2 -n I w-j 2 2 (w+j)/2 a (u,v) (w) = a (0,v) (w) + 1 3 n-k U -k V     n w 2 w - w j=0 j odd n I j n/2 -n I w-j 2 2 (w+j)/2    
On the other hand, when we choose a linear code of length n over F 3 with a random parity-check matrix of size (n -k U -k V ) × n chosen uniformly at random, then the expected number a(w) of codewords of weight w > 0 is given by

a(w) = n w 2 w 3 n-k U -k V .
The proof of this proposition is in Appendix §C Remark 6. When the generalized (U, U + V ) code is chosen in this way, its dimension is

k U + k V with probability 1 -O max(3 k U -n/2 , 3 k V -n/2
) . This also holds for the random codes of length n.

We have plotted in Figure 11 the normalized logarithm of the density of codewords of the form (uD 1 , uD 3 ) and (vD 2 vD 4 ) of relative even weight x = w n against x in the case where U is of rate

k U n/2 = 0.7, V is of rate k V n/2 = 0.
3 and n I n/2 = 1 2 . These two relative densities are defined respectively by

α u (w/n) = log 2 (a (u,0) (w)/a (u,v) (w)) n ; α v (w/n) = log 2 (a (0,v) (w)/a (u,v) (w))
n We see that for a relative weight w/n below approximately 0.26 almost all the codewords are of the form (uD 1 , uD 3 ) in this case.

Since the weight distribution is invariant by permuting the positions, this slight difference also survives in the permuted version of the admissible generalized (U, U +V ) code. These considerations lead to the best attack we have found for recovering the structure of a permuted admissible generalized (U, U + V ) code. It consists in applying known algorithms aiming at recovering low weight codewords in a linear code. We run such an algorithm until getting at some point either a permuted (uD 1 , uD 3 ) codeword where u is in U or a permuted (vD 2 , vD 4 ) codeword where v belongs to V . The rationale behind this algorithm is that the density of codewords of the form (uD 1 , uD 3 ) or (vD 2 , vD 4 ) is bigger when the weight of the codeword gets smaller.

Once we have such a codeword we can bootstrap from there very similarly to what has been done in [START_REF] Otmani | An efficient attack on all concrete KKS proposals[END_REF]Subs. 4.4]. Note that this attack is actually very close in spirit to the attack that was devised on the KKS signature scheme [START_REF] Otmani | An efficient attack on all concrete KKS proposals[END_REF]. In essence, the attack against the KKS scheme really amounts to recover the support of the V code. The difference with the KKS scheme is that the support of V is much bigger in our case. As explained in the conclusion of [START_REF] Otmani | An efficient attack on all concrete KKS proposals[END_REF] the attack against the KKS scheme has in essence an exponential complexity. This exponent becomes really prohibitive in our case when the parameters of U and V are chosen appropriately as we will now explain.

Recovering the U Code up to Permutation

We consider here the permuted code

U =(U D 1 , U D 3 )P = {(uD 1 , uD 3 )P : u ∈ U }.
The attack in this case consists in recovering a basis of U . Once this is done, it is easy to recover the U code up to permutation by matching the pairs of coordinates which are either always equal or always sum to 0 in U . The basic algorithm for recovering the code U is given in Algorithm 7.

It uses other auxiliary functions -Codewords(Punc I (C pk ), p) which computes all (or a big fraction of) codewords of weight p of the punctured public code Punc I (C pk ). All modern [Dum91, FS09, MMT11, BJMM12, MO15] algorithms for decoding linear codes perform such a task in their inner loop. -Complete(x, I, C pk ) which computes the codeword c in C pk such that its restriction outside I is equal to x. -CheckU(x) which checks whether x belongs to U .

Choosing N Appropriately. Let us first analyse how we have to choose N such that Compu-teU returns Ω(1) elements. This is essentially the analysis which can be found in [OT11, Subsec 5.2]. This analysis leads to Algorithm 7 ComputeU: algorithm that computes a set of independent elements in U .

Parameters: (i) : small integer (typically 40), (ii) p : very small integer (typically 1 p 10). Input: (i) C pk the public code used for verifying signatures. (ii) N a certain number of iterations Output: an independent set of elements in U 1: function ComputeU(C pk ,N ) 2:

for i = 1, . . . , N do 3: B ← ∅ 4:
Choose a set I ⊂ {1, . . . , n} of size n -k -uniformly at random 5:

L ← Codewords(PuncI (C pk ), p) 6:

for all x ∈ L do 7:

x ← Complete(x, I, C pk ) 8:

if CheckU(x) then 9: add x to B if x / ∈< B > 10:

return B Proposition 8. The probability P succ that one iteration of the for loop (Instruction 2) in Com-puteU adds elements to the list B is lower-bounded by

P succ ≥ n/2 w=0 n/2 w n/2-w k+l-2w 2 k+l-2w n k+l f k+ -2w p-2i w i 2 p-i 3 max(0,k+ -w-k U ) ( 32
)
where f is the function defined by f (x) = max x(1 -x/2), 1 -1 x . Algorithm 7 returns a non zero list with probability Ω(1) when N is chosen as

N = Ω 1 Psucc .
Proof. It will be helpful to recall [OT11, Lemma 3] Lemma 6. Choose a random code C rand of length n from a parity-check matrix of size r×n chosen uniformly at random in F r×n

3

. Let X be some subset of F n 3 of size m. We have

P(X ∩ C rand = ∅) ≥ f m 3 r .
We say that two positions i and j are matched (for U ) if and only if there exists λ ∈ {±1} such that c i = λc j for every c ∈ U . From the fact that we only consider admissible generalized (U, U + V )-codes, there are clearly n/2 pairs of matched positions. W will now be defined by the number of matched pairs that are included in {1, . . . , n} \ I where I is the random set of size n -k -l which is drawn in Instruction 4 of Algorithm 7. We compute the probability of success by conditioning on the values taken by W :

P succ = n/2 w=0 P(W = w)P ( ∃x ∈ U : |xĪ | = p | W = w) (33)
where Ī ={1, . . . , n}\I. Notice that we can partition Ī as Ī = J 1 ∪J 2 where J 2 consists in the union of the matched pairs in Ī. Note that |J 2 | = 2w. We may further partition J 2 as J 2 = J 21 ∪ J 22 where the elements of a matched pair are divided into the two sets. In other words, neither J 21 nor J 22 contains a matched pair. We are going to consider the codes

U " = Punc I (U ) U = Punc I∪J22 (U ) The last code is of length n -(n -k -+ w) = k + -w as |J 22 | = w and |I| = n -k -l.
The point of defining the first code is that

P (∃x ∈ U : |xĪ | = p | W = w)
is equal to the probability that U " contains a codeword of weight p. The problem is that we can not apply Lemma 6 to it due to the matched positions it contains (the code is not random). This is precisely the point of defining U . In this case, we can consider that it is a random code whose parity-check matrix is chosen uniformly at random among the set of matrices of size max(0, k + -w -k U ) × (k + -w). We can therefore apply Lemma 6 to it. We have to be careful about the words of weight p in U " though, since they do not have the same probability of occurring in U " due to the possible presence of matched pairs in the support. This is why we introduce for i in {0, . . . , p/2 } the sets X i defined as follows

X i ={x = (x i ) i∈ Ī\J22 ∈ F k+ -w 3 : |x J1 | = p -2i, |x J21 | = i}
A codeword of weight p in U " corresponds to some word in one of the X i 's by puncturing it in J 22 . We obviously have the lower bound

P {∃x ∈ U : |xĪ | = p | W = w} ≥ p/2 max i=0 {P(X i ∩ U = ∅)} (34)
By using Lemma 6 we have

P(X i ∩ U = ∅) ≥ f k+ -2w p-2i w i 2 p-i 3 max(0,k+ -w-k U ) . (35)
On the other hand, we may notice that

P(W = w) = n/

Psucc

. This can be done by a combination of two techniques -Once a non-zero element of U has been identified, it is much easier to find other ones. This uses one of the tricks for breaking the KKS scheme (see [START_REF] Otmani | An efficient attack on all concrete KKS proposals[END_REF]Subs. 4.4]). The point is the following: if we start again the procedure ComputeU, but this time by choosing a set I on which we puncture the code which contains the support of the codeword that we already found, then the number N of iterations that we have to perform until finding a new element is negligible when compared to the original value of N .

-The call to CheckU can be implemented in such a way that the additional complexity coming from all the calls to this function is of the same order as the N calls to Codewords. The strategy to adopt depends on the values of the dimensions k and k U . In certain cases, it is easy to detect such codewords since they have a typical weight that is significantly smaller than the other codewords. In more complicated cases, we might have to combine a technique checking first the weight of x, if it is above some prescribed threshold, we decide that it is not in U , if it is below the threshold, we decide that it is a suspicious candidate and use then the previous trick. We namely check whether the support of the codeword x can be used to find other suspicious candidates much more quickly than performing N calls to CheckU.

To keep the length of this paper within some reasonable limit we avoid here giving the analysis of those steps and we will just use the aforementioned lower bound on the complexity of recovering a permuted version of U .

Recovering the V Code up to a Permutation

We consider here the permuted code

V =(V D 2 , V D 4 )P = {(vD 2 , vD 4 )P where v ∈ V }.
The attack in this case consists in recovering a basis of V . Once this is achieved, the support Supp(V ) of V can easily be obtained. Recall that this is the set of positions for which there exists at least one codeword of V that is non-zero in this position. This allows to easily recover the code V up to some permutation. The algorithm for recovering V is the same as the algorithm for recovering U . We call the associated function ComputeV though since they differ in the choice for N . The analysis is slightly different indeed.

Choosing N Appropriately. As in the previous subsection let us analyse how we have to choose N in order that ComputeV returns Ω(1) elements of V . We have in this case the following result.

Proposition 9. The probability P succ that one iteration of the for loop (Instruction 2) in Com-puteV adds elements to the list B is lower-bounded by

P succ ≥ min(n-k-l,n-n I ) w=0 n/2-n I m=0 n 2 -n I m n I n-k-l-w n n-k-l p/2 max i=0 f n-n I -w-2m p-2i m i 2 p-i 3 max(0,n-n I -w-m-k V ) n/2-n I -m j=0 n/2 -n I -m j 2 j n I w -n + 2n I + 2m + j
where f is the function defined by f (x) = max x(1 -x/2), 1 -1

x . ComputeV returns a non-zero list with probability Ω(1) when N is chosen as

N = Ω 1 Psucc .
Proof. To lower-bound the probability P succ that an iteration is successful, let us first introduce the concept of matched positions (for V ). We say that two positions i and j are matched if and only if there exists λ ∈ {±1} such that c i = λc j for every c ∈ V . There are clearly n 2 -n I pairs of matched positions. Let us define the following set: J is the set of positions that are of the images of the permutation P of the positions 1 ≤ i ≤ n/2 such that D 2 (i, i) = 0 and the images of positions n/2 + j with 0 ≤ j ≤ n/2 such that D 4 (j, j) = 0. Let us now bring in the following random variables

I = I ∩ J and W = |I |
and M be the number of matched pairs which are included in J \ I . J \ I represents the set of positions that are not necessarily equal to 0 in the punctured code Punc I (V ) (see Figure 12). ComputeV outputs at least one element of V if there is an element of weight p in Punc I (V ). Therefore the probability of success P succ is given by

P succ = min(n-k-l,n-n I ) w=0 n/2-n I m=0 P (∃x ∈ V : |x J | = p | W = w, M = m) P(W = w, M = m) (36)
where J = J \ I .

Notice that we can partition J as J = J 1 ∪ J 2 where J 2 consists in the union of the matched pairs in J . Note that |J 2 | = 2m. We may further partition J 2 as J 2 = J 21 ∪ J 22 where the elements of a matched pair are divided in two sets. In other words, neither J 21 nor J 22 contains a matched pair. We are going to consider the following codes

V " = Punc I∪ J (V ) V = Punc I∪ J∪J22 (V ).
V " is of length n -n I -w, whereas the last code is of length n -n I -w -m. The point of defining the first code is that

P (∃x ∈ V : |x J | = p | W = w
) is equal to the probability that V " contains a codeword of weight p. The problem is that we can not apply Lemma 6 to it due to the matched positions it contains. This is precisely the point of defining V . In this case, we can consider that it is a random code whose parity-check matrix is chosen uniformly at random among the set of matrices of size max(0, n

-n I -w -m -k V ) × (n V -w -m).
We can therefore apply Lemma 6 to it. We have to be careful about the words of weight p in V " though, since they do not have the same probability of occurring in V " due to the possible presence of matched pairs in the support. This is why we introduce for i in {0, . . . , p/2 } the sets X i defined as follows

X i ={x = (x i ) i∈J \J22 ∈ F n-n I -w-m 3 : |x J1 | = p -2i, |x J21 | = i}
A codeword of weight p in V " corresponds to some word in one of the X i 's by puncturing it in J 22 . We obviously have the lower bound

P {∃x ∈ V : |xĪ | = p | W = w, M = m} ≥ p/2 max i=0 {P(X i ∩ V = ∅)} (37)
By using Lemma 6 we have

P(X i ∩ V = ∅) ≥ f n-n I -w-2m p-2i m i 2 p-i 3 max(0,n-n I -w-m-k V ) . (38)
On the other hand, we have

P(W = w, M = m) = n 2 -n I m n I n-k-l-w n n-k-l n/2-n I -m j=0 n/2 -n I -m j 2 j n I w -n + 2n I + 2m + j
These considerations lead to the following lower bound on P succ

P succ ≥ min(n-k-l,n-n I ) w=0 n/2-n I m=0 n 2 -n I m n-n-n I n-k-l-w n n-k-l p/2 max i=0 f n-n I -w-2m p-2i m i 2 p-i 3 max(0,n-n I -w-m-k V ) n/2-n I -m j=0 n/2 -n I -m j 2 j n I w -n + 2n I + 2m + j
The claim on the number N of iterations follows directly from this.

Complexity of Recovering a Permuted Version of V . As for recovering the permuted U code, the complexity for recovering the permuted V is of order Ω C1(p,k, ) Psucc .

Distinguishing a Generalized (U, U + V ) Code

It is not clear in the second case that from the single knowledge of V and a permuted version of V we are able to find a permutation of the positions which gives to the whole code the structure of a generalized (U, U + V )-code. However in both cases as single successful call to ComputeV (resp. ComputeU) is really distinguishing the code from a random code of the same length and dimension. In other words, we have a distinguishing attack whose complexity is given by the following proposition Proposition 10. The aforementioned algorithms lead to a distinguishing attack whose complexity is given by min (O (min p,l C U (p, l)) , O (min p,l C U (p, l)))

C U (p, l) = C 1 (p, k, ) n/2 w=0 ( n/2 w )( n/2-w k+l-2w )2 k+l-2w ( n k+l ) p/2 max i=0 f ( k+ -2w p-2i )( w i )2 p-i 3 max(0,k+ -w-k U ) (39) C V (p, l) = C 1 (p, k, ) I ( n 2 -n I m )( n I n-k-l-w ) ( n n-k-l ) p/2 max i=0 f ( n-n I -w-2m p-2i )( m i )2 p-i 3 max(0,n-n I -w-m-k V ) n/2-n I -m j 2 j n I w-n+2n I +2m+j . ( 40
)
where C 1 (p, k, ) is the the complexity of a computing a constant fraction (say half of them) of the codewords of weight p in a code of length k + and dimension k and f is the function f (x) = max x(1 -x/2), 1 -1 x . The sum in the denominator of (40) is over the domain

I = {(w, m, j) | 0 ≤ w ≤ min(n -k -, n -n I ), 0 ≤ m ≤ n/2 -n I , 0 ≤ j ≤ n/2 -n I -m}.

Parameter Selection

In the light of the security proof in §6 and the reject sampling method in §5, we need to derive parameters which lead to negligible success for the two following problems:

1. Solve a syndrome decoding problem with multiple instances (DOOM) for parameters n, k, w and an arbitrarily large number of instances. 2. Distinguish public matrices of the generalized admissible (U, U + V ) code family from random matrices of same size.

To specify the signature scheme, we need to choose the salt size λ 0 . From the security proof, it is sufficient to have λ 0 = log 2 (q sign ) where q sign is the number of signature queries allowed to the adversary. Since q sign ≤ 2 λ (λ the security parameter) we choose a conservative λ 0 = λ. We gave in §7 and §8 state-of-the-art algorithms for the two problems mentioned above. This served as a basis for the parameters proposed in Table 1.

For any set of parameters (n, k, w, k U , k V ) the message security is based on the cost of Dumer's algorithm, as mentioned in §7, in the range of parameters we consider here, this cost cannot be improved as it is done in the binary case. Moreover, considering multiple target (DOOM) does not seem to give an advantage to the attacker. For the range of parameters we have explored, the key security seems to depend solely of the attacks on U , that is (39).

The essential point for parameter selection is the number α introduced at the end of §5. It is a number between 0 and 1 which affects the distribution of the signature weight. We need α < 1 to allow an efficient rejection sampling. Large values of α favour the message security while small values favour key security. For each value of α and k/n we derive from equations ( 23), (24), and (25), the values of w/n, k U /n, and k V /n and thus the security estimates from §7 and §8.

The optimal pair in this respect is (α, k/n) = (0.545, 0.7555) for which, in the current state-ofthe-art, the best attack has a cost 2 cn with c = 0.02464. The choice is made such that key attacks and message attacks have the same cost. For 128 bits of security against a classical adversary we obtain the numbers of Table 1. Recall that we are using the ternary alphabet F 3 . Those parameters scale linearly, except for the key size which grows as the square of the security. We did not investigate specific quantum attacks, but since known attacks are based on decoding problems, it should be more than enough to increase the classical exponent by a factor two. This leads to quantum safe parameters that are the double of those given in Table 1, except for the key size which would be slightly below 4 megabytes. Rejection Sampling Cost. Each of the two steps of our decoding algorithm takes as parameter a weight distribution, respectively D V and D U . For the parameters of Table 1, the first decoding step with D V a normalized Laplace distribution of mean (1 -α)k V and variance 18.81 yields a rejection rate of 11%. For the second decoding step, we also choose a Laplace distribution. The mean and variance of that distribution is optimized according to the first step output weight. In the average case the rejection rate is 19%. That is one rejection every 3 or 4 signatures.

Concluding Remarks and Further Work

We have presented Wave the first code-based "hash-and-sign" signature scheme which strictly follows the GPV strategy [START_REF] Gentry | Trapdoors for hard lattices and new cryptographic constructions[END_REF]. This strategy provides a very high level of security, but because of the multiple constraints it imposes, very few schemes managed to comply to it. For instance, only one such scheme based on hard lattice problems [FHK + ] was proposed to the recent NIST standardization effort. Our scheme is secure under two assumptions from coding theory. Both of those assumptions relate closely to hard decoding problems. Using rejection sampling, we have shown how to efficiently avoid key leakage from any number of signatures. The main purpose of our work was to propose this new scheme and assess its security. Still, it has a few issues and extensions that are of interest.

Decoding Problems. The message security of Wave relates to the hardness of finding a codeword far from a given word. We derived a solver from existing decoding techniques, namely ISD [START_REF] Prange | The use of information sets in decoding cyclic codes[END_REF][START_REF] Dumer | On minimum distance decoding of linear codes[END_REF], but the evolutions of ISD [MMT11, BJMM12] that successfully improved decoding in the close codeword setting, fail for high weights. Similarly, multiple target decoders [START_REF] Sendrier | Decoding one out of many[END_REF] are ineffective here. We believe the problem is exponential by nature, but further studies certainly need to be conducted to understand if, and how much, the exponent can be lowered by new techniques.

Distinguishability. Deciding whether a matrix is a parity check matrix of a generalized (U, U + V ) code is also a new problem. As shown in [START_REF] Debris-Alazard | The problem with the surf scheme[END_REF] it is hard in the worst case since the problem is NP-complete. In the binary case, (U, U + V ) codes have a large hull dimension for some set of parameters which are precisely those used in [START_REF] Debris-Alazard | The problem with the surf scheme[END_REF]. In the ternary case the admissible generalized (U, U + V ) codes do not suffer from this flaw. The freedom of the choice on the diagonal matrices D i is very likely to make the distinguishing problem much harder for generalized (U, U + V ) codes than for plain (U, U + V )-codes. Coming up with non-metric based distinguishers in the generalized case seems a tantalizing problem here.

Rejection Sampling. Rejection sampling in our algorithm is relatively unobtrusive: a rejection every few signatures with a crude tuning of the decoder. We believe that it can be further improved.

Our decoding has two steps. Each step is parametrized by a weight distribution which conditions the output weight distribution. We believe that we can tune those distributions to reduce the probability of rejection to an arbitrarily small value. This task requires a better understanding of the distributions involved. This could offer an interesting trade-off in which the designer/signer would have to precompute and store a set of distributions but in exchange would produce a signing algorithm that emulates a uniform distribution without rejection sampling.

A Proofs for §6

A.1 List Emulation

In the security proof, we need to build lists of indices (salts) in F λ0 3 . Those lists have size q sign , the maximum number of signature queries allowed to the adversary, a number which is possibly very large. For each message m which is either hashed or signed in the game we need to be able to create a list L m of q sign random elements of F λ0 3 , when calling the constructor new list(); pick an element in L m , using the method L m .next(), this element can be picked only once; decide whether or not a given salt r is in L m , when calling L m .contains(r).

The straightforward manner to achieve this is to draw q sign random numbers when the list is constructed, this has to be done once for each different message m used in the game. This may result in a quadratic cost q hash q sign just to build the lists. Once the lists are constructed, and assuming they are stored in a proper data structure (a heap for instance) picking an element or testing membership has a cost at most O(log q sign ), that is at most linear in the security parameter λ. Note that in our game we condition on the event that all elements of L m are different. This implies that now L m is obtained by choosing among the subsets of size q sign of F λ0 3 uniformly at random. We wish to emulate the list operations and never construct them explicitly such that the probabilistic model for L m .next() and L m .contains(r) stays the same as above (but again conditioned on the event that all elements of L m are different). For this purpose, we want to ensure that at any time we call either L m .contains(r) or L m .next() we have

class list method list.contains(r) elt, index return r ∈ {elt[i], 1 ≤ i ≤ qsign} list() index ← 0 method list.next() for i = 1, . . . , qsign index ← index + 1 elt[i] ← randint(2 λ 0 ) return elt[index]
P(L m .contains(r) = true) = P(r ∈ L m |Q) (41)
P(r = L m .next()) = p(r|Q) (42)
for every r ∈ F λ0 3 . Here Q represents the queries to r made so far and whether or not these r's belong to L m . Queries to r can be made through two different calls. The first one is a call of the form Sign(m) when it chooses r during the random assignment r ← {0, 1} λ0 . This results in a call to Hash(m, r) which queries itself whether r belongs to L m or not through the call L m .contains(r). The answer is necessarily positive in this case. The second way to query r is by calling Hash(m, r) directly. In this case, both answers true and false are possible. p(r|Q) represents the probability distribution of L m .next() that we have in the above implementation of the list operations given the previous queries Q.

A convenient way to represent Q is through three lists S, H true and H false . S is the list of r's that have been queried through a call Sign(m). They belong necessarily to L m . H true is the set of r's that have not been queried so far through a call to Sign(m) but have been queried through a direct call Hash(m, r) and for which L m .contains(r) returned true. H false is the list of r's that have been queried by a call of the form Hash(m, r) and L m .contains(r) returned false.

A.2 Proof of Lemma 3

The goal of this subsection is to estimate the probability of a collision in a signature query for a message m when we allow at most q sign queries (the event F in the security proof) and to deduce Lemma 3 of §6.3. We recall that in S code for each signature query, we pick r uniformly at random in {0, 1} λ0 . Then the probability we are looking for is bounded by the probability to pick the same r at least twice after q sign draws. The following lemma will be useful.

Lemma 7. The probability to have at least one collision after drawing uniformly and independently t elements in a set of size n is upper bounded by t 2 /n for sufficiently large n and t 2 < n.

Proof. The probability of no collisions after drawing independently t elements among n is:

p n,t = t-1 i=0 1 - i n ≥ 1 - t-1 i=0 i n = 1 - t(t -1) 2n
from which we easily get 1 -p n,t ≤ t 2 /n, concluding the proof.

In our case, the probability of the event F is bounded by the previous probability for t = q sign and n = 2 λ0 , so, with λ 0 = λ + 2 log 2 q sign , we can conclude that

P (F ) ≤ q 2 sign 2 λ0 = 1 2 λ0-2 log 2 (qsign) = 1 2 λ
which concludes the proof of Lemma 3.

B Proof of Proposition 3

Our goal in this subsection is to prove Proposition 3 of §5.1.

Probabilistic notation. Recall that we denote by U w the uniform distribution over S w .

Vector notation. If e ∈ F n 3 and i ∈ 1, n , we will denote by e(i) the i-th component of e. Furthermore, if we split e as (e 1 , e 2 ) where e 1 (resp. e 2 ) is the vector formed by its first (resp. last) n/2 coordinates. We define e (i) for all i ∈ 1, n/2 as:

e (i) = e 1 (i) e 2 (i)
We start by computing here a distribution that will be useful in the following.

Proposition 11. Let e = (e 1 , e 2 ) be random a random variable whose distribution is U w where the e i 's are vectors of F n/2 3 . We have for all j ∈ 0, n/2 : Lemma 8. Let e = (e 1 , e 2 ) be a word of S w . The weight |e 1 + e 2 | is given by the number of i ∈ 1, n/2 such that e (i) is one of the following element:

-1 0 ; 0 -1 ; 1 0 ; 0 1 ; -1 -1 ; 1 1
Proof (Proposition 11). Let us enumerate the number of errors e = (e 1 , e 2 ) ∈ S w which verify |e 1 + e 2 | = j. For this let introduce the following intermediary weights:

|e| 1 = i ∈ 1, n/2 : e (i) ∈ -1 0 ; 0 -1 ; 1 0 ; 0 1 |e| 2 = i ∈ 1, n/2 : e (i) ∈ -1 -1 ; 1 1 |e| 3 = i ∈ 1, n/2 : e (i) ∈ 1 -1 ; -1 1 It is easily verified that, |e| = |e| 1 + 2|e| 2 + 2|e| 3 and |e 1 + e 2 | = |e| 1 + |e| 2
In this way,

P e (|e 1 + e 2 | = j) = j p=0 P e |e| 2 = j -p |e| 1 = p P e |e| 1 = p = j p=0 P e |e| 2 = j -p, |e| 1 = p = 1 2 w n w j p=0 n/2 p 4 p n/2 -p j -p 2 j-p n/2 -p -(j -p) w-p-2(j-p) 2 2 w-p-2(j-p) 2 = 1 2 w n w j p=0 n/2 p n/2 -p j -p 2 2p+j-p n/2 -j w-2j+p 2 2 w-2j+p 2 = 1 2 w n w j p=0 n/2 p n/2 -p j -p n/2 -j w+p 2 -j 2 w+3p 2
It remains now the following computation to conclude:

n/2 p n/2 -p j -p n/2 -j w+p 2 -j = (n/2)! (n/2 -p)!p! (n/2 -p)! (n/2 -j)!(j -p)! (n/2 -j)! ((n -w -p)/2)!((w + p)/2 -j)! = (n/2)! p! 1 (j -p)! 1 ((n -w -p)/2)!((w + p)/2 -j)! = (n/2)! ((n -w -p)/2)!((w + p)/2)! ((w + p)/2)! ((w + p)/2 -j)!j! j! (j -p)!p! = n/2 w+p 2 w+p 2 j j p
which concludes the proof.

Let us recall now Proposition 3 that we want to prove. We recall first that we denote by H pk the random matrix chosen as the public parity-check matrix of our scheme. Let us recall that it is obtained as

H pk = SH sk P with H sk = H U D 4 M -H U D 2 M H V D 3 M -H V D 1 M
where D 1 , • • • , D 4 are four diagonal matrices which verify (12) and M =(D 1 D 4 -D 3 D 2 ) -1 , S is chosen uniformly at random among the invertible ternary matrices of size (n -k) × (n -k), H U is chosen uniformly at random among the ternary matrices of size (n/2 -k U ) × n/2, H V is chosen uniformly at random among the ternary matrices of size (n/2 -k V ) × n/2 and P is chosen uniformly at random among the permutation matrices of size n × n.

Proposition 3. Let D H w be the distribution of the syndromes eH when e is drawn uniformly at random among the ternary vectors of weight w and U be the uniform distribution over the syndrome space F n-k 3 . We have Proposition 3 is based on two lemmas. The first one is the following:

Lemma 9. Let y be a non-zero vector of F n 3 and s an arbitrary element in F r 3 . We choose a matrix H of size r × n uniformly at random among the set of r × n binary matrices. In this case

P yH = s = 1 3 r
Proof. The coefficient of H at row i and column j is denoted by h ij , whereas the coefficients of y and s are denoted by y i and s i respectively. The probability we are looking for is the probability to have j h ij y j = s i (50) for all i in {1, . . . , r}. Since y is non zero, it has at least one non-zero coordinate. Without loss of generality, we may assume that y 1 = 1. We may rewrite (50) as h i1 = j>1 h ij y j . This event happens with probability 1 3 for a given i and with probability 1 3 r on all r events simultaneously due to the independence of the h ij 's.

Let us now consider the following lemma which is a variation of the left over hash lemma: Lemma 1. Consider a finite family H = (h i ) i∈I of functions from a finite set E to a finite set F . Denote by ε the bias of the collision probability, i.e. the quantity such that P h,e,e (h(e) = h(e )) =

1 |F | (1 + ε)
where h is drawn uniformly at random in H, e and e are drawn uniformly at random in E. Let U be the uniform distribution over F and D(h) be the distribution of the outputs h(e) when e is chosen uniformly at random in E. We have

E h {ρ(D(h), U)} ≤ 1 2 √ ε.
Proof. Let q h,f be the probability distribution of the discrete random variable (h 0 , h 0 (e)) where h 0 is drawn uniformly at random in H and e drawn uniformly at random in E (i.e. q h,f = P h0,e (h 0 =

1 |H| • |F | = 1 2 (h,f )∈H×F q h,f - 1 |H| • |F | . ( 51
)
Using the Cauchy-Schwarz inequality, we obtain

(h,f )∈H×F q h,f - 1 |H| • |F | ≤ (h,f )∈H×F q h,f - 1 |H| • |F | 2 • |H| • |F |. ( 52
)
Let us observe now that

(h,f )∈H×F q h,f - 1 |H| • |F | 2 = h,f q 2 h,f -2 q h,f |H| • |F | + 1 |H| 2 • |F | 2 = h,f q 2 h,f -2 h,f q h,f |H| • |F | + 1 |H| • |F | = h,f q 2 h,f - 1 |H| • |F | . (53)
Consider for i ∈ {0, 1} independent random variables h i and e i that are drawn uniformly at random in H and E respectively. We continue this computation by noticing now that h,f q 2 h,f = h,f P h0,e0 (h 0 = h, h 0 (e 0 ) = f )P h1,e1 (h 1 = h, h 1 (e 1 ) = f ) = P h0,h1,e0,e1 (h 0 = h 1 , h 0 (e 0 ) = h 1 (e 1 )) = P h0,e0,e1 (h 0 (e 0 ) = h 0 (e 1 ))

|H| = 1 + ε |H| • |F | . ( 54
)
By substituting for h,f q 2 h,f the expression obtained in (54) into (53) and then back into (52) we finally obtain

(h,f )∈H×F q h,f - 1 |H| • |F | ≤ 1 + ε |H| • |F | - 1 |H| • |F | |H| • |F | = ε |H| • |F | |H| • |F | = √ ε.
This finishes the proof of our lemma.

In order to use this lemma to bound the statistical distance we are interested in, we perform now the following computation Lemma 10. Assume that x and y are random vectors of S w that are drawn uniformly at random in this set. We have , H U is chosen uniformly at random among F (n/2-k U )×n/2 3 , H V is chosen uniformly at random among F (n/2-k V )×n/2 3 and P is chosen uniformly at random among the permutation matrices of size n × n. As S is non-singular and P is a permutation, the probability of the event xH pk = yH pk is the same as the probability of the event

P
H U D 4 M -H U D 2 M H V D 3 M -H V D 1 M x = H U D 4 M -H U D 2 M H V D 3 M -H V D 1 M y .
Let x be a vector of F n 3 , we will denote in the following by x 1 (resp. x 2 ) the vector formed by its first (resp. last) n/2 coordinates. In other words, the probability we are looking for is

P ((x 1 -y 1 )D 4 M -(x 2 -y 2 )D 2 M) H U = 0, ((x 1 -y 1 )D 3 M -(x 2 -y 2 )D 1 M) H V = 0 .
where the probability is taken over H U , H V , x, y. To compute the previous probability we use Lemma 9 which says that:

P H eH = 0 = 1 3 n-k if e = 0 and 1 otherwise ( 55
)
when H is chosen uniformly at random in F

(n-k)×n 3

. This lemma motivates to distinguish between four disjoint events P x,y (E 1 ) 3 n/2-k V + P x,y (E 2 ) 3 n/2-k U + P x,y (E 3 ) 3 n-k + P x,y (E 4 ) = 1 3 n-k P (E 1 ) 3 n/2-k V -n+k + P (E 2 ) 3 n/2-k U -n+k + P (E 3 ) + 3 n-k P (E 4 ) ≤ 1 3 n-k 1 + 3 n/2-k U P (E 1 ) + 3 n/2-k V P (E 2 ) + 3 n-k P(E 4 ) ,

where we used for the last inequality the trivial upper-bound P (E 3 ) ≤ 1. Let us now upper-bound (or compute) the probabilities of the events E 1 , E 2 and E 4 . For (57)

Let us now estimate to probability of E 2 for which derive the following upper-bound:

P (E 2 ) ≤ P ((x 1 -y 1 )D 3 M = (x 2 -y 2 )D 1 M)

But now from the condition (12):

∀i ∈ 1, n/2 , D 3 (i, i)D 1 (i, i) = 0 of the definition of admissible generalized (U, U + V )-codes and the fact that M is an invertible diagonal matrix we have:

(x 1 -y 1 )D 3 M = (x 2 -y 2 )D 1 M ⇐⇒ ∀i ∈ 1, n/2 , (x 1 -y 1 )(i) = ±(x 2 -y 2 )(i)

Let us notice that distribution of a vector x = (x 1 , x 2 ) uniformly picked at random in S w is the same as by multiplying some of its components to -1 . In this way we have

P (E 2 ) ≤ P (x 1 -y 1 = x 2 -y 2 )
To upper-bound P(x 1 -x 2 = y 1 -y 2 ), let us derive the distribution of x 1 -x 2 . We first observe that In other words from the fact that M is invertible, the event E 1 = {(x 1 -y 1 )D 4 M = (x 2y 2 )D 2 M, (x 1 -y 1 )D 3 M = (x 2 -y 2 )D 1 M} is the same (up to a permutation of indices of x and y) as: ∀i ∈ 1, n I , (x 1 -y 1 )(i) = 0 or (x 2 -y 2 )(i) = 0 ; ∀i ∈ n I +1, n/2 , (x 1 -y 1 )(i) = ±(x 2 -y 2 )(i) Now by using the fact that distribution of a vector x = (x 1 , x 2 ) which is uniformly picked at random in S w is the same as by multiplying some of its components by -1 or exchanging some of its component we have P (E 1 ) ≤ P (∀i ∈ 1, n I , (x 1 -y 1 )(i) = 0, ∀i ∈ n I + 1, n/2 , (x 1 -y 1 )(i) = (x 2 -y 2 )(i))

Let us now derive the following upper bound P(∀i ∈ 1, n I , (x 1 -y 1 )(i) = 0, ∀i ∈ n I + 1, n/2 , (x 1 -y 1 )(i) = (x 2 -y 2 )(i))

Fig. 1 .

 1 Fig. 1. Asymptotic Hardness of Decoding

  H, s, I, x) 5: return e function InfoSet(H) -information set Require: H ∈ F (n-k)×n q

Fig. 2 .

 2 Fig. 2. Areas of relative signature distances.

Fig. 3 .

 3 Fig. 3. Hardness of (U,U+V) Decoding

Fig. 4 .

 4 Fig. 4. The form of the errors eV and e

  ) 2: repeat 3: eU ← DU (HU , sU , eV ) 4: e ← (eU , eU + eV ) 5: until |e| = w 6: return e function DV (HV , sV ) IV ← InfoSet(HV ) InfoSet returns an information set return PrangeStep(HV , sV , IV , 0) function DU (HU , sU ,eV ) IU ← InfoSet(HU ) InfoSet returns an information set xU ← {x ∈ F n/2 3 | Supp(x) = IU and xI = (eV )I , I = IU ∩ Supp(eV )} return PrangeStep(HU , sU , IU , xU )

Fig. 5 .

 5 Fig. 5. Areas of relative signature distances with our trapdoor when q = 3

  Fig. 6. Hardness of (U,U+V) Decoding with no leakage of signature

Fig. 8 .

 8 Fig. 8. Areas of relative signature distances with rejection sampling when q = 3

Fig. 9 .

 9 Fig.9. Asymptotic exponent of Prange's algorithm for code rate R ∈ {1/4, 1/2} and q ∈ {2, 3}

Fig. 10 .

 10 Fig. 10. Asymptotic exponent of Dumer (dotted) vs. Prange for q = 3

Fig. 11 .

 11 Fig. 11. αu(w/n) and αv(w/n) against x = w n .

.

  These considerations lead to the following lower bound on P succP succ ≥ -i 3 max(0,k+ -w-k U )Complexity of Recovering a Permuted Version of U . The complexity of a call to Compu-teU can be estimated as follows. We denote the complexity of computing the list of codewords of weight p in a code of length k + and dimension k by C 1 (p, k, ). It depends on the particular algorithm used here. For more details see [Dum91, FS09, MMT11, BJMM12, MO15]. This is the complexity of the call Codewords(Punc I (C pk ), p) in Step 5 in Algorithm 7. The complexity of ComputeU and hence the complexity of recovering a permuted version of U is clearly lower bounded by Ω C1(p,k, ) Psucc . It turns out that the whole complexity of recovering a permuted version of U is actually of this order, namely Θ C1(p,k, )

Remark 7 .

 7 From Definition 3 it follows that |J| = n -n I (see Remark 3 in §5.1).

Fig. 12 .

 12 Fig. 12. A figure representing J, I and I and the form of a codeword in V .positions in J

Fig. 13 .

 13 Fig. 13. Standard implementation of the list operations.

P

  e (|e 1 -e 2 | = j) = P e (|e 1 + e 2 | = j)

  -n I -j p=0 n/2 -nI h n/2 -nI -h j -h n/2 -nI -j p 2nI w -j -h -2p 2 w-j-h-2p

h, h 0 P

 0 (e) = f )). By definition of the statistical distance we have E h {ρ(D(h), U)} = h0,e (h 0 = h, h 0 (e) = f ) -

  H pk ,x,y xH pk = yH pk ≤ 1 3 n-k (1 + ε) with ε given in Proposition 3.Proof. Recall that H pk is obtained asH pk = SH sk P with H sk = H U D 4 M -H U D 2 M H V D 3 M -H V D 1 M where D 1 , • • • ,D 4 are four diagonal matrices which verify (12) in Definition 2 in §4.2 and M =(D 1 D 4 -D 3 D 2 ) -1 , S is chosen uniformly at random among F (n-k)×(n-k) 3

E 1 4 i=1P

 14 ={(x 1 -y 1 )D 4 M = (x 2 -y 2 )D 2 M, (x 1 -y 1 )D 3 M = (x 2 -y 2 )D 1 M} Event 2: E 2 ={(x 1 -y 1 )D 4 M = (x 2 -y 2 )D 2 M, (x 1 -y 1 )D 3 M = (x 2 -y 2 )D 1 M} Event 3: E 3 ={(x 1 -y 1 )D 4 M = (x 2 -y 2 )D 2 M, (x 1 -y 1 )D 3 M = (x 2 -y 2 )D 1 M} Event 4: E 4 ={(x 1 -y 1 )D 4 M = (x 2 -y 2 )D 2 M, (x 1 -y 1 )D 3 M = (x 2 -y 2 )D 1 M}Under these events we get thanks to (55) and k = k U + k V :P H sk ,x,y xH sk = yH sk = H sk xH sk = yH sk |E i P x,y (E i ) =

  E 4 , recall that from the definition of admissible generalized (U, U + V )-codes and especially the fact that D = D 1 D 2 D 3 D 4 and M are invertible we clearly have E 4 = {x 1 = y 1 , x 2 = y 2 } which easily gives P x,y (E 4 ) = P(x = y)

P(x 1

 1 x 2 = e) = P x 1 -x 2 = e |x 1 -x 2 | = w e P(|x 1 -x 2 | = w e ) deduce thatP (x 1 -y 1 = x 1 -y 2 ) = x (x 1 -x 2 = e)upper bound E 1 let us first recall the following definition Definition 3. (number of V blocks of type I). In a generalized (U, U + V ) code of length n associated to the 4-tuple of diagonal matrices of size n/2 (D 1 , D 2 , D 3 , D 4 ), the number of V blocks of type I, which we denote by n I , is defined by: n I = |{1 ≤ i ≤ n/2 : D 2 (i, i)D 4 (i, i) = 0}| .

P 2 PPP

 2 (x 1 -y 1 ) 1,n I = 0, (x 1 -x 2 ) n I +1,n/2 = (y 1 -y 2 ) n I +1,n/2 |(x 1 ) 1,n I | = l, |(y 1 ) 1,n I | = l P |(x 1 ) 1,n I | = l, |(y 1 ) 1,n I | = l = (x 1 -y 1 ) 1,n I = 0, (x 1 -x 2 ) n I +1,n/2 = (y 1 -y 2 ) n I +1,n/2 |(x 1 ) 1,n I | = l, |(y 1 ) 1,n I | = l = (x 1 ) 1,n I = e 1 , (x 1 -x 2 ) n I +1,n/2 = e 2 |(x 1 ) 1,n I | = l (x 1 ) 1,n I = e 1 , (x 1 -x 2 ) n I +1,n/2 = e 2 |(x 1 ) 1,n I | = l, |(x 1 -x 2 ) n I +1,n/2 | = j P |(x 1 -x 2 ) n I +1,n/2 | = j I l 2 j n/2-n I j P |(x 1 -x 2 ) n I +1,n/2 | = j x 1 -x 2 ) n I +1,n/2 | = j -n I -j p=0 n/2 -n I h 2 h n/2 -n I -h j -h 2 2(j-h) n/2 -n I -j p 2 p 2n I w -j -h -2p 2 w-j-p-2h   2

  The functions InfoSet(•) and PrangeStep(•) are defined in Algorithm 1. Ensure: returns I a set of k + coordinate indices containing an information set of H ⊥ function Decomp(H, I) -shorten and supplement

				k
				q
	Ensure: eH = s and |e| = w
	1: loop
	2:	I ← ExtInfoSet(H, )
	3:	S, H , H ← Decomp(H, I)
	4:	(s , s ) ← sS
	5:	E ← BirthdaySD(H , s , k + -p, I, L)
	6:	for e ∈ E do
	7:	e ← PrangeStep(H , s , I, e )
	8:	if |e| = w then
	9:	return e
	function ExtInfoSet(H, ) -extended information set
	Require: H ∈ F	(n-k)×n q	, ≥ 0 integer

Table 1 .

 1 Proposed Parameters for the Wave Signature Scheme and 128 bits of (classical) security

	(n, k, w)	(5172, 3908, 4980)
	(kU , kV )	(2299, 1609)
	Signature length (bits)	8326
	Public key size (MBytes)	0.98

Hq(x) = -x log q (x/(q -1)) -(1 -x) log q (1 -x) is the q-ary entropy.

This work was supported by the ANR CBCRYPT project, grant ANR-17-CE39-0007 of the French Agence Nationale de la Recherche.

We clearly have

To compute the probability distribution p(r|Q) it is helpful to notice that P(L m .next() outputs an element of

This can be used to derive p(r|Q) as follows

(47) is obvious. (48) follows from that all elements of H true have the same probability to be chosen as return value for L m .next() and ( 46). (49) follows by a similar reasoning by arguing (i) that all the elements of F λ0 3 \ (S ∪ H true ∪ H false ) have the same probability to be chosen as return value for L m .next(), (ii) the probability that L m .next() outputs an element of F λ0 3 \ (S ∪ H true ∪ H false ) is the probability that it does not output an element of H true which is 1 -

. Figure 14 explains how we perform the emulation of the list operations so that they perform similarly to genuine list operations as specified above. The idea is to create and to operate explicitly on the lists S, H true and H false described earlier. We have chosen there

we also assume that when we call randomPop() on a list it outputs an element of the list uniformly at random and removes this element from it. The method push adds an element in a list. The procedure rand() picks a real number between 0 and 1 uniformly at random. The correctness of this emulation follows directly from the calculations given above. For instance the correctness of the call L m .next() follows from the fact that with probability |Htrue| qsign-|S| = γ it outputs an element of H true chosen uniformly at random (see (46)). In such a case the corresponding element has to be moved from H true to S (since it has been queried now through a call to Sign(m)). The correctness of L m .contains(r) is a direct consequence of the formulas for P(r ∈ L m |Q) given in (43), (44) and (45). All push, pop, membership testing above can be implemented in time proportional to λ 0 . which gives

Therefore, with Equations ( 56),( 57),( 60) and ( 59) we finally obtain

which concludes the proof.

Lemmas 10 and 1 imply directly Proposition 3.

and H be the set of functions associated to the 4-tuples (H U , H V , S, P) used to generate a public parity-check matrix H pk . These functions h are given by h(e) = eH pk . Lemma 10 gives an upper-bound for the ε term in Lemma 1 and this finishes the proof of Proposition 3.

We are now able to prove Lemma 4 (we use here notations of the security proof in §6.3).

Lemma 4.

P(S 1 ) ≤ P(S 2 ) + q hash 2 √ ε where ε is given in Proposition 3.

Proof (Lemma 4). To simplify notation we let q = q hash . Then we notice that

where -U is the uniform distribution over F n-k 2 ; -D pub w,q is the distribution of the (q + 1)-tuples (H pk , e 1 H pk , • • • , e q H pk ) where the e i 's are independent and uniformly distributed in S w ; -D pub ⊗ U ⊗q is the distribution of the (q + 1)-tuples (H pk , s 1 , • • • , s q ) where the s i 's are independent and uniformly distributed in F n-k

We now observe that

C Proof of Proposition 7

Let us recall Proposition 7

Proposition 7. Assume that we choose an admissible generalized (U, U + V ) code over F 3 with a number n I of linear combinations of type I by picking the parity-check matrices of U and V uniformly at random among the ternary matrices of size

respectively. Let a (u,v) (w), a (u,0) (w) and a (0,v) (w) be the expected number of codewords of weight w that are respectively in the admissible generalized (U, U +V ) code, of the form (uD 1 , uD 3 ) where u belongs to U and of the form (vD 2 , vD 4 ) where v belongs to V . These numbers are given for even w in {0, . . . , n} by

On the other hand, when we choose a linear code of length n over F 3 with a random parity-check matrix of size (n -k U -k V ) × n chosen uniformly at random, then the expected number a(w) of codewords of weight w > 0 is given by

Lemma 9 in Appendix §B will be useful four the proof. The last part of Proposition 7 is a direct application of this lemma. We namely have Proposition 12. Let a(w) be the expected number of codewords of weight w in a ternary linear code C of length n whose parity-check matrix is chosen H uniformly at random among all binary matrices of size r × n. We have

Proof. Let Z = x∈F n 3 :|x|=w Z x where Z x is the indicator function of the event "x is in C". We have

This proves the part of Proposition 7 dealing with the expected weight distribution of a random linear code. We are ready now to prove Proposition 7 concerning the expected weight distribution of a random (U, U + V ) code.

) is an admissible generalized code which enforces that ∀i ∈ 1, n/2 , D 1 (i, i)D 3 (i, i) = 0 and therefore it follows directly from Proposition 12 since a (u,0) (w) = 0 for odd and a (u,0) (w) is equal to the expected number of codewords of weight w/2 in a random linear code of length n/2 with a parity-check matrix of size (n/2 -k U ) × n/2 when w is even. On the other hand, the weight distribution of (D 2 v, D 4 v) for v ∈ V is little more sophisticate. Let us recall the following definition:

Definition 3. (number of V blocks of type I). In a generalized (U, U + V ) code of length n associated to the 4-tuple of diagonal matrices of size n/2 (D 1 , D 2 , D 3 , D 4 ), the number of V blocks of type I, which we denote by n I , is defined by:

where from the definition of generalized (U, U + V ) when either D 2 (i, i) = 0 or D 4 (i, i) = 0, the other one is necessarily different from 0. In this way, a (0,v) (w) is equal to the expected number of weight j + w-j 2 for all j in 1, n I in a random linear code of length n/2 where j positions correspond to the n I positions which gives the number of block of type I and w-j 2 for the others as there are involved in components which count twice in the weight. Furthermore this code has a parity-check matrix of size (n/2 -k V ) × n/2. This easily gives from Proposition 12:

The admissible generalized (U, U + V )code is chosen randomly by picking up a parity-check matrix H U of U uniformly at random among the set of (n/2 -k U ) × n/2 ternary matrices and a parity-check matrix H V of V uniformly at random among the set of (n/2 -k V ) × n/2 ternary matrices. Let Z = x∈F n 3 :|x|=w Z x where Z x is the indicator function of the event "x is in (U

We have

Let us recall now that a parity-check matrix of the code (U

and only if at the same time:

There are three disjoint cases (see