Paper 2011/289

Polly Cracker, Revisited

Martin R. Albrecht, Jean-Charles Faugère, Pooya Farshim, Gottfried Herold, and Ludovic Perret

Abstract

We initiate the formal treatment of cryptographic constructions based on the hardness of computing remainders modulo an ideal 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 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 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 (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 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 LWE-based public-key encryption scheme is (somewhat) multiplicatively homomorphic for appropriate choices of parameters.

Note: This work also incorporates corrections that appeared at PKC 2012.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. short version appeared at ASIACRYPT 2011, corrections appeared at PKC 2012
Keywords
Public-key encryptionProvable security
Contact author(s)
malb @ lip6 fr
History
2012-11-19: last of 2 revisions
2011-06-03: received
See all versions
Short URL
https://ia.cr/2011/289
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2011/289,
      author = {Martin R.  Albrecht and Jean-Charles Faugère and Pooya Farshim and Gottfried Herold and Ludovic Perret},
      title = {Polly Cracker, Revisited},
      howpublished = {Cryptology {ePrint} Archive, Paper 2011/289},
      year = {2011},
      url = {https://eprint.iacr.org/2011/289}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.