Next: Missions et invitations
Up: Présentation des thèmes
Previous: Cryptographie quantique
Un certain nombre d'éléments prospectifs ont été déjà évoqués ci-dessus,
comme par exemple la question du calcul quantique pour lequel nous
avons prévu la visite à l'ENS d'Andy Yao (Princeton University),
pour juin 96.
Nous comptons également ouvrir de nouvelles perspectives de recherche
selon les axes suivants :
Le GRECC a déjà fourni
un travail considérable dans l'étude de ce sujet difficile et
qui a donné lieu récemment à des résultats profonds liant les
fonctions à sens uniques de la cryptographie et les générateurs
de pseudo-aléa. Ce travail préliminaire devrait être parachevé
prochainement grâce à la visite en juin 95 de Mike Luby
(ICSI, Berkeley), expert reconnu du domaine. Nous devrions être
alors prêts à obtenir nos propres résultats et comptons nous
concentrer sur deux questions
-
la mise en évidence de nouveaux <<bits difficiles>> : il résulte
en effet de résultats de Yao d'une part, Goldreich et Levin d'autre part,
que tout <<bit difficile>> donne lieu à un générateur de pseudo-aléa.
Une série de travaux de Shamir, Schnorr, Micali, Blum et autres
a montré que les bits de poids fort de RSA ou du logarithme discret
sont difficiles. Le résultat s'étend aux bits de poids faible mais
la question des bits centraux est un problème ouvert réputé difficile.
Nous pensons avoir quelques idées au moins pour le cas du logarithme discret.
-
la question du rendement : chaque bit d'aléa produit par un générateur
fonctionnant sur la base d'un bit difficile 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 l'espoir de produire un aléa
avec un rendement linéaire.
Les travaux évoqués ci-dessus sont naturellement susceptibles
d'applications pratiques.
Comme on l'a
mentionné plus haut, les procédés de signature en usage ne sont pas
totalement satisfaisants pour diverses raisons
-
ils nécessitent le calcul d'exponentielles modulaires, ce qui excède
les possibilités des cartes à microprocesseur bas-coût
-
ils ont une taille relativement élevée (512 bits pour RSA, 320 bits pour DSS),
ce qui interdit par exemple la signature individuelle de messages de petite
taille (comme les paquets des transmissions par paquets)
Il y a là, à l'évidence, des enjeux théoriques et économiques importants.
Notre projet est d'entreprendre des recherches sur les deux questions.
S'agissant de l'amélioration des performances, nous sommes convaincus
qu'un compromis temps/mémoire est possible. Pour ce qui est des signatures
de taille réduite, la seule proposition jamais faite (par Matsumoto et
Imai) vient d'être cassée. Nous croyons être en mesure de
simplifier la méthode d'attaque et, éventuellement, de pouvoir ainsi
réparer le procédé de signature, en contrant l'attaque.
Il s'agit
là d'une question sur laquelle il faut avancer avec prudence puisque
les meilleurs experts ont vu parfois leur propositions mises en échec.
Nous pensons néanmoins pouvoir progresser sur un scénario qui n'a pas
encore reçu toute l'attention souhaitable et que nous appelons
échange de clés dissymétrique. Il s'agit d'autoriser un échange
de clés entre deux entités cryptographiques : un serveur doté d'une
puissance de calcul importante et un client aux capacités réduites
(par exemple une carte à microprocesseur). Un tel système pourrait avoir
des applications sur les problèmes de contrôle d'accès. Nous
pensons aborder là encore le problème sous l'angle de la théorie des
codes.
Forts de notre succès sur la mise en évidence d'une dualité entre
les deux méthodes de cryptanalyse, nous espérons pouvoir unifier
voire améliorer les deux techniques en nous plaçant dans le cadre
des tests statistiques généraux. Il nous semble en effet que les
progrès récents n'ont pas épuisé le potentiel des méthodes proposées.
Par ailleurs, l'expérience acquise devrait nous permettre, le moment venu, de
proposer, le cas échéant,
de nouveaux systèmes conventionnels (hachage ou chiffrement).
Next: Missions et invitations
Up: Présentation des thèmes
Previous: Cryptographie quantique