Martin R Albrecht
email: martin.albrecht@rhul.ac.uk

Carlos Cid
email: carlos.cid@rhul.ac.uk

Jean-Charles Faugère
email: jean-charles.faugere@inria.fr

Robert Fitzpatrick
email: robert.fitzpatrick.2010@live.rhul.ac.uk

Ludovic Perret
email: ludovic.perret@lip6.fr

Algebraic Algorithms for LWE Problems

We analyse the complexity of algebraic algorithms for solving systems of linear equations with noise. Such systems arise naturally in the theory of error-correcting codes as well as in computational learning theory. More recently, linear systems with noise have found application in cryptography. The Learning with Errors (LWE) problem has proven to be a rich and versatile source of innovative cryptosystems, such as fully homomorphic encryption schemes. Despite the popularity of the LWE problem, the complexity of algorithms for solving it is not very well understood, particularly when variants of the original problem are considered. Here, we focus on and generalise a particular method for solving these systems, due to Arora & Ge, which reduces the problem to non-linear but noise-free system solving. Firstly, we provide a refined complexity analysis for the original Arora-Ge algorithm for LWE. Secondly, we study the complexity of applying algorithms for computing Gröbner basis, a fundamental tool in computational commutative algebra, to solving Arora-Ge-style systems of non-linear equations. We show positive and negative results. On the one hand, we show that the use of Gröbner bases yields an exponential speed-up over the basic Arora-Ge approach. On the other hand, we give a negative answer to the natural question whether the use of such techniques can yield a subexponential algorithm for the LWE problem. Under a mild algebraic assumption, we show that it is highly unlikely that such an improvement exists. We also consider a variant of LWE known as BinaryError-LWE introduced by Micciancio and Peikert recently. By combining Gröbner basis algorithms with the Arora-Ge modelling, we show under a natural algebraic assumption that BinaryError-LWE can be solved in subexponential time as soon as the number of samples is quasi-linear, e.g. m = O (n log log n). We also derive precise complexity bounds for BinaryError-LWE with m = O (n), showing that this new approach yields better results than best currently-known generic (exact) CVP solver as soon as m/n ≥ 6.6. More generally, our results provide a good picture of the hardness degradation of BinaryError-LWE for a number of samples ranging from m = n 1 + Ω 1/log(n) (a case for which BinaryError-LWE is as hard as solving some lattice problem in the worst case) to m = O n 2 (a case for which it can be solved in polynomialtime). This addresses an open question from Micciancio and Peikert. Whilst our results do not contradict the hardness results obtained by Micciancio and Peikert, they should rule out BinaryError-LWE for many cryptographic applications. The results in this work depend crucially on the assumption the algebraic systems considered systems are not easier and not harder to solve than a random system of equations. We have verified experimentally such hypothesis. We also have been able to prove formally the assumptions is several restricted situations. We emphasize that these issues are highly non-trivial since proving our assumptions in full generality would allow to prove a famous conjecture in commutative algebra known as Fröberg's Conjecture.

Introduction

Whilst linear systems of polynomial equations can be solved very efficiently and with low data requirements, the situation changes dramatically once we introduce some kind of error or noise to these equations. In this work we consider the hardness of solving such systems of linear equations with noise, a problem that can be informally defined as follows:

Definition 1 (Linear System with Noise). Let q be a prime. Given a matrix G ∈ Z n×m q and a vector c ∈ Z m q . The LINEAR SYSTEM WITH NOISE problem is the task of finding a vector s ∈ Z n q such that: c = s × G + e, where e ∈ Z m q is a "small" error-vector.

A classical way to define smallness is to consider the Hamming weight of e ∈ Z m q , i.e. the number of non-zero components of e. Equipped with this norm, the problem defined above is a classical NP-hard problem from coding theory known as BOUNDED DISTANCE DECODING [START_REF] Berlekamp | On the inherent intractability of certain coding problems (corresp.)[END_REF]. The hardness of this problem has been used by McEliece to design the first public-key code-based encryption scheme [START_REF] Mceliece | A Public-Key System Based on Algebraic Coding Theory[END_REF]. The McEliece cryptosystem, which was proposed in the late seventies, still belongs to the small group of public-key schemes that remain unbroken. The alphabet Z q in the McEliece cryptosystem is usually small (typically, q = 2) and independent of the security parameter n. More recently, Regev [START_REF] Regev | On lattices, learning with errors, random linear codes, and cryptography[END_REF][START_REF] Regev | On lattices, learning with errors, random linear codes, and cryptography[END_REF] considered an alternative way of introducing errors. He suggested a larger modulus q (typically, taken to be polynomial in n), and sample the components of the error-vector according to a discrete Gaussian distribution χ on Z (considered modulo q) with mean 0 and standard deviation σ = α q/ √ 2π, for some α ∈ (0, 1). In this context, LINEAR SYSTEM WITH NOISE is better known as the LEARNING WITH ERRORS (LWE) problem. The probability distribution used for error sampling implies that each of its components will have a small norm (w.r.t. the size of the field) with high probability. Since its introduction, LWE has proven to be a rich and versatile source of many innovative cryptosystems, such as the oblivious transfer protocol by Peikert et al. [START_REF] Peikert | A framework for efficient and composable oblivious transfer[END_REF], a cryptosystem by Akavia et al. [START_REF] Akavia | Simultaneous hardcore bits and cryptography against memory attacks[END_REF] that is secure even if almost the entire secret key is leaked, homomorphic encryption [START_REF] Albrecht | Polly Cracker, revisited[END_REF][START_REF] Brakerski | Efficient fully homomorphic encryption from (standard) LWE[END_REF][START_REF] Gentry | A fully homomorphic encryption scheme[END_REF] and many others. Below we reproduce the definition of LWE from [START_REF] Regev | On lattices, learning with errors, random linear codes, and cryptography[END_REF][START_REF] Regev | On lattices, learning with errors, random linear codes, and cryptography[END_REF].

Definition 2 (LWE). Let n ≥ 1 be an integer, q be an odd integer, χ be a probability distribution on Z q and s ∈ Z n q be a secret vector. We denote by L (n) s,χ the probability distribution on Z n×m q × Z m q obtained by choosing G ∈ Z n×m q uniformly at random, sampling e according to χ m , and returning (G, s × G + e) = (G, c) ∈ Z n×m q × Z m q . LWE is the problem of finding s ∈ Z n q from (G, s × G + e) sampled according to

L (n) s,χ .
In what follows, χ α,q will denote a discrete Gaussian distribution over Z with standard deviation α q/ √ 2π considered modulo q. A typical setting for the standard deviation (std) is σ = n ǫ , with 0 ≤ ǫ ≤ 1. It has been shown that as soon as ǫ > 1/2, (worst-case) GAPSVP -Õ(n/α) classically reduces to (average-case) LWE [START_REF] Brakerski | Classical hardness of Learning with Errors[END_REF][START_REF] Peikert | Public-key cryptosystems from the worst-case shortest vector problem: extended abstract[END_REF][START_REF] Regev | On lattices, learning with errors, random linear codes, and cryptography[END_REF][START_REF] Regev | On lattices, learning with errors, random linear codes, and cryptography[END_REF]. Thus, any algorithm solving LWE (when ǫ > 1/2) can be used for GAPSVP -Õ(n/α). We note that it is widely believed that only exponential (classical or quantum) algorithms exist for solving GAPSVP -Õ(n/α).

The Arora-Ge Algorithm for Solving LWE

In [START_REF] Arora | New algorithms for learning in presence of errors[END_REF], Arora & Ge show that solving LWE can be reduced to solving a system of (error-free) high-degree nonlinear equations. The total complexity (time and space) of this approach is 2 Õ(n 2ǫ ) . Hence, it is sub-exponential when ǫ < 1/2, but remains exponential when ǫ ≥ 1/2. As a corollary, this result also shows that Regev's reduction in [START_REF] Regev | On lattices, learning with errors, random linear codes, and cryptography[END_REF][START_REF] Regev | On lattices, learning with errors, random linear codes, and cryptography[END_REF] is tight. The strategy in [START_REF] Arora | New algorithms for learning in presence of errors[END_REF] is to construct a non-linear but noise-free system of equations; from each noisy linear sample a non-linear equation of degree 2T + 1 is formed, encoding the information that any noise value e i is in the interval {-T, . . . , T }. If T < q/2 these equations still carry information and restrict the space of the secret. Hence, collecting many such equations and solving the resulting system allows to recover the secret. In [START_REF] Arora | New algorithms for learning in presence of errors[END_REF] linearisation is used to solve this noise-free high-degree system of equations. Hence, O n 2T +1 equations are required. However, since χ α,q is a discrete Gaussian, requesting more samples also increases the probability that the noise of at least one sample falls outside of the chosen interval {-T, . . . , T } implying that, as the number of samples grows, so does T , which then requires a further increase in the number of samples. More samples make the problem easier but at the same time more samples make the problem harder (cf. Section 3). These opposing characteristics of the Arora-Ge algorithm naturally propose the application of algorithms for solving non-linear systems of equations when the number of samples is restricted. Indeed, linearisation is a special case of computing a Gröbner basis, a notion going back to the seminal work of Buchberger [START_REF] Buchberger | Ein Algorithmus zum Auffinden der Basiselemente des Restklassenringes nach einem nulldimensionalen Polynomideal[END_REF][START_REF] Buchberger | Computer algebra symbolic and algebraic computation[END_REF][START_REF] Cox | Ideals, Varieties and Algorithms[END_REF]. Gröbner basis algorithms are fundamental tools in computational commutative algebra and allow to solve systems of equations in degree d when less than O n d equations are available -at the cost of increased computational complexity. Applying the theory of Gröbner bases promises the following advantages over merely applying linearisation. We may hope to reduce the complexity of solving the system even if we are given access to as many samples as we would like. Since Gröbner basis algorithms need less than O n d equations to solve systems and since the number of equations increases the required degree in the Arora & Ge modelling, we may hope to improve the complexity of solving LWE by reduction to non-linear polynomial system solving. After deriving a precise complexity of the basic Arora-Ge algorithm (Section 4), we show that the use of Gröbner bases (cf. Section 2) does indeed yield an exponential speedup for solving LWE but is unlikely to yield a subexponential algorithm (Section 5).

LWE with Binary Errors

We then apply these ideas to a recent variant of LWE proposed by Micianccio and Peikert in [START_REF] Micciancio | Hardness of sis and lwe with small parameters[END_REF]: LWE instances where the components in the error vectors are sampled uniformly in a fixed interval. This generalises an earlier result of Döttling and Müller-Quade [START_REF] Döttling | Lossy codes and a new variant of the learning-with-errors problem[END_REF] who first introduced a variant of LWE with uniform errors whilst keeping a strong security reduction to lattice problems which we reproduce informally below:

Theorem 1 (UniformError-LWE [START_REF] Döttling | Lossy codes and a new variant of the learning-with-errors problem[END_REF]). Let n, m, q be in k O (1) and T ≥ n 1 2 +ǫ for any constant ǫ > 0. Then, solving LWE with parameters n, m, q and independent uniformly distributed errors in {-T, . . . , T } is at least as hard as solving worst-case problems on (n/2)-dimensional lattices to within a factor mq T • n

1 2 +ǫ .
In [START_REF] Micciancio | Hardness of sis and lwe with small parameters[END_REF], the authors further expand this result. They consider uniform errors in a much smaller interval, i.e. T is a constant. For binary errors [START_REF] Micciancio | Hardness of sis and lwe with small parameters[END_REF]Theorem 1.2], they obtain the following result.

Theorem 2 (BinaryError-LWE [START_REF] Micciancio | Hardness of sis and lwe with small parameters[END_REF]). Let n, m = n 1 + Ω 1/log(n) be integers, and q ≥ n O(1) be a sufficiently large polynomially bounded (prime) modulus. Then, solving LWE with parameters n, m, q and independent uniformly random binary errors is at least as hard as approximating lattice problems in the worst-case on Θ n/log(n)dimensional lattices within a factor Õ(

√ n • q).
From now on, we shall denote by BinaryError-LWE the problem of finding s ∈ Z n q from (G, s × G + e) sampled according to L (n) s,U (F2) , i.e. LWE with uniform binary errors. Note, though, that the result of Theorem 2 can be generalised to any uniform error in a bounded interval {-T, . . . , T } [START_REF] Micciancio | Hardness of sis and lwe with small parameters[END_REF]Theorem 4.6].

