Let be the number of variables in some polynomial ring
(with
a ring) and let
be the degree of a bunch of polynomials
in
, i.e.,
. Of course, we can “solve”
by computing a Gröbner basis on
. Furthermore, it is well-known that if
computing a GB is equivalent to computing the GCD of
and that if
computing a GB is equivalent to Gaussian elimination, i.e., finding a triangular basis for a module. In a nutshell, Gröbner bases generalise GCDs and Gaussian elimination. So far, so classical.
It is no secret that I spent some time looking into a problem which we call Gröbner Bases with Noise (GBN), which again can be seen — with the appropriate choice of parameters — as a generalisation of the LWE problem (cf. these slides for some details. Sorry, the paper is still not done). Similarly, we may consider GBN as a generalisation of an approximate GCD problem over .
In our work (you know, the one which isn’t done yet), we define GBN over to keep things simple but the notion can easily be extended to for example
. Hence, one could say GBN over
is a generalisation of GCDs over
and in particular over
(cf. this paper which constructs a homomorphic encryption scheme based on the approximate GCD problem over the integers) which is just
restricted to constant polynomials. So, we have a connection between GBN, LWE and the approximate GCD problem.
Now, as my tag cloud gives away, I like linear algebra and have the tendency to think about problems in terms of linear algebra and triangular bases. Hence, the above connection made me think about the applicability of algorithms for solving LWE to the approximate GCD problem over the integers. It turns out, they are applicable (kinda).
BKW: The BKW algorithm was originally devised for the LPN problem and is essentially a strategy for avoiding additions since those quickly increase the noise. Instead of performing one addition per column, the algorithm gets enough samples such that it is reasonable to expect enough collisions in a number of columns. Perhaps, a small example is helpful to understand how the algorithm works. Let be a matrix with
columns over
, say:
1 0 1 0 1 | x x x x x x x ... 1 1 1 1 0 0 | x x x x x x x ... 1 1 0 1 0 1 | x x x x x x x ... 1 0 0 1 0 1 | x x x x x x x ... 0 0 0 0 0 1 | x x x x x x x ... 1
In the picture above the line is roughly at , x denotes an arbitrary value and the last column is noisy. If we get about
samples then we expect roughly
samples for each value in the first
columns. For each value, we pick one row and add it to all other rows. In the example above, we’d add the first row to the third etc. Hence, we eliminate
columns using only one addition. We repeat this for the next chunk of
columns until we arrive in the last column. We do this a couple of times and do a majority vote on the result. We expect this vote to be more successful than after straight Gaussian elimination because we performed less additions and hence increased the noise to a lesser extend. The idea is pretty much the same actually as in the M4RM/M4RI algorithms.
Now, to apply this approach to the approximate GCD problem over the integers, we think about integers in their binary representation or more generally in their p-adic expansion. Every integer can be written as for
a number and
. If
is the size of the integers we are considering, we may pick
. We now sample integers with the same approximate GCD, i.e. these integers are of size
and of the form
where
is small and
is the GCD we are looking for. Again, we put these integers in buckets according to the first
bits or the coefficient of
where
is the highest degree of
appearing in all samples. Just as in BKW we pick one representative for each class and subtract it from all other elements, effectively knocking down one degree (or clearing the first
bits). We repeat the process until we observe a sudden drop in size. This has to happen if the noise
is small enough compared to
, since at some point we will compute
which should be small. Hence, we recover elements which are close to
. Again, we expect those elements to be closer to
than by straight “Gaussian elimination” since we eliminated more than one bit per addition.
However and perhaps as expected, this algorithm does not work for the parameters suggested in the integer homomorphic paper. In fact, I’m not even sure it is any good … moving on.
Arora&Ge: Quite recently a new algorithm for solving LWE was proposed by Arora and Ge. The key idea here is that if with
small, then
will vanish on the secret if
and
is big enough (so
depends on the size of the noise, see the paper for details). For example, if we expect
, then one of the factors of
will vanish on
and hence
will vanish on
too. Hence, solving the noise-free system
of high degree will reveal the solution for the low degree noisy system
.
Similarly, if the approximate GCD of is
for
, then
is divisible by
if
is large enough. Hence, the (noise-free) GCD of
is also divisible by
. Note however that we don’t immediately recover
because the construction of the
introduces additional (but small) common factors. As for BKW this approach does not solve the approximate GCD problem for the parameters suggested in the integer homomorphic paper (the algorithm is a bit stupid for GCD problems: we could just guess the noise if it was that small).
So, what to make of all this? As far as I can see, these algorithms do not improve the state of the art of solving the approximate GCD problem. However, they do highlight a connection between LWE and the approximate GCD problem. Just as in the noise-free setting there is a (somewhat) close connection between problems over and
and more generally over
.
2 thoughts on “Algorithms for LWE and the Approximate GCD Problem over the Integers”