domain: info math

text:
Nicolas Aragon

consideration for standardization or withdrawn from consideration by all submitter(s) and owner(s), I understand that rights granted and assurances made under Sections 2.D.1, 2.D.2 and 2.D.3, including use rights of the reference and optimized implementations, may be withdrawn by the submitter(s) and owner(s), as appropriate.

Prologue

The public key encryption protocol NTRU [START_REF] Hoffstein | NTRU: A ring-based public key cryptosystem[END_REF] was introduced in 1998, the main idea behind the protocol is that the secret key consists in the knowledge of a small Euclidean weight vector, which is used to derive a double circulant matrix. This matrix is then seen as a dual matrix of an associated lattice and a specific decoding algorithm based on the knowledge of this small weight dual matrix is used as decryption.

This idea of having as a trapdoor, the knowledge of a small weight dual matrix (with a specific associated decoding algorithm) can naturally be generalized to other metrics. It was done in 2013 with MDPC [START_REF] Misoczki | MDPC-McEliece: New McEliece variants from moderate density parity-check codes[END_REF] for Hamming metric and also in 2013 for Rank metric with LRPC codes [START_REF] Gaborit | Low rank parity check codes and their application to cryptography[END_REF]. These three protocols derive from the same basic main idea, adapted for different metrics, which have different properties in terms of efficiency, size of parameters and security reduction.

In this proposal we build on a small variation of the LRPC rank metric approach, by introducing Ideal-LRPC codes, and propose an IND-CPA Key Encapsulation Mechanism (KEM) for Key Exchange, efficient in terms of size of parameters and computational complexity which benefits from the nice properties of rank metric. The scheme has a failure probability but this probability is well understood and can be made very low.

Specifications

In the following document, q denotes a power of a prime p. The finite field with q elements is denoted by F q and more generally for any positive integer m the finite field with q m elements is denoted by F q m . We will frequently view F q m as an m-dimensional vector space over F q .

We use bold lowercase and capital letters to denote vectors and matrices respectively. We will view vectors here either as column or row vectors. It will be clear from the context whether it is a column or a row vector. For two matrices A, B of compatible dimensions, we let (A|B) and A B respectively denote the horizontal and vertical concatenations of A and B.

Presentation of rank metric codes

1.1.1 General definitions Definition 1.1 (Rank metric over F n q m ). Let x = (x 1 , . . . , x n ) ∈ F n q m and (β 1 , . . . , β m ) ∈ F m q m a basis of F q m viewed as an m-dimensional vector space over F q . Each coordinate x j is associated to a vector of F m q in this basis: x j = m i=1 m ij β i . The m × n matrix associated to x is given by M (x) = (m ij ) 1 i m

1 j n .
The rank weight x of x is defined as

x def = Rank M (x).
The associated distance d(x, y) between elements x and y in F n q m is defined by d(x, y) = xy . Definition 1.2 (F q m -linear code). An F q m -linear code C of dimension k and length n is a subspace of dimension k of F n q m embedded with the rank metric. It is denoted [n, k] q m . C can be represented by two equivalent ways:

• by a generator matrix G ∈ F k×n q m . Each rows of G is an element of a basis of C,

C = {xG, x ∈ F k q m }
• by a parity-check matrix H ∈ F

(n-k)×n q m

. Each rows of H determines a parity-check equation verified by the elements of C:

C = {x ∈ F n q m : Hx T = 0}
We say that G (respectively H) is under systematic form iff it is of the form (I k |A) (respectively (I n-k |B)).

Definition 1.3 (Support of a word). Let x = (x 1 , . . . , x n ) ∈ F n q m . The support E of x, denoted Supp(x), is the F q -subspace of F q m generated by the coordinates of x: E = x 1 , . . . , x n Fq and we have dim E = x .

The number of supports of dimension w of F q m is denoted by the Gaussian coefficient m w q =

w-1 i=0 q m -q i q w -q i

Double circulant and ideal codes

To describe an [n, k] q m linear code, we can give its systematic generator matrix or its systematic parity-check matrix. In both case, the number of bits needed to represent such a matrix is k(n-k)m log 2 q . To reduce the size of a representation of a code, we introduce the double circulant codes. First we need to define the circulant matrices. We denote M n (F q m ) the set of circulant matrices of size n × n over F q m .

The following proposition states an important property of circulant matrices.

Proposition 1.5. M n (F q m ) is an F q m -algebra isomorphic to F q m [X]/(X n -1), that-is-tosay the set of polynomials with coefficients in F q m modulo X n -1. The canonical isomorphism is given by

ϕ : F q m [X]/(X n -1) -→ M n (F q m ) n-1 i=0 m i X i -→      m 0 m 1 . . . m n-1 m n-1 m 0 . . . m n-2 . . . . . . . . . . . . m 1 m 2 . . . m 0     
In the following, in order to simplify the notation, we will identify the polynomial G(X) = n-1 i=0 g i X i ∈ F q m [X] with the vector g = (g 0 , . . . , g n-1 ) ∈ F n q m . We will denote ug mod P the vector of the coefficients of the polynomial n-1 j=0 u j X j n-1 i=0 g i X i mod P or simply ug if there is no ambiguity in the choice of the polynomial P . Definition 1.6 (Double circulant codes). An [2n, n] q m linear code C is said double circulant if it has a generator matrix G of the form G = (A|B) where A and B are two circulant matrices of size n.

With the previous notations, we have

C = {(xa, xb), x ∈ F n q m }. If a is invertible in F q m [X]/(X n -1), then C = {(x, xg), x ∈ F n q m } where g = a -1 b.
In this case we say that C is generated by g ( mod X n -1). Thus we only need nm log 2 q bits to describe an [2n, n] q m double circulant code.

We can generalize the double circulant codes by choosing another polynomial P to define the quotient-ring F q m [X]/(P ). Definition 1.7 (Ideal codes). Let P (X) ∈ F q [X] be a polynomial of degree n and

g 1 , g 2 ∈ F n q m . Let G 1 (X) = n-1 i=0 g 1i X i and G 2 (X) = n-1
j=0 g 1j X j the polynomials associated respectively to g 1 and g 2 .

By definition, the [2n, n] q m ideal code C of generator (g 1 , g 2 ) is the code with generator matrix

G =      G 1 (X) mod P G 2 (X) mod P XG 1 (X) mod P XG 2 (X) mod P . . . . . . X n-1 G 1 (X) mod P X n-1 G 2 (X) mod P     
More concisely, we have C = {(xg 1 mod P, xg 2 mod P ), x ∈ F n q m }. We will often omit to precise the polynomial P if there is no ambiguity.

If

g 1 is invertible, under systematic form, C = {(x, xg), x ∈ F n q m } with g = g -1 1 g 2 mod P .

Relation between polynomial and matrix forms for the syndrome computation

We need to be careful when we use these notations in the case of parity-check matrix. Indeed, if we have a syndrome σ = e 1 h 1 + e 2 h 2 mod P , this equality is equivalent in term of product matrix-vector to

(H 1 |H 2 )(e 1 |e 2 ) T = σ T where H 1 =      h 1 mod P Xh 1 mod P . . . X n-1 h 1 mod P      T and H 2 =      h 2 mod P Xh 2 mod P . . . X n-1 h 2 mod P     
T Thus, we said that (h 1 , h 2 ) and P generate a parity-check matrix of a code

C if (H T 1 |H T 2 ) is a parity-check matrix of C.

Difficult problems in rank metric

In this section, we introduce the difficult problems on which our cryptosystem is based.

Problem 1.8 (Rank Syndrome Decoding). Given a full-rank matrix H ∈ F (n-k)×n q m
, a syndrome σ and a weight ω, it is hard to sample a vector x ∈ F n q m of weight lower than ω such that Hx T = σ T .

The RSD problem has recently been proven hard in [6] on probabilistic reduction. Problem 1.9 (Ideal-Rank Syndrome Decoding). Given a vector h ∈ F n q m , a polynomial P ∈ F q [X] of degree n, a syndrome σ and a weight ω, it is hard to sample a vector x = (x 1 , x 2 )F 2n q m of weight lower than ω such that x 1 + x 2 h = σ mod P .

Since h and P define a systematic parity-check matrix of an [2n, n] q m ideal code, the I -RSD problem is a particular case of the RSD problem. Problem 1.10 (Ideal-Rank Support Recovery). Given a vector h ∈ F n q m , a polynomial P ∈ F q [X] of degree n, a syndrome σ and a weight ω, it is hard to recover the support E of dimension lower than ω such that e 1 + e 2 h = σ mod P where the vectors e 1 and e 2 were sampled from E.

