Edward Eaton
email: ted.eaton@isara.com

Matthieu Lequesne
email: matthieu.lequesne@inria.fr

Alex Parent
email: alex.parent@isara.com

Nicolas Sendrier
email: nicolas.sendrier@inria.fr

QC-MDPC: A Timing Attack and a CCA2 KEM

Keywords: post-quantum cryptography, code-based cryptography, QC-MDPC codes, side-channel attack, timing attack, CCA2 security, key encapsulation

In 2013, Misoczki, Tillich, Sendrier and Barreto proposed a variant of the McEliece cryptosystem based on quasi-cyclic moderatedensity parity-check (QC-MDPC) codes. This proposal uses an iterative bit-flipping algorithm in its decryption procedure. Such algorithms fail with a small probability. At Asiacrypt 2016, Guo, Johansson and Stankovski (GJS) exploited these failures to perform a key recovery attack. They introduced the notion of the distance spectrum of a sparse vector and showed that the knowledge of the spectrum is enough to find the vector. By observing many failing plaintexts they recovered the distance spectrum of the QC-MDPC secret key. In this work, we explore the underlying causes of this attack, ways in which it can be improved, and how it can be mitigated. We prove that correlations between the spectrum of the key and the spectrum of the error induce a bias on the distribution of the syndrome weight. Hence, the syndrome weight is the fundamental quantity from which secret information leaks. Assuming a side-channel allows the observation of the syndrome weight, we are able to perform a key-recovery attack, which has the advantage of exploiting all known plaintexts, not only those leading to a decryption failure. Based on this study, we derive a timing attack. It performs well on most decoding algorithms, even on the recent variants where the decryption failure rate is low, a case which is more challenging to the GJS attack. To our knowledge, this is the first timing attack on a QC-MDPC scheme. Finally, we show how to construct a new KEM, called ParQ that can reduce the decryption failure rate to a level negligible in the security parameter, without altering the QC-MDPC parameters. This is done through repeated encryption. We formally prove the IND-CCA2 security of ParQ, in a model that considers decoding failures. This KEM offers smaller key sizes and is suitable for purposes where the public key is used statically.

Introduction

Code-based cryptography is almost as mature as public-key cryptography itself, dating back to 1978 with the invention of the original McEliece public-key encryption scheme [START_REF] Mceliece | A public-key cryptosystem based on algebraic coding theory[END_REF]. This scheme, when used with (as originally proposed) binary Goppa codes, has largely resisted all cryptanalytic efforts, from both classical and quantum adversaries. Because of this, code-based cryptography is a strong candidate for post-quantum standardisation, with several variants [START_REF] Niederreiter | Knapsack type of cryptosystems and algebraic coding theory[END_REF][START_REF] Monico | Using low density parity check codes in the McEliece cryptosystem[END_REF] attempting to make improvements or refinements on the original design.

Following [START_REF] Gaborit | Shorter keys for code based cryptography[END_REF][START_REF] Baldi | A new analysis of the McEliece cryptosystem based on QC-LDPC codes[END_REF], a new variant was proposed in 2013 using quasi-cyclic (QC) moderate density parity-check (MDPC) codes [START_REF] Misoczki | MDPC-McEliece: New McEliece variants from moderate density parity-check codes[END_REF]. QC-MDPC codes use much shorter keys (about 10 kbits). This choice appears promising and the QC-MDPC scheme was recommended for further study by the report "Initial Recommendation of long-term secure post-quantum systems" of the European project PQCRYPTO [START_REF] Augot | Initial recommendations of long-term secure post-quantum systems[END_REF]. Some hardware implementations of this scheme were published in [START_REF] Heyse | Smaller keys for code-based cryptography: QC-MDPC McEliece implementations on embedded devices[END_REF] and [START_REF] Von Maurich | Implementing QC-MDPC McEliece encryption[END_REF].

The decryption algorithm of the QC-MDPC scheme is a variant of Gallager's bit-flipping algorithm [START_REF] Gallager | Low-Density Parity-Check Codes[END_REF]. It is an iterative algorithm with a simple structure, very easy to implement, even on constrained devices. It has an inconvenient though, it is subject to failure with non-negligible probability. The algorithm proposed in the original paper [START_REF] Misoczki | MDPC-McEliece: New McEliece variants from moderate density parity-check codes[END_REF] has a decoding failure rate (DFR) of 10 -7 .

While decoding errors may not represent a serious reliability issue, in a recent paper by Guo, Johansson and Stankovski (GJS) [START_REF] Guo | A key recovery attack on MDPC with CCA security using decoding errors[END_REF], the authors showed that these decoding failures actually do represent a very serious security issue. The authors exploited this DFR and managed to successfully recover the key by analyzing the error patterns that made the decryption fail. They found that these error patterns are correlated with the key. They introduce a new tool, the distance spectrum, to describe the correlation. They successfully use this correlation to perform their attack and give some hints on the reason why error patterns correlated in such a way are more prone to cause decryption failure.

The original QC-MDPC primitive is extremely vulnerable because the adversary may choose the error and even force a higher weight, in this case the attack of [START_REF] Guo | A key recovery attack on MDPC with CCA security using decoding errors[END_REF] recovers the key within minutes, when attacking a parameter set intended for the 80-bit classical security level. With a semantically secure conversion (CCA security, as in [START_REF] Kobara | Semantically secure McEliece public-key cryptosystemsconversions for McEliece PKC[END_REF]) it requires 2 39.7 operations.

Our Contributions

In this paper we extend the analysis of the GJS attack on QC-MDPC. The GJS attack works because the decoding failure depends of the existence of common values in the spectrums of the error pattern and of the secret key. In Section 3 we show that this correlation can be observed through the weight distribution of the first syndrome computed by the MDPC decoder. Pushing the analysis further we are able to quantify this bias. This allows us to perform a side-channel attack using the syndrome weight to recover the distance spectrum of the secret key. We show that the number of samples we need to make this attack work is consistent with the Chernoff bound applied to the above mentioned bias. This opens the way to theoretical estimates for the cost of attacks related to the secret key distance spectrum recovery.

Next, by remarking that the syndrome weight is correlated to the decoding time, we perform a GJS type of attack by counting the number of iterations. This provides a timing attack which is very generic and can be applied to any variant of the bit flipping algorithm which is not protected against timing attacks. Moreover, it works regardless of the failure rate. To our knowledge, this is the first timing attack on this kind of scheme. This confirms a conjecture made by Maurich and Güneysu [START_REF] Von Maurich | Towards side-channel resistant implementations of QC-MDPC McEliece encryption on constrained devices[END_REF] that the number of iterations in the decoding procedure leaks secret information.

In Section 4 we demonstrate the power of this attack by showing experimental results of the timing attack on various parameter sets and decoding procedures. This shows that the attack is practical even against the 256-bit classical parameter set. Additionally, we analyze and discuss how some other variations in the decoding procedure proposed in [START_REF] Von Maurich | Implementing QC-MDPC McEliece encryption[END_REF] affect the attack and its effectiveness.

Finally in Section 5, we show a new construction for a QC-MDPC-based KEM, called ParQ. This KEM uses QC-MDPC encryption as the underlying primitive, and does not need to alter the parameter set of the primitive itself. The scheme works by creating multiple independent encapsulations of the same key, so that a decapsulation failure only occurs if a decoding failure happens for each ciphertext. This causes the decapsulation algorithm to only fail with negligible probability, and so it entirely eliminates the possibility of using decoding failures to recover the key with the GJS attack. This scheme does not increase key sizes at all, and only increases the size of the encapsulation by a small factor (3 -12×). We provide a comprehensive proof of IND-CCA2 security of the scheme, and analyse the KEM compared with other code-based key transport methods. Our proof considers the possibility of decoding failures. Other CCA2 constructions [START_REF] Kobara | Semantically secure McEliece public-key cryptosystemsconversions for McEliece PKC[END_REF][START_REF] Von Maurich | IND-CCA secure hybrid encryption from QC-MDPC Niederreiter[END_REF] did not consider this, which is why the GJS attack was able to break CCA2 security. Most commentary on mitigating the GJS attack has focused on either altering the parameters of QC-MDPC to decrease the DFR or using the keys ephemerally. Through our scheme we show that there is a third option that can address decoding failures at the protocol level.

Related Work

The McEliece cryptosystem was originally proposed in [START_REF] Mceliece | A public-key cryptosystem based on algebraic coding theory[END_REF], and low density parity-check codes were proposed in [START_REF] Gallager | Low-Density Parity-Check Codes[END_REF]. The QC-MDPC variant of McEliece was proposed in [START_REF] Misoczki | MDPC-McEliece: New McEliece variants from moderate density parity-check codes[END_REF]. The key-recovery reaction attack we focus on in this paper was shown in [START_REF] Guo | A key recovery attack on MDPC with CCA security using decoding errors[END_REF]. In [START_REF] Fabšič | A reaction attack on the QC-LDPC McEliece cryptosystem[END_REF], the authors analyzed how the observations from [START_REF] Guo | A key recovery attack on MDPC with CCA security using decoding errors[END_REF] applied to the case of LDPC McEliece [START_REF] Monico | Using low density parity check codes in the McEliece cryptosystem[END_REF], showing that the attack also worked on soft decision decoding procedures.

Since the first publication of the QC-MDPC scheme, efforts have been made to tune the decoding algorithm, especially exploring the different ways to fix the thresholds in order to reduce the DFR [START_REF] Chaulet | Worst case QC-MDPC decoder for mceliece cryptosystem[END_REF]. This is discussed in details in Section 2.2.

Side-channel timing attacks [START_REF] Kocher | Timing attacks on implementations of Diffie-Hellman, RSA, DSS, and other systems[END_REF] on McEliece systems other than QC-MDPC have been considered for example in [START_REF] Strenzke | A timing attack against the secret permutation in the McEliece PKC[END_REF][START_REF] Strenzke | Timing attacks against the syndrome inversion in code-based cryptosystems[END_REF][START_REF] Strenzke | Side channels in the McEliece PKC[END_REF] which has motivated the need for constant-time implementations [START_REF] Bernstein | McBits: Fast constant-time code-based cryptography[END_REF][START_REF] Chou | QcBits: Constant-time small-key code-based cryptography[END_REF]. In [START_REF] Von Maurich | Towards side-channel resistant implementations of QC-MDPC McEliece encryption on constrained devices[END_REF][START_REF] Chen | Differential power analysis of a mceliece cryptosystem[END_REF][START_REF] Chen | Horizontal and vertical side channel analysis of a mceliece cryptosystem[END_REF], the authors demonstrated several power-analysis side-channel attacks on QC-MDPC, and [START_REF] Von Maurich | Towards side-channel resistant implementations of QC-MDPC McEliece encryption on constrained devices[END_REF] conjectured that it might be possible that the number of decoding rounds leaks secret information. To our knowledge, our paper is the first to conclusively show that this is in fact the case.

