Polly Cracker, revisited

We formally treat cryptographic constructions based on the hardness of deciding ideal membership in multivariate polynomial rings. Of particular interest to us is a class of schemes known as "Polly Cracker." We start by formalising and studying the relation between the ideal membership problem and the problem of computing a Grobner 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 $$\mathsf {CPA}$$CPA security under the hardness of the ideal membership problem. Furthermore, we show that a large class of algebraic transformations cannot convert this scheme to a fully secure Polly Cracker-style scheme. On the positive side, we formalise noisy variants of the ideal-theoretic problems. These problems can be seen as natural generalisations of the learning with errors ($$\mathsf {LWE}$$LWE) and the approximate GCD problems over polynomial rings. After formalising and justifying the hardness of the noisy assumptions, we show that noisy encoding of messages results in a fully $$\mathsf {IND}{\text {-}}\mathsf {CPA}$$IND-CPA-secure and 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 of constructing a secure Polly Cracker-style cryptosystem reducible to the hardness of solving a random system of equations. Indeed, our results go beyond this and also provide a new family of somewhat homomorphic encryption schemes based on generalised hard problems. Our results also imply that Regev's $$\mathsf {LWE}$$LWE-based public-key encryption scheme is (somewhat) multiplicatively homomorphic for appropriate choices of parameters.