We note that this problem instance immediately matches the assumption made in the Arora & Ge algorithm where the noise is considered to be bounded by some T . Hence, it is clear that the complexity of solving with uniform error is at most the cost of computing a Gröbner basis for m equations of degree 2T + 1 in n variables. In the binary case, the approach of [START_REF] Arora | New algorithms for learning in presence of errors[END_REF] yields a polynomial-time algorithm as soon as the number of samples m = O n 2 . This is already acknowledged in [START_REF] Döttling | Lossy codes and a new variant of the learning-with-errors problem[END_REF][START_REF] Micciancio | Hardness of sis and lwe with small parameters[END_REF], which only show that BinaryError-LWE remains hard if the number of samples is severely limited. As emphasized in [START_REF] Micciancio | Hardness of sis and lwe with small parameters[END_REF], though, it is a natural open question to investigate the hardness of such LWE variants when the number of sample is (strictly) smaller than the upper bound provided by the Arora & Ge approach. Put differently, there is a gap between m = n 1 + Ω 1/log(n) where the hardness reduces to standard LWE and O(n 2 ) where problem is known to be easy due to the Arora-Ge algorithm. Indeed, applications in lattice-based cryptography typically require the provision of m = O (n) or m = Õ(n) samples, i.e. from within that gap.

In Section 6, we show -under a mild assumption, cf. Section 7 -that BinaryError-LWE can be solved in subexponential time as soon as the number of samples is quasi-linear, typically, m = O (n log log n). Precisely, for such number of samples, there is an algorithm solving BinaryError-LWE with complexity:

O m 2 2 ω n log log log n 8 log log n ,
with ω, 2 ≤ ω < 3 being the linear algebra constant. Currently, the best known value for ω is 2.3728639 [START_REF] Coppersmith | Matrix multiplication via arithmetic progressions[END_REF][START_REF] Franc | Powers of tensors and fast matrix multiplication[END_REF]. We also derive precise complexity bounds for BinaryError-LWE with m = O (n). Let

H 2 (x) = -x log 2 (x) -(1 -x) log 2 (1 -x)
be the binary entropy, and assume that m = C • n, with C ≥ 1. Then we show that there is an algorithm solving BinaryError-LWE in

O n 2 2 ω n(1+β) H2( β 1+β ) (time) and O n 2 2 2n(1+β) H2( β 1+β ) (memory) with β = C -1 2 -C(C -1)
. More concretely, we can solve BinaryError-LWE in dimension n in time n 2 • 2 0.344 n using a memory n 2 • 2 0.289 n as soon as m ≥ 6.6 n. This is better than the best currently-known generic (exact) CVP solver [START_REF] Becker | Solving shortest and closest vector problems: The decomposition approach[END_REF] (time 2 0.377 n using memory 2 0.029 n ). As a consequence, our results provide a good picture of the hardness degradation of BinaryError-LWE for a number of samples ranging from m = n 1 + Ω 1/log(n) to m = O n 2 which addresses an open question by Micciancio and Peikert. Whilst our results does not contradict the hardness result of [START_REF] Micciancio | Hardness of sis and lwe with small parameters[END_REF], they certainly rule out BinaryError-LWE for cryptographic applications requiring a quasi-linear number of samples.

Fröberg's Conjecture and Arora-Ge Equations

The results in this work depend crucially on two algebraic assumptions on the algebraic systems considered. The assumption is as follows for BinaryError-LWE:

Assumption 2. Let (G, s × G + e) = (G, c) ∈ Z n×m q × Z m q be sampled according to L (n)
s,U (F2) , and let P (x) = X(X -1). We define:

f 1 = P c 1 - n j=1 s j G j,1 = 0, . . . , f m = P c m - n j=1 s j G j,m = 0.
It holds that f 1 , . . . , f m is semi-regular (Definition 3, Section 2).

For LWE, Assumption 1 is similar but we consider a polynomial P (X) = X CGB•σ i=1 (X + i)(X -i), where C GB depends on the Gaussian distribution. The motivation of these assumptions is that the complexity of computing the Gröbner basis of semi-regular sequences is well mastered. One can compute a Gröbner basis (Proposition 1, Section 2) of a semi-regular sequence

f 1 , . . . , f m ∈ Z q [x 1 , . . . , x n ] in O mD reg n + D reg D reg ω , as D reg → ∞,
where D reg can be computed explicitly from the Hilbert polynomial given in [START_REF] Akavia | Simultaneous hardcore bits and cryptography against memory attacks[END_REF]. Hence, semi-regular sequences are a family of algebraic systems for which the complexity can be explicitly and easily computed [START_REF] Bardet | Étude des systèmes algébriques surdéterminés[END_REF][START_REF] Bardet | Complexity study of Gröbner basis computation[END_REF][START_REF] Bardet | On the complexity of Gröbner basis computation of semi-regular overdetermined algebraic equations[END_REF][START_REF] Bardet | Asymptotic behaviour of the degree of regularity of semi-regular polynomial systems[END_REF].

It is believed that semi-regular sequences capture rather precisely the behaviour of random system of equations. Our semi-regularity assumptions essentially states that our systems are not easier and not harder to solve than a random system of equations. We note that that in algebraic cryptanalysis efficient attacks are only reported in the case that the degree of regularity for the systems considered is much smaller than the degree of regularity of semi-regular systems (for instance, see the attack against HFE [START_REF] Faugère | Algebraic cryptanalysis of hidden field equation (hfe) cryptosystems using gröbner bases[END_REF]). If Arora-Ge-style systems were easier than random systems this would imply that the analysis of Section 5 could be much improved and lead to progress towards a subexponential classical algorithm for solving GAPSVP. Furthermore, to verify that Assumption 1 and 2 hold, we experimentally confirmed that they hold for reasonably large parameters in Section 7.1. For BinaryError-LWE, we have checked the assumption for n up to 53. In LWE, we can only check our assumption up to n = 8 due to the high degree of equations (n = 8 already requires 65GB of RAM). We note that the fact that semi-regular sequences captures the behaviour of random sequences of polynomials is related to a famous conjecture in algebraic geometry known as Fröberg's conjecture [START_REF] Fröberg | An inequality for Hilbert series of graded algebras[END_REF] which states that semiregular sequences form a dense subset among the set of all sequences. More precisely, the Fröberg conjecture states that a property -i.e. the rank of some linear map associated to Macaulay matrices (the matrices occurring in a Gröbner basis computation) is maximal -holds generically.

A property is said to be generic if it holds on a Zariski open subset Z O when the characteristic of K is 0. In Zariski's topology, a close subset is defined defined as the vanishing set of algebraic equations. Hence, we can find a polynomial h(a) in Z[a] which does not depend on the field K such that h(a) = 0 ⇒ a ∈ Z O . The main difficulty in Fröberg's conjecture is to prove that the polynomial h is not identically zero or that Z O is not empty (see [START_REF] Fröberg | Hilbert series for ideals generated by generic forms[END_REF]).

To prove Fröberg's conjecture, it is then sufficient to find one explicit family of polynomials which can be proven semi-regular for any m and n. Proving Assumption 1 or 2 would provide such family and hence solve Fröberg's conjecture. Furthermore, any non-trivial partial results on our assumptions would lead to progress on the general Fröberg's conjecture.

Fröberg's conjecture is proved in very few cases: bi-variate sequences, and tri-variate sequences in characteristic 0 or over a sufficiently big finite field, sequences with the same number of polynomials (m) and same number of variables (n), m = n + 1 in characteristic 0, m polynomials of degree 2 with n ≤ 11, and m polynomials of degree 3 with n ≤ 8 [20, [START_REF] Fröberg | An inequality for Hilbert series of graded algebras[END_REF][START_REF] Fröberg | Hilbert series for ideals generated by generic forms[END_REF].

We note that Fröberg and Hollman [START_REF] Fröberg | Hilbert series for ideals generated by generic forms[END_REF] already investigated the question of semi-regularity for powers of generic linear forms. In characteristic 0, [29, Lemma 2.1] proves that a sequence of n + 1 squares of generic linear forms in n variables is generically semi-regular. Assumption 1 and 2 state that powers of random affine forms behave as semi-regular sequences.

A technical difficulty for proving results towards Fröberg's conjecture is that over a finite field, the notion of Zariski open set is meaningless due to the field equations. However, the notion of genericity can be understood via the classical Schwartz-Zippel-DeMillo-Lipton [START_REF] Demillo | A probabilistic remark on algebraic program testing[END_REF][START_REF] Schwartz | Fast probabilistic algorithms for verification of polynomial identities[END_REF][START_REF] Zippel | Probabilistic algorithms for sparse polynomials[END_REF].

Lemma 1 (Schwartz, Zippel, DeMillo, Lipton [START_REF] Demillo | A probabilistic remark on algebraic program testing[END_REF][START_REF] Schwartz | Fast probabilistic algorithms for verification of polynomial identities[END_REF][START_REF] Zippel | Probabilistic algorithms for sparse polynomials[END_REF]). Let K be a field and P ∈ K[x 1 , . . . , x n ] be a nonzero polynomial. Select r 1 , . . . , r n uniformly at random from a finite subset X of K. Then, the probability that P (r 1 , . . . , r n ) = 0 is less than deg(P )/|X |.

The Fröberg conjecture, being related to rank defects of certain matrices, can be easily interpreted algebraically as the vanishing of some determinants. The difficult task is to prove that these determinants are non-zero. The determinant polynomials involved being of high degree, they can not be expanded symbolically. But, these determinant polynomials can be efficiently evaluated. So, a classical strategy to prove that such polynomials are non-zero is to find an explicit family for which the determinants can be proven to be non-zero. This allows to understand why a core difficulty of Fröberg's conjecture is to find only one explicit example.

In this paper, we report some progress towards proving Fröberg conjecture by investigating our assumptions. The first step to prove our assumptions is to show that the algebraic equations constructed are linearly independent. In Theorem 9 (Section 7.2), we prove that the equations f 1 , . . . , f m generated for BinaryError-LWE are linearly independent with high probability. Another necessary condition implies by Assumption 2 is that the sequence f 1 , . . . , f m is semigeneric (Definition 4), i.e. {x i • f j } 1≤j≤n 1≤i≤n spans a vector space of maximal dimension. For BinaryError-LWE, we prove that such algebraic independence at low degree holds with m ≤ n + ⌊ n-2 2 ⌋ (Theorem 13, Section 7.2). This improves on a result of [START_REF] Fröberg | Hilbert series for ideals generated by generic forms[END_REF]Theorem 2.2] where Fröberg and Hollman proved that the squares of m generic linear forms are semigeneric as long as m ≤ n + 15 and n ≤ 6. In Section 7.2, we finally consider algebraic independence at higher degree. We have been able to prove that the assumption for BinaryError-LWE for m = n + 1 (Theorem 12, Section 7.2) for a field which is big enough.

Preliminaries

Algorithms for computing Gröbner bases are a fundamental tool in computational commutative algebra and one of the main tools for solving systems of non-linear polynomial equations over finite fields. Lazard [START_REF] Lazard | Gröbner-bases, Gaussian elimination and resolution of systems of algebraic equations[END_REF] showed that computing the Gröbner basis for a system of homogeneous polynomials f 1 . . . , f m is equivalent to perform Gaussian elimination on the Macaulay matrices M acaulay (f 1 . . . , f m ) is defined as the coefficient matrix of (t i,j • f i ) where 1 ≤ i ≤ m and t i,j runs through all monomials of degree ddeg(f i ). It can be shown that Macaulay matrices up to degree d can be used to compute a partial Gröbner basis, called d-Gröbner basis. For d big enough, a d-Gröbner basis is a Gröbner basis and we have the following result: Theorem 3 ( [START_REF] Lazard | Gröbner-bases, Gaussian elimination and resolution of systems of algebraic equations[END_REF]). Let q be a prime and let f = (f 1 , . . . , f m ) ∈ (Z q [x 1 , . . . , x n ]) m be homogeneous polynomials and ≺ be a monomial ordering. There exists a positive integer D for which Gaussian elimination on all

