Polly Cracker, Revisited

Date Added: Jun 2011
Format: PDF

In this paper, the authors 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 paper 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, they start by formalising and studying the relation between the ideal remainder problem and the problem of computing a Grobner basis. They show both positive and negative results. On the negative side, they define a symmetric Polly Cracker encryption scheme and prove that this scheme only achieves bounded CPA security under the hardness of the IR problem.