Introduction à la cryptologie
La cryptologie est une science au moins aussi vieille que les arts militaires. La cryptologie est définie comme étant la science du secret. Elle est constituée de deux composante complémentaires : la cryptographie et la cryptanalyse.
La principale mission de la cryptographie est de garantir la sécurité des communications c’est à dire permettre à des entités qui ne se font pas confiance en général de pouvoir communiquer en toute sécurité en présence de potentiels adversaires.
Il existe 5 services fondamentaux de sécurité :confidentialité, authentification, intégrité, non répudiation et disponibilité. La crytographie assure les 4 premiers services .
Confidentialité : garantir le secret des données (elle est assurée par les algorithmes de chiffrement); Authentification : garantir qu’une entité est celle qu’elle prétend être (elle est assurée par les protocoles cryptographiques);
Intégrité : garantir la non modification des données (elle est assurée par les fonctions de hachages); Non-répudiation : garantir qu’une transaction ne peut pas être niée (elle est assurée par les signatures numériques).
Quelques notions de sécurité
Les objectifs généraux de sécurité des systèmes de chiffrement asymétrique sont : ”Incassabilité” : Il doit être calculatoirement très difficile de déduire la clé secrète de la clé publique. Fonction à sens unique : La fonction de chiffrement doit être à sens unique, donc on doit pas pouvoir déduire un clair de son chiffré(Diffie-Hellman 1976).
Indistinguabilité : Connaissant le chiffré c d’un clair m on ne doit pas pouvoir déduire un seul bit d’information de m (d’une façon meilleure qu’un choix au hasard) (Introduit par Goldwasser et Micali 1984).
Non-malléabilité : (absence de corrélation) Il doit être impossible de transformer un chiffré c1 d’un clair m1 en un chiffré c2 d’un clair m2 de sorte que 40 m1 et m2 soient liés avec une probabilité meilleur que la probabilité uniforme (Dolev, Dwork, Naor 1991).
Systèmes de chiffrement complétement homomorphes(FHE)
Un système de chiffrement est dit complétement homomorphe s’il permet d’évaluer un nombre arbitraire d’additions et de multiplications c’est à dire permettre d’évaluer n’importe quel algorithme sur les données chiffrées.
L’application du chiffrement complètement homomorphe constitue une brique importante dans la sécurité du cloud. Le premier système de chiffrement complètement homomorphe a été proposé en 2009 par l’américain Craig Gentry. Ce système utilise des idéaux d’anneaux de polynômes et sa sécurité repose sur les réseaux d’idéaux.
En quelques mots, le schéma de Gentry chiffre des messages en leur ajoutant du bruit. Les opérations homomorphes sont effectuées impactant également ce bruit.
Lorsque le bruit devient important, Gentry applique une procédure dite de ”Bootstrap” qui permet de réduire ce bruit à un niveau acceptable. Concrètement, cette procédure consiste à évaluer la fonction de déchiffrement de manière homomorphe.
En d’autre termes Gentry construit d’abord un chiffrement pseudo homomorphe puis le transforme en un chiffrement complètement homomorphe en appliquant la procédure de ”Bootstrap”. Gentry a montré que tout système de chiffrement pseudo homomorphe peut (sous certaines conditions) être transformé en un système de chiffrement complètement homomorphe avec un bootstraping.
Systèmes de chiffrement pseudo homomorphes(SHE)
Un système de chiffrement est dit pseudo homomorphe s’il permet d’évaluer un nombre limité d’additions et de multiplications. La recherche d’un chiffrement permettant d’évaluer sur des clairs à la fois des additions et des multiplications a été pendant très longtemps une question ouverte. L’existence d’un tel chiffrement a été conjecturé pour la première fois en 1978 par Rivest Adleman et Dertouzos sous l’appellation de privacy homomorphism.
Depuis lors peu d’avancées ont été notée. En 1998, Hoffstein, Pipher et Silverman publient leur cryptosystème ”NTRU” basé sur les réseaux euclidiens, et permettant d’évaluer à la fois des additions et des multiplications sur les données chiffrées.
Cependant, la taille des chiffrés augmente exponentiellement en la profondeur du circuit à évaluer. Plus récemment, tout une série de résultats sur les réseaux eu-46 clidiens ont permis de définir des nouveaux schémas permettant de réaliser un nombre plus ou moins arbitraire d’additions et de multiplications sur les clairs.
Le chiffrement Diophantine Approximation Encrypt (DA-Encrypt)
Le chiffrement Diophantine Approximation Encrypt (DA-Encrypt) est un nouveau schéma de chiffrement homomorphe bas´e sur l’approximation diophantienne sur un espace non archimédien. Il a été publié en 2015 par Jeff Hoffstein, Jill Pipher, John M. Schank, Joseph H. Silverman, William Whyte et Zhenfei Zhang. Ce schéma est en quelque sorte l’inverse des systèmes de chiffrement basés sur les réseaux d’idéaux principaux. Le principe du chiffrement asymétrique basé sur ces derniers est simple : la clé publique est une mauvaise base d’un réseau idéal principal et la clé privée est une bonne base (le générateur) du réseau idéal principal. Il faut noter qu’il est facile à partir d’une bonne base de générer une mauvaise mais il est difficile de faire l’inverse. Dans ce schéma on utilise une bonne base (avec un peu de bruits injecté) pour générer les cryptogrammes, tandis que la clé secrète est le réseau lui-même (sous la forme d’une mauvaise base). Retrouver une base sans bruit à partir d’une base bruyante peut être vu comme une analogie au problème ”Learning With Errors” sur un réseau idéal principal. Les cryptogrammes sont des points à proximité d’un réseau idéal principal inconnu. La distance entre un cryptogramme au réseau est un message bruité. Les auteurs de ce système conjecturent que même si un attaquant est en mesure de résoudre le problème le plus court vecteur dans un réseau idéal principal, il ne sera pas en mesure de briser leur système, parce que leur réseau est secret. Cela permet à ce système de fonctionner sur des réseaux de plus petites dimensions. Ce système de chiffrement a deux versions (symétrique et asymétrique).
Table des matières
Introduction
I Préliminaires
1 Groupes et anneaux
1.1 Groupes
1.1.1 Sous-groupe discret de Rn
1.2 Anneaux
1.2.1 idéal
1.3 Résultant de deux polynômes
1.4 Polynômes d’interpolation de Lagrange
2 Les réseaux euclidiens
2.1 Principales définitions sur les réseaux
2.1.1 Réseaux euclidiens
2.1.2 Réseaux idéaux
2.1.3 Forme normal d’Hermite
2.1.4 Orthogonalisation de Gram-Schmidt
2.2 Quelques invariants d’un réseau
2.2.1 Déterminant d’un réseau
2.2.2 Les minimas successifs
2.3 Théorèmes de Minkowski et invariant d’Hermite
2.4 Approximation diophantienne et réseau
2.4.1 Approximation diophantienne dans R
2.4.2 Approximation simultanée de réels par des rationnels
2.5 Rappels de complexité
2.5.1 Quelques définitions
2.5.2 Classes de complexité
2.5.3 Réduction entre problèmes
2.6 Quelques problèmes difficiles
2.6.1 The Approximate GCD problem (A-GCD)
2.6.2 Problèmes sur les réseaux
2.6.3 The Learning With Errors Problem (LWE)
3 état de l’art des systèmes de chiffrement homomorphes
3.1 Introduction à la cryptologie
3.1.1 Quelques définitions et remarques
3.1.2 Quelques notions de sécurité
3.2 Chiffrements homomorphes
3.2.1 systèmes de chiffrement partiellement homomorphes (PHE)
3.2.2 systèmes de chiffrement pseudo homomorphes(SHE)
3.2.3 systèmes de chiffrement complètement homomorphes(FHE)
3.2.4 Sécurité
II Le chiffrement Diophantine Approximation Encrypt (DA-Encrypt)
4 Description du système
4.1 La version systémique de DA-Encrypt
4.1.1 algorithme
4.1.2 Exactitude du déchiffrement
4.1.3 Evaluation homomorphique
4.1.4 sécurité de DAE SY M
4.2 La version asymétrique de DA-Encrypt
4.2.1 Algorithme
4.2.2 Exactitude du déchiffrement
4.2.3 sécurité de DAE-ASY
4.3 Technique de génération de clefs
4.3.1 Génération d’un réseau idéal principal
4.3.2 Calcul du réseau final
4.3.3 Analyse de sécurité
III Applications
5 Exemples d’applications
5.1 Protocole de retrait d’informations privé ou PIR(Private Information Retrieval)
5.1.1 contexte
5.2 Le vote électronique
5.3 Application numérique
6 Implémentation
6.1 Représentation des données
6.2 Quelques fonctions utiles
6.3 Calcul sur les polynômes
6.4 Génération de clefs
6.5 Chiffrement et déchiffrement
6.6 Application
Conclusion
