Vadim Lyubashevsky, ERC Starting Grant 2014

Après un diplôme en sciences informatiques obtenu à l’Université de Columbia, Vadim Lyubashevsky poursuit son cursus académique en doctorat à l’Université de San Diego en Californie en 2008, puis en post-doctorat au département de sciences informatiques de l’Université de Tel-Aviv. Il rejoint finalement en 2010 l’équipe projet commune « Cascade » du Département d’Informatique de l’Ecole Normale Supérieure (DI ENS, CNRS/Inria/ENS Paris).

Le domaine général des recherches de Vadim Lyubashevsky est la cryptographie. Plus spécifiquement, il travaille sur la conception de modèles de chiffrements à clé publique qui resteraient sécurisées dans le contexte de l’informatique quantique.

Comme toujours en cryptographie, Vadim Lyubashevsky illustre les principes scientifiques sur lesquels il travaille par des personnages. Alice et Bob désignent ainsi deux entités qui tentent de communiquer discrètement, alors qu’Eve, une autre entité, les écoute. Le chiffrement à clé publique permet à Alice de communiquer de façon sécurisée avec Bob même si Eve les écoute. Cela représente une notion non intuitive : comment Alice et Bob peuvent-ils communiquer de façon secrète même si Eve entend tout ? Depuis les années 1970, différentes méthode de chiffrement à clé publique, qui permettent de respecter ce principe, ont été mises au point. Toutes utilisent des objets mathématiques avec des structures algébriques particulières, et la sécurité de ces systèmes repose sur la difficulté à résoudre certains problèmes, les plus utilisés étant ceux de la factorisation et du logarithme discret. Bien que ces problèmes soient difficiles à résoudre pour les ordinateurs actuels, leur nature les rendrait vulnérables aux attaques d’éventuels ordinateurs quantiques. Dans ce contexte, tout ce qui fonctionne avec un chiffrement à clé publique, comme de nombreuses applications sur Internet, deviendrait vulnérable.

Le but principal des recherches de Vadim Lyubashevsky est de mettre au point des méthodes de chiffrement à clé publique qui soient suffisamment efficaces pour être implantées partout (sur des ordinateurs personnels, des cartes à puce…) et qui soient capables de résister aux attaques des ordinateurs quantiques. Une des approches prometteuses est celle de la cryptographie à base de réseaux Euclidiens. Plutôt que de se baser sur la difficulté de problèmes théoriques comme la factorisation ou le logarithme discret, cette nouvelle forme de cryptographie repose sur l’algèbre linéaire. Par exemple, bien que la résolution d’un problème d’équations linéaires soit simple, trouver une petite solution entière semble difficile même pour un ordinateur quantique.

Des approches similaires ont été employées depuis les années 1980, mais elles sont restées inefficaces. Durant les cinq dernières années cependant, les connaissances théoriques et pratiques dans ce domaine ont considérablement évolué. Suite aux travaux de Vadim Lyubashevsky, de ses collègues et de ses étudiants, les principes de base sont aujourd’hui bien établis et reposent sur des fondations solides. Par ailleurs, de nouveaux concepts ont émergé. Le plus notable est celui du chiffrement homomorphe, qui permet de calculer directement sur des données cryptées. Malheureusement, beaucoup de ces nouvelles constructions sont inefficaces en pratique, et davantage de travaux fondamentaux sont nécessaires pour parvenir à des systèmes utilisables. C’est l’axe principal de l’ERC de Vadim Lyubashevsky : construire les fondations qui permettront la construction de schémas cryptographiques qui soient résistants aux attaques quantiques.