Antoine Joux, ERC Advanced Grant 2014
La cryptographie est la base de la sécurité de l’information dans le monde numérique. Elle s’appuie sur des problèmes présumés difficiles. Toutefois, les connaissances actuelles en complexité ne permettent pas de garantir la solidité de ces portes blindées derrière lesquelles nous mettons nos secrets. L’ambition de l’ERC Advanced Grant d’Antoine Joux, enseignant-chercheur et membre du Laboratoire d’informatique de Paris 6 (LIP6 - CNRS/Université Pierre et Marie Curie), est d’apporter des outils algorithmiques pour différencier les problèmes faciles des difficiles et pour mieux choisir les portes derrière lesquelles se protéger. L’objectif étant d’éviter l’utilisation de systèmes ne protégeant pas correctement les données sensibles.
Lorsque vous souhaitez chiffrer et déchiffrer des messages (plus ou moins) secrets, signer un document numérique ou vous authentifier auprès de votre banque, vous (ou plutôt votre ordinateur ou à votre carte bancaire) utilisez des techniques ou cryptosystèmes construits à partir de problèmes calculatoires réputés difficiles. Bien choisir les hypothèses sur lesquelles reposent ces problèmes est plus délicat qu’il n’y paraît : il faut barrer la route d’un éventuel attaquant tout en permettant un déchiffrement efficace pour un utilisateur légitime muni de la bonne clé. Les hypothèses ou problèmes utilisés doivent être polyvalents pour offrir de larges possibilités de fonctionnalités et autoriser des implémentations efficaces, tout en étant assez solides pour garantir la sécurité. Malheureusement, les connaissances actuelles ne permettent pas de prouver cette solidité !
En effet, du point de vue de la théorie de la complexité, la cryptographie ne peut exister que si P est différent de NP. La classe P correspond aux problèmes solvables en temps polynomial tandis que la classe NP regroupe ceux pour lesquels une solution, une fois connue, est vérifiable en temps polynomial. Les problèmes difficiles qui nous intéressent sont dans NP car il est facile de tester si une clé est correcte, mais ne doivent pas être dans P pour que la bonne clé ne se trouve pas facilement. Or, la question « P = NP ? » n’est pas résolue. Pire, elle est considérée comme le problème ouvert le plus important en informatique théorique, à un point tel qu’elle fait partie des sept problèmes à 1 million de dollars du Clay Millenium Challenge. Par conséquent, on ne sait pas aujourd’hui avec certitude s’il existe véritablement des problèmes difficiles sur lesquels appuyer les fondements de la cryptographie telle qu’on la définit aujourd’hui. On ne peut que choisir des problèmes qui ont été suffisamment étudiés pour que l’absence de solution soit un bon indice de leur difficulté. Les problèmes difficiles utilisés en cryptographie peuvent être vus comme des portes blindées, derrière lesquelles nous protégeons nos données. La question pour Antoine Joux est de déterminer si les problèmes sont vraiment difficiles. Il essaie donc de casser ces portes blindées pour voir celles qui résistent et vérifier la protection que chacune apporte.
La principale ambition de l’ERC Almacrypt est de réaliser ces attaques par une analyse algorithmique avancée. En effet, les réelles avancées en cryptanalyse ne proviennent pas de l’explosion de la puissance de calcul des ordinateurs lors des dernières décennies, mais sont liées aux progrès algorithmiques. Par exemple, sur un problème tel que celui du logarithme discret en petite caractéristique, alors qu’en 30 ans d’augmentation de la puissance de calcul la taille des clefs attaquables n’avait que doublée, les derniers progrès algorithmiques ont permis de gagner un facteur 10 en quelques années seulement. L’avancée théorique se positionne donc comme le véritable enjeu car elle permet de faire des progrès que même une multiplication par 100 ou 1000 des moyens matériels n’aurait pas autorisés.
L’objectif principal de cette ERC est de remettre en question les deux piliers soutenant la cryptographie à clé publique utilisés sur internet : la factorisation et le logarithme discret. Récemment, il a été montré que dans certains cas le problème du logarithme discret est considérablement plus faible que prévu. Cette découverte, initiée par Antoine Joux, aurait pu être réalisée il y a 30 ans. Mais comme souvent la découverte de nouvelles méthodes ne peut se faire qu’à force de manipuler mentalement les problèmes et les objets mathématiques, et la résolution se fait par un déclic : tout à coup une idée ouvre de nouvelles perspectives. Dans le même esprit, le positionnement de l’ERC est de trouver de nouvelles voies, et de réfléchir à la sécurité des autres cas de problème du logarithme discret. Antoine Joux souhaite étudier la généralisation des techniques récentes et rechercher de nouvelles options algorithmiques avec une efficacité comparable ou meilleure.
Parcours
Antoine Joux a soutenu sa thèse en informatique sous la direction de Jacques Stern en 1993. Ingénieur de l’Armement de 1993 à 2012, il a été sous-directeur scientifique à la Direction Centrale de la Sécurité des Systèmes d’Information. Après avoir été professeur associé à l’Université de Versailles Saint-Quentin-en Yvelines, il est titulaire de la Chaire Cryptologie de la Fondation l’Université Pierre et Marie Curie depuis septembre 2013. Rattaché au Laboratoire d’informatique de Paris 6 (LIP6 - CNRS/Université Pierre et Marie Curie), il y dirige l’équipe Almasty. Il est le second chercheur français à avoir obtenu (en 2013) le prestigieux Prix Gödel qui récompense des travaux remarquables en informatique théorique. Il est Fellow de l’IACR (International Association for Cryptologic Research) depuis 2014.