The I -RSR problem is trivially reduced to the I -RSD problem. Indeed to recover the support E of an instance of the I -RSD problem from a solution x of the I -RSD problem, we just have to compute the support of x.

Reciprocally, the I -RSD problem can also be reduced to the I -RSR problem. Let us suppose we know the support E of a solution of the I -RSR problem for a weight ω. We want to find x = (x 1 , x 2 ) of weight lower than ω such that

x 1 + x 2 h = σ mod P .
This equation is equivalent to

  I n H   (x 10 . . . x 1,n-1 , x 20 . . . x 2,n-1 ) T = σ T (1)
where

H =      h Xh mod P . . . X n-1 h mod P      T and x 1 = (x 10 . . . x 1,n-1 ), x 2 = (x 20 . . . x 2,n-1 ).
Let (E 1 , . . . , E ω ) be a basis of E. We can express the coordinates of x 1 and x 2 in this basis:

∀i ∈ {1, 2}, 0 j n -1, x ij = ω k=1 λ ijk E k , with λ ijk ∈ F q
Then we rewrite the equations 1 in the new unknowns λ ijk . We obtain a system of 2nω unknowns over F q and n equations over F q m , so nm equations over F q .

Since e 1 + e 2 h = σ mod P , the system has at least one solution and by construction all the solutions have their support included in E of dimension ω, so we can find a solution the I -RSD problem by solving this system.

Even if there is no reduction proof as for the generic RSD problem, the ideal (and quasicyclic double circulant) versions of the RSD problem are considered hard. The situation is similar to Hamming and Euclidean metrics for double circulant codes, for which there is known strong improvement on the attack complexity whenever one avoids weak keys, typically choosing a polynomial P with many small factors: in our case P is chosen irreducible. The complexity of known attacks against these problems are described in Section 5.

The Low Rank Parity Check codes

Definition

The LRPC codes have been introduced in [START_REF] Gaborit | Low rank parity check codes and their application to cryptography[END_REF]. They are good candidates for the cryptosystem of McEliece because the have a weak algebraic structure.

Definition 1.11 (LRPC codes). Let H

= (h ij ) 1 i n-k 1 j n ∈ F (n-k)×n q m
a full-rank matrix such that its coefficients generate an F q -subspace F of small dimension d:

F = h ij Fq
Let C be the code with parity-check matrix H. By definition, C is an [n, k] q m LRPC code of weight d.

Such a matrix H is called homogeneous matrix of weight d and support F .

We can now define the ideal LRPC codes as we have defined the ideal codes.

Definition 1.12 (Ideal LRPC codes). Let F be a F q -subspace of dimension d of F q m , (h 1 , h 2 ) two vectors of F n q m of support F and P ∈ F q [X] a polynomial of degree n. Let

H 1 =      h 1 Xh 1 mod P . . . X n-1 h 1 mod P      T and H 2 =      y Xh 2 mod P . . . X n-1 h 2 mod P      T By definition, the code C with parity check matrix H = (H 1 |H 2 ) is an ideal LRPC code of type [2n, n] q m .
As we can see, since P ∈ F q [X], the support of X i h 1 is still F for all 1 i n -1 hence the necessity to choose P with coefficients in the base field F q to keep the LRPC structure of the ideal code.

To hide the structure of an ideal LRPC, we only reveal its systematic parity-check matrix.

Definition 1.13 (Ideal LRPC codes indistinguishability). Given a polynomial P ∈ F q [X] of degree n and a vector h ∈ F n q m , it is hard to distinguish whether the ideal code C with the parity-check matrix generated by h and P is a random ideal code or if it is an ideal LRPC code of weight d.

In other words, it is hard to distinguish if h was sampled uniformly at random or as x -1 y mod P where the vectors x and y have the same support of small dimension d.

The ideal LRPC codes are particularly interesting if we choose an irreducible polynomial for P . In this case we counter a structural attack against double circulant LRPC which can be found in [7].

A support recovery algorithm

The decoding algorithm of LRPC codes first recover the support of the error vector then solve a linear system in order to recover the error coordinates. For our protocol LAKE we only need to recover the support of the error. The probabilistic support recovery algorithm was recently improved in [START_REF] Aragon | More on lrpc codes and their cryptographic applications[END_REF]. The algorithm we present here, uses both the general decoding algorithm of the LRPC codes described in [START_REF] Gaborit | Low rank parity check codes and their application to cryptography[END_REF] and a tweak of the improved algorithm described in [START_REF] Aragon | More on lrpc codes and their cryptographic applications[END_REF] designed to run in constant time.

Notation 1.14. In the following, S is the vector space generated by the coordinates of the syndrome s 1 , ..., s n . Its dimension is at most rd, and it is a subspace of the product vector space E.F = E 1 .F 1 , E 2 .F 1 , ..., E r .F d . S i is defined by S i = F -1 i .S with F i an element of a basis of F , and S ij = S i ∩ S j .

Algorithm

Algorithm 1: Rank Support Recover algorithm (RS-Recover)

Data:

F = F 1 , ..., F d , s = (s 1 , • • • , s n ) (a vector),

r (the dimension of E)

Result: A candidate for the vector space E //Part 1 : Compute the vector space E.F

1 Compute S = s 1 , • • • , s n 2 Precompute every S i for i = 1 to d 3 Precompute every S i,i+1 for i = 1 to d -1 4 for i from 1 to d -2 do 5 tmp ← S + F.(S i,i+1 ⊕ S i+1,i+2 ⊕ S i,i+2 ) 6 if dim(tmp) rd then 7 S ← S ∪ tmp 8 end 9 end
//Part 2 : Recover the vector space

E 10 E ← F -1 1 .S ∩ ... ∩ F -1 d .S 11 return E
The algorithm is designed in two parts : the first one is used to recover the whole vector space E.F in case S is of dimension < rd. This ensures that the second part, which is the general decoding of the LRPC codes, outputs the right E. Note that we don't need to recover the coordinates of the error vector e since we only use the support E in the protocol.

Probability of failure

The second part of the algorithm will fail if and only if S = E.F , thus the global probability of failure depends both from the probability of dim(S) being smaller than rd and the probability of not recovering E.F using the first part of the algorithm. Notation 1.15. In the following, c is the codimension of S inside E.F : dim(S) = rd -c. P (c = i) is the probability of S being of codimension i inside E.F and P c=i (f ailure) if the probability of not recovering E.F when c = i. This algorithm uses the fact that dim(S i ∩ E) >= r -c (r -1 in this case), which means each S i contains at least r -1 vectors of E. Since all other vectors in S i are random, we need to intersect two different S i in order to recover r -2 vectors of E : those are the S ij .

At each iteration, we compute S i,i+1 ⊕ S i+1,i+2 ⊕ S i,i+2 to find vectors of E. Once we have those, we multiply them by the vector space F to find vectors of S. If one of these vectors (we note it x) is not in S, then S + x = E.F : we can decode successfully.

We know that every S ij contains at least r -2 vectors of E.

To study what happens during each iteration of the algorithm, we suppose that S ij contains exactly r -2 vectors of E. Two cases may occur during each of the d -2 iterations :

• If S i,i+1 = S i+1,i+2 , then dim(S i,i+1 ⊕ S i+1,i+2 ⊕ S i,i+2 ) = r -2,
since the equality implies that each vector that we find is in S i , S i+1 and S i+2 at the same time. In that case the algorithm might not find new vectors of E.F . This equality happens with probability q 2-r .

• S i,i+1 = S i+1,i+2 , then dim(S i,i+1 ⊕ S i+1,i+2 ⊕ S i,i+2 ) = r : the inequality implies that dim(S i,i+1 ⊕ S i+1,i+2 ) = r -1 and, since S i,i+2
is different from both of the other S ij (otherwise we would be in the first case), the union of the three S i j is exactly E. In that case the algorithm always finds E.F .

