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.