Martin R Albrecht

Jean-Charles Faugère

Pooya Farshim

Gottfried Herold

Ludovic Perret

Polly

la diffusion de documents scientifiques

Keywords: 94A60] Cryptography, [93C35] Multivariable systems, [68Q17] Computational difficulty of problems

de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Background. Fully homomorphic encryption [START_REF] Gentry | Fully homomorphic encryption using ideal lattices[END_REF] is a cryptographic primitive which allows performing arbitrary computations over encrypted data. In such a scheme, given a function f and a ciphertext c encrypting a plaintext m, it is possible to transform c into a new ciphertext c which encrypts f (m). From an algebraic perspective, this homomorphic feature can be seen as the ability to evaluate multivariate (Boolean) polynomials over ciphertexts. Hence, instantiating homomorphic encryption over the ring of multivariate polynomials is perhaps most natural, although not necessarily conceptually the simplest (cf. [START_REF] Van Dijk | Fully homomorphic encryption over the integers[END_REF]).

Indeed, let I be some ideal in P := F[x 0 , . . . , x n-1 ]. Denote an injective function mapping bit strings to elements in the quotient ring P/I by Encode(•), and its inverse by Decode(•). If Decode(Encode(m 0 ) • Encode(m 1 )) = m 0 • m 1 for • ∈ {+, •}, we can encrypt a message m as c = f + Encode(m), for f randomly chosen in I.

(

) 1
The homomorphic features of this scheme follow from the definition of an ideal. Decryption is performed by computing remainders modulo I. Alternative, if Encode(m) = 0 for some message m, decryption is performed by deciding ideal membership. The problems of computing remainders modulo an ideal and deciding ideal membership were solved by Buchberger [START_REF] Buchberger | Ein Algorithmus zum Auffinden der Basiselemente des Restklassenrings nach einem nulldimensionalen Polynomideal[END_REF][START_REF] Buchberger | Gröbner bases: an algorithmic method in polynomial ideal theory[END_REF][START_REF] Buchberger | An algorithm for finding the basis elements of the residue class ring of a zero dimensional polynomial ideal[END_REF], where he introduced the notion of Gröbner bases, and gave an algorithm for computing such bases.

In fact, most known homomorphic schemes which support both addition and multiplication are based on variants of the ideal membership problem over various rings. For example in [START_REF] Van Dijk | Fully homomorphic encryption over the integers[END_REF] the ring p ⊆ Z, for p an odd integer, is considered. In [START_REF] Gentry | Fully homomorphic encryption using ideal lattices[END_REF] ideals in a number field play the same role (cf. [START_REF] Smart | Fully homomorphic encryption with relatively small key and ciphertext sizes[END_REF]). One can also view Regev's LWE-based public-key encryption scheme [START_REF] Regev | On lattices, learning with errors, random linear codes, and cryptography[END_REF] as well as the homomorphic encryption scheme based on it [START_REF] Brakerski | Efficient fully homomorphic encryption from (standard) LWE[END_REF] in this framework. Furthermore, if we instantiate the construction in [START_REF] Aguilar Melchor | Additively homomorphic encryption with doperand multiplications[END_REF] over P , we can view its multiplication operation as constructing the set of cross-terms appearing in multivariate polynomial multiplication. Finally, we note that the construction displayed above is essentially Polly Cracker [START_REF] Fellows | Combinatorial cryptosystems galore![END_REF][START_REF] Barkee | Why you cannot even hope to use Gröbner bases in Public Key Cryptography: An open letter to a scientist who failed and a challenge to those who have not yet failed[END_REF][START_REF] Koblitz | Algebraic aspects of cryptography[END_REF], a family of cryptosystems dating back to the early 1990s. Despite their simplicity, our confidence in Polly Cracker-style schemes has been shaken as almost all such proposals have been broken [START_REF] Levy | A survey on Polly Cracker systems[END_REF]. This is partially due to the lack of formal treatment of security for such schemes in the literature. In fact, it is a long-standing open research problem to propose a secure Polly Cracker-style encryption scheme [START_REF] Barkee | Why you cannot even hope to use Gröbner bases in Public Key Cryptography: An open letter to a scientist who failed and a challenge to those who have not yet failed[END_REF] (cf. [40, p. 41]).

Related works

Polly Cracker. In 1993, Barkee et al. wrote a paper [START_REF] Barkee | Why you cannot even hope to use Gröbner bases in Public Key Cryptography: An open letter to a scientist who failed and a challenge to those who have not yet failed[END_REF] whose aim was to dispel the urban legend that "Gröbner bases are hard to compute." Another goal of this paper was to direct research towards sparse systems of multivariate equations. To do so, the authors proposed the most obvious dense Gröbner-based cryptosystem, namely an instantiation of the construction mentioned at the beginning of the introduction. In their scheme, the public key consists of a set of polynomials {f 0 , . . . , f m-1 } ⊂ I which are used to construct an element f ∈ I. Encryption of messages m ∈ P/I are computed as c = h i f i + m = f + m for f ∈ I. The private key is a Gröbner basis G which allows computing m = c mod I = c mod G. As highlighted in [START_REF] Barkee | Why you cannot even hope to use Gröbner bases in Public Key Cryptography: An open letter to a scientist who failed and a challenge to those who have not yet failed[END_REF] this scheme can be broken using results from [START_REF] Dickenstein | The membership problem for unmixed polynomial ideals is solvable in single exponential time[END_REF] (cf. Section 5, Theorem 9).

