Projet ANR-13-JS02-0003 – CLE : Cryptography from Learning with Errors
Programme : JCJC - SIMI 2 - Science informatique et applications (JCJC SIMI 2) 2013
Année de financement : 2013
Coordinateur du projet : Monsieur Vadim LYUBASHEVSKY (Institut national de recherche en informatique et automatique)
Partenaires : Inria Centre Paris - Rocquencourt
Montant : 196302.0 euros
Date de début : 2013
Durée : 48 mois
Résumé : L'application du problème "Learning With Errors" (LWE) à la construction de
nouveaux cryptosystèmes est un des développements récents les plus
passionnants en cryptographie. Le problème LWE est de résoudre un système d'équations
linéaires dont les sorties ont été perturbées par de petites erreurs. 
Ces dernières années, les chercheurs ont montré que la sécurité de presque 
toutes les primitives cryptographiques que l'on peut imaginer, se
réduit à la difficulté de ce problème. Des systèmes aux très fortes propriétés
 sont récemment apparus (par exemple les systèmes complètement
homomorphes), mais leurs implémentations restent pour l'instant inefficaces.
L'objectif principal de ce projet est d'étudier les implications pratiques
du problème LWE et ses variantes. Nous étudierons tout particulièrement
la construction de primitives essentielles dont l'usage est répandu dans 
le monde réel. Dans la dernière partie du projet, notre but est de proposer et de normaliser 
plusieurs schémas à clé publique et à clé secrète, qui
présenteront des avantages spécifiques par rapport aux
schémas actuels.
Cryptographie à clé publique. 
Les signatures numériques représentent de nos jours l'application
majoritaire des schémas à clé publique. Malheureusement,
presque tous les schémas efficaces reposent sur des problèmes de
théorie des nombres, comme la factorisation ou le logarithme discret,
dont la sécurité s'effondrerait avec l'arrivée d'ordinateurs
quantiques. Au contraire, le problème LWE resterait exponentiel
même pour des algorithmes quantiques. Une grande ligne de recherche vise
à développer des signatures digitales basées sur LWE, et l'un des objectifs du
projet CLÉ est d'aboutir à une instanciation concrète et standardisée qui
aura la sécurité requise dans le monde quantique futur.
Cryptographie symétrique.
La cryptographie symétrique étudie des constructions comme les
générateurs de nombres pseudo-aléatoires, les systèmes d'authentification et de
chiffrement à clé secrète. Pour des raisons d'efficacité, ces
primitives n'utilisent pas les mêmes techniques que leurs
homologues à clés publiques. Dans ce projet, nous souhaitons montrer que
certains scénarios à clé publique peuvent se révéler très utile.
Par exemple, pour s'authentifier, un prouveur peut convaincre le vérificateur 
de son identité en chiffrant un challenge avec AES. Le problème est que
cette construction est très vulnérable aux attaques par canaux auxiliaires.
Pour contrer de telles attaques, le prouveur devrait changer sa
clé secrète après chaque invocation. À l'heure actuelle, les solutions pour masquer la clé 
d'AES ralentissent le système de plusieurs ordres de grandeur. 
Les schémas d'authentification récents construits sur l'hypothèse LWE 
(ou ses variantes) sont légèrement plus lents qu'AES, mais leur structure
algébrique se prête mieux au masquage de la clé. 
De plus, nous comptons étudier l'influence du choix de la représentation des 
corps finis sur l'efficacité des systèmes utilisant LWE. Ainsi, les systèmes masqués à 
l'aide LWE pourraient s'avérer plus efficace en pratique que ceux qui utilisent AES. 
Par delà les problèmes abordés dans ce projet, les techniques qui seront développées 
ouvriront de nouvelles pistes pour la recherche cryptographique. 
Si nous commencerons par chercher des moyens d'appliquer le problème LWE, 
nous étendrons cette approche à toutes les pistes possibles, 
utilisant des techniques de cryptographie symétrique ou publique. 
Il existe actuellement très peu de collaborations 
entre les groupes travaillant sur les aspects pratiques de la cryptographie 
symétrique et publique. Nous espérons que la construction d'un groupe 
interdisciplinaire étudiant les problématiques communes aux deux
domaines, verront naître un terrain d'entente et une collaboration 
étroite dans avenir prochain.