A Survey on Polly Cracker Systems

Françoise Levy-Dit-Vehel (1) , Maria-Grazia Marinari (2) , Ludovic Perret (3) , Carlo Traverso (4)

1 ENSTA Paris - École Nationale Supérieure de Techniques Avancées
2 UniGe - Università degli studi di Genova = University of Genoa
3 SALSA - Solvers for Algebraic Systems and Applications
4 University of Pisa - Università di Pisa

In 1993 Boo Barkee and others have written a paper “Why you cannot even hope to use Gröbner Bases in Public Key Cryptography: an open letter to a scientist who failed and a challenge to those who have not yet failed.” Since 1994, further attempts have been made, that gave rise to several cryptosystems now known as Polly Cracker systems. None of these proposals have been successful, and while Gröbner Bases are now an established tool for cryptanalysis, the challenge of Boo Barkee still stands w.r.t. the design point of view. We outline a description of how all these attempts have failed.

Domaines: Informatique [cs]

Françoise Levy-Dit-Vehel, Maria-Grazia Marinari, Ludovic Perret, Carlo Traverso. A Survey on Polly Cracker Systems. Gröbner Bases, Coding, and Cryptography, Springer, pp.285-305, 2009, 978-3-540-93805-7. ⟨10.1007/978-3-540-93806-4_16⟩. ⟨hal-01298878⟩