At about the same time, and independently of Barkee et al.,Fellows and Koblitz [39,[START_REF] Koblitz | Algebraic aspects of cryptography[END_REF] proposed a framework for the design of public-key cryptosystems. The ideas in [START_REF] Fellows | Combinatorial cryptosystems galore![END_REF] were similar to Barkee et al.'s, but differed in two aspects. First, the polynomials generating the public ideal were derived from combinatorial or algebraic NP-complete problems (such systems were named CA-systems for "combinatorial-algebraic"). Second, the secret key was not a Gröbner basis of the public ideal, but rather a root of it, i.e. a Gröbner basis of a maximal ideal containing the public ideal. The main instantiation of such a system was the Polly Cracker cryptosystem. Fellows and Koblitz suggested several NP-complete problems, mainly based on graph-theoretic problems, for use in this context. The authors, however, did not investigate how one might generate "hard-on-average" instances of these problems with known solutions. Subsequently, a variety of sparse Polly Cracker-style schemes were proposed. The focus on sparse polynomials aimed to prevent the attack based on Theorem 9 (Section 5), yet almost all of these schemes were broken. We point the reader to [START_REF] Levy | A survey on Polly Cracker systems[END_REF] for a good survey of various constructions and attacks. Currently, the only Polly Cracker-style scheme which is not broken is the scheme in [START_REF] Caboara | Lattice Polly Cracker cryptosystems[END_REF]. This scheme is based on binomial ideals, which in turn are closely related to lattices. importantly, [START_REF] Albrecht | Polly Cracker, revisited[END_REF] contains several errors which were pointed out and partly corrected in [START_REF] Herold | Polly cracker, revisited, revisited[END_REF] which appeared at PKC 2012. In light of this, the authors of both publications [START_REF] Herold | Polly cracker, revisited, revisited[END_REF] and [START_REF] Albrecht | Polly Cracker, revisited[END_REF] jointly revisited all theorems, proofs and constructions which resulted in this paper.

Contributions & organisation

Our contributions in this paper can be summarised as follows:

1. We conduct a formal treatment of Polly Cracker-style schemes over multivariate polynomial rings and characterise their security. 2. We demonstrate the impossibility of converting such schemes to fully IND-CPA-secure schemes through a large class of transformations. 3. We introduce natural noisy variants of classical problems related to Gröbner bases which also generalise previously considered noisy problems such as the LWE and the approximate GCD (AGCD) problems. 4. We present a new somewhat (and doubly) homomorphic encryption scheme based on these new hard problems.

In order of achieve these results, our work also provide some new results about the intractability of multivariate problems with noise.

After this introduction, we start by giving an overview of Gröbner bases in Section 2. The reader already familiar with commutative algebra can skip this part. In Section 3, we formalise various problems associated with ideals in polynomials rings in the language of code-based security definitions [START_REF] Bellare | The security of triple encryption and a framework for code-based gameplaying proofs[END_REF]. Namely, we define the Gröbner basis (GB) and the ideal membership (IM) problems in the code-based game-playing language [START_REF] Bellare | The security of triple encryption and a framework for code-based gameplaying proofs[END_REF]. It not difficult to show, in the game-based formalism, that IM is not harder than GB. We show also that deciding ideal membership with overwhelming probability is equivalent to compute Gröbner bases for zero-dimensional ideals for certain choices of parameters.

Lemma 1 (informal). If IM is overwhelmingly easy, then GB is overwhelmingly easy. Conversely, if GB is easy then IM is easy as well.

This allows us to introduce a symmetric variant of Polly Cracker, that we shall call SPC, and precisely characterise its security guarantees. In particular, we show that this scheme achieves a weaker version of IND-CPA security where the total number of ciphertexts that the attacker can obtain is a priori bounded by a fixed polynomial. We prove this result under the assumption that computing Gröbner bases is hard if only a small number of polynomials are available to the attacker (Section 4). Bounded IND-CPA security is, in some sense, the best level of security that this scheme can possibly achieve: we give an attacker breaking the cryptosystem once enough ciphertexts are collected.

Theorem 1 (simplified). The bounded IND-BCPA security of SPC is essentially equivalent to the hardness of IM.

In Section 5, using results from computational commutative algebra, we show the security limitations of the constructed scheme are, in some sense, intrinsic. More precisely, we show that a large class of algebraic transformation cannot turn this scheme into a fully IND-CPA-secure and additively homomorphic (public-key) Polly Cracker-type scheme. Our result captures both known symmetric-to-asymmetric conversion techniques for homomorphic schemes in the literature [START_REF] Rothblum | Homomorphic encryption: From private-key to public-key[END_REF][START_REF] Van Dijk | Fully homomorphic encryption over the integers[END_REF]. Furthermore, this result-due to the generality of Gröbner bases-implies that IND-CPA-secure homomorphic encryption is difficult to construct without noisy encoding of messages (further evidence for this is given in [START_REF] Brakerski | When homomorphism becomes a liability[END_REF]). The main technical result of Section 5 is:

Theorem 2 (informal). Sampling uniformly elements of a polynomial ideal I up to some degree is equivalent to computing a Gröbner basis for I.

In order to go beyond this barrier we consider constructions where the Encode() function introduced in ( 1) is randomised. To prove security for such schemes, we consider noisy variants of the ideal membership (IMN) and related problems (namely, WIMN a weaker version of ideal ideal membership with noise, and GBN a noisy variant of GB). These can be seen as natural generalisations of the (decisional) LWE and AGCD problems over polynomial rings (Section 6). Regarding the hardness of these new problems, we show that:

Lemma 2 (informal). If GBN easy, then it holds that WIMN is easy.

Note that WIMN is not harder that IMN, whilst the converse is not always true. However, we show that the equivalence holds in a relevant case. We also prove an average-case-to-worst-case reduction for IMN.

Lemma 3. (informal) Assume that the ideal considered in the IMN games have a unique solution.

Then, if we can solve the IMN problem for a polynomial fraction of instances, then we can also solve it for all instances.

After formalising and justifying the hardness of the noisy assumptions in Section 7, we show that noisy encoding of messages can indeed be used to construct a fully IND-CPA-secure somewhat homomorphic scheme.

Theorem 3 (informal). The IND-CPA security of SPCN scheme is essentially equivalent to the hardness of WIMN.

Our result, together with a standard symmetric-to-asymmetric conversion for homomorphic schemes, provides a positive answer to the long-standing open problem proposed by Barkee et al. [START_REF] Barkee | Why you cannot even hope to use Gröbner bases in Public Key Cryptography: An open letter to a scientist who failed and a challenge to those who have not yet failed[END_REF] asking for a Polly Cracker-style public-key encryption scheme whose security is based on the hardness of computing Gröbner bases for random systems of polynomials. This result also implies that Regev's LWE-based public-key scheme is multiplicatively homomorphic under appropriate choices of parameters.

In Section 8 we show that our scheme allows proxy re-encryption of ciphertexts. This re-encryption procedure can be seen as trading noise for degree in ciphertexts. In this section, we also show that our scheme achieves a limited form of key-dependent message (KDM) security in the standard model, where the least significant bit of the constant term of the key is encrypted. We leave it as an open problem to adapt the techniques of [START_REF] Applebaum | Fast cryptographic primitives and circular-secure encryption based on hard learning problems[END_REF] to achieve full KDM security for the Polly Cracker with noise scheme. We conclude by discussing concrete parameter choices in Section 9, and give a reference implementation in Section 10.

Basics of Gröbner Bases

In this section we recall some basic definitions and results related to Gröbner bases [START_REF] Buchberger | An algorithm for finding the basis elements of the residue class ring of a zero dimensional polynomial ideal[END_REF][START_REF] Buchberger | Ein Algorithmus zum Auffinden der Basiselemente des Restklassenrings nach einem nulldimensionalen Polynomideal[END_REF][START_REF] Buchberger | Gröbner bases: an algorithmic method in polynomial ideal theory[END_REF]. For a more detailed treatment we refer the reader to [START_REF] Cox | Ideals, Varieties, and Algorithms[END_REF]. We consider a polynomial ring P = F[x 0 , . . . , x n-1 ] over some finite field (typically prime), some degree-compatible monomial ordering on the elements of P with x i > x j if i < j, and a set of polynomials f 0 , . . . , f m-1 . We denote by M(f ) the set of all monomials appearing in f ∈ P and extend this definition to sets of polynomials in the natural way. By LM(f ) we denote the leading monomial appearing in f ∈ P according to the chosen term ordering. We denote by LC(f ) the coefficient of LM(f ) in f , and set LT(f

) := LC(f )•LM(f ).
We denote by P <d the set of polynomials of degree < d (and analogously for >, ≤, ≥, and = operations). We define P =0 as the underlying field, including 0 ∈ F. We define P <0 as zero. Finally, we denote by M <m the set of all monomials < m for some monomial m (and analogously for >, ≤, ≥, and = operations). We assume the usual power-product representation for elements of P .

Definition 1 (Generated ideal). Let f 0 , . . . , f m-1 ∈ P be polynomials. The set

I = f 0 , . . . , f m-1 := m-1 i=0 h i f i | h 0 , . . . , h m-1 ∈ P is called the ideal generated by f 0 , . . . , f m-1 .
It is known that every ideal I of P is finitely generated, i.e. there exists a finite number of polynomials f 0 , . . . , f m-1 in P such that I = f 0 , . . . , f m-1 . A Gröbner basis of an ideal is a set of generators of the ideal which takes a particular form.

Definition 2 (Gröbner basis). Let I be an ideal of F[x 0 , . . . , x n-1 ] and fix a monomial ordering.

A finite subset G = {g 0 , . . . , g m-1 } ⊂ I is said to be a Gröbner basis of I if for any f ∈ I there exists a g i ∈ G such that LM(g i ) | LM(f ).

Remark. We note that for the vector space F n , the notion of a Gröbner basis coincides with that of a row echelon form, and Gröbner basis algorithms (see below) reduce to Gaussian elimination. For univariate polynomial rings, e.g. F[x] and Z[x], the notion of a Gröbner basis coincides with greatest common divisor, and running a Gröbner basis algorithm computes the GCD.

It is possible to extend the polynomial division algorithm to multivariate polynomials: we write r = f mod G when r is a possible result of applying the multivariate division algorithm on f and G for the given monomial ordering. It holds that

f = m-1 i=0 h i g i + r with M(r) ∩ LM(G) = ∅.
When G is a Gröbner basis, r is unique and is called the normal form of f with respect to the ideal I. In particular, we have that f mod I = f mod G = 0 if and only if f ∈ I. Given P and I, we can define the quotient ring P/I. By abuse of notation, we write f ∈ P/I if f mod I = f where the last equality is interpreted over the elements of P . That is, we identify elements of the quotient P/I with their minimal representation in P .

As defined above, a Gröbner basis is not unique. For instance, we can multiply any polynomial of a Gröbner basis by a nonzero constant. However, given any Gröbner basis we can compute the unique reduced Gröbner basis in polynomial time via ReduceGB(•) given in Algorithm 1.

Definition 3 (Reduced Gröbner basis).

A reduced Gröbner basis for an ideal I ⊂ P is a Gröbner basis G such that: (1) LC(g) = 1, for all g ∈ G, and (2) ∀g ∈ G, ∃ m ∈ M(g) such that m is divisible by some element of LM(G \ {g}).

Algorithm 1: ReduceGB(G) 1 begin 2 G ← ∅; 3 while G = ∅ do 4 f ← the smallest element of G according to the term ordering; 5 G ← G \ {f }; 6 if LM(f ) ∈ LM( G) then 7 G ← G ∪ {LC(f ) -1 • f }; 8 return h mod G\{h} | h ∈ G ;
Buchberger [START_REF] Buchberger | Ein Algorithmus zum Auffinden der Basiselemente des Restklassenrings nach einem nulldimensionalen Polynomideal[END_REF] proved that in order to compute a Gröbner basis from a given ideal basis, it is sufficient to consider so-called S-polynomials. From such a basis, it is easy to compute the (unique) reduced Gröbner basis using Algorithm 1.

Definition 4 (S-polynomial

). Let f, g ∈ F[x 0 , . . . , x n-1 ] be nonzero polynomials. -Let LM(f ) = n-1 i=0 x α i i and LM(g) = n-1 i=0 x β i i , with α i , β i ∈ N,
denote the leading monomials of f and g respectively. For every 0 ≤ i < n set γ i := max(α i , β i ) and denote by x γ the polynomial n-1 i=0 x γ i i . Then x γ is the least common multiple of LM(f ) and LM(g):

x γ = LCM(LM(f ), LM(g)).
-The S-polynomial of f and g is defined as

S(f, g) = x γ LT(f ) • f - x γ LT(g) • g.
Buchberger showed that a basis is a Gröbner basis if all S-polynomials "reduce to zero."

Definition 5 (Reduction to zero). Fix a monomial order in P and let G = {g 0 , . . . , g s-1 } ⊂ P be an unordered set of polynomials and let t be a monomial. Given a polynomial f ∈ P , we say f has a t-representation with respect to ≤ and G if f can be written as

f = a 0 g 0 + • • • + a s-1 g s-1 ,
such that whenever a i g i = 0, we have a i g i ≤ t. Furthermore, we write that f -→ G 0 ("f reduces to zero") if and only if f has an LM(f )-representation with respect to G.

Note that f mod G = 0 implies that f -→ G 0 while the converse is not necessarily the case.

Theorem 4 (Buchberger's criterion).

A basis G = {g 0 , . . . , g s-1 } for an ideal I is a Gröbner basis if and only if for all i = j we have S(g i , g j ) -→ G 0.

Theorem 4 (see [13, p.211f] for a proof) leads to an algorithm [START_REF] Buchberger | Ein Algorithmus zum Auffinden der Basiselemente des Restklassenrings nach einem nulldimensionalen Polynomideal[END_REF] which computes a Gröbner basis by constructing and reducing S-polynomials. However, this algorithm -Buchberger's algorithmspends most of its time reducing elements to zero, a computation which is of no use. Buchberger also proposed two criteria which tell us a priori whether the S-polynomial of two polynomials reduces to zero. We make use of the first criterion in this work (see [13, p.222f] for a proof of this result):

Theorem 5 (Buchberger's first criterion). Let f, g ∈ P be such that

LCM(LM(f ), LM(g)) = LM(f ) • LM(g),
i.e. f and g have disjoint leading terms. Then S(f, g) -→

{f,g} 0.

From this, we obtain the following corollary.

Corollary 1. A set {g 0 , . . . , g n-1 } ⊂ P with LM(g i ) = x d i i with d i ≥ 0 for all i, 0 ≤ i < n is a Gröbner basis.
All ideals considered in this work are zero-dimensional, i.e. their associated varieties have finitely many points. The following lemma establishes the equivalence between various statements about zero-dimensional ideals. This result will be required to analyse some algorithms introduced in Section 3 (a proof of this result can be found, for instance, in [30, p.234f]).

Lemma 4 (Finiteness criterion). Let I = f 0 , . . . , f m-1 ⊂ P := F[x 0 , . . . , x n-1 ] be an ideal. The following conditions are equivalent. 1. The system has only finitely many solutions in the algebraic closure of F. 2. For any i ∈ {0, . . . , n -1}, we have I ∩ F[x i ] = ∅. 3. For any i ∈ {0, . . . , n -1}, there exists g i ∈ I such that LM(g i ) = x d i i with d i > 0. 4. The set of monomials S(I) := M(P ) \ {LM(f ) | f ∈ I} is finite. 5. The F-vector space P/I is finite-dimensional and a basis is given by S(I).

As soon as one of these conditions holds true, then we call the ideal I zero-dimensional. Moreover, the number of solutions counted with multiplicities in the algebraic closure of F is exactly the cardinal of S(I) which is the dimension of the vector space P/I. We will be using reduction modulo an ideal to sample polynomials from some ideal. The following lemma will be helpful to assert that this sampling is uniform. In particular, if M(P ≤b /I) is the set of monomials in P/I with degree at most b, then for any f ∈ I ≤b there are q s elements f i in P ≤b with f = f i -(f i mod I) and s = |M(P ≤b /I)|.

Proof. Given f we recover the unique r by computing f mod G by a standard fact about Gröbner bases and get f = f -r. Since P has a degree-compatible ordering, r has degree at most b. To prove the second claim, note that the monomials in P ≤b span an n+b b -dimensional vector space V over F q . The monomials in P/I up to degree b span a subspace of V of dimension |M(P ≤b /I)|, from which the claim follows.

The Gröbner Basis and Ideal Membership Problems

In this section we formalise various problems associated with Gröbner bases.

Notation. We write x ← y for assigning value y to a variable x, and x ← $ X for sampling x from a set X uniformly at random. If A is a probabilistic algorithm we write y ← $ A(x 1 , . . . , x n ) for the action of running A on inputs x 1 , . . . , x n with uniformly chosen random coins, and assigning the result to y. For a random variable X we denote by [X] the support of X, i.e. the set of all values that X takes with nonzero probability. We use PPT for probabilistic polynomial-time. We call a function (λ) negligible if | (λ)| ∈ λ -ω (1) . We say a function f (λ) is overwhelming if 1-f (λ) is negligible. We say that a function space FunSp(P) and a message space MsgSp(P), both parameterised by P, are compatible if for any possible value of P and for any f ∈ FunSp(P), the domain of f is MsgSp(P). We also denote by ω the matrix multiplication exponent (a.k.a. the linear-algebra constant) as defined in [START_REF] Von | Modern computer algebra[END_REF]Chapter 12]. We recall [START_REF] Vassilevska | Multiplying matrices faster than Coppersmith-Winograd[END_REF][START_REF] Stothers | On the Complexity of Matrix Multiplication[END_REF] that ω ∈ [2, 2.3727].

To formalise our problems, we use the code-based game-playing language [START_REF] Bellare | The security of triple encryption and a framework for code-based gameplaying proofs[END_REF]. Each game has an Initialize and a Finalize procedure. It also has specifications of procedures to respond adversary's various oracle queries. A game Game is run with an adversary A as follows. First Initialize runs and its outputs are passed to A. Then A runs and its oracle queries are answered by the procedures of Game. When A terminates, its output is passed to Finalize which returns the outcome of the game y. This interaction is written as Game A =⇒ y. In each game, we restrict our attention to legitimate adversaries, which are defined specifically for each game.

Following [START_REF] Cramer | Design and analysis of practical public-key encryption schemes secure against adaptive chosen ciphertext attack[END_REF], we define a computational polynomial ring scheme. This is a general framework allowing to discuss in a concrete way the different families of rings that may be used in cryptographic applications. More formally, a computational polynomial ring scheme P is a sequence of probability distribution of polynomial ring descriptions (P λ ) λ∈N . A polynomial ring description1 P specifies various algorithms associated with P such as computing the ring operations, sampling of elements, testing membership, encoding of elements, ordering of monomials, etc. We assume each polynomial ring distribution is over n = n(λ) variables, for some polynomial n(λ), and is over a finite field of prime size q(λ).

For q a prime, there is a one-to-one correspondence between ideals I ⊂ F q n [x 0 , . . . , x n-1 ] on polynomial rings over finite extension fields and over prime fields J ⊂ F q [x 0 , . . . , x n-1 , α]: map a root of F q n to α and add the characteristic polynomial of F q n to the generating basis. Hence, finite extension fields are covered by this definition. The ring Z[x 0 , . . . , x n-1 ] is not covered by our definition for brevity, but it can easily be generalised [START_REF] Becker | Gröbner Bases -A Computational Approach to Commutative Algebra[END_REF]Ch. 10].

Once P is given and a concrete ring P is sampled, one can define various Gröbner basis generation algorithms on P . In this work we denote by GBGen(1 λ , P, d, ) any PPT algorithm which outputs a reduced Gröbner basis G for some zero-dimensional ideal I ⊂ P such that the last elements of G have degree d and the remaining elements have degree 1 and such that (P \ I) ≤b is not empty. Of particular interest to us is the Gröbner basis generation algorithm shown in Algorithm 2 called GBGen dense (•). Throughout this paper we assume an implicit dependency of various parameters associated with P on the security parameter. Thus, we drop λ to ease notation. Finally, we always assume that LM(G) and hence S(I) is fixed by GBGen(•) for each λ, and thus is known. We Algorithm 2: Algorithm GBGen dense (1 λ , P, d, ) note that using Buchberger's First Criterion in Algorithm 2 is a special case of using Macaulay's trick [START_REF] Mora | De Nugis Groebnerialium 2: Applying Macaulay's trick in order to easily write a Gröbner basis[END_REF]. Also, GBGen dense (•) for d = 1 or any d > 1 with = 0 captures the usual case of a set of polynomials which have a (unique) common root in the base field, and where LM(g i ) = x i for all i, 0 ≤ i < n. This case is common in cryptographic applications such as algebraic cryptanalysis, e.g. [START_REF] Faugère | Algebraic cryptanalysis of Hidden Field Equation (HFE) cryptosystems using Gröbner bases[END_REF][START_REF] Courtois | Cryptanalysis of block ciphers with overdefined systems of equations[END_REF][START_REF] Sala | Gröbner Bases, Coding, and Cryptography[END_REF] and is well studied. The next lemma -which is an easy consequence of Corollary 1 -establishes that GBGen dense (•) returns a Gröbner basis with dim(P/I) = d .

1 begin 2 if d = 0 then return {0} for i ∈ {0, . . . , n -1} do 3 if i > n --
Lemma 6. Let G = {g 0 , . . . , g n-1 } ⊂ P = F[x 0 , . . . , x n-1 ] be the set of polynomials defined as

g i := x d i i + m j ∈M <x d i i c ij m j , ∀i, 0 ≤ i < n
where c ij ∈ F. Then G is a Gröbner basis for the zero-dimensional ideal g 0 , . . . , g n-1 . Additionally, the dimension of the F q -vector space P/ g 0 , . . . , g n-1 is n-1 i=0 d i .

Proof. The Gröbner basis property follows from Corollary 1. Clearly, S(I) = M(P ) \ {LM(f ) | f ∈ I} is the set of all monomials of the form n-1 j=0 x γ j j where all γ j < d j . Since there are n-1 i=0 d i such elements, this is also the dimension of the vector space by Lemma 4.

Denote Q = P ≤b /I for b some fixed parameter and note here that P ≤b /I = (P/I) ≤b , since the monomial order sorts by total degree first. In this work we are mainly interested in the case where Q has polynomially many elements. In this case we require to be a constant but allow q to depend on λ. We note, however, that larger quotients are permitted by our definitions.

We now formally define the Gröbner basis problem, which is the problem of computing the Gröbner basis for some ideal I given a set of polynomials f 0 , . . . , f m-1 ∈ I.

Definition 6 (The Gröbner basis (GB) problem). The Gröbner basis problem is defined through game GB P,GBGen(•),d, ,b,m shown in Figure 1. The advantage of a PPT algorithm A in solving the GB problem is defined by

Adv gb P,GBGen(•),d, ,b,m,A (λ) := Pr GB A P,GBGen(•),d, ,b,m (λ) ⇒ True .
An adversary is legitimate if it calls the Sample procedure of Figure 1 at most m = m(λ) times.

Initialize(1 λ , P, d, ): begin P ← $ P λ ; G ← $ GBGen(1 λ , P, d, ); return (1 λ , P ); end Sample(): begin f ← $ P ≤b ; f ← f -(f mod G); return f ; end Finalize(G ): begin return (G = G ); end Fig. 1. Game GB P,GBGen(•),d, ,b,m .
It follows from Lemma 5 that the Sample procedure in Figure 1 returns elements of degree ≤ b which are uniformly distributed in G ≤b . We note that usually we must require b ≥ d in order to exclude the trivial case where Sample always returns zero or elements independent of some elements of the Gröbner basis.

We recall that given a Gröbner basis G of an ideal I, r = f mod I = f mod G is the normal form of f with respect to the ideal I. We sometimes drop the explicit reference to I when it is clear from the context which ideal we are referring to, and simply refer to r as the normal form of f . Furthermore f ∈ I if and only if r = 0. This is the well-known ideal membership problem formalised below. We mention that solving this problem was the original motivation which led to the discovery of Gröbner bases [START_REF] Buchberger | Ein Algorithmus zum Auffinden der Basiselemente des Restklassenrings nach einem nulldimensionalen Polynomideal[END_REF].

Definition 7 (The ideal membership (IM) problem). The ideal membership problem is defined through game IM P,GBGen(•),d, ,b,m shown in Figure 2. The advantage of a PPT algorithm A in solving IM is defined by

Adv im P,GBGen(•),d, ,b,m,A (λ) := 2 • Pr IM A P,GBGen(•),d, ,b,m (λ) ⇒ True -1.
An adversary is legitimate if it calls the Sample procedure of Figure 2 at most m = m(λ) times.

Initialize(1 λ , P, d, ): begin P ← $ P λ ; G ← $ GBGen(1 λ , P, d, ); c ← $ {0, 1}; Q ← (P/ G ) ≤b ; return (1 λ , P ); end Sample(): begin f ← $ P ≤b ; f ← f mod G; return f -f ; end Challenge(): begin f ← $ P ≤b ; f ← f -(f mod G); if c = 0 then r ← $ Q \ {0}; f ← f + r; return f ; end Finalize(c ): begin return (c = c ); end Fig. 2. Game IM P,GBGen(•),d, ,b,m .
We note that in the above definition we have excluded the zero element in the sampling of the remainder when coin c takes value 0. This is to ensure than an algorithm can have an overwhelming advantage in solving the IM problem.

We define a game IM P,GBGen(•),d, ,b,m similarly to the game in Figure 2 except that the zero element is allowed when c = 0 in the Challenge procedure (i.e., r ← $ Q \ {0} is replaced by r ← $ Q). The advantage of any adversary A in a modified IM game can be easily related to that in the IM game.

Lemma 7. It holds that Adv im P,GBGen(•),d, ,b,m,A (λ) = 1 -1 |Q| • Adv im P,GBGen(•),d, ,b,m,A (
λ), for any adversary A.

Proof. Let p be the probability that A outputs 0 when the remainder of the challenge polynomial modulo G is zero. Let p denote the probability that A outputs 1 when this remainder is nonzero. We have:

2 • Pr[A wins the IM game] -1 = p + p -1, 2 • Pr[A wins the IM game] -1 = p + 1 |Q| (1 -p) + 1 - 1 |Q| p -1 = 1 - 1 |Q| • (p + p -1).
We show below that under certain conditions the GB and IM problems are equivalent. Informally, the reduction of the GB problem to the IM problem works as follows. Consider an arbitrary element g i in the Gröbner basis G. We can write g i as x d i i -gi for some gi < g i . Now, assume x d i i -r i is in the ideal and that r i < x d i i , i.e. LM(x

d i i -r i ) = x d i i and x d i i -r i ∈ G .
To find such an r i we exhaustively search Q and hence require |Q| = poly(λ). Repeat this process for all x d i i and accumulate the results

x d i i -r i in a list G. The list G is a list of elements in G with LM( G) = LM(G)
which implies that G is a Gröbner basis. We note that this is the core idea behind the FGLM algorithm [START_REF] Faugère | Efficient Computation of Zero-Dimensional Gröbner Bases by Change of Ordering[END_REF] which allows to efficiently change the ordering of a Gröbner basis given access to an oracle computing normal forms with probability 1 (and also "Bulygin's attack" in a different context [START_REF] Bulygin | Chosen-ciphertext attack on noncommutative Polly Cracker[END_REF]).

Lemma 8. (IM overwhelmingly easy =⇒ GB overwhelmingly easy) Suppose the quotient size |Q| is polynomial in λ. Then for any PPT adversary A against the IM problem, there exists a PPT adversary B against the GB problem such that

1 -poly(λ) • 1 -Adv im P,GBGen(•),d, ,b,m,A (λ) ≤ Adv gb P,GBGen(•),d, ,b,m+1,B (λ),
where poly(λ

) := |LM(G)| • (|Q| -1).
(GB easy =⇒ IM easy) Conversely, for any PPT adversary A against the GB problem, there exists a PPT adversary B against the IM problem such that

Adv gb P,GBGen(•),d, ,b,m,A (λ) ≤ Adv im P,GBGen(•),d, ,b,m,B (λ).
Proof. Let us write P im-0 A (resp., P im-1 A ) for the success probability of any algorithm A against the IM problem conditioned on the event c = 0 (uniform challenge) (resp., c = 1). Various parameters are implicitly understood from the context. By the definition of advantage, we have

Adv im P,GBGen(•),d, ,b,m,A = P im-0 A + P im-1 A -1.
Now, to prove the first statement, we construct an algorithm B against the GB problem based on an algorithm A against the IM problem. This algorithm is described in Algorithm 3. We lower-bound the probability that algorithm B returns the correct Gröbner basis based on the success probability of A. Note that if all of A's answers are correct, then B's output will be the Gröbner basis. Applying the union bound, we derive an upper bound on the failure probability of B by bounding the failure probability of A in each invocation. Let ε = P im-0

A + P im-1 A -1 be A's advantage. Now consider invocations of A with gi = m -b ∈ I within B.
Then on such a query, A is run in an environment with the challenge bit being 1. By definition, the probability of A's failure in this case is 1-P im-1

A . Now consider invocations with gi ∈ I. Since we iterate over all remainders, the average (over the choice of b, such that gi ∈ I) failure probability for such invocations is 1 -P im-0

A . The union bound leads to an upper bound of

|LM(G)|(1 -P im-1 A ) + |LM(G)|(|Q| -1)(1 -P im-0 A )
on the failure probability of B, which in turn can be upper bounded by

|LM(G)|(|Q| -1)(2 -P im-1 A -P im-0 A ) = |LM(G)|(|Q| -1)(1 -ε), as desired.
Finally, it is easy to see that Algorithm 3 runs in polynomial time. For the second statement, we construct B as in Algorithm 4. We use A to find a candidate Gröbner basis G . If G = G we can compute the remainder r modulo the ideal spanned by the basis in polynomial time (cf. [30, p. 82]) and check if r = 0. So B will be successful whenever A is. By definition, the advantage of B is given by

Adv im P,GBGen(•),d, ,b,m,B (λ) = 2 • Pr [B successful] -1 = 2 Pr [B successful | A successful] -1 2 • Pr [A successful] + 2 Pr [B successful | A not successful] -1 2 • Pr [A not successful] .
The first summand is exactly what we need, so to finish the proof we need to show that the second summand is non-negative. This means, it remains to show that if G = G, then B still has a nonnegative advantage, i.e. B guesses c with probability at least 1/2. Indeed, if G does not have the correct form, B simply guesses the bit c (leading to a zero advantage). Moreover, if G has the right form, reduction modulo G gives rise to an F q -linear map m G : P ≤b -→ Q, f → f mod G . Since surjective linear maps preserve uniform distributions on finite-dimensional vector spaces, it follows that Pr

f ← $ P ≤b [m G (f ) = 0] = 1 |m G (P ≤b )|
and Pr

f ← $ I ≤b [m G (f ) = 0] = 1 |m G (I ≤b )| .
Since I ≤b ⊆ P ≤b , we get Pr

f ← $ P ≤b [m G (f ) = 0] ≤ Pr f ← $ I ≤b [m G (f ) = 0] . Now, let p 0 := Pr f ← $ P ≤b [f ∈ I ≤b ] and p 1 := Pr f ← $ P ≤b [f ∈ P ≤b \ I ≤b ] ,
where p 1 = 0 since the quotient has positive dimension. Finally, let A be the event "m G (f ) = 0." Then, since Pr

f ← $ P ≤b [A] = p 0 • Pr f ← $ I ≤b [A] + p 1 • Pr f ← $ P ≤b \I ≤b [A] ,
we get

p 0 • Pr f ← $ I ≤b [A] + p 1 • Pr f ← $ P ≤b \I ≤b [A] ≤ Pr f ← $ I ≤b [A] ⇐⇒ p 1 • Pr f ← $ P ≤b \I ≤b [A] ≤ (1 -p 0 ) • Pr f ← $ I ≤b [A] ⇐⇒ p 1 • Pr f ← $ P ≤b \I ≤b [A] ≤ p 1 • Pr f ← $ I ≤b [A] ⇐⇒ Pr f ← $ P ≤b \I ≤b [A] ≤ Pr f ← $ I ≤b [A] .
Remark. Lemma 8 only proves a weak form of the equivalence between IM and GB. That is, for Lemma 8 to be meaningful we require that the IM adversary returns the correct answer with overwhelming probability. First, this is due to the restriction that Sample can only be called a bounded number of times, and thus we cannot amplify the success probability of the IM adversary through repetition. We note that it is possible to prove a stronger statement than Lemma 8 for d = 1 using the re-randomisation technique from [START_REF] Berbain | QUAD: A multivariate stream cipher with provable security[END_REF]. Second, Lemma 8 does not address "structural errors" when d > 1, e.g. an IM oracle which decides based on partial information only. For example, assume

G = [x 0 +s 0 x n-1 , x 1 +s 1 x n-1 , . . . , x 2 n-1 +s n-1 x n-1 ]
where s i ← $ F q . This is a valid Gröbner basis generated by an algorithm satisfying the requirements for GBGen(•). We have that S(I) = {x n-1 , 1} and by construction any f ∈ P with a nonzero constant coefficient is not an element of I = G . Hence, it is easy -although not overwhelmingly so -to solve the IM problem by considering the constant coefficient only. On the other hand, the GB problem is still assumed to be hard, as it requires to recover all s i .

Hardness assumptions

It is well known [START_REF] Bayer | On the complexity of computing syzygies[END_REF] that the worst-case complexity of the best algorithms of Gröbner bases computation is doubly exponential in the number of variables. However, in this work we are concerned with polynomial systems over finite fields, which do not achieve this worst-case complexity. In particular, we consider zero-dimensional ideals, i.e. ideals with a finite number of common roots. In order to make the paper self-content, we recall here a number of classical complexity results for these type of systems.

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 polynomials is equivalent to performing Gaussian elimination on so-called Macaulay matrices M acaulay of degree d as follows. Each column corresponds to one monomial. List "horizontally" all the degree ≤ d monomials from largest to smallest sorted by some fixed monomial ordering. The smallest monomial comes last. Multiply each f i by all monomials t i,j of degree d -d i where d i = deg(f i ). Finally, construct the coefficient matrix for the resulting system: The F 4 algorithm [START_REF] Faugère | A new efficient algorithm for computing Gröbner basis (F4)[END_REF] can be seen as another way to use linear algebra without knowing an a priori bound: it successively constructs and reduces matrices until a Gröbner basis is found. The same is true for the F 5 algorithm when considered in "F 4 -style" [START_REF] Ars | Applications des bases de Gröbner à la cryptographie[END_REF]1]. Consequently, the complexity is bounded by the degree D and the number of polynomials considered at each degree. For F 5 [START_REF] Faugère | A new efficient algorithm for computing Gröbner bases without reduction to zero (F5)[END_REF] and the matrix-F 5 variant [START_REF] Faugère | Solving systems of polynomial equations with symmetries using SAGBI-Gröbner bases[END_REF] we know that under some regularity assumptions all matrices have full rank which implies that the number of rows in the matrix is bounded by the number of columns. The number of monomials up to some degree d is bounded by n+d n and thus when considering some degree d the number of rows and columns of the matrices considered by F 5 is also bounded above by n+d d . Thus, knowing the degree up to which F 5 has to compute provides an upper bound on the complexity of Gröbner bases. For this, the following definition [START_REF] Bardet | On the complexity of Gröbner basis computation of semi-regular overdetermined algebraic equations[END_REF] is useful.

