## Chen & Nguyen’s algorithm and Arora & Ge’s algorithm

In Faster Algorithms for Approximate Common Divisors: Breaking Fully-Homomorphic-Encryption Challenges over the Integers Yuanmi Chen and Phong Q. Nguyen (preprint here) propose a new algorithm for solving the approximate GCD problem. It drops the complexity from $2^{2\rho}$ to $2^{3/2\rho}$ in the general case and from $2^{\rho}$ to $2^{\rho/2}$ in the partial case (one multiple of $p$ is given noise-free) which is a pretty big deal.

The algorithm is based on two key ideas (explained using the partial approximate GCD problem):

1. Noisy solving reduced to noise-free solving

Similar to Arora & Ge’s algorithm for solving LWE Chen and Nguyen reduce the approximate solving problem to a noise-free solving problem. In fact, the strategy is exactly the same (cf. also this post). Given noisy ideal elements $f_i = \sum h_i g_i + r_i$ where $g_i$ are generators of the ideal, $h_i$ are ring elements and $r_i$ are small noise terms, then $F_i = f_i \cdot \prod (f_i + j)(f_i - j)$

will be elements of the ideal $I$ spanned by $g_i$ if $j$ is big enough (depending on the exact setup we may drop the $-j$ part). In the approximate GCD case $g_0$ is simply a small odd integer (often denoted $p$). Additionally, if we are given some sufficient “description” of some sufficiently big ideal $\langle G_1,\dots,G_s \rangle = J \supset I$ (i.e., all elements of $I$ are in $J$ but not vice versa and $J$ is considerably bigger than $I$) then we can compute $F_i = f_i \cdot \prod (f_i + j)(f_i - j) \mod J$

which keeps the size of $F_i$ small-ish. This is the role of $x_0$, the noise free multiple of $p$ in the partial approximate GCD problem. Now, one simply solves the noise free system $F_1,\dots,F_m$. In the PAGCD case this means to compute a single GCD, in the multivariate polynomial case (including LWE) this means to compute a Gröbner basis (or linearise, which is the same thing for the cases we are concerned with). Hence, so far Arora&Ge and Chen&Nguyen are really the same thing (it should be mentioned that this ideal due to Nguyen was already mentioned in this paper) applied to different rings.

However, this is not really why the Chen & Nguyen algorithm is efficient (although this already provides a speed-up by a factor of 5).

2. Efficient multiplication

The key idea to drop the exponent from $2^{\rho}$ to $2^{\rho/2}$ is as follows. Instead of computing with integers we compute univariate polynomials mod $x_0$, i.e. one defines $f_j(x) = \prod_{j=0}^{j-1} (x_1 - (x + i)) \in \mathbb{F}_{x_0}[x]$

and notices that for $\rho' = \lfloor \rho/2 \rfloor$: $\prod_{i=0}^{2^\rho-1} (x_1 - i) = \prod_{k=0}^{2^{\rho - \rho'} -1} f_{2^{\rho'}}(2^{\rho'}k)$

