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

Details:

   
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
ISBN978-3-642-30056-1/pbk
URL http://link.springer.com/chapter/10.1007%2F978-3-642-30057-8_2
LanguageEnglish
Pages17--33
PublisherBerlin: Springer
Year2012
Edition0
Translation No
Refereed No
Webmaster