Théorie de la complexité : Preuves Interactives et Approximation des problèmes -complets

Depuis une quinzaine d'années, les progrès de la théorie des algorithmes ont permis de mettre en évidence la possibilité d'établir ou de transmettre certains faits mathématiques, non pas à l'aide d'une preuve au sens logique du terme, mais à travers un processus interactif de questions réponses aléatoires. Ces travaux ont entre autres choses conduit à la formulation de la notion de preuve <<zero-knowledge>>.

Ces découvertes sont riches d'applications : on a ainsi pu réaliser effectivement des systèmes cryptographiques présentant des fonctionnalités entièrement nouvelles :

• systèmes à clefs publiques (où la clef de codage est publique)
• systèmes <<zero-knowledge>>, qui autorisent l'authentification sur un canal non sécurisé et pour des architectures décentralisées.

Citons en particulier

• La définition du <<zero-knowledge>> dans un modèle restreint : le modèle original suppose que l'un des participants a une puissance de calcul infinie ([BCLL91]).
• Les résultats sur l'impossibilité de définir des algorithmes d'approximation pour certains problèmes d'optimisation concernant les codes correcteurs d'erreur ou les réseaux à coordonnées entières ([Ste93a,ABSS93]). La version définitive de ce dernier travail va paraître prochainement dans un numéro spécial du JCSS, consacré aux preuves interactives et à l'approximation.