i.e., we can reduce $2^\rho -1$ multiplications to $2^{\rho - \rho'} - 1$ multiplications and $2^{\rho - \rho'} - 1$  polynomial evaluations. It turns out, this can be done in $\mathcal{O}(2^{\rho'})$. For the details read the paper.

But to get back to my previous point: It turns out the Arora&Ge perspective on noisy system solving is also useful for approximate GCDs. Which provides further evidence that it is useful to generalise LWE and AGCD to ideal theoretic problems in multivariate polynomial rings.

## Yet another Polly Cracker talk

… but this time

• it has less formal definitions.
• a brief discussion on related work.

Speaking of related work: Efficient Fully Homomorphic Encryption from (Standard) LWE by Zvika Brakerski and Vinod Vaikuntanathan is a good read. In summary, it has two main contributions:

1. a somewhat homomorphic scheme based on LWE which turns out to be the same (as far as I can tell) as ours and
2. a new dimension reduction trick which allows to turn it into a fully homomorphic scheme.

What is kind of curious about this work is its explicit non-algebraic perspective. While we talk about LWE from a multivariate polynomial ideal perspective the authors of 2011/344 explicitly state that their scheme is not.  I am not sure we’d have seen the dimension reduction trick with our perspective, though.

## Polly Cracker, Revisited

I’ve been mentioning this work a few times; well,  finally a pre-print is ready (by myself, Pooya Farshim, Jean-Charles Faugère and Ludovic Perret).

In this paper we initiate the formal treatment of cryptographic constructions – commonly known as “Polly Cracker” – based on the hardness of computing remainders modulo an ideal over multivariate polynomial rings. This work is motivated by the observation that the Ideal Remainder (IR) problem is one of the most natural candidates to build homomorphic encryption schemes. To this end, we start by formalising and studying the relation between the ideal remainder problem and the problem of computing a Gröbner basis.

We show both positive and negative results.

On the negative side, we define a symmetric Polly Cracker encryption scheme and prove that this scheme only achieves bounded CPA security under the hardness of the IR problem. Furthermore, using results from computational commutative algebra we show that a large class of algebraic transformations cannot convert this scheme to a fully secure Polly Cracker-type scheme.

On the positive side, we formalise noisy variants of the ideal membership, ideal remainder, and Gröbner basis problems. These problems can be seen as natural generalisations of the LWE problem and the approximate GCD problem over polynomial rings. After formalising and justifying the hardness of the noisy assumptions we show – following the recent progress on homomorphic encryption – that noisy encoding of messages results in a fully IND-CPA secure somewhat homomorphic encryption scheme. Together with a standard symmetric-to-asymmetric transformation for additively homomorphic schemes, we provide a positive answer to the long standing open problem proposed by Barkee et al. (and later also by Gentry) of constructing a secure Polly Cracker-type cryptosystem reducible to the hardness of solving a random system of equations. Indeed, our results go beyond that by also providing a new family of somewhat homomorphic encryption schemes based on new, but natural, hard problems.

Our results also imply that Regev’s LWE-based public-key encryption scheme is (somewhat) multiplicatively homomorphic for appropriate choices of parameters. Finally, we estimate the parameters which define our cryptosystem and give a proof-of-concept implementation.

Sage source code included, have fun.

I will give an online talk on Wednesday 12pm New York time (EDT) as part of the “Symbolic Computations and Post-Quantum Cryptography” seminar series. My talk is titled “Polly Cracker Revisited” and I’ll present classical and noisy problems in multivariate polynomial rings and how they relate to homomorphic encryption. I will post my slides here afterwards.

Edit: Slides with typos and all that.

## Algorithms for LWE and the Approximate GCD Problem over the Integers

Let $n$ be the number of variables in some polynomial ring $\mathbb{R}[x_1,\dots,x_n]$ (with $\mathbb{R}$ a ring) and let $d$ be the degree of a bunch of polynomials $F = [f_1,\dots,f_m]$ in $\mathbb{R}$, i.e., $\deg(f_i) = d$. Of course, we can “solve” $F$ by computing a Gröbner basis on $F$. Furthermore, it is well-known that if $n=1$ computing a GB is equivalent to computing the GCD of $F$ and that if $d=1$ 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 $\mathbb{R}[x]$.

In our work (you know, the one which isn’t done yet), we define GBN over $\mathbb{F}_q$ to keep things simple but the notion can easily be extended to for example $\mathbb{Z}$. Hence, one could say GBN over $\mathbb{Z}$ is a generalisation of GCDs over $\mathbb{Z}[x]$ and in particular over $\mathbb{Z}$ (cf. this paper which constructs a homomorphic encryption scheme based on the approximate GCD problem over the integers) which is just $\mathbb{Z}[x]$ 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).

## Cryptanalysis of “Fully Homomorphic Encryption over the Binary Polynomials”

Turns out, I’m not he only one who was inspired to adapt the Fully Homomorphic Encryption over the Integers scheme by van Dijk, Gentry, Halevi and Vaikuntanathan to polynomials. ﻿﻿﻿ Gu Chunsheng posted a pre-print on the IACR eprint server this week which essentially instantiates the integer scheme over univariate polynomials over $\mathbb{F}_2$.  Below is my implementation (in Sage) of his somewhat homomorphic scheme:

class BinPolySHE:
def __init__(self, n):
n = n
tau = n # choice here
P = PolynomialRing(GF(2),'x')

x = P.gen()

s = P.random_element(degree=2*n+1)
while not (s.is_irreducible() and s.degree()==2*n+1):
s = P.random_element(degree=2*n+1)

b = []

a0 = P.random_element(2*n+1)
if a0.degree() < 2*n+1:
a0 += x**(2*n+1)
e0 = P.random_element(degree=n-1)
b0 = a0*s + x*e0 # deg: 4*n+2

b.append(b0)

for i in range(1,tau):
ai = P.random_element(degree=n) # choice here
ei = P.random_element(degree=n-1)
bi = ai*s + x*ei # deg 3*n+1
bi = bi % b0
b.append(bi)

self.n = n
self.pk = b
self.sk = s
self.P = P

def encrypt(self, m):
T = []

for i in range(1, len(self.pk)):
if random() <= 0.5: # choice here
T.append(i)

c = self.P(m%2)

x = self.P.gen()

for i in T:
e = self.P.random_element(degree=self.n-1)
c += self.pk[i] + x*e

return c % self.pk

def decrypt(self, c):
x = self.P.gen()
return (c % self.sk) % x


Regular readers of this blog might have noticed that the scheme looks like a bit like a univariate specialisation of this PollyCracker scheme. Indeed, just like this first PollyCracker scheme, Gu’s scheme is badly broken. Below, the source code of my attack:

    def attack(self, c):

A = Matrix(GF(2),len(self.pk),4*self.n+2)

x = self.P.gen()

for i,b in enumerate(self.pk):
for j in b.exponents():
A[i,A.ncols()-j-1] = 1
E = A.echelon_form(reduced=False)

pk2 = []
for i,r in enumerate(A.rows()):
b = 0
for j in range(A.ncols()):
b += E[i,A.ncols()-j-1]*x**j
pk2.append(b)

for b in pk2:
if c[b.degree()]:
c -= b
return c % x


The attack proceeds pretty much as discussed here: we can compute a triangular basis for the span of the public key and use that to perform all eliminations. Since the noise does not grow with each addition and does not affect the constant coefficient (which holds the message), we can essentially ignore it.

## Polly Cracker Revisited – Slides

I just gave a talk in the ISG seminar at Royal Holloway, University of London about this Polly Cracker business I’ve been thinking about lately. I’ve also decided to publish the slides. However, I’d like to stress that everything in there is preliminary, i.e. this is yet another of those presentations presenting work in progress (which I personally think is a good thing to do). Anyway, here’s the abstract:

“Since Gentry’s seminal work on homomorphic encryption, this area has received considerable attention from the cryptographic community. Perhaps one of the most natural homomorphic schemes conceivable is Polly Cracker which is naturally homomorphic. However, almost all Polly Cracker inspired schemes that have been proposed so far have been badly broken. In fact, it was conjectured about 15 years ago in “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.”that it was impossible to construct a secure Polly Cracker-style scheme.

In this work we initiate a formal treatment of cryptosystems based on the hardness of Gröbner basis computations for random systems of equations, discuss their limitations, why standard techniques from homomorphic encryption research fail in this area, and propose a Polly Cracker variant based on polynomial system solving with noise which is a first step towards a provably secure Polly Cracker public-key scheme.”