M acaulay d,m (f 1 , . . . , f m ) matrices for d, 1 ≤ d ≤ D computes a Gröbner basis of f 1 , . . . , f m w.r.t. to ≺.
It follows that the complexity of computing a Gröbner basis is bounded by the complexity of performing Gaussian elimination on the Macaulay matrices up to some degree D. In general, computing the maximum degree occurring in a Gröbner computation is a difficult problem. However, this degree is precisely known for a specific family of polynomial systems [START_REF] Bardet | Étude des systèmes algébriques surdéterminés[END_REF][START_REF] Bardet | Complexity study of Gröbner basis computation[END_REF][START_REF] Bardet | On the complexity of Gröbner basis computation of semi-regular overdetermined algebraic equations[END_REF][START_REF] Bardet | Asymptotic behaviour of the degree of regularity of semi-regular polynomial systems[END_REF].

Definition 3 (Semi-regular Sequence [START_REF] Bardet | On the complexity of Gröbner basis computation of semi-regular overdetermined algebraic equations[END_REF][START_REF] Bardet | Asymptotic behaviour of the degree of regularity of semi-regular polynomial systems[END_REF]). Let m ≥ n, and f 1 , . . . , f m ∈ Z q [x 1 , . . . , x n ] be homogeneous polynomials of degrees d 1 , . . . , d m respectively and I the ideal generated by these polynomials. The system is said to be a semi-regular sequence if the Hilbert polynomial [START_REF] Cox | Ideals, Varieties and Algorithms[END_REF] associated to I w.r.t. the grevlex order is:

HP(z) = m i=1 (1 -z di ) (1 -z) n + , (1)
with [S] + being the polynomial obtained by truncating the series S before the index of its first non-positive coefficient.

We shall call degree of regularity of a semi-regular sequence the quantity :

1 + deg HP(z) .
This degree of regularity is the degree D involved in Theorem 3 for a semi-regular sequence. Finally, let f 1 , . . . , f m ∈ Z q [x 1 , . . . , x n ] be a sequence of affine polynomials. We denote by f H 1 , . . . , f H m ∈ Z q [x 1 , . . . , x n ] the corresponding homogeneous components of highest degree. We shall say that f 1 , . . . , f m is semi-regular if the sequence f H 1 , . . . , f H m is semi-regular. In this paper, we will use the assumptions that the algebraic equations considered in our approaches behave as semiregular sequences. Throughout this paper, we use intensively the following complexity results about semi-regular sequences.

Proposition 1 (adapted from [START_REF] Bardet | On the Complexity of the F5 Gröbner basis Algorithm[END_REF]).

Let f = (f 1 , . . . , f m ) ∈ (Z q [x 1 , . . . , x n ]) m be affine polynomials with m > nn. If f 1 , . . . , f m is semi-regular,
then the number of operations in Z q required to compute a Gröbner basis for any admissible order is bounded by:

O mD reg n + D reg D reg ω , as D reg → ∞, (2)
where 2 ≤ ω < 3 is the linear algebra constant and D reg is the degree of regularity of f 1 , . . . , f m .

Note that (2) is actually the cost of computing a Gröbner basis with a grevlex ordering. To change the ordering, we have also to use FGLM [START_REF] Faugère | Efficient computation of zero-dimensional Gröbner bases by change of ordering[END_REF] whose complexity is polynomial in the degree of the ideals. For semi-regular sequences, this is equal to the number of solutions counted with multiplicities. This part can be ignored for m > n (see for instance [START_REF] Bettale | Hybrid Approach for solving multivariate systems over finite fields[END_REF]). Note that the complexity bound ( 2) is rather pessimistic as we do not take into account the particular structure of the matrices involved. Typically, the Macaulay matrices considered have huge rank defects which correspond to useless computations. More recent algorithms such as F 4 and F 5 [START_REF] Faugère | A new efficient algorithm for computing Gröbner bases (F4)[END_REF][START_REF] Faugère | A new efficient algorithm for computing Gröbner bases without reduction to zero (F5)[END_REF]) are actually trying to take advantage as much as possible of the structure of Macaulay matrices. This leads to considerable speed-up for practical applications [START_REF] Faugère | Cryptanalysis of minrank[END_REF][START_REF] Faugère | Algebraic cryptanalysis of hidden field equation (hfe) cryptosystems using gröbner bases[END_REF] and in theory as well [START_REF] Bardet | On the Complexity of the F5 Gröbner basis Algorithm[END_REF]. However, to simplify the asymptotical analysis we will consider Lazard's algorithm (Theorem 3) which performs row reductions on Macaulay matrices. Finally, the following classical approximation of the binomial coefficient due to Stirling will be useful to prove some of our results below.

Lemma 2. Let H 2 (x) = -x log 2 (x) -(1 -x) log 2 (1 -x)
log n + D D ≈    D log(n/D), if D ∈ o(n), n log(D/n), if n ∈ o(D).
This follows easily from Stirling's expansion of the binomial.

Arora & Ge

The Arora & Ge algorithm proceeds by generating a non-linear noise-free system of equations from LWE samples. In the construction of such a system, it makes use of the following well-known fact about the Gaussian distribution.

Lemma 4. Let χ denote the Gaussian distribution with standard deviation σ. Furthermore, for x > 0, we denote

Q(x) = 1 2 1 -erf x √ 2
. Then, for all C > 0, it holds that:

Pr[e $ ← χ : |e| > C • σ] ≈ 2 × Q(C) ≤ 2 C √ 2π e -C 2 /2 ∈ e O(-C 2 ) .
That is, for a C > 0, elements sampled from a Gaussian distribution take only values on the interval

[-C • σ, . . . , C • σ] of Z q with probability at least 1 -e O(-C 2 ) if we represent elements in Z q as integers in [-⌊ q 2 ⌋, . . . , ⌊ q 2 ⌋]. Moreover, if e $ ← χ then P (e) = 0 for P (X) = X C•σ i=1 (X + i)(X -i), with probability at least 1 -e O(-C 2 ) . Clearly P is of degree 2 C • σ + 1 ∈ O (C • σ). It follows that if (a i , b i ) = (a i , a i , s + e i ) ∈ Z n q × Z q , and e i $ ← χ, then P -b + n j=1 (a i ) (j) x j = 0, (3)
with probability at least 1 -e O(-C 2 ) . Each sample (a i , a i , s + e i ) = (a i , b i ) ∈ Z n q × Z q allows to generate a nonlinear equation of degree 2 C • σ + 1 in the n components of the secret s which holds with probability 1 -e O(-C 2 ) . The Arora & Ge algorithm then proceeds by generating M AG independent equations of the form (3), to be then solved by linearisation. However, a value for C -denoted by C AG -occurring in Lemma 4 has to be chosen sufficiently large so that all errors e i lie with high probability in the interval [-C AG • σ, . . . , C AG • σ] ⊆ Z q , i.e. such that the secret s is indeed a common solution of the M AG equations. To this end, let S AG be the system of equations generated from M AG equations as in (3) and bound the probability of failure by the union bound:

p f = M AG × Pr[e $ ← χ α,q : |e| > C AG • σ] ≤ M AG e O(C 2 AG )
.

Hence, p f is the probability of failure of the Arora & Ge algorithm, i.e. it is an upper bound on the probability that the secret s ∈ Z n q is not a solution to S AG . Let also D AG = 2 C AG σ + 1 be the degree of the equations occuring in S AG . It is shown in [START_REF] Arora | New algorithms for learning in presence of errors[END_REF] (cf. Section 4) that taking C AG ∈ Õ(σ) allows us to make the probability of failure negligible. In summary, the Arora & Ge algorithm reduces solving LWE to linearisation of a system of M AG equations of degree

D AG = 2 C AG σ + 1 ∈ Õ(σ 2 ).
In particular, the following theorem holds: DAG) equations as in (3) has at most one solution with high probability.

