Complexité et cryptographie
Programme
- Classes de complexité P, NP et co-NP.
Formules booléennes, clauses, problèmes SAT et CNF.
Réductions polynomiales et problèmes NP-complets.
Position du problème PRIME (primalité) ;
réduction de la factorisation à un problème de décision,
et position de ce problème.
- Classes de complexité probabilistes RP,
co-RP et BPP.
Fonctions négligeables, fonctions significatives
et lemmes d'amplification.
Test polynomial probabiliste de primalité.
Références :
- Fonctions à sens unique. Définition et collections
de fonctions candidates : DLP (Discrete Logarithm Problem),
RSA et Rabin.
- Générateurs pseudo-aléatoires cryptographiquement sûrs.
Définition et lemme d'étirement.
Construction à partir de prédicats difficiles.
Preuves relatives de sécurité.
Références :
- Preuves interactives et classe de complexité IP.
Protocoles sans divulgation (ZK = Zero Knowledge) : Fiat-Shamir,
Guillou-Quisquater et Schnorr.
Références :
Annales
Autres références
La Génération d'Aléas
sur Ordinateur,
par Louis Goubin et Jacques Patarin.
Voici la version pdf
complète du cours d'Oded Goldreich,
qui est aussi l'auteur du livre
Foundations of Cryptography,
en deux volumes.
Notes du cours
Computational
Complexity , donné en 2004 à Berkeley par
Luca Trevisan.
Diapositives et notes du cours
Advanced
Complexity Theory,
donné en 2003 au MIT par
Madhu Sudan.
Le blog
de Lance Fortnow
et le
zoo
gardé par son ami
Scott Aaronson,
qui recense près de 400 classes de complexité (ou de comptage),
et fournit aussi un
glossaire
intéressant :
on this page I've collected terms […]
that theoretical computer scientists tend
to use without defining them,
assuming everyone just knows what they mean.