Description
La cryptographie cherche systématiquement à mettre l’adversaire en face
de tâches algorithmiques insurmontables. La question de la caractérisation
des problèmes algorithmiquement difficiles engendre la théorie de la
complexité. Le cours s’articule autour des notions suivantes:
- Algorithme, machine de Turing
- Calculabilité, décidabilité
- Classes de complexité, la classe P, la classe NP
- Réductions polynomiales, problèmes NP-complets, théorème de Cook
- la classe PSPACE.
Les bases de la théorie de la complexité préparent aux réductions de sécurité qui
accompagnent les protocoles cryptographiques modernes.
Références
- M. Zeitoun, Théorie de la complexité, matériel de cours
- G. Zémor, Notes de cours.
- M. Sipser, Introduction to the theory of computation, 1996, 3rd Edition Cengage Learning, 2012.
- M. R. Garey et D. S. Johnson, Computers and Intractability: a guide to the theory of NP-completeness, 1979, Freeman.
- S. Arora et B. Barak, Computational Complexity: A Modern Approach, 2009, Cambridge.
- L. Trevisan, Computational Complexity, lecture notes.