CCA2 conversions for McEliece systems have been considered before, most notably in [START_REF] Kobara | Semantically secure McEliece public-key cryptosystemsconversions for McEliece PKC[END_REF]. General conversions for designing CCA2 KEMs from OW-CPA systems were studied in [START_REF] Dent | A designer's guide to KEMs[END_REF]. Other key exchange and key encapsulation schemes related to QC-MDPC include [START_REF] Barreto | CAKE: Code-based algorithm for key encapsulation[END_REF][START_REF] Chou | QcBits: Constant-time small-key code-based cryptography[END_REF][START_REF] Deneuville | Ouroboros: A simple, secure and efficient key exchange protocol based on coding theory[END_REF][START_REF] Von Maurich | IND-CCA secure hybrid encryption from QC-MDPC Niederreiter[END_REF].

A line of constructions beginning with [START_REF] Rosen | Chosen-ciphertext security via correlated products[END_REF], and applied to McEliece in several follow-up works [START_REF] Döttling | A CCA2 secure variant of the McEliece cryptosystem[END_REF][START_REF] Yoshida | Ouroboros: A simple, secure and efficient key exchange protocol based on coding theory[END_REF] explored the concept of the k-repetition paradigm for encryption. This paradigm bears some resemblance to our parallel KEM in Section 5, although these constructions are different and have a different goal: CCA2 security without random oracles. While QC-MDPC can allow for k to be any divisor of n, we will consider the case of n/k = 2. We let E denote the set of e ∈ IF n 2 with Hamming weight t. Note that the size of each block, r = (n -k) = k. Multiple parameter sets for QC-MDPC have been proposed for multiple security levels. Our interest is in the 80-bit and 256-bit classical security sets (which corresponds to at least 40-bit and 128-bit quantum security) that were originally proposed in [START_REF] Misoczki | MDPC-McEliece: New McEliece variants from moderate density parity-check codes[END_REF], and have been further discussed in [START_REF] Barreto | CAKE: Code-based algorithm for key encapsulation[END_REF]. The original paper on MDPC codes [START_REF] Misoczki | MDPC-McEliece: New McEliece variants from moderate density parity-check codes[END_REF] proposes to use a hard decision version of Gallager's bit-flipping algorithm for decoding LDPC codes [START_REF] Gallager | Low-Density Parity-Check Codes[END_REF]. The main idea is the following. At each iteration, the algorithm computes the number of unsatisfied parity-check equations associated to each bit. Each bit that is involved in ≥ b unsatisfied equations is flipped, for b some threshold, and the syndrome is recomputed. This repeats until the syndrome becomes zero. In practice, the algorithm stops after fixed number of iterations and this is considered a decoding failure.

QC-MDPC McEliece and the GJS Attack

Algorithm 1 QCMDPC.KeyGen

For our main analyses we use decoder D 1 from [START_REF] Von Maurich | Implementing QC-MDPC McEliece encryption[END_REF] with fixed thresholds {95, 85, 80, 76, 74, 73, 72, 72}. D 1 is a modification of Gallager's algorithm which updates the syndrome in place after each bit flipped. Algorithm 4 is the normal out-of-place bit flipping algorithm and Algorithm 5 is the in-place version.

Variable thresholds. A more recent approach, studied in [START_REF] Chaulet | Worst case QC-MDPC decoder for mceliece cryptosystem[END_REF], is to choose the values of b at each iteration depending on the syndrome weight at the time. This Algorithm 4 Iterative bit flipping decoding algorithm

Input: c = (c0, . . . , cn-1) ∈ IF n 2 , H = (h (0) , . . . , h (n-1) ) ∈ IF r×n 2 s ← H • c compute the syndrome while s = 0 do for i = 0, . . . , n -1 do if s, h (i) ≥ b then if number of unsatisfied equations ≥ threshold b ci ← ci ⊕ 1 flip the i th bit s ← H • c return c
Algorithm 5 In-Place: Iterative bit flipping decoding algorithm

Input: c = (c0, . . . , cn-1) ∈ IF n 2 , H = (h (0) , . . . , h (n-1) ) ∈ IF r×n 2 s ← H • c compute the syndrome while s = 0 do for i = 0, . . . , n -1 do if s, h (i) ≥ b then if number of unsatisfied equations ≥ threshold b ci ← ci ⊕ 1 flip the i th bit s ← s ⊕ h (i) return c
approach gives the best results so far, both in terms of decryption failure rate and average number of iterations.

In both cases, until now the thresholds were claimed as experimental results with no explanation on the way they were generated. In appendix B we discuss a procedure to obtain such thresholds for any security parameters.

The GJS Attack

The key recovery attack in [START_REF] Guo | A key recovery attack on MDPC with CCA security using decoding errors[END_REF] is a reaction attack. It takes advantage of the decoding failures that occasionally occur during decryption. It assumes only that an adversary is able to tell when such an error has occurred, for example because a request for resend is sent back. It consists of two steps. The first step is to calculate the distance spectrum of the secret key (or one part of the secret key), based on observing a large number of error vectors that resulted in a decoding failure. The second step is to reconstruct the secret key based on its distance spectrum.

In this paper, we will focus our attention on the first step. Reconstructing the secret key from the distance spectrum has been analysed before [START_REF] Guo | A key recovery attack on MDPC with CCA security using decoding errors[END_REF][START_REF] Fabšič | A reaction attack on the QC-LDPC McEliece cryptosystem[END_REF], and shown to be fairly fast and simple as compared to the first step, and is an entirely offline computation, requiring no communication.

Definition 1 (Distance Spectrum). The distance spectrum of a vector h ∈ IF r 2 , denoted ∆(h), is the set of distances δ such that there exist two non-zero bits of h at distance δ. The distance are counted cyclically.

∆(h) =    δ : 1 ≤ δ ≤ r 2 , ∃(i, j), 0 ≤ i < j < r, h[i] = h[j] = 1, min{j -i, r -(j -i)} = δ   
where h[i] denotes the i th entry of the binary vector h. For example, the distance spectrum of the vector 100100011 2 is {1, 2, 3, 4} (fig. 1). Note that any cyclic shift or reversal of a vector will result in the same distance spectrum. In [START_REF] Guo | A key recovery attack on MDPC with CCA security using decoding errors[END_REF][START_REF] Fabšič | A reaction attack on the QC-LDPC McEliece cryptosystem[END_REF], it was shown how to quickly reconstruct a vector (up to a reversal or cyclic shift) from a distance spectrum. The first step of the GJS attack is to find the distance spectrum of the first half h 0 of the secret key (h 0 , h 1 ). From this, h 0 can be computed, which allows us to also calculate h 1 by elementary linear algebra.

In order to analyse more precisely the results, we need to take into account the fact that some distances may appear more than once.

Definition 2 (Distance Spectrum with multiplicity). The distance spectrum with multiplicity of a vector h

∈ IF r 2 , denoted ∆ µ (h), is a vector of IN r 2 such that for every distance 1 ≤ δ ≤ r 2 , its δ th component ∆ µ (h)[δ]
is the number of existing sets of two non-zero bits of h at distance δ. The distance are counted cyclically.

Example 1. For h = 0011000011 2 (see Figure 1), then

∆ µ (h) = [2, 1, 1, 2].
In general we can see that if a vector h 0 ∈ IF k 2 has weight w 0 , then the distance spectrum with multiplicity of h 0 will be a vector of size k/2 such that the sum of the entries of ∆ µ (h 0 ) is w0 2 . Finding the distance spectrum of the secret key is done by taking note whether a decoding failure occurs for a large number of error vectors. This is done because of the following observation: Observation 1 (GJS, Key Observation). When a distance in the error vector used in a QC-MDPC encryption matches a distance in the distance spectrum of the secret key, a decoding failure is less likely to occur.

Based on this observation, it was noticed that by carefully calculating the decoding failure rate for errors that have a given distance vs. those that do not, the multiplicity of that distance in the secret key's distance spectrum can be correctly guessed. Note that this observation applies to each half of the error vector (and parity check matrix) independently. So when we refer to the distance spectrum of the error or parity-check matrix, we mean the distance spectrum of the first k bits, unless stated otherwise.

Algorithm 6 was proposed in [START_REF] Guo | A key recovery attack on MDPC with CCA security using decoding errors[END_REF] for attacking the CCA security of a QC-MDPC implementation. The resulting values, f ailed d /observed d for each d give an estimate of the decoding failure rate for error vectors with d in their distance spectrum. We can then recover the distance spectrum, identifying the multiplicity of each distance from the following observation:

Observation 2 (GJS). For a fixed key, the decoding failure rate for error vectors with d in their distance spectrum is inversely proportional to the multiplicity of d in the distance spectrum of the key.

For large enough values of M , the decoding failure rate clearly separates into bands. These bands exactly correspond to the multiplicity of that distance in ∆(h 0 ). This allows an attacker to recover ∆(h 0 ), and thus the secret key.

The complexity of the attack is dominated by the value M . The decoding failure rates for different multiplicities are quite close together, and so a very accurate estimation is need in order to properly decide on the multiplicity. In [START_REF] Guo | A key recovery attack on MDPC with CCA security using decoding errors[END_REF], the authors found that M = 2 29 was sufficient for the 80-bit classical parameter set, using the Gallager decoding algorithm. They conjectured that using a more sophisticated decoding algorithm like that in [START_REF] Misoczki | MDPC-McEliece: New McEliece variants from moderate density parity-check codes[END_REF], would mean that M would have to be increased by an amount proportional to the difference in the decoding failure rate. They also conjectured that higher parameter sets would not significantly alter the effectiveness of the attack, as the decoding failure rate does not significantly change.

3 Analysis and Timing Attack

Correlation

Our attack is based on the fact that the average syndrome weight is slightly different if the relative position of non-zero bits in the key and the error are correlated.

For the sake of simplicity, in this section, we will consider a parity-check matrix made of one single circulant block in H ∈ IF k×k 2 instead of two. We will see later that the practical results are the same. We denote by h ∈ IF k 2 the first row of the matrix H. The variable t still represents the weight of the error e, so here the numerical value of t should be half its usual value.

Without any information.

Let us suppose that we do not have any information on the key. For a random key vector h of size k and weight d and a random error vector e of size k and weight t, denote by f (k, d, t, b) the probability that the scalar product in IF 2 is of parity b:

f (k, d, t, b) := Pr[ h, e = b] = d i=0, i is of parity b d i k-d t-i k t .
The average syndrome weight of an error e and a parity-check matrix generated by cyclic shifts of h is k times the probability that a bit is non-zero (see [9, page 91]), that is:

E [ wt (H • e ) ] = k • f (k, d, t, 1).
Case of two consecutive non-zero bits in the key. Now, suppose the key vector h has times two consecutive non-zero bits. Let us observe the shifts of the vector:

shift(h) = 1 1 u, wt(u) = d -2 times shift(h) = 1 0 u, wt(u) = d -1 d -times shift(h) = 0 1 u, wt(u) = d -1 d -times shift(h) = 0 0 u, wt(u) = d k -2d + times.
Suppose that the first two bits of the error vector are non-zero, that is:

e = 1 1 u, wt(u) = t -2 .
With this extra assumption on the form of h and e, the average syndrome weight of e with respect to the the parity-check matrix H generated by cyclic shifts of h can now be approximated by:

