Créé en 1988, le Groupe de Recherche en Complexité et Cryptographie (GRECC) a pour objet de contribuer au développement en France de ces deux thèmes d'étude. Il a été intégré au LIENS en janvier 1992. Depuis lors, huit thèses ont été soutenues et la notoriété internationale acquise par le groupe en fait le point de référence pour la recherche civile en cryptographie dans notre pays. Sans chercher à surestimer l'importance du domaine, on constate le rôle croissant des techniques de cryptographie dans des domaines d'applications aussi divers que la sécurisation de l'Internet, le téléphone cellulaire, la télévision à péage, les transactions bancaires, la conservation et le transfert de données médicales etc. La présence en France d'une équipe de recherche amont d'un niveau comparable à celle d'autres institutions universitaires ou industrielles telles que le MIT, ATT Research, IBM Research ou l'Institut Weizmann, présence qui n'allait pas de soi et qui est à mettre à l'actif du LIENS, semble donc un atout pour le CNRS.
Certes, la pérennité du GRECC paraît maintenant établie. Néanmoins, la structure du groupe reste fragile. Les départs successifs de Claude Crépeau et de Jean-Marc Couveignes posent un problème d'encadrement que ne résout pas complètement le recrutement comme CR1 de Serge Vaudenay. Un fonctionnement optimal requiert l'arrivée d'un autre chercheur permanent et le groupe espère donc vivement pouvoir bénéficier dans les années qui viennent d'un recrutement au titre du CNRS ou de l'ENS.
La cryptologie, dans ses
aspects théoriques et pratiques forme maintenant le c 
ur
des recherches menées au GRECC. Cependant, cette recherche s'insère dans
un large environnement théorique et pratique qui amène
l'équipe à couvrir un
domaine d'étude
très ``vertical'' puisqu'il va de la théorie
abstraite de la complexité et
de la théorie algorithmique des nombres,
à l'implantation d'algorithmes cryptographiques
sur ordinateur ou sur carte à mémoire ou à la conception de
solutions globales pour le micropaiement et le contrôle d'accès
pour la télévision à péage.
-completsDepuis 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 ou certaines assertions, 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 :
-complets.
Le GRECC a participé à ce mouvement d'idées
en montrant
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
([27, 4]).
Un autre travail de l'équipe relevant de la théorie de la complexité, quoique motivé par une recherche par l'étude de mécanismes d'authentification nécessitant peu de ressources de calcul, recherche menée en liaison avec un partenaire industriel, a conduit à prouver le caractère rapidement transitif d'un système formé par des permutations aléatoires agissant sur des tableaux de taille fixe (voir [14, 49]).
Outre la théorie de la complexité algorithmique, la cryptographie s'appuie sur la théorie des nombres, en particulier sur les questions liées à la factorisation des nombres entiers. Depuis longtemps, le groupe suit de très près les développements dans ce domaine qui conditionnent la sécurité de nombreux algorithmes cryptographiques. Il a participé, en collaboration avec des chercheurs étrangers, à l'élaboration de diverses techniques de pointe, en particulier à l'accélération du crible algébrique (Number Field Sieve), méthode de factorisation des entiers naturels proposée par Lenstra et Pollard en 1990. Cette méthode se heurte à des difficultés pratiques telles que la manipulation de nombres entiers gigantesques (plusieurs millions de décimales). Un des chercheurs du groupe ([3]) a développé des techniques modulaires qui permettent d'éviter ces manipulations trop coûteuses et qui de plus, facilitent la parallélisation. Une version de l'algorithme NFS, utilisant, entre autres éléments, ces améliorations, a conduit au dernier record du monde dans ce domaine, établi par Arjen Lenstra.
Plus récemment, l'équipe a décidé de se doter, elle-aussi, d'une implantation complète et indépendante de NFS. Son choix s'est porté sur une variante de NFS développée par Montgomery. Un assez long travail de programmation fine a été nécessaire, auquel un des chercheurs du groupe s'est consacré à temps plein. Ce travail a inclus le crible proprement dit et les deux phases dites ``extraction de la racine carrée'' et ``calculs matriciels''.
Les résultats sont encourageants et ont permis d'obtenir la
factorisation complète du nombre :
, pour lequel il restait à décomposer un facteur
de cent chiffres. On a utilisé pour le criblage 32 stations
ayant 24 Mo de
RAM et cadencées à 80Mhz pendant pendant environ trois semaines.
L'algèbre linéaire
a pu être implantée en 29 jours de calculs sur Sparc 20
à 75Mhz avec ``seulement''
288 Mo de RAM.
Un réseau est un Z-module discret de R 
. Réduire un
réseau, c'est trouver une bonne base du réseau,
formée de vecteurs assez courts et assez orthogonaux. C'est un
problème
largement étudié mais
les solutions classiques
- sauf en petite dimension- ne sont jamais constructives.
Lenstra, Lenstra, Lovàsz, en 1983, ont
obtenu un algorithme polynomial, appelé LLL,
qui trouve une assez bonne base du réseau. En particulier, le
premier vecteur de cette base est suffisamment court pour jouer le
même
rôle que le plus court vecteur du réseau.
L'algorithme LLL, qui utilise l'arithmétique rationnelle pour
manipuler de très grands nombres est
extrêmement inefficace. Son implantation pratique nécessite
la substitution à l'arithmétique rationnelle de l'arithmétique flottante de
la machine. Le contrôle de
cette substitution est très délicat, tant du point de vue
théorique que pratique. Le GRECC
maintient une version finement optimisée qui a été développée
il y a quelque temps déjà([82, 9]). Il est ainsi en mesure
de valider tout nouveau résultat dans le domaine. Tout récemment,
il a proposé une nouvelle méthode heuristique permettant d'utiliser
LLL. Cette heuristique, dite du bidual, applique la réduction au dual
d'un réseau L, puis au dual du réseau obtenu en ``oubliant''
les derniers vecteurs de la base réduite (voir [88]).
Celle-ci a permis des progrès en cryptanalyse
qui seront détaillés un peu plus loin.
L'algorithme LLL, décrit ci-dessus permet également d'obtenir efficacement la description exacte d'un nombre algébrique dont on ne connaît qu'une représentation approchée. On peut ainsi utiliser des méthodes numériques pour certains problèmes du calcul formel.
Le groupe a mis en uvre ces idées pour
calculer explicitement des objets mathématiques complexes :
les revêtements de la sphère ramifiés au dessus de trois points
seulement, appelés aussi Dessins d'Enfants à cause de leur
représentation géométrique ([2]).
L'étude de ces objets remonte au siècle dernier mais ils ont été
remis au goût du jour par ``l'esquisse d'un programme'' rédigée
il y a quelques années par
Alexandre Grothendieck.
Le GRECC a ainsi obtenu des résultats sur les
propriétés de rationalité de ces revêtements ([80]).
A partir des dessins, il est possible de
construire explicitement des objets mathématiques ayant
certaines propriétés particulièrement intéressantes. Par exemple
on peut ainsi tenter de résoudre certaines instances du problème de
Galois inverse. C'est ainsi que le GRECC a pu
réaliser la construction et le calcul explicite d'un dessin
correspondant à une extension régulière de Q(T) de groupe de
Galois 
([15]). On connaissait l'existence d'une telle
extension sans en avoir la description. Cela prouve l'intérêt des
techniques de calcul de dessins.
C'est René Schoof qui a proposé en 1985 le premier
algorithme polynomial pour le calcul
du nombre de points rationnels sur une courbe elliptique définie
sur un corps fini.
Malheureusement sa méthode restait impraticable et ce sont des
idées d'Elkies et d'Atkin qui on permis d'aboutir à des calculs
explicites au moins dans le cas où le corps est primitif
( 
) ou du moins de caractéristique assez grande.
L'application de ces méthodes au calcul
de la cardinalité d'une courbe elliptique sur un corps
de type 
est restée un problème ouvert pendant
quelques années. Or le cas de la caractéristique 2 est le plus
utile dans les applications pratiques (cryptographie en particulier).
Ce problème à été résolu au sein du GRECC
en utilisant la géométrie des groupes formels
attachés aux courbes elliptiques et la notion de
-torsion ([42]).
Contre toute attente,
ces objets jouissent de propriétés algorithmiques
remarquables qui en font des auxiliaires précieux pour
le calcul.
Une implémentation réalisée
en collaboration avec le laboratoire de l'École
Polytechnique a démontré
l'efficacité de cette méthode.
À plusieurs reprises, un lien s'est établi entre les recherches du GRECC et la théorie des codes. C'est ainsi que les chercheurs du GRECC ont été amenés à étudier divers problèmes de codes. On se bornera à mentionner deux de ces ``points de contact''.
Les différentes études précédentes ont montré la nécessité de disposer de librairies de calcul dans les corps finis de caractéristique 2 Des librairies semblables dans Z/pZ ont par ailleurs été développées à l'École Polytechnique par Morain et Lercier. Ces travaux ont été unifiés pour obtenir une librairie unique de calcul optimisé dans toute extension définie sur un anneau primitif. Baptisée zen, elle se veut à la fois simple d'emploi et efficace. Les premiers résultats expérimentaux d'implantation prouvent que cette librairie répond à ces objectifs [85].
L'invention de la cryptographie à clé publique remonte en 1976 avec l'article fondateur de Diffie et Hellman. L'idée, reposant sur une dissymétrie entre la clé de chiffrement supposée disponible pour tous et la clé de déchiffrement, réservée à l'utilisateur légitime, est encore aujourd'hui illustrée par un très petit nombre d'exemples, le principal étant le système RSA, du nom de ses auteurs Rivest, Shamir et Adleman.
Cela dit, et contrairement à une opinion répandue, la cryptographie à clé publique ne sert pas seulement, et sans doute même pas principalement, à chiffrer. Elle autorise diverses autres fonctionnalités riches d'applications, par exemple :
La question des alternatives à RSA est évidemment un défi essentiel auquel fait face la cryptographie moderne. Récemment, en collaboration avec David Naccache, nous avons conçu deux cryptosystèmes différents de RSA mais reposant sur des propriétés arithmétiques ([56, 86]). Le premier est une version multiplicative du sac à dos a malheureusement des performances qui ne sont pas comparables à celles du RSA (en terme de temps de calcul). Le second est plus prometteur : il est basé sur le problème du calcul des logarithmes ``discrets'' (c'est-à-dire modulo un entier), alors que RSA est fondé sur la difficulté de factoriser les entiers. Ce nouveau système pourrait rivaliser avec le RSA, après avoir naturellement été examiné par la communauté...
Au delà de la signature de base, il existe de nombreuses variantes assurant diverses fonctionnalités. Citons par exemple, sans souci d'exhaustivité :
En collaboration avec des collègues allemands, le groupe a entrepris récemment un effort de classification de différents concepts de schémas de signature électronique, permettant de les ranger en plusieurs classes orthogonales([57]) mais combinables entre elles. Il a également proposé de nouveaux schémas de signatures avec vérifieurs multiples([58]), pour lesquels la fraude d'un vérifieur est détectable par les autres vérifieurs ainsi qu'un nouveau schéma de signature de groupe avec signeur anonyme, qui est plus efficace que les propositions connues ([91])
Le GRECC s'est également intéressé à la question de la certification des clés publiques, qui est l'un des principaux problèmes à résoudre pour que le commerce électronique se développe sur l'Internet. Nous avons pu étendre le concept de clefs publiques basées sur l'identité introduit par Marc Girault en 1991 et mettre au point diverses applications( [89]).
Enfin, l'équipe s'est penchée sur la question du temps de calcul : en effet, les deux principaux schémas de signature à clé publique, le RSA et le DSS, obligent l'entité qui le signe à effectuer une exponentiation modulaire. Or, en pratique, ces signatures sont souvent effectuées par des cartes à puces qui ont une puissance de calcul très limitée qui ne leur permet pas de réaliser en un temps raisonnable ces exponentiations. Une alternative à ce problème est d'utiliser la puissance de calcul d'un serveur (terminal bancaire, téléphonique, etc) en lui déléguant des calculs. Cette idée a été introduite en 1988 par Matsumoto, Kato et Imai. Mais aucun des protocoles existants n'étaient sécurisés. En collaboration avec Jean-Jacques Quisquater (Université Catholique de Louvain, Belgique), nous avons pu proposer des méthodes d'accélération plus sûres, tant pour le RSA ([29, 31]) que pour le DSS ([30]).
Les systèmes ``zero-knowledge'' ont été évoqués ci-dessus dans le paragraphe relatif à la théorie de la complexité. Fiat et Shamir ont donné en 1986 une application de ce concept en imaginant un procédé d'identification fondé sur l'utilisation d'une clé secrète mais ne révélant aucune information (en particulier pas la clé, au contraire des méthodes du type mot-de-passe). Le GRECC a examiné la possibilité d'arriver à un résultat analogue en n'autorisant que des calculs très simples. Dans cet ordre d'idées, l'équipe a mis au point toute une série de protocoles d'identification simples :
uvre de codes correcteurs d'erreurs. -complet, inspiré de la théorie des réseaux de
neurones
([78]).Plus récemment nous sommes passés à l'étude fine de la sécurité des problèmes combinatoires sous-jacents ainsi qu'à l'analyse des performances dans la pratique. Pour la proposition 2 ci-dessus, nous avons malheureusement constaté qu'elle est inutilisable sur carte à puce car les tailles de problèmes implantables sur ces cartes sont à la portée d'attaques que nous avons imaginées, en des temps de quelques heures sur SparcStation 10.
En revanche, l'étude des autres protocoles a conduit à des conclusions prometteuses. Nous avons pu réaliser l'implémentation sur une carte à microprocesseur de faible capacité du protocole mentionné ci-dessus en 3. Nous avons également mené dans [21] une analyse de sécurité ``réaliste'' du protocole 4 ainsi que du protocole PKP de Shamir. Par réaliste, on veut dire qu'on ne se contente pas d'estimations asymptotiques sur les attaques potentielles mais qu'on évalue aussi, par extrapolation, la performance de ces attaques avec une implémentation pratique. Cette méthode permet de déterminer les paramètres qui assurent une utilisation sûre.
La recherche de ``preuves de sécurité'' est tendance significative de la recherche la plus récente en cryptographie. Le simple fait qu'un algorithme cryptographique ait résisté durant plusieurs années aux attaques des cryptanalystes a constitué pendant longtemps la seule forme possible de validation. Un paradigme totalement distinct provient du concept de ``sécurité prouvée''. Cette approche propose des preuves relatives qui ramènent la sécurité du schéma proposé à celle d'un problème classique tel que la factorisation des entiers ou le problème du logarithme discret, déjà cités. Bien entendu, tout comme dans d'autres sciences, on fait, le cas échéant appel à une certaine idéalisation des objets qu'on manipule. A ce prix, on obtient parfois des ``preuves'' qui ne sont, au plan méthodologique, qu'une autre technique de détection des erreurs mais qui contribuent fortement à la confiance.
Dans les dernières années, le GRECC a fait des preuves de sécurité un de ses axes de recherche majeurs. En utilisant des outils de théorie de la complexité, nous avons pu prouver la sécurité - relativement au problème du logarithme discret - d'une modification mineure du schéma de signature maintenant classique de ElGamal (voir [61]).
Nous nous sommes ensuite tournés vers le difficile problème de la sécurité des signatures en blanc. Comme on l'a dit plus haut, il s'agit d'un mécanisme destiné à reproduire sous une forme purement numérique les principales caractéristiques de l'argent liquide, y compris l'anonymat des transactions. Le problème suivant dit de la ``conservation du flux'' semble naïf : prouver qu'après avoir reçu n pièces de monnaie électroniques, un utilisateur ne peut en générer n+1, mais la question restait, depuis quinze ans, d'ordre conjectural. En systématisant la méthode que nous avions utilisée pour les signatures El Gamal, nous avons pu proposer un schéma de signature en blanc de sécurité prouvée relativement au logarithme discret [60]. Nous avons ensuite proposé un schéma analogue prouvé sûr relativement à la factorisation [62].
Nous avons enfin essayé d'appliquer nos idées à la sécurité du standard DSS. Nous avons tout d'abord mis en évidence des faiblesses potentielles [74], puis donné une preuve de sécurité d'une variante proche [98].
La question des preuves de sécurité peut sembler théorique : selon nous, il
n'en est rien. Il s'agit de recherche appliquée : dans sa conférence
invitée au congrès CRYPTO 96, Ernie Brickell, passé récemment de Sandia
Labs à Banker's Trust, a cité nos travaux sur les signatures en blanc
comme
des éléments qui contribuent à la confiance requise pour la mise
en uvre systématique des paiements sécurisés sur l'Internet.
Le GRECC a fourni un travail de préparation considérable dans l'étude de ce sujet difficile et qui a donné lieu récemment à des résultats profonds liant les fonctions à sens unique de la cryptographie et les générateurs de pseudo-aléa. Ce travail a bénéficié de la visite en juin 95 de Mike Luby (ICSI, Berkeley), expert reconnu du domaine.
Ce travail nous a permis d'attaquer avec succès la question du rendement : chaque bit d'aléa produit par un générateur a un coût en terme de complexité algorithmique. Ce coût est mesuré en fonction d'un paramètre de sécurité qui mesure la taille des nombres manipulés. En substituant à la théorie des nombres la théorie des codes, comme nous l'avons fait pour l'identification, nous avons pu dans [48] proposer un générateur pseudo-aléatoire extrêmement simple, de rendement linéaire et dont la sécurité est aussi prouvée au sens du paragraphe précédent.
L'analyse cryptographique est la partie de la cryptographie qui s'efforce de recouvrer la partie secrète d'un message, d'un code ou d'un outil cryptographique, à partir des éléments publics. Une méthode très efficace en ce domaine est la recherche de relations de dépendance linéaires à coefficients modérés en utilisant l'algorithme de Lenstra, Lenstra et Lovàsz (LLL). En utilisant son implantation performante de LLL, le groupe a pu mener à bien plusieurs ``cryptanalyses'' nouvelles :
En dehors des méthodes utilisant l'algorithme LLL, nous nous sommes intéressés à l'analyse de la sécurité des système basés sur la difficulté du décodage général des codes linéaires (système de Mc Eliece et, plus récemment procédé d'identification de Stern, mentionné plus haut). En utilisant des algorithmes existant et en les optimisant, il a été possible d'améliorer les performances des attaques contre le cryptosystème de McEliece. Il ne s'agit pas à proprement parler de cryptanalyse puisque le système n'est pas cassé mais les paramètres minimaux assurant la sécurité sont ainsi plus finement évalués [100, 37, 77] Un travail analogue pour le procédé de Stern a aussi été mené. Dans le même ordre d'idées, une cryptanalyse réaliste du schéma d'authentification de K. Chen a été proposée [35]. Cette cryptanalyse s'appuie sur un algorithme original de décodage général à distance minimale de Gabidulin des codes linéaires.
Nous avons également, dans un travail mené avec Don Coppersmith (IBM Yorktown), montré qu'un procédé de signature introduit par Adi Shamir et basé sur les permutations birationnelles, pouvait être attaqué avec succès ([39, 8]). Notre cryptanalyse utilise des méthodes empruntées à la théorie de Galois et, là encore, permet des calculs explicites.
Pendant longtemps, la cryptographie conventionnelle a fait l'objet de très peu de recherches en dehors de celles de Shannon, qui, dans les années cinquante, a introduit les notions de diffusion et de confusion. De façon surprenante, le développement de la cryptographie à clé publique a amené, par ricochet, des progrès sur les méthodes conventionnelles. Il faut noter en effet que la cryptographie à clé publique n'élimine pas le recours aux procédés conventionnels, pour au moins deux raisons :
S'agissant précisément des fonctions de chiffrement symétriques (comme le DES, Data Encryption Standard) ou des fonctions de hachage, deux méthodes très générales d'évaluation et d'attaque sont apparues récemment :
On vient de mentionner le concept de fonction de hachage. On requiert en général que l' opération se fasse de façon qu'il soit virtuellement impossible de calculer deux messages ayant même condensé (on parle de collision). Le GRECC a ainsi étudié la fonction de hachage FFT-Hash 2 proposée par Claus Schnorr au colloque Eurocrypt'92 pour laquelle il a trouvé des collisions. Il a ensuite, en collaboration avec Claus Schnorr, proposé des variantes plus sûres de FFT-hash [23, 64].
Plus récemment, le GRECC a également mis en évidence certaines faiblesses de la fonction de hachage MD4 proposée par R. Rivest en obtenant des collisions pour une version simplifiée ([24]).
On a parlé plus haut des deux méthodes générales de cryptanalyse (différentielle et linéaire). En utilisant une approche basée sur l'utilisation systématique de la transformée de Fourier des fonctions booléennes, le groupe a pu mettre en évidence des propriétés de dualité de ces deux cryptanalyses, et donc leur complémentarité [95, 36]. Il a aussi unifié les deux types de cryptanalyse en les isolant de leur aspect linéaire par une approche statistique [73].
Le GRECC a aussi porté son attention sur la fonction de chiffrement SAFER proposée par J. Massey et dédiée aux microprocesseurs 32 bits. ainsi que sur la fonction de chiffrement Blowfish. Il a en particulier proposé une attaque sur une variante de SAFER ([24]) montré dans [75] l'existence de clefs qui affaiblissent la sécurité de Blowfish.
Enfin le GRECC a proposé un mécanisme de chiffrement adapté aux coprocesseurs arithmétiques ([54]). Ce travail mené en collaboration avec la société GEMPLUS, permet d'optimiser la vitesse du chiffrement sur une carte à puce en utilisant les fonctions disponibles à bord, en particulier celles du coprocesseur.
S'inspirant des cryptanalyses dont on vient de parler dans les trois paragraphes précédents, le GRECC a entrepris d'élaborer une théorie générale des fonctions cryptographiques conventionnelles (hachage et chiffrement). Cette théorie s'est pour l'instant développée suivant deux axes
Les protocoles cryptographiques sont des algorithmes à plusieurs participants où certaines information secrètes sont traitées. On considère, par exemple, le problème général du calcul partagé d'une fonction : deux participants A et B veulent calculer une fonction f(x, y) sur données a et b, a étant connue de A et b connue de B, sans se révéler mutuellement a et b, mais seulement le résultat f(a, b). On considère également le scénario où une information secrète doit être partagée entre n participants de façon que k d'entre eux doivent contribuer leur part pour que le secret soit découvert : c'est le problème du ``partage du secret''. Sans en faire l'axe principal de ses recherches, le GRECC ne néglige pas l'étude des protocoles.
En matière de partage du secret, un problème important est d'optimiser la taille des parts : en effet, un fait bien connu dans la théorie des partages de secrets parfaits (au sens de la théorie de l'information) est que la taille des parts détenues par chaque personne doit être supérieure ou égale à celle du secret. Si l'on requiert une sécurité basée seulement sur la complexité algorithmique, on peut s'affranchir de cette contrainte comme l'a montré H. Krawczyk à Crypto'93 pour les structures d'accès seuil. En collaboration avec Antonnella Cresti (Université de Rome, Italie), nous avons pu généraliser ce résultat à toutes les structures d'accès ([28])
Comme on l'a dit dès le début de ce chapitre, les applications industrielles de la cryptographie sont nombreuses. Bien entendu, le GRECC a principalement pour vocation la recherche fondamentale. Cependant, il lui paraît essentiel de ne pas perdre de vue le côté pratique de la cryptographie et c'est pourquoi, s'agissant des algorithmes, il a toujours le souci, ainsi qu'on l'a vu plus haut, de les valider par des implantations sur carte à puce ou sur machine.
Certains domaines d'applications demandent, au delà des algorithmes, la définition de solutions cryptographiques globales. À plusieurs reprises, Le GRECC a proposé de telles solutions :
A la suite des travaux de G. Brassard et C. Bennett, il a été proposé d'utiliser des phénomènes quantiques dans la construction de protocoles cryptographiques. Depuis quelques années, il existe aux États-Unis un prototype de transmetteur quantique démontrant le potentiel de ces idées. Le GRECC a participé à l'élaboration de la cryptographie quantique en démontrant en particulier la sécurité des solutions proposées précédemment [6] [34]. Il a également participé à des recherches de physique fondamentale sur la téléportation d'un état quantique [5].
Il a ensuite concentré ses recherches sur l'élaboration de protocoles efficaces pour des tâches cryptographiques. Une fois encore, ces protocoles nécessitent l'utilisation de la théorie des codes. C'est ainsi que nous avons mis au point avec Louis Salvail (Université de Montréal) un protocole d'identification quantique permettant à deux personnes de vérifier qu'ils possèdent un mot de passe commun sans se le révéler. ([44]).
Il faut noter que la cryptographie quantique ouvre des perspectives
de coopération avec les physiciens de l'École Normale Supérieure.
Un autre sujet, le calcul quantique éveille également
l'intérêt de nos collègues physiciens. Il s'agit d'une approche
nouvelle de théorie de la complexité qui envisage la mise
en uvre de machines dont l'évolution réalise des superpositions
d'états quantiques. Les premiers résultats obtenus dans ce domaine sont
impressionnants puisque ces machines (si elles voyaient le jour)
seraient à même de réaliser des tâches au delà des limites
des calculateurs actuels.
Le GRECC suit
de près l'évolution de cette nouvelle spécialité. Il a pu faire le point
grâce aux visites successives de Gilles Brassard (Université de Montréal)
en 1995 et de
Andy Yao (Princeton University),
en juin 96. Cependant, le départ de Claude Crépeau risque de conduire
à investir moins dans ces questions.
Un certain nombre d'éléments prospectifs ont été déjà évoqués ci-dessus, comme par exemple la question de la généralisation de la cryptanalyse linéaire/différentielle, pour laquelle nous avons prévu la visite à l'ENS d'Eli Biham (Technion, Haïfa), pour octobre 1997.
Nous comptons également ouvrir de nouvelles perspectives de recherche selon les axes suivants :
C'est une question qui vient de se retrouver posée nettement à la suite de trois articles parus à Eurocrypt 96 et mettant en jeu des techniques algébriques ou fondées sur l'utilisation de l'algorithme LLL. Compte tenu de notre savoir faire dans ces deux domaines, nous pensons pouvoir unifier les diverses attaques et les améliorer. Également, utilisant les méthodes de sécurité prouvée, nous pourrions proposer des contremesures adéquates.