M acaulay d,m := monomials of degree ≤ d (t 0,0 , f 0 ) (t 0,1 , f 0 ) (t 0,2 , f 0 ) . . . (t 1,0 , f 1 ) . . . (t m-1,0 , f m-1 ) (t m-1,1 , f m-1 ) . . .                                 . Theorem 6. Let F = {f 0 , . . . , f m-1 }
Definition 9 (Semi-regular sequence of degree D). Let f 0 , . . . , f m-1 be homogeneous polynomials in P whose degrees are d 0 , . . . , d m-1 respectively. We call this system a semi-regular sequence of degree D if:

1. f 0 , . . . , f m-1 = F[x 0 , . . . , x n-1 ]. 2. For all 0 ≤ i < m and g ∈ F[x 0 , . . . , x n-1 ], (deg(g • f i ) < D and g • f i ∈ f 0 , . . . , f i-1 ) =⇒ g ∈ f 0 , . . . , f i-1 .
We call D the degree of semi-regularity of the system. Definition 10 (Semi-regular sequence [START_REF] Bardet | On the complexity of Gröbner basis computation of semi-regular overdetermined algebraic equations[END_REF]). Let m > n, and f 0 , . . . , f m-1 be homogeneous polynomials of degree b in P generating an ideal I. The system is said to be a semi-regular sequence if the Hilbert series [START_REF] Becker | Gröbner Bases -A Computational Approach to Commutative Algebra[END_REF] of I with respect to the degree reverse lexicographical order is

