Soutenance mémoire
Les dernières années ont vu se démocratiser les téléphones intelligents, dont les possibilités et les applications sont de plus en plus nombreuses et variées. En plus de fournir les services d’un téléphone classique, cette nouvelle génération de téléphones offre beaucoup plus de services, tels que la géolocalisation, la reconnaissance vocale ou encore l’accès internet. Il est désormais également possible d’ajouter des applications additionnelles pour couvrir tous les besoins. De nombreuses applications sont désormais basées sur la localisation de l’usager : la cartographie, la réalité augmentée ou les outils de rencontre. Cependant, ces applications sont pour l’instant limitées aux contextes où les usagers n’ont pas de motivation à falsifier leur position. Plus récemment, il est apparu évident que l’utilisation actuelle des téléphones peut poser de graves problèmes d’atteinte à la vie privée, tels que le traçage des usagers et le recueil de données personnelles.
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.
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.
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.
|
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
