L'Agence nationale de la recherche Des projets pour la science

Translate this page in english

JCJC - SIMI 2 - Science informatique et applications (JCJC SIMI 2) 2013
Projet CLE

Cryptography from Learning with Errors

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.

Partenaires

Inria Paris - Rocquencourt Institut national de recherche en informatique et automatique

Aide de l'ANR 196 302 euros
Début et durée du projet scientifique octobre 2013 - 48 mois

 

Programme ANR : JCJC - SIMI 2 - Science informatique et applications (JCJC SIMI 2) 2013

Référence projet : ANR-13-JS02-0003

Coordinateur du projet :
Monsieur Vadim LYUBASHEVSKY (Institut national de recherche en informatique et automatique)

 

Revenir à la page précédente

 

L'auteur de ce résumé est le coordinateur du projet, qui est responsable du contenu de ce résumé. L'ANR décline par conséquent toute responsabilité quant à son contenu.