H I (z) = k≥0 c k z k = (1 -z b ) m (1 -z) n .
Hence, for semi-regular sequences the degree of semi-regularity of the system is given by the index of the first non-positive coefficient of H I (z).

This notion can be extended to affine polynomials by considering their homogeneous components of highest degree. It is conjectured that random systems are semi-regular with overwhelming probability. For semi-regular sequences, we have the following complexity result for F 5 [START_REF] Bardet | On the complexity of Gröbner basis computation of semi-regular overdetermined algebraic equations[END_REF][START_REF] Bardet | Asymptotic expansion of the degree of regularity for semi-regular systems of equations[END_REF][START_REF] Bardet | Étude des systèmes algébriques surdéterminés[END_REF].

Theorem 7. Let F = {f 0 , . . . , f m-1 } be a set of polynomials in P . Assuming that F is a semiregular sequence, the complexity of the currently best known algorithm (i.e. F 5 ) to solve the Gröbner basis problem is given by

O n + D D ω
where 2 ≤ ω < 3 is the linear algebra constant, and D is the degree of semi-regularity of the system.

Asymptotic bounds for the degree of semi-regularity for semi-regular sequences of degree 2 can be found in [START_REF] Bardet | On the complexity of Gröbner basis computation of semi-regular overdetermined algebraic equations[END_REF]. These bounds for the degree of regularity lead to the following complexity estimates for Gröbner basis computations.

Corollary 2. Let c ≥ 0. Then for m(λ) = c • n(λ) (resp., m(λ) = c • n(λ) 2 ) quadratic polynomials in some ideal I ⊂ F q [x 0 , . . . , x n-1 ],
the Gröbner basis of I can be computed in exponential (resp., polynomial) time in n(λ).

Lemma 8 states that the IM problem is equivalent to the GB problem if we have access to an IM oracle which succeeds with overwhelming probability. Although we cannot show this equivalence in general, we may assume that the two problems are indeed equivalent when d = 1 (cf. [START_REF] Berbain | QUAD: A multivariate stream cipher with provable security[END_REF]):

Definition 11 (The GB and IM assumptions). Let P be such that n(λ) = Ω(λ). Assume b > 1, d = 1, and that m(λ) = c • n(λ) for a constant c ≥ 1. Then the advantage of any PPT algorithm in solving the GB or the IM problem is negligible as function of λ.

4 Symmetric Polly Cracker: The Noise-Free Version

Homomorphic symmetric encryption

Syntax. An arity-t homomorphic symmetric encryption scheme is specified by four PPT algorithms as follows.

1. Gen(1 λ ). This is the key-generation algorithm, and is run by the receiver. On input a security parameter, it outputs a (secret) key SK and an (evaluation) public key PK. This algorithm also outputs the descriptions of a pair of compatible spaces FunSp and MsgSp. 2. Enc(m, SK). This is the encryption algorithm, and is run by the sender. On input a message m, and a key SK, it returns a ciphertext c. 3. Eval(c 0 , . . . , c t-1 , C, PK). This is the evaluation algorithm, and is run by an evaluator. On input t ciphertexts c 0 , . . . , c t-1 , a circuit C, and the public key, it outputs a ciphertext c evl .

4. Dec(c evl , SK). This is the deterministic decryption algorithm, and is run by the receiver. On input an (evaluated) ciphertext c evl , a key SK, it returns either a message m or a special failure symbol ⊥. The syntax of a homomorphic public-key encryption scheme is defined similarly, with the exception that the encryption algorithm takes the public key rather than the secret key as an input.

Correctness

Description of the scheme

In this section we formally define the (noise-free) symmetric Polly Cracker encryption scheme. We present a family of schemes parametrised not only by the underlying computational polynomial ring scheme P, but also by a Gröbner basis generation algorithm, which itself depends on a degree bound d, and a second degree bound b. However, to satisfy our security assumption (cf. Definition 11) we require d = 1. Our parameterised scheme, which we write as SPC P,GBGen(•),d, ,b , is presented in Figure 3. The message space is Q = P ≤b /I. As a vector space, Q is determined by the leading terms LM(G) alone and hence independent of the randomness of GBGen(•). However, as a ring, Q is only independent of the randomness of GBGen(•) if d = 1; in that case Q = F q . Here, Q as a ring being independent of the randomness of GBGen(•) means that we can perform ring operations in Q such that the result, represented as an element of Q ⊂ P , can be computed without knowledge of G. For d > 1 this is not the case for multiplication. Correctness of evaluation. Let d = 1 and consider the two ciphertexts c 0 = h 0,j g j + m 0 and c 1 = h 1,j g j + m 1 . Addition and multiplication of the two ciphertexts c 0 , c 1 are given by

c 0 + c 1 = h 0,j g j + m 0 + h 1,j g j + m 1 = (h 0,j + h 1,j )g j + m 0 + m 1 , c 0 • c 1 = ( h 0,j g j + m 0 ) • ( h 1,j g j + m 1 ) = ( h 0,j g j ) • ( h 1,j g j ) + h 0,j g j • m 1 + h 1,j g j • m 0 + m 0 m 1 =
hj g j + m 0 m 1 , for some hj .

The homomorphic features follow. Correctness of addition and multiplication for arbitrary numbers of operands follow from the associative laws of addition and multiplication in P .

Compactness. This scheme is not compact for general circuits. Although additions do not increase the size of the ciphertext, multiplications square the size of the ciphertext.

Security

As we will show shortly, the above scheme only achieves a weak form of chosen-plaintext security where a limited number of ciphertexts can be eavesdropped on. We sometimes omit the subscript from schemes to ease notation. For example, in the result below, we have written SPC for SPC P,GBGen(•),d, ,b . The security guarantees are as follows.

Theorem 8. Let A be a PPT adversary against the m-IND-BCPA security of the scheme in Figure 3. Then there exists a PPT adversary B against the IM problem such that for all λ ∈ N: Conversely, let A be a PPT adversary against the IM problem. Then there exists a PPT adversary B against the m-IND-BCPA security of the scheme in Figure 3 such that for all λ ∈ N we have

