Protocole de signature dans le cas d’un protocole de comparaison avec arbre binaire

Protocole de signature dans le cas d’un protocole de comparaison avec arbre binaire

INTRODUCTION

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.
L’objectif de ce mémoire est de permettre à un individu, que l’on nommera le prouveur, d’obtenir des preuves de sa localisation, authentifiées par les utilisateurs environnants, que l’on appellera témoins. Ces preuves seront bien sûr datées dans le temps. Il s’agira donc de preuves de localisation à un instant précis. Ces preuves seront ainsi générées par des témoins qui ne devraient pas avoir de motivation à mentir, contrairement au prouveur qui pourrait obtenir certains navantages à falsifier sa preuve de localisation.
Les preuves de localisation permettront à terme de développer une nouvelle génération d’applications.
Dans cette nouvelle vague d’applications, les utilisateurs auront une réelle motivation de falsifier leur position. L’article de Saroiu et Wolman (2009) propose quelques applications possibles : (1) le vote électronique où un électeur doit pouvoir prouver qu’il est résident d’une région depuis un certain nombre d’années, (2) le contrôle d’accès basé sur l’emplacement géographique (un utilisateur aurait accès à un service seulement s’il peut prouver qu’il se situe à un emplacement spécifique), (3) le contrôle de présence des étudiants à des activités académiques ou encore (4) lors de la cueillette d’information pour les enquêtes policières. C’est sur ce dernier exemple que nous nous concentrons particulièrement, bien que les autres problèmes soient équivalents.

REVUE DE LITTÉRATURE

Ce chapitre est dédié à la revue de littérature. Les différents outils cryptographiques qui sont utilisés dans la suite du mémoire y sont présentés. Les sujets abordés sont la sécurité sémantique, les chiffrements homomorphes, les transferts inconscients et les calculs multi-parties (principalement les protocoles de comparaison et de calcul de maximum). Dans le reste du mémoire, la notion d’aléatoire implique l’uniformité.

 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.

 Protocoles de calcul de somme

L’objectif de ces protocoles est de permettre à un groupe d’utilisateurs Pi (0 ≤ i ≤ k−1) possédant chacun une valeur privée xi de calculer conjointement la somme de leur valeur. La solution la plus évidente a été présentée par Clifton (2001) et est expliquée dans le protocole 2.7.
Seules k communications consécutives sont nécessaires dans ce protocole. En supposant que les données transmises sont chiffrées pour éviter les écoutes clandestines, deux opérations cryptographiques sont nécessaires pour chaque utilisateur. Malheureusement, cette approche possède un désavantage majeur : si Pi−1 et Pi+1 forment une collusion, ils peuvent déterminer la valeur de Pi.

PROTOCOLES DE COMPARAISONS APPLIQUÉS À UN ARBRE BINAIRE

L’objectif de ce chapitre est de proposer un protocole permettant au prouveur P d’obtenir la valeur maximale ET (xmax) détenue par les témoins Wi (1 ≤ i ≤ n) chiffrée avec la clé du juge T. Pour cela, nous chercherons à savoir lequel des témoinsWi possède la plus grande valeur xi, puis à permettre à P de récupérer cette valeur chiffrée avec la clé du juge. Il s’agit donc d’un protocole de comparaison à n individus avec une partie externe P qui doit recevoir le résultat.
Contrairement aux divers protocoles de calcul de maximum étudiés en revue de littérature, P construira un arbre binaire de comparaison avec les n témoins dans lequel ceux-ci seront éliminés jusqu’à ce qu’il n’en reste plus qu’un. L’avantage d’une telle méthode est évident : il n’est plus nécessaire de comparer l’ensemble des témoins deux à deux. Il y a donc à la fois un gain de temps et de communication. Cependant, pour réaliser cela, il est indispensable que P connaisse le résultat de certaines comparaisons.

PROTOCOLE DE CALCUL DE MAXIMUM BIT À BIT

Dans ce chapitre, nous avons pour but de permettre à P de découvrir la valeur maximale xmax détenue par les témoins Wi (1 ≤ i ≤ n). La méthode présentée est une solution alternative aux solutions du chapitre précédent, les objectifs étant sensiblement différents. En effet, nous considérons que P ne cherche plus à savoir quel est le témoin qui possède la plus grande valeur, mais qu’il cherche à connaître directement cette valeur. Par ailleurs, nous considérons que les témoins peuvent aussi découvrir aussi la valeur maximale, mais pas son possesseur.
Cette méthode se distingue des protocoles de calcul de maximum évoqués dans la revue de littérature par une complexité moins élevée au détriment d’une moins bonne sécurité face aux collusions.

CONCLUSION

Depuis quelques années, les fonctionnalités et les applications des téléphones s’accroissent très rapidement. Dans ce mémoire, nous avons présenté une nouvelle fonctionnalité permettant aux utilisateurs de téléphones intelligents d’obtenir des preuves de leur localisation à un instant donné. Ces preuves permettent à une nouvelle génération d’applications basées sur la localisation de voir le jour. La protection de la vie privée et l’anonymat étant devenus des contraintes incontournables, la méthode présentée a pour objectif primordial de protéger la vie privée des usagers. Ni les identités ni les positions précises des individus ne sont divulguées au cours des différents protocoles proposés.
La solution proposée nécessite que les téléphones des utilisateurs soient dotés d’antennes directionnelles, ce qui n’est pas le cas dans les technologies actuelles. De plus, nous supposions que les antennes directionnelles sont calibrées de manière à n’avoir que quatre quarts de plan possibles : nord-est, sud-est, sud-ouest et nord-ouest, ce qui est assez difficile à obtenir avec une bonne précision. En effet, les gyroscopes et boussoles dont sont équipés les téléphones ne sont, aujourd’hui, pas assez précis pour obtenir nos quatre quarts de plan de manière fiable.
Cependant, cette problématique nous a permis d’étudier plusieurs sous-problèmes, dont les applications possibles sont beaucoup plus vastes que les preuves de localisation seulement.

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