Ayoub Otmani
email: ayoub.otmani@inria.fr

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

An Efficient Attack on All Concrete KKS Proposals

Keywords: Code-based cryptography, digital signature, random error-correcting codes, cryptanalysis

Kabastianskii, Krouk and Smeets proposed in 1997 a digital signature scheme based on a couple of random error-correcting codes. A variation of this scheme was proposed recently and was proved to be EUF-1CMA secure in the random oracle model. In this paper we investigate the security of these schemes and suggest a simple attack based on (essentially) Stern's algorithm for finding low weight codewords. It efficiently recovers the private key of all schemes of this type existing in the literature. This is basically due to the fact that we can define a code from the available public data with unusual properties: it has many codewords whose support is concentrated in a rather small subset. In such a case, Stern's algorithm performs much better and we provide a theoretical analysis substantiating this claim. Our analysis actually shows that the insecurity of the proposed parameters is related to the fact that the rates of the couple of random codes used in the scheme were chosen to be too close. This does not compromise the security of the whole KKS scheme. It just points out that the region of weak parameters is really much larger than previously thought.

Introduction

Digital signature schemes are probably among the most useful cryptographic algorithms. If quantum computers were to become reality, it would be useful to devise such schemes which would resist to it. A possible approach to meet this goal could be to build such schemes whose security relies on the difficulty of decoding linear codes. Two code based schemes of this kind have been proposed, namely the Courtois-Finiasz-Sendrier signature scheme [START_REF] Courtois | How to achieve a McEliece-based digital signature scheme[END_REF] and the Kabatianskii, Krouk and Smeets (KKS) scheme [START_REF] Kabatianskii | A digital signature scheme based on random errorcorrecting codes[END_REF][START_REF] Kabatiansky | Error Correcting Coding and Security for Data Networks: Analysis of the Superchannel Concept[END_REF].

The Courtois-Finiasz-Sendrier (CFS) scheme presents the advantage of having an extremely short signature and its security has been proven to rely on the well-known syndrome decoding problem and the distinguishability of binary Goppa codes from a random code. However, it has been proved in [FGO + 10] that the latter problem can be solved in the range of parameters used in the CFS signature algorithm. This does not prove that their proposal is insecure. However, it invalidates the hypotheses of their security proof. The main difficulty in suggesting a CFS type scheme is to come up with a family of very high rate codes with an efficient decoding algorithm and whose structure can be hidden in the same way as in the McEliece scheme. This narrows down quite a bit the families of codes which can be used in this setting and up to now only Goppa codes are known to meet this goal. It should be emphasized that it is precisely their rich algebraic structure which makes it possible to distinguish them from random codes.

On the other hand, the KKS proposal does not rely on Goppa codes and can be instantiated with random codes. Moreover, unlike in the CFS signature scheme, it does not compute a signature by using a decoding algorithm for the code and thus completely avoids the necessity of having to use restricted families of codes with a "hidden" trapdoor. Moreover, a variation of it has been proposed in [START_REF] Barreto | One-time signature scheme from syndrome decoding over generic error-correcting codes[END_REF] and has been proved to be EUF-1CMA secure in the random oracle model. The security of the KKS scheme has been investigated in [START_REF] Cayrel | On Kabatianskii-Krouk-Smeets Signatures[END_REF]. It was shown that a passive attacker who may intercept just a few signatures can recover the private key. All the schemes proposed in [START_REF] Kabatianskii | A digital signature scheme based on random errorcorrecting codes[END_REF] can be broken in this way with the help of at most 20 signatures. Basically it uses the fact that a valid message-signature pair reveals on average half of the secret support J (see Section 3 where this set is defined precisely). Therefore with O(log |J|) message-signature pairs it is expected to recover the whole set J. The security of the scheme is not compromised by this attack however if only one signature is computed, and this especially in the variant proposed in [START_REF] Barreto | One-time signature scheme from syndrome decoding over generic error-correcting codes[END_REF] where some random noise is added on top of the signature.

The purpose of this article is to present a completely new security analysis of the KKS scheme and its variant proposed in [START_REF] Barreto | One-time signature scheme from syndrome decoding over generic error-correcting codes[END_REF]. Our approach for breaking the scheme is to define a certain error correcting code from the couple of public matrices used in the scheme and to notice that certain rather low weight codewords give actually valid signatures. It is therefore natural to use standard algorithms for finding low-weight codewords in this setting, such as Stern's algorithm [START_REF] Stern | A method for finding codewords of small weight[END_REF] or its Dumer variant [START_REF] Dumer | Suboptimal decoding of linear codes : partition techniques[END_REF][START_REF] Finiasz | Security bounds for the design of code-based cryptosystems[END_REF] (see also [START_REF] Bernstein | Smaller decoding exponents: ball-collision decoding[END_REF]). It turns out that such algorithms are unusually successful in this setting due to the conjunction of three factors: (i) there are many lowweight codewords, (ii) they are localized on a rather small support, (iii) some part of this support is known to the attacker. It appears that all parameters suggested in [KKS97, [START_REF] Kabatiansky | Error Correcting Coding and Security for Data Networks: Analysis of the Superchannel Concept[END_REF][START_REF] Barreto | One-time signature scheme from syndrome decoding over generic error-correcting codes[END_REF] are easily broken by this approach and this without even knowing a single signature pair. Moreover, this approach can exploit the knowledge of a message-signature pair which speeds up the attack.