Adv ind-bcpa m,SPC,A (λ) = 2 |Q| |Q| -1 • Adv im P,GBGen(•),d, ,b,m,B (λ). Initialize(1 λ ): begin (SK, PK) ← $ Gen(1 λ ); c ← $ {0, 1}; i ← 0; return PK; end Encrypt(m): begin i ← i + 1; if i > m(λ) then return ⊥; c ← $ Enc(m,
Adv im P,GBGen(•),d, ,b,m,A (λ) = Adv ind-bcpa m,SPC,B (λ).
Proof. The second part of the lemma is clear: the Sample oracle is easily simulated by asking for encryptions of 0. The Challenge oracle is answered by querying Left-Right on (0, r) where r is a uniformly chosen nonzero element of the quotient. Now deciding ideal membership directly leads to a distinguishing attack.

For the first part, we construct an algorithm B attacking the IM problem based on an algorithm A attacking the scheme as shown in Algorithm 5. To simplify the analysis, we compute the advantage of B in the IM game and deduce the advantage of B in the IM game via Lemma 7.

Symmetric-to-Asymmetric Conversion

Given the security limitation of the symmetric Polly Cracker scheme, the goal for the rest of the paper is to convert the scheme to one which is not only fully IND-CPA-secure down to the problem of computing Gröbner bases but also is homomorphic and retains its generality. Once we achieve this, then it is possible to construct a public-key scheme using the additive homomorphic features of the symmetric scheme by applying various generic conversions. In section we pursue the less ambitious goal of constructing an additively homomorphic IND-CPA-secure public-key scheme from SPC. In the literature there are two prominent conversions based on additive homomorphicity:

(A) Publish a set F 0 of encryptions of zero as (part of) the public key. To encrypt m ∈ {0, 1} compute c = f i ∈S f i + m where S is a sparse subset of F 0 [START_REF] Van Dijk | Fully homomorphic encryption over the integers[END_REF]. (B) Publish two sets F 0 and F 1 of encryptions of zero and one as (part of) the public key. To encrypt m ∈ {0, 1} compute c = f i ∈S 0 f i + f j ∈S 1 f j , with S 0 and S 1 being sparse subsets of F 0 and F 1 respectively such that the parity of |S 1 | is m. Decryption checks whether Dec(c, SK) is even or odd [START_REF] Rothblum | Homomorphic encryption: From private-key to public-key[END_REF].

The security of the above transformations rests upon the (computational) indistinguishability of asymmetric ciphertexts from those produced directly using the symmetric encryption algorithm. As noted above, since SPC is not IND-CPA-secure the above transformations cannot be used. However, when applied to a specific scheme, the transformations might still result in secure schemes. Yet, it can be shown that the security of the transformed schemes are equivalent to that of the underlying scheme. However, one could envisage a larger class of transformations which might lead to a fully secure additively homomorphic SE (or equivalently an additively homomorphic PKE) scheme. In this section we rule out a large class of such transformations. To this end, we consider PKE schemes which lie within the following design methodology.

1. The secret key is the Gröbner basis G of a zero-dimensional ideal I ⊂ P . The decryption algorithm computes c mod I = c mod G (perhaps together with some post-processing such as a mod 2 operation). Thus, the message space is (essentially) Q. As before, we assume that S(I)-and hence Q as a vector space-is known. 2. The public key consists of elements f i ∈ P . We assume that the remainders of these elements modulo the ideal I, i.e. r i = f i mod I, are known. 3. A ciphertext is computed using ring operations. In other words, it can be expressed as f = N -1 i=0 h i f i + r. Here f i are as in the public key, h i are some polynomials (possibly depending on f i ), and r is an encoding of the message in Q. 4. The construction of the ciphertext does not encode knowledge of I beyond f i . That is, we have

N -1 i=0 h i f i + r mod I = N -1 i=0 h i r i + r.
Hence we have that N -1 i=0 h i r i + r ∈ Q as an element of P . 5. The security of the scheme relies on the fact that elements f produced at step (3) are computationally indistinguishable from random elements in P ≤b .

Although conditions 1-3 impose natural algebraic restrictions on the construction, and condition 5 provides a standard way to argue for security, condition 4 imposes some real restrictions on the set of allowed transformation, but strikes a reasonable balance between allowing a general statement without ruling out too large a class of conversions. It requires that the r i and r do not encode any information about the secret key. We currently require this restriction on the "expressive power" of r i and r so as to make a general impossibility statement. If r i and r produce a nonzero element in I using some arbitrary algorithm A, we are unable to prove anything about the transformation. Furthermore, it is plausible that for any given A a similar impossibility result can be obtained if the remaining conditions hold (although we were unable to prove this).

Note that the two transformations listed above are special linear cases of this methodology. For transformation (A) we have that f i ∈ I (hence r i = 0), h i ∈ {0, 1}, and r = m. For transformation (B) we have

r i = 0 if f i ∈ F 0 , r i = 1 if f i ∈ F 1 , h i ∈ {0, 1}
, and r = 0.

To show that any conversion of the above form cannot lead to an IND-CPA-secure public-key scheme, we will use the following theorem from commutative algebra which was already used in [START_REF] Barkee | Why you cannot even hope to use Gröbner bases in Public Key Cryptography: An open letter to a scientist who failed and a challenge to those who have not yet failed[END_REF] to discourage the use of Gröbner bases in the construction of public-key encryption schemes.

Theorem 9 (Dickenstein et al. [START_REF] Dickenstein | The membership problem for unmixed polynomial ideals is solvable in single exponential time[END_REF]). Let I = f 0 , . . . , f m-1 be an ideal in the polynomial ring P = F[x 0 , . . . , x n-1 ], h be such that deg(h) ≤ D, and let h -(h mod I) = m-1 i=0 h i f i , where h i ∈ P and deg(h i f i ) ≤ D. Let G be the output of some Gröbner basis computation algorithm up to degree D (i.e. all computations with degree greater than D are ignored and dropped). Then h mod I can be computed by polynomial reduction of h via G.

The main result of this section is a consequence of the above theorem. It essentially states that uniformly sampling elements of the ideal up to some degree is equivalent to computing a Gröbner basis for the ideal. Note that Theorem 9 in itself does not provide this result, since there is no assumption about the "quality" of h. Hence, to prove this result we first show that the above methodology implies sampling as in Theorem 9 but with uniformly random output. Theorem 9 then allows us to compute normal forms, which in turn allows deciding ideal membership with success probability 1. This together with the fact that h is random allows us to compute a Gröbner basis by Lemma 8. Note that although we arrive at the same impossibility result using Corollary 2, the approach taken below better highlights the structure of the underlying problem.

Theorem 10. Let G = {g 0 , . . . , g n-1 } be the reduced Gröbner basis of a zero-dimensional ideal I ⊂ P where each deg(g i ) ≤ d. Assume that S(I) is known and that Q = P ≤b /I has s elements. Furthermore, let F = {f 0 , . . . , f N -1 } be a set of polynomials with known r i = f i mod I. Let A be a PPT algorithm which given F produces elements f =

h i f i + r with deg(f ) ≤ b, h i ∈ P, b ≤ B, deg(h i f i ) ≤ B, and (f mod I) = h i r i + r.
Suppose further that the outputs of A are computationally indistinguishable from random elements in P ≤b . Then there exists an algorithm which computes a Gröbner basis for

I from F in O n ωB + |LM(G)| • s • n 2b field operations. Proof. Let f = N -1 i=0 h i f i + r. Writing fi = f i -r i , we get that h = f -(f mod I) = N -1
i=0 h i fi + r for some r ∈ P ≤b /I. Hence h satisfies the condition of Theorem 9, and we can compute the remainder of all elements of degree b produced by A by computing a Gröbner basis up to degree B. From Theorem 7 we know that this costs O n ωB field operations. We now have an algorithm which returns the remainder for arbitrary elements of P ≤b with probability 1. This follows since h is computationally indistinguishable from random elements in P ≤b . More explicitly, we can generate the system parameters, including the Gröbner basis, and provide the algorithm with either an output of A or a random element. We can check for the correctness of the answer using the basis. Any non-negligible difference in algorithm's success rate translates to a break of the indistinguishability of the outputs of A. Now given an algorithm which computes normal forms, it is trivial to construct an algorithm which decides ideal membership: compute the normal form and compare with zero. Furthermore, by Lemma Therefore, if for some degree b ≥ d computationally uniform elements of P ≤b can be produced using the public key f 0 , . . . , f N -1 , there is an attacker which recovers the secret key g 0 , . . . , g n-1 in essentially the same complexity. Hence, while conceptually simple and provably secure up to some bound, our symmetric Polly Cracker scheme SPC P,GBGen(•),d, ,b does not provide a valid building block for constructing a fully homomorphic public-key encryption scheme. We also stress that SPC is secure down to the IM problem with noticeable advantage, but in order to construct an adversary against the GB problem we need an IM oracle with overwhelming advantage.

Remark. Although the above impossibility result is presented for public-key encryption schemes, due to the equivalence result of [START_REF] Rothblum | Homomorphic encryption: From private-key to public-key[END_REF], it also rules out the existence of additively homomorphic symmetric Polly Cracker-style schemes with full IND-CPA security.

Our goal now is to achieve full IND-CPA security for a symmetric Polly Cracker-type scheme down to the hardness of computing Gröbner bases. To this end, we introduce noisy variants of GB and IM in the next section. These variants ensure that the conditions of Theorem 10 do not hold any more. In particular, the condition that r i = f i mod I are known will be no longer valid.

Gröbner Bases with Noise

In this section, we introduce noisy variants of the problems presented in Section 3. The goal is to lift the restriction on the number of samples that the adversary can obtain and, following a similar design methodology to Polly Cracker, construct an IND-CPA-secure scheme. Put differently, we consider problems that naturally arise if we consider noisy encoding of messages in SPC. Similarly to [START_REF] Van Dijk | Fully homomorphic encryption over the integers[END_REF][START_REF] Regev | The learning with errors problem[END_REF] we expect a problem which is efficiently solvable in the noise-free setting to be also hard in the noisy setting. We will justify this assumption in Section 6.1 by arguing that our construction can be seen as a generalisation of [START_REF] Van Dijk | Fully homomorphic encryption over the integers[END_REF][START_REF] Regev | The learning with errors problem[END_REF].

The games below will be parametrised by a noise distribution χ. The discrete Gaussian distribution is of particular interest to us. Definition 13 (Discrete Gaussian distribution). Let α > 0 be a real number and q ∈ N. The discrete Gaussian distribution χ α,q , is a Gaussian distribution rounded to the nearest integer and reduced modulo q with mean zero and standard deviation αq.

In what follows we assume that χ is defined over Q, i.e. for d > 1 we have that χ is a multidimensional noise distribution. For example, χ may simply consist of |S(I) ≤b | independent discrete Gaussian distributions, one for each m ∈ S(I) ≤b . However, as pointed out in [START_REF] Lyubashevsky | On ideal lattices and learning with errors over rings[END_REF] simply using the same Gaussian on each monomial is possibly not the best choice. Another notable special case is q = 2. In this case, χ α,2 is a Bernoulli distribution with just one parameter 0 < p < 1, the probability that 1 is returned.

We now define a noisy variant of the Gröbner basis problem. The task here is still to compute a Gröbner basis for some ideal I. However, we are now only given access to a noisy sample oracle which provides polynomials which are not necessarily in I but rather are "close" approximations to elements of I. Here the term "close" is made precise using a noise distribution χ on Q.

Definition 14 (The Gröbner basis with noise (GBN) problem). The Gröbner basis with noise problem is defined through game GBN P,GBGen(•),d, ,b,χ shown in Figure 5. The advantage of a PPT algorithm A in solving the GBN problem is The essential difference between the noisy and noise-free versions of the Gröbner basis problem is that by adding noise we have eliminated the restriction on the adversary to call the Sample oracle a bounded number of times. Put differently, if χ is the delta distribution, the GBN problem degenerates to the GB problem with an unbounded number of samples. Hence, in this case the GBN problem is easy. On the other hand if χ is uniform, the GBN problem is information-theoretically hard. Thus, the choice of χ greatly influences the hardness of the GBN problem. We leave an in-depth investigation of the noise parameter to future work.

Adv gbn P,GBGen(•),d, ,b,χ,A (λ) := Pr GBN A P,GBGen(•),d, ,b,χ (λ) ⇒ True . Initialize(1 λ , P, d): begin P ← $ P λ ; G ← $ GBGen(1 λ , P, d, ); return (1 λ , P ); end Sample(): begin f ← $ P ≤b ; e ← $ χ; f ← f -(f mod G) + e; return f ; end Finalize(G ): begin return (G = G ); end
As in the noise-free setting, we can ask various questions about the ideal I generated by G. One such example is solving the ideal membership problem with access to noisy samples from I. In our definition the adversary wins the game if it can distinguish whether an element was sampled uniformly from P ≤b or from I ≤b + χ.

Definition 15 (The ideal membership with noise (IMN) problem). The ideal membership with noise problem is defined through game IMN P,GBGen(•),d, ,b,χ shown in Figure 6. The advantage of a PPT algorithm A in solving the IMN problem is defined by

Adv imn P,GBGen(•),d, ,b,χ,A (λ) := 2 • Pr IMN A P,GBGen(•),d, ,b,χ (λ) ⇒ True -1.
Initialize Our definition of the IMN problem can be seen as an instantiation of Gentry's ideal coset problem [START_REF] Gentry | A fully homomorphic encryption scheme[END_REF] since both problems require distinguishing uniformly chosen elements in P ≤b from those in I ≤b + χ. Now, a pressing question is equivalence of the GBN and the IMN problem, i.e. decision-to-search reduction. We have been able to prove this equivalence in the special case d = 1 (see below). Intuitively, a straightforward reduction fails when d > 1 because an IMN oracle does not have to consider the coefficient of every monomial in S(I) ≤b when deciding ideal membership to be successful. On the other hand, a GBN oracle must recover coefficients of all monomial. For example, let G = {x 0 +s 0 x n-1 , . . . , x n-2 +s n-2 x n-1 , x2 n-1 +s n-1 x n-1 } and hence S(I) ≤b = {x n-1 , 1}. Assume the noise distribution χ is such that the coefficient for x n-1 of the noise is uniform ∈ F q , while the constant coefficient is always zero. For this shape and noise, it is easy to solve the IMN problem: any f ∈ P ≤b with a nonzero constant coefficient is not an element of I = G . However, turning this oracle into an adversary against the GBN problem would require to recover all s i which are not even considered by IMN. Furthermore, the coefficients of x n-1 are information-theoretically hidden, so the distribution on I ≤b + χ does not even depend on the s i (cf. [START_REF] Herold | Polly cracker, revisited, revisited[END_REF]).

In fact, this type of counterexample is essentially the only thing that can go wrong: for a weaker variant of the IMN problem, which we aptly call the weak IMN problem (and define below in such a way to ensure that the adversary has to consider all monomials) we are able to show a reduction to the GBN problem. In this definition we let s := dim(Q) = |S(I) ≤b |, which is independent of the randomness of GBGen(•). Given χ, we also define the distributions χ t for t ∈ S(I) ≤b by sampling an element e from Q according to χ and setting all but the coefficient corresponding to t to some independent uniform values. 2 Hence, all coefficients except that corresponding to t are informationtheoretically blinded. Any algorithm which can distinguish samples following I ≤b +χ t from uniform samples in P ≤b for all t can be used to solve the GBN problem.

Definition 16 (The weak ideal membership with noise (WIMN) problem). The weak ideal membership with noise problem is defined through games WIMN G,χ,t for t ∈ S(I) ≤b shown in Figure 7. The advantage of a PPT algorithm A in solving the WIMN problem is defined by

Adv wimn P,GBGen(•),d, ,b,χ,A (λ) := E G min t 2 • Pr WIMN A G,χ,t (λ) ⇒ True -1 ,
where the expectation is taken over G sampled from GBGen(1 λ , P, d, ). Our definition of advantage is somewhat non-standard but it bears similarities to game definitions in recent work on multi-instance security [START_REF] Bellare | Multi-instance security and its application to passwordbased cryptography[END_REF]. Indeed, we require that only those WIMN adversaries win the overall game which work for all t ∈ S(I) ≤b for a particular Gröbner basis G. As we shall see, only such adversaries allow us to recover the full Gröbner basis. Also, we note that the term "weak" is justified by the relation between WIMN and IMN. It is easy to see that if the IMN problem is hard, then so is the WIMN problem, while, as we have seen, the converse is not necessarily true. Finally, if d = 1 the IMN and WIMN problems are equivalent. We answer queries to WIMN's Challenge t and Sample oracles with answers from IMN's Sample oracle. If IMN's Sample follows I + χ, WIMN runs in the right environment. If IMN's Sample follows a uniform distribution on P ≤b then WIMN's receives no information about the problem instance and hence has advantage zero.

Initialize(G, χ, t ): begin c ← $ {0, 1}; return (1 λ , P, t ); end Sample(t): begin f ← $ P ≤b ; e ← $ χ t ; f ← f mod G; f ← f -f + e; return f ; end Challenge t (): begin f ← $ P ≤b ; if c = 1 then e ← $ χ t ; f ← f mod G; f ← f -f + e; return f ; end
We next show that when q and |S(I) ≤b | are polynomial in λ and the WIMN problem is hard, the GBN problem is also hard. The intuition behind the reduction is that the adversary can exhaustively search for the coefficients for each monomial t ∈ S(I) ≤b independently and then use the WIMN solver for t to verify its guess. This is formalised in the lemma below.

Lemma 9. (WIMN easy =⇒ GBN easy) Suppose the finite field size q and |S(I) ≤b | are polynomial in λ. Then for any polynomial p and any PPT adversary A against the WIMN problem there exists a PPT adversary B against the GBN problem such that

Adv gbn P,GBGen(•),d, ,b,χ,B (λ) ≥ (1 -o(1)) • Adv wimn P,GBGen(•),d, ,b,χ,A (λ) + negl(λ)
for all values of λ ∈ N such that

Adv wimn P,GBGen(•),d, ,b,χ,A (λ) ≥ 1 p(λ) .
Proof. We construct an adversary B against GBN from adversary A against WIMN in Algorithm 6. Algorithm 6 runs A in the environment it expects. This is clear for calls to the Sample(t) oracle.

For the Challenge t () oracles, first assume that we guessed correctly and β is the coefficient of t of g i ∈ G with leading monomial m. Since g i and m + β • t differ only by an element in Q with coefficient 0 for t , which is blinded by e, the challenge f + a • (m + β • t ) + e follows the same distribution as f + a • g i + e. This in turn has the same distribution as I + χ t as required. On the other hand, if we guessed incorrectly then f + a • (m + b • t ) + e is uniform as a is independently uniform in F q and e is independently uniform for all coefficients of the quotient = t . Hence, A either sees elements following I + χ t or uniform in P ≤b .

Algorithm Algorithm 6 is correct and returns the reduced Gröbner basis G such that G = I. For this, first note that whenever we make a fixed wrong guess β, the distribution of the challenge f + a • (m + β • t ) + e presented to A does not depend on the value of β due to the multiplication by the uniform a. As a consequence, we can amplify the success probability of A by r(λ) = p(λ) 2 λ-fold repetition: Call G good if the minimal (over t ) conditional advantage of A (conditioned on G) is at least 1 p(λ) log λ . By a standard argument, the probability that G is good must then be at least (1 -1 log λ )Adv wimn P,GBGen(•),d, ,b,χ,A (λ). For those good G, our choice of number of repetitions r is large enough to amplify the advantage A to overwhelming using Chernoff-Hoeffding bounds. Hence in each majority vote we will pick the correct value with overwhelming probability, so G = G holds with overwhelming probability for good G, which finishes the proof.

Remark. In the lemma above, we were able to amplify the success probability of any adversary which solves the WIMN problem with non-negligible advantage to one which has an overwhelming advantage via Chernoff bounds, since we have no a priori bound on the number of queries as we had in the noiseless setting. In contrast to Lemma 8 we also do not require |Q| to be polynomial in λ but only |S(I) ≤b | and the field size q. Finally, because WIMN treats every monomial t independently, "structural errors" as in described after Lemma 8 are ruled out.

We note that when d = 1 Lemma 9 implies IMN is hard if GBN is hard, as in this case WIMN and IMN are equivalent. Furthermore, it is easy to see that in this case a converse reduction can also be constructed because a WIMN adversary expects samples from Sample(1) which GBN's Sample oracle returns. Hence, for d = 1 we an equivalence between the IMN, WIMN, and GBN problems holds. Moreover, in this case, we can also demonstrate an average-case-to-worst-case reduction analogous to that known for the LWE problem. That is, for d = 1 we show below that if we can solve the IMN problem for a polynomial fraction of instances, then we can also solve it for all instances.

Lemma 10 (Average-case-to-worst-case reduction for d = 1). Let A be a PPT adversary against GBN P,GBGen dense (•),1, ,b,χ that is successful for a polynomial fraction of all secrets. Then there exists a PPT adversary B which solves GBN P,G,1, ,b,χ on all instances G. That is, the basis is no longer sampled at random, but is fixed to be a specific value G. More precisely

Adv gbn P,G,1, ,b,χ,B (λ) = 1 -negl(λ)
for all values of G, provided that Adv gbn P,GBGen dense (•),1, ,b,χ,A (λ) > 1 p(λ) for a polynomial p.

Proof. The proof is similar to the proof of [START_REF] Regev | The learning with errors problem[END_REF]Lemma 3.2]. The idea is to find a suitable class of transformations which allow us to randomise a specific Gröbner basis G. We remark that G should be a valid output of GBGen dense ()

