Description
Date depot: 1 janvier 1900
Titre: Étude de cryptosystèmes à clé publique basés sur les codes MDPC quasi-cycliques
Directeur de thèse:
Nicolas SENDRIER (Inria-Paris (ED-130))
Domaine scientifique: Sciences et technologies de l'information et de la communication
Thématique CNRS : Non defini
Resumé:
1. Contexte
Bien qu'il soit difficile de prévoir avec certitude si et quand
l'ordinateur quantique apparaîtra, il pourrait remettre en cause une
bonne partie des systèmes cryptographiques à clé publique utilisés
aujourd'hui, notamment ceux basés sur la théorie des nombres
(factorisation, courbes elliptiques, logarithme discret). L'algorithme
de Shor permettrait de casser ces systèmes en temps polynomial et
obligerait à reconcevoir un grand nombre d'applications
cryptographiques. Des menaces peuvent aussi provenir de progrès
algorithmiques, par exemple il a été récemment montré que le calcul du
logarithme discret dans des corps finis de petite caractéristique
pouvait se faire en temps quasi-polynomial. Au delà de ces seules
menaces, cela a été l'occasion pour la communauté cryptographique de
réaliser combien il est important de disposer d'une variété de
cryptosystèmes dont la sécurité reposerait sur d'autres hypothèses que
celles de la seule théorie des nombres.
L'étude des alternatives porte, à tort ou à raison, le nom de
« cryptographie post-quantique » et les cryptosystèmes basés sur les
codes en font partie, tout comme la cryptographie basée sur les
réseaux (lattice en anglais) ou la cryptographie multivariée.
La cryptographie basée sur les codes date de 1978, avec le système de
McEliece, dont la sécurité n'a toujours pas été significativement
menacée à ce jour. Un autre système de chiffrement similaire a été
proposé en 1986 par Niederreiter. Ces systèmes utilisent les codes de
Goppa binaires et leur mise en oeuvre est particulièrement simple et
efficace, gagnant un ordre de grandeur en complexité algorithmique par
rapport aux systèmes basés sur la théorie des nombres. Ces systèmes
ont néanmoins des défauts. Le premier de ces défauts est la taille de
la clé publique (plusieurs dizaines de kilo-octets). Une autre
faiblesse est l'absence de diversité pour le choix de la famille de
codes: les tentatives pour utiliser d'autres familles que les codes de
Goppa (codes de Reed-Solomon, codes concaténés, codes LDPC, ...) ont
souvent échoué à produire des systèmes sûrs.
Des techniques ont été proposées pour produire des clés publiques
quasi-cycliques ou quasi-dyadiques. Elles ont permis de réduire la
taille des clés de façon spectaculaire (linéaire en la taille de bloc
au lieu de quadratique) mais ont été considérablement affaiblies par
des attaques algébriques. Même si ces techniques ne sont pas
condamnées, loin de là, il semble que la forte structure algébrique de
ces familles de codes ne permette pas un gain de taille aussi
important qu'espéré tout en conservant une sécurité suffisante. Une
nouvelle série de travaux, faisant suite à, a permis d'aboutir à une
solution basée sur les codes MDPC (Moderate Density Parity Check)
quasi-cycliques. Ces codes, bien que quasi-cycliques, possèdent très
peu de structure algébrique, et sont invulnérables aux attaques
connues. Leur mise en oeuvre est très efficace et la taille de la clé
publique peut être réduite à quelques milliers de bits. Cette
proposition est récente mais semble d'un grand intérêt, elle possède
en effet le principal avantage des systèmes basés sur les codes, une
mise en oeuvre simple et efficace, et corrige le principal défaut avec
des clés publiques de petites tailles. De plus, la proximité des codes
MDPC avec les codes aléatoires les rend peu vulnérables aux attaques
algébriques, et permet même d'espérer une réduction de sécurité à des
problèmes difficiles de théorie des codes.
2. Objectifs
L'objectif est de promouvoir l'utilisation des cryptosystèmes basés
sur les codes en général. Nous nous intéresserons en priorité à une
implantation effective du système de chiffrement MDPC-McEliece.
Bien que les systèmes de type McEliece existent depuis plus de 30 ans,
leur ingénierie a été peu étudiée. Il existe une implantation
logicielle publique du système de McEliece. D'autres travaux, comme
ceux de Stefan Heyse
(http://www.emsec.rub.de/chair/_staff/stefan_heyse/) donnent une
indication intéressante, ces systèmes peuvent être mis en oeuvre, et
en particulier MDPC-McEliece, sur des processeurs embarqués de petites
tailles (8 ou 16 bits) et ont de bonnes propriétés en terme de
consommation d'énergie. D'une façon générale, ces travaux précurseurs,
relèvent de la preuve de concept.
Pour les codes MDPC, notre objectif est d'étudier leur ingénierie de
façon approfondie. Par exemple, en l'état actuel des choses,
l'algorithmique du décodage est efficace, mais ne fonctionne pas en
temps constant et échoue dans un petit nombre de cas. Les propriétés
sémantiques des systèmes basés sur les codes rendent obligatoires une
couche de sécurité sémantique sous peine d'affaiblir le système.
Ceci, ainsi que d'autres éléments qu'il conviendra peut-être de
découvrir, devra nous guider pour une étude générique de l'ingénierie
de ces systèmes. L'objectif ne sera pas seulement d'étudier une
application et une plateforme particulière, mais aussi d'expliq
Doctorant.e: Chaulet Julia