Theorem 4 ( [3]). Let D AG < q. The system obtained by linearizing M AG = O n+DAG DAG ω σ q log q = n O(DAG) = 2 Õ(
Note that O n+DAG DAG equations is sufficient to linearise the system. The extra factor σ q log q allows to prove that the linearised system has at most one solution with high probability [START_REF] Arora | New algorithms for learning in presence of errors[END_REF]. The overall complexity of the Arora-Ge algorithm is the cost of performing Gaussian elimination on a matrix of size M AG × n+DAG DAG , i.e.

C plx AG = n O(DAG) = 2 Õ(σ 2 ) = 2 Õ(n 2ǫ ) .
Note also that, if we have the standard deviation σ = n ǫ , then the algorithm requires 2 Õ(n 2ǫ ) LWE samples for performing the linearisation step. It follows that the Arora & Ge algorithm is subexponential when ǫ < 1/2.

Refined Analysis of Arora & Ge

However, the above analysis and the analysis in [START_REF] Arora | New algorithms for learning in presence of errors[END_REF] leaves room for improvements as it hides not only constants in the exponent but also logarithm factors. In this section we address this issue so we can then compare potential improvements due to the application of Gröbner bases in Section 5. As established in the previous section, the overall complexity of solving an LWE instance with the Arora & Ge algorithm is that of executing Gaussian elimination on a matrix of size M AG × n+DAG DAG . Gaussian elimination on an m × n matrix of rank r has complexity O mnr ω-2 [START_REF] Jeannerod | Rank-profile revealing Gaussian elimination and the CUP matrix decomposition[END_REF]. The Arora & Ge algorithm hence has a complexity of

O M AG • n + D AG D AG ω-1 = O M AG • n + 2 C AG σ + 1 2 C AG σ + 1 ω-1
.

Hence, we need to bound C AG .

Lemma 5. Let n, q, σ = α•q be parameters of an LWE χα,q instance where q = poly(n). Let p ′ f ∈ [0, 1] be a constant upper bound on the probability of failure and

C AG ≤ 2 σ log n + a 1/2 ≈ 4 σ log n, with a = 4(σ log n) 2 + 2 log(σ q log q) -2 log p ′ f + 2 log n. Finally, let also D AG = 2 C AG σ + 1.
Then, the system obtained by linearizing n+DAG DAG σ q log q equations of degree as in (3) is correct, i.e. the secret is a zero of all the polynomials, with probability bigger than 1 -p ′ f .

Proof. The probability of failure is upper bounded by by:

p f = M AG × Pr[e $ ← χ α,q : |e| > C AG • σ] ≈ 2 n+DAG DAG σ q log q √ 2π C AG e C 2 AG /2 < n+DAG DAG σ q log q C AG • e C 2 AG /2 .
We bound n+DAG DAG by n DAG . While this approximation is rather loose, it allows to simplify our expression sufficiently to recover a closed form of the complexity. With this simplification, our goal is to find C AG such that:

0 ≤ n DAG • σ q log q C AG • e C 2 AG /2 = p ′ f ≤ 1.
That is: e log σ q log q e (2 CAG σ+1) log n

e log p ′ f • e log CAG • e C 2 AG /2 = 1.
Namely, we want to solve

0 = log(σ q log q) + 2 C AG σ log n + log n -log C AG -log p ′ f -C 2 AG /2 > log(σ q log q) + 2 C AG σ log n + log n -log p ′ f -C 2 AG /2
for C AG . The last line has 2 roots:

[R 1 = 2 σ • log(n) -a 1/2 , R 2 = 2 σ • log(n) + a 1/2 ],
with a = 4(σ log n) 2 + 2 log(σ q log q) -2 log p ′ f + 2 log n. Note that a 1/2 > 2 σ log(n) and hence R 1 < 0. Thus, the smallest possible value for C AG is R 2 . Now, assume that q ∈ poly(n), i.e. q ≈ n c . Also, recall that p ′ f is a constant. Thus, for n big enough:

a = 4(σ log n) 2 + 2 log(σ q log q) -2 log p ′ f + 2 log n = 4(σ log n) 2 + 2c log(σ n c log n) -2 log p ′ f + 2 log n ≈ 4(σ log n) 2 .

So, we have

C AG ≤ 2 σ log n + a 1/2 ≈ 4 σ log n.

⊓ ⊔

We hence arrive at the following theorem:

Theorem 5. Let n, q, σ = α • q be parameters of an LWE χα,q instance. If D AG (= 8 σ 2 log n + 1) ∈ o(n) then the Arora & Ge algorithm solves the computational LWE problem in time complexity

O 2 ω•DAG log n D AG • σ q log q = O 2 8 ω σ 2 log n(log n-log(8 σ 2 log n)) • poly(n)
and memory complexity

O 2 2•DAG log n D AG • σ q log q = O 2 16 σ 2 log n(log n-log(8 σ 2 log n)) • poly(n) .
If n ∈ o(σ 2 log(n)) then the Arora & Ge algorithm solves the computational LWE problem in time complexity

O 2 ω•n log D AG n • σ q log q = O 2 ω n log(8 σ 2 log n)-n log n • poly(n)
and memory complexity

O 2 2n log D AG n • σ q log q = O 2 2n log(8 σ 2 log n)-n log n • poly(n) .
Proof. The result follows immediately from plugging the Lemmata 3 and 5 into Theorem 4.

This establishes a baseline to compare any potential improvements due to the application of Gröbner basis algorithms with.

Solving LWE with Gröbner Bases

We are now ready to address the question if the complexity of the basic Arora & Ge algorithm can be improved by using Gröbner bases instead of linearisation. Let the notation be as in Section 4. The motivation for this section is that the constant C AG (and hence the degree of the equations) depends on the number of equations M AG considered.

Hence, on the one hand, we may lower the number of equations to a value smaller than Õ(n 2 ǫ ) whilst keeping the probability of failure small enough. On the other hand, this means that the cost of solving the resulting system will grow compared to that of linearisation. The optimisation target is then to find a tradeoff allowing to improve upon linearisation.

We assume that σ = n ǫ , with ǫ,

0 ≤ ǫ ≤ 1. Let also θ, 0 ≤ θ ≤ ǫ ≤ 1.
We consider a number of samples of the following form:

M GB = e γ θ , with γ θ = n 2•(ǫ-θ) .
Note that θ = 0 corresponds up to polylog factors to the basic Arora-Ge approach. To explain the rational for the choosing this form for M GB the number of samples we state below a simple lemma which relates the number of samples considered to the degree of the multivariate equations: Lemma 6. Let (a 1 , b 1 ), . . . , (a m , b m ) be elements of F n q × F q sampled according to LWE χα,q . If C = 2 log(m) then, the equations generated as in (3) vanish with probability at least:

p g = 1 - 1 π • log(m)
.

Proof. By Lemma 4, the probability of failure verifies

≤ 2 m C √ 2π e -C 2 /2 = 2m 4π • log(m) e - √ 2 log(m) 2 /2 = m π • log(m) e -log(m) = 1 π • log(m)
.

From this the probably of success

p g ≥ 1 -p f follows. ⊓ ⊔ Remark 1. If m ∈ O (n) then it holds that p g ∈ 1 -o(1).
We can then deduce the degree D GB required for M GB = e γ θ equations. From Lemma 6, we have to fix

C GB = 2 • log(M GB ) = √ 2 • γ θ . Thus: D GB = 2 2 • log(M GB ) • σ + 1 ∈ O log(M GB ) • σ = O ( √ γ θ • σ) = O n 2ǫ-θ = O γ θ • n θ .
But to ease the analysis below, we further simplify D GB to:

D GB ≈ γ θ • n θ = log(M GB ) • n θ .
Furthermore, we restrict our attention to the case σ = √ n/ √ 2π. Now, in order to analyse the complexity of the Gröbner basis computation, we need to make the following assumption about the structure of the generated equations:

Assumption 1 Let (a 1 , b 1 ), . . . , (a MGB , b MGB ) be elements of F n q × F q sampled according to LWE χα,q . Let P (X) = X CGB•σ i=1 (X + i)(X -i).
We define:

f i = P -b + n j=1 (a i ) (j) x j = 0, ∀i, 1 ≤ i ≤ M GB . (4)
Then, f 1 , . . . , f m is semi-regular.

We justify this assumption in Section 7.

From D GB and M GB we now need to establish the degree of regularity. Whilst there are classical results on the degree of regularity in the literature, these do not apply here. In particular, we need to consider systems of equations having a non-constant degree. For brevity and due to the fact a detailed analysis is beyond the scope of this paper, we only provide the general statement which allows to derive the result below in Appendix A (Proposition 3).

Lemma 7. Let A ≥ 1, and f 1 , . . . , f m ∈ Z q [x 1 , . . . , x n ] be semi-regular polynomials of degree n A , and D reg be the degree of regularity of these polynomials. If m = e π•n 4•A 2 , then3 it holds that D reg behaves asymptotically as

C A • n, where C A is a constant which depends on A.
The constant C A in the Lemma can be computed explicitly for any value of A as explained in Proposition 3. For A = 1, we get in particular that D reg = 1.41 • n, for n big enough. Putting all these results together we can now derive the complexity of solving LWE using a Gröbner basis algorithm. Theorem 6. Let A ≥ 1, ω, C A be as defined in Lemma 7, ω, 2 ≤ ω < 3, be the linear algebra constant, and

H 2 (x) = -x log 2 (x) -(1 -x) log 2 (1 -x). Let (a i , b i ) i≥1 be elements of F n
q × F q sampled according to LWE χα,q with a standard deviation σ = √ n √ 2π and A ≥ 1. There is an algorithm recovering the secret in

O 2 n ω (1+C A ) H2 C A 1+C A + π•log 2 (e) 4•A 2 (time) and O 2 n 2 (1+C A ) H2 C A 1+C A + π•log 2 (e) 4•A 2 (memory), ( 5
)
The algorithm has success probability ≥ 1 -

2 π √ n = 1 -o(1).
Proof. Let M GB = e π•n 4•A 2 and D GB = n/A. We generate a system of M GB non-linear equations of degree D GB as (4). Under our regularity assumption 1, the complexity of computing a Gröbner basis for this system is:

O n e π•n 4•A 2 n(1 + C A ) C A n ω , (6)
Combining this with Lemma 2 gives the complexity. By Lemma 4, the probability of failure verifies is

≤ 2 m C √ 2π e -C 2 /2 . In our case, C ≈ √ 2πn 2
which gives a failure probability

≤ 2 π √ n . ⊓ ⊔
Note that the complexities in Theorem 6 are minimized by taking a constant A = 1. So, we get a complexity of O 2 n 2.35 ω+1. 13 (time) and O 2 5.85 n (memory). As a consequence we have that using Gröbner bases yields an exponential speed-up (for σ = √ n/ √ 2π and under Assumption 1) over the basic Arora-Ge approach (cf. Theorem 5). On the other hand, our results also give a negative answer to the natural question whether the combination of Gröner basis techniques with the Arora-Ge modelling can yield a subexponential algorithm for the LWE problem. From Lemma 7, one can notice that there is no choice of A (constant, log n, . . . ) which makes the number of samples sub-exponential whilst keeping the degree of regularity sub-linear.

Solving LWE with Bounded Errors

We now turn to studying the complexity of solving BinaryError-LWE using the modelling of Arora & Ge [START_REF] Arora | New algorithms for learning in presence of errors[END_REF] and applying a Gröbner basis algorithm for solving the resulting system of equations. As discussed earlier, BinaryError-LWE is an LWE instance over Z q but with errors restricted to the binary field, as in [START_REF] Micciancio | Hardness of sis and lwe with small parameters[END_REF]. Generating noise-free non-linear equations is straightforward in this case: if e = (e 1 , . . . , e m ) ∈ {0, 1} m and P (X) = X(X -1), then we have P (e i ) = 0, for all i,

1 ≤ i ≤ m. Now, let (G, s × G + e) = (G, c) ∈ Z n×m q × Z m q be sampled according to L (n) s,U (F2)
. Then

e i = c i - n j=1 s j G j,i , for 1 ≤ i ≤ m.
It follows that the secret s ∈ Z n q is a solution of the following algebraic system:

f 1 = P c 1 - n j=1 s j G j,1 = 0, . . . , f m = P c n - n j=1 s j G j,n = 0. (7)
This is an algebraic system of m quadratic equations in Z q [x 1 , . . . , x n ]. As already pointed out in [START_REF] Arora | New algorithms for learning in presence of errors[END_REF][START_REF] Micciancio | Hardness of sis and lwe with small parameters[END_REF], this system can be solved using linearization if m = O n 2 . However the case m < O n 2 remained untreated. Here, we address this problem of evaluating the complexity of solving the algebraic system [START_REF] Bardet | On the Complexity of the F5 Gröbner basis Algorithm[END_REF] with an arbitrary number m of equations.

As discussed in Section 2, answering this question in general is hard. But for one particular class of systems, namely semi-regular systems of equations, this question has in fact been settled. In particular, the following result [START_REF] Bardet | Étude des systèmes algébriques surdéterminés[END_REF][START_REF] Bardet | Complexity study of Gröbner basis computation[END_REF][START_REF] Bardet | On the complexity of Gröbner basis computation of semi-regular overdetermined algebraic equations[END_REF][START_REF] Bardet | Asymptotic behaviour of the degree of regularity of semi-regular polynomial systems[END_REF] allows us to classify the complexity of solving polynomial systems with respect to the number of equations.

Theorem 7. (i) Let m = C • n, with C > 1, and let f 1 , . . . , f m ∈ Z q [x 1 , . . . , x n ] be a semi-regular system of equations. The degree of regularity of f 1 , . . . , f m behaves asymptotically as

D reg = C - 1 2 -C(C -1) n - a 1 2 C(C -1) 1/6 n 1 3 -2 - 2C -1 4 C(C -1) 1/2 + O 1 n 1 3
, where a 1 ≈ 2.3381 is the largest zero of the classical Airy function.

(ii) Let m = n • log 1/ǫ (n), for any constant ǫ > 0, or m = n log log n. The degree of regularity of f 1 , . . . , f m behaves asymptotically as:

D reg = n 2 8m (1 + o(1)) .
A proof of i) can be found, for instance, in [8, Theorem 1]. A proof similar to the case of ii) can be found in [START_REF] Bardet | Complexity study of Gröbner basis computation[END_REF]. However, there is slight difference between [START_REF] Bardet | Complexity study of Gröbner basis computation[END_REF] (binary fields) and our case (generic prime fields). In Appendix A we briefly sketch a proof for ii) of Theorem 7.

Hence, under the assumption that the system (7) behaves like a semi-regular system of equations, Theorem 7 allows one to compute an upper bound on the complexity for solving it with Gröbner basis algorithms. While no proof currently exists that would demonstrate that the system (7) does indeed behave like a semi-regular system, we make the following assumption based on the discussion in Section 7.

Assumption 2 Let (G, s × G + e) = (G, c) ∈ Z n×m q × Z m q be sampled according to L (n)
s,U (F2) , and let P (x) = X(X -1). We define:

f 1 = P c 1 - n j=1 s j G j,1 = 0, . . . , f m = P c n - n j=1 s j G j,m = 0. ( 8
)
It holds that f 1 , . . . , f m is semi-regular.

Based on Assumption 2, we can now state the main result of this section. We classify the hardness of our approach with various number of samples. The first one corresponds to the number of equations required in the security proof [START_REF] Micciancio | Hardness of sis and lwe with small parameters[END_REF]Theorem 1.2]. We then consider a slightly larger number of equations than what is required in the security proof, i.e. m = 2n equations. In addition we give the results for a quasi-linear number of equations.

Theorem 8. Let ω, 2 ≤ ω < 3, be the linear algebra constant, and

H 2 (x) = -x log 2 (x) -(1 -x) log 2 (1 -x).
Under Assumption 2, we have the following.