for d = 1: it is of the form G = G s := [x 0 -s 0 , . . . , x n-1 -s n-1 ]
where s i ∈ F. We also denote by I s the ideal generated by G s and by J = I s,≤b + χ the probability distribution on P ≤b presented to B. We consider the transformation L t : P -→ P defined by

L t (f ) := f (t) for any t := (x 0 -t 0 , x 1 -t 1 , . . . , x n-1 -t n-1 ) with t i ∈ F q .
We remark that the image I of I s under L t is I s+t (i.e. the ideal generated by G s+t ). Indeed, since L t is a bijection, there is a one-to-one correspondence between the zeroes of I and I s . This implies that the variety corresponding to I only consists of the single element s + t. Therefore, the unique Gröbner basis of I is G s+t , and I = I s+t . Therefore, L t allows to map I s + χ to I s+t + χ. It is clear that G s+t is a valid output of GBGen dense (). Moreover, the distribution of G s+t is uniform on the image of GBGen dense (). Now, we use A a polynomial number of times on L t (J ), each using a freshly chosen and uniform t ← $ F n . With overwhelming probability, A will output the correct Gröbner basis G s+t at least once, from which we can recover s (and hence G s ) and verify against J .

Note that we can verify in PPT whether a given s is correct for J = I s,≤b + χ. Indeed, as soon as s = s then J (s )-the evaluation of polynomials distributed according to J on s -is distributed according to χ, because I s (s ) = 0. In contrast, whenever s = s , J (s ) = I s,≤b (s ) + χ is uniform. This is the case, because the evaluation of a polynomial at a given point is a surjective linear map from I s,≤b to F, and such maps preserve the uniform distribution. Hence, to verify that a given s is correct for J we have to decide whether each polynomial in J (s ) is uniform or follows χ. We can obtain overwhelming confidence in polynomial time if χ is a Gaussian distribution [START_REF] Regev | On lattices, learning with errors, random linear codes, and cryptography[END_REF]Lemma 3.6].

More generally, we may use A to verify in PPT whether a given s is correct for J = I s,≤b + χ for any distribution χ. Indeed, to verify s against s, we test whether the probability that A returns G u when presented with samples from I u,≤b + J (s ) for a uniform u ∈ F n is ≥ 1 p or equal to 1 q n . Since 1 p -1 q n is noticeable, we can obtain overwhelming confidence in polynomial time.

We note that this proof strategy does not apply to d > 1 for two reasons. First, it is not necessarily true that we have more maps L t than secrets as the space of the secrets increases with d but the number of maps does not. Second, if we have noise on non-constant coefficients our maps change the noise distribution.

Hardness assumptions and justifications

In this subsection we investigate the hardness of the GBN, WIMN, and IMN problems. We first consider the GBN problem and relate it to the well-established LWE problem [START_REF] Regev | The learning with errors problem[END_REF]. Then, we discuss the relation between the GBN problem and various approximate GCD problems [START_REF] Van Dijk | Fully homomorphic encryption over the integers[END_REF]. Third, we discuss the special case q = 2 by relating the GBN problem to the well-known Max-3SAT problem, and more generally when d = 1 to Max-MQ, the problem of finding an assignment for polynomials f 0 , . . . , f m-1 ∈ F q [x 0 , . . . , x n-1 ] such that the majority of them evaluate to zero. Finally, we consider known attacks against the GBN problem. We start by recalling the LWE problem.

Definition 17 (The learning with errors (LWE) problem). The LWE problem is defined though game LWE n,q,χ shown in Figure 8. The advantage of a PPT algorithm A in solving LWE is Adv lwe n,q,χ,A (λ) := Pr LWE A n,q,χ (λ) ⇒ True . From the definition of LWE it is easy to see that GBN can be considered as a nonlinear generalisation of LWE if q is a prime. In other words, we have equivalence between these problems if we consider b = d = 1 in GBN. This is formalised in the next lemma.

