Over at the Bristol Cryptography Blog Martijn Stam writes about our “Polly Cracker, Revisted” paper:

We did not discuss the paper in great detail, but Jake did mention one interesting avenue for continued research. Given that this new approach allows one to cast both LWE and approximate GCD in the same framework, can one also capture ring-LWE. If so, this might enable a better comparison of the various fully homomorphic encryption (FHE) schemes out there. The hope expressed by Jake was that this might allow a reduction to standard LWE (for the current batch of ring-LWE schemes), which would boost our confidence in those schemes.

This motivated me to express the Ring-LWE problem in a language of Gröbner bases, here’s what I could come up with so far.

But let’s recall the computational Ring-LWE problem first: Given a prime and an ideal where is a power of two and , we consider the quotient ring . We pick a random element which is our secret. We sample tuples where are random and are sampled according to some noise distribution. The computational Ring-LWE problem is to compute given .

Assume for all , so that we can discuss the algebraic structure directly. Clearly, all are in the ideal spanned by in . Furthermore, there is a direct correspondence between ideals in the quotient ring and in . Hence, to recover the Gröbner basis for the ideal spanned by , we simply compute the Gröbner basis of , easy right? Except that the Gröbner basis will be … wait for it … 1 with very high probability. This might reduce the search space slightly (since it tells us that and have no common factors over ) and is correct (since one is the smallest representative of the ideal spanned by in ) this is not terribly useful. But we did ignore so far.

Namely, the problem actually is to compute or . Now, in order to compute in – which is defined if – we may run an extended GCD algorithm which returns for inputs such that . Hence, for our inputs it will compute and thus .

In the language of Gröbner bases the extended GCD equivalent is often called “lifting”: Given an ideal and some , find such that . The problem is easy given a Gröbner basis (in our case ), since every element can be written as where . In general, it might be hard because the *a priori* bound on the degree of the output may be large. In any case, instead of solving a(n approximate) GCD (or GB(N)), we are now solving an extended GCD (or lifting with GB(N)), i.e., we keep track of our computation. Well, here’s an example in Sage:

sage: n = 2^3 sage: q = 17 sage: R. = GF(q)[] sage: Q. = R.quotient(Xbar^n + 1) sage: s = Q.random_element() sage: s 8*X^7 + 4*X^6 + 11*X^5 + 6*X^4 + 15*X^3 + 12*X^2 + 14*X + 12 sage: a = Q.random_element() sage: P. = PolynomialRing(GF(q),1) sage: A = sage_eval(str(a),{'X':x}) sage: S = sage_eval(str(s),{'X':x}) sage: Ainv = P(1).lift( (A,x^n + 1) )[0] sage: Ainv*(A*S) % (x^n + 1) 8*x^7 + 4*x^6 - 6*x^5 + 6*x^4 - 2*x^3 - 5*x^2 - 3*x - 5

Alternatively, we may “lift” with respect to directly. Well, I don’t know if any of the above is actually useful, as I said that’s how far I got after reading Martijn’s blog post.