E [ wt (H • e ) ] = f (k -2, d -2, t -2, 1) + 2(d -) f (k -2, d -1, t -2, 0) + (k -2d + ) f (k -2, d, t -2, 1). (1)
Contrary to the previous result, this is an approximation. Indeed, this model assumes that the rest of the vector (denoted by u) is random for each shift. It does not take into account the covariance between the bits of the syndrome. Previously we were averaging on all the lines and the covariance was therefore null, while here the fact that we group the rows depending on the value of the first two bits breaks the symmetry. Still, we will see that the approximation is close to the real value and we can neglect the correction term for the rest of the study.

Exploiting the leak. Suppose that we only consider error patterns starting with two consecutive non-zero bits, the syndrome weight is expected to be slightly different on average, depending on the number of times two consecutive bits are non-zero in the key vector h. Moreover, the expected value varies linearly with . Therefore, if we observe enough values of the syndrome weight, we can recover the value of . Definition 3 (Average syndrome weight with multiplicity). Let us denote by D the following set:

D := (h, e) ∈ IF k 2 × IF k 2 | wt(h) = d, wt(e) = t, δ ∈ ∆(e), ∆ µ (h)[δ] = .
The average syndrome weight with multiplicity σ is the expectation of the syndrome weight for a uniform distribution of (h, e) over D :

σ := E (h,e)∼U (D ) [ wt(H • e ) ] .
From the equation (1) in Section 3.1 we know that we can approximate σ by: σ

= f (k -2, d -2, t -2, 1) + 2(d -) f (k -2, d -1, t -2, 0) + (k -2d + ) f (k -2, d, t -2, 1). with f (k, d, t, b) := d i=0, i is of parity b d i k-d t-i k t
Comparison with measured values. The values of σ correspond to the different clusters that we can see on the figures. According to the approximation, the value of σ is linear in the multiplicity: σ0 -σ = •(σ 0 -σ 1 ). This is consistent with what we observe.. With the usual parameters for 80-bit security, (here using t = 42 as there is only one block) we obtain σ0 = 1324.23 and σ1 = 1323.28. When comparing the values to those measured on Fig. 2, we can see that the measured σ0 is slightly lower than the approximated value, and on the contrary σ1 is slightly higher. This error is due to the approximation that neglects the covariance. When performing the same experiment on parameters for LDPC codes, where the covariance is much smaller, the measures correspond exactly to the computed values.

As a consequence, the real distance σ0 -σ1 is smaller than the one computed using equation [START_REF]NIST post-quantum cryptography project[END_REF]. Hence, the theoretical analysis gives an interesting bound on the relative distance ε = σ0-σ1 k : ε measured < ε computed .

Hypothesis testing. Each syndrome is the result of k scalar products between the error and a parity-check equation. When the error contains a distance present in the spectrum of the key with multiplicity , the average syndrome weight is σ , this means that on average σ of the k parity-check equations are not verified. Hence, under the independence assumption, we can see each bit of the syndrome as a Bernoulli trial satisfied with probability σ k . Here, our goal is to decide for each distance δ whether or not δ is in the distance spectrum of h. We do not care about the multiplicity. Formally, we want to distinguish D 0 from ∪ ≥1 D . Let us by D ≥1 := ∪ ≥1 D . We can define σ≥1 on D ≥1 just like we defined σ on D . The sets are disjoint so we have

σ≥1 = ≥1 σ |D | ≥1 |D | .
Hence, deciding whether a distance is in the spectrum of the key or not is just like distinguishing a random binary variable with success probability p 0 := σ0 from a random binary variable with success probability p 1 := σ≥1 . This is a classic problem of hypothesis testing.

Note that for our parameters, the size of D for ≥ 2 is negligible compared to D 1 , hence there is no practical need to distinguish σ1 from σ≥1 .

Sample size. There is a lot of literature about hypothesis testing, and in particular a theorem from Chernoff [START_REF] Habib | Probabilistic methods for algorithmic discrete mathematics[END_REF] concerning such cases.