Initialize(1 λ ): begin n ← n(λ); s ← $ Z n q ; return (1 λ , n); end Sample(): begin a ← $ Z n q ; e ← $ χ; b ← e + i a i s i ; return (a
Lemma 11 (LWE hard =⇒ GBN hard for b = d = 1). Let q be a prime. Then for any PPT adversary A against the GBN problem3 with b = d = 1, there exists a PPT adversary B against the LWE problem such that Adv gbn P,GBGen(•),1, ,1,χ,A (λ) = Adv lwe n,q,χ,B (λ).

Proof. We construct an adversary B against the LWE problem based on an adversary A against the GBN problem for d = 1 and b = 1. Algorithm B initialises A with P . Whenever A calls its Sample oracle, B queries its own Sample oracle to obtain (a, b) where a = (a 0 , . . . , a n-1 ). It returns a i x i -b to A. This is a valid GBN sample of degree b = 1. The Challenge oracle is answered similarly. When A calls its Finalize on G, since d = 1, we can assume w.l.o.g. that G is of the form [x 0 -s 0 , . . . , x n-1 -s n-1 ] with s i ∈ F q . Algorithm B terminates by calling its Finalize oracle on s = (s 0 , . . . , s n-1 ).

Adversary B is successful whenever A is. Indeed, from a i x i -b = 0 it follows that a i s i = e and hence that s satisfies the LWE samples (a, a i s i + e). Finally, it is easy to see that B runs in polynomial time and uses polynomially many samples. This result can be generalised to any b = d if we allow = n and consider the amortised variant of Regev's LWE scheme from [START_REF] Peikert | A framework for efficient and composable oblivious transfer[END_REF] where each monomial m of Q <b corresponds to one parallel instance of Regev's original scheme. Note, however, that = n implies an exponentially large quotient. Let q be a prime, and assume χ outputs e ← $ χ , e = m∈Q e m • m, where the e m are chosen independently, their distribution possibly depending on m. Then for any PPT adversary A against the GBN problem with b = d, ∃ PPT adversary B against the amortised LWE from [START_REF] Peikert | A framework for efficient and composable oblivious transfer[END_REF] such that Adv gbn P,GBGen dense (•),d,n,b,χ,A (λ) ≤ Adv lwe n,q,χ,B (λ).

Proof (Sketch). Samples from GBN if b = d are necessarily of the form c = t i g i + e where t i ∈ F q . Write c = c m m where the sum is over all monomials in c. The coefficients ∈ Q of c are c m = t i g i, m + e m where m ∈ Q, g i, m is the coefficient for m in g i , and e m is the coefficient of m in e. These are noisy random linear combinations of the secrets g i, m as in LWE. For m ∈ Q <b , the g i, m are uniform. All monomials ∈ Q are of the form x d i and we have that the coefficient of x d i = LM(g i ) is t i , exactly as in the amortised construction from [START_REF] Peikert | A framework for efficient and composable oblivious transfer[END_REF].

Note that for coefficients m ∈ Q =b , we can get LWE instances where some of the secret coefficients g i, m are always zero and so these instances will be easier, which is why we don't have equality between the advantages above.

Relation to the approximate GCD problem. The GBN problem for n = 1 is the approximate GCD problem over F q [x]. Contrary to the approximate GCD problem over the integers (cf. [START_REF] Van Dijk | Fully homomorphic encryption over the integers[END_REF][START_REF] Coron | Fully homomorphic encryption over the integers with shorter public keys[END_REF][START_REF] Chen | Faster algorithms for approximate common divisors: Breaking fullyhomomorphic-encryption challenges over the integers[END_REF][START_REF] Cohn | Approximate common divisors via lattices[END_REF]), this problem has not yet received much attention (a variant of this problem is investigated in [START_REF] Cohn | Approximate common divisors via lattices[END_REF]), and hence it is unclear under which parameters it is hard. However, as mentioned in Section 2, the notion of a Gröbner basis can be extended to Z[x 0 , . . . , x n-1 ], which in turn implies a version of the GBN problem over Z. This can be seen as a direct generalisation of the approximate GCD problem in Z.

The q = 2 case. Recall that if b = d = 1 we have an equivalence with the LWE problem (or the well-known problem of learning parity with noise if q = 2). More generally, for d = 1 we can reduce Max-3SAT instances to GBN instances by translating each clause individually to a Boolean polynomial. However, in Max-3SAT the number of samples is bounded and hence this reduction only shows the hardness of GBN with a bounded number of samples. Still, the Gröbner basis returned by an arbitrary algorithm A solving GBN using a bounded number of samples will provide a solution to the Max-3SAT problem. Vice versa, we may convert a GBN instance for d = 1 to a Max-3SAT instance (more precisely a Partial Max-SAT instance where some clauses must be satisfied) by running an ANF-to-CNF conversion algorithm [START_REF] Bard | Efficient methods for conversion and solution of sparse systems of low-degree multivariate polynomials over GF(2) via SAT-solvers[END_REF].

The d = 1 case. When d = 1 the GBN problem is closely related to the Max-MQ problem. In [START_REF] Håstad | A well-characterized approximation problem[END_REF] it was shown that if all f i are square-free it is NP-hard to approximate this problem to within a factor of q -for a small positive number. Latter [START_REF] Zhao | Minimal achievable approximation ratio for MAX-MQ in finite fields[END_REF] proves that the minimal approximation ratio that can be achieved in polynomial time for Max-MQ is q. The most significant difference between GBN for d = 1 and Max-MQ is that the latter treats polynomials either as correct or incorrect, and no notion of "smallness" of noise exists. It follows from the properties of the Gaussian distribution that a Max-MQ oracle solves the GBN problem for d = 1.

Known attacks. be the number of monomials up to degree b. Let M : P -→ F N q be a mapping of polynomials in P to vectors in F N q by assigning to the ith component of the image vector the coefficient of the ith monomial ∈ M ≤b . Then, in order to reduce GBN with n variables and degree b to LWE with N variables, reply to each LWE Sample query by calling GBN's Sample oracle to retrieve f , computing v = M(f ) and returning (a, b) with a := (v N -1 , . . . , v 1 ) and b := -v 0 . When the LWE adversary queries Finalize on s, query GBN's Finalize oracle with [x 0 -s 0 , . . . , x n-1 -s n-1 ]. Correctness follows from the correctness of linearisation in the noise-free setting [START_REF] Arora | New algorithms for learning in presence of errors[END_REF]. Furthermore, the LWE problem in N variables and with respect to the discrete Gaussian noise distribution χ α,q is considered to be hard if

α ≥ 3 2 • max 1 q , 2 -2 √ N log q log δ
for an appropriate choice of δ, which is the quality of the approximation for the shortest vector problem. With the current lattice algorithms δ = 1.01 is hard, and δ = 1.005 is infeasible [START_REF] Micciancio | Lattice-based cryptography[END_REF].

Perhaps the most interesting attack on the LWE problem from the perspective of this work is that due to Arora and Ge [START_REF] Arora | New algorithms for learning in presence of errors[END_REF]. This attack reduces the problem of solving linear systems with noise to the problem of solving (structured) nonlinear noise-free systems. We may apply this technique directly to GBN, i.e. without going through LWE first, and reduce it to GB with large b. However, it seems this approach does not improve the asymptotic complexity of the attack. Finally, certain conditions to rule out exhaustive search for the noise (and reduction to a noise-free system) must be imposed. We conclude this section by explicitly stating our hardness assumption.

Definition 18 (The GBN and WIMN assumptions). Let b, d ∈ N with b ≥ d. Let P be a polynomial ring distribution and χ α,q be the discrete Gaussian distribution. Suppose the parameters n, α, and q (all being a function of λ) satisfy the following set of conditions:

1. n ≥ b √ λ to rule out linearisation attacks. 2. GBGen(•) is instantiated with GBGen dense (•), and q and |S(I) ≤b | are poly(λ) such that Lemma 9 applies. 3. (αq) nd ≈ 2 λ so exhaustive search over the noise or the secret key is ruled out. 4. For N := n+b b , α and q are chosen such that the advantage of any PPT algorithm in solving the LWE problem with dimension N , modulus q and noise distribution χ α,q is negligible as a function of λ.

Then the advantage of any PPT algorithm in solving the GBN or the WIMN problem is negligible as a function of λ.

Polly Cracker with Noise

We present a fully IND-CPA-secure Polly Cracker-style symmetric encryption scheme and prove it secure down to the hardness of the GBN problem. Our parameterised scheme, SPCN P,GBGen(•),d, ,b,χ , is shown in Figure 9. Here we represent elements in F q as integers in the interval [-q 2 , q 2 ]. This convention is also used in the definition of noise. All the computations are performed in the ring P as generated by Gen. Furthermore, we assume that gcd(q, 2) = 1. This condition is needed for the correctness and the security of our scheme. The message space is F 2 (although we note that this can be generalised to other small fields).

Correctness of evaluation.

For any choice of d, SPCN P,GBGen(•),d, ,b,χ is additively homomorphic. However, to achieve multiplicative homomorphicity we need to set d = 1 as in Section 4. Hence, we restrict our attention to d = 1 and define the size of the noise as the logarithm of distance to zero over the integers. Addition and multiplication of the two ciphertexts c 0 = h 0,j g j +2e 0 +m 0 and c 1 = h 1,j g j + 2e 1 + m 1 are given by

c 0 + c 1 = h 0,j g j + 2e 0 + m 0 + h 1,j g j + 2e 1 + m 1 = (h 0,j + h 1,j )g j + 2(e 0 + e 1 ) + (m 0 + m 1 ), c 0 • c 1 = ( h 0,j g j + 2e 0 + m 0 ) • ( h 1,j g j + 2e 1 + m 1 ) = ( h 0,j g j ) • ( h 1,j g j + 2e 1 + m 1 ) + (2e 0 + m 0 ) • ( h 1,j g j ) + (4e 0 e 1 + 2e 0 m 1 + 2e 1 m 0 + m 0 m 1 )
= hj g j + 2(2e 0 e 1 + e 0 m 1 + e 1 m 0 ) + m 0 m 1 for some hj .

The homomorphic features follow. Correctness of addition and multiplication for arbitrary numbers of operands follow from the associative laws of addition and multiplication in P up to overflows. Permitted circuits. Circuits composed of Add and Mult gates can be seen as multivariate Boolean polynomials in t variables over F 2 . We can consider the generalisation of this set of polynomials to F q (i.e., when the coefficients are in F q ). In order to define the set of permitted circuits (which will be parametrised by α > 0) we first embed the Boolean polynomials into the ring of polynomials over Z. For χ α,q , the probability of noise being larger than kαq is at most exp(-k 2 /2). We say that a circuit is valid if for any (s 0 , . . . , s t-1 ) with s i ≤ tαq the outputs are less than q for some parameter t. This restriction ensures that no overflows occur when polynomials are evaluated over F q . Section 9 discusses how to set α and q in order to allow for evaluation of polynomials of some fixed degree µ.

Compactness. Additions do not increase the size of the ciphertext, but they do increase the size of the error by at most one bit. Multiplications square the size of the ciphertext and increase the bit size of the noise by approximately log(8e 0 e 1 ) bits The theorem below states the security properties of the above scheme.

Theorem 11. Let b ≥ d be arbitrary and let A be a PPT adversary against the IND-CPA security of the scheme in Figure 9. Then there exists a PPT adversary B against the WIMN problem such that for all λ ∈ N we have

Adv ind-cpa SPCN ,A (λ) = 2 • Adv wimn P,GBGen(•),d, ,b,χ,B (λ).
Proof. We construct an algorithm B against the WIMN problem for some arbitrary but fixed t ∈ S(I) ≤b based on A attacking the IND-CPA security of the scheme. Roughly speaking, this algorithm runs A and answers its encryption queries using the provided sample oracle. Algorithm B answers A's left-or-right query by constructing the ciphertext components for t ∈ S(I) ≤b using its sample oracle when t = t , and its challenge oracle when t = t . See Algorithm 7 for the details.

B with the help of a (unidirectional) re-encryption key K A→B . Hence, after each multiplication we can apply this re-encryption for K A→A to reduce the size of our ciphertexts at the cost of increasing the noise.

We discuss how one can achieve the above functionality for our scheme. Since the construction only uses additions, this feature also applies to the LWE-based encryption scheme as previously observed in 4 . Let P = F q [x 0 , . . . , x n-1 ] and suppose that G A = {g 0 , . . . , g n-1 } and G B = {h 0 , . . . , h n-1 } are two (possibly distinct) Gröbner bases for ideals I A ⊂ P and I B ⊂ P . Finally, suppose P/I A = P/I B as vector spaces (the equality always holds for d = 1). To re-encrypt a ciphertext intended for G A under key G B we first generate a re-encryption key G A→B using Algorithm 8, and then use this key in Algorithm 9 -the re-encryption algorithm -to obtain a ciphertext under G B .

The central idea behind these algorithms is the equivalence between different representations of elements in P/I. While for the most part of this work we identify elements in P/I with elements f mod I, Algorithms 8 and 9 make use of different representations of elements in P/I. For example, if x + 1 is an element of a Gröbner basis G A , both f = x and r = -1 represent the same element in P/I A since f mod G A = r, i.e. x mod G A = -1. Hence, if we are interested in P/I A (our messages live in P/I) we can use f and r interchangeably. That is, for some f = c i m i with monomials m i and coefficients c i ∈ F q , we can compute the first decryption step, i.e. m + 2e = f mod I A , as (c i m i mod I A ). Furthermore, since P/I A = P/I B , we may encrypt the encoded message m + 2e for G B by computing

f = (f mod I A ) + f = (c i m i mod I A ) + f = m + 2e + f for f ∈ I B .
Hence, we get that f mod I B = f mod I A .

f 2 j •m ← i∈s f i ; 8 GA→B[2 j • m] ← f 2 j •m + 2 j • m ; 9 return GA→B;
Now, using the key G A→B we may re-encrypt a ciphertext f under G A to a ciphertext f under G B using Algorithm 9.

Lemma 13. Let G A be a Gröbner basis. Let f 0 , . . . , f s-1 be polynomials of degree b encrypting zero under a Gröbner basis G B . We set G A→B = Re-encryptionKey(G A , [f 0 , . . . , f s-1 ], b, y) for some where 2 e 2 j •m is the noisy part of f 2 j •m , namely 2 e 2 j •m = f 2 j •m mod G B . Now, for any polynomial f , we denote by T(f ) the terms of f . Recall that a term is a monomial times a constant. We have Finally, if |e max | is the maximal bit size of noise in any of the f i used to generate G A→B by Algorithm 8, then entries of G A→B have maximal noise of bit size log(y) + |e max |. Now, given a polynomial of degree b, Algorithm 9 performs at most log(q) n+b b ≤ log(q) (n + 1) b additions of polynomials with noise of size log(y) + |e max |. The bit size of the noise added in Algorithm 9 will be (log log(q) + b log(n + 1) + log(y) + |e max |). Additionally, Algorithm 9 will "copy" the noise from f .

For the security, we first discuss re-encryption under the same key, i.e. when G A = G B . If b = b , the key G A→A can be publicly constructed given access to encryptions of zero by requesting a fresh encryption of zero f and storing G A→A [2 j •m] = 2 j •m+f . Since (f mod I) = 2e for some small error term e, it holds that f + 2 j • m mod I = (2 j • m mod I) + 2e. Hence, G A→A is a correct re-encryption key which can be generated given access only to encryptions of zero, and no additional information is leaked. This implies a limited form of key-dependent message security in the standard model: the least significant bits of the constant terms of the Gröbner basis elements are encrypted.

However, this argument does not go through for b > b . While it is easy to construct elements f which satisfy f mod I ≈ 2 j • m mod I for m a monomial of degree at least b + 1 and at most b with access to encryptions of zero, it is not easy to produce such an element f with degree ≤ b and small noise. Yet, for G A → G B with G A = G B security of re-encryption can be shown under the WIMN assumption. That is, any adversary breaking the IND-CPA security of the scheme with access to the re-encryption key G A→B can be turned into an adversary breaking the IMN problem. A full proof of this for the special case of LWE is presented in [START_REF] Brakerski | Efficient fully homomorphic encryption from (standard) LWE[END_REF], where this technique was independently proposed.

Parameters

Picking parameters for SPCN essentially reduces to fulfilling our correctness requirements and to ensuring that the linearised LWE instance is hard. We emphasise that a public-key version of SPCN is not competitive with Ring-LWE based schemes which have a public-key at least a factor of N = n+b b smaller. Furthermore, recent constructions apply additional techniques to manage parameter growth as the multiplication depth increases such as modulus switching, which we do not consider in this work. However, for completeness, we now give concrete suggestions for various parameters that are involved in our scheme. This section is to be understood as a sanity check showing how all parts fit together and not as a proposal of SPCN as a contender for an efficient somewhat homomorphic encryption scheme -it could not be such a contender as it attempts to provide a more unified view on such schemes.

We denote by µ the maximal degree of the Boolean polynomials corresponding to the circuits that we wish to support, and by λ the security parameter as before. One restriction on our choice of parameters is imposed by the requirement that decryption error probability on evaluated ciphertexts should be low. Since additions have a small effect on the noise, we concentrate on the degree of polynomials. This means that in order to allow for polynomials of degree up to µ and at most a, say, 2 -20 decryption error probability, we must have Pr [|e µ | ≥ q/2 : e ← $ χ] < 2 -20 . Hence (cf. Section 7) we need to ensure that exp(k 2 /2) > 2 20 and k(αq) < 1/2 • µ √ q.

Another set of restrictions comes from the conditions stated in our intractability assumption in Definition 18, i.e. that the linearised LWE instance should be hard. For this, we make the somewhat arbitrary choice of b = 2 and denote by N = n+b b = n+2 2 the number of monomials in a fresh ciphertext. We pick d = 1 because this case is best understood and allows for multiplicative homomorphicity. We set the parameters in a way which keeps q independent of b and allow for dependency on λ and µ only. (This is compatible with the definitional framework that we have set up.) We pick: q ≈ λ (2+µ) and α = 1/(λ µ log 2 (λ)

√ λ).

Under these choices, we now have to establish the conditions under which the LWE instance characterised by N , q and χ α,q is hard. Since a detailed treatment of algorithms for solving LWE is out of scope for this work, we here restrict ourselves to a simple distinguishing attack for which we follow [START_REF] Lindner | Better key sizes (and attacks) for LWE-based encryption[END_REF]. Denote by Λ the lattice spanned by our linearised polynomials and by Λ T its dual lattice scaled by q. For the distinguishing attack we need a vector of length 1/α in the dual lattice Λ T , i.e. we require a lattice reduction algorithm with root hermite factor δ satisfying:

1/α = δ m • det(Λ T )

1/α = δ m • q N/m δ = (1/α • q N/m ) 1/m .

We want to ensure that achieving this δ costs at least 2 λ operations. We set m = n • log q/ log δ [START_REF] Micciancio | Lattice-based cryptography[END_REF] and assume λ ≈ 1.8/ log δ -110 [START_REF] Lindner | Better key sizes (and attacks) for LWE-based encryption[END_REF] to be compatible with related work. This allows to estimate parameters for SPCN . To turn it into a public-key scheme, we may use a standard symmetric-toassymetric conversion. In particular, picking strategy (A) from Section 5, we require 2 N log 2 q encryptions of zero. Putting all this together, we arrive at the example choices of parameters given in Table 1 which was generated using the reference implementation from Section 10. ) and N = n+2 2 . The column log 2 sk expresses the logarithm of the bitsize of the secret key, the column log 2 enc the logarithm of the bitsie of a fresh ciphertext, the column log 2 pk the logarithm of the bitsize of the public key. For SPCN the last column is ignored.

From Table 1 it is easy to see that SPCN and its public-key variant only supports very limited levels of multiplicative homomorphicity. This is to be expected, as the public key has size O (N log q) 2 with q ≈ λ 2+µ , i.e. O (N µ) 2 .

Reference Implementation

We implemented our scheme using the Sage mathematics software [START_REF] Stein | SAGE Mathematics Software[END_REF]. 5 Although this implementation is not efficient, the code not only concretely demonstrates the correctness of the scheme, it also shows that if basic mathematical structures are available, it can be easily implemented.

Lemma 5 .

 5 Let I ⊂ P be an ideal with a degree-compatible term ordering ≤. Then any f ∈ P with deg(f ) = b has a unique representation f = f + r with f ∈ I and r ∈ P/I where deg( f ) ≤ b and deg(r) ≤ b.

