Le Graal cryptographique peut-il être atteint ?

Les protocoles cryptographiques les plus avancés de ces dernières années reposent sur une nouvelle piste d'exploration, les applications multilinéaires, qui pourraient à long terme être employées de multiples façons dans la vie quotidienne. Mais une grande proportion des travaux sur cette piste de recherche viennent d'être rendus caducs suite à l'article de Damien Stehlé du Laboratoire d'informatique du parallélisme (LIP, CNRS/Inria/ENS de Lyon/Université de Lyon 1) et de ses collègues de la Seoul National University, qui ont "cassé" une des deux propositions d'applications multilinéaires faites jusque-là. En récompense de ce résultat, ils ont obtenu en avril le prix du meilleur article à la conférence Eurocrypt 2015, conférence de premier plan en cryptographie.

La cryptographie vise à sécuriser les données et la transmission de ces données. On se repose pour cela sur des protocoles que l'on espère sûrs, des plus simples comme le chiffrement symétrique (j'utilise une clé pour chiffrer, mon correspondant doit avoir cette même clé pour déchiffrer), jusqu'à des protocoles plus avancés comme le vote électronique qui mettent en jeu des fonctionnalités et des garanties de sécurité beaucoup plus complexes.

Un outil central pour construire des protocoles avancés s'appelle les applications multilinéaires cryptographiques. Beaucoup de chercheurs tentent d'en élaborer car les utilisations seraient nombreuses. Cela fournirait un chiffrement qui permet d'extraire n'importe quelle fonction pré-établie du message, à l'aide d'une clé qui ne donne accès qu'à la partie souhaitée des informations. Par exemple, un service de messagerie veut protéger la vie privée de ses utilisateurs, mais est dans le même temps pressé par les services secrets de lui donner accès à l'ensemble des mails en sa possession. Ce service de messagerie pourrait alors décider de donner accès à des chiffrés des mails et de fournir aux services secrets une clé ne permettant que de détecter certains mots définis comme suspects (tout en préservant la confidentialité des utilisateurs non visés). Autre exemple: cet outil cryptographique devrait permettre d'effectuer des statistiques sur des données médicales en préservant la confidentialité des patients.

Les fonctionnalités que ces applications multilinéaires permettent ont été étudiées dès 2003, mais c'est seulement en 2013 que deux propositions d'applications multilinéaires voient le jour, grâce à une équipe américaine et une autre française. Ce sujet d'études a été particulièrement intense dans la communauté depuis deux ans, avec de nombreuses constructions cryptographiques exploitant ces nouveaux objets. L'article “Cryptanalysis of the Multilinear Map over the Integers” de Jung Hee Cheon, Kyoohyung Han, Changmin Lee, Hansol Ryu (Seoul National University) et Damien Stehlé (LIP), montre que les données qui étaient censées être protégées dans l'application mutilinéaire de l'équipe française sont en fait facilement accessibles. Les auteurs ont décrit une idée qui disqualifie ainsi une douzaine d'applications qui reposaient spécifiquement sur cette construction. Ce travail a été effectué dans le cadre de l'ERC Starting Grant LattAC portée par Damien Stehlé.

Plus récemment, des chercheurs chinois ont quant à eux cassé l'application multilinéaire de l'équipe américaine. Une proposition de réparation de l'application multilinéaire cassée par Damien Stehlé et ses collègues a été publiée, mais il est trop tôt pour être certain de sa sécurité. Le Graal cryptographique est difficile à atteindre !