(i) If m = n 1 + 1 log(n) , then there is an algorithm solving BinaryError-LWE with a time complexity:

O n 2 2 1.37 ω n . ( 9
)
(ii) If m = 2 • n, then there is an algorithm solving BinaryError-LWE with a time complexity

O n 2 2 0.43 ω n . ( 10
) (iii) More generally, if m = C • n, with C > 1,
there is an algorithm solving BinaryError-LWE in:

O n 2 2 ω n(1+β) H2( β 1+β ) (time) and O n 2 2 2n(1+β) H2( β 1+β ) (memory), ( 11
)
with β = C -1 2 -C(C -1) . (iv) If m = O (n log log n),
) (v) Finally, if m = n • log 1/ǫ (n), 12
for any ǫ > 0, then there is a subexponential algorithm solving BinaryError-LWE whose complexity is:

O   m 2 2 ω n log log 1/ǫ (n) 8 log 1/ǫ (n)   (time), O   m 2 2 2n log log 1/ǫ (n) 8 log 1/ǫ (n)   (memory). ( 13
)
Proof. As explained Section 2, the complexity of computing a Gröbner basis is:

O m D reg n + D reg D reg ω (time), O m D reg n + D reg D reg 2 (memory). ( 14
)
Under our semi-regularity assumption, Theorem 7 gives:

D reg = 0.5 • n + o(n) for m = n 1 + 1 log(n) , D reg = 0.08 • n + o(n) for m = 2 • n and more generally D reg = C -1 2 -C(C -1) n + o(n) for m = C • n, for any constant C > 1.
In these cases, the binomial coefficient in [START_REF] Brakerski | Efficient fully homomorphic encryption from (standard) LWE[END_REF] has the following form:

α • n β • n
, for some α > β > 0.

We obtain ( 9) -( 11) by taking β = C -1 2 -C(C -1) by applying Lemma 2. For ( 12) and ( 13), we combine Lemma 3 and Theorem 7.

⊓ ⊔

It follows from Theorem 8 that we can solve BinaryError-LWE in dimension n in time n 2 2 0.344 n using memory n 2 2 0.289 n as soon as as soon as m ≥ 6.6 n. We note that this is better than the best currently-known generic (exact) CVP solver [START_REF] Becker | Solving shortest and closest vector problems: The decomposition approach[END_REF]. Theorem 8 also provides a good picture of the hardness degradation of BinaryError-LWE for the number of available samples ranging from m = n 1 + Ω 1/log(n) , a case for which BinaryError-LWE is as hard as solving some lattice problem in the worst case (as shown in [START_REF] Micciancio | Hardness of sis and lwe with small parameters[END_REF]) to m = O n 2 , the case for which it can be solved in polynomial-time. In view of items (iv)-(v) of Theorem 8, we conclude that BinaryError-LWE should be ruled out for cryptographic applications that require a quasi-linear number of samples.

Justifications of our Assumptions

The results in this work depend crucially on two assumptions, namely that all systems of equations occurring in this work are semi-regular. While no proof currently exists that would demonstrate either Assumption 1 or 2, we argue below why we believe these assumptions do indeed hold. As already mentioned, we note that each semi-regularity assumption essentially states that our systems are not easier and not harder to solve than a random system of equations. If Arora-Ge-style systems were easier than random systems this would imply that the analysis of Section 5 could be much improved and lead to progress towards a subexponential classical algorithm for solving Bounded Distance Decoding. Furthermore, this subexponential classical algorithm would work despite ignoring the particular error distribution and would consist of applying a generic Gröbner basis algorithm. We consider this case to be unlikely. Furthermore, we note that Arora & Ge essentially showed in [START_REF] Arora | New algorithms for learning in presence of errors[END_REF] that Assumption 1 holds for m = 2 Õ(σ 2 ) (Theorem 4). Following [START_REF] Arora | New algorithms for learning in presence of errors[END_REF], we prove in Section 7.2 that Assumption 2 holds for m = O n 2 . We also prove in 7.2 several partial results regarding our assumptions. Before this, we report in Section 7.1 on experimental results confirming that our assumptions hold for reasonably large parameters.

Experimental Verification

We experimentally confirmed that our assumptions hold for reasonably large parameters. Namely, we verified Assumption 1 for systems up to n = 8 variables. In particular we computed for n = 8 and m = 256, α • q/ √ 2π = 1 using MAGMA [START_REF] Bosma | The Magma algebra system I: The user language[END_REF] (V2.20-4) and Sage [START_REF] Stein | Sage Mathematics Software Version 6.2. The Sage Development Team[END_REF]. The generated system of equations has degree 9 and the degree of semi-regularity is 13. The highest degree reached was indeed degree 13.

While n ≤ 8 might seem rather small, we point out that it is the last n for which we can reasonably expect to run experiments on current hardware. Theorem 6 bounds the memory complexity by O 2 5.85n . We note that for n = 8, our computation required 65GB of memory and 68 hours to complete. Hence, we would require about 2 5.85 • 65GB of memory to perform this computation for n = 9 which is beyond our reach. Also, to verify Assumption 2, we have generated systems as in [START_REF] Bardet | Asymptotic behaviour of the degree of regularity of semi-regular polynomial systems[END_REF] with m = ⌊n log 2 (n)⌋ equations and n ∈ {5, . . . , 45} variables. We take q as the next prime larger than n (or n 2 in some instances). We then computed a Gröbner basis of the equations using MAGMA. Below we report the maximal degree reached D real in our experiments, and the theoretical degree of regularity D reg , as given by Assumption 2. We note that the largest of these experiments took 7 days to complete.

D reg D real n ∈ {5, . . . , 25} 3 3 n ∈ {26, . . . , 53} 4 4

Formal Proofs in Limited Cases

In this part we provide formal proofs of some statements implied by Assumption 2 as first steps towards proving the assumption itself.

Linear Independence Assumption 2 for BinaryError-LWE implies in particular that the equations ( 8) are linearly independent. Below, we prove that this indeed holds with high probability for any

1 ≤ m ≤ n+1 2 . Theorem 9. Let (G, s×G+e) = (G, c) ∈ Z n×m q ×Z m q be sampled according to L (n)
s,U (F2) , and let P (x) = X(X -1). Assume that q > 2m. Then, for all 1 ≤ m ≤ n+1 2 , the equations

f 1 = P c 1 - n j=1 x j G j,1 , . . . , f m = P c m - n j=1 x j G j,m , (15)
are linearly independent with probability ≥ 1 -2m q . More precisely, the homogeneous components f H 1 , . . . , f H m of degree 2 are linearly independent with probability ≥ 1 -2m q .

Proof. The coefficients of the f i s can be viewed as polynomials of degree ≤ 2 in the components of the matrix G. We denote by N be the number of monomials of degree 2, and by Mac 2 the m × N matrix whose rows are the coefficients of the f H i s. This the Macaulay matrix of the f H i s at degree 2. We assume that the monomials are sorted with respect to a graded reverse lexicographical order. Let Mat 2 be a m × m sub-matrix of Mac 2 . We can view Det(Mat 2 ) as a polynomial p of degree 2m whose variables are the components of G. According to Lemma 9 (Appendix A.2), the polynomial p is non-zero for all 1 ≤ m ≤ n+1

2 . The Schwartz-Zippel-DeMillo-Lipton Lemma (Lemma 1) yields that p(G) = 0 with probability ≥ 1 -2m q . ⊓ ⊔

One can remark that the notion of semi-genericity only depends on the homogeneous components of highest degree. Thus, the polynomial P in Theorem 9 could be replaced by X 2 and the proof will remain the same (also, the constants c i s are irrelevant in the proof). This illustrates that it is equivalent to consider the semi-regularity of the systems as in Assumption 2 or the semi-regularity of the square of linear forms as done by Fröberg and Hollman [START_REF] Fröberg | Hilbert series for ideals generated by generic forms[END_REF].

A consequence of Theorem 9 is:

Corollary 1. Let q > 2m.
There is a polynomial-time algorithm solving BinaryError-LWE with probability 1 -2m q as soon as n < m ≤ n+1 2 .

In [START_REF] Micciancio | Hardness of sis and lwe with small parameters[END_REF], it was mentioned without a proof that BinaryErrors-LWE can be solved in polynomial-time as soon as the number of samples is O n 2 . Precisely, a direct adaptation of [3, Theorem 3.1] to binary noise gives:

Theorem 10. Let (G, s×G+e) = (G, c) ∈ Z n×m q ×Z m q be sampled according to L (n)
s,U (F2) , and let P (x) = X(X-1). The system obtained by linearizing the f i 's, as defined in [START_REF] Buchberger | Ein Algorithmus zum Auffinden der Basiselemente des Restklassenringes nach einem nulldimensionalen Polynomideal[END_REF], has unique solution with probability ≥ 1 -

2 m • q N2-m , with N 2 = n+2
2 . The bound is then non-trivial (< 1) if m ≥ cN 2 , for some constant c > 0.

Proof. We know that s ∈ Z n q is a solution of f 1 , . . . , f m . Given s ′ = s, the idea is to bound the probability that s ′ vanishes simultaneously the linearized system corresponding to f 1 , . . . , f m . By definition, c = (s × G) + e. So, we can write:

f i = P e i - n j=1 (s j -x j )G j,i .
Now by setting x * j = (s j -x j ), we have:

f * i (x * 1 , . . . , x * n ) = f i (s 1 -x * 1 , . . . , s n -x * n ) = P e i - n j=1
x * j G j,i .

Thus, ∃s ′ = s such that f i (s ′ ) = 0 ⇐⇒ ∃ a non-zero s * ∈ Z n q such that f * i (s * ) = 0. We can view f * i (s *
) has a multivariate polynomial of degree 2 in the components of G. Thus, assuming that f * i (s * ) is non-identically zero, it holds that:

Pr (G,c)← $ L (n) s,U (F 2 ) f * i (s * ) = 0 | e i = b ≤ 2/q, with b ∈ {0, 1}.
The fact that the f * i (s * ) is a non-zero polynomial -viewed as a polynomial whose variables in the components of G follows easily from [START_REF] Arora | New algorithms for learning in presence of errors[END_REF]Lemma 3.4].

The same result holds if you replace f * i by its linearization L f * i . Thus, for any

S ′ = s ′ ⊗ s ′ ∈ Z N2 q with s ′ = s ∈ Z n q , it holds that: Pr (G,c)← $ L (n) s,U (F 2 ) L f1 (S ′ ) = 0, . . . , L fm (S ′ ) = 0 = m i=1 Pr (G,c)← $ L (n) s,U (F 2 )
L fi (S ′ ) = 0 .

We then have Pr

(G,c)← $ L (n) s,U (F 2 ) L fi (S ′ ) = 0 = 1 2 Pr (G,c)← $ L (n) s,U (F 2 ) L fi (S ′ ) = 0 | e i = 0 + 1 2 Pr (G,c)← $ L (n) s,U (F 2 ) L fi (S ′ ) = 0 | e i = 1 ≤ 2/q.
Finally, we consider the event E S ′ = "L f1 (S ′ ) = 0, . . . , L fm (S ′ ) = 0". The probability that the linearized system has more than one solution is the probability of the event ∪ S ′ E S ′ which is:

Pr (G,c)← $ L (n) s,U (F 2 )
(linearized system has not unique solution) ≤ 2 m • q N2-m .

⊓ ⊔

Linearization (Theorem 10) requires a number of samples which is a constant times the number of monomials of degree ≤ 2 in n variables ≥ c n+2 2 whilst a Gröbner basis approach (Corollary 1) requires a number of samples equal to the number of monomials of degree exactly 2 in n variables, i.e. n+1

2 . So, Gröbner bases already require a smaller number of samples than linearization to solve BinaryError-LWE in polynomial-time (we compute a Gröbner basis by performing a row reduction on the Macaulay matrix at the degree of the equations).