Since each iteration can fail to recover E.F with probability q 2-r , the probability of not finding E.F when dim(S) = rd -1 is q (2-r)(d-2) . Proposition 1.17. From [START_REF] Gaborit | Low rank parity check codes and their application to cryptography[END_REF] we know that P (c = i) = q -i(n-rd+i) thus the probability of failure of this algorithm is max(q (2-r)(d-2) × q -(n-rd+1) , q -2(n-rd+2) .

In practice, this algorithm can decode event when c > 1, but P c=2 (f ailure) is harder to study. Notice that the algorithm supposes that m is sufficiently higher than 2rd -r to work, which is be the case for all parameters considered.

LAKE an IND-CPA KEM based on rank metric

KEM: definition and security model

A Key-Encapsulation scheme KEM = (KeyGen, Encap, Decap) is a triple of probabilistic algorithms together with a key space K. The key generation algorithm KeyGen generates a pair of public ad secret key (pk, sk). The encapsulation algorithm Encap uses the public key pk to produce a encapsulation c, and a key K ∈ K. Finally Decap using the secret key sk and an encapsulation c, recovers the key K ∈ K or fails and return ⊥.

We define IND-CPA-security of KEM formally via the following experiment, where Encap 0 returns a valid key pair c * , K * , while Encap 1 return a valid c * and a random K * .

Indistinguishability under Chosen

Plaintext Attack : This notion states that an adversary should not be able to efficiently guess which key is encapsulated.

Exp ind-b E,A (λ) 1. param ← Setup(1 λ ) 2. (pk, sk) ← KeyGen(param) 3. (c * , K * ) ← Encap b (pk) 4. b ← A(GUESS : c * , K * ) 5. RETURN b Definition 1.18 (IND-CPA Security). A key encapsulation scheme KEM is IND-CPA-secure if for all PPT adversary A, Adv indcpa KEM (A) := | Pr[IND-CPA A real ⇒ 1] -Pr[IND-CPA A rand ⇒ 1]| is negligible.

Description of the scheme

Our scheme contains a hash function G modeled as a ROM.

• KeyGen(1 λ ):

choose an irreducible polynomial P ∈ F q [X] of degree n.

choose uniformly at random a subspace F of F q m of dimension d and sample a couple of vectors (x, y) $ ← F n ×F n such that x is invertible mod P , Supp(x, y) = F .

compute h = x -1 y mod P .

define pk = (h, P ) and sk = (x, y).

• Encap(pk):

choose uniformly at random a subspace E of F q m of dimension r and sample a couple of vectors (e 1 , e 2 )

$ ← E n × E n with Supp(e 1 , e 2 ) = E.
compute c = e 1 + e 2 h mod P .

define K = G(E) and return c.

• Decap(sk):

compute xc = xe 1 + ye 2 mod P and recover E with the support recovery algorithm of previous section.

- We need to have a common representation of a subspace of dimension r of F q m . The natural way is to choose the unique matrix M ∈ F r×m q of size r × m in its rows echelon form such that the rows of M are a basis of E.

recover K = G(E). Alice Bob choose random F of dimension d (x, y) $ ← F n × F n s.t. x invertible mod P Supp(x, y) = F, h ← x -1 y mod P xc = xe 1 + ye 2 mod P E ← RS-Recover(F, xc, r) G (E) h -----→ c ← ----- Shared Secret choose random E of dimension r (e 1 , e 2 ) $ ← E n × E n , Supp(e 1 , e 2 ) = E c = e 1 + e 2 h mod P G (E)
We deal with the semantic security of the KEM in Section 4.

Correctness: since P is in F q [X],
xc has a support in the product space E.F . Hence knowing F , one can apply the RS-Recover algorithm of the previous section which recovers E.

Computational costs. The Encapcost corresponds to a polynomial inversion mod P in F q m , for a multiplication cost of elements of F q m in m log(m) log(log(m)), we obtain an encryption complexity in O (n 2 log(n)m log (m) log (log (m))). The Decapcost is a matrixvector multiplication of cost O (n 2 m log (m) log (log (m))) plus the decoding cost of the RS-Recover algorithm (intersections of subspaces of dimension rd in F q m ) in O((rd) 2 m).

Parameters

In this section, we give some sets of parameters for a security parameters of 128, 192 and 256 corresponding to NIST security levels 1, 3 and 5 respectively. In all cases, we have chosen q = 2. The parameters are :

• n is the length the vectors h and c sent on the public channel.

• m is the degree of the extension F 2 m .

• d is the weight of the ideal LRPC code used in the protocol.

• r is the weight of the error.

• P is the irreducible polynomial of degree n of F 2 [X] which defines the ideal LRPC code. We have chosen sparse polynomials in order to diminish the computation costs.

• the structural attack parameter is the logarithm in basis 2 of the complexity of the best attack to recover the structure of the ideal LRPC code. It consists in looking for a codeword of weight d in an ideal LRPC of type [2n, n] 2 m defined by the parity-check matrix (I n |H) where

H =      h(X) mod P Xh(X) mod P . . . X n-1 h(X) mod P     
• the generic attack parameter is the logarithm in basis 2 of the complexity of the best attack to recover the support E. It consists in solving the I -RSDproblem for a random ideal code of type [2n, n] 2 m and an error of weight r.

• p f is the probability of failure of the decoding algorithm. We have chosen the parameters such that the theoretic upper bound is below 2 -30 .

• the entropy parameter is the entropy of the subspace E. It is equal to log 2 m w q and have to be greater than the security parameter. We represent E by a matrix of size w × m in its row echelon form.

• the public key size is the number of bits needed to represent the public key h ∈ F n q m . It is equal to mn.

Name

Performance Analysis

In this section, we provide concrete timings of our implementations. The benchmarks were performed on an Intel R Core TM i7-4700HQ CPU running @ up to 3.40GHz and the software was compiled using GCC (version 6.3.0) with the following command : g++ -O2 -pedantic -Wall -Wextra -Wno-vla.

Reference Implementation

Tab. 1 gives timings (in ms) of the reference implementation on our benchmark platform, and Tab.

Optimized Implementation

No optimized implementation has been realized. Therefore, the folder ../Opti-mized_Implementation/ is a copy of ../Reference_Implementation/.

Known Answer Test Values

KATs are provided in the folder ../KATS/Reference_Implementation/.

As mentioned in Sec.

2.2, since the reference and optimized implementations are identical, ../KATS/Optimized_Implementation/ is just a copy of ../KATS/Reference_Implementation/.

KATs have been generated using the script provided by NIST. They are available under the folder labeled "KATs". Additionally, we provide a complete example with intermediate values in the KATs folder. This complete example corresponds to a successful run of LAKE. By successful, we mean that no decryption error occurred in the Decapsulation step.

Notice that one can also generate other such detailed instances using the verbose mode of each implementation.

For instance, use make lakeI-verbose in ../Reference_Implementation/LAKE-I/, then run ./bin/lakeI-verbose to get a complete detailed instance with intermediate values.

Security

Theorem 4.1. Under the Ideal LRPC indistinguishability 1.13 and the Ideal-Rank Syndrome Decoding 1.9 Problems, the KEM presented earlier in section 1.5.2 is indistinguishable against Chosen Plaintext Attack in the Random Oracle Model.

Proof. We are going to proceed in a sequence of games. The simulator first starts from the real scheme. First we replace the public key matrix by a random element, and then we use the ROM to solve the Ideal-Rank Support Recovery.

• Game G 0 is the regular scenario: We generate the public key h honestly, and E, c also.

• In game G 1 , we now replace h by a random vector, the rest is identical to the previous game. From an adversary point of view, the only difference is the distribution on h, which is either generated at random, or as a product of low weight vectors. This is exactly the Ideal LRPC indistinguishability problem, hence

Adv G 0 A ≤ Adv G 1 A + Adv I-LRPC A
• In game G 2 , we now proceed as earlier except we receive h, c from a Support Recovery challenger. After sending c to the adversary, we monitor the adversary queries to the Random Oracle, and pick a random one that we forward as our simulator answer to the Ideal-Rank Support Recovery problem. Either the adversary was able to predict the random oracle output, or with probably 1/q G , we picked the query associated with the support E (by q G we denote the number of queries to the random oracle G), hence

Adv G 1 A ≤ 2 -λ + 1/q G • Adv I-RSR A .
Since we saw in Sec. 1.2 that the problems I -RSR and I -RSD were equivalent it leads to the conclusion.

Known Attacks

There are two ways to attack our system: either the opponent can try to recover the structure of the ideal LRPC code by searching a codeword of weight d in the ideal code generated by h, or he can try to solve an instance of the I -RSR 1.10 problem of weight r for a random ideal code.

There exist two types of generic attacks on these problems:

• the combinatorial attacks where the goal is to find the support of the error or of the codeword.

• the algebraic attacks where the opponent tries to solve an algebraic system by Groebner basis.

First, we deal with the combinatorial attacks, both in the generic case and in the ideal LRPC case and in a third subsection we discuss about the algebraic attacks.

Generic attacks

In this section, we give the complexity of the best attack on the I -RSR 1.10 problem: the inputs are a vector h ∈ F n q m which defines the systematic parity-check matrix of an [2n, n] q m ideal code C, a syndrome c = e 1 + e 2 h mod P and an integer r which is the dimension of the support E of e = (e 1 , e 2 ). The goal is to find E.

This attack is an improvement of a previous attack described in [START_REF] Gaborit | On the complexity of the rank syndrome decoding problem[END_REF], a detailed description of the attack can be found in [START_REF] Aragon | Improvement of Generic Attacks on the Rank Syndrome Decoding Problem[END_REF]. For a better understanding, we first describe the first attack, then the new attack can easily be deduced from it. These attacks do not take account on the ideal structure of the code but in the current state-of-the-art, we do not know any generic combinatorial attack which uses this structure.

The first step is to compute a parity check matrix H of size n × 2n of C from h such that we have the system He T = c T of n equations over F q m . This step is polynomial so its cost is negligible. Let F be a subspace of F q m of dimension t and (F 1 , . . . , F t ) a basis of F . We will determine the value of t later. Let us assume that E ⊂ F .

⇒ ∀i ∈ [1..2n], e i = t j=1 λ ij F j
This gives us 2nt unknowns over F q and we have:

He T = c T (2) ⇔      H 1,1 e 1 + • • • + H 1,2n e 2n = c 1 . . . . . . . . . H n1 e 1 + • • • + H n,2n e 2n = c n ⇔      t j=1 (λ 1j H 1,1 F j + • • • + λ 2n,j H 1,2n F j ) = c 1 . . . . . . . . . t j=1 (λ 1j H n,1 F j + • • • + λ 2n,j H n,2n F j ) = c n (3)
Let ϕ i the i th canonical projection from F q m on F q :

ϕ i : F q m → F q m i=1 x i β i → x i
We apply these functions to the n equations of (3) to obtain

He T = c T ⇔ ∀i ∈ [1..m],      t j=1 λ 1j ϕ i (H 1,1 F j ) + • • • + λ 2n,j ϕ i (H 1,2n F j ) = ϕ i (c 1 ) . . . . . . . . . t j=1 λ 1j ϕ i (H n,1 F j ) + • • • + λ 2n,j ϕ i (H n,2n F j ) = ϕ i (c n ) (4)
Since we assume E ⊂ F , this system has at least one solution. We want nm 2nt to have more equations than unknowns =⇒ t m 2 . To check this assumption, we have to try and solve the system, that's why the complexity of this attack is O n 3 m 3 p where p is the probability that E ⊂ F . p is equal to the number of subspaces of dimension r in a subspace of dimension t divided by the total number of subspaces of dimension r in

F q m . p = t r q m r q ≈ q -r(m-t) By taking t = m 2 we obtain a complexity of O n 3 m 3 q r m 2
The new attack take account on the F q m -linearity of the code C. Let x be any solution of the system He T = c without consider its weight. Let C = C + F q m x be the [2n, n + 1] q m code generated by C and x. By construction, e ∈ C and by F q m -linearity any multiples αe ∈ C , α ∈ F q m . If r is small, then with overwhelming probability, all the codewords of C of weight r are multiple of e. If we know a codeword e = αe of weight r of C , we can recover e then E by solving the equation He = αc of unknown α ∈ F q m . The rest of the algorithm is the same as previously. We choose a subspace F of dimension t and assume that F contains the support αE of a codeword αe. There are at most

q m -1 q-1 subspaces of this form, because αE = βE if α/β ∈ F *
q and this bound is reached if m is prime, which is always the case in the parameters we have proposed. Since we have

q m -1 q-1 t r q m r q
, we can approximate the probability p that F ⊃ αE by the product of the probability that F ⊃ E by the number of subspaces of the form αE

p ≈ q m -1 q -1 t r q m r q ≈ q -r(m-t )+m-1
Then we express the coordinates of αe in a basis of F , which gives us 2nt unknowns over F q . Since C is an [2n, n + 1] q m code, the parity-check equations give us m(n -1) equations over F q , so we need t m(n-1) 2n

= m -m(n+1) 2n to solve the system. The complexity of the attack is

O (nm) 3 p = O (nm) 3 q r m(n+1) 2n -m
and the gain is almost q m with respect to the previous attack.

Structural attack against ideal LRPC codes

Let C be an [2n, n] q m ideal LRPC code generated by the two polynomials (x, y) of support F of dimension d. Let h = x -1 y which generates the systematic parity-check matrix of C.

The problem is to recover the structure of C, given only access to h. The most efficient known attack is to find a codeword of weight d in the dual code C ⊥ generated by h. The algorithm described in the previous section is the best known algorithm to solve this problem. However its complexity is better in the case of the dual of an ideal LRPC code than in a random code with the same parameters.

Indeed, let H be the matrix of size nn generated by (x, y). By definition, H is a generator matrix of C ⊥ . Let (h i ) 1 i n be the rows of H. For all 1 i n, Supp(h i ) = F =⇒ C ⊥ contains q n codewords of the same support, so the complexity of the algorithm is divided by q n . Thus, the complexity of the attack is

O n 3 m 3 q d m 2 -m-n
There exists a specific attack on the ideal LRPC codes which can be found in [8]. In this article, the authors present an attack against double circulant LRPC codes but it can be adapted straightforwardly in the case of ideal LRPC codes. However, the crucial point of this attack is that the polynomial X n -1 has always X -1 as divisor and may have many more factors depending on n and q. In the case of ideal LRPC codes, we can choose an irreducible polynomial P of degree n of F q [X] to generate the quotient-ring F q [X]/(P ), which completely negates this specific attack.

Algebraic attacks

The second way to solve the equations of the system (4) is to use the Groebner basis [START_REF] Vehel | Algebraic decoding of codes in rank metric[END_REF]. The advantage of these attacks is that they are independent of the size of q. They mainly depend on the number of unknowns with respect to the number of equations. However, in the case q = 2 the number of unknowns is generally too high for that the algorithms by Groebner basis are more efficient than the combinatorial attacks. We have chosen our parameters such that the best attacks are combinatorial, the expected complexity of the algorithms by Groebner basis is based on the article [START_REF] Bettale | Hybrid approach for solving multivariate systems over finite fields[END_REF].

Advantages and Limitations

Advantages

The proposed scheme is very efficient, both in terms of size of keys and computational complexity. The scheme also benefits from a constant time decoding algorithm. The choice of parameters is very versatile. There is a reduction to a well understood generic problem I -RSD, which is a natural generalization of Quasi-Cyclic RSD. This type of problem is the same type of problem which has been used for many years for Hamming and Euclidean distances.

Limitations

Rank metric has very nice features, the use of rank metric for cryptographic purposes is not very old (1991), it may be seen as a limitation, but still in recent years there has been a lot activities on understanding the inherent computational difficulty of the problem and it seems very hard to improve on the general complexity of the problem.

ACKNOWLEDGEMENT

Philippe Gaborit and Jean-Pierre Tillich thank the RISQ project for its support.

I, Nicolas Aragon, of University of Limoges, 123 avenue Albert Thomas, 87060 Limoges Cedex, FRANCE, do hereby declare that the cryptosystem, reference implementation, or optimized implementations that I have submitted, known as LOCKER, is my own original work, or if submitted jointly with others, is the original work of the joint submitters.

I further declare that (check one):

☑

I do not hold and do not intend to hold any patent or patent application with a claim which may cover the cryptosystem, reference implementation, or optimized implementations that I have submitted, known as LOCKER; OR (check one or both of the following):

☐
to the best of my knowledge, the practice of the cryptosystem, reference implementation, or optimized implementations that I have submitted, known as LOCKER, may be covered by the following U.S. and/or foreign patents: "Cryptographic method for communicating confidential information" US9094189 B2, and "Procédé cryptographique de communication d'une information confidentielle" FR 10/51190; ☐ I do hereby declare that, to the best of my knowledge, the following pending U.S. and/or foreign patent applications may cover the practice of my submitted cryptosystem, reference implementation or optimized implementations: "Cryptographic method for communicating confidential information" US9094189 B2, and "Procédé cryptographique de communication d'une information confidentielle" FR 10/51190. I do hereby acknowledge and agree that my submitted cryptosystem will be provided to the public for review and will be evaluated by NIST, and that it might not be selected for standardization by NIST. I further acknowledge that I will not receive financial or other compensation from the U.S. Government for my submission. I certify that, to the best of my knowledge, I have fully disclosed all patents and patent applications which may cover my cryptosystem, reference implementation or optimized implementations. I also acknowledge and agree that the U.S. Government may, during the public review and the evaluation process, and, if my submitted cryptosystem is selected for standardization, during the lifetime of the standard, modify my submitted cryptosystem's specifications (e.g., to protect against a newly discovered vulnerability).

I acknowledge that NIST will announce any selected cryptosystem(s) and proceed to publish the draft standards for public comment I do hereby agree to provide the statements required by Sections 2.D.2 and 2.D.3, below, for any patent or patent application identified to cover the practice of my cryptosystem, reference implementation or optimized implementations and the right to use such implementations for the purposes of the public review and evaluation process. I, Olivier Blazy, of University of Limoges, 123 avenue Albert Thomas, 87060 Limoges Cedex, FRANCE, do hereby declare that the cryptosystem, reference implementation, or optimized implementations that I have submitted, known as LOCKER, is my own original work, or if submitted jointly with others, is the original work of the joint submitters.

I further declare that (check one):

☑

I do not hold and do not intend to hold any patent or patent application with a claim which may cover the cryptosystem, reference implementation, or optimized implementations that I have submitted, known as LOCKER; OR (check one or both of the following):

☐
to the best of my knowledge, the practice of the cryptosystem, reference implementation, or optimized implementations that I have submitted, known as LOCKER, may be covered by the following U.S. and/or foreign patents: "Cryptographic method for communicating confidential information" US9094189 B2, and "Procédé cryptographique de communication d'une information confidentielle" FR 10/51190; ☐ I do hereby declare that, to the best of my knowledge, the following pending U.S. and/or foreign patent applications may cover the practice of my submitted cryptosystem, reference implementation or optimized implementations: "Cryptographic method for communicating confidential information" US9094189 B2, and "Procédé cryptographique de communication d'une information confidentielle" FR 10/51190. I do hereby acknowledge and agree that my submitted cryptosystem will be provided to the public for review and will be evaluated by NIST, and that it might not be selected for standardization by NIST. I further acknowledge that I will not receive financial or other compensation from the U.S. Government for my submission. I certify that, to the best of my knowledge, I have fully disclosed all patents and patent applications which may cover my cryptosystem, reference implementation or optimized implementations. I also acknowledge and agree that the U.S. Government may, during the public review and the evaluation process, and, if my submitted cryptosystem is selected for standardization, during the lifetime of the standard, modify my submitted cryptosystem's specifications (e.g., to protect against a newly discovered vulnerability).

I acknowledge that NIST will announce any selected cryptosystem(s) and proceed to publish the draft standards for public comment I do hereby agree to provide the statements required by Sections 2.D.2 and 2.D.3, below, for any patent or patent application identified to cover the practice of my cryptosystem, reference implementation or optimized implementations and the right to use such implementations for the purposes of the public review and evaluation process. I acknowledge that, during the post-quantum algorithm evaluation process, NIST may remove my cryptosystem from consideration for standardization. If my cryptosystem (or the derived cryptosystem) is removed from consideration for standardization or withdrawn from consideration by all submitter(s) and owner(s), I understand that rights granted and assurances made under Sections 2.D.1, 2.D.2 and 2.D.3, including use rights of the reference and optimized implementations, may be withdrawn by the submitter(s) and owner(s), as

☑

I do not hold and do not intend to hold any patent or patent application with a claim which may cover the cryptosystem, reference implementation, or optimized implementations that I have submitted, known as LOCKER; OR (check one or both of the following):

☐
to the best of my knowledge, the practice of the cryptosystem, reference implementation, or optimized implementations that I have submitted, known as LOCKER, may be covered by the following U.S. and/or foreign patents: "Cryptographic method for communicating confidential information" US9094189 B2, and "Procédé cryptographique de communication d'une information confidentielle" FR 10/51190; ☐ I do hereby declare that, to the best of my knowledge, the following pending U.S. and/or foreign patent applications may cover the practice of my submitted cryptosystem, reference implementation or optimized implementations: "Cryptographic method for communicating confidential information" US9094189 B2, and "Procédé cryptographique de communication d'une information confidentielle" FR 10/51190. I do hereby acknowledge and agree that my submitted cryptosystem will be provided to the public for review and will be evaluated by NIST, and that it might not be selected for standardization by NIST. I further acknowledge that I will not receive financial or other compensation from the U.S. Government for my submission. I certify that, to the best of my knowledge, I have fully disclosed all patents and patent applications which may cover my cryptosystem, reference implementation or optimized implementations. I also acknowledge and agree that the U.S. Government may, during the public review and the evaluation process, and, if my submitted cryptosystem is selected for standardization, during the lifetime of the standard, modify my submitted cryptosystem's specifications (e.g., to protect against a newly discovered vulnerability). I acknowledge that NIST will announce any selected cryptosystem(s) and proceed to publish the draft standards for public comment I do hereby agree to provide the statements required by Sections 2.D.2 and 2.D.3, below, for any patent or patent application identified to cover the practice of my cryptosystem, reference implementation or optimized implementations and the right to use such implementations for the purposes of the public review and evaluation process.

I acknowledge that, during the post-quantum algorithm evaluation process, NIST may remove my cryptosystem from consideration for standardization. If my cryptosystem (or the derived cryptosystem) is removed from consideration for standardization or withdrawn from consideration by all submitter(s) and owner(s), I understand that rights granted and assurances made under Sections 2.D.1, 2.D.2 and 2.D.3, including use rights of the reference and optimized implementations, may be withdrawn by the submitter(s) and owner(s), as appropriate.

Signed: Jean-ChristopheDeneuville Title: PhD, post-doc Date: November 28, 2017 Place: Limoges I, Philippe Gaborit, of University of Limoges, 123 avenue Albert Thomas, 87060 Limoges Cedex, FRANCE, do hereby declare that the cryptosystem, reference implementation, or optimized implementations that I have submitted, known as LOCKER, is my own original work, or if submitted jointly with others, is the original work of the joint submitters. I further declare that (check one):

☑

I do not hold and do not intend to hold any patent or patent application with a claim which may cover the cryptosystem, reference implementation, or optimized implementations that I have submitted, known as LOCKER; OR (check one or both of the following):

☐
to the best of my knowledge, the practice of the cryptosystem, reference implementation, or optimized implementations that I have submitted, known as LOCKER, may be covered by the following U.S. and/or foreign patents: "Cryptographic method for communicating confidential information" US9094189 B2, and "Procédé cryptographique de communication d'une information confidentielle" FR 10/51190; ☐ I do hereby declare that, to the best of my knowledge, the following pending U.S. and/or foreign patent applications may cover the practice of my submitted cryptosystem, reference implementation or optimized implementations: "Cryptographic method for communicating confidential information" US9094189 B2, and "Procédé cryptographique de communication d'une information confidentielle" FR 10/51190. I do hereby acknowledge and agree that my submitted cryptosystem will be provided to the public for review and will be evaluated by NIST, and that it might not be selected for standardization by NIST. I further acknowledge that I will not receive financial or other compensation from the U.S. Government for my submission. I certify that, to the best of my knowledge, I have fully disclosed all patents and patent applications which may cover my cryptosystem, reference implementation or optimized implementations. I also acknowledge and agree that the U.S. Government may, during the public review and the evaluation process, and, if my submitted cryptosystem is selected for standardization, during the lifetime of the standard, modify my submitted cryptosystem's specifications (e.g., to protect against a newly discovered vulnerability). I acknowledge that NIST will announce any selected cryptosystem(s) and proceed to publish the draft standards for public comment I do hereby agree to provide the statements required by Sections 2.D.2 and 2.D.3, below, for any patent or patent application identified to cover the practice of my cryptosystem, reference implementation or optimized implementations and the right to use such implementations for the purposes of the public review and evaluation process. I acknowledge that, during the post-quantum algorithm evaluation process, NIST may remove my cryptosystem from consideration for standardization. If

☐
to the best of my knowledge, the practice of the cryptosystem, reference implementation, or optimized implementations that I have submitted, known as LOCKER, may be covered by the following U.S. and/or foreign patents: "Cryptographic method for communicating confidential information" US9094189 B2, and "Procédé cryptographique de communication d'une information confidentielle" FR 10/51190; ☐ I do hereby declare that, to the best of my knowledge, the following pending U.S. and/or foreign patent applications may cover the practice of my submitted cryptosystem, reference implementation or optimized implementations: "Cryptographic method for communicating confidential information" US9094189 B2, and "Procédé cryptographique de communication d'une information confidentielle" FR 10/51190. I do hereby acknowledge and agree that my submitted cryptosystem will be provided to the public for review and will be evaluated by NIST, and that it might not be selected for standardization by NIST. I further acknowledge that I will not receive financial or other compensation from the U.S. Government for my submission. I certify that, to the best of my knowledge, I have fully disclosed all patents and patent applications which may cover my cryptosystem, reference implementation or optimized implementations. I also acknowledge and agree that the U.S. Government may, during the public review and the evaluation process, and, if my submitted cryptosystem is selected for standardization, during the lifetime of the standard, modify my submitted cryptosystem's specifications (e.g., to protect against a newly discovered vulnerability). I acknowledge that NIST will announce any selected cryptosystem(s) and proceed to publish the draft standards for public comment I do hereby agree to provide the statements required by Sections 2.D.2 and 2.D.3, below, for any patent or patent application identified to cover the practice of my cryptosystem, reference implementation or optimized implementations and the right to use such implementations for the purposes of the public review and evaluation process. I acknowledge that, during the post-quantum algorithm evaluation process, NIST may remove my cryptosystem from consideration for standardization. If

☐

to the best of my knowledge, the practice of the cryptosystem, reference implementation, or optimized implementations that I have submitted, known as LOCKER, may be covered by the following U.S. and/or foreign patents: "Cryptographic method for communicating confidential information" US9094189 B2, and "Procédé cryptographique de communication d'une information confidentielle" FR 10/51190; ☐ I do hereby declare that, to the best of my knowledge, the following pending U.S. and/or foreign patent applications may cover the practice of my submitted cryptosystem, reference implementation or optimized implementations: "Cryptographic method for communicating confidential information" US9094189 B2, and "Procédé cryptographique de communication d'une information confidentielle" FR 10/51190. I do hereby acknowledge and agree that my submitted cryptosystem will be provided to the public for review and will be evaluated by NIST, and that it might not be selected for standardization by NIST. I further acknowledge that I will not receive financial or other compensation from the U.S. Government for my submission. I certify that, to the best of my knowledge, I have fully disclosed all patents and patent applications which may cover my cryptosystem, reference implementation or optimized implementations. I also acknowledge and agree that the U.S. Government may, during the public review and the evaluation process, and, if my submitted cryptosystem is selected for standardization, during the lifetime of the standard, modify my submitted cryptosystem's specifications (e.g., to protect against a newly discovered vulnerability). I acknowledge that NIST will announce any selected cryptosystem(s) and proceed to publish the draft standards for public comment I do hereby agree to provide the statements required by Sections 2.D.2 and 2.D.3, below, for any patent or patent application identified to cover the practice of my cryptosystem, reference implementation or optimized implementations and the right to use such implementations for the purposes of the public review and evaluation process. I acknowledge that, during the post-quantum algorithm evaluation process, NIST may remove my cryptosystem from consideration for standardization. If my cryptosystem (or the derived cryptosystem) is removed from consideration for standardization or withdrawn from consideration by all submitter(s) and owner(s), I understand that rights granted and assurances made under Sections 2.D.

☐

to the best of my knowledge, the practice of the cryptosystem, reference implementation, or optimized implementations that I have submitted, known as LOCKER, may be covered by the following U.S. and/or foreign patents: "Cryptographic method for communicating confidential information" US9094189 B2, and "Procédé cryptographique de communication d'une information confidentielle" FR 10/51190; ☐ I do hereby declare that, to the best of my knowledge, the following pending U.S. and/or foreign patent applications may cover the practice of my submitted cryptosystem, reference implementation or optimized implementations: "Cryptographic method for communicating confidential information" US9094189 B2, and "Procédé cryptographique de communication d'une information confidentielle" FR 10/51190. I do hereby acknowledge and agree that my submitted cryptosystem will be provided to the public for review and will be evaluated by NIST, and that it might not be selected for standardization by NIST. I further acknowledge that I will not receive financial or other compensation from the U.S. Government for my submission. I certify that, to the best of my knowledge, I have fully disclosed all patents and patent applications which may cover my cryptosystem, reference implementation or optimized implementations. I also acknowledge and agree that the U.S. Government may, during the public review and the evaluation process, and, if my submitted cryptosystem is selected for standardization, during the lifetime of the standard, modify my submitted cryptosystem's specifications (e.g., to protect against a newly discovered vulnerability). I acknowledge that NIST will announce any selected cryptosystem(s) and proceed to publish the draft standards for public comment I do hereby agree to provide the statements required by Sections 2.D.2 and 2.D.3, below, for any patent or patent application identified to cover the practice of my cryptosystem, reference implementation or optimized implementations and the right to use such implementations for the purposes of the public review and evaluation process. I acknowledge that, during the post-quantum algorithm evaluation process, NIST may remove my cryptosystem from consideration for standardization. If my cryptosystem (or the derived cryptosystem) is removed from consideration for standardization or withdrawn from consideration by all submitter(s) and owner(s), I understand that rights granted and assurances made under Sections 2.D.

☑

I do not hold and do not intend to hold any patent or patent application with a claim which may cover the cryptosystem, reference implementation, or optimized implementations that I have submitted, known as LAKE; OR (check one or both of the following):

☐

to the best of my knowledge, the practice of the cryptosystem, reference implementation, or optimized implementations that I have submitted, known as LAKE, may be covered by the following U.S. and/or foreign patents: "Cryptographic method for communicating confidential information" US9094189 B2, and "Procédé cryptographique de communication d'une information confidentielle" FR 10/51190; ☐ I do hereby declare that, to the best of my knowledge, the following pending U.S. and/or foreign patent applications may cover the practice of my submitted cryptosystem, reference implementation or optimized implementations: "Cryptographic method for communicating confidential information" US9094189 B2, and "Procédé cryptographique de communication d'une information confidentielle" FR 10/51190. I do hereby acknowledge and agree that my submitted cryptosystem will be provided to the public for review and will be evaluated by NIST, and that it might not be selected for standardization by NIST. I further acknowledge that I will not receive financial or other compensation from the U.S. Government for my submission. I certify that, to the best of my knowledge, I have fully disclosed all patents and patent applications which may cover my cryptosystem, reference implementation or optimized implementations. I also acknowledge and agree that the U.S. Government may, during the public review and the evaluation process, and, if my submitted cryptosystem is selected for standardization, during the lifetime of the standard, modify my submitted cryptosystem's specifications (e.g., to protect against a newly discovered vulnerability). I acknowledge that NIST will announce any selected cryptosystem(s) and proceed to publish the draft standards for public comment I do hereby agree to provide the statements required by Sections 2.D.2 and 2.D.3, below, for any patent or patent application identified to cover the practice of my cryptosystem, reference implementation or optimized implementations and the right to use such implementations for the purposes of the public review and evaluation process. I acknowledge that, during the post-quantum algorithm evaluation process, NIST may remove my cryptosystem from consideration for standardization. If my cryptosystem (or the derived cryptosystem) is removed from consideration for standardization or withdrawn from consideration by all submitter(s) and owner(s), I understand that rights granted and assurances

Definition 1 . 4 (

 14 Circulant matrix).A square matrix M of size n × n is said circulant if it is of the form

Proposition 1 . 1 i=1P

 11 16. The probability of failure of the new algorithm is rd-(c = i) × P c=i (f ailure) Analysis of P c=1 (f ailure)

Figure 1 :

 1 Figure 1: Description of LAKE key exchange protocol.

Table 1 :

 1 2 gives the number of CPU cycles. Timings (in ms) of the reference implementation for different instances of LAKE.

	Instance KeyGen Encap Decap
	LAKE-I	0.65	0.13	0.53
	LAKE-II	0.73	0.13	0.88
	LAKE-III	0.77	0.15	1.24
	Instance KeyGen Encap Decap
	LAKE-I	1.58	0.30	1.27
	LAKE-II	1.74	0.31	2.09
	LAKE-III	1.79	0.35	2.89

Table 2 :

 2 Millions of cycles reference implementation for different instances of LAKE.

  appropriate. Christophe Deneuville, of INSA-CVL, 88 boulevard Lahitolle, 18000 Bourges, FRANCE, and University of Limoges, 123 avenue Albert Thomas, 87060 Limoges Cedex, FRANCE, do hereby declare that the cryptosystem, reference implementation, or optimized implementations that I have submitted, known as LOCKER, is my own original work, or if submitted jointly with others, is the original work of the joint submitters.

	Signed: Olivier Blazy I, Jean-I further declare that (check one):
	Title: Associate Professor
	Date: November 28, 2017
	Place: Limoges

  my cryptosystem (or the derived cryptosystem) is removed from consideration for standardization or withdrawn from consideration by all submitter(s) and owner(s), I understand that rights granted and assurances made under Sections 2.D.1, 2.D.2 and 2.D.3, including use rights of the reference and optimized implementations, may be withdrawn by the submitter(s) and owner(s), as appropriate. Adrien Hauteville, of University of Limoges, 123 avenue Albert Thomas, 87060 Limoges Cedex, FRANCE, do hereby declare that the cryptosystem, reference implementation, or optimized implementations that I have submitted, known as LOCKER, is my own original work, or if submitted jointly with others, is the original work of the joint submitters.

	Signed: I, I further declare that (check one):
	I do not hold and do not intend to hold any patent or patent application with a claim which may cover the cryptosystem, reference implementation, or optimized ☑ Title: Professor implementations that I have submitted, known as LOCKER; OR (check one or both of the Date: November 28, 2017 Place: Limoges following):

  my cryptosystem (or the derived cryptosystem) is removed from consideration for standardization or withdrawn from consideration by all submitter(s) and owner(s), I understand that rights granted and assurances made under Sections 2.D.1, 2.D.2 and 2.D.3, including use rights of the reference and optimized implementations, may be withdrawn by the submitter(s) and owner(s), as appropriate. Olivier Ruatta, of University of Limoges, 123 avenue Albert Thomas, 87060 Limoges Cedex, FRANCE, do hereby declare that the cryptosystem, reference implementation, or optimized implementations that I have submitted, known as LOCKER, is my own original work, or if submitted jointly with others, is the original work of the joint submitters.

	Signed: Adrien Hauteville I, I further declare that (check one):
	Title: PhD Student Date: November 28, 2017 I do not hold and do not intend to hold any patent or patent application with a ☑ claim which may cover the cryptosystem, reference implementation, or optimized Place: Limoges implementations that I have submitted, known as LOCKER; OR (check one or both of the
	following):

  1, 2.D.2 and 2.D.3, including use rights of the reference and optimized implementations, may be withdrawn by the submitter(s) and owner(s), as appropriate. Pierre Tillich, of INRIA Rocquencourt, B.P. 105 78153 Le Chesnay Cedex, FRANCE, do hereby declare that the cryptosystem, reference implementation, or optimized implementations that I have submitted, known as LOCKER, is my own original work, or if submitted jointly with others, is the original work of the joint submitters.

	Signed: Olivier Ruatta I, Jean-I further declare that (check one):
	Title: Associate Professor Date: November 28, 2017 I do not hold and do not intend to hold any patent or patent application with a ☑ claim which may cover the cryptosystem, reference implementation, or optimized Place: Limoges implementations that I have submitted, known as LOCKER; OR (check one or both of the
	following):

  1, 2.D.2 and 2.D.3, including use rights of the reference and optimized implementations, may be withdrawn by the submitter(s) and owner(s), as appropriate. Gilles Zémor, of IMB, University of Bordeaux, 351 cours de la Libération, F-33405 Talence Cedex, FRANCE, do hereby declare that the cryptosystem, reference implementation, or optimized implementations that I have submitted, known as LAKE, is my own original work, or if submitted jointly with others, is the original work of the joint submitters.

	Signed: Jean-Pierre Tillich I, I further declare that (check one):
	Title: Research Director, Professor
	Date: November 28, 2017
	Place: Paris

Signed: Gilles Zémor Title: Professor Date: November 28, 2017 Place: Bordeaux I, Nicolas Aragon, of University of Limoges, 123 avenue Albert Thomas, 87060 Limoges Cedex, FRANCE, am the owner of the submitted reference implementation and optimized implementations and hereby grant the U.S. Government and any interested party the right to reproduce, prepare derivative works based upon, distribute copies of, and display such implementations for the purposes of the post-quantum algorithm public review and evaluation process, and implementation if the corresponding cryptosystem is selected for standardization and as a standard, notwithstanding that the implementations may be copyrighted or copyrightable.

Signed: Nicolas Aragon Title: PhD Student Date: November 28, 2017 Place: Limoges I, Olivier Blazy, of University of Limoges, 123 avenue Albert Thomas, 87060 Limoges Cedex, FRANCE, am the owner of the submitted reference implementation and optimized implementations and hereby grant the U.S. Government and any interested party the right to reproduce, prepare derivative works based upon, distribute copies of, and display such implementations for the purposes of the post-quantum algorithm public review and evaluation process, and implementation if the corresponding cryptosystem is selected for standardization and as a standard, notwithstanding that the implementations may be copyrighted or copyrightable. Signed: Olivier Blazy Title: Associate Professor Date: November 28, 2017 Place: Limoges I, Jean-Christophe Deneuville, of INSA-CVL Bourges, 88 boulevard Lahitolle, 18000 Bourges, FRANCE, and University of Limoges, 123 avenue Albert Thomas, 87060 Limoges Cedex, FRANCE, am the owner of the submitted reference implementation and optimized implementations and hereby grant the U.S. Government and any interested party the right to reproduce, prepare derivative works based upon, distribute copies of, and display such implementations for the purposes of the post-quantum algorithm public review and evaluation process, and implementation if the corresponding cryptosystem is selected for standardization and as a standard, notwithstanding that the implementations may be copyrighted or copyrightable. Signed: Jean-Christophe Deneuville Title: Ph.D. post-doc Date: November 28, 2017 Place: Limoges I, Philippe Gaborit, of University of Limoges, 123 avenue Albert Thomas, 87060 Limoges Cedex, FRANCE, am the owner of the submitted reference implementation and optimized implementations and hereby grant the U.S. Government and any interested party the right to reproduce, prepare derivative works based upon, distribute copies of, and display such implementations for the purposes of the post-quantum algorithm public review and evaluation process, and implementation if the corresponding cryptosystem is selected for standardization and as a standard, notwithstanding that the implementations may be copyrighted or copyrightable. Signed: Title: Professor Date: November 28, 2017 Place: Limoges

I, Adrien Hauteville, University of Limoges, 123 avenue Albert Thomas, 87060 Limoges Cedex, FRANCE, am the owner of the submitted reference implementation and optimized implementations and hereby grant the U.S. Government and any interested party the right to reproduce, prepare derivative works based upon, distribute copies of, and display such implementations for the purposes of the post-quantum algorithm public review and evaluation

process, and implementation if the corresponding cryptosystem is selected for standardization and as a standard, notwithstanding that the implementations may be copyrighted or copyrightable.

Signed: Adrien Hauteville Title: Ph.D. Student Date: November 28, 2017 Place: Limoges I, Olivier Ruatta, of University of Limoges, 123 avenue Albert Thomas, 87060 Limoges Cedex, FRANCE, am the owner of the submitted reference implementation and optimized implementations and hereby grant the U.S. Government and any interested party the right to reproduce, prepare derivative works based upon, distribute copies of, and display such implementations for the purposes of the post-quantum algorithm public review and evaluation process, and implementation if the corresponding cryptosystem is selected for standardization and as a standard, notwithstanding that the implementations may be copyrighted or copyrightable.

Signed: Olivier Ruatta Title: Associate Professor Date: November 28, 2017 Place: Limoges I, Jean-Pierre Tillich, of INRIA Rocquencourt, B.P. 105 78153 Le Chesnay Cedex, FRANCE, am the owner of the submitted reference implementation and optimized implementations and hereby grant the U.S. Government and any interested party the right to reproduce, prepare derivative works based upon, distribute copies of, and display such implementations for the purposes of the post-quantum algorithm public review and evaluation process, and implementation if the corresponding cryptosystem is selected for standardization and as a standard, notwithstanding that the implementations may be copyrighted or copyrightable.

Signed: Jean-Pierre Tillich Title: Research Director, Professor Date: November 28, 2017 Place: Paris I, Gilles Zémor, of IMB, University of Bordeaux, 351 cours de la Libération, F-33405 Talence Cedex, FRANCE, am the owner of the submitted reference implementation and optimized implementations and hereby grant the U.S. Government and any interested party the right to reproduce, prepare derivative works based upon, distribute copies of, and display such implementations for the purposes of the post-quantum algorithm public review and evaluation process, and implementation if the corresponding cryptosystem is selected for standardization and as a standard, notwithstanding that the implementations may be copyrighted or copyrightable.

Signed: Gilles Zémor Title: Professor Date: November 28, 2017 Place: Bordeaux

A Signed statements by the submitters NIST requires statements about the intellectual property of the present submission. While NIST clearly mentioned they require the original paper version of these statements, the authors estimated useful to include a digital copy of these statements in this document. The paper version of these statements will be provided directly to Dustin Moody (or any other NIST member) at the first PQC Standardization Conference.

The remainder of this submission consists of statements. Below is a list of the statements included.

Statement by each submitter. Each of the authors has such a statement included.

Statement by patent owners. No patent are involved.

Statement by reference/optimized implementations' owners. Each of the authors has such a statement included.


domain: spi math phys

text:
Alexandre Albore
email: alexandre.albore@onera.fr

Sandra Castellanos-Paez
email: sandra.castellanos@univ-grenoble-alpes.fr

Nicolas Hili
email: nicolas.hili@univ-grenoble-alpes.fr

BOARD-AI: A Goal Recognition-Based Objective-Aware Modeling Interface for Systems Engineering

Paper and pens remain the most commonly used tools by systems engineers to capture system models. However, digitizing models sketched on a whiteboard into Computer-Aided Systems Engineering (CASE) tools remains a difficult and error-prone activity that requires the knowledge of tool experts. This study presents a reactive whiteboard interface for model sketching. This online approach combines techniques from Automated Planning and Machine Learning to improve performance while not compromising explainability of the system's output. Our approach mainly relies on two main modules: (1) a trained neural network that separates upstream from the global recognition process, handwritten text from geometrical symbols, and (2) a goal recognition algorithm that models the sketching task as a planning problem to identify the final s ketches t hat a re d eemed p ossible. T he main benefits of BOARD-AI are its autonomy, i.e. it does not rely on any other interaction modalities (e.g., virtual keyboards), and its explainability, i.e. the outcomes of the modeling assistant are understandable since a plan provides a valid explanation of the system's suggestions. Finally, BOARD-AI usability was validated trough user evaluations of engineers, experts and non experts in software and/or system modeling design.

Introduction

The usage of symbolic AI techniques to aid systems engineers to design models in a freehand way using large multitouch screens is a viable process that has shown to be usable as an Human-machine interface for Systems Engineering modeling [START_REF] Castellanos-Paez | BOARD-AI: A goal-aware modeling interface for systems engineering, combining machine learning and plan recognition[END_REF].

BOARD-AI is a reactive modeling interface for natural sketching that allows engineers to capture system models using interactive whiteboards. The heart of our approach lies in the use of goal recognition [START_REF] Shvo | Active goal recognition[END_REF][START_REF] Keren | Goal recognition design[END_REF][START_REF] Lesh | A sound and fast goal recognizer[END_REF][START_REF] Kautz | Generalized plan recognition[END_REF] techniques to translate user's sketches into model elements [START_REF] Albore | From Informal Sketches to System Engineering Models using AI Plan Recognition: Opportunities and Challenges[END_REF][START_REF] Hili | From Informal Sketches to Systems Engineering Models Using AI Plan Recognition[END_REF]. More precisely, a modeling assistant identifies the most probable model elements intended to be drawn by a user from an initial sketch, even if partial. The outcome is an ordered list of suggestions ordered by the probability that a complete model element corresponds to the user's intent.

The main benefit of relying on symbolic AI rather than on ML is explainability, i.e. the property of a system that provides an output that makes understandable to the human user the reasons of an algorithm's choice. This condition is needed by any process-directed tool that allows users to evaluate the criteria behind a choice to use the tool more efficiently [START_REF] Rosenfeld | Explainability in humanagent systems[END_REF]. Not only the modeling assistant provides the user with a list of suggestions, but it also details the remaining steps to draw the suggested model elements completely.

Finally, we conducted an evaluation that helped us to understand how BOARD-AI supports and facilitates the work of system engineers, and whether an AI-based modeling environment is trusted and deemed usable by its users. We obtained very encouraging results about usability, and AIassisted sketching [START_REF] Castellanos-Paez | BOARD-AI: A goal-aware modeling interface for systems engineering, combining machine learning and plan recognition[END_REF].

Goal-Aware Natural Sketching

The architecture of BOARD-AI follows a client-server architecture where the back-end (in Python) is responsible for calling the different services for shape recognition. It consists of three main modules. The handler module makes the link with the interface. It starts a Web-socket server to communicate with the front-end. Shape recognition being incremental, the web-socket communication is used to update the interface every-time a more optimized plan is found. A Classifier module built on top of numpy distinguishes geometrical shapes from textual annotations. The planner module is responsible for translating sketched elements into PDDL. Models elements to be recognized are structured as JSON objects and stored in separate files. When the planner module starts, it first loads the different files and then translates each JSON object into PDDL problem templates.

On the usage of Goal Recognition

We use PDDL to formalize our drawing problem, describe the initial sketch, and describe the list of all the model elements deemed possible. This list constitutes the goal library for goal recognition. The PDDL domain definition contains the formalization of the drawing problem.

This formalization of the drawing problem and the goal library are generic and reused across different executions of the recognition process. Only the formalization of the initial sketch in PDDL is specific and is automatically generated from the graph obtained in the previous step.

Given the current state of the board and the goal library, we run the planner for the sketch being drawn by the user. We used the Fast Downward planning system [START_REF] Helmert | The fast downward planning system[END_REF], running the version of LAMA Planner (Richter and Westphal 2010) that participated in IPC 2011, and that has been integrated into Fast Downward's code. The anytime algorithm used in LAMA does not continue the weighted A* search once it finds a solution. Instead, it start a new weighted A*-based search from the initial state. The planner then outputs several plans, with increasing quality (measured in the number of actions in the plan). Each plan is an ordered list of possible matches between the sketch being drawn by the user and the goals denoting the different model elements that could be recognized. The set of possible matches is ordered based on the degree of confidence of the match regarding the element currently drawn. The degree depends on the distance (in the plan) between the current sketch and the possible goal, i.e., the number of steps that would remain to finish drawing the element completely.

Implementation details

Fig. 1 pictures the BOARD-AI main interface. The interface is developed using Web technologies (HTML, CSS, and JavaScript) so it can be used remotely and it can be run on any interactive pen display devices, ranging from tablets to large screens equipped with stylus. We adopted a minimalist style where the entirety of the screen can be used to draw a model so that users can fully focus on the sketching activity without being disturbed by an overloaded interface. The main area is an HTML5 Canvas for drawing model elements. A toolbar provides some useful features, such as undo/redo, page management, different edition modes (drawing, erasing, and selection), and two options to customize the thickness and the color of the drawing. The toolbar can be collapsed to maximize the drawing area. Besides these features, a chalk effect is applied to replicate the writing on a blackboard.

Two distinct interaction modalities are used to interact with the screen. Drawing is only possible using the stylus while touch gestures enable the user to navigate across the interface. Zooming in and out is achieved by pinching the screen. Single finger panning can also be used to navigate within the Canvas when it is scaled up. When the interface is scaled up, an outline at the bottom right of the screen shows the visible area.

When the user starts drawing, the recognition process is performed. Under the hood, the recognition engine consecutively identifies and characterizes the primitive shapes drawn by the user, invokes the classifier, and performs text or shape recognition according to the output of the classifier. Visual hints are given in the shape of bubbles accompanying the elements to recognize. Clicking on a visual hint results in converting the partial drawing into the suggested model element or text. If the partial drawing is updated by the user, the suggestions are updated as well.

Multiple shapes and/or textual annotations can be recognized at the same time. Hints to geometrical shapes are provided by the Fast Downward planning system [START_REF] Helmert | The fast downward planning system[END_REF] and are updated according to the anytime algorithm used. A limit of the three best suggestions is kept and displayed along with the partial drawing. Recognizing textual annotation is done using third-party Optical Character Recognition (OCR) engines.

Figure 1 :

 1 Figure 1: Screenshot of the BOARD-AI interface running on a Samsung Galaxy S6 Lite. Blue bubbles along with drawn sketches provide hints about the model elements to recognize.