HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation

A Polly Cracker system based on Satisfiability

Abstract : This paper presents a public-key cryptosystem based on a subclass of the well-known satisfiability problem from propositional logic, namely the doubly-balanced 3-sat problem. We first describe the construction of an instance of our system starting from such a 3-sat formula. Then we discuss security issues: this is achieved on the one hand by exploring best methods to date for solving this particular problem, and on the other hand by studying (systems of multivariate) polynomial equation solving algorithms in this particular setting. The result of our investigations is that both types of method fail to break our instances. We end the paper with some complexity considerations and implementation results.
Document type :
Complete list of metadata

Cited literature [1 references]  Display  Hide  Download

Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Tuesday, May 23, 2006 - 7:09:57 PM
Last modification on : Thursday, April 14, 2022 - 1:58:01 PM
Long-term archiving on: : Sunday, April 4, 2010 - 8:50:03 PM


  • HAL Id : inria-00071888, version 1



Françoise Levy-Dit-Vehel, Ludovic Perret. A Polly Cracker system based on Satisfiability. [Research Report] RR-4698, INRIA. 2003. ⟨inria-00071888⟩



Record views


Files downloads