Polly Cracker, revisited. / Albrecht, Martin; Faugere, Jean-Charles; Farshim, Pooya; Herold, Gottfried; Perret, Ludovic.

In: Designs, Codes and Cryptography, Vol. 79, No. 2, 05.2016, p. 261-302.

Research output: Contribution to journalArticlepeer-review

Published

Standard

Polly Cracker, revisited. / Albrecht, Martin; Faugere, Jean-Charles; Farshim, Pooya; Herold, Gottfried; Perret, Ludovic.

In: Designs, Codes and Cryptography, Vol. 79, No. 2, 05.2016, p. 261-302.

Research output: Contribution to journalArticlepeer-review

Harvard

Albrecht, M, Faugere, J-C, Farshim, P, Herold, G & Perret, L 2016, 'Polly Cracker, revisited', Designs, Codes and Cryptography, vol. 79, no. 2, pp. 261-302. https://doi.org/10.1007/s10623-015-0048-8

APA

Albrecht, M., Faugere, J-C., Farshim, P., Herold, G., & Perret, L. (2016). Polly Cracker, revisited. Designs, Codes and Cryptography, 79(2), 261-302. https://doi.org/10.1007/s10623-015-0048-8

Vancouver

Albrecht M, Faugere J-C, Farshim P, Herold G, Perret L. Polly Cracker, revisited. Designs, Codes and Cryptography. 2016 May;79(2):261-302. https://doi.org/10.1007/s10623-015-0048-8

Author

Albrecht, Martin ; Faugere, Jean-Charles ; Farshim, Pooya ; Herold, Gottfried ; Perret, Ludovic. / Polly Cracker, revisited. In: Designs, Codes and Cryptography. 2016 ; Vol. 79, No. 2. pp. 261-302.

BibTeX

@article{15b958cd7e8248f484ae97071334a539,
title = "Polly Cracker, revisited",
abstract = "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 Gr{\"o}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 CPACPA 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 (LWELWE) 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-CPAIND-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{\textquoteright}s LWELWE-based public-key encryption scheme is (somewhat) multiplicatively homomorphic for appropriate choices of parameters.",
author = "Martin Albrecht and Jean-Charles Faugere and Pooya Farshim and Gottfried Herold and Ludovic Perret",
year = "2016",
month = may,
doi = "10.1007/s10623-015-0048-8",
language = "English",
volume = "79",
pages = "261--302",
journal = "Designs, Codes and Cryptography",
issn = "0925-1022",
publisher = "Springer Netherlands",
number = "2",

}

RIS

TY - JOUR

T1 - Polly Cracker, revisited

AU - Albrecht, Martin

AU - Faugere, Jean-Charles

AU - Farshim, Pooya

AU - Herold, Gottfried

AU - Perret, Ludovic

PY - 2016/5

Y1 - 2016/5

N2 - 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 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 CPACPA 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 (LWELWE) 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-CPAIND-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 LWELWE-based public-key encryption scheme is (somewhat) multiplicatively homomorphic for appropriate choices of parameters.

AB - 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 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 CPACPA 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 (LWELWE) 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-CPAIND-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 LWELWE-based public-key encryption scheme is (somewhat) multiplicatively homomorphic for appropriate choices of parameters.

UR - https://eprint.iacr.org/2011/289

U2 - 10.1007/s10623-015-0048-8

DO - 10.1007/s10623-015-0048-8

M3 - Article

VL - 79

SP - 261

EP - 302

JO - Designs, Codes and Cryptography

JF - Designs, Codes and Cryptography

SN - 0925-1022

IS - 2

ER -