François Arnault |
Date de l'exposé : 21 juin 2002
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.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.