Algebraic Independence at Low Degree. Semigenericity. We consider algebraic independence at the degree of the equations plus 1. More precisely, following the terminology as in [START_REF] Fröberg | Hilbert series for ideals generated by generic forms[END_REF], we consider the notion of semigenericity. Definition 4. Let f 1 , . . . , f m ∈ Z q [x 1 , . . . , x n ] be homogeneous equations of degree d. We shall say that a sequence of polynomials f 1 , . . . , f m is semigeneric if {x i • f j } 1≤j≤n 1≤i≤n spans a vector space of maximal dimension, i.e. min n • m, d-1+n d . For affine polynomials f 1 , . . . , f m ∈ Z q [x 1 , . . . , x n ], we shall say that the sequence f 1 , . . . , f m is semigeneric if f H 1 , . . . , f H m is semigeneric.

For BinaryError-LWE, this corresponds to investigate Assumption 2 for a Macaulay matrices at degree 3. In [29, Theorem 2.2], the authors prove that the square of m generic linear forms are semigeneric as long as m ≤ n + 15 and n ≤ 6. Here, we prove that system [START_REF] Buchberger | Ein Algorithmus zum Auffinden der Basiselemente des Restklassenringes nach einem nulldimensionalen Polynomideal[END_REF] is semigeneric for m ≤ n + ⌊ n-2 2 ⌋ ≈ ( 3 2 )n; improving then towards [START_REF] Fröberg | Hilbert series for ideals generated by generic forms[END_REF].

Theorem 11. We assume q = Ω(n 2 ). Let (G, s × G + e) = (G, c) ∈ Z n×m q × Z m q be sampled according to

L (n) s,U (F2) . For any m, 1 ≤ m ≤ n + ⌊ n-2
2 ⌋, the sequence (15) is semigeneric with probability ≥ 1 -2mn q . Proof. The strategy is similar to the proof of Theorem 9. Now, let N be the number of monomials of degree 3 and let Mat 3 be a sub-matrix of size m • n × m • n of the Macaulay matrix f H 1 , . . . , f H m at degree 3. We can view Det(Mat 3 ) as a polynomial p of degree 2mn whose variables are the components of G. According to Lemma 11, p is non-zero. Hence, Lemma 1 yields that p(G) = 0 with probability ≥ 1 -2mn q .

⊓ ⊔

We have a found a particular example which could allow to extend Theorem 13 up to m ≈ n 2 / log n (Remark 2). However, although we verified experimentally that the example is semi-generic, we have not been able to prove it formally. Still, a first difficulty in this type of proof is to actually to describe a particular example. The second step is of course to make the proof.

Full Proof of Assumption 2 for m = n + 1. We conclude this part by proving that Assumption 2 holds for m = n + 1 equations. The proof requires however to have field size big enough.

Theorem 12. We assume

q = O (exp(n)). Let (G, s × G + e) = (G, c) ∈ Z n×m q × Z m q be sampled according to L (n)
s,U (F2) , and let P (x) = X(X -1). With probability ≥ 1 -o(1), it holds that the sequence

f 1 = P c 1 - n j=1 x j G j,1 , . . . , f n+1 = P c n+1 - n j=1 x j G j,n+1 is semi-regular.
Proof. It is well known that the degree of regularity of a semi-generic sequence of m = n + 1 equations is ⌈ n+1 2 ⌉. So, we need to prove that the Macaulay matrices associated to f H 1 , . . . , f H n+1 of degree 2 to n+1 2 are of maximal possible rank. That is, the only linear dependencies occurring in the Macaulay matrices are the one induces by the trivial syzygies, i.e. f H i f H j = f H j f H i . Until now, we investigated degrees 2 and 3 for which there is no trivial syzygies. Let [t d ]HP(z) be the dth coefficient of the Hilbert polynomials [START_REF] Akavia | Simultaneous hardcore bits and cryptography against memory attacks[END_REF]. This coefficient gives the rank defects, and then the expected rank, of the Macaulay matrix of f H 1 , . . . , f H m at degree d ≥ 2. As in the previous proofs, we can write easily that Macaulay matrix of f H 1 , . . . , f H m at each degree d has the expected rank if a minor is non-zero. The degree of this minor is O n d-1 . We then conclude the proof by providing an explicit example of a sufficiently generic system of m = n + 1 equations. This is the purpose of the next Lemma.

Lemma 8. Let P (x) = X(X -1). We consider a matrix G * ∈ Z n×n+1 q such that all coefficients are zero except:

-G * [i, i] = 1, for all i, 1 ≤ j ≤ n. -G * [i, n + 1] = 1, for all i, 1 ≤ i ≤ n. Let c = s × G * + e, s ∈ Z n
q be chosen uniformly at random, e ∈ {0, 1} n+1 be sampled uniformly. Then, the sequence

