A Fully Homomorphic Cryptosystem with Approximate Perfect Secrecy

At CT-RSA 2013 a paper titled “A Fully Homomorphic Cryptosystem with Approximate Perfect Secrecy” by Michal Hojsík and Veronika Půlpánová was presented. Here is the abstract:

We propose a new fully homomorphic cryptosystem called Symmetric Polly Cracker (SymPC) and we prove its security in the information theoretical settings. Namely, we prove that SymPC approaches perfect secrecy in bounded CPA model as its security parameter grows (which we call approximate perfect secrecy). In our construction, we use a Gröbner basis to generate a polynomial factor ring of ciphertexts and use the underlying field as the plaintext space. The Gröbner basis equips the ciphertext factor ring with a multiplicative structure that is easily algorithmized, thus providing an environment for a fully homomorphic cryptosystem.

The proposal seems to have succeeded where we could not: a fully homomorphic encryption scheme that also is information theoretic secure. Indeed, the authors reference our work and point out that they are taking a different approach (from ours) which allows them to succeed in realising these two goals.

To understand the claim made, here’s a quick rehash of our Symmetric Polly Cracker (SPC) for d=1 and b=2.

The secret key is a Gröbner basis . To encrypt we pick  and publish where is the message we want to encrypt. Decryption is easy if we know because it is equivalent to computing normal forms modulo . Indeed, it can be shown that the problem of finding under a chosen plaintext attack is as hard as finding which we assume is a hard problem. This scheme is homomorphic: we can do additions and multiplications of ciphertexts which decrypt to the sums and products of plaintexts. However, the scheme is not fully homomorphic as the ciphertext size increases with each multiplication. Also, the problem of computing the Gröbner basis becomes easy once we published many encryptions, so the scheme only supports a limited number of encryptions. So far, so general.

Now, let’s take a look at the new approach. Despite the claim that “A Fully Homomorphic Cryptosystem with Approximate Perfect Secrecy” is a new approach, it is – as far as I can see – a tweak of this general construction (essentially going back to Koblitz and Fellows). The two tweaks are:

  1. is augmented with the so-called “field polynomials” as they evaluate to zero on every element of (Note: the actual construction is slightly different, which I ignore here for clarity of presentation).
  2. Instead of limiting the number of encryptions to some such that the Gröbner basis problem is assumed to be hard, the number of encryptions is limited to some value .

The first tweak means that after a certain number of multiplications ciphertexts do not grow in size any more. That is, the largest monomial (under some degree compatible ordering) is . This allows to call the scheme “compact” and hence allows to declare it a fully homomorphic scheme under the technical definition of compactness. Yet, this means that ciphertexts are exponentially big in (e.g., if , we are talking about ciphertexts with bits). I am not convinced these should be called “compact”.

The second tweak implies that a computationally unbound attacker’s chance of breaking the scheme approaches zero as approaches infinity. There simply aren’t enough equations to recover . Hence, at the cost of making the scheme exceptionally short-lived it is information theoretic secure (asymptotically).

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.