Ring-LWE and the GB(N) Problem

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.

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 to in the general case and from to in the partial case (one multiple of 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):

Yet another Polly Cracker talk

… but this time

• it has less formal definitions.
• I also added a section talking about trading noise for degree and
• 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.

Webinar about Polly Cracker

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 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).

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 .  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[0]

    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.”

Cryptanalysis of my Somewhat Homomorphic PollyCracker Scheme

About 5 months ago I wrote about a homomorphic scheme based on integers and an adaptation of this schemes to use multivariate polynomials. At the very end I wrote: 

“Of course, I assume that my adaptation above can still be broken somehow since that’s what tends to happen with multivariate crypto schemes. Also, I’m really really not an expert on public-key cryptography. Hey, this is a blog post, not a research paper … so break it in the comments “

Well, with some delay, here is how to break it. Recall, that the secret is some Gröbner basis in (assume for simplicity) and that a ciphertext is constructed as

where has constant coefficient 0 and are random polynomials. Now, let with to ensure correct decryption (i.e. no interference of the noise with the normal form computation).

To break the scheme simply request encryptions of zero and compute the row echelon form on the linearisation of those polynomials of degree without elimination above the pivot (i.e. don’t compute the reduced row echelon form). Throw away any element of degree and call the resulting list . This list allows to decrypt any ciphertext by reducing modulo .

Below, the attack in Sage:

class PolynomialHomomorphic:
    def __init__(self, l):
        self.l = l
        K = GF(2) # pick some field
        # we choose a ring with l unknowns, which
        # should make any GB computation at least
        # as hard as 2^l if we pick the ideal sufficiently
        # random.
        R = PolynomialRing(K, l, 'x', order='degrevlex')
        self.K = K
        self.R = R
        # our small ideal, defines the message space.
        self.b = Ideal([x for x in R.gens()])

        # these parameters are pretty arbitrary from a
        # security perspective!
        self.N = 1
        self.P = 2
        self.Q = 1
        self.key_gen()

    def key_gen(self):
        b,l = self.b, self.l
        K, R = self.K, self.R
        # we pick a random ideal with l element of degree P
        p = [R.gen(i)**self.P + R.random_element(degree=self.P-1)
              for i in range(l)]
        self.p = Ideal(p)

    def encrypt(self, m):
        # we pick some m' which encodes the
        # same plaintext but is bigger
        m = self.R(m)
        mprime = self.R.random_element(degree=self.N)
        mprime -= mprime.constant_coefficient()
        mprime += m.constant_coefficient()

       # adding a random ideal element
        for f in self.p.gens():
            mprime += self.R.random_element(degree=self.Q)*f
        return mprime

    def decrypt(self, c):
        # decryption is just as in the integer case.
        return c.reduce(self.p).reduce(self.b)

def break_cpa(pc, challenge):
    ciphertexts = [pc.encrypt(0) for _ in xrange(2*pc.l**(pc.Q+pc.P))]
    F = Sequence(ciphertexts)
    A,v = F.coefficient_matrix(sparse=False)
    E = A.echelon_form(full=False)
    s = dict([(f.lm(),f) for f in (E*v).list() if f.degree() >= pc.P])

    while True:
        print challenge
        if challenge.lm() in s:
            challenge = challenge - s[challenge.lm()]
        else:
            if challenge.degree() > pc.P:
                raise ValueError("Ah, snap! It didn't work.")
            else:
                return challenge.constant_coefficient()

This works because the noise is constructed in such a way as to never interfere with elimination: it does not affect any leading monomial of the ideal ever. Thus, we don’t need to consider it during the elimination and simply ignore the lower terms once we are done.

Note that this attack does not work against the integer homomorphic scheme by van Dijk et al. because there additions are not free: When we perform elimination of the higher order bits in the integer scheme also the noise accumulates; eventually it surpasses the size of the prime leaving us with no information. Put differently, we can attack schemes that are inspired by the integer-based scheme if additions are free. Thus, while it might seem tempting to replace integers by, say, univariate polynomials which are often considered essentially computationally equivalent to integers and which would provide free additions  it would break the security of the scheme.

Somewhat Homomorphic Encryption

Today I read the paper “Computing Arbitrary Functions of Encrypted Data” by Craig Gentry in which he explains the basic ideas behind his work on fully homomorphic encryption. If you don’t know what homomorphic encryption is: it means that one can evaluate a function on ciphertexts which has the same result as evaluating that function on the plaintexts. Thus, one can compute with data without getting to see it. The canonical example Gentry uses in his papers is a search engine that searches through sensitive data without seeing the actual content. It is similar to secure multi-party computation except that it is not interactive at all, i.e. you send your query and get the result back without any interaction in between. In the above mentioned paper Gentry gives a simplified version of a recent integer based fully homomorphic scheme. This simplified version is symmetric and only somewhat homomorphic (more on this below). Since the basic idea of the scheme is so simple, it is quickly implemented. The code below is actually some slight generalisation such that b isn’t always forced to be two.