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 describe the construction of an instance of our system - which is a modified Polly Cracker scheme - 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 main feature of our system is the resistance to intelligent linear algebra attacks.
Type de document :
Chapitre d'ouvrage
Progress in Computer Science and Applied Logic Volume 23, 23, Springer, pp.177-192, 2004, 978-3-0348-9602-3. 〈10.1007/978-3-0348-7865-4_11〉
Liste complète des métadonnées

https://hal-ensta.archives-ouvertes.fr/hal-00988797
Contributeur : Aurélien Arnoux <>
Soumis le : vendredi 9 mai 2014 - 10:34:38
Dernière modification le : mercredi 6 décembre 2017 - 16:46:10

Lien texte intégral

Identifiants

Collections

Citation

Françoise Levy-Dit-Vehel, Ludovic Perret. A Polly Cracker System Based on Satisfiability. Progress in Computer Science and Applied Logic Volume 23, 23, Springer, pp.177-192, 2004, 978-3-0348-9602-3. 〈10.1007/978-3-0348-7865-4_11〉. 〈hal-00988797〉

Partager

Métriques

Consultations de la notice

91