Projet ANR-12-JS02-0004 – ROMAnTIC : L'aléatoire en cryptographie mathématique
Programme : JCJC - SIMI 2 - Science informatique et applications (JCJC SIMI 2) 2012
Année de financement : 2012
Coordinateur du projet : Monsieur Damien Vergnaud (Département d'Informatique de l'Ecole Normale Supérieure)
Partenaires : Département d'Informatique de l'École Normale Supérieure
Montant : 215268.0 euros
Date de début : 2012
Durée : 48 mois
Résumé : Depuis trente ans, la cryptographie a considérablement évolué et aujourd'hui tout le monde est susceptible d'en être un utilisateur direct ou indirect. La cryptographie moderne est désormais une discipline à la croisée des mathématiques, de l'informatique et de l'ingénierie. 
L'utilisation d'aléas est un élément clé en cryptographie. Des bits aléatoires sont nécessaires non seulement pour générer des clés, mais ils sont également souvent nécessaires dans l'exécution d'algorithmes cryptographiques. Les protocoles probabilistes permettent d'effectuer des tâches qui sont impossibles de façon déterministe, ils sont parfois plus rapides, plus compacts ou plus simples que les algorithmes déterministes.Les cryptographes supposent généralement que les utilisateurs ont accès à des aléas parfait, mais dans la pratique, cette hypothèse est souvent violée. 
Le but du projet de recherche ROMAnTIC (pour RandOmness in MathemaTIcal Cryptography, en anglais) est d'obtenir une meilleure compréhension de l'interaction entre l'aléa et la cryptographie et d'étudier la sécurité de protocoles cryptographiques nouveaux ou existants (au sens de la théorie de l'information ou calculatoire) et les hypothèses algorithmiques sous-jacentes. Il s'agit d'un projet de recherche fondamentale qui réunit des chercheurs universitaires en cryptographie théorique et un expert de l'Agence nationale de la sécurité des systèmes d'information (ANSSI). 
Généralement, les cryptographes ne considèrent pas le fait que la génération d'aléas est coûteuse et que les aléas devraient être considérés comme une ressource comme l'espace et le temps. Puisque l'aléa parfait ne semble pas physiquement réalisable, il est intéressant de déterminer si un aléa  imparfait est "suffisamment bon" pour certaines tâches cryptographiques et de concevoir des algorithmes robustes même lorsqu'ils sont utilisés avec des aléas imparfaits.
La puissance de l'aléatoire est un problème central dans la théorie de la complexité et en cryptographie que les cryptographes devraient certainement prendre en compte au moment de proposer de nouveaux schémas. Il existe des tâches cryptographiques pour lesquelles les seuls algorithmes efficaces connus sont probabilistes mais inversement, il est parfois possible rendre des algorithmes probabilistes plus efficaces en les rendant déterministes. Comme ces constructions sont susceptibles de nuire à la sécurité des schémas, il est d'un grand intérêt d'étudier les compromis efficacité/sécurité obtenus par l'utilisation d'aléas en cryptographie. 
Dans la pratique, les bits aléatoires dans les protocoles cryptographiques sont générées par un processus de génération pseudo-aléatoire. Dans ce cas, la sécurité du système dépend bien sûr de manière cruciale de la qualité des bits produits par le générateur. Malgré cela, de nombreux protocoles ne précisent pas quel générateur utiliser. Nous savons que les générateurs de nombres pseudo-aléatoires existent si et seulement si les fonctions à sens-unique existent et il existe des également constructions qui reposent sur diverses hypothèses algorithmiques, mais ces constructions sont généralement inefficaces et dans la pratique les concepteurs reposent sur des constructions "ad hoc". Il est donc intéressant de proposer des constructions plus efficaces, d'analyser la sécurité de ceux qui existent déjà et de certaines constructions cryptographiques utilisant des générateurs faibles. 
Le projet ROMAnTIC vise à entreprendre des recherches dans ces trois thèmes. L'approche adoptée sera à la fois théorique et pratique, puisque nous fournirons des résultats de sécurité dans un cadre mathématique (théorie de l'information ou calculatoire) avec pour objectif de concevoir des protocoles parmi les plus efficaces connus. Le projet fera notamment intervenir des structures mathématiques discrètes pour modéliser des problèmes de sécurité et une cryptanalyse algébrique et  une analyse mathématique de constructions cryptographiques.