Algorithm 3 :begin 2 B 3 G ← ∅; 4 query 12 gi = m -b; 13 return f + gi; 14 if 16 G ← G ∪ {gi}; 17 break; 18 call

 3234121314161718 GB adversary B from IM adversary A 1 receives (1 λ , P ); GB.Sample() to get f0, . . . , fm-1; 5 query GB.Sample() to get f ; 6 for m ∈ LM(G) do 7 for b ∈ P/I do 8 run A(1 λ , P ) as follows: 9 if A queries IM.Sample() then 10 answer A's ith query with fi; // we reuse fi between different runs of A. 11 if A queries IM.Challenge() then A calls IM.Finalize(c ) then 15 if c = 1 then // gi likely in I GB.Finalize( G);

  d,m for d, 1 ≤ d ≤ D for some D. Definition 8 (Macaulay matrix). For a set of m polynomials f 0 , . . . , f m-1 ∈ P , we define the Macaulay matrix M acaulay d,m

  be a set of polynomials in P . There exists a positive integer D for which Gaussian elimination on all M acaulay d,m matrices for d = 1, . . . , D computes a Gröbner basis of F .

  . A homomorphic symmetric encryption scheme is correct if for any polynomial p, any λ ∈ N, any (SK, PK) ∈ [Gen(1 λ )], any t = p(λ) messages m i ∈ MsgSp(PK), any circuit C ∈ FunSp(PK) of arity t, any t ciphertexts c i ∈ [Enc(m i , SK)], and any evaluated ciphertext c evl ∈ [Eval(c 0 , . . . , c t-1 , C, PK)], we have that Dec(c evl , SK) = C(m 0 , . . . , m t-1 ). Depending on the context, the correctness condition might also be imposed over freshly created ciphertexts.Compactness. A homomorphic encryption scheme is compact if there exists a fixed polynomial bound B(•) so that for any (SK, PK) ∈ [Gen(1 λ )], any circuit C ∈ FunSp(PK), any t messages m i ∈ MsgSp(PK), any c i ∈ [Enc(m i , SK)], and any c evl ∈ [Eval(c 0 , . . . , c t-1 , C, PK)], the size of c evl is at most B(λ + |C(m 0 , . . . , m t-1 )|) (independently of the size of C).

Fig. 3 .

 3 Fig. 3. The (noise-free) Symmetric Polly Cracker scheme SPC P,GBGen(•),d, ,b .

Efficiency.

  If d = 1 and q(λ) = poly(λ) we set n(λ) = Ω(λ) to rule out exhaustive search for the Gröbner basis {x 0 -b 0 , . . . , x n-1 -b n-1 } where b i ∈ F q . Message expansion is n b with b ≥ 1. That is, encrypting a single field element results in a ciphertext of length n+b b = O n b field elements. The complexity of both encryption and decryption for fresh ciphertexts are O n b ring operations. Decryption of ciphertexts with µ levels of multiplications require O n 2 µ b ring operations.

Definition 12 (

 12 m-IND-BCPA security). The m-IND-BCPA security of a (homomorphic) symmetrickey encryption scheme SE for a polynomial m is defined by requiring that the advantage of any PPT adversary A given by Adv ind-bcpa m,SE,A (λ) := 2 • Pr IND-BCPA A m,SE (λ) ⇒ True -1 is negligible as a function of the security parameter λ. Game IND-BCPA m,SE is shown in Figure 4. The difference with the usual IND-CPA security is that the adversary can query its encryption oracle at most m(λ) times.

Fig. 4 .

 4 Fig. 4. Game IND-BCPA m,SE . An adversary is legitimate if it calls oracle Left-Right exactly once on two message of equal lengths.

2 =

 2 8, deciding ideal membership with overwhelming probability is equivalent to computing a Gröbner basis by making at most |LM(G)| • s queries to the IM oracle where both |LM(G)| and s are poly(n). Note that the IM oracle constructed here has success probability 1. Each IM query costs at most n+b b O n 2b field operations. Therefore the overall cost of the second step is O |LM(G)| • s • n 2b . In fact, this last step is unnecessary, since it can be shown that the output of the Gröbner basis computation up to degree B is a Gröbner basis for I. In any case, the overall complexity is O n ωB for the first step and O |LM(G)| • s • n 2b for the second step with b ≤ B from which an overall complexity of O n ωB + |LM(G)| • s • n 2b follows.

Fig. 5 .

 5 Fig. 5. Game GBN P,GBGen(•),d, ,b,χ .

Fig. 6 .

 6 Fig. 6. Game IMN P,GBGen(•),d, ,b,χ . The adversary may call Sample multiple times.

FinalizeFig. 7 .

 7 Fig.7. Games WIMN G,χ,t . In each game, the adversary may call Sample with any monomials t ∈ S(I) ≤b multiple times and Challenge t once.

23 break; 24 r 25 G

 232425 ← r + β • t for a maximal C β ; // majority vote ← G ∪ {m + r}; 26 call GBN.Finalize(G ); Algorithm 6 runs in polynomial time. The outer loop terminates after at most |LM(G)| = n(λ) iterations. The two inner loops terminate after at most |S(I)| and q iterations, both of which are polynomial in λ by assumption.

Fig. 8 .

 8 Fig.8. Game LWE n,q,χ .

Lemma 12 (

 12 LWE hard =⇒ GBN hard for b = d, = n, and GBGen(•) = GBGen dense (•)).

  Finally, we consider known attacks to understand the difficulty of the GBN problem. Recall, that if b = d = 1 Lemma 11 states that we can solve the LWE problem if we can solve the GBN problem. Conversely, for any b ≥ d and d = 1 the best known attack against the GBN problem is to reduce it to the LWE problem similarly to the linearisation technique used for solving nonlinear systems of equations in the noise-free setting. Let N = n+b b

Fig. 9 .

 9 Fig. 9. The symmetric Polly Cracker with noise scheme, SPCN P,GBGen(•),d, ,b,χ .

Algorithm 8 : 2 GA→B ← ∅; 3 for m ∈ M ≤b do 4 m

 8234 Generating a re-encryption key (Re-encryptionKey)Input: GA -a Gröbner basis Input: f 0 , . . . , f s-1 -polynomials of degree b encrypting zero under a Gröbner basis GB Input: b -a bound on the degree of polynomials Input: y -sparsity parameter 1 begin ← m mod GA; 5 for 0 ≤ j < log 2 (q/2) do 6 s ← $ a sparse subset of {0, . . . , s -1} of size y;

7

 7

c j f 2 jc j f 2 j 2 c 2 c 2 c

 22222 Re-encryptionKey(f, G A→B ) = c•m∈T(f ) Re-encryptionKey(c • m, G A→B ) = c•m∈T(f ) •m + c • (m mod G A )   . Hence, Re-encryptionKey(f, G A→B ) mod G B = c•m∈T(f ) Re-encryptionKey(c • m, G A→B ) mod G B = c•m∈T(f ) •m + c • (m mod G A ) j e 2 j •m + c • (m mod G A ) j e 2 j •m   + c•m∈T(f ) c • (m mod G A ) j e 2 j •m   + 2e + m = 2e + m, where e = c•m∈T(f ) s(c) • t-1 j=0 2 c j e 2 j •m + 2e ∈ P/I B . Also, note that m + 2e = c•m∈T(f ) c • (m mod G A ) = f mod G A holdsbecause of the additive/multiplication-by-a-constant homomorphic features of the encryption scheme. All elements in G A→B are of degree at most b . Hence, the degree of the output of Algorithm 9 is at most b .

  The outer loop is repeated |LM(G)| and the inner loop |P/I| both of which are poly(λ). Algorithm B makes one additional query to Sample compared to A and hence needs m + 1 samples.

Algorithm 4: IM adversary B from GB adversary A 1 begin 2 B receives (1 λ , P ); 3 Query IM.Challenge() to get h; 4 Run A(1 λ , P ) as follows: 5 if A queries GB.Sample() then 6 query IM.Sample() to get f ; 7 return f ; 8 if A calls GB.Finalize(G ) then 9 if G is a red. Gröbner basis with the correct leading monomials then 10 r ← h mod G ; 11 call IM.Finalize 1 -(r = 0) ; 12 else 13 c ← $ {0, 1}; 14 call IM.Finalize(c );

  6: GBN adversary B from WIMN adversary A

	1 begin
	2	B receives (1 λ , P );
	3	G ← ∅;
	4	for m ∈ LM(G) do
	5	r ← 0;

6 for t ∈ S(I) ≤b do 7 for β ∈ Fq do 8 C β ← 0; 9 for i ∈ {1, . . . , λp(λ) 2 } do // amplification 10 run A(1 λ , P, t ) as follows: 11 if A queries WIMN.Sample(t) then 12 query GBN.Sample() to get f ; 13 e ← random polynomial ∈ Q but coefficient 0 for t; 14 answer A's query with f + e; 15 if A queries WIMN.Challenge t () then 16 a ← $ Fq;

17 e ← random polynomial ∈ Q but coefficient 0 for t ; 18 query GBN.Sample() to get f ; 19 return f + a • (m + β • t ) + e; 20 if A calls WIMN.Finalize(c ) then 21 if c = 1 then // β • t likely a correct guess 22 C β ← C β + 1;

Table 1 .

 1 λ µ n N log 2 α log 2 q log 2 sk log 2 enc log 2 pk 40 1 11 78 -7.48 11.27 Example parameter choices for b = 2, k = 2 log(220

		6.95	9.78	20.56
	40 2 15 136 -12.81 16.94	7.99	11.17	23.34
	40 3 18 190 -18.13 22.16	8.64	12.04	25.08
	40 4 21 253 -23.45 27.19	9.16	12.75	26.50
	40 5 23 300 -28.77 32.64	9.55	13.26	27.52
	80 1 18 190 -8.48 12.96	7.87	11.27	23.53
	80 2 18 190 -14.80 19.60	8.46	11.86	24.73
	80 3 22 276 -21.13 25.97	9.16	12.81	26.61
	80 4 25 351 -27.45 32.38	9.66	13.47	27.94
	80 5 29 465 -33.77 38.32	10.12	14.12	29.24
	128 1 26 378 -9.11 14.04	8.51	12.37	25.75
	128 2 25 351 -16.11 21.28	9.06	12.87	26.73
	128 3 25 351 -23.11 28.61	9.48	13.29	27.59
	128 4 29 465 -30.11 35.77	10.02	14.02	29.04
	128 5 33 595 -37.11 42.62	10.46	14.63	30.26

Here we are slightly abusing notation and using P both for the polynomial ring and its description.

Since the noise distribution χ only enters our construction via χ t , this has the side effect of removing all dependencies between the coefficients. In particular, we may as well assume that χ samples the coefficients of all monomials t independently.

Here P is a distribution which returns P = Fq[x0, . . . , xn-1] with q as in the LWE game. Algorithm GBGen(•) returns [x0 -s0, . . . , xn-1 -sn-1] for some si ∈ Fq, which is the only choice for d = 1.

http://xagawa.net/pdf/20100120_SCIS_PRE.pdf

See https://bitbucket.org/malb/research-snippets/src/tip/noisy-polly-cracker.py .

Acknowledgements

We would like to thank Carlos Cid for valuable feedback and discussions on this work. We would also like to thank Frederik Armknecht for helpful discussions on an earlier draft of this work. The work described in this paper has been supported by the Royal Society grant JP090728 and by the Commission of the European Communities through the ICT program under contract ICT-2007-216676 (ECRYPT-II).

Martin R. Albrecht, Jean-Charles Faugère, and Ludovic Perret are also supported by the French ANR under the Computer Algebra and Cryptography (CAC) project (ANR-09-JCJCJ-0064-01) and the EXACTA project (ANR-09-BLAN-0371-01).

Now if the sample returned from the Challenge oracle in IM to B is uniform in P ≤b , then the probability that c = c is 1/2. On the other hand, if the sample is an element of the ideal then adversary A is run in an environment which is identical to the m-IND-BCPA game. Hence in this case the probability that c = c is equal to the probability that A wins the m-IND-BCPA game. Switching from IM to IM gives a factor Algorithm 7 is correct. If the samples returned by the Challenge t oracle to B are uniform in P ≤b , then the probability that c = c is 1/2. On the other hand, if the sample is a noisy element of the ideal, then adversary A is run in an environment which is identical to the IND-CPA game. Note that since gcd(q, 2) = 1, multiplications by 2 at lines 9 and 19 do not affect the distribution of f (apart from doubling the noise, which is necessary to get the IND-CPA game environment). Hence in this case the probability that c = c is equal to the probability that A wins the IND-CPA game. The theorem follows.

The above theorem, Lemma 9 and the recent results in [START_REF] Rothblum | Homomorphic encryption: From private-key to public-key[END_REF] which establish the equivalence of symmetric and asymmetric homomorphic encryption schemes leads to the first provably secure public-key encryption scheme reducible to the hardness of computing Gröbner bases for random systems. This provides a positive answer to the challenges raised by Barkee et al. [START_REF] Barkee | Why you cannot even hope to use Gröbner bases in Public Key Cryptography: An open letter to a scientist who failed and a challenge to those who have not yet failed[END_REF] (and later also by Gentry [START_REF] Gentry | A fully homomorphic encryption scheme[END_REF]). We note here that the transformation -as briefly described in Section 5only uses the additive features of the scheme and does not require full homomorphicity.

Trading Degrees for Noise

The product of two polynomials of degree b is a polynomial of degree 2b, and hence the size of the ciphertext squares if two ciphertexts are multiplied together. In this section, we discuss how to reduce polynomials of degree b to polynomials of degree b by performing proxy re-encryption. Proxy re-encryption allows to transform a ciphertext intended for a party A to a ciphertext for a party c ← the coefficient in f of m, represented as an integer in (-q 2 , q 2 ]; Proof. Let f be an encryption of a message m under the key G A and G A→B be a re-encryption key generated using Algorithm 8. We want to show that Re-encryption(f, G A→B ) is an encryption of a message m under the key G B . Let then m be a monomial of f , and c be the coefficient of m in f , represented as an integer in (-q 2 , q 2 ]. To simplify the notation, we set t = log 2 ( q 2 ). By definition, we can write c • m = s(c) • t-1 j=0 c j • 2 j • m, the c j 's being the binary decomposition of the absolute value of c, and s(c) ∈ {-1, +1} the sign of c. It is clear that Re-encryption will transform each term c • m (c is a constant and m is a monomial) as follows:

For any 0 ≤ j < t, by definition we have: