Fonctions de bases

Dans ce mémoire, nous utilisons un ensemble de fonctions classiques en cryptographie dont nous rappelons ici les principales définitions.

Notions de complexité

Tout d’abord, nous donnons quelques bases de la complexité : les notions d’algorithme polynomial, de fonction négligeable et de probabilité négligeable.
Le terme d’algorithme efficace correspond à une application qui peut être évaluée en un temps jugé raisonnable en pratique. De façon formelle, nous parlons d’algorithme polynomial défini comme suit.
Définition 8 (Algorithme polynomial). Un algorithme A est dit polynomial ou s’exécutant en temps polynomial s’il existe un polynôme p tel que, étant donné une entrée x ∈ {0,1} ∗ , le temps d’exécution est borné par p(| x |) où | x | est la longueur de l’entrée x . Sauf mention contraire, un adversaire, contre un schéma donné, correspond à un algorithme s’exécutant en temps polynomial. En outre, la notion de fonction négligeable est primordiale. Définition 9 (Fonction négligeable). Une fonction ν : N → R + est dite négligeable si, pour tout entier positif c , il existe un entier k c tel que.

Sécurité prouvée

Assurer la sécurité des protocoles cryptographiques proposés est aujourd’hui essentielle. Cependant, il n’est pas possible d’obtenir à la fois un schéma efficace et résistant à tout adversaire quelque soit la puissance de ce dernier. Par exemple, le chiffrement dit “parfait” de Vernam, aussi appelé “masque jetable”, est inadapté aux cas pratiques puis que la clé utilisée doit être au moins aussi longue que le message à chiffrer et ne peut pas être réutilisée. Nous nous appuyons donc sur une sécurité dite calculatoire qui est basée sur la difficulté de résoudre un problème considéré comme difficile. En d’autres termes, si un attaquant est en mesure de mettre en défaut la sécurité du schéma, c’est qu’il est également à même de résoudre un problème pourtant jugé difficile. Ces problèmes difficiles vont être utilisés pour construire des preuves de la sécurité de certaines propriétés du schéma.
Nous présentons l’ensemble des problèmes difficiles considérés dans ce mémoire. Ensuite, nous détaillons le fonctionnement des différents types et modèles de preuves.

Problèmes difficiles

De façon informelle, un problème est considéré comme difficile lorsque sa résolution est calculatoirement difficile. Autrement dit, pour un problème donné, la probabilité de succès de l’adversaire est négligeable. Chaque problème énoncé ici est associé à une hypothèse qui le suppose difficile. Nous évaluons alors la sécurité des schémas sous une hypothèse particulière. Nous distinguons ici trois catégories de problèmes/hypothèses difficiles

Types de preuves et modèles de sécurité

Pour attester de la robustesse d’un schéma, sa sécurité doit donc être prouvée. Pour cela, il est nécessaire de montrer qu’il est difficile, au sens calculatoire, de mettre en défaut sa sécurité. Nous utilisons alors des preuves de sécurité réalisées dans un modèle particulier.

Types de preuves – sécurité par réduction

Nous présentons ici trois types de preuves différentes. Derrière chacune de ces méthodes, nous retrouvons l’idée de sécurité dite réductionniste. Preuves standard, par réduction. Dès 1984, GOLDWASSER et MICALI [GM84] introduisent les bases de la sécurité prouvée réductionniste. Ces preuves par réduction reposent sur l’idée que si un adversaire parvient à casser la sécurité du schéma alors il est parvenu à résoudre un problème considéré comme difficile – ou à casser la propriété d’un autre schéma lui-même prouvé sûr. Pour formaliser cela, nous construisons un adversaire A contre une expérience Exp p A propre à une propriété p. De plus, un challenger C est, quant à lui, construit contre le problème difficile. Pour modéliser les capacités de l’adversaire, nous lui donnons éventuellement accès à un certains nombres d’oracles. Indirectement, l’adversaire est utilisé pour casser le problème difficile – en ajoutant une interface entre A et C . Ses réponses contre l’expérience Exp p A sont utilisés par le challenger C pour casser le problème difficile. Bien sûr, casser le problème difficile n’est possible qu’avec une probabilité négligeable. Cela nous permet d’affirmer que la probabilité de succès de l’adversaire est négligeable également et donc que le schéma est sûr. Nous parlerons également d’avantage négligeable de l’adversaire. Cela correspond la probabilité de succès relative à l’expérience Exp p A considérée.
Preuves par jeux. Une autre méthode pour réaliser des preuves par réduction consiste à utiliser une suite d’étapes appelée séquence de jeux [BG90, KR96, BR04]. Formalisée en 2004 par SHOUP [Sho04], cette technique consiste tout d’abord à décrire formellement l’attaque réalisée par l’adversaire, sous la forme d’une expérience. Cette description est alors appelée jeu 0 et est associée à l’évènement “S 0 : l’adversaire gagne”. Ensuite, une séquence de jeux est définie où chaque jeu i est associé à un évènement “S i : l’adversaire gagne”. La preuve de sécurité consiste alors à montrer que la probabilité de succès P(Si ) au jeu i est très proche de la probabilité de succès P(S i +1 ) à l’étape i +1. Le but est de créer autant d’instance que nécessaire pour se ramener à un jeu n où la probabilité est facile à calculer. Au final, la probabilité de succès de l’adversaire P(S 0 ) à l’étape initiale sera alors très proche de la probabilité de succès P(S n ) au jeu n.

Outils cryptographiques

Dans ce chapitre, nous présentons les outils cryptographiques nécessaires à la compréhension de la suite du manuscrit. Tout d’abord, nous rappelons le fonctionnement de la cryptographie dite “à clé publique” dans le contexte de la confidentialité. Ensuite, nous définissons les techniques permettant d’assurer l’authentification et l’intégrité des données, à savoir les signatures numériques et les codes d’authentification de messages. Enfin, nous présentons quelques primitives additionnelles utilisées couramment en cryptographie. Dans chaque section, nous précisons les définitions générales des méthodes citées, leur sécurité et les schémas particuliers utilisés pour la construction de nos systèmes présentés dans les chapitres suivants.

Authentification et intégrité

Comme nous l’avons vu, le but premier de la cryptographie est la confidentialité des messages. À l’ère de la cryptographie moderne, cela n’est plus suffisant. Il est nécessaire de construire des mécanismes pour assurer à la fois l’authentification et l’intégrité des messages. L’authentification garantit l’identité de l’expéditeur du message. L’intégrité, quant à elle, permet au destinataire d’être certain que le message reçu n’a pas été altéré pendant le transport. Plusieurs mécanismes répondent à ces problématiques aussi bien dans les constructions symétriques qu’asymétriques. Nous détaillons principalement le cas asymétrique à travers les signatures numériques et certaines de leurs variantes. Ensuite, nous présentons rapidement le cas symétrique avec l’utilisation de codes d’authentification de messages.

Signatures numériques

Tout comme pour les documents papiers, la signature numérique a pour rôle d’authentifier l’auteur d’un message. En outre, elle garantit aussi que ce message n’a pas été modifié depuis la signature. Elle repose sur la cryptographie à clé publique. Chaque utilisateur détient donc une paire de clés : une clé privée, connue uniquement par le signataire, et une autre publique, connue de tous. La clé privée permet de générer la signature qui sera vérifiable par tous, grâce à la clé publique. La signature numérique assure à la fois la vérification publique de l’intégrité du message et celle de l’identité du signataire.
Pour un tel mécanisme, plusieurs propriétés sont attendues :
– l’identité du signataire doit pouvoir être retrouvée avec certitude ;
– un attaquant ne peut pas se faire passer pour le signataire en signant à sa place ;
– la signature ne doit pas être réutilisée pour un autre contenu ;
– une fois signé, il doit être impossible de modifier le document ;
– enfin, le signataire ne doit pas pouvoir répudier une de ces signataire.
La définition plus formelle de la signature numérique est la suivante

Description

Modèle de sécurité

Un schéma de MAC séquentiellement agrégé (Setup, KeyGen, AggMAC,Verif) doit satisfaire la propriété de résistance aux falsifications existentielles contre des attaques adaptatives à messages choisis, avec oracle de vérification, notée EUF-CMVA. Autrement dit, il doit être impossible de produire un nouveau MAC valide sur un message m qui n’a pas fait l’objet d’une requête de MAC au préalable. Nous présentons ici le modèle dit certifié de LU, OSTROVSKY, SAHAI, SHACHAM et WATERS [LOS + 06] où pour chaque requête d’adhésion, l’adversaire doit prouver en plus la connaissance du secret sk associé à la valeur publique X = h sk . Cela permet d’extraire la clé sk grâce aux techniques de rejeu et d’extraction de la preuve de connaissance.
Plus formellement, la propriété est définie par le jeu suivant entre un challenger C et un adversaire A :

Notre signature partiellement aveugle

Les signatures partiellement aveugles (Définition 29) découlent des signatures aveugles qui sont une autre variante de la signature numérique classique. Elles permettent au signataire d’ajouter une information commune à une signature aveugle sur un message m qui lui est inconnu. De cette façon, le signataire garde un minimum de contrôle sur les données qu’il signe. Il peut par exemple ajouter, en accord avec le destinataire, une date, une période de validité ou le montant d’une transaction en cours. Nous présentons le modèle de sécurité associé à cette primitive cryptographique. Nous détaillons ensuite notre nouveau schéma de signature partiellement aveugle qui est également basée sur la construction introduite par CHASE, MEIKLEJOHN et ZAVERUCHA [CMZ14]. Nous montrons que notre schéma peut être défini sans couplage, sous la forme d’un MAC, puis réalisons les preuves de sécurité associées. Ce résultat a été publié à la conférence FC 2016, dans l’article “Private eCash in Practice” [BBD +17].

État de l’art

En 1982, CHAUM [Cha82] introduit l’idée des systèmes d’accréditations anonymes. Un tel système permet à un utilisateur de prouver que ses attributs ont été certifiés, sans révéler d’information superflue. Idéalement, l’utilisation successive d’une même accréditation ne doit pas pouvoir être détectée, pour éviter tout risque de traçage. En outre, il peut parfois s’avérer utile de certifier certains attributs sans les révéler. Un tel système requiert un schéma de signature qui permet d’une part de signer des messages mis en gage et d’autre part de prouver efficacement la connaissance d’une signature sans la révéler. De nombreuses applications existent pour les accréditations anonymes comme le paiement [Cha82] et le vote électronique.
Chacune d’entre elles entraîne ses propres contraintes et nécessite généralement des solutions efficaces qui doivent être adaptées aux environnements où elles peuvent être déployées. Nous reviendrons sur ces cas d’usages et leurs spécificités plus en détails dans les chapitres suivants.
En 2013, au sein de Microsoft, PAQUIN et ZAVERUCHA [Paq13, PZ13] proposent l’un des systèmes d’accréditations anonymes les plus connus actuellement, appelé U-Prove et basé sur un schéma de signature aveugle due à BRANDS [Bra94]. Cette construction est particulièrement efficace puisqu’elle repose sur des groupes d’ordre premier et permet de choisir les attributs communiqués. Néanmoins, U-Prove ne permet pas la non-chaînabilité lorsqu’une même accréditation est utilisée à plusieurs reprises. Pour atteindre cette propriété, l’utilisateur doit détenir une accréditation différente pour chaque nouvelle utilisation. En outre, la sécurité de ce schéma n’a pas été prouvée formellement, à ce jour.
La même année, BALDIMTSI et L YSYANSKAYA [BL13] proposent un système un peu moins efficace qui repose sur une extension d’une signature proposée par ABE [Abe01]. Ce schéma est prouvé sûr dans le modèle de l’oracle aléatoire sous l’hypothèse DDH. Plus récemment, en 2015, FUCHSBAUER, HANSER et SLAMANIG [FHS15] introduisent un schéma prouvé sûr dans le modèle standard. Cependant, tout comme U-Prove, une accréditation ne peut servir qu’une seule fois au risque de devenir traçable.
Le second système d’accréditations anonymes parmi les plus répandus est celui proposé par IBM en 2010 [IBM10], appelé Identity Mixer ou plus couramment Idemix. Il est basé sur un schéma de signature proposé par CAMENISCH et L YSYANSKAYA (CL) [CL01, CL03]. Ce système satisfait la propriété de non-chaînabilité multiple mais cela entraîne des pertes de  performances car les signatures CL reposent sur l’hypothèse RSA forte [BP97]. Ainsi, les paramètres RSA requis sont particulièrement grands et rendent Idemix inadapté pour les périphériques aux ressources limitées. Néanmoins, en 2013, VULLERS et ALPÁR [VA13] réalisent une implémentation d’Idemix sur une carte à puces MULTOS. Pour un module de 1024 bits, leur implémentation nécessite une seconde pour présenter une accréditation avec trois attributs dont un seul reste caché. En 2014, DE LA PIEDRA, HOEPMAN et VULLERS [PHV14] s’intéressent aux capacités limitées de la mémoire vive (RAM, pour Random Access Memory) des cartes à puces et proposent une implémentation plus efficace pour Idemix. Grâce à ce travail, une carte à puce peut supporter des accréditations pour plus de cinq attributs. Malgré cette amélioration, lestemps d’exécution restent trop importants pour certains cas d’usages, ce qui limite l’utilisation d’Idemix en pratique.
CAMENISCH et L YSYANSKAYA [CL04] introduisent en 2004 un schéma de signature efficace dans un environnement bilinéaire et l’utilise pour créer un schéma d’accréditations anonymes.
Par la suite, AKAGI, MANABE et OKAMOTO [AMO08] proposent un schéma plus efficace basé sur les signatures Boneh-Boyen (voir Section 2.2.1). En 2015, CAMENISCH, DUBOVITSKAYA, HARALAMBIEV et KOHLWEISS [CDHK15] définissent un nouveau schéma d’accréditations anonymes prouvé sûr dans le modèle UC (Universal Composability, [Can01]). Il satisfait la nonchaînabilité multiple et assure une taille constante pour la preuve de présentation de l’accréditation. Cependant, toutes ces constructions impliquent des calculs de couplages de la part de l’utilisateur ou bien des calculs dans le groupe G 2 . Par conséquent, ces systèmes ne peuvent pas être implémentés sur les cartes SIM actuelles puisqu’elles ne supportent pas ce type d’opérations.
En 2014, CHASE, MEIKLEJOHN et ZAVERUCHA [CMZ14] introduisent les accréditations anonymes dites “avec vérification par clé”. Ce nouveau type de schéma ne permet plus la vérification publique d’une accréditation mais offre en contrepartie de meilleures performances. Cela répond à des problématiques bien précises où l’émetteur et le vérificateur possèdent une même clé secrète commune et repose sur des MACs algébriques. En outre, les auteurs mettent en avant le fait qu’il est possible de passer d’un système à clé publique à une version à clé secrète.
Pour cela, il suffit d’utiliser son accréditation anonyme classique, publique, auprès d’un vérificateur qui va alors la convertir en une accréditation vérifiable uniquement par lui pour faciliter leurs futurs échanges. Ils proposent alors deux nouveaux schémas de MACs algébriques, notés MACDDH et MACGGM (voir Section 2.2.2), à partir desquels ils proposent des schémas d’accréditations anonymes avec vérification par clé. Cependant, pour n attributs non-révélés, chaque construction a une complexité en O(n) en nombre d’éléments du groupe cyclique sous-jacent car chaque nouvel attribut non-révélé nécessite une clé secrète supplémentaire. En outre, la garantie d’anonymat procurée n’est pas parfaite mais calculatoire puisque chacun des attributs est caché séparément avec du chiffrement ElGamal

