Study Group: Polly Cracker, Revisited

Today along came Polly and it was cracking! In other words, our study group for this week was dedicated to Polly Cracker, Revisited by Albrecht, Farshim, Faugère, and Perret. The paper will be presented at Asiacrypt 2011 (LNCS 7073) later this year.

Polly Cracker schemes use ideals of multivariate polynomial rings and they are based on the presumed hardness of computing good (Gröbner) bases for these ideals. The first schemes were introduced in the early nineties (just when I went to University) and there has been a steady amount of work on them, though they never really gained the widespread acceptance that for instance factoring, discrete log, or recently lattice based cryptosystem acquired.

We started our study group with a review of the relevant mathematics. David gave us an excellent turbo tutorial on rings, ideals, monomial orderings and finally Gröbner bases. It was a very useful reminder of the basics and inevitably I had to think back of times long gone by, when, as part of a coursework, I had to prove the Pythagorean theorem using Gröbner bases (definitely one of the geometrically least insightful ways of going about proving this theorem).

After this refresher, Jake took over to discuss the Polly Cracker, Revisited paper. The first part of the paper (and our discussion) deals with noiseless version of Polly Cracker. This can be considered the more classical problem. Three different hardness assumptions can be considered, all based on an adversary with access to an oracle returning randomly sampled elements in the ideal: in the first version (GB), the adversary has to reconstruct a Gröbner basis; in the second version (IR) the adversary needs to compute the remainder (modulo the ideal) of a random challenge (in the ring); and in the third version (IM) the adversary just needs to decide whether some challenge element is in the ideal or not. Of course, in the paper all the relevant probability distributions are worked out properly. While it is quite obvious that the ability to compute Gröbner basis suffices to solve the other two problems, the other direction is less straightforward and in fact, Albrecht et al. only provide a conditional implication. They also show how to create a symmetric encryption scheme that satisfies a bounded version of IND-CPA security (here the adversary has only a limited number of calls to its left-or-right and encryption oracles).

The interesting stuff appears afterwards, when the authors introduce errors or perturbations in analogy of the LWE and approximate GCD problems. Indeed, they even show that their approach is a proper generalization of these two settings. Unsurprisingly, this allows the creation of IND-CPA secure scheme. More exciting is the fact that it also shows that Regev's scheme based on LWE allows for a fixed number of multiplications.

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.