P c 1 - n k=1 x k G * k,1 , . . . , P c n+1 - n k=1 x k G * k,n+1 ∈ Z q [x 1 , . . . ,
      1 1 1 1 1 0 1 0 0 1 0 0 1 0 1 0 0 0 0 1 0 0 0 1 1       .
To conclude this part, we mention that we can adapt all the results of Section 7.2 on BinaryError-LWE to UniformError-LWE (for instance, we have Theorem 14).

Proof. We assume that we have m quadratic equations in n variables. In this case, we have to consider the Hilbert series:

H m,n (z) = 1 -z 2 m (1 -z) n = ∞ d=0 h d z d .
The degree of regularity is the index D reg such that h Dreg < 0. We try to find D reg = ℓ(n) n = ℓ n such that h ℓ n < 0.

To do so, we consider :

h ℓ n = H m,n (z) z ℓ n dz = e f (z) n dz,
where the contour is a circle centered in 0 whose radius is smaller than 1.

In our context:

f (z) = log(H m,n (z)) n = m log 1 -z 2 -n log (1 -z) -n ℓ log (z) n .
Laplace's Method gives then:

h ℓ n ≈ {a|f ′ (a)=0}
e f (a)n .

More details about this preliminary part can be found in the literature, for instance [START_REF] Bardet | Étude des systèmes algébriques surdéterminés[END_REF][START_REF] Bardet | Complexity study of Gröbner basis computation[END_REF][START_REF] Bardet | On the complexity of Gröbner basis computation of semi-regular overdetermined algebraic equations[END_REF][START_REF] Bardet | Asymptotic behaviour of the degree of regularity of semi-regular polynomial systems[END_REF]. As n increases, the integral concentrates in the neighbourhood of one or several saddle points, i.e. the solutions of f ′ = 0.

When the equation f ′ (z) = 0 has two solutions, we have h ℓ n ≈ e f (z -)n + e f (z + )n → ∞. Hence, since when d = D reg = ℓ n we must have h d = 0 this implies that the equation f ′ (z) = 0 has a multiple root.

In our case, we have:

f ′ (z) = 1 1 -z - 2 m z n(1 -z 2 ) - ℓ z .
Now, we set m = n F (n). We have multiple root if the discriminant of f ′ is 0. As a consequence, ℓ = ℓ(n) is the smallest real root of :

4 n 3 F (n) 2 + 4 n 3 -8 n 3 F (n) ℓ 2 + -8 n 3 F (n) 3 -16 n 3 F (n) + 20 n 3 F (n) 2 + 4 n 3 ℓ -2 n 3 F (n) + n 3 F (n) 2 + n 3 .
This yields :

ℓ(n) = F (n) -1/2 -F 2 (n) -F (n) n = 1 8 n F (n) + O n F 2 (n)
.

⊓ ⊔

In Section 5, we use the following result.

Proposition 3. Let α and β be constants > 0, and f 1 , . . . , f m ∈ K[x 1 , . . . , x n ] be semi-regular polynomials of degree αn. We define the function

F (X, ℓ) = log(1+ℓ)-ℓ log(ℓ)+ℓ log(1+ℓ)-log(1+ℓ-X)+log(ℓ-X)ℓ-log(ℓ-X)α -log(1+ℓ-X)ℓ+log(1 +ℓ-X)α -log(β ).
Assuming m = β n , then it holds that:

D reg n ≈ α if α < α 0 PositiveRealRoot F (α, ℓ) , if α 0 ≤ α < 6,
and α 0 is the real value such that F (α 0 , α 0 ) = 0.

We give below the value of α 0 for various β. For β = e π/4 , the degree of regularity is then for instance ≈ 1.41 n. Below, we compare the theoretical degree of regularity obtained from Proposition 3 for various β and α with the degree of regularity obtained by computing the generic Hilbert series (Definition 3). The proof of this result is beyond the scope of this paper. The first step is similar to the the previous Proposition 2, i.e. we use Laplace's method to approximate the coefficient h ℓ n in the Hilbert series. The next step requires different tools that the ones used classically to cancel the coefficient asymptotically. The proof will be presented in an extended version of this paper. To simplify the analysis, it is possible to upper bound uniformly the degree of regularity; that is: Proposition 4. Let α and β be constants > 0, and f 1 , . . . , f m ∈ K[x 1 , . . . , x n ] be semi-regular polynomials of degree αn. If m = β n :

D reg ≤ n • β β -1 For β = e π 4 , we have β β-1 = 1.83.

A.2 Formal Proof in Limited Cases

The example below is used in Theorem 9 to show that the determinant considered is non-zero.

Lemma 9. For all i, 1 ≤ i ≤ n, construct a n × n -(i -1) matrix G i as follows. All the coefficients of G i are zero except:

-G i [i, j] = 1, for all j, 1 ≤ j ≤ n -(i -1) . -G i [j + (i -1), j] = 1, for all j, 1 ≤ j ≤ n -(i -1) . Now, let G * = G 1 G 2 • • • G n be a block matrix, s ∈ Z n
q chosen uniformly at random, and e ∈ {0, 1} m sampled uniformly. We set c = s × G * + e and P (x) = X(X -1) and define:

f 1 = P c 1 - n j=1 x j G * j,1 , . . . , f m = P c m - n j=1 x j G * j,m .
Then, the homogeneous components f H 1 , . . . , f H m of degree 2 are linearly independent.

Proof. Let f i,j be the the jth equation derived from the matrix G i (the equation corresponding to the jth column of the ith matrix G i ) . We start with the simple case m = n where G * = G 1 . The monomial of highest degree in f 1,1 = P (c 1 -x 1 ) is simply x 2 1 . More generally, for all i, 1 ≤ j ≤ n, the monomials of degree 2 in f 1,j = P (c j -x 1 -x j ) are x 2 1 , x 1 x j and x 2 j . Remark then that the system

F 1 := [ f1,1 = f 1,1 , f1,2 = -f 1,1 + f 1,2 , . . . , f1,n = -f 1,1 + f 1,n ]
has a triangular shape: the leading monomial of f1,j is x 1 • x j (all the terms of degree 2 divisible by x 1 ) and hence distinct.

More generally, let

G * = G 1 G 2 G 3 • • • G n . We consider, for all i, 1 ≤ i ≤ n: F i := [ fi,1 = f i,1 , fi,2 = -f i,1 + f i,2 , . . . , fi,n-i+1 = -f i,1 + f i,n-i+1 ]. (16)
All these equations are in triangular form, and leading monomials of F i are the monomials x i x j , with j ≥ i. Consequently the set of equations 1≤i≤n F i are linearly independent. Finally, the numbers of rows of

G * is n + (n -1) + (n -2) + • • • (n -(n -1)) = n 2 -n(n -1)/2 = n(n + 1)/2 = n+1 2 . ⊓ ⊔
Example 2 For n = 4, and m = n(n + 1)/2 = 10 the matrix G * is as follows:

    1 1 1 1 0 0 0 0 0 0 0 1 0 0 1 1 1 0 0 0 0 0 1 0 0 1 0 1 1 0 0 0 0 1 0 0 1 0 1 1     .
After such reductions, the terms of degree 3 in M (2) [i, j] is updated as:

T (2) i,j = {x 2 x 2 i , x i x 2 2j+1 , x i x 2 2j+2 , 2 x i x 2 x 2j+1 , 2 x i x 2 x 2j+2 , 2x i x 2j+1 x 2j+2 }, for i > 2.
For i = 1, 2 the only difference is that the term x 2 x 2 i not appear in T

i,j . We consider the particular case of the first row M (2) :

T (2) 1,j = {2 x 1 x 2 x 2j+1 , 2 x 1 x 2 x 2j+2 , x 1 x 2 2j+1 , 2x 1 x 2j+1 x 2j+2 , x 1 x 2 2j+2 }.
We can see that all these terms can be reduced by the leading terms of a suitable M (1) [i, j]. More precisely, x 1 x 2 2j+1 , and x 1 x 2 2j+2 can be reduced by M (1) [1, 2j + 1] and M (1) [1, 2j + 2] respectively. Thus, for all j, 1 ≤ j ≤ m 2 , we update the matrix as follows:

M (2) [1, j] = M (2) [1, j] -M (1) [1, 2j + 1] -M (1) [1, 2j + 2].
The corresponding reductions will only yield new terms of degree < 3. Similarly, x 1 x 2 x 2j+1 , x 1 x 2 x 2j+2 , x 1 x 2j+1 x 2j+2 can be reduced by a M (1) [i ′ , j ′ ] with (i ′ , j ′ ) ∈ U 1 . Thus, for all j, 1 ≤ j ≤ m 2 , we update the matrix as follows:

M (2) [1, j] = -M (2) [1, j] + M (1) [2, 2j + 1] + M (1) [2, 2j + 2] + M (1) [2j + 1, 2j + 2].

After this step, we have:

T (2)
1,j = {x 2 x 2 2j+1 , x 2 x 2 2j+2 , x 2j+1 x 2 2j+2 } and LT(M (2) [1, j]) = x 2 x 2 2j+1 .

We consider then the second row of M (2) whose terms of degree 3 are:

T (2)
2,j = {2 x 2 2 x 2j+1 , 2 x 2 2 x 2j+2 , x 2 x 2 2j+1 , 2 x 2 x 2j+1 x 2j+2 , x 2 x 2 2j+2 }.

We can again reduce x 2 2 x 2j+1 and x 2 2 x 2j+2 by the leading terms of polynomials of M (1) . However, the reduction will create new elements x 2 x 2 2j+1 and x 2 x 2 2j+2 which are irreducible modulo LT(M (1) ). For all j, 1 ≤ j ≤ m 2 , we set:

M (2) [2, j] = M (2) [2, j] -2 M (1) [2j + 1, 2] -2 M (1) [2j + 2, 2].

After this step, we have

T (2)
2,j = {3 x 2 x 2 2j+1 , 2 x 2 x 2j+1 x 2j+2 , 3 x 2 x 2 2j+2 } and LT(M (2) [1, j]) = 3 x 2 x 2 2j+1 . T

2,j and T

(2) 2,j can not be further reduced by LT(M (1) ). Let U 2 := {(i, j) ∈ [4, . . . , n] × [1, . . . , m 2 ] | i > 2j + 2}. In this case, we can cancel the terms x 2 2j+1 x i and x 2 2j+2 x i by M (1) . However, the reduction will create new terms x 2j+1 x 2 i and x 2j+2 x 2 i which are irreducible modulo LT(M (1) ). More precisely, for all (i, j) ∈ U 2 , we update the matrix M (2) as follows: M (2) [i, j] = M (2) [i, j] -M (1) [i, 2j + 2] -M (1) [i, 2j + 1].

The terms of degree 3 of M (2) [i, j] are then:

T (2)
i,j = {2 x 2 x 2j+1 x i , 2 x 2 x 2j+2 x i , x 2 x 2 i , 2x 2j+1 x 2j+2 x i , x 2j+1 x 2 i , x 2j+2 x 2 i }, ∀(i, j) ∈ U 2 .

The terms of T

i,j are clearly no divisible by x 1 . We have that x 2 x 2 i is irreducible modulo LT(M (1) ). The others terms are divisible by a square only if i = 2j + 2. However, x 2 x 2 2j+2 and x 2j+1 x 2 2j+2 can not be reduced modulo LT(M (1) ). Again, x 2j+1 x 2 i and x 2j+2 x 2 i can not be reduced by LT(M (1) ). Thus, ∀(i, j) ∈ U 2 , the set T

i,j is irreducible modulo LT(M (1) ).

For i = 2j + 2, we have a rather similar situation. The only difference is that the reduction of x 3 2j+2 will only yield terms of degree < 3. We have then:

T (2)
2j+2,j = {2 x 2 x 2j+1 x 2j+2 , 3 x 2 x 2 2j+2 , 3 x 2j+1 x 2 2j+2 }.

Similarly, for i = 2j + 1, we have: T

i,j = {3 x 2 x 2 2j+1 , 2 x 2 x 2j+1 x 2j+2 , x 3 2j+1 , 2 x 2 2j+1 x 2j+2 , x 2j+2 x 2 2j+1 }.

Using LT(M (1) ), we can reduce x 2 2j+1 x 2j+2 and x 3 2j+1 . So, we compute:

M (2) [2j + 1, j] = M (2) [2j + 1, j] -2 M (1) [2j + 2, 2j + 1] -M (1) [2j + 1, 2j + 1].

This yields: T

2j+1,j = {3 x 2 x 2 2j+1 , 2 x 2 x 2j+1 x 2j+2 , 3 x 2j+1 x 2 2j+2 }.

Finally, we define L 2 := {(i, j) ∈ [3, . . . , n] × [1, . . . , m 2 ] | 2 < i < 2j + 1}. For all, (i, j) ∈ L 2 , it holds that: T

i,j = {x 2 x 2 i , 2 x 2 x i x 2j+1 , 2 x 2 x i x 2j+2 , x i x 2 2j+1 , x i x 2 2j+2 , 2 x i x 2j+1 x 2j+2 }.

All in all, after these steps, no term of M (2) can be reduced by LT(M (1) ).

We have then:

-T

1,j = {x 2 x 2 2j+1 , x 2 x 2 2j+2 , x 2j+1 x 2 2j+2 }, for all j, 1 ≤ j ≤ m 2 , -T

2,j = {3 x 2 x 2 2j+1 , 2 x 2 x 2j+1 x 2j+2 , 3 x 2 x 2 2j+2 }, for all j, 1 ≤ j ≤ m 2 , -T

i,j = {x 2 x 2 i , 2 x 2 x i x 2j+1 , 2 x 2 x i x 2j+2 , x i x 2 2j+1 , x i x 2 2j+2 , 2 x i x 2j+1 x 2j+2 } , ∀(i, j) ∈ L 2 , -T

(2) 2j+1,j = {3 x 2 x 2 2j+1 , 2 x 2 x 2j+1 x 2j+2 , 3 x 2j+1 x 2 2j+2 }, for all j, 1 ≤ j ≤ m 2 , -T

(2) 2j+2,j = {2 x 2 x 2j+1 x 2j+2 , 3 x 2 x 2 2j+2 , 3 x 2j+1 x 2 2j+2 }, for all j, 1 ≤ j ≤ m 2 , -T

(2) i,j = {2 x 2 x 2j+1 x i , 2 x 2 x 2j+2 x i , x 2 x 2 i , 2x 2j+1 x 2j+2 x i , x 2j+1 x 2 i , x 2j+2 x 2 i }, ∀(i, j) ∈ U 2 .

We now proceed the polynomials M (2) to have distinct leading monomials. We first reduce polynomials of the second row. That is, for all j, 1 ≤ j ≤ m 2 :

M (2) [2, j] = M (2) [2, j] -3 M (2) [1, j].
This gives: T

2,j = {2 x 2 x 2j+1 x 2j+2 , -3 x 2j+1 x 2 2j+2 }. Also, for all j, 1 ≤ j ≤ m 2 , we compute: M (2) [2j + 2, j] = M (2) [2j + 2, j] -M (2) [2, j].

This gives: T

(2) 2j+2,j = {3 x 2 x 2 2j+2 , 6 x 2j+1 x 2 2j+2 }. For all j, 1 ≤ j ≤ m 2 , we compute: M (2) [2j + 1, j] = M (2) [2j + 1, j] -3M (2) [1, j].

This gives: T

2j+1,j = {2 x 2 x 2j+1 x 2j+2 , -3 x 2 x 2 2j+2 }. Finally, for all j, 1 ≤ j ≤ m 2 : M (2) [2j + 1, j] = M (2) [2j + 1, j] -M (2) [2, j].

We can generalize for instance Theorem 9 to UniformError-LWE. Theorem 14. Let T > 0, and (G, s × G + e) = (G, c) ∈ Z n×m q × Z m q be sampled according to L (n) s,U ([-T ...,T ]) . Let also P (x) = X T i=1 (X -i). We assume that q > (2T + 1) • m. For all 1 ≤ m ≤ n+1 2 , we define:

f 1 = P c 1 - n j=1
x j G j,1 , . . . , f m = P c m -n j=1

x j G j,m .

It holds that f H 1 , . . . , f H m are linearly independent with probability ≥ 1 -(2T +1)m q .

Proof. Let N be the number of monomials of degree ≤ 2T + 1. We define Mac as m × N matrix whose rows are the coefficients of the f i s. Let p = Det(Mat) be the determinant of a m × m sub-matrix Mat of Mac. If p is non-zero, Schwartz-Zippel-DeMillo-Lipton Lemma yields the result stated. The fact that p is non-zero follows from a similar argument than Lemma 9. ⊓ ⊔

  for d, min deg(f 1 ), . . . , deg(f m ) ≤ d ≤ D for some integer D. The Macaulay matrix M acaulay d,m

1

 1 degree of regularty divided by n dreg/n for β = 1.1 α → α real experiments (n=10000)

  be the binary entropy. For n and k large enough, we have log 2

	n k ≈ n H 2	k n .
	Similarly, we have the following lemma.
	Lemma 3.

  then there is a subexponential algorithm solving BinaryError-LWE with complexity

	O m 2 2	ω n log log log n 8 log log n	(time), O m 2 2	2n log log log n 8 log log n	(memory).	(

  x n ] is semi-regular. The proof of this result is exactly the proof of [29, Lemma 2.1]. For n = 5, the matrix G * in Lemma 8 is as follows:

	⊓ ⊔
	Example 1

We will see that the constant π/4 in the exponent allows to adjust the success probability in Theorem 6.

A Appendix

A.1 Degree of Regularity

The proof of Theorem 7-ii) is derived from the following more general result. Proposition 2. Let ǫ > 0, and F (n) ∈ {log 1/ǫ (n), log log n}. Assuming m = F (n) n, then the degree of regularity of a system of quadratic semi-regular equations f 1 , . . . , f m ∈ Z q [x 1 , . . . , x n ] behaves asymptotically as:

.

The equations f i,j corresponding are then By performing the reductions as in [START_REF] Buchberger | Computer algebra symbolic and algebraic computation[END_REF], we get:

In order to prove Theorem 13, we first consider the case where m = n as an intermediate step.

Theorem 13. We assume q = Ω(n 2 ).

s,U (F2) , and let P (x) = X(X -1). For any m, 1 ≤ m ≤ n, the equations

Proof. The strategy is similar to the proof of Theorem 9. Let N be the number of monomials of degree 3 and let Mat 3 be a sub-matrix of size m • n × m • n of the Macaulay matrix at at degree 3 of f H 1 , . . . , f H m . We can view Det(Mat 3 ) as a polynomial p of degree 2mn whose variables are the components of G. The next result shows that the determinant polynomial considered is not identically zero.

Lemma 10. Let P (x) = X(X -1). Let G * = G 1 be as defined in Lemma 9. We set c = s × G * + e, s ∈ Z n q chosen uniformly at random, m = n and e ∈ {0, 1} m sampled uniformly. We define:

Then, the polynomials f 1 , . . . , f m are semi-generic.

Proof. We first perform a simple reduction on the f j , that is:

From now on, we consider a degree ordering for which

We can see that the terms of degree 3 in x i • f1 is equal to T

i,1 := {2x 2 1 x i } 1≤i≤n . Similarly, we have that T

i,j := {2 • x 1 x i x j , x i x 2 j } 2≤j≤n 1≤i≤n are terms of degree 3 in x i • fj (with j = 1). We consider a matrix M (1) := {M (1) [i, j] = x i • fj } 1≤j≤m 1≤i≤n and define r