Table des matières
Introduction 
I Préliminaires 
1 Préliminaires mathématiques
1.1 Rappels d’algèbre
1.1.1 Groupes et corps
1.1.2 Courbes elliptiques et couplages
1.2 Fonctions de bases
1.2.1 Notions de complexité
1.2.2 Fonctions particulières
1.3 Sécurité prouvée
1.3.1 Problèmes difficiles
1.3.2 Types de preuves et modèles de sécurité
2 Outils cryptographiques
2.1 Confidentialité
2.1.1 Chiffrement à clé publique
2.1.2 Chiffrements à clé publique
2.2 Authentification et intégrité
2.2.1 Signatures numériques
2.2.2 Codes d’authentification de messages
2.3 Autres primitives
2.3.1 Mise en gage
2.3.2 Preuves de connaissance à divulgation nulle de connaissance
2.3.3 Confidentialité différentielle
II Accréditations anonymes avec vérification par clé
3 Nouvelles primitives et accréditations anonymes
3.1 Notre MAC algébrique amélioré
3.1.1 Description
3.1.2 Preuves de sécurité
3.2 Notre MAC séquentiellement agrégé
3.2.1 Description
3.2.2 Preuve de sécurité
3.3 Notre signature partiellement aveugle
3.3.1 Description
3.3.2 Preuves de sécurité
4 Conception d’un système d’accréditations anonymes avec vérification par clé
4.1 Accréditations anonymes avec vérification par clé
4.1.1 État de l’art
4.1.2 Définition
4.2 Notre système
4.2.1 Description
4.2.2 Analyse de performance et de sécurité .
4.2.3 Preuves de sécurité
5 Conception d’un système de vote électronique
5.1 Vote électronique
5.1.1 État de l’art
5.1.2 Définitions
5.2 Notre système
5.2.1 Description
5.2.2 Preuves de sécurité
6 Conception d’un système de paiement électronique privé
6.1 Paiement électronique
6.1.1 État de l’art
6.1.2 Définitions
6.2 Notre système
6.2.1 Description
6.2.2 Preuves de sécurité
III Anonymisation de données 
7 Anonymisation de graphes par la confidentialité différentielle
7.1 Confidentialité différentielle et graphes
7.1.1 Définitions et notations
7.1.2 État de l’art
7.2 Notre procédé de confidentialité différentielle par blocs
7.2.1 Description
7.2.2 Autres mécanismes possibles
7.3 Évaluation expérimentale et preuves des théorèmes
7.3.1 Expérimentation
7.3.2 Preuves
Conclusion 
Publications et brevet 
Bibliographie