Proposition 1 (Chernoff 's bound). Let 0 < p < 1, let X 1 , X 2 , . . . , X N be in- dependent binary random variables, with Pr[X k = 1] = p and let S N = N k=1 X k N . Then for any t ≥ 0, Pr[|S N -p| ≥ t] ≤ 2e -2N t 2 .
This can be used to understand how the number of samples required to find the key evolves. Here we want to distinguish p 0 from p 1 , we will use p0+p1 2 as the decision threshold. Chernoff's bound states that we should have N ∼ 1 ε 2 repeated Bernoulli trials for the decision test to be relevant, where ε = |p 1 -p 0 | = σ0-σ1 k is the distance between the two outcomes.

To decide whether a particular distance δ is in the spectrum or not, we need to compute the mean of N Bernoulli trials, but each syndrome weight is already the sum of the results of k Bernoulli tests. Hence, we need to observe the weight of N k syndromes. These syndromes need to be in one of the D , this means that the distance δ needs to be in the spectrum of the error pattern that generates the syndrome. As the error patterns are generated uniformly, we proceed by rejection sampling to ensure this condition. The number of vectors of size k and weight w that do not contain a particular distance is w-1 j=0 (k -3j), so neglecting the cases of multiplicity we obtain a good approximation of the frequency of such vectors with:

α := Pr(δ ∈ ∆(e)) ≈ 1 - t 2 -1 j=0 (k -3j) t 2 -1 j=0 (k -j) .
Hence, to decide whether or not δ ∈ ∆(h), we need to observe the decoding of

N α•k syndromes, with N ∼ 1 ε 2 .
As we use the same data to decide for all distances, this is the number of samples needed to recover the whole spectrum.

Attack on the Syndrome Weight

Attack Model. The scenario for our attack is the following. Eve can encrypt random messages using the QC-MDPC scheme described in 2.1 and Alice's public key. She has access to the plaintext but cannot choose the messages. She sends the messages for decryption. Whenever the device decodes a message sent by Eve, she has a way to observe the weight of the syndrome.

The attack we describe here is an abstraction. We do not focus on how, or even if, Eve gets access to the data. It might be possible or not depending on a particular implementation and on the abilities of the attacker. The point is to establish through a simulation that some secret information leaks from the syndrome weight and to compare the cost of that simulation with the theoretical analysis of the previous section.

Eve

Alice's Decoder

m ← IF k 2 e $ ← -IF n 2 , wt(e) = t c = G Alice • m + e Decode(c, H Alice ) : s ← H Alice • c σ σ ← wt(s) . . .
We suppose that Eve's error patterns are randomly generated. Indeed, in the scheme, semantically secure conversions ensure that the error patterns are random [START_REF] Kobara | Semantically secure McEliece public-key cryptosystemsconversions for McEliece PKC[END_REF]. If we allow Eve to choose the error patterns, this will only make the attack easier, as in [START_REF] Guo | A key recovery attack on MDPC with CCA security using decoding errors[END_REF].

Contrary to [START_REF] Guo | A key recovery attack on MDPC with CCA security using decoding errors[END_REF], we collect information from all the error patters, not only those leading to a decoding failure.

Attack on Syndrome Weight. Our goal is to compute the distance spectrum of Alice's private key. For each distance δ between 1 and k 2 we want to decide whether or not δ ∈ ∆(h Alice ). As we have seen in 3.1, for each distance δ ∈ ∆(e), the expected average weight of the syndrome σ = wt(s), where s =

H Alice • c = H Alice • e , is expected to be different if δ ∈ ∆(h Alice ).
Hence, the idea is, for each distance δ, to compute the average value of the syndrome weight σ for error patterns e such that δ ∈ ∆(e). The error patterns are generated randomly and each error e can be used to obtain information on all the distances in its spectrum. This leads to algorithm 7.

Following the discussion in Section 3.1, we will take threshold = σ0+σ1 2 .

Attack on Iteration Count

Now that we know that the syndrome weight leaks information, any parameter correlated to this quantity could be used for a side channel attack. An interesting parameter that is often easy to measure is the number of iterations of a loop. The decoding algorithm for QC-MDPC codes is an iterative algorithm with no termination proof. The number of rounds needed to correct the errors varies. This has been studied by in [START_REF] Chaulet | Worst case QC-MDPC decoder for mceliece cryptosystem[END_REF]. As mentioned in Section 2.2, the algorithm depends on the way we chose the thresholds. For most instances, using fixed or variable thresholds, the algorithm usually corrects the error in 3 rounds, but some instances need 4, 5 or even more iterations. Usual implementations abort after a certain number of rounds (around 10), this is what was used for the attack in [START_REF] Guo | A key recovery attack on MDPC with CCA security using decoding errors[END_REF].

Experimentally, we observe that the correlations between the spectrum of the error and the spectrum of the key has an impact on the average decryption time.

Algorithm 7 Computing the distance spectrum

Input: N the size of the sample, oracle access to the decoder SyndromeCount ← (0, . . . , 0

) ∈ IN k 2 OccurenceCount ← (0, . . . , 0) ∈ IN k 2 ∆ ← (0, . . . , 0) for 0 ≤ i ≤ N -1 do e $ ← -IF n 2 , wt(e) = t σ ← OracleDecoder(e) σ = wt(e • H Alice ) for δ ∈ ∆(e) do SyndromeCount[δ] += σ OccurenceCount[δ] += 1 for 1 ≤ δ ≤ k 2 do if SyndromeCount[δ]/OccurenceCount[δ] < threshold then ∆[δ] ← 1 return ∆
The more distances appear both in spectrum of the error and in the spectrum and the key, the fewer the number of iterations needed to decode on average. This appears clearly on Fig. 3. We note that the correlation is slightly more important on Fig. 3 when we use variable thresholds than with fixed theresholds (the average value is lower for variable thresholds, but the same scale is used for both figures). Fig. 3: Average number of iterations needed for decryption, depending on the size of the intersection of the spectrum of the error and the spectrum of the key. 2 29 samples, 128-bit security QC-MDPC scheme, decoding with fixed thresholds (left) and variable thresholds (right). Note that use of variable thresholds results in stronger correlation. This motivated us to try to perform a theoretical timing attack (algorithm 8). The scenario is the same as previously, but instead of observing the syndrome weight, Eve can measure the number of iterations needed to decode her message.

To obtain the spectrum, Eve uses the exact same data collection algorithm: for every distance in the spectrum, she computes the average number of iterations needed to correct an error containing this distance.

This works well and it is possible to fully recover the distance spectrum with variable thresholds using 2 25 samples on 80-bit security QC-MDPC scheme, 2 25 samples for 128-bit security parameters (see Fig. 6) and 2 28 samples for 256-bit security parameters. For fixed thresholds, we manage to recover the spectrum for 256-bit security with 2 28

Experimental Results

Results of Syndrome attack. The spectrum recovery algorithm was first tried on a simplified version of the scheme using only one block, in order to compare to the expected behaviour. The result is striking. Using the usual parameters for 80-bit security, with one hundred thousand samples, the spectrum appears very clearly and we can even see the multiplicities, that is, distances that appear several times in the key, see Fig. 2. When pushing to one billion samples, there is no room for confusion.

When performing the same experiment on the real QC-MDPC scheme with two blocks, we obtain similar results. The attack is performed on each block separately, that is for each error pattern, we added the syndrome weight to the counters of all distances present in the first half of the error to recover the spectrum of the first block. Because there is no correlation between the two halves of the error pattern, the presence of the second block acts as a random noise added to the syndrome weight. Hence the only difference is that we need more samples to reduce the variance and distinguish well which distances are in the key spectrum. Note that it is possible to compute the spectrum of both blocks at the same time, so there is no need to double the number of samples to recover the second block.

For 80-bit security parameters, we can see on Fig. 4 the spectrum appearing more and more distinctively when we increase the number of samples. With 2 20 samples, we can fully distinguish the spectrum. The same attack requires 2 23 samples for 128-bit security parameters and 2 25 for 256-bit security parameters. This attack was also performed when another error is added to the syndrome, like in the Ouroboros scheme [START_REF] Deneuville | Ouroboros: A simple, secure and efficient key exchange protocol based on coding theory[END_REF] (with an additional error of weight 3d). Again, this only adds random noise and we can recover the spectrum with around a few million samples for the 80-bit security parameters.

Results of iteration attack. After running algorithm 8 we collect data corresponding to the average number of iterations it took to decode an error when d is present. The resulting plots (fig. 5) look very similar to the plots of the decoding failure rate that result from Algorithm 6. Once the bands have completely separated, the distance spectrum (and thus the secret key) can be recovered in the same way it was in the GJS [START_REF] Guo | A key recovery attack on MDPC with CCA security using decoding errors[END_REF] attack.

This side-channel attack is much faster than the reaction attack. An intuitive explanation for the speedup is that differences in the number of iterations are much more common than decoding errors. This allows more information about the correlations to be collected per iteration.

In-place decoder vs. out-of-place decoder

We observed that changes to the decoding algorithm can have a significant impact on the information gathered during the attack.

D 1 uses in-place updates to the syndrome which seems to cause some asymmetry in the errors with respect to distance. For example, in Figure 5 the bands converge as distance increases.

Postponing the updates until the end of each iteration (using B from [START_REF] Von Maurich | Implementing QC-MDPC McEliece encryption[END_REF]) seems to eliminate this asymmetry and reduces the correlation between number of iterations and distance multiplicity. This may reduce the efficiency of the attack.

Figure 7 shows a direct comparison between these two types of decoders. Note that the relationship between number of iterations and multiplicity is inverted between decoders.

We are not sure why this is the case but give a possible explanation for the behaviour. When distances match the resulting behaviour is a decrease in total changes to counters (both correct and incorrect). As noted in [START_REF] Guo | A key recovery attack on MDPC with CCA security using decoding errors[END_REF] this decreases the error rate since it decreases the probability of an incorrect change. It also decreases the expected number of bits flipped which could cause an increase in the expected number of iterations.

When multiple bits are flipped at once in the out-of-place decoder the benefit of a correct flip early in an iteration is removed so it is possible that benefit of early flipping is dominated by the increased chance of an incorrect flip. Fig. 7: Comparison of in-place and out-of-place decoders with fixed thresholds using 30 million iterations against 80-bit security. Decoder definitions are from [START_REF] Von Maurich | Implementing QC-MDPC McEliece encryption[END_REF].

In this section we present ParQ -A KEM constructed from repeating a QC-MDPC encryption scheme in order to eliminate the effect of decoding failures. The general idea is for the ciphertext to include several independent encapsulations of the same key in such a way that the scheme achieves CCA2 security, and so that a decapsulation failure occurs in ParQ only if a decryption failure occurs in every instance of the underlying QC-MDPC scheme. As current estimates for the failure rate indicate that failures occur at a rate of roughly 2 -23 , this suggests that a small amount of parallelization (3 -12×) will make decapsulation failures occur in ParQ at a negligible rate, thus removing the possibility of implementing a reaction attack based on these failures.

ParQ -A Parallelized QC-MDPC KEM

ParQ is largely characterized by the same parameters as other QC-MDPC codebased schemes, specifically, k, the plaintext length, n = 2k, w, the weight of the secret key, and t, the weight of the error. In addition to these parameters, ParQ has the parameter P , denoting the degree of parallelization. P must be greater than or equal to 2, and should generally be chosen to be in the range of 3 -12.

ParQ is described by three algorithms: ParQ.KeyGen for key generation (omitted since it is the same as algorithm 1), ParQ.Enc for encapsulation, and ParQ.Dec for decapsulation. It uses three functions which we model as random oracles, ErrGen, PRF, and KDF, which map onto E, IF k 2 , and {0, 1} λ , respectively.

Algorithm 9 ParQ.Enc

Input: Public key pk, a seed s ∈ {0, 1} k . Output: Session key K, key encapsulation C = (c1, . . . , cP ).

1: for i = 1 to P do 2: Let ei = ErrGen(s||i).

3:

Compute xi = s ⊕ PRF(ei||i).

4:

Compute ci = QCMDPC.Enc(pk, xi, ei). 5: Compute K = KDF(s). 6: Return session key K, key encapsulation C = (c1, . . . , cP ).

Overview of IND-CCA2 reduction for ParQ

For the rest of this section, we show the IND-CCA2 (INDistinguishable under Chosen Ciphertext Attack) security of the ParQ KEM. We show this by reduction from the OW-CPA (One Way under Chosen Plaintext Attack) security of the QC-MDPC McEliece system. We use the standard definitions of IND-CCA2 and OW-CPA security, which can be found in appendix A for completeness.

Algorithm 10 ParQ.Dec

Input: Secret key sk, public key pk, and encapsulation C = (c1, c2, . . . , cP ). Output: Session key K, or decapsulation failure symbol ⊥.

1: for i = 1 to P do 2:

Run (xi, ei) ← QCMDPC.Dec(sk, ci).

3:

if QCMDPC.Dec succesfully decoded for the first time then 4:

Set used index j = i. 5: if QCMDPC.Dec failed to decode for i = 1 to P then 6:

Return decapsulation failure ⊥. 7: Compute s = xj ⊕ PRF(ej||j). 8: Compute K, C = (c 1 , c 2 , . . . , c P ) ← ParQ.Enc(pk, s). 9: if ci = c i for all i ∈ {1, . . . , P } then 10:

Return K. 11: else 12:

Return decapsulation failure ⊥.

Theorem 1. Let A be an adversary capable of winning the IND-CCA2 security game with the ParQ KEM with q d decapsulation queries and q ErrGen , q PRF , and q KDF queries to the random oracles ErrGen, PRF, and KDF respectively, in time t and with advantage . Then there exists a reduction B that uses A as a subroutine by simulating the IND-CCA2 environment in order to break the OW-CPA security of QC-MDPC McEliece, in time ≈ t and with success probability γ( /P -δ), where δ is negligible and γ is negligibly close to 1 in the security parameter.

In order to establish IND-CCA2 security via a reduction from OW-CPA, we need to establish how to embed the given OW challenge c * into an IND challenge (Section 5.4), and how to successfully respond to decapsulation queries (Section 5.5). Then we need to show that the simulation satisfies several key properties: that the simulated challenge is indistinguishable from a real challenge (Section 5.4), that an adversary's ability to solve the IND challenge allows the simulation to solve the OW challenge (Section 5.4), and that the simulated responses to decapsulation queries are indistinguishable from actual responses to a decapsulation query (Section 5.5).

In ParQ, we have that e i = ErrGen(s||i) and x i = s ⊕ PRF i (e i ), or s = x i ⊕ PRF i (e i ). So for any possible c and i, there is at most one s associated with it such that c = QCMDPC.Enc(s ⊕ PRF(ErrGen(s||i)||i), ErrGen(s||i)).

Simulating the Random Oracle

ParQ makes use of three functions that we will model as random oracles -a pseudo random function PRF, an error generation function ErrGen, and a key derivation function KDF. Each random oracle will be maintained by a standard 'on-the-fly' method. For each oracle, a table is maintained specifying which queries have been made and what the responses were. For each oracle, when a query is made, we first check if it has been queried before, and if so, respond with the same response made before. We then specify how to handle new queries.

For new queries to ErrGen of the form s||i we choose a uniformly random error vector e ∈ E. We then also calculate x = s ⊕ PRF(e||i) and add e and c = QCMDPC.Enc(x, e) to the table. We then respond with e.

For new queries to the PRF oracle of the form e||i we first check and see if e is the error vector associated with the challenge ciphertext c * . We do this by using the generator matrix G to see if c * -e is a codeword. If so, then we have solved the challenge. Otherwise, generate a uniformly random string from {0, 1} k , add it to the table and respond.

New queries to KDF can simply be handled by responding with a uniformly random {0, 1} λ .

Challenge Injection

As we are attempting to solve an OW-CPA challenge, we are given a public key G and a ciphertext c * and asked to find the (x * , e * ) such that c * = x * G + e * .

To simulate a challenge, we will first select a uniformly random index j $ ← -{1, . . . , P }. Then, we will select a uniformly random seed s ∈ {0, 1} k . We will run the encapsulation algorithm ParQ.Enc on the seed s, except that we will not query ErrGen(s||j) to generate e j , and thus not generate x j and c j . Thus we will have c 1 , . . . , c j-1 , c j+1 , . . . , c P and K.

To finish the challenge encapsulation, we will select a uniformly random bit b ∈ {0, 1}. If b = 0, we will send K, and if b = 1 we will send a uniformly random K ∈ {0, 1} λ . We will send C = (c 1 , . . . , c j-1 , c * , c j+1 , . . . , c P ) as the encapsulation.

OW Challenge Solution Extraction. We need to show that the adversary's advantage in solving the IND-CCA2 challenge corresponds to an extractor's ability to solve the OW-CPA challenge. Note that the only way for an adversary to distinguish the correct key from an incorrect one is by querying the s associated with each c i to the KDF oracle. Without having done this, the adversary has no information on K and so she has no advantage in distinguishing a proper K from a random one. Therefore, the adversary's advantage in distinguishing corresponds exactly to their ability to query (and thus find) s.

First, we show that the adversary's probability of querying s to KDF without having queried an e i for one of the c i 's to PRF (along with i) is negligibly small. Without having queried some e i to PRF, the plaintext values x 1 , . . . , x p provide no information on s. Recall that s = x i ⊕ PRF(e i ||i). Then (x 1 , . . . , x P ) can be thought of as P maskings of the same value s, with independent masking values. This contains no information about s, unless the adversary has queried at least one e i to PRF.

Similarly, the values (e 1 , . . . , e P ) provide no information about s, unless the adversary queries s||i to ErrGen for some i. This happens with probability at most q ErrGen /2 k . So as long as s is not queried to ErrGen and e i ||i is not queried to PRF, then both (x 1 , . . . , x P ) and (e 1 , . . . , e P ) give no information about s, and so the encapsulation C = (c 1 , . . . , c P ) does not.

So we have shown that unless the adversary queries e i ||i to PRF or s||i to ErrGen (for any i), the encapsulation C = (c 1 , . . . , c P ) actually contains no information whatsoever about s. Therefore, the adversary can only query random seeds to KDF and so the probability that they query s to KDF is at most q KDF /2 k .

If the adversary queries e i ||i to PRF for any i, then they can easily find s and thus break the indistinguishability challenge. But (as we will establish next), since the adversary has not queried s to KDF or s||i to ErrGen, the adversary has no ability to detect which ciphertext c i corresponds to the OW challenge c * . So if the adversary submits an e i to PRF, with probability 1/P , this e i is in fact e * , and we will solve the OW-CPA challenge.

Indistinguishability of Simulated Challenge. When the adversary is given a challenge encapsulation C = (c 1 , . . . , c j-1 , c * , c j+1 , . . . , c P ), along with a possible key K, we need to ensure that they cannot tell that this is not a correctly formatted encapsulation. Other than replacing c j with c * , this is a correct encapsulation. All encapsulations come in the form of P uniform ciphertexts. However a correct encapsulation has the additional property that for each (x i , e i ) associated with a c i , s = x i ⊕ PRF(e i ||i) is the same for all c i , and e i = ErrGen(s||i).

Intuitively, we can see that the only way for an adversary to distinguish between a correctly formatted encapsulation, and one that is generated as in our simulation is by being able to find the (x i , e i ) associated with at least one of the c i , and then checking the other c i through the PRF and ErrGen functions. Formally, if s has not been queried to kdf , s||i has not been queried to ErrGen for any i, and e i ||i has not been queried to PRF for any i, then each x i and e i is indistinguishable from being independently and uniformly generated. As such, the ciphertext is perfectly indistinguishable unless the adversary queries e i ||i to PRF for some i. This event also corresponds to the adversary's ability in solving the IND challenge and is considered in the previous subsection.

Simulating Decapsulation Queries

When we receive a query for decapsulation C = (c 1 , . . . , c P ), we need to respond with the decapsulation K. Upon receiving the query, we lookup the ErrGen table for P queries of the form s||1, s||2, . . . , s||P such that c i is in the table for each s||i. If such a set of P queries is found, we respond with KDF(s). Otherwise, we return the decryption failure symbol ⊥.

We must establish that this simulation is indistinguishable from a real decapsulation oracle. To establish this, we need to show two things: that we do not respond with ⊥ when we should respond with a decapsulated key, and that we do not respond with a decapsulated key when we should respond with ⊥. For the first point, we must ensure that any potential encapsulation query made by the adversary in any way other than by beginning with a seed s and generating each c i according to c i = QCMDPC.Enc(s ⊕ PRF(ErrGen(s||i)||i), ErrGen(s||i)) only results in a ciphertext that would not return ⊥ with negligible probability.

As previously noted, any ciphertext and index pair (c, i) is associated with exactly one seed s induced by s = x⊕PRF(e||i), as there is at most one pair (x, e) associated with c. For the ciphertext to be valid (and thus for a decapsulation oracle to not output ⊥), it must be the case that ErrGen(s||i) = e. So for a decapsulation query C = (c 1 , . . . , c P ), for a correct decapsulation oracle to not return ⊥, each c i must be associated with the same seed s, and for each i, e i = ErrGen(s||i).

When an adversary submits a decapsulation query, if it is not the case that a single s has been queried P times to ErrGen in the form s||1, s||2, . . . , s||P , then there are two possibilities. Either for at least one c i , no query has been made of the form s ||i that results in c i , or such a query has been made but the s is different from one other s.

In the latter case, our simulation would return ⊥, and indeed this is consistent with what an actual decapsulation oracle would return, as each c i is not associated with the same seed, which the decapsulation algorithm can always detect.

In the first case, where s||i has not been queried to generate c i , our simulation will return ⊥. This is usually consistent with what a correct decapsulation oracle will return. The only case an inconsistency would arise is if, when ErrGen(s||i) is later queried, ErrGen(s||i) = e i , despite it not having been queried at the time that the decapsulation query is made. As ErrGen is a random oracle, this only happens with probability at most 1/#E.

Showing that we do not respond with a decapsulation when we should respond with ⊥ corresponds to the fact that we will never have a decoding failure. In a real decapsulation oracle, if a decoding error were to occur for each c i , then we would be forced to respond with ⊥. But in our simulated version, we would respond with the correct decapsulation, as we would have seen it from the random oracle. However, because of the parallelization, we can see that any s will result in errors that will give a total decapsulation failure (i.e. the decoding procedure fail for all e 1 , e 2 , . . . , e P ) with probability ζ P , where ζ is the decoding failure rate. Given this, we need to consider the probability that an adversary queries an encapsulation C that should result in a decapsulation failure. We should note that it should be hard to identify error vectors which will result in decoding failures (or else an adversary may not need to launch the GJS attack at all), but as we have no proof of this, we assume an adversary can perfectly distinguish which error vectors will result in decoding failures.

A fraction ζ P of seeds will result in an encapsulation that cannot be decapsulated. So in q ErrGen queries to the random oracle, the probability that the adversary is able to find such a seed is less than q ErrGen ζ P . We assume that P is chosen so that this quantity is negligible (we discuss this further in Section 5.7).

Combining

We let Game 0 (or G0) refer to the original IND-CCA2 game. We let Game 1 (G1) refer to the simulated IND-CCA2 game, where the challenge and decapsulation oracle are simulated.

To simplify our calculation, we also define three events that can occur in the process of either Game 0 or Game 1.

-Event 1 (or E1) refers to the event that the adversary A queries s to the KDF oracle. -Event 2 (or E2) refers to the event of the adversary A querying one of the e i ||i (from the challenge encapsulation) to PRF prior to querying s to KDF or s||i to ErrGen. -Event 3 (or E3) is the event that the adversary A breaks the distinguishability of the simulated decapsulation oracle. Specifically, that they query an s||i to ErrGen such that ErrGen(s||i) will result in a decoding failure for each i, or that they submit a ciphertext to the decapsulation oracle without querying the associated s to construct it, and that when s is later queried, it does result in the proper error vector, and that they do this prior to Event 1 or 2.

Then, according to the discussion in Sections 5.4 and 5.5, we perform the following calculation:

1 2 + = Pr G0 [A wins] ≤ Pr G0 [A wins|¬E1] + Pr G0 [E1] ≤ 1 2 + Pr G0 [E1]. (2)
This tells us that ≤ Pr G0 [E1]. Next, we consider Pr G0 [E1]:

≤ Pr G0 [E1] ≤ Pr G0 [E2] + Pr G0 [E1|¬E2] ≤ Pr G0 [E2] + q KDF + q ErrGen 2 k . (3)
Next, we relate Pr G0 [E2] to Pr G1 [E2]. This is done simply by noting that

Pr G0 [E2] ≤ Pr G0 [E2|¬E3] + Pr G0 [E3], (4)
and that

Pr

G0 [E2|¬E3] = Pr G1 [E2|¬E3], Pr G0 [E3] = Pr G1 [E3]. (5)
Then finally, noting that our ability to solve the OW-CPA challenge corresponds to 1/P times Pr G1 [E2 ∧ ¬E3], we get that Pr[We win OW-CPA game] ≥

1 P Pr G1 [E2 ∧ ¬E3] = 1 P Pr G0 [¬E3] Pr G0 [E2|¬E3] ≥ 1 P Pr G0 [¬E3] Pr G0 [E2] -Pr G0 [E3] , (6)
and so Pr[We win OW-CPA game] ≥ γ P ( -δ),

where

δ = q ParQ.Dec #E + q KDF + q ErrGen 2 k + q ErrGen ζ P (8)
and γ = 1 -q ParQ.Dec #E -q ErrGen ζ P . (9)

Comparison

In this section we compare aspects of ParQ's efficiency and security with other code-based KEMs, many of which have been submitted to NIST's Post-Quantum Cryptography project [START_REF]NIST post-quantum cryptography project[END_REF]. We restrict ourselves to code-based systems for direct comparison. Comparing code-based systems to other post-quantum systems has been done elsewhere in the literature, for example in [START_REF] Barreto | CAKE: Code-based algorithm for key encapsulation[END_REF]. All comparisons are done considering parameters that have been proposed for 128 bits of post-quantum security, or NIST's security level 5 (AES 256) (see table 1). While we do not have specific data on the speed of ParQ as it compares to other systems, one can expect that, because it requires P encapsulations and the decapsulation must be constant time to avoid side-channel timing attacks, the time to encapsulate and decapsulate likely increases by a factor of roughly P as opposed to a construction like CAKE.

Here we have selected the parameter P to be 12. This reflects the fact that it reduces the decapsulation error rate to be on the order of 2 -252 , presumably hard for even a fully quantum adversary to find a seed that results in a total decapsulation failure (even if the adversary is perfectly able to tell which errors will result in decoding failures, which is presumably hard without the secret key). One could choose P to be much lower, on the order of 2 or 3. While it appears that the GJS attack would be mitigated by these low values of P , (increasing the attack complexity to an estimated 2 66 or 2 87 queries respectively), decapsulation errors may still occur in the normal lifetime of a key, meaning that the guarantees of the CCA2 security proof would not apply. While we have specified that P must be at least 2, note that P could be set to 1. This would cause the scheme to bear some resemblance to the CAKE scheme [START_REF] Barreto | CAKE: Code-based algorithm for key encapsulation[END_REF] or the BIKE-1 scheme [START_REF] Aragon | BIKE -bit flipping key encapsulation[END_REF]. However, this would cause the scheme to be vulnerable to the GJS attack, which is why these schemes currently insist on using the public key ephemerally.

Conclusion and Future Work

We have explored and answered several fundamental questions that arose as a result of the powerful GJS reaction attack on QC-MDPC McEliece. We analyzed the origin of this leak: a bias on the distribution of the syndrome weight. This analysis allows a better understanding of the GJS attack and we deduce other side-channel attacks exploiting all decoding instances.

Our analysis provides quantitative bounds on the minimal number of samples needed to deduce relevant information (using Chernoff's bound), which could be used to deduce better parameters to prevent attacks on the syndrome weight. Other side-channel attacks on different (noisier) parameters exploiting the same idea will be even more costly.

We also discussed how variations in the implemented decoding procedure can affect the attack. Lastly we have showed how decoding failures can be addressed at the protocol level by constructing a KEM that entirely defeats the GJS reaction attack for QC-MDPC, without altering the parameters of the system. We provided a proof of the CCA2 security of the KEM in the random oracle model. Notably, this proof considered the possibility of decoding failures, meaning that it should not be possible to attack the system by exploiting decoding failures.

The security of ParQ is proven in the random-oracle model. A complete and thorough analysis of post-quantum security would require a security reduction in the quantum random-oracle model [START_REF] Boneh | Random oracles in a quantum world[END_REF]. Showing that ParQ (or a small modification of ParQ) is secure in this model would give greater post-quantum assurance.

MDPC codes are still a recent proposal. Even though they are close to the thoroughly studied LDPC codes, they seem to behave differently, in particular as far as decoding is concerned [START_REF] Chaulet | Étude de cryptosystèmes à clé publique basés sur les codes MDPC quasi-cycliques[END_REF]. It is very likely that the state of the art for decoding MDPC codes will evolve quickly, especially considering the NIST call for quantum safe primitives. Interestingly, it seems that more efficient decoders (e.g. those using variable threshold rules) are more prone to information leakage, and thus better decoders might not be safer. Evaluating new decoding algorithm, their failure rates and running time distribution with respect to this work could indicate whether and at what cost QC-MDPC codes could be used for PKEs as safely as for KEMs.

2. 1

 1 Quasicyclic Moderate Density Parity Check McEliece QC-MDPC-McEliece is a public key encryption method consisting of three algorithms. It is defined by four parameters, n, k, w, and t. The key generation algorithm QCMDPC.KeyGen constructs an (n, k)-linear quasicyclic code, consisting of a generator matrix G (the public key) and a parity check matrix H (the secret key), for which each row has weight w. The encryption algorithm QCMDPC.Enc encrypts a plaintext x ∈ IF k 2 by calculating the corresponding codeword to x, xG and adding an error e of weight t to obtain the ciphertext c = e + xG. The decryption algorithm QCMDPC.Dec decodes c back to xG and recovers x.

Input: 1 :

 1 Security parameter 1 λ . Output: Public key pk, secret key sk. Generate h0, h1 ∈ IF k 2 , both with weight w/2. 2: Let H = [H0|H1], where H0 and H1 are k × k matrices generated from h0 and h1 by cyclically rotating them. 3: Set G = [I k |Q], where I k is the k × k identity matrix, Q = (H -1 1 H0) T . 4: return pk = q, the first row of Q and sk = h0, h1. These allow for the reconstruction of G and H. Algorithm 2 QCMDPC.Enc Input: Public key pk = q, plaintext x ∈ IF k 2 , error vector e ∈ E. Output: Ciphertext c ∈ IF n 2 . 1: Reconstruct G = [I k |Q] by cyclically rotating q to obtain Q. 2: return c = e + xG. Algorithm 3 QCMDPC.Dec Input: Secret key sk, public key pk, and ciphertext c ∈ IF n 2 . Output: Plaintext x ∈ IF k 2 and error vector e ∈ E, or decryption failure symbol ⊥. 1: Reconstruct parity-check matrix H = [H0|H1], and generator matrix G = [I k |Q]. 2: Run the decoding procedure on c with parity-check matrix H to recover codeword xG. If a decoding failure occurs, return ⊥. 3: Recover x from the first k bits of xG. 4: Recover e = c -xG. 5: return (x, e).

Fig. 1 :

 1 Fig. 1: Distance spectrum of 100100011 2

Algorithm 6

 6 GJS CCA attack 1: Initialize observed d = 0 and f ailed d = 0 for d ∈ {1, . . . , k/2 }. 2: for i = 1 to M do 3: Send c = QCMDPC.Enc(x, e) with a uniformly random e = [e0||e1] to target. 4: for d ∈ ∆(e0) do 5: Increment observed d by 1. 6: if Decoding failed for c then 7: Increment f ailed d by 1. 8: return f ailed d /observed d for d ∈ {1, . . . , k/2 }.

Fig. 2 :

 2 Fig. 2: Attack on the syndrome weight (1 block): Average syndrome weight per distance, 10 5 samples. The color of the distances indicate their multiplicity in the key spectrum (black = 0, red = 1, blue = 2, green = 3)

Fig. 4 :

 4 Fig. 4: Average syndrome weight per distance, (from left to right, from top to bottom) 2 14 , 2 16 , 2 18 and 2 20 samples, 80-bit security QC-MDPC scheme. The color of the distances indicate their multiplicity in the key spectrum (black = 0, red = 1, blue = 2, green = 3, purple ≥ 4)

Fig. 5 :

 5 Fig. 5: Attack using the number of decoding iterations against parameters for 256-bit security with fixed threshold decoding.

Fig. 6 :

 6 Fig. 6: Attack using the number of decoding iterations, with 2 25 samples, against parameters for 128-bit security QC-MDPC scheme with variable threshold decoding. The color of the distances indicate their multiplicity in the key spectrum (black = 0, red = 1, blue = 2, green = 3, purple ≥ 4)

(

  a) In-place decoder (D1).

  Out-of-place decoder (B).

  samples.

	Algorithm 8 Timing attack on QC-MDPC
	1: Initialize observed d = 0 and iterations d = 0 for d ∈ {1, . . . , k/2 }.
	2: for i = 1 to M do
	3:	e	$ ← -IF n 2 , wt(e) = t
	4:	c ← QCMDPC.Enc(x, e)
	5:	Send c to target.
	6:	n ← number of iterations (from side channel).
	7:	for d ∈ ∆(e0) do
	8:		observed d += 1.
	9:		iterations

d += n. 10: Return iterations d /observed d for d ∈ {1, . . . , k/2 }.

Table 1 :

 1 Length in bytes of keys and encapsulations for Code-Based KEMs. Using 8192128 for Classic McEliece

	Scheme	Public Key	Secret Key	Encapsulation	Static Key Use
	CAKE[5]	8193	8193	8225
	BIKE-1[2]	8188	8188	8188
	BIKE-2[2]	4094	8188	4094
	BIKE-3[2]	9033	9033	9033
	Classic McEliece[6]	1 357 824	14 080	240
	ParQ	4094	8193	98 313

We use the linear approximation unless the quadratic approximation gives different values of bi(σ) = gi(σ) for σ in the observed range.

Supported in part by the Commission of the European Communities through the Horizon 2020 program under project number 645622 (PQCRYPTO).

A Security Definitions and Games

These standard definitions, used in the security proof for ParQ, have been replicated from [START_REF] Dent | A designer's guide to KEMs[END_REF] for the sake of completeness.

The IND-CCA2 and OW-CPA games take place between two parties, the challenger C, and the attacker or adversary, A. We write A's ability to win Game 1 as 1/2 + . We call the adversary's advantage in breaking IND-CCA2 security.

Game 2 (OW-CPA Challenge).

B Choosing the Bit-flipping Thresholds

In standard literature, rules for threshold computation are heuristic and are not available for all parameter sets. To convince that our experiments were fair we describe the rules we used for fixed and variable threshold. We denote d = w/2 the column weight.

Monitoring Strategy: For a given set of parameters, we run the bit-flipping algorithm on many random instances and we choose at each iteration the threshold which minimizes the error weight at the end of all flips 1 . This is possible in a simulation because we know the initial error pattern and we can monitor its evolution. We will refer to this as the "monitoring strategy" and use it as a tool to define the thresholds.

Fixed Thresholds: For a given set of parameters, we run a simulation using the monitoring strategy and we keep track of the threshold values used at the first iteration. The maximum of those values is kept as the fixed threshold, say b 0 , for the first iteration. We run a second simulation, for which the first threshold is fixed to b 0 and the monitoring strategy is used for the following iterations. We keep track of the threshold values used at the second iteration. The maximum of those values is kept as the fixed threshold, say b 1 , for the second iteration. We repeat this until we reach the maximal expected number of iterations.

1 In case of a tie, we choose the smallest threshold, but never smaller than d/2.

Variable thresholds: For a given set of parameters, the goal here is to establish a rule b i (σ), i ≥ 0, giving the i-th iteration threshold as a function of the syndrome weight σ. Assuming all b for < i are known, we run a simulation using the functions b 0 , . . . , b i-1 for the first i iterations and using the monitoring strategy after that. We keep track of the pairs (σ, b) of syndrome weights and threshold values used at the i-th iteration. For each syndrome weight σ, we define f i (σ) as the average of all thresholds observed. Next, using the least square method, we find the quadratic 2 function g i (σ) which best approximates all the (σ, f i (σ)) where each (σ, f i (σ)) is weighted by the number of occurrences of the syndrome weight σ. The threshold function for the i-th iteration will be g i (σ) . We add the condition that b i is increasing with σ and we get b i : σ → max b min i , g i (σ) where b min i is the minimal value of g i (σ) over the observed range for σ, and is never smaller than d/2.

Results and Comments. We give below the threshold rules we used for our simulations deduced from the above-mentioned process. Note that we do not claim, nor observed, that those rules are giving any kind of improvement in speed or failure rate.

Fixed Thresholds. For 80-bit security parameters, (k, w, t) = (4801, 90, 84), we have (b i ) i≥0 = (30, 28, 26, 25, 23, . . . ). The dots meaning that the last value is repeated as much as necessary. We remark that, for the same parameters, QcBits [START_REF] Chou | QcBits: Constant-time small-key code-based cryptography[END_REF] uses thresholds that are exactly one unit lower for the first 4 iterations. This probably reflects the fact that our strategy is rather conservative.

For 128-bit security, (k, w, t) = (10163, 142, 134), we get (b i ) i≥0 = (46, 43, 41, 40, 39, 37, 36, . . . ). Finally for 256-bit security, (k, w, t) = (32771, 274, 264) we obtain (b i ) i≥0 = (83, 80, 77, 74, 72, . . . ).

Variable Thresholds.


Hervé Guillard

Hervé

∇p + ρa 2 div u = 0

Low Mach number flows

Compressible Euler equations :

Low Mach number flows

The acoustic limit Incompressible limit is not the unique low Mach limit of compressible eqs hidden assumption in incompressible asymptotic analysis time scale t * = L * /u * : large time scale choose instead t * = L * /a * : short time scale scaling becomes

                   1 ε ∂ t ρ + div ρu+ = 0 1 ε ∂ t ρu + div ρu ⊗ u + 1 M 2
First example : Low Mach number flows Superposition incompressible + acoustics Asymptotic analysis of the acoustic limit

f = f 0 + M * f 1 + M 2 * f 2 O(1/M 2 * ) : ∇p 0 = 0 O(1/M * )

Slow and fast limits of hyperbolic PDEs

Let W ∈ I R N solution of the hyperbolic system with a large operator

∂ t W + j [A j (W , ε) + 1 ε C j ]∂ x j W = 0 W (0, x, ε) = W 0 (x, ε)
What is the behavior of the solutions when ε → 0 ?

Let n be a arbitrary direction, then some eigenvalues of j n j (A j + 1 ε C j ) are of the form a k + 1 ε c k → ±∞ while the others (kernel of j n j C j ) are simply a k

What is the behavior of the solutions when Slow and Fast waves co-exist ?

Singular limit of hyperbolic PDEs : Slow limit

∂ t W + j A j (W , ε)∂ x j W + 1 ε j C j ∂ x j W = 0 LW = j C j ∂ x j W has to be O(ε)
Look for the solution as W = W 0 + εW 1 with LW 0 = 0, obtain :

∂ t W 0 + j A j (W , ε)∂ x j W 0 + LW 1 = O(ε)
and the solutions converge to W 0 defined by :

LW 0 = 0 ∂ t W 0 + P j A j (W 0 , 0)∂ x j W = 0
P projection on the kernel of L Hervé Guillard Paris, February 1st 2018-10

But the system has also a fast limit

∂ t W + j A j (W , ε)∂ x j W + 1 ε j C j ∂ x j W = 0
Let us do the simple change of variable : t = ετ :

1 ε ∂ τ W + j A j (W , ε)∂ x j W + 1 ε j C j ∂ x j W = 0
and when ε → 0 the limiting form becomes :

∂ τ W + j C j ∂ x j W =
∂ t v + Hv + 1 ε Lv = 0 Notations : v = r u Lv = ∇ • u ∇r Hv = a.
∇v is a constant velocity linear advection operator In Fourier space

∂ v (k) ∂t + i[ Ĥ(k) + 1 ε L (k)]v (k) = 0 for k ∈ Z 2 (1)
where the matrix Ĥ(k) + 1/ε L(k) is equal to :

     a.k k 1 /ε k 2 /ε k 1 /ε a.k 0 k 2 /ε 0 a.k      (2)
Hervé Guillard Paris, February 1st 2018-14

This matrix is diagonalizable, its eigenvectors are :

s 1 (k) = 1 √ 2   1 -k 1 / | k | -k 2 / | k |   , s 2 (k) = 1 | k |   0 -k 2 k 1   , s 3 (k) = 1 √ 2   1 k 1 / | k | k 2 / | k |   (3) with associated eigenvalues λ 1 = a.k - | k | ε , λ 2 = a.k and λ 3 = a.k + | k | ε .
Note : Ls 2 (k) = 0 ;in physical space s 2 (k) corresponds to constant density (∇r = 0) and div free vectors (∇ . u = 0)

Explicit linear example III

v (k, t) =                      1 √ 2 (r (k, 0) - k1 | k | û(k, 0) - k2 | k | v (k, 0))e -i(a.k -|k |/ε)t s1(k) + 1 | k | (-k2 û(k, 0) + k1 v (k, 0))e -ia.k t s2(k) + 1 √ 2 (r (k, 0) + k1 | k | û(k, 0) + k2 | k | v (k, 0))e -i(a.k +|k |/ε)t s3(k)
Hervé Guillard Paris, February 1st 2018-16

Explicit linear example IV

Fast oscillatory component v f (k, t, t/ε) 1 √ 2                        (r (k, 0) - k1 | k | û(k, 0) - k2 | k | v (k, 0))e -i(a.k - | k | ε )t s1(k) + (r (k, 0) + k1 | k | û(k, 0) + k2 | k | v (k, 0))e -i(a.k + | k | ε )t s3(k) (4)
Hervé Guillard Paris, February 1st 2018-17

Explicit linear example V

Slow component belonging to the kernel of L v s (k, τ ) = 1 | k | (-k 2 û(k, 0) + k 1 v (k, 0))e -ia.k t s 2 (k)
This component belongs to the kernel of L and satisfies the incompressible system The wave operator

L LV = ∇ • v ∇p L 2 (Ω) × (L 2 (Ω)) 2 = KerL ⊕ ImL KerL = {(p, v ); p = cte, ∇ • v = 0} ImL = {(p, v ); p = 0, ∃Φv = ∇Φ} Spectrum of L on ImL Let {ψ k , k ≥ 1} the eigenvectors of the Laplace operator -∆ψ k = λ 2 k ψ k λ k > 0
then the eigenvectors of L are :

Φ ± k =    ψ k ± ∇ψ k iλ k    with LΦ ± k = ±iλ k Φ ± k Hervé Guillard Paris, February 1st 2018-23
The solution operator L of the wave equation

Let L(t) be the group (L(t), t ∈ I R) defined by

L(t) = exp(-Lt) (5)
In other words

V (t, x) = L(t)V 0 (x) means that ∂V ∂t + LV = 0 with V (t = 0, x) = V 0 (x)
Using the expression of the spectrum of L we can have an explicit representation of the solution operator L(t) : Let P be the L 2 projection on KerL Expression of the solution at time

t if V (0) = PV (0) + k,± a ± k Φ ± k then V (t) = PV (0) + k,± ±a ± k e ±iλ k t Φ ± k a - k = (a + k ) * conjugate (real functions)
Hervé Guillard Paris, February 1st 2018-24

Step 1 : Filtered variable Ṽ ε

∂t V ε + H(V ε , V ε ) + 1 ε LV ε = O(ε)
introduce the filtered variable

Ṽ ε = L(-t/ε)V ε with L(t) = exp(-Lt)
From the definition of L, we deduce that

∂ Ṽ ε ∂t = L ε Ṽ ε + L(-t/ε) ∂V ε ∂t = L ε Ṽ ε -L(-t/ε)H(L(t/ε) Ṽ ε , L(t/ε) Ṽ ε ) -L(-t/ε) L ε L(t/ε) Ṽ ε + O(ε) = -L(-t/ε)H(L(t/ε) Ṽ ε , L(t/ε) Ṽ ε ) + O(ε)
since L(t/ε) and L commute. Initial data : Ṽ ε (t = 0) = V ε (t = 0) since L(0) is the identity Hervé Guillard Paris, February 1st 2018-25

Limit Equation

Step 2 : Limit Equation for the filtered variable

Ṽ ε ∂ Ṽ ε ∂t + L(-t/ε)H(L(t/ε) Ṽ ε , L(t/ε) Ṽ ε ) = O(ε) Ṽ 0 = lim ε→0 Ṽ ε ∂ Ṽ 0 ∂t + H( Ṽ 0 , Ṽ 0 ) = 0
where H( Ṽ 0 , Ṽ 0 ) = lim ε→0 L(-t/ε)H(L(t/ε) Ṽ 0 , L(t/ε) Ṽ 0 ) is a time-independent operator whose expression can be computed explicitly (see next slides)

Step 3 : Go back to the unfiltered variable V ε

(W Fast , W Fast ) = (v • ∇)v = (v ) j ∂ j v (Lv (t/ε)QV • ∇)Lv (t/ε)QV = { k (a + k e iλ k t/ε -a - k e -iλ k t/ε ) ∇ψ k iλ k } j ∂ j { l (a + l e iλ l t/ε -a - l e -iλ l t/ε ) ∇ψ l iλ l } = k,l
[-a + k a + l e i(λ k +λ l )t/εa - k a - l e -i(λ k +λ l )t/ε ]

1 λ k λ l (∇ψ k ) j ∂ j (∇ψ l ) + k,l
[a - k a + l e i(λ l -λ k )t/ε + a + k a - l e i(λ k -λ l )t/ε ] 1 λ k λ l (∇ψ k ) j ∂ j (∇ψ l ) lim ε→0 (distribution) of all the terms is 0 except when k = l and we get :

(Lv (t/ε)QV • ∇)Lv (t/ε)QV → k [a - k a + k + a + k a - k ] 1 λ 2 k (∇ψ k ) j ∂ j (∇ψ k ) = k |a + k | 2 λ 2 k ∇(|∇ψ k | 2 /2)
On the average (weak limit) fast k-waves interact with l-waves only if k = l and the result is a gradient the result of the interaction between fast waves and slow dynamics is a gradient ! Hervé Guillard Paris, February 1st 2018-28

  ∂t p0 = ∂t p0 = 0 ρ0∂t u0 + ∇p1 = 0 O(1) : ∂ t p 1 + ρ 0 a 2 0 ∇.u 0 = 0 Linear Acoustic equations ρ 0 ∂ t u + ∇p = 0 ∂ t p + ρ 0 a 2 0 div u = 0 Incompressible + Acoustic superposition Very complex answer depending on Initial data well-prepared initial data (initial data "close" to incompressible flow) general initial data State Law barotropic flow (p = p(ρ)) p = p(ρ, s) : the sound speed (at first order ) is NOT a constant Dissipative or not (Euler or NS) Boundary conditions Incompressible + Acoustic superposition Very complex answer depending on Initial data well-prepared initial data (initial data "close" to incompressible flow) general initial data State Law barotropic flow (p = p(ρ)) p = p(ρ, s) : the sound speed (at first order ) is NOT a constant Dissipative or not ( Euler or NS) Boundary conditions

  1st 2018-13 Interaction of fast waves Warm-up : Explicit linear example II Compact form :

  What is the behavior of the solutions when ε → 0 ? For any ε the solution is composed of a superposition of fast and slow waves. Does the solution converge toward something when ε → 0 ?In a point-wise : NO : faster and faster oscillations In a weak sense (average or distribution) YES e part of the solution → 0 and the solutions converge (weakly) toward v 0 that satisfies the incompressible system :

  the limit equation for P Ṽ 0 example : computation of the quadratic term Q

Hervé GuillardParis, February 1st 2018-15

Singular limit of hyperbolic PDEs

Let W ∈ I R N solution of the hyperbolic system with a large operator

What is the behavior of the solutions when ε → 0 ?

How Slow and Fast waves co-exist ? Why do we think that we can split the fast and slow phenomena ?

Is it true also for non-linear systems ?

Can we discard the fast component of the solution ? How to deal with non-linear interactions of the fast waves : non linear system contain quadratic terms e.g :

Can we prove that non-linear interaction of fast waves : Q(W Fast , W Fast ) is not important for the slow dynamics of the system ?

Counter-example : Turbulence and Reynolds stresses ! Hervé Guillard Paris, February 1st 2018-20

Some notations

The variables :

The equations :

) is a non-linear operator (at most quadratic)

LV is the constant coefficient linear operator

The proof strategy S. Schochet, E. Grenier, P.L.Lions-N.Masmoudi, B. Desjardins...

Limit for the original variable

But we have

Final result : weak limit of V ε = P Ṽ 0 that satisfies

Hervé Guillard Paris, February 1st 2018-27

Summary for single phase flows

When it goes well : Weak limit of the solutions of compressible systems :

are the solutions of the incompressible system

where P is the projection on ker(L).

In general for these systems : decoupling between fast waves and slow dynamics Hervé Guillard

Paris, February 1st 2018-29

Some Comments on numerical approximation by upwind schemes

Continous Acoustic operator :

Discrete Acoustic operator :

Hervé Guillard Paris, February 1st 2018-30

Some Comments on numerical approximation by upwind schemes

Discrete Acoustic operator :

can be rewritten :


Céline Coutrix
email: celine.coutrix@imag.fr

Guillaume Rivière
email: g.riviere@estia.fr

Katarzyna Borgiel
email: c.borgiel@estia.fr

Julien Castet
email: julien.castet@gmail.com

Nadine Couture
email: nadine.couture@labri.fr

Brygg Ullmer
email: ullmer@cct.lsu.edu

Jens Geelhaar
email: jens.geelhaar@uni-weimar.de

Patrick Reuter
email: preuter@labri.fr

Nawel Takouachet
email: n.takouachet@estia.fr

Christophe Kolski

Katarzina Borgiel

Sophie Lepreux

Jérémy Legardeur
email: j.legardeur@estia.fr

Sebastien Kubicki
email: sebastien.kubicki@enib.fr

Yvonne Jansen
email: yvonne.jansen@inria.fr

Amira Bouadid
email: amira.bouabid@gmail.com

Methods for Designing Tangible UI: A First Comparative Case Study

Keywords: Tangible User Interfaces, Design Methods, Case Study ACM Classification H.5.m. Information interfaces and presentation (e.g., HCI): Miscellaneous Design, Experimentation

come   L'archive ouverte pluridisciplinaire

Introduction

The design of mixed reality interfaces and TUIs can be driven by different approaches: e.g., by interaction paradigms, interaction models, creativity methods, or special concern for respecting ergonomics and human factors. Alternately, design can be engaged ad-hoc, without a specific formal approach; or by ensembles of multiple approaches. Here, we begin to consider the comparison of such approaches. It is not an easy task for designers to find the appropriate approach for a given design problem. Providing them with a consensual comparison of benefits and drawbacks of each approach can be of important benefit. However, the comparison is a difficult problem as design methods can be compared from many different points of view. Examples include quality of results, ease of understanding by designers, number of alternatives designed, or rapidity of use, to name a few. In this paper we report on experiences from a workshop conducted to compare the results and processes of different design approaches applied on the same topic: creative approach, paradigm-driven approach, interaction model approach, ergonomic approach and free approach. Our aim is to find what differences can appear with different approaches and to see if complementarities can be observed.

Related Works

Experimental comparisons between design approaches are infrequently described in the academic literature. Most related work, like in [START_REF] Jacob | Reality-based interaction: a framework for post-WIMP interfaces[END_REF], compare propositions in a theoretical way with related work.

Another previous work proposed three dimensions from interaction models: descriptive, comparative, and generative power [START_REF] Beaudouin-Lafon | Designing interaction, not interfaces[END_REF]. Generative power is the ability of the model to help design new ideas. These criteria could be used for an experimental evaluation of design approaches, whether model-based or not. For instance, the number or novelty of solutions generated by the approaches could be assessed.

Other works like [START_REF] Myers | Past, present, and future of user interface software tools[END_REF] can inspire additional criteria for the experimental comparison of approaches. For instance, thresholds and ceilings, or the path of least resistance can be assessed, by evaluating the time needed to generate a solution and the limitations of, or the similarities between designed solutions. However, such conceptual criteria have yet to be experimentally applied to methods for designing TUIs. In this paper, we propose a first step for an experimental comparison between different approaches for designing TUIs.

Case Study: Designing for LED lighting

In contrast with traditional lighting technologies, LEDs are smaller and digitally controlled with greater flexibility. Where past lighting systems might contain one or a few light bulbs, future systems may contain many hundreds of LED light sources embedded in the environment. Far beyond simple on/off control, we will be able to control lighting intensity, heat, color, etc. As a consequence, replacing the traditional light switch, the user interface(s) for future LED lighting likely remain(s) to be invented.

As a concrete scenario, we provided participants in a design charrette with a scenario concerning clients for a hotel where rooms are equipped with LED lighting. Figure 1 illustrates a possible setting of the lights of such a room.

We proposed the following tasks for the participants of our workshop to design a TUI for this scenario:  Turn all lights on/off, e.g. when leaving the room  Choose among predefined scenarios, e.g., arriving, night reading, relaxing, sleeping, etc.  Choose a particular LED module to vary its heat/color or its intensity. E.g., customize the intensity of a bedside lamp in order to read textual materials; or change the colors of LED modules in the room to customize the ambiance.



Choose a particular area of the room to be illuminated, e.g., desk, cabinet, etc. The participants were senior researchers, PhD students and post-doctoral researchers, with experience in TUI design or with a long term awareness of TUIs. They came from the HCI field, computer graphics or industrial design.

Prior to designing a TUI by groups, our participants brainstormed in order to agree on criteria for the evaluation of the TUIs for this specific context of the hotel room lighting. During this half hour discussion, we agreed that the interfaces should:

Outcomes of the Workshop by Approaches

Participants were given one hour to sketch a TUI while respecting the scenario's constraints and methodology.

Creative approach

The guideline for this three-person group was to use a creativity method. The team proposed a minimallyintrusive solution using hotel keycard(s) or smartphone(s) and a graphical multi-touch interface integrated in the desk to control the lighting of the room. When the user enters the room, s/he can place the card in an array of slots. Each slot stands for a scenario, e.g., a welcome state, TV watching, sleeping, taking a bath, etc. Each scenario could be customized prior to or during the stay through a web interface, or at check-in. For the better control of the user, common devices, e.g., switches, overrule scenario settings.

Paradigm-driven approach

The constraint of this three-person group was to design a tabletop-based TUI. They proposed a set of tangible tokens representing meaningful groups of lights, e.g., cooking area, living room or child's bed. These tokens could be placed on the surface displaying the controls, e.g., the color space, in order to modify the lighting in the corresponding area. To provide extended control and creativity (in the context of an envisioned trio of child occupants, with their parents residing in a separate room), this approach allowed them to keep control of private areas by hiding tokens, e.g., under a pillow or in a pocket.

Interaction Model approach

This two-person group was requested to use two systematic approaches for exploring the design space: the 7-questions framework described in [START_REF] Couture | Tangible Interaction in Mixed Reality Systems[END_REF] and the Mixed Interaction Model (MIM) [START_REF] Coutrix | An Integrating Framework for Mixed Systems[END_REF]. Numerous solutions were designed with these frameworks, e.g. using a miniature room for pointing at lights and areas, using the keycard of the hotel or using a painting where a color or an ambiance can be selected. By using MIM, they proposed a spherical object with a laser pointer that users can orient and scale up/down in order to point at a target and modify the light intensity of it.

Ergonomic Approach

The main objective of this three-person group was to take into account the user experience of interaction with the future TUI. During the brainstorming they referred to the user experience research framework proposed by Mahlke [START_REF] Mahlke | User Experience of Interaction with Technical Systems. Theories, Methods, Empirical Results, and Their Application to the Design of Interactive Systems[END_REF]. Thus the final solution had not to be only useful and usable, but also aesthetic, symbolic and motivating for its user. This proposal tries to remain close to traditional uses associated to a hotel room assuming that it is generally difficult to change habits. It is therefore not a question of removing switches, for example, but an aesthetic question, focused on relaxation. For this purpose, this is the only group having modified the initial hardware setup. It proposed a ceiling covered with LEDs instead of scattered lighting spots, in order to have a very flexible way to adapt to users. Firstly, about displacements in the room, the user can draw lines on a tablet computer, associated to various times of the day, that are reproduced on the ceiling by the LEDs. Secondly, in the bathroom, they imagined a metaphor with bath salts that control the color of light. Small plates with colored bath salts are provided around the bath, the user pours salts in the bath or in a cup, and in function of the lack of salts in each small plate the light is adapted in the bathroom. Then, they are complying with the use of salt in a bathroom; the bath salts retain their first function but the proposal enhances its main objective: the relaxation.

Free approach

As a baseline, we had a four-person group working with no constraints or guidelines, except the tangible criteria. In fact, the group first generated ideas individually. Then they confronted their ideas to converge to a final design.

They proposed a personal object called Magic Light, given by the hotel to the customer. This object could be the keycard or a dedicated magic wand. First, the user points towards its target. Then s/he gestures from there, in opposite directions to turn on/off the light. S/he can gesture perpendicularly to change the color of the light. In addition, s/he can use a magic gesture, e.g., bump the wand, in order to retrieve its personal favorite light settings. A skin conductivity sensor is used on the wand to set the light according to the affective state of the user.

Discussion

This very first experience of comparison of methods for designing TUIs leads us to notice interesting facts. Note that our work is in its first steps and we do not wish to present them as final results, but would rather like to discuss them, and our experience, with the TEI conference attendees. The final aim is to reach a consensual comparison of benefits and drawbacks of each approach, as such a consensual result could highly benefit to designers. First, we had two kinds of approaches: instrumented with a framework, e.g. the ones from [START_REF] Couture | Tangible Interaction in Mixed Reality Systems[END_REF], [START_REF] Coutrix | An Integrating Framework for Mixed Systems[END_REF] or [START_REF] Mahlke | User Experience of Interaction with Technical Systems. Theories, Methods, Empirical Results, and Their Application to the Design of Interactive Systems[END_REF], and the approaches that were not instrumented, like the free or paradigm-driven approaches. We noticed that the participants applying a framework had to learn the framework beforehand if they were not already expert of it, in addition to relying on the designers' experience of TUIs like the free or paradigm-driven approaches. The high threshold [START_REF] Myers | Past, present, and future of user interface software tools[END_REF] of the frameworks is a drawback, but we envisioned that, as a consequence, the results of the design were less dependent on the participants' individual skills and could be more easily repeated.

Second, the participants using interaction models were the only ones providing with several alternatives. Providing with as many alternatives as possible was not an instruction, but it is the aim of these methods to explore the design space in a systematic way, making it easier to design different solutions. We noticed as well that this approach leads to solutions that remind some elements from other approaches, like the picture or the keycard, even though the design was not as detailed because of the limited time. As a consequence, these approaches can be good candidates for generation phases [START_REF] Beaudouin-Lafon | Designing interaction, not interfaces[END_REF].

Third, the solution from the paradigm-driven approach was the only one to provide support for multiple users and to deal with possible conflicts between them. We explain this feature by the fact that the paradigm constraint, i.e. the tabletop, is an opportune one for multiple users to interact. The other approaches more naturally lead to a tangible object targeting a single user.

Fourth, two of the approaches allowed using current switches for turning on and off the lights, in addition to new interactions: the ergonomic approach and the creative approaches. Indeed, the study of existing solutions is part of these two approaches, on the contrary to other approaches where this is left to the designers' initiative. As a consequence, these approaches can be good candidates for designing a TUI where a lot of related interfaces already exist.

Finally, our aim was to take a first step towards the evaluation of the approaches' ability to lead to good solutions. For this, following the design session, the participants proposed a common, rough evaluation of the interfaces produced. This very early result will have to be repeated across several design sessions in order to be confirmed.

Creative approach

Paradigmdriven approach

Interaction model approach

Ergonomic approach

Free approach

Provide emotional feeling

Yes Yes

Take into account the number of people

Yes

Be easy to use Yes Yes As one can notice in Table 1, none of the approaches were able to comply all the criteria in such a short time (one hour). It would be interesting to provide a longer time for the participants so that they are able to exploit the full potential of their method.

Adapt to the user's profile

Future Work

This work is a first step towards an experimental comparison of methods for designing TUIs. In this first experience, the results cannot be generalized yet due to the correlation to individual designers' skills. The next step of this work is to conduct more workshops of this kind in order to vary designers so that the comparison can be generalized. For instance, a next step after more workshops could assess the path of least resistance of the approaches, independently of the designers' individual specificities.

We also noted that the creative approach was only partially followed. However, this could happen to any approach. A way to improve this limitation could be to have an external group leader or a physical support guiding the process, ensuring that the group follows the assigned approach.

Moreover, an ongoing work is to integrate the use of more frameworks for designing TUIs, like RBI [START_REF] Jacob | Reality-based interaction: a framework for post-WIMP interfaces[END_REF] or TAC [START_REF] Shaer | The TAC Paradigm: Specifying Tangible User Interfaces[END_REF].

Figure 1 .

 1 Figure 1. Hotel room equipped with simple LED lighting.



  Take into account the number of people/users  Be easy to use  Adapt to the user's profile  Offer good affordances  Be able to transition between contexts  Provide flexibility  Be secure for the user/the hotel  Take cost into account  Support tasks presented  Provide control for hotel staff  Support emotional feeling, e.g. change in valence and arousal dimension of emotion [5].

able to transition between context Yes Yes Provide flexibility Yes Be secure for the user/the hotel Yes Take cost into account

		Yes	Yes		Yes	Yes
	Offer good affordances	Yes		Yes	Yes	Yes
	Be Yes		Yes		Yes
	Cover tasks presented	Partially	Partially	Partially	Partially	Partially
	Provide control for the staff		Yes

Table 1 :

 1 Assessing evaluation criteria to the solutions produced.

Acknowledgements

French

Speaking Human-Computer Interaction Association (AFIHM), French Speaking working group about tangible interaction TANGINT/FR, French DELight collaborative project.