i,j as the function which returns LT(M (1) [i, j]). For all (i, j) ∈ [1, . . . , n] × [1, . . . , n], we have: r

i,j = r (1) (1) [i, j] and M (1) [j, i] have the same leading terms. Our goal is to perform suitable linear combinations on the polynomials of M (1) [i, j] such that all components have distinct leading terms.

We first process the first column and first row of M (1) . We define

Thus, for all (1, j) ∈ R 1 , we update M (1) [1, j] as follows:

After this step, for all (1, j) ∈ R 1 , the term of degree 3 in M (1) [1, j] is now T

1,j := {x 1 x 2 j } and then r

1,j := x 1 x 2 j . For all (i, 1) ∈ C 1 , we still have r

This is the lower diagonal part. For all (i, j) ∈ L 1 , with i = j, we update the matrix M (1) as follows:

1,i /2, we then update the elements of the diagonal as follows:

After this step, for all (i, j) ∈ L 1 , with i = j, the terms of degree 3 in M (1) [i, j] is T

i,j = {x 2 j x i , -x j x 2 i } and we set r

i,i reduces to {x 3 j }.

For all (i, j) ∈ L 1 , the terms r

i,j are distinct. Indeed, given (i, j) ∈ L 1 , the only solution

i,j = r

i,j = 2x 1 x i x j . For all (i, j) ∈ U 1 , the terms r (1) i,j are distinct. Indeed, given (i, j) ∈ U 1 , the only non-trivial solution

i ′ ,j ′ is (i ′ = j, j ′ = i). Since (i, j) ∈ U 1 , this implies that i ′ -j ′ > 0 and then (i ′ , j ′ ) ∈ U 1 . For all, (i, j) ∈ U 1 , the terms of degree 3 of M (1) [i, j] remains T (1) i,j := {2 x 1 x i x j , x i x 2 j } 2≤j≤n 1≤i≤n . To summarize:

r

The equations fj corresponding are:

By performing the reductions as in the previous lemma, we get:

Finally, this is the example used in Theorem 13.

Lemma 11. Let P (x) = X(X -1). Let G 1 be defined as in Lemma 10. We consider a n × m 2 matrix G 2 , with m 2 = ⌊ n-2 2 ⌋. The coefficients are zero except for:

q chosen uniformly at random, and e ∈ {0, 1} m sampled uniformly. We define:

Then, the sequence f 1 , . . . , f m is semigeneric.

Proof. Let M (1) be the matrix constructed as in Lemma 10. The matrix is such that:

The leading terms of the polynomials in M (1) are then divided by a square or divided by x 1 . In fact, all the terms of degree 3 divisible by x 1 appear as leading terms. For all j, 1 ≤ j ≤ m 2 , we denote by f 2,j = f m1+j the equations derived from G 2 . This is the polynomial constructed from the jth column of G 2 . We define by

the terms of degree 3 in x i • f 2,j . We also consider a matrix M (2)

. The first step of the proof is to perform all possible reductions of the polynomials in M (2) modulo the polynomials M (1) [i, j]. The term x i x 2 2 can always be reduced by the leading term of a polynomial in the second column of M (1) . For all (i, j) ∈ [1, . . . , n] × [1, . . . , m 2 ], we cancel this term as follows:

This gives: T

2j+1,j = {-3 x 2 x 2 2j+2 , 3 x 2j+1 x 2 2j+2 }. Finally, for all j, 1 ≤ j ≤ m 2 : M (2) [2j + 1, j] = M (2) [2j + 1, j] + M (2) [2j + 2, j].

This gives T

(2) 2j+1,j = {9 x 2j+1 x 2 2j+2 }. To summarize, we have:

}, and r

(2)

2j+2 }, and r

(2)

}, and and r

By inspecting the terms in bold, it can be noticed that they are all distinct.

⊓ ⊔

.

The initial system -after a first simple reduction on the equations of G 1 -is:

We give below homogeneous components of degree 3 of the polynomials of M (2) after all the operations described in the previous proof.

Remark 2. We emphasize that we have found an example which extends Lemma 11. We construct a matrix We perform experiments to verify that such G yields semigeneric systems. We have been able to verify the assumption up to n = 100. However, we have not been able to prove that such family is semigeneric. This would allow to prove semigenericity for m ≈ n 2 / log n.


Srivari Chandrasekhar

Vidyavathi Patro

Lahu N Chavan

Rambabu Chegondi

René Grée

Multicomponent reactions in PEG-400: Ruthenium-catalyzed synthesis of substituted pyrroles

Since the first synthesis of "pyrrole" ring by Knorr way back in 1884, the preparation of pyrroles has come a long way over the past century. 6 Several approaches viz, [3+2] cycloadditions, 7 [4+1] approach, 8 [2+2+1] approach 9 and intramolecular versions 10 have been developed for the synthesis of pyrroles. These approaches are compiled in excellent reviews by Ferreira 11 and Menendez. 12 Recently, a novel three-component method for pyrrole synthesis has been reported by the Beller's group using ruthenium catalysis, assisted by Xantphos as ligand, in a [2+2+1] strategy for pyrrole formation. 13 This work combined with our experience in using PEG-400 as a solvent medium, 5 prompted us to look at the recyclability of expensive Ru-catalyst in such a pyrrole synthesis. The results pertaining to Ru-catalyzed three-component pyrrole synthesis with a recyclable medium (Ru and PEG-400) are reported herein (Scheme 1). Furthermore, a significant advantage of the described method is that the expensive ligand (xantphos) is avoided since the PEG-400 acts as external ligand. [START_REF] Mao | The OH groups of PEG can act as ligands see[END_REF] In the first instance, cyclopentanone 1a, cyclohexylamine 2a and ethylene glycol 3 were chosen as partners in the [2+2+1] condensation process (Table 1, entry 1). The reaction in PEG-400 in the presence of 1 mol% [RuCl 2 (p-cymene)] 2 and 20 mol% t-BuOK catalytic system was successful and the 1,2,3-trisubstituted pyrrole 4a was isolated in 75% yield, after a routine work-up process. 5k, 15 With this observation on hand, the reaction generality was studied by performing experiments with various substrates. Keeping cyclopentanone 1a and ethylene glycol 3 as the common partners, 4-methoxybenzylamine 2b (Table 1, entry 2) and n-butyl amine 2c (Table 1, entry 3) as variable amine counterparts, the pyrroles 4b, 4c were obtained in decent yields. To understand the patterns for aryl ketones, phenylethylketone 1b and ethylene glycol 3 as common partners were treated with benzyl amine 2d, 4-methoxy aniline 2e, (R)-(+)-1-(1naphthyl)ethyl amine 2f, cyclohexylamine 2a, n-butyl amine 2c to give the trisubstituted pyrroles 4d-h respectively in satisfactory yields (Table 1, entries 4-8). In addition, other ketones such as acetophenone 1c with benzyl amine 2d and cyclopropylamine 2g gave disubstituted pyrroles 4i and 4j respectively in acceptable yields (Table 1, entries 9 and10). The cyclohexanone 1d provided bicyclic fused pyrroles 4k-n with (S)-phenylethylamine 2h, butylamine 2c, benzylamine 2d, aniline 2i consistently well (Table 1, entries 11-14). Another ketone, -tetralone 1e was attempted with butylamine 2c, 4-chlorobenzylamine 2j, benzylamine 2d, cyclopropylamine 2g providing angular tricyclic pyrroles 4o-r respectively in the 75-85% yield range (Table 1, entries 15-18). For direct comparision of present method with Beller's protocol, the experiments were performed with 2phenylethylamine (2k) as one of the partners (Table 1, entries 19 and 20). The observations reveal that the yields obtained with the

A R T IC LE IN F O A B S TR A C T

An efficient and eco-friendly method for the synthesis of substituted pyrroles has been developed via ruthenium-catalyzed multicomponent reaction of ketone, amine and ethylene glycol in PEG-400 as solvent medium without using any external ligand. The catalytic system and solvent can be recycled with the same, as well as different, ketones with minimum loss of Ru-catalyst activity.

new system are marginally lower, however offers an additional advantage that the external ligand is not required. Further, the efficacy of the developed method by recycle and reuse 12 of expensive ruthenium catalyst, has been demonstrated. Towards this, entry 13 (Table 1) has been chosen as representative example. Thus, 1d and 2d were condensed with ethylene glycol 3 in the presence of t-BuOK for over five times using the same PEG-400 and ruthenium catalyst with good yields without significant loss of catalytic activity (Table 2). Also, the cross over experiments performed with three different ketones (Table 3) demonstrated that the products could be completely extracted from PEG and no detectable contaminations were observed. However, due the aqueous work-up process, 20 mol% t-BuOK has to be added after each run. Here also, an addition of 0.2 mol% [RuCl 2 (p-cymene)] 2 allowed us to improve the yields in next runs.

Table 3: Recyclability of catalyst and solvent in crossover experiments

Based on these findings, it may be inferred that the [2+2+1] condensation for pyrrole synthesis proceeds smoothly in PEG, even in the absence of any added ligand, via imine formation between ketone and amine, followed by dehydrogenation of ethylene glycol to an in situ generated dialdehyde for further condensation to form pyrrole. 11 Disappointingly, the substituted vicinal diols viz, 2,3butanediol, 1,2-diphenylethane-1,2-diol, cyclohexane-1,2-diol and 2-phenylethane-1,2-diol did not participate in the pyrrole synthesis. However, -hydroxyacetone 5 when subjected to the coupling protocol with ketones 1d or 1e and n-butylamine (Scheme 2) provided the pyrroles 4s and 4t in moderate yields. Scheme 2. Synthesis of -methyl substituted pyrroles in PEG-400.

These results endorse that the developed methodology follows the major principles of green chemistry wherein catalyst and solvent are recyclable. This MCR is well tolerated in PEG-400, with H 2 and H 2 O as byproducts, and additionally the molecules obtained, especially the tricyclic pyrroles, are potentially useful in bioorganic and medicinal chemistry.

In conclusion, we have successfully synthesized substituted pyrroles using readily accessible ketones, amines and ethylene glycol using [Ru(p-cymene)Cl 2 ] 2 as catalyst and potassium tertbutoxide as base in PEG-400 without using any extra ligand. In the process, the catalyst along with PEG solvent was recycled up to five times with the same ketone, as well as with different ketones.

Scheme 1 .

 1 Scheme 1. Synthesis of substituted pyrroles in PEG-400 ________________________ *Corresponding author. Tel.: +91 40 27193210; fax: +91 40 27160512. E-mail address: srivaric@iict.res.in (S. Chandrasekhar).

a

  Isolated yield after column chromatography *An additional 0.2 mol% 'Ru' catalyst was added to the reaction

Table 1 :

 1 Ruthenium-catalyzed synthesis of substituted pyrroles

	'		%	(*
	%		%	()
	&		%	('
	(		)*	&'
		!	! "
	#	$

Table 2 :

 2 Recyclability of catalyst in PEG-400

	Entry	Ketone	Amine		Product a	Time (h)	Yield (%) b
		O	NH 2
	1	1a		2a		Cy N	4a	16	75
		O
	2							20	74
		1a		2b			4b
		O
	3			NH 2				16	70
		1a		2c			4c
		O			Me
	4 Ph				Ph	N
						Bn
		O
	5 Ph
					Me
			Me	NH 2	Ph	N
	6				Me

Elsevier Ltd. All rights reserved.

Acknowledgments

This research has been performed as part of the Indo-French "Joint Laboratory for Sustainable Chemistry at Interfaces". We thank CNRS, CSIR, University of Rennes 1 and CEFIPRA/IFCPAR for support of this research. V.P. & L.N.C thank to CSIR, New Delhi, for research fellowship and R.C. thanks CSIR-SRA for financial assistance. SC thanks CSIR XII plan project ORIGIN (CSC-0108) for funding.

Supporting Information

Supplementary data associated with this article, experimental and characterization data, can be found in the online version.