Polly Cracker, Revisited

Abstract : We initiate the formal treatment of cryptographic constructions (“Polly Cracker”) based on the hardness of computing remainders modulo an ideal over multivariate polynomial rings. We start by formalising 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. 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 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. We then show that noisy encoding of messages results in a fully IND-CPA-secure somewhat homomorphic encryption scheme. Our results provide 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.
Type de document :
Communication dans un congrès
ASIACRYPT 2011 - 17th International Conference on the Theory and Application of Cryptology and Information Security, Dec 2011, Seoul, South Korea. Springer, 7073, pp.179-196, Lecture Notes in Computer Science. 〈10.1007/978-3-642-25385-0_10〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01113718
Contributeur : Ludovic Perret <>
Soumis le : vendredi 6 février 2015 - 10:46:35
Dernière modification le : vendredi 31 août 2018 - 09:25:54

Lien texte intégral

Identifiants

Collections

Citation

Martin Albrecht, Jean-Charles Faugère, Pooya Farshim, Ludovic Perret. Polly Cracker, Revisited. ASIACRYPT 2011 - 17th International Conference on the Theory and Application of Cryptology and Information Security, Dec 2011, Seoul, South Korea. Springer, 7073, pp.179-196, Lecture Notes in Computer Science. 〈10.1007/978-3-642-25385-0_10〉. 〈hal-01113718〉

Partager

Métriques

Consultations de la notice

192