Soutenance mémoire
Notions de sécurité sémantique
Les notions de sécurité sémantiques définies ici sont extraites de Goldreich (2004). Trois niveaux de sécurité sont étudiés : l’indiscernabilité avec des textes clairs choisis (indistinguishability under chosen-plaintext attack IND-CPA) et les deux variantes de l’indiscernabilité avec des textes chiffrés choisis (indistinguishability under chosen-cyphertext attack IND-CCA1 et IND-CCA2). Le niveau de sécurité IND-CPA est défini de la manière suivante : il est difficile pour un adversaire d’extraire des informations à partir de messages chiffrés, même en connaissant les chiffrements de messages qu’il a lui-même choisis. En d’autres termes, l’adversaire demande le chiffrement d’autant de messages qu’il désire dans une première phase, puis, dans une seconde phase, choisit arbitrairement deux messages m0 et m1. Il reçoit ensuite le chiffrement E(mx) d’un seul de ces deux messages choisi aléatoirement et doit deviner lequel des deux messages a été chiffré. Le niveau de sécurité IND-CPA est atteint si et seulement si la probabilité de succès de l’adversaire, dont la puissance de calcul est bornée polynomialement, est proche de 1/2. Dans le niveau de sécurité IND-CCA1, l’adversaire est autorisé à demander le déchiffrement d’autant de cryptogrammes qu’il le désire pendant la première phase. Dans le niveau de sécurité IND-CCA2, il peut demander des déchiffrements de cryptogrammes même au cours de la seconde phase, après avoir reçu E(mx). Les chiffrés doivent toutefois évidemment être différents du défi. Il s’agit du niveau de sécurité le plus élevé. Pour respecter la sécurité sémantique, un système de chiffrement à clé publique doit être probabiliste (condition nécessaire). Un système de chiffrement est dit probabiliste si pour un message donné, il existe plusieurs chiffrements possibles de ce message. Pour un système de chiffrement non-probabiliste, il suffit en effet à l’adversaire de chiffrer lui-même m0 et m1 avec la clé publique s’il s’agit de cryptographie asymétrique, ou qu’il ait déjà demandé le chiffrement de m0 ou m1 s’il s’agit de cryptographie symétrique. L’un des deux cryptogrammes obtenus E(m0) ou E(m1) sera nécessairement identique à E(mx). Un système de chiffrement non-probabiliste n’atteint donc pas le niveau IND-CPA.
Chiffrement homomorphe
Le chiffrement homomorphe est un type particulier de chiffrement qui permet de réaliser certaines opérations (telles que l’addition ou la multiplication) sur des données chiffrées, puis de retrouver le résultat de ces opérations après le déchiffrement. La plupart des systèmes de chiffrement ne permettent de réaliser qu’une seule opération : soit l’addition [Paillier (1999)] ou soit la multiplication [Rivest et al. (1978)]. Plus récemment, Gentry et al. (2009) a proposé un système de chiffrement homomorphe complet (fully homomorphic encryption) permettant ces deux opérations sans aucune contrainte. Toutefois, celui-ci est peu performant et de nombreuses variantes sont apparues depuis (par exemple, Gentry et Halevi (2011) et Coron et al. (2011)). Malheureusement, ces variantes ne sont pas encore suffisamment efficaces pour développer des solutions simples. Les systèmes de chiffrement homomorphe complet ne seront pas étudiés dans ce mémoire. Par définition, un système de chiffrement homomorphe ne peut pas atteindre le niveau de sécurité IND-CCA2. En effet, pour un chiffrement homomorphe additif, l’adversaire peut demander le déchiffrement de E(mx − m0) (respectivement E(mx · m0 −1 pour un système multiplicatif). Si le résultat est 0 (respectivement 1), alors mx= m0, sinon mx = m1. Les travaux de Fontaine et Galand (2007) prouvent d’ailleurs que le niveau de sécurité maximal que peut atteindre un système de chiffrement homomorphe est IND-CPA.
Chiffrement RSA
Le chiffrement RSA [Rivest et al. (1978)] est l’un des exemples les plus simples et les plus courants de système de chiffrement homomorphe multiplicatif. Ce chiffrement est défini comme suit :
• Soit p,q ∈ Z∗ deux grands nombres premiers privés
• Soit N = pq le produit rendu public
• Soit l’exposant public e ∈ Z∗N tel que pgcd(e,φ(N)) = 1 où φ(N)=(p − 1)(q − 1) est l’indicatrice d’Euler.
• Soit l’exposant privé d ∈ Z∗N tel que ed ≡ 1 (mod φ(N)). Cet exposant est donc l’inverse de e modulo φ(N) et peut être calculé grâce à l’algorithme d’Euclide étendu. La fonction de chiffrement EN,e(·) d’un message m ∈ Z∗ n est définie de la façon suivante :
EN,e : Z∗N → Z∗N
EN,e(m) = me mod N
Transfert inconscient
Dans le transfert inconscient 1-parmi-2 (1-out-of-2 oblivious tranfert), une des parties, Alice, possède deux secrets M0 et M1. L’autre partie, Bob, souhaite récupérer une et une seule de ces données Mi de son choix en s’assurant qu’Alice ignore la valeur de i. De son côté, Alice s’assure que Bob ne puisse pas connaître plus d’un seul secret. Les données d’Alice sont donc protégées tout autant que le choix de Bob. Une des approches les plus simples pour le transfert inconscient 1-parmi-2 a été donnée par Even et al. (1985) et peut être résumée par les quelques étapes décrites dans le protocole 2.1. On supposera qu’Alice possède deux secrets M0 et M1 et des fonctions de chiffrement et déchiffrement EA(·) et DA(·) respectivement. Les secrets et les clés de chiffrement doivent être de la même longueur. L’opérateur ⊕ dénote l’addition bit à bit modulo 2.
Calculs multi-parties
Les calculs multi-parties sécuritaires sont une branche de la cryptographie permettant à plusieurs parties de calculer coopérativement une fonction publique sans dévoiler les paramètres privés. Le premier protocole à s’inscrire dans cette branche est celui de Yao (1982) qui cherche à résoudre le problème des millionnaires permettant à deux individus de comparer leur fortune respective. Plus tard, les travaux de Goldreich (1998) et de Goldwasser (1997) ont motivé les chercheurs à travailler sur des problèmes multi-parties précis plutôt que sur des problèmes généraux afin d’en améliorer l’efficacité, le but étant de développer des protocoles performants.
Les notions de sécurité d’un protocole de calcul multi-partie ci-dessous sont extraites du livre de Hazay et Lindell (2010). Soit deux participants Alice et Bob dont les valeurs privées respectives sont notées a et b. Alice désire calculer f1(a,b) et Bob souhaite déterminer f2(a,b). Un protocole de calcul multi-partie peut être noté sous la forme de la fonction suivante
f : (a,b) → (f1(a,b), f2(a,b))
Un protocole est dit sécurisé si ce qui peut être calculé par une partie grâce au protocole peut aussi être calculé à partir des valeurs privées et du résultat de cette partie seulement. Ainsi, la valeur b de Bob est protégée s’il existe un simulateur qui puisse générer équiprobablement le même résultat f1(a,b) quelle que soit la valeur de b (tel que le résultat recherché ne soit bien sûr pas modifié). Le protocole ne permet donc pas à un adversaire d’un apprendre plus qu’il ne sait déjà sur la valeur des participants.
Problème de recherche du maximum
Ce problème tend à généraliser le problème des millionnaires à n individus. Chacun de ces individus Pi possède une valeur xi et on cherche à savoir qui possède max{xi | 1 ≤ i ≤ n−1} tout en protégeant les valeurs. Certaines approches ont un but sensiblement différent : elles visent à diffuser la valeur maximale en gardant secrète l’identité de son possesseur. Deux approches existent. La première consiste à utiliser un protocole de comparaison classique à deux utilisateurs et à le répéter entre les différents utilisateurs jusqu’à déterminer qui possède la valeur maximale. L’une des difficultés de cette approche est de ne pas divulguer le résultat des comparaisons entre deux utilisateurs. La solution proposée par Zhang et Makedon (2005) parvient à surmonter cela grâce à un système de vecteurs qui camoufle les résultats des comparaisons jusqu’au résultat final. Cette solution est présentée dans le protocole 2.10. Elle nécessite l’utilisation d’un protocole de comparaison dit asymétrique, ce qui signifie qu’une seule des deux parties connaît le résultat de la comparaison. Le vecteur π(T’ i ) généré par P0 à l’étape 4 représente le vecteur Ti que devrait avoir Pi s’il avait gagné toutes les comparaisons. Par conséquent, si π(T’ i ) = Ti, xi est la valeur maximale. À la fin de ce protocole, la valeur maximale est connue de tous, mais son propriétaire reste inconnu. Cependant, cela requiert n2 −n comparaisons avant d’obtenir le résultat, et toutes les valeurs doivent impérativement être différentes deux à deux. La complexité de ce protocole dépend des protocoles de comparaison utilisés aux étapes 3 et 4, ainsi que du protocole de somme des étapes 5 et 6. L’étape la plus contraignante est l’étape 3 pour laquelle il y a (n2−n)C communications, où C est le nombre de communications du protocole de comparaison utilisé. C étant généralement constant, quelque soit le protocole, la complexité communicationnelle de cette solution est de l’ordre de O(n2).
La seconde approche cherche à comparer l’ensemble des valeurs bit à bit selon quelques règles simples exposées dans le protocole 2.11. On notera xi, j le j eme ` bit de poids fort de la valeur xi et l le nombre de bits des valeurs. À l’aide du protocole 2.11, on obtient ainsi la valeur maximale. Cependant, les premiers bits significatifs de chacune des valeurs sont révélés. Il s’agit donc de trouver une méthode permettant de dissimuler l’identité du possesseur du maximum, et de protéger entièrement les autres valeurs.
La méthode présentée par Hasan et al. (2013) résout ce problème au moyen d’un calcul de somme. On supposera que P0 est l’utilisateur chargé d’obtenir et de diffuser le maximum. Au lieu de lui transférer la valeur de chaque xi, j, les autres utilisateurs lui envoient la somme ∑i xi, j grâce à un des protocoles déjà présentés. Cependant, P0 peut encore déterminer combien de personnes possèdent xi, j = 1. L’auteur propose alors de remplacer les 1 par des valeurs aléatoires non nulles. P0 obtiendra donc un nombre aléatoire s’il existe i tel que xi, j = 1 et une somme nulle sinon.
|
Table des matières
INTRODUCTION
CHAPITRE 1 PROBLÉMATIQUE
CHAPITRE 2 REVUE DE LITTÉRATURE
2.1 Notions de sécurité sémantique
2.2 Chiffrement homomorphe
2.2.1 Chiffrement RSA
2.2.2 Système de Paillier
2.3 Transfert inconscient
2.4 Calculs multi-parties
2.4.1 Problème des millionnaires de Yao
2.4.2 Protocoles de calcul de somme
2.4.3 Problème de recherche du maximum
2.5 Conclusion sur les calculs multi-parties
CHAPITRE 3 PROTOCOLES DE COMPARAISONS APPLIQUÉS À UN ARBRE BINAIRE
3.1 Adaptation de Blake et Kolesnikov (2004)
3.1.1 Protocole
3.1.1.1 Exactitude
3.1.1.2 Preuves de sécurité
3.1.2 Protocole corrigé
3.1.2.1 Exactitude
3.1.2.2 Preuves de sécurité
3.1.3 Protocole final
3.1.3.1 Exactitude
3.1.3.2 Preuves de sécurité
3.1.3.3 Analyse de la complexité
3.1.4 Généralisation à n individus
3.1.4.1 Protocole modifié
3.1.4.2 Exactitude
3.1.4.3 Preuves de sécurité
3.1.4.4 Analyse de la complexité
3.1.4.5 Divulgation d’information
3.2 Adaptation de Lin et Tzeng (2005)
3.2.1 Protocole
3.2.1.1 Exactitude
3.2.1.2 Preuves de sécurité
3.2.1.3 Analyse de la complexité
3.2.2 Généralisation à n individus
3.2.2.1 Protocole modifié
3.2.2.2 Analyse de la complexité
3.3 Protocole de comparaison optimisé
3.3.1 Protocole
3.3.1.1 Exactitude
3.3.1.2 Preuves de sécurité
3.3.1.3 Entropie
3.3.1.4 Analyse de la complexité
3.3.2 Généralisation à n individus
3.3.2.1 Protocole modifié
3.3.2.2 Analyse de la complexité
3.4 Transfert du maximum
3.4.1 Protocole
3.4.2 Exactitude
3.4.3 Preuves de sécurité
3.4.4 Analyse de la complexité
3.5 Comparaison des protocoles et conclusion
CHAPITRE 4 PROTOCOLE DE CALCUL DE MAXIMUM BIT À BIT
4.1 Signatures de groupe
4.2 Initialisation
4.3 Protocole de calcul de maximum
4.3.1 Exactitude
4.3.2 Preuves de sécurité
4.3.3 Choix du témoin de chiffrement
4.3.4 Analyse de la complexité
4.3.5 Conclusion
CHAPITRE 5 GÉNÉRATION DES PREUVES DE LOCALISATION
5.1 Protocole de signature dans le cas d’un protocole de comparaison avec arbre binaire
5.1.1 Preuves de sécurité
5.1.2 Analyse de la complexité
5.1.3 Analyse des preuves
5.2 Protocole de signature dans le cas d’un protocole de calcul de maximum bit à bit
5.2.1 Preuves de sécurité
5.2.2 Analyse de la complexité
5.2.3 Analyse des preuves
5.3 Construction du rectangle
5.4 Conclusion
CONCLUSION
Télécharger le rapport complet
