Algorithms for LWE and the Approximate GCD Problem over the Integers

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 .