Introduction aux preuves interactives et au zero-knowledge

Les preuves intéractives définissent une classe de problèmes assez large englobant en particulier NP et co-NP. Elles ont un intérêt pratique dans le cadre de l'identification cryptographique, en particulier lorsqu'elles sont accompagnées de la propriété zero-knowledge.<br/> Cet exposé est une introduction, suivant un plan traditionnel. Il sera illustré par quelques exemples pris à la théorie des graphes et à la théorie des nombres élémentaire. On évoquera les relations entre les classes de complexité introduites et la hiérarchie polynomiale classique.