Home | Quick Search | Advanced Search | Bibliography submission | Bibliography submission using bibtex | Bibliography submission using bibtex file | Links | Help | Internal


TitlePolly cracker, revisited, revisited.
Author(s) Gottfried Herold
TypeBook, Chapter in Book, Conference Proceeding
AbstractIn this paper, we consider the Polly Cracker with Noise (PCN) cryptosystem by Albrecht, Farshim, Faugère, and Perret (Asiacrypt 2011), which is a public-key cryptosystem based on the hardness of computing Gröbner bases for noisy random systems of multivariate equations. We examine four settings, covering all possible parameter ranges of PCN with zero-degree noise. In the first setting, the PCN cryptosystem is known to be equivalent to Regevís LWE-based scheme. In the second, it is known to be at most as secure as Regevís scheme. We show that for one other settings it is equivalent to a variants of Regevís with less efficiency and in the last setting it is completely insecure and we give an efficient key-recovery attack. Unrelated to the attack, we also fix some flaws in the security proofs of PCN.
KeywordsPolly Cracker with Noise, Learning with Errors ,Gröbner bases, Cryptanalysis
URL http://link.springer.com/chapter/10.1007%2F978-3-642-30057-8_2
PublisherBerlin: Springer
Translation No
Refereed No