Next: Théorie algorithmique des
Up: Présentation des thèmes
Previous: Présentation des thèmes
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.
En 1992, on a assisté à un spectaculaire ``retour''
des études de cryptographie puisque des concepts issus
de cette discipline appliquée (celui d'interaction en
particulier) ont permis de faire des progrès spectaculaires
sur la question de l'approximation des
problèmes 
--complets.
Le GRECC a participé à ce mouvement d'idées
(Voir entre autre [BCY91] et [Ste93a,SAS93]).
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 concerant les
codes correcteurs d'erreur ou les réseaux à coordonnées entières
([Ste93a,SAS93]).
Next: Théorie algorithmique des
Up: Présentation des thèmes
Previous: Présentation des thèmes