We provide an analysis of this attack which explains what makes it feasible for the parameters proposed in [KKS97, [START_REF] Kabatiansky | Error Correcting Coding and Security for Data Networks: Analysis of the Superchannel Concept[END_REF][START_REF] Barreto | One-time signature scheme from syndrome decoding over generic error-correcting codes[END_REF]. The KKS scheme relies on a couple of matrices which can be viewed as parity-check matrices of two linear codes. We show that when the first code has a rate which is smaller than the rate of the second one (or has approximately the same rate), then our attack is quite successful. This was exactly the case for all the parameters suggested in the past. In other words, our attack does not compromise the security of the whole KKS scheme. It just points out that the region of weak parameters is really much larger than previously thought.

Terminology and Notation

In the whole paper q denotes some prime power and we denote by F q the finite field with q elements. Let n be a non-negative integer. The set of integers i such that 1 i n is denoted by [1

• • • n].
The cardinality of a set A is denoted by |A|. The concatenation of the vectors x = (x 1 , . . . , x n ) and y = (y 1 , . . . , y m ) is denoted by (x||y) def = (x 1 , . . . , x n , y 1 , . . . , y m ). The support supp(x) of x ∈ F n q is the set of i's such that x i = 0. The (Hamming) weight |x| is the cardinality of supp(x). For a vector x = (x i ) and a subset I of indices of x, we denote by x I its restriction to the indices of I, that is:

x

I def = (x i ) i∈I .
We will also use this notation for matrices, in this case it stands for the submatrix formed by the columns in the index set, i.e. for any k × n matrix H

H J def = (h ij ) 1 i k j∈J .
A linear code C of type [n, k, d] over F q is a linear subspace of F n q of dimension k and minimum distance d where by definition d def = min{|x| : x ∈ C and x = 0}. The elements of C are codewords. A linear code can be defined either by a parity check matrix or a generator matrix. A parity check matrix H for C is an (nk) × n matrix such that C is the right kernel of H:

C = {c ∈ F n q : Hc T = 0}
where x T denotes the transpose of x. A generator matrix G is a k × n matrix formed by a basis of C . We say that G is in systematic form if there exists a set J such that G J = I k . The syndrome s by H of x ∈ F n q is defined as s T def = Hx T . A decoding algorithm for H is an algorithm such that, given s in F r q , finds a vector e of minimum weight whose syndrome is s.

3 The Kabatianskii-Krouk-Smeets Signature Scheme and its Variant

This section is devoted to the description of two code-based signature schemes proposed in [START_REF] Kabatianskii | A digital signature scheme based on random errorcorrecting codes[END_REF] and more recently in [START_REF] Barreto | One-time signature scheme from syndrome decoding over generic error-correcting codes[END_REF], where the latter can be viewed as a "noisy" version of the former [START_REF] Kabatianskii | A digital signature scheme based on random errorcorrecting codes[END_REF]. Our presentation presents the main ideas without giving all the details which can be found in the original papers. We first focus on the scheme of [START_REF] Kabatianskii | A digital signature scheme based on random errorcorrecting codes[END_REF] whose construction relies on the following ingredients:

1. a full rank binary matrix H of size (N -K) × N with entries in a finite field F q . 2. a subset J of {1, . . . , N } of cardinality n, 3. a linear code C hidden over F q of length n N and dimension k defined by a generator matrix G of size k × n. Let t 1 and t 2 be two integers such that with very high probability, we have that t 1 |u| t 2 for any non-zero codeword u ∈ C hidden .

The matrix H is chosen such that the best decoding algorithms cannot solve the following search problem.

Problem 1. Given the knowledge of s ∈ F N -K q which is the syndrome by H of some e ∈ F N q whose weight lies in [t 1 • • • t 2 ], find explicitly e, or eventually x in F N q different from e sharing the same properties as e.

Finally let F be the (N -K) × k matrix defined by F def = H J G T . The Kabatianskii-Krouk-Smeets (KKS) signature scheme is then described in Figure 1. -Setup.

1. The signer S chooses N , K n, k, t1 and t2 according to the required security level. 2. S draws a random (N -K) × N matrix H. 3. S randomly picks a subset J of {1, . . . , N } of cardinality n. 4. S randomly picks a random k × n generator matrix G that defines a code C hidden such that with high probability t1 |u| t2 for any non-zero codeword u ∈ C hidden .

F def

= HJ G T where HJ is the restriction of H to the columns in J. -Keys.

• Private key. J and G • Public key. F and H -Signature. The signature σ of a message x ∈ F k q is defined as the unique vector σ of F N q such that σi = 0 for any i ∈ J and σJ = xG.

-Verification. Given (x, σ) ∈ F k q × F N q , the verifier checks that t1 |σ| t2 and Hσ T = F x T .

The scheme was modified in [START_REF] Barreto | One-time signature scheme from syndrome decoding over generic error-correcting codes[END_REF] to propose a one-time signature scheme by introducing two new ingredients, namely a hash function f and adding an error vector e to the signature. It was proved that such a scheme is EUF-1CMA secure in the random oracle model. The description is given in Figure 2.

Description of the Attack

The purpose of this section is to explain the idea underlying our attack which aims at recovering the private key. The attack is divided in two main steps. First, we produce a valid signature for some message using only the public key. To do so, we define a certain code from matrices H and F . It turns out that low weight codewords of this code give valid message-signature pairs. Then we just apply Dumer's algorithm [START_REF] Dumer | On minimum distance decoding of linear codes[END_REF] in order to find these low weight codewords. This attack can -Setup.

1. The signer S chooses N , K n, k, t1 and t2 according to the required security level.

2. S chooses a hash function f :

{0, 1} * × F N -K 2 -→ F k 2 . 3. S draws a random binary (N -K) × N matrix H.
4. S randomly picks a subset J of {1, . . . , N } of cardinality n. 5. S randomly picks a k × n generator matrix G that defines a binary code C hidden such that with high probability t1 |u| t2 for any non-zero codeword u ∈ C hidden .

6.

F def = HJ G T
where HJ is the restriction of H to the columns in J. -Keys.

• Private key. J and G • Public key. F and H -Signature. The signature of a message x ∈ {0, 1} * is (h, σ) defined as follows:

• S picks a random e ∈ F N 2 such that |e| = n. • Let h def = f (x, He T ) and y be the unique vector of F N 2 such that (i) supp(y) ⊂ J, (ii) y J = hG. The second part of the signature σ is then given by σ

def = y + e. -Verification. Given a signature (h, σ) ∈ F k 2 × F N 2 for x ∈ {0, 1} * , the verifier checks that |σ| 2n and h = f (x, Hσ T + F h T ).
even be refined in the following way. Whenever we are able to produce one valid message-signature pair, and since each signature reveals partial information about the private key (especially about J as explained further in this section), we can use it to get another valid message-signature pair revealing more information about J. We repeat this process a few times until we totally recover the whole private key. More details will be given in the following sections.

In what follows, we make the assumption that all the codes are binary because all the concrete proposals are of this kind. The non-binary case will be discussed in the conclusion.

An auxiliary code

We give here the first ingredient we use to forge a valid message/signature pair for the KKS scheme just from the knowledge of the public pair H, F . This attack can also be used for the second scheme given by Figure 2. In the last case, it is not a valid message/signature pair anymore but an auxiliary quantity which helps in revealing J. This ingredient consists in a linear code C pub of length N + k defined as the kernel of Ĥ which is obtained by the juxtaposition of the two public matrices H and F as given in Figure 3. The reason behind this definition lies in the following Fact 1.

Fig. 3. Parity-check matrix Ĥ of the code C pub N k N-K H = ^H F Fact 1. Let x ′ be in F N +k 2 and set (σ||x) def = x ′ with σ in F N 2 and x in F k 2 .
Then σ is a signature of x if and only if:

1. Ĥx ′T = 0 2. t 1 |σ| t 2 .
The code C pub is of dimension k + K, and of particular interest is the linear space C sec ⊂ C pub that consists in words that satisfy both conditions of Fact 1 and that are obtained by all pairs (σ, x) of valid message-signature pairs which are obtained by the secret signature algorithm, that is to say:

C sec def = (σ||x) ∈ F N +k 2 : x ∈ F k 2 , σ ∈ F N 2 , σ J = xG, σ [1•••N ]\J = 0 . (1)
Clearly, the dimension of C sec is k. Additionally, we expect that the weight of σ is of order n/2 for any (σ, x) in C sec , which is much smaller than the total length N . This strongly suggests to use well-known algorithms for finding low weight codewords to reveal codewords in C sec and therefore message-signature pairs. The algorithm we used for that purpose is specified in the following subsection.

Finding low-weight codewords

We propose to use the following variation on Stern's algorithm due to [START_REF] Dumer | On minimum distance decoding of linear codes[END_REF] (See also [START_REF] Finiasz | Security bounds for the design of code-based cryptosystems[END_REF]). The description of the algorithm is given in Algorithm 1. It consists in searching for low-weight codewords among the candidates that are of very low-weight 2p ( where p is typically in the range 1 p 4) when restricted to a set I of size slightly larger than the dimension k + K of the code C pub , say |I| = k + K + l for some small integer l. The key point in this approach is to choose I among a set S of test positions. The set S will be appropriately chosen according to the considered context. If no signature pair is known, then a good choice for S is to take:

S = [1 • • • N ]. (2)
This means that we always choose the test positions among the N first positions of the code C pub and never among the k last positions. The reason for this choice will be explained in the following subsection.

H H

H 0 1 1 ... 1 0 0 1 2 N-K-l (K+k+l)/2 (K+k+l)/2 N-K-l l

Explaining the success of the attack

It turns out that this attack works extremely well on all the parameter choices made in the literature, and this even without knowing a single message-signature pair which would make life much easier for the attacker as demonstrated in [START_REF] Cayrel | On Kabatianskii-Krouk-Smeets Signatures[END_REF]. In a first pass, the attack recovers Algorithm 1 KKSforge: algorithm that forges a valid KKS signature.

PARAMETERS:

r : number of iterations, l : small integer (l 40), p : very small integer (1 p 4). S : a subset of [1 • • • N ] from which in each iteration a subset of cardinality K + k + l will be randomly chosen.

INPUT: Ĥ OUTPUT: a list L containing valid signature/message pairs (σ, x) ∈ F N 2 ×F k 2 . 1: L ← ∅. 2: for 1 t r do 3:
Step 1: Randomly pick K + k + l positions among S to form the set I. This set is partitioned into

I = I1 ∪ I2 such that ||I1| -|I2|| 1. 4:
Step 2: Perform Gaussian elimination over the complementary set {1, 2, . . . , N + k} \ I to put Ĥ in quasi-systematic form (as shown in Figure 4). 5:

Step

x def = (x1||x2||x3) of C pub 10: if t1 |x [1•••N ] | t2 then 11: L ← L ∪ {x} 12:
end if 13:

end for 14:

end for 15: end for 16: return L easily message-signature pairs for all the parameters suggested in [BMJ11, [START_REF] Kabatianskii | A digital signature scheme based on random errorcorrecting codes[END_REF][START_REF] Kabatiansky | Error Correcting Coding and Security for Data Networks: Analysis of the Superchannel Concept[END_REF]. Once a signature-message pair is obtained, it can be exploited to bootstrap an attack that recovers the private key as we will explain later.

The reason why the attack works much better here than for general linear codes comes from the fact that Ĥ does not behave like a random matrix at all even if the two chosen matrices for the scheme, namely H and G are chosen at random. The left part and the right part H and F are namely related by the equation:

F = H J G T .
Indeed, the parity-check matrix Ĥ displays peculiar properties: C pub contains C sec as a subcode and its codewords represent valid message-signature pairs. This subcode has actually a very specific structure that helps greatly the attacker:

1. There are many codewords in C sec , namely 2 k . 2. The support of these codewords is included in a fixed (and rather small) set of size k + n.

3. k positions of this set are known to the attacker. 4. These codewords form a linear code (of dimension k).

Because of all these properties, the aforementioned attack will work much better than should be expected from a random code. More precisely, let us bring in:

I ′ def = I ∩ J.
Notice that the expectation E {|I ′ |} of the cardinality of the set I ′ is equal to:

E {|I ′ |} = n N (k + K + l) = (R + αρ + λ)n (3)
where we introduced the following notation:

R def = K N , ρ def = k n , α def = n N and λ def = l N .
The point is that whenever there is a codeword c in C sec which is such that |c I ′ | = 2p we have a non-negligible chance to find it with Algorithm 1. This does not hold with certainty because the algorithm does not examine all codewords x such that |x I | = 2p, but rather it consists in splitting I in I 1 and I 2 of the same size and looking for codewords x such that |x I1 | = |x I2 | = p. In other words, we consider only a fraction δ of such codewords where:

δ = (K+k+l)/2 p (K+k+l)/2 p K+k+l 2p ≈ (K + k + l) πp(K + k + l -2p)
.

We will therefore obtain all codewords c in C sec which are such that |c I1 | = |c I2 | = p. Consider now the restriction C ′ sec of C sec to the positions belonging to I ′ , that is:

C ′ sec = (x i ) i∈I ′ : x = (x i ) i∈[1•••N +k] ∈ C sec . (4)
The crucial issue is now the following question:

Does there exist in C ′ sec a codeword of weight 2p? The reason for this is explained by the following proposition.

Proposition 1. Let I ′ s def = I s ∩ J for s ∈ {1, 2}. If there exists a codeword x ′ in C ′ sec such that |x ′ I ′ 1 | = |x ′ I ′ 2 | = p,
then it will be the restriction of a codeword x in C sec which will belong to the list L output by Algorithm 1.

Proof. Consider a codeword x ′ in C ′ sec such that |x ′

I ′ 1 | = |x ′ I ′ 2 | = p.
For s ∈ {1, 2}, extend x I ′ s with zeros on the other positions of I s and let x s be the corresponding word. Notice that x 1 and x 2 will be considered by Algorithm 1 and x 1 will be stored at the address H 1 x T 1 . By definition of x ′ , (x 1 ||x 2 ) is the restriction of a codeword x of C sec to I, say x = (x 1 ||x 2 ||y) with y ∈ F N -K-l 2 . Since C sec ⊂ C pub we have Ĥx T = 0. Let Ĥ′ be the matrix obtained from Ĥ put in quasi-systematic form through a Gaussian elimination as given in Figure 4. We also have Ĥ′ x T = 0 and hence:

H 1 x T 1 + H 2 x T 2 = 0 (5)
and

H 3 (x 1 ||x 2 ) T + y T = 0. (6)
Equation (5) shows that x 1 is stored at address H 2 x T 2 and will be considered at Step 8 of the algorithm. In this case, x will be stored in L.

⊓ ⊔

We expect that the dimension of C ′ sec is still k and that this code behaves like a random code of the same length and dimension. Ignoring the unessential issue whether or not x ′ satisfies |x ′

I ′ 1 | = |x ′ I ′ 2 | = p, let us just assume that there exists x ′ in C ′ sec such that |x ′ | = 2p.
There is a non negligible chance that we have |x ′

I ′ 1 | = |x ′ I ′ 2 | = p
and that this codeword will be found by our algorithm. The issue is therefore whether or not there is a codeword of weight 2p in a random code of dimension k and length |I ′ |. This holds with a good chance (see [START_REF] Barg | Random codes: Minimum distances and error exponents[END_REF] for instance) as soon as:

2p d GV (|I ′ |, k) (7)
where d GV (|I ′ |, k) denotes the Gilbert-Varshamov distance of a code of length |I ′ | and dimension k. Recall that [START_REF] Macwilliams | The Theory of Error-Correcting Codes[END_REF]:

d GV (|I ′ |, k) ≈ h -1 (1 -k/|I ′ |) |I ′ |
where h -1 (x) is the inverse function defined over [0, 1 2 ] of the binary entropy function h(x)

def = -x log 2 x -(1 -x) log 2 (1 -x).
Recall that we expect to have:

|I ′ | ≈ (R + αρ + λ)n, which implies k |I ′ | ≈ ρ R + αρ + λ ≈ ρ R
when α and λ are small. Roughly speaking, to avoid such an attack, several conditions have to be met:

1. ρ has to be significantly smaller than R, 2. n has to be large enough.

This phenomenon was clearly not taken into account in the parameters suggested in [KKS97,KKS05,BMJ11] as shown in Table 1. The values of d GV (|I ′ |, k) are extremely low (in the range 1 -6). In other words, taking p = 1 is already quite threatening for all these schemes. For the first parameter set, namely (k, n, K, N ) = (60, 1023, 192, 3000), this suggests to take p = 3. Actually taking p = 1 is already enough to break the scheme. The problem with these low values of p comes from the dependency of the complexity in p as detailed in the following section. For instance as long as p is smaller than 3 the complexity of one iteration is dominated by the Gaussian elimination Step 2. Finally, let us observe that when this attack gives a message/signature pair, it can be used as a bootstrap for an attack that recovers the whole private key as will be explained in the following subsection.

Exploiting a signature for extracting the private key

If a signature σ of a message x is known, then y def = (σ, x) is a codeword of C sec which has weight about n/2 when restricted to its N first positions. This yields almost half of the positions of J. This can be exploited as follows. We perform the same attack as in the previous subsection, but we avoid choosing positions i for which σ i = 1. More precisely, if we let

J σ def = supp(σ) = {i : σ i = 1}, then we choose K + k + l positions among [1 • • • N ] \ J σ to form I.
The point of this choice is that we have more chances to have a smaller size for I ′ = I ∩ J. Let n ′ def = |I ′ |, we have now:

E {n ′ |J σ } = n -|J σ | N -|J σ | (k + K + l) (8) E {|I ′ |} = E {E {n ′ |J σ }} ≈ n/2 (N -n/2) (k + K + l). ( 9
)
The last approximation follows from the fact that the weight |σ| is quite concentrated around n/2. The same reasoning can be made as before, but the odds that the algorithm finds other valid signatures are much higher. This comes from the fact that the expectation |I ′ | is half the expected size of I ′ in the previous case as given in Equation ( 3). Previously we had E

|I ′ | k ≈ R ρ
, whereas now we have:

E |I ′ | k ≈ R 2ρ .
In other words, in order to avoid the previous attack we had to take ρ significantly smaller than R and now, we have to take ρ significantly smaller than R/2. For all the parameters proposed in the past, it turns out that d GV (|I ′ |, k) is almost always equal to 1, which makes the attack generally successful in just one iteration by choosing p = 1.

Moreover, if another valid signature σ ′ is obtained and by taking the union J σ ∪ J σ ′ of the supports, then about 3/4 of the positions of J will be revealed. We can start again the process of finding other message/signature pairs by choosing K + k + l positions among {1, 2, . . . , N } \ (J σ ∪ J σ ′ ) to form the sets I. This approach can be iterated as explained in Algorithm 2. This process will quickly reveal the whole set J and from this, the private key is easily extracted as detailed in [START_REF] Cayrel | On Kabatianskii-Krouk-Smeets Signatures[END_REF].

Algorithm 2 Recovering the private key from t 1 signatures.

PARAMETERS:

r : number of iterations l : small integer (l 40) p : very small integer (1 p 4).

INPUT:

Ĥ : public matrix as defined in Figure 3 {σ1, . . . , σt} : list of t 1 valid signatures

OUTPUT: J ⊂ [1 • • • N ] of cardinality n 1: J ← ∪ t i=1 supp(σi) 2: repeat 3: S ← [1 • • • N ] \ J 4:
L ← KKSforge(r,l,p,S, Ĥ) 5:

for all σ ∈ L do 6:

J ← J ∪ supp(σ) 7:
end for 8: until |J| = n 9: return J Finally, let us focus on the variant proposed in [START_REF] Barreto | One-time signature scheme from syndrome decoding over generic error-correcting codes[END_REF]. In this case, we have slightly less information than in the original KKS scheme. This can be explained by the following reasoning. In this case too, we choose S again as [1 • • • N ]\J σ , where as before J σ is defined as

J σ def = {i : σ i = 1}.
However this time, by defining n ′ again as n ′ def = |I ′ |, we have

E {n ′ |J σ } = |J ′ σ | N -|J σ | (k + K + l)
where J ′ σ = J \ J σ . However, this time due to the noise which is added, |J σ | is expected to be larger than before (namely of order n 2 + (N -n)n

N

).

Analysis of the Attack

The purpose of this section is to provide a very crude upper-bound on the complexity of the attack. We assume here that the code C rand of length n which is equal to the restriction on J of C sec :

C rand def = (x j ) j∈J : x = (x 1 , . . . , x N +k ) ∈ C sec
behaves like a random code. More precisely we assume that it has been chosen by picking a random parity-check matrix H rand of size (nk) × n (by choosing its entries uniformly at random among F 2 ). This specifies a code C rand of length n as C rand = {x ∈ F n 2 : H rand x T = 0}. We first give in the following section some quite helpful lemmas about codes of this kind.

Preliminaries about random codes

We are interested in this section in obtaining a lower bound on the probability that a certain subset X of F n 2 has a non empty intersection with C rand . For this purpose, we first calculate the two following probabilities. The probabilities are taken here over the random choices of H rand . Lemma 1. Let x and y be two different and nonzero elements of

F n 2 . Then prob(x ∈ C rand ) = 2 k-n (10) prob(x ∈ C rand , y ∈ C rand ) = 2 2(k-n) (11)
To prove this lemma, we will introduce the following notation and lemma. For x = (x i ) 1 i s and y = (y i ) 1 i s being two elements of F s 2 for some arbitrary s, we define x • y as

x • y = 1 i s x i y i ,
the addition being performed over F 2 .

Lemma 2. Let x and y be two different and nonzero elements of F n 2 and choose h uniformly at random in F n 2 , then

prob(x • h = 0) = 1 2 (12) prob(x • h = 0, y • h = 0) = 1 4 (13)
Proof. To prove Equation (12) we just notice that the subspace {h ∈ F n 2 : x•h = 0} is of dimension n -1. There are therefore 2 n-1 solutions to this equation and

prob(x • h = 0) = 2 n-1 2 n = 1 2 .
On the other hand, the hypothesis made on x and y implies that x and y generate a subspace of dimension 2 in F n 2 and that the dual space, that is {h ∈

F n 2 : x • h = 0, y • h = 0} is of dimension n -2. Therefore prob(x • h = 0, y • h = 0) = 2 n-2 2 n = 1 4 ⊓ ⊔ Proof (of Lemma 1). Let h 1 , . . . , h n-k be the n -k rows of H rand . Then prob(x ∈ C rand ) = prob(H rand x T = 0) = prob(h 1 • x = 0, . . . , h n-k • x = 0) = prob(h 1 • x = 0) . . . prob(h n-k • x = 0) (14) = 2 k-n (15)
where Equation ( 14) follows by the independence of the events and Equation (15) uses Lemma 2. Equation ( 11) is obtained in a similar fashion. ⊓ ⊔ Lemma 3. Let X be some subset of F n 2 of size m and let f be the function defined by f (x)

def = max x(1 -x/2), 1 -1
x . We denote by x the quantity m 2 n-k , then prob(X ∩ C rand = ∅) ≥ f (x).

Proof. For x in X we define E x as the event "x belongs to C rand " and we let q def = 2 k-n . We first notice that

prob(X ∩ C rand = ∅) = prob x∈X E x .
By using the Bonferroni inequality [START_REF] Comtet | Advanced Combinatorics[END_REF]p. 193] on the probability of the union of events we obtain

prob x∈X E x ≥ x∈X prob(E x ) - {x,y}⊂X prob(E x ∩ E y ) (16) ≥ mq - m(m -1) 2 q 2 (17) ≥ mq - m 2 q 2 2 ≥ mq(1 -mq/2),
where (17) follows from Lemma 1. This bound is rather sharp for small values of mq. On the other hand for larger values of mq, another lower bound on prob(X ∩ C rand = ∅) is more suitable [dC97]. It gives

prob x∈X E x ≥ x∈X prob(E x ) 2 y∈X prob(E x ∩ E y ) (18) ≥ mq 2 q + (m -1)q 2 (19) ≥ mq 2 q + mq 2 (20) ≥ 1 1 + 1 mq ≥ 1 - 1 mq ,
By taking the maximum of both lower bounds, we obtain our lemma. ⊓ ⊔

Estimating the complexity of Algorithm 1

Here we estimate how many iterations have to be performed in order to break the scheme when no signature is known and when

S = [1 • • • N ].
For this purpose, we start by lower-bounding the probability that an iteration is successful. Let us bring the following random variables for i ∈ {1, 2}:

I ′ i def = I i ∩ J and W i def = |I ′ i |
. By using Lemma 1, we know that an iteration finds a valid signature when there is an x in C sec such that |x

I ′ 1 | = |x I ′ 2 | = p.
Therefore the probability of success P succ is lower bounded by

P succ ≥ w1,w2:w1+w2 n prob(W 1 = w 1 , W 2 = w 2 )prob ∃x ∈ C sec : |x I ′ 1 | = x I ′ 2 | = p|W 1 = w 1 , W 2 = w 2 (21)
On the other hand, by using Lemma 3 with the set

X def = x = (x j ) j∈J : |x I ′ 1 | = x I ′ 2 | = p which is of size w1 p w2 p 2 n-w1-w2 , we obtain prob ∃x ∈ C sec : |x I ′ 1 | = x I ′ 2 | = p|W 1 = w 1 , W 2 = w 2 ≥ f (x). ( 22
)
with

x def = w1 p w2 p 2 n-w1-w2 2 n-k = w 1 p w 2 p 2 k-w1-w2
The first quantity is clearly equal to

prob(W 1 = w 1 , W 2 = w 2 ) = n w1 n-w1 w2 N -n (K+k+l)/2-w1 N -n-(K+k+l)/2+w1 (K+k+l)/2-w2 N (K+k+l)/2 N -(K+k+l)/2 (K+k+l)/2 . ( 23
)
Plugging in the expressions obtained in ( 22) and ( 23) in ( 21) we have an explicit expression of a lower bound on P succ . The number of iterations for our attack to be successful is estimated to be of order 1 Psucc . We obtain therefore an upper-bound on the expected number of iterations, what we denote by UpperBound. Table 2 shows for various KKS parameters, p and l the expected number of iterations.

Number of operations of one iteration

The complexity of one iteration of Algorithm 1 is C(p, l) = C Gauss + C hash + C check where C Gauss is the complexity of a Gaussian elimination, C hash is the complexity of hashing all the x 1 's and C check is the complexity of checking all the x 2 's with the following expressions:

C Gauss = O (N + k)(N -k)(N -k -l) = O(N 3 ) (24) C hash = O (K + k + l)/2 p (25) C check = O 1 2 l (N -K -l) 2 (K + k + l)/2 p 2 (26)
The last expression giving C check comes from the fact that the algorithm considers (K+k+l)/2 p elements x 2 , and for each of these candidates, we check about O 1 2 l (K+k+l)/2 p elements x 1 's, which involves a matrix multiplication in Step 9. Let us note that l will be chosen such that C hash and C check are roughly of the same order, say 2 l ≈ (K+k+l)/2 p Table 3

Concluding Remarks

Design principles. As explained in Section 3, the parameters of the KKS scheme were chosen in order to make decoding of C known intractable when the weight of errors is in the range

[t 1 • • • t 2 ],
where C known denotes the code defined by the parity-check matrix H. In [START_REF] Barreto | One-time signature scheme from syndrome decoding over generic error-correcting codes[END_REF], it is further required that C known is of minimum distance greater than 4n. Both requirements are clearly insufficient to ensure that the scheme is secure as demonstrated by this paper. We suggest here to replace all these requirements by choosing the parameters such as to make our attack impracticable. This algorithm is exponential in nature when the parameters are well chosen. If we want to avoid that the knowledge of a message-signature pair allows to recover the secret key, this implies for instance that the rate R of C known should be significantly larger than 2ρ, that is twice the rate of the secret code C hidden . This would change the parameters of the scheme significantly and give much larger key sizes than has been proposed in [KKS97, [START_REF] Kabatiansky | Error Correcting Coding and Security for Data Networks: Analysis of the Superchannel Concept[END_REF][START_REF] Barreto | One-time signature scheme from syndrome decoding over generic error-correcting codes[END_REF]. Choosing these parameters requires however to analyze properly the complexity of the attack when one messagesignature is known (here we just analyzed the complexity of the attack which does not make use of any message-signature pair). The analysis we performed in our case can be carried over to the case when a message-signature pair is known but this is beyond the scope of this paper and will appear in a full version of this paper.

Relating the security to the problem of decoding a linear code. The attack which has been suggested here is nothing but a well known algorithm for finding low weight codewords or for decoding a generic linear code. It just happens that this algorithm is much more powerful here than for a random linear code due to the peculiar nature of the code it is applied to. However as mentioned above, this attack is exponential in nature and can easily be defeated by choosing the parameters appropriately. It would be interesting to analyze the relationship of the problem of breaking the KKS scheme with decoding problems in more depth, or to prove that the problem which has to be solved is indeed NP hard.

Non-binary codes. Obviously there is a non binary version of the KKS scheme which would deal with codes defined over larger alphabets. The benefits of the generalized scheme are questionable. The attack presented here generalizes easily to higher order fields. What is more, moving to non-binary fields seems to be a poor idea in terms of security. For instance, whereas a message/signature pair reveals only half the positions of J in the binary case, in the q-ary case we expect to obtain roughly a fraction q-1 q of positions of J, which is significantly larger. Decoding one out of many. Another approach could have been used for attacking the scheme. Let us denote by s 1 , • • • , s k the columns of F . These vectors can be considered as k syndromes of codewords of C hidden with respect to the parity-check matrix H. If we want to obtain one message/pair we can try to find an error e i of weight in the range [t 1 • • • t 2 ] such that He T i = s i . This suggests to use "the decoding one out of many" approach [START_REF] Sendrier | Decoding one out of many[END_REF], that is we have k words to decode and we want to decode at least one of them. This problem can be solved more efficiently than just decoding one instance. We can even refine this approach by considering all possible syndromes obtained by all possible (non-zero) combinations i α i s i . In this case, we would have to solve "a decoding one out of many" problem with 2 k -1 instances. However a naive use of the results of [START_REF] Sendrier | Decoding one out of many[END_REF] would be far from indicating that all the parameters of [KKS97, [START_REF] Kabatiansky | Error Correcting Coding and Security for Data Networks: Analysis of the Superchannel Concept[END_REF][START_REF] Barreto | One-time signature scheme from syndrome decoding over generic error-correcting codes[END_REF] are easily broken by this approach.

Fig. 1 .

 1 Fig. 1. Description of the KKS scheme given in [KKS97].

Fig. 2 .

 2 Fig. 2. Description of the scheme of [BMJ11].

Fig. 4 .

 4 Fig. 4. A parity-check matrix for C pub in quasi-systematic form.

Table 1 .

 1 KKS Parameters with the corresponding value of dGV(n ′ , k).

	Article	ρ	n l n ′ def = E {|I ′ |}	R	N dGV(n ′ , k)
	[KKS97] 60 1023 ≈ 0.059 1,023 8 [KKS05] 48 255 ≈ 0.188 255 8 [KKS97] 48 180 ≈ 0.267 180 8	89 65 64	192 3000 ≈ 0.064 3,000 273 1200 ≈ 0.228 1,200 335 1100 ≈ 0.305 1,100	6 5 4
	[BMJ11]	1/2	320 12	165	1/2	11,626	1
	[BMJ11]	1/2	448 13	230	1/2	16,294	1
	[BMJ11]	1/2	512 13	264	1/2	18,586	1
	[BMJ11]	1/2	768 13	395	1/2	27,994	2
	[BMJ11]	1/2	1,024 14	527	1/2	37,274	2

Table 2 .

 2 KKS Parameters with the corresponding value of 1 Psucc .

	Article	ρ	n	l p n ′ def = E {|I ′ |}	R	N	UpperBound
	[KKS97] 60 1023 ≈ 0.059 1,023 8 1 60 1023 ≈ 0.059 1,023 14 2 [KKS05] 48 255 ≈ 0.188 255 8 1 48 255 ≈ 0.188 255 14 2 [KKS97] 48 180 ≈ 0.267 180 8 1 48 180 ≈ 0.267 180 15 2	91 91 66 66 65 65	192 3000 ≈ 0.064 3,000 192 3000 ≈ 0.064 3,000 273 1200 ≈ 0.228 1,200 273 1200 ≈ 0.228 1,200 335 1100 ≈ 0.305 1,100 335 1100 ≈ 0.305 1,100	111.26 14.17 26.41 4.37 6.07 1.82
	[BMJ11]	1/2	320 12 1	165	1/2	11,626	1.24
	[BMJ11]	1/2	448 13 1	230	1/2	16,294	1.34
	[BMJ11]	1/2	512 13 1	264	1/2	18,586	1.39
	[BMJ11]	1/2	768 13 1	395	1/2	27,994	1.61
	[BMJ11]	1/2	1,024 14 1	527	1/2	37,274	1.85

.

  Average number of iterations of Algorithm 1.

	Article	ρ	n l p	R	N UpperBound t1 t2 Iterations Average time of
									an attack (in s)
	[KKS97] 60 1023 ≈ 0.059 1,023 8 1 192 3000 ≈ 0.064 3,000 60 1023 ≈ 0.059 1,023 14 2 192 3000 ≈ 0.064 3,000 [KKS05] 48 255 ≈ 0.188 255 8 1 273 1200 ≈ 0.228 1,200 48 255 ≈ 0.188 255 14 2 273 1200 ≈ 0.228 1,200 [KKS97] 48 180 ≈ 0.267 180 8 1 335 1100 ≈ 0.305 1,100 48 180 ≈ 0.267 180 15 2 335 1100 ≈ 0.305 1,100	111.26 14.17 26.41 4.37 6.07 1.82	352 672 102.34 352 672 9.22 48 208 24.32 48 208 3.13 96 96 5.58 96 96 1.23	19.50 1.754 0.384 0.051 0.061 0.017
	[BMJ11]	1/2	320 12 1	1/2	11,626	1.24	133 187	1.13	6.425
	[BMJ11]	1/2	448 13 1	1/2	16,294	1.34	192 256	1.18	18.90
	[BMJ11]	1/2	512 13 1	1/2	18,586	1.39	222 290	1.26	32.23
	[BMJ11]	1/2	768 13 1	1/2	27,994	1.61	342 426	1.51	119.5
	[BMJ11]	1/2	1,024 14 1	1/2	37,274	1.85	464 560	1.73	350.8