Université de Montréal

Évaluation de fonctions sur données privées

par

Alain Tapp

Département d’Informatique et de Recherche Opérationnelle Faculté des Arts et des Sciences

Mémoire présenté à la Faculté des études supérieures

en vue de l’obtention du grade de

Maître ès sciences (M.Sc) en Informatique

août 1995

\begin{matrix}c \\ ◯ \end{matrix}Alain Tapp, MCMXCV Université de Montréal Faculté des études supérieures

Ce mémoire intitulé

Évaluation de fonctions sur données privées

présenté par:

Alain Tapp

a été évalué par un jury composé des personnes suivantes:

(président-rapporteur) Geňa Hahn

(directeur de recherche) Claude Crépeau

(co-directeur) Gilles Brassard

(membre du jury) Pierre McKenzie

Mémoire accepté le: 12 décembre 1995

Sommaire

Ce mémoire traite de calculs multi-parties sur données privées (Private multiparty computation, pmpc). Soit N participants désirant évaluer y = F (x_{1}, x_{2}, ..., x_{N}) avec x_{i} la donnée privée du i ième participant. On aimerait qu’un protocole pmpc réalise cette tâche de façon à ce que: (1) Il soit possible à N participants honnêtes d’apprendre y. (2) Aucune coalition de participants ne pourra apprendre plus au sujet des données des autres participants que ce qui peut être déduit à partir de leurs propres données secrètes et de la connaissance de F et de y. (3) Un participant sait quand le protocole a échoué et qu’il n’apprend pas y. (4) Si un participant apprend y, alors tous l’apprennent.

Dans ce mémoire, un protocole original et efficace permettant d’accomplir cette tâche cryptographique est présenté. Notons qu’aucune supposition ne sera faite quant au nombre de participants honnêtes. Le protocole est réalisable dans une multitude de modèles étant donné qu’il nécessite seulement l’existence d’un transfert inconscient, par extension une mise en gage, et d’un canal de diffusion. Il est le premier protocole de ce genre à être efficace et sûr.

Pour en arriver à ce résultat, une procédure intermédiaire appelée transfert inconscient certifié sera utilisée. Le transfert inconscient certifié est un transfert inconscient où tous les bits en jeu sont des mises en gage. La réalisation efficace de ce sous-protocole est probablement la contribution originale la plus importante de ce mémoire.

Mots clés: Cryptologie, circuit, mise en gage, transfert inconscient, théorie des codes, calcul multi-parties, sécurité.

Table des matières

Identification du jury i

Sommaire ii

Mots clés ii

Remerciements ix

1 Introduction 1 1.1 Conventions et Notations . . . . . . . . . . . . . . . . . . . . . . . 5 1.2 Organisation des chapitres . . . . . . . . . . . . . . . . . . . . . . 6

2 Fondations 8

2.1 Transfert Inconscient (_{2}^{1})-ot . . . . . . . . . . . . . . . . . . . . . 10 2.1.1 (_{2}^{1})-ot à partir du transfert équivoque . . . . . . . . . . . 11 2.1.2 (_{2}^{1})-ot avec hypothèses calculatoires . . . . . . . . . . . . . 12 2.1.3 (_{2}^{1})-ot avec canal bruyant . . . . . . . . . . . . . . . . . . 13 2.1.4 (_{2}^{1})-ot avec canal quantique . . . . . . . . . . . . . . . . . 13

2.2 Mise en Gage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.2.1 bc à partir de (_{2}^{1})-ot ou du transfert équivoque . . . . . . 16 2.2.2 bc avec hypothèse calculatoire . . . . . . . . . . . . . . . . 16 2.2.3 bc avec canal quantique . . . . . . . . . . . . . . . . . . . 17 2.2.4 bc avec canal bruyant . . . . . . . . . . . . . . . . . . . . 17 2.2.5 Application de bc au tirage aléatoire . . . . . . . . . . . . 17 2.3 xor-camouflage (bcx) . . . . . . . . . . . . . . . . . . . . . . . . 19

2.3.1 bcx calculatoire . . . . . . . . . . . . . . . . . . . . . . . . 19 2.3.2 Obtenir des bcx à partir de bc . . . . . . . . . . . . . . . 20 2.3.3 Linéairement corrélable . . . . . . . . . . . . . . . . . . . . 20 2.3.4 Jumelable . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

3 Transfert Inconscient Certifié 26 3.1 Définition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 3.2 Description informelle de cot . . . . . . . . . . . . . . . . . . . . 29 3.3 Description Formelle . . . . . . . . . . . . . . . . . . . . . . . . . 30 3.4 Choix du code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 3.5 Preuves à divulgation nulle de cot . . . . . . . . . . . . . . . . . 33 3.6 Validité de cot . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

3.6.1 cot est correct . . . . . . . . . . . . . . . . . . . . . . . . 34 3.6.2 cot est honnête . . . . . . . . . . . . . . . . . . . . . . . 35 3.6.3 cot est privé pour Bob . . . . . . . . . . . . . . . . . . . 35 3.6.4 cot est privé pour Alice . . . . . . . . . . . . . . . . . . . 36

3.7 cot à l’intérieur d’un groupe (gcot) . . . . . . . . . . . . . . . . 37 3.8 Complexité de gcot . . . . . . . . . . . . . . . . . . . . . . . . . 38

4 Calculs Multi-Parties sur des données Privées 40

4.1 Initialisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

4.1.1 Mise en gage distribuée (DBC) . . . . . . . . . . . . . . . 43 4.2 Évaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

4.2.1 Évaluation du not . . . . . . . . . . . . . . . . . . . . . . 45 4.2.2 Évaluation du and . . . . . . . . . . . . . . . . . . . . . . 46

4.3 Révélation graduelle du résultat . . . . . . . . . . . . . . . . . . . 48 4.4 Validité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

4.4.1 Le protocole est correct . . . . . . . . . . . . . . . . . . . . 50 4.4.2 Le protocole est privé . . . . . . . . . . . . . . . . . . . . . 50 4.4.3 Le protocole est honnête . . . . . . . . . . . . . . . . . . . 50

4.4.4 Le protocole est juste . . . . . . . . . . . . . . . . . . . . . 51 4.5 Complexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

5 Conclusion 53

Table des protocoles

(_{2}^{1})-ot naïf . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

rnd . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

bcx-ou-exclusif . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 bcx-copie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 créer-bcxs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

cot naïf . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

cot . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

créer-dbc . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

not . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
pand . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
and . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

Table des figures

1.1 Relations entre les protocoles . . . . . . . . . . . . . . . . . . . . 7 2.1 Transfert inconscient . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.2 Mise en gage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 3.1 Transfert inconscient certifié . . . . . . . . . . . . . . . . . . . . . 27 4.1 Calculs multi-parties . . . . . . . . . . . . . . . . . . . . . . . . . 40 4.2 Complexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

viii

À mon père.

Remerciements

Cette petite section de mon mémoire est le premier endroit où je peux exprimer officiellement mes plus sincères remerciements à tous ceux qui depuis le commencement de mes études ont eu confiance en moi.

Je voudrais remercier Pierre Vaillancourt qui m’a fait aimer les mathématiques, Gaétan Hains qui m’a encouragé lors de mon Bac et m’a ouvert l’esprit à l’informatique théorique, Pierre McKenzie, qui par son enseignement a contribué à faire de moi un étudiant accompli, Geňa Hahn qui m’a encouragé et surtout Claude Crépeau et Gilles Brassard qui m’ont dirigé et ont été des modèles pour moi.

À l’université, il n’y a pas que les professeurs qui ont influencé mon épanouissement intellectuel. Je voudrais remercier Catherine Dufourd qui m’a encouragé et fait profiter de son expérience, Hervé Caussinus qui m’a supporté moralement et intellectuellement de façon constante tout au long de ma maîtrise, Jeroen van de Graaf avec qui j’ai écrit un article pour CRYPTO et qui m’a fait profiter de son expérience, Julie Vachon et Christian Foisy de l’équipe DPML, David Janin pour l’été COQ et Alexandre pour ma réputation de savant fou qu’il entretient avec joie.

Je voudrais aussi remercier les gens de l’ENS à Paris qui m’ont si chaleureusement accueilli lors de mon séjour et particulièrement Philippe Béguin.

Je voudrais remercier le CRSNG qui a subventionné mes deux années de recherche et sans lequel beaucoup d’étudiants ne pourraient poursuivre leurs études et ainsi en faire profiter toute la communauté.

Finalement, un merci spécial pour Mélanie qui m’a supporté lors des moments plus difficiles. Je remercie aussi pour leur support mon père, ma mère, mon frère ainsi que tous mes amis.

MERCI!

Chapitre 1

Introduction

Historiquement, la cryptologie s’est surtout intéressée à la protection des communications contre les oreilles indiscrètes. Le scénario classique est le suivant: Alice veut révéler à Bob des informations secrètes dans un contexte où les seuls média de communication à sa disposition sont susceptibles d’être espionnés. À travers les époques, des solutions originales à ce problème ont été formulées. Le 20e siècle est très riche en résultats. Citons par exemple la théorie de l’information de Shannon [50, 51], la cryptologie quantique [10], ainsi que la cryptographie à clef publique [29] qui sont sans aucun doute les réalisations les plus marquantes dans le domaine.

Cependant, le champ d’action de la cryptologie ne se limite pas à cet unique problème. L’informatique, avec l’incroyable quantité d’informations qu’elle nous permet de traiter, menace certaines de nos valeurs démocratiques. En effet, dans notre société moderne, la confidentialité, l’authenticité et l’accès à l’information sont devenues des préoccupations importantes. Paradoxalement, l’ordinateur est à la fois mal et remède, étant devenu l’un des outils indispensables de la cryptologie.

Il est maintenant possible de concilier nos débordants besoins d’information et de confidentialité. C’est d’ailleurs une des préoccupations importantes de la cryptologie contemporaine. Dans cette catégorie de problèmes cryptographiques, on retrouve une multitude de protocoles concrets. L’identification permet à deux interlocuteurs de s’assurer de leur identité mutuelle. Elle peut être utilisée entre un client et une banque pour leur permettre à tous deux d’effectuer des opérations bancaires en confiance [27]. La signature électronique [30], semblable à son homologue conventionnel, est mieux adaptée aux besoins modernes de communication. L’argent électronique [16] pourra remplacer les billets de banque tout en garantissant l’anonymat à leurs utilisateurs. Le vote ou l’élection secrète permettra, à partir des ressources de télécommunications déjà existantes, de réaliser une élection sans que toute la population ait à se déplacer. Les statistiques à l’aveugle permettront aux statisticiens de faire leur travail sans rien apprendre d’autre sur la population étudiée que la statistique qu’il doivent évaluer. Notons encore le tirage au sort [8], le poker à l’aveugle [49, 21] et le problème du millionnaire, problème-jouet introduit par Yao qui consiste pour deux millionnaires à déterminer lequel est le plus riche sans toutefois révéler leur fortune respective.

Beaucoup de ces problèmes sont en fait des cas particuliers de calculs multiparties sur données privées (PMPC). En général, N participants avec chacun une entrée secrète x_{i} désirent calculer y = F (x_{1}, ..., x_{N}) de telle façon que chacun apprend le résultat de la fonction sans rien apprendre au sujet des x_{i} provenant des autres participants, à l’exception bien entendu de ce qui peut être déduit par la connaissance de F, y et de son propre x_{i}.

Voici cinq caractéristiques propres à ce genre de protocole.

– On dit que le protocole est correct si N participants qui respectent le protocole arrivent bien à apprendre F (x_{1}, ..., x_{N}). Les protocoles cités et décrits dans ce mémoire sont tous corrects.

– On dit que le protocole est privé si la seule information qu’un groupe de participants G peut apprendre au sujet des x_{i} des autres participants est ce qui peut en être logiquement déduit à partir de y, F et des x_{i} appartenant aux membres du groupe. Un protocole est t-privé s’il résiste à n’importe quel groupe d’au plus t participants malhonnêtes.

– Le protocole est honnête si chaque participant sait quand il n’apprend pas le résultat de la fonction.

– Le protocole est juste si le fait qu’un participant apprenne y = F (x_{1}, ..., x_{N}) implique que tous l’apprennent.

– Finalement, un protocole est robuste (résiliant) si les participants malhonnêtes ne peuvent le faire avorter une fois qu’il est bien engagé.

Une solution simple consiste à faire confiance à une tierce partie à qui tous révéleront en privé leur x_{i}. Il devra calculer la fonction, révéler sa valeur à chaque participant et tout oublier par la ensuite. Malheureusement une telle solution est en général irréaliste ou insatisfaisante, c’est pourquoi beaucoup de recherches ont été réalisées à la fois sur le problème général et pour des cas particuliers comme ceux cités plus haut.

Le reste de ce document traitera du problème général de l’évaluation multi-parties de fonctions sur données privées. On trouve dans [32] un survol détaillé de l’ensemble des résultats dans ce domaine. Seuls les résultats les plus pertinents seront présentés dans cette introduction. Les protocoles se divisent en trois familles: ceux sans hypothèse cryptographique, ceux basés sur des hypothèses calculatoires et les protocoles basés sur le transfert inconscient. Il ne sera question ici que de protocoles où aucune restriction n’est faite quant au comportement que pourraient avoir des participants malhonnêtes.

Ben-Or, Goldwasser et Wigderson (1988) [3] et de façon indépendamment Chaum, Crépeau et Damgård (1988) [18] ont présenté une solution (N/3)-privée, juste, honnête et robuste. Leurs protocoles nécessitent qu’au moins 2/3 des participants soient honnêtes et qu’un canal privé existe entre chaque paire de participants. Si, en plus des canaux privés, les participants disposent d’un canal de diffusion, Tal Rabin et Ben-Or (1989) [47] et, de façon indépendante, Beaver (1991) [1] ont montré comment obtenir des résultats similaires en se contentant seulement d’une majorité de participants honnêtes. Ces protocoles ont l’avantage de ne reposer sur aucune hypothèse cryptographique et d’être robustes. Ils sont malheureusement très inefficaces.

En faisant l’hypothèse de l’existence de fonctions à brèches secrètes [55], Goldreich, Micali et Wigderson (1987) ont présenté un protocole privé, juste, honnête et robuste. Ce protocole nécessite lui aussi un canal de diffusion et une majorité de participants honnêtes. Chaum, Damgård et van de Graaf (1987) [19] ont présenté indépendamment un protocole privé, juste et honnête basé sur des hypothèses calculatoires. Ce protocole nécessite un canal de diffusion. Il a la caractéristique intéressante de camoufler les données d’un des participants de façon inconditionnelle. Chaum a aussi présenté une solution hybride [17] qui pour certains aspects repose sur des hypothèses calculatoires mais qui pour d’autres est inconditionnellement sûre.

Il est aussi possible de réaliser des protocoles multi-parties en s’appuyant sur l’existence d’un transfert inconscient et par extension d’une mise en gage. Ces procédures cryptographiques bien connues peuvent être implantées dans une multitude de modèles et dans le modèle quantique en particulier. Elles seront décrites en détail dans le prochain chapitre. Notons immédiatement que le protocole original présenté dans ce mémoire appartient à cette catégorie. Le premier résultat de ce genre est celui de Kilian (1988) [39], qui donna une solution pour deux participants. Malheureusement, ce protocole nécessite une transformation complexe du circuit à évaluer et n’a pas été généralisé au cas où le nombre de participants est supérieur à deux. Goldreich et Vainish (1987) [35] ont présenté un protocole privé et honnête fondé sur le transfert inconscient où on suppose que les participants ne trichent pas activement. Le protocole présenté dans ce document lui emprunte plusieurs idées.

Ce mémoire présente un protocole correct, privé, juste et honnête permettant l’évaluation de fonctions multi-parties ne faisant aucune supposition quant à l’honnêteté des participants. Ce protocole est fondé sur l’existence d’un canal de diffusion et d’un canal privé de transfert inconscient entre chaque pair de participants. Pour réaliser cela, il sera utile de construire un protocole intermédiaire de transfert inconscient de mise en gage. Cette tâche cryptographique introduite par Crépeau [24] sera appelé transfert inconscient certifié (cot). Une version améliorée de ce protocole sera combinée avec des idées de Goldwasser et Levin [36] pour réaliser le premier protocole multi-parties sûr et efficace de ce genre.

1.1 Conventions et Notations

Dans l’ensemble de ce document, certaines conventions seront utilisées. Les noms de certaines variables et tous les noms des protocoles sont fixés. Notez que des protocoles différents ont parfois des propriétés de même nom. Ces propriétés doivent être interprétées dans le contexte bien précis du protocole auquel elles sont associées.

Notez que:

– P désigne un ensemble de participants.

– N = |P | est le nombre de participants.

– m représente la taille d’un circuit.

– Nous qualifierons d’actifs les participants qui ont un rôle direct dans un protocole par opposition aux participants passifs qui ne feront que vérifier que tout se déroule convenablement.

– n est le paramètre de sécurité. Les caractéristiques de tous les protocoles seront vérifiées sauf avec probabilité inférieure à 1/c^{n} (c > 1).

– Nous utiliserons les mots certitude et nécessairement même dans le cas où il existe une probabilité d’erreur exponentiellement faible.

– Dans tous les protocoles, quand une condition n’est pas satisfaite, le protocole avorte.

– On note une mise en gage (bc) à un bit b par b̂ et un xor-camouflage (bcx) à un bit b par b (voir chapitre 2 sections 2 et 3). Dans le chapitre 3, on écrit w pour représenter { w_{0} , w_{2} , ..., w_{n} }. Cet abus de langage ne sera utilisé que lorsque le contexte ne laissera aucun doute quant à la nature de la mise en gage.

– x ∈_{R} A signifie: x est choisi aléatoirement dans A selon la distribution uniforme.

– A ⊂_{R} B signifie: A est un sous-ensemble choisi aléatoirement parmi les éléments de B selon la distribution uniforme.

– On note la négation booléen de A par ¬A.

– Pour des raisons de cohérence avec les différentes références, les noms abrégés des protocoles sont inspirés de leurs noms anglais.

1.2 Organisation des chapitres

Le chapitre 2 sera consacré au transfert inconscient ((_{2}^{1})-ot) et à la mise en gage (bc). Ces protocoles seront les briques de base à partir desquelles tous les autres protocoles seront construits. Ils y seront définis formellement et les implantations dans les modèles les plus courants y seront brièvement discutées. De plus, nous introduirons dans ce chapitre une forme spéciale de mise en gage appelée xor-camouflage (bcx). Ses propriétés y seront décrites et une partie importante du chapitre sera consacrée à leur implantation à partir de la mise en gage conventionnelle.

Le chapitre 3, qui est techniquement le plus difficile, est probablement aussi le plus important. Dans ce chapitre, nous décrivons en détail la procédure de transfert inconscient certifié. Elle sera construite à partir des xor-camouflage (bcx) et du transfert inconscient ((_{2}^{1})-ot).

C’est à partir de la procédure de transfert inconscient certifié que nous construirons, dans le chapitre 4, le protocole de calculs multi-parties sur données privées (pmpc). Les détails du protocole, de sa fiabilité et de son efficacité y seront discutés.

Suivra ensuite la conclusion dans laquelle nous discuterons de l’importance qu’occupera ce type de cryptologie dans les années à venir.

La figure 1.1 montre les dépendances logiques entre les différents protocoles présentés dans ce mémoire. Le lecteur pourra y référer pour conserver une vision globale tout au long de la lecture.

[figure: .; BC; (1/2)OT; AND; DBC; (G)BCX; (G)COT; PAND; NOT; PMPC; RND]

Fig. 1.1 - Relations entre les protocoles

Chapitre 2

Fondations

Tous les domaines des mathématiques reposent sur des vérités non démontrées: les axiomes. Ces axiomes ne sont pas choisis au hasard, on exige d’eux plusieurs propriétés. On les souhaite non-contradictoires mais suffisamment puissants pour engendrer toutes les “vérités” que l’on veut mettre en lumière. Cette approche est aussi très utilisée en science et en particulier en physique, comme en témoignent brillamment la théorie de la relativité et la mécanique quantique.

La cryptologie ne fait pas exception. Les cryptologues fondent la sécurité de leurs protocoles sur des hypothèses non-démontrées. Parmi ces hypothèses, on retrouve l’existence d’un canal bruyant, l’existence d’un canal quantique, et de façon plus courante, les hypothèses calculatoires comme la difficulté de factoriser les grands entiers, d’extraire le logarithme discret ou les racines carrées modulaires. Il existe une multitude de suppositions permettant de garantir aux protocoles une sécurité relative. Cette variété est la bienvenue, néanmoins il est intéressant pour des protocoles cryptographiques de haut niveau de résister aux changements de modèle. Il est fastidieux de créer de nouveaux protocoles chaque fois que l’on utilise un modèle différent ou même que l’on adapte un modèle déjà existant.

Dans le but de conserver toute la généralité possible, les protocoles que nous présentons dans ce document sont fondés sur deux procédures de base: le transfert inconscient ((_{2}^{1})-ot) et la mise en gage (bc). On connaît des implantations sécuritaires de ces protocoles cryptographiques dans une multitude de modèles. En fait, la mise en gage peut être implantée à partir du transfert inconscient et même à partir d’une version plus faible appelée transfert équivoque. En pratique, comme la mise en gage possède des implantations efficaces dans tous les modèles où l’on sait implanter le transfert inconscient ((_{2}^{1})-ot) nous considérerons ces deux procédures de façon indépendante. Ceci facilitera l’analyse des protocoles et donnera une idée plus juste de leurs complexités intrinsèques.

Les deux premières sections du chapitre sont consacrées au transfert inconscient et à la mise en gage. Nous consacrerons la dernière partie de ce chapitre à l’introduction du xor-camouflage qui est une extension de la mise en gage. Le transfert inconscient et le xor-camouflage seront les protocoles de base du transfert inconscient certifié présenté dans le chapitre suivant.

2.1 Transfert Inconscient (_{2}^{1})-ot

Le transfert inconscient pourrait être considéré comme une panacée étant donné qu’à partir de ce simple outil on peut régler une multitude de problèmes cryptographiques. Ce protocole est en l’occurrence suffisamment puissant pour permettre l’implantation de toutes les procédures qui seront décrites dans les pages qui suivent.

[figure: (_{2}^{1})-OT (a_{0}, a_{1}, b)(a_{b}); a_{0}; a_{1}; a_{b}; b; Bob; Alice]

Fig. 2.1 - Transfert inconscient

Formellement, supposons qu’Alice connaît (choisit) deux bits a_{0} et a_{1} et que Bob connaît (choisit) un bit b. Après l’exécution de (_{2}^{1})-ot, Bob apprend c = a_{b}. Le protocole doit aussi être privé, c’est-à-dire que peu importe leur comportement, Alice n’apprend rien au sujet de b et Bob n’apprend rien au sujet de a_{¬b} même s’il connaissait déjà a_{b}. On appelle ce protocole Transfert inconscient (“One out of two Oblivious Transfer”, (_{2}^{1})-ot). Il a été introduit par Wiesner sous le nom “message multiplexing” [5] et redécouvert par Even, Goldreich et Lempel [31]. La multitude des publications qui en traitent témoigne de sa grande utilité [26, 39, 22, 2, 46].

Ce protocole est conceptuellement simple. Supposons qu’Alice et Bob ont un ami commun, Charles, et que tous deux lui font entièrement confiance. L’implantation de (_{2}^{1})-OT(a_{0}, a_{1}, b)(c) d’Alice vers Bob devient un jeu d’enfant. Le protocole devrait s’exécuter comme suit.

Protocole: (_{2}^{1})-ot naïf

Entrées Sorties Alice : a_{0}, a_{1} : BIT Bob : c : BIT Bob : b : BIT Relations Propriétés c = a_{b} privé

1: Alice révèle secrètement a_{0} et a_{1} à Charles.

2: Bob révèle secrètement b à Charles.

3: Charles révèle secrètement c = a_{b} à Bob.

4: Charles oublie a_{0}, a_{1} et b.

Il est facile de voir que cette implantation du protocole est correcte si Charles agit convenablement. Comme avec toutes les procédures cryptographiques, le fait d’avoir à sa disposition une tierce partie fiable en laquelle tous les protagonistes ont confiance permet une résolution simple du problème. Heureusement pour les cryptologues, il est parfois impossible (et surtout irréaliste) d’avoir confiance en un tel tiers.

On connaît une multitude de modèles dans lesquels (_{2}^{1})-ot peut être implanté, chacun avec ses caractéristiques propres. Voyons rapidement quelques-uns de ces modèles.

2.1.1 (_{2}^{1})-ot à partir du transfert équivoque

La première apparition du transfert équivoque dans la littérature nous vient de Rabin [46]. Le transfert équivoque qu’il présentait est une version plus simple du transfert inconscient présenté précédemment. Supposons qu’Alice connaît (choisit) un message w. En exécutant ot(w) avec Alice, Bob a une chance sur deux d’apprendre w sans qu’Alice ait la moindre information sur le fait que Bob l’ait appris ou non. Par contre, Bob, lui, sait s’il a appris w. Ce protocole sera appelé transfert équivoque (“Oblivious Transfer”, ot).

Il n’est pas tellement difficile pour Alice et Bob en utilisant O(n) OT d’effectuer un (_{2}^{1})-ot d’un bit [23]. La sécurité d’(_{2}^{1})-ot implanté de cette façon repose évidemment sur la sécurité de l’implantation de l’ot utilisé.

2.1.2 (_{2}^{1})-ot avec hypothèses calculatoires

Plusieurs problèmes cryptographiques calculatoires n’ont aucune solution efficace connue. Malheureusement, la difficulté intrinsèque de ces problèmes n’a pas encore été démontrée. Lorsque la sécurité d’un protocole dépend d’un tel problème, on dit que le protocole repose sur une hypothèse calculatoire. En fait, on limite la capacité de calcul d’un (ou même des deux) participants.

De façon générale, Goldreich, Micali et Wigderson ont montré que l’existence d’une permutation à brèche secrète est suffisante pour implanter (_{2}^{1})-ot [34]. Le problème de la factorisation des grands entiers et en particulier du résidu quadratique [37] permet une implantation intéressante de (_{2}^{1})-ot [14]. Cette technique peut être généralisée à d’autres hypothèses calculatoires comme RSA [48] et le problème du logarithme discret.

L’avantage de faire reposer un protocole sur une hypothèse calculatoire réside dans la simplicité de son implantation. Il est facile de mettre à la disposition des participants des machines et des canaux de communication classiques. Par contre, comme la sécurité intrinsèque de ces problèmes n’a pas été prouvée, ils sont potentiellement à la merci d’un adversaire ayant une puissance algorithmique supérieure.

2.1.3 (_{2}^{1})-ot avec canal bruyant

Les propriétés d’un canal bruyant sont très semblables à celles du transfert équivoque de Rabin [46], il n’en demeure pas moins que l’implantation de (_{2}^{1})-ot à partir d’un canal binaire symétrique (canal bruyant) d’erreur ϵ nécessite un travail non négligeable. Le problème a été énoncé pour la première fois dans [26] et une solution plus efficace est à paraître dans [25]. L’algorithme utilise O(n^{3}) transferts de bits sur le canal pour obtenir un seul (_{2}^{1})-ot. L’avantage de cette implantation est de ne pas reposer sur des hypothèses calculatoires.

2.1.4 (_{2}^{1})-ot avec canal quantique

L’introduction du canal quantique [54, 5, 4] a été une véritable révolution dans le domaine de la cryptologie. Avec le canal quantique la sécurité de (_{2}^{1})-ot repose sur la validité même de la mécanique quantique et non sur des hypothèses calculatoires ou d’autres techniques non démontrées. Sans être absolue, cette notion de sécurité est probablement la plus forte que l’on puisse imaginer dans le contexte d’un (_{2}^{1})-ot.

Le protocole est présenté dans [6] et un premier pas vers la démonstration de sa sécurité se trouve dans [56]. Le néophyte trouvera une foule de références utiles dans [10] de même que dans [11] sa version World Wide Web (WWW) régulièrement mise à jour.

2.2 Mise en Gage

La mise en gage (“Bit Commitment”, bc) est, tout comme (_{2}^{1})-ot, une procédure fondamentale de la cryptologie. Elle est utilisée dans une multitude de protocoles cryptologiques et en particulier dans les protocoles où des preuves à divulgation nulle [38] sont nécessaires.

Par mise en gage (bc), on réfère en réalité à deux procédures distinctes mais complémentaires, soit l’engagement et l’ouverture (ou révélation). Supposons qu’Alice a un bit a en tête. On dit qu’elle s’engage à a envers Bob par â si le protocole exécuté est:

correct: il existe une procédure Ouvre(â) = a qui révèle a à Bob.

confidentiel: Bob n’apprend rien au sujet de a avec â.

et liant: il n’est pas possible pour Alice de convaincre Bob que Ouvre(â) = ā.

Par exemple, pour s’engager au sujet d’un certain bit, Alice pourrait remettre un coffre-fort à Bob dont elle seule connaît la combinaison. À l’intérieur du coffre se trouverait un bout de papier sur lequel serait écrit 0 ou 1. Pour ouvrir la mise en gage, Alice n’aurait qu’à donner la combinaison du coffre à Bob qui pourrait alors apprendre la valeur du bit qui s’y trouve camouflé. Cet exemple-jouet illustre bien les trois caractéristiques d’une mise en gage.

15

Fig. 2.2 - Mise en gage Tout comme (_{2}^{1})-ot, bc ne peut être implanté sans hypothèses. Dans l’exemple précédent, c’est la confiance envers le coffre-fort qui permet sa réalisation. De multiples modèles existent dans lesquels il est possible d’implanter bc. En fait, on peut utiliser (_{2}^{1})-ot et même le transfert équivoque pour le réaliser. Comme dans la plupart des modèles où (_{2}^{1})-ot existe, on peut implanter bc directement de façon plus efficace et parfois même avec des hypothèses plus faibles, bc sera aussi considéré comme procédure de base. Voici quelques modèles où des implantations intéressantes sont connues.

2.2.1 bc à partir de (_{2}^{1})-ot ou du transfert équivoque

Comme nous l’avons dit plus tôt, la mise en gage peut être réalisée en utilisant (_{2}^{1})-ot ou le transfert équivoque comme sous-protocole. On trouve dans [12] comment le réaliser à partir de (_{2}^{1})-ot. Sa réalisation à partir du transfert équivoque est décrite dans [40] et attribuée à Crépeau. Dans les deux cas, le protocole nécessite O(n) transferts pour effectuer une mise en gage et l’ouverture se fera en envoyant un message classique de taille O(n). La sécurité de ces implantations repose sur la sécurité du transfert utilisé.

2.2.2 bc avec hypothèse calculatoire

On peut implanter la mise en gage en faisant des suppositions de nature calculatoire. En fait, il a été démontré par Naor [44] que l’existence d’un générateur pseudo-aléatoire (et donc d’une fonction à sens unique) est suffisante pour réaliser la mise en gage. On trouve aussi dans [28, 45, 12, 19] d’autres implantations intéressantes.

La dernière partie du chapitre est consacrée à des implantations spéciales de mise en gage permettant des opérations supplémentaires. Notons tout de suite que dans le monde calculatoire, plusieurs mises en gage possèdent déjà ces propriétés de façon intrinsèque.

2.2.3 bc avec canal quantique

De la même façon que pour le transfert inconscient, il est possible d’effectuer la mise en gage en utilisant le canal quantique et ainsi de faire reposer sa sécurité sur la validité de la mécanique quantique elle-même. Ce résultat de Brassard, Crépeau, Jozsa et Langlois [15] nous donne une implantation de bc utilisant O(n) transferts sur le canal quantique. L’ouverture se fait en communiquant un message classique de taille O(n).

2.2.4 bc avec canal bruyant

Il est possible d’implanter la mise en gage si l’on dispose d’un canal bruyant. Une légère modification du protocole basé sur le canal quantique [13] ou de celui basé sur le transfert équivoque [40] permet l’implantation de bc. Le protocole se retrouvera aussi dans [25]. L’avantage de l’utilisation du canal bruyant est encore une fois d’éviter les hypothèses calculatoires.

2.2.5 Application de bc au tirage aléatoire

Il est possible, en utilisant la mise en gage, à un groupe de N participants de choisir un bit aléatoirement. Le bit pourra être choisi de façon à ce que même une coalition de N − 1 participants ne puisse prédire avec plus d’une chance sur deux le bit qui sera choisi, et ce en autant qu’au moins un participant soit honnête.

Nous présentons ici une solution simple qui sera suffisante pour les besoins des protocoles qui suivent. Pour tirer un bit aléatoirement en groupe, chaque participant choisit lui même un bit aléatoire et s’y engage envers tous les autres participants. Ensuite, chaque participant ouvre toutes ses mises en gage. Le bit aléatoirement tiré par le groupe est le ou-exclusif de la valeur que chaque participant avait aléatoirement choisie.

Protocole: rnd

Entrées Sorties Nil x : BIT Relations Propriétés Nil aléatoire

1: ∀i ∈ P, i choisit b_{i} ∈_{R} {0, 1}
2: ∀i, j ∈ P tel que i ≠ j, i s’engage à b̂_{i}^{j} = b_{i} envers j.
3: ∀i, j ∈ P tel que i ≠ j, i ouvre b̂_{i}^{j} à j puis j diffuse b_{i}.
4: ∀i ∈ P, i vérifie que ∀j b_{j}^{i} = b_{j}.
5: x = ⨁_{i=1}^{N} b_{i}

Il est facile de voir que ce protocole répond bien aux exigences décrites précédemment. Tous les participants s’engagent à leur choix aléatoire pour éviter que les participants malhonnêtes choisissent la valeur de leur bit en fonction des valeurs déjà révélées. Il suffit qu’un bit parmi les N soit aléatoire pour que le résultat du ou-exclusif le soit aussi.

Ce protocole nécessite un canal de diffusion et O(N) opérations sur des mises en gage par participant.

2.3 xor-camouflage (bcx)

Dans cette section, nous introduisons un type spécial de mise en gage. En plus des propriétés habituelles des mises en gage, à savoir être confidentielles et liantes, elle seront linéairement corrélables et jumelables.

linéairement corrélable: Si Alice est engagée au sujet de { b_{1} , b_{2} , ..., b_{k} } via des bcx, il lui sera possible de prouver à Bob que ⨁_{i=1}^{k} b_{i} = c sans ouvrir aucune des mises en gage ni révéler aucune autre information à leur sujet.

jumelable: Il est possible à Alice de s’engager envers plusieurs participants à une même valeur de telle façon que les participants honnêtes soient convaincus qu’Alice s’est effectivement engagée à la même valeur envers chacun d’eux.

On appellera ces mises en gage des xor-camouflages (bcx). Les propriétés supplémentaires des bcx en font des outils puissants. Il seront, avec (_{2}^{1})-ot, les briques de base du protocole de transfert inconscient certifié (gcot) présenté dans le prochain chapitre.

2.3.1 bcx calculatoire

Dans le modèle calculatoire, il existe des implantations de la mise en gage ayant d’office les propriétés des bcx. Sans entrer dans les détails, notons que plusieurs mises en gage obtenus à partir d’hypothèses calculatoires sont déjà linéairement corrélables et jumelables [19]. Aucun bc ayant directement ces propriétés n’est encore connu dans les autres modèles. Heureusement on peut réaliser des bcx à partir de bc aux propriétés conventionnelles. Le reste de ce chapitre sera d’ailleurs consacré à cette réalisation.

2.3.2 Obtenir des bcx à partir de bc

Voyons maintenant comment, à partir des bc conventionnels corrects, confidentiels et liants, on peut construire des bcx qui seront en plus linéairement corrélables et jumelables. La technique présentée ici est directement inspirée de travaux de Kilian [41] qui lui même s’est inspiré de Rudich et de Bennett.

Les bcx seront constitués de n paires de bc conventionnels, chaque paire représentant la valeur auquel le participant est engagé. On dit qu’une paire représente une certaine valeur si le ou-exclusif de ses deux composantes égale cette valeur. Formellement un bcx b à une valeur b est un ensemble de n paires de bc

b = {(b̂_{iG}, b̂_{iD})|1 ≤ i ≤ n, ∀i b_{iG} ⊕ b_{iD} = b}

Si toutes les paires n’ont pas la même valeur, on dira que le bcx est inconsistant. La valeur d’un tel bcx sera égale à la valeur de la majorité des paires et on dira que les paires telles que b̂_{iG} ⊕ b̂_{iD} ≠ b sont inconsistantes. Nous verrons plus de détails au sujet de leur création et des inconsistances ultérieurement.

2.3.3 Linéairement corrélable

Nous présentons maintenant un protocole permettant à Alice de convaincre Bob que le ou-exclusif de k bcx est c. Le protocole sera

– privé: aucune autre information au sujet des k bcx ne sera révélée.

– honnête: Alice ne pourra convaincre Bob que le ou-exclusif des k bcx est b si ce n’est pas le cas.

Pour ce faire, Bob choisira aléatoirement une paire de bc pour chaque bcx et demandera à Alice de le convaincre que ces paires ont la bonne parité c. Pour ce faire Alice révélera la parité des bc de gauche à Bob qui pouras alors calculer la parité des bc de droite. Bob lui demandera ensuite selon un choix aléatoire d’ouvrir tous les bc de gauche ou au contraire tous les bc de droite. Il s’assurera finalement que leur valeur est consistante avec ce qu’Alice avait prétendu. Toutes ces opérations devront être répéter n fois de façon à ce que Bob acquière la certitude qu’Alice n’a pu le trompé.

Protocole: bcx-ou-exclusif

Entrées Sorties Alice : b^{1} , ..., b^{k} :bcx Nil Alice : b : BIT Relations Propriétés Etablir: ⨁_{i=1}^{k} b^{i} = b privé

1: Alice révèle b = ⨁_{i=1}^{k} b^{i} à Bob.

2: Bob permute aléatoirement l’ordre des paires dans chaque bcx.

3: Pour j de 1 à n

3.1: Alice révèle b_{jG} = ⨁_{i=1}^{k} b_{jG}^{i}.

3.2: Bob fixe b_{jD} = b_{jG} ⊕ b

3.3: Bob choisit aléatoirement X_{j} ∈_{R} {G, D}

et révèle son choix à Alice. 3.4: Pour i de 1 à k Alice ouvre b̂_{jX_{j}}^{i}. 3.5: Bob vérifie que b_{jX_{i}} = ⨁_{i=1}^{k} b_{jX_{j}}^{i}

Il n’est pas trop difficile de se convaincre que si Alice et Bob suivent le protocole et que ⨁_{i=1}^{k} b^{i} = b, le protocole s’exécutera sans encombres. Par contre, si les bcx sont construits de façon inconsistante ou si leur parité n’est pas b, Bob aura une probabilité exponentiellement faible de ne pas avorter le protocole. En effet, si ⨁_{i=1}^{k} b^{i} ≠ b on aura que ∀i(⨁_{j=1}^{k} b_{jG}^{i} ≠ ⨁_{j=1}^{k} b_{jD}^{i} ⊕ b). Si Alice révèle la véritable valeur de b_{jG} = ⨁_{i=1}^{k} b_{jG}^{i}, Bob fixera b_{jD} = b_{jG} ⊕ b ≠ ⨁_{i=1}^{k} b_{jD}^{i} et Alice sera prise en défaut si X_{i} = D. De la même façon, si Alice ment et prétend que b_{jG} = ⨁_{j=1}^{k} b_{jD}^{i} ⊕ b ≠ ⨁_{j=1}^{k} b_{jG}^{i} elle sera prise en défaut si X_{i} = G. Donc peu importe la stratégie d’Alice, si Bob choisit les X_{i} de façon aléatoire, il n’aura qu’une probabilité de 1/2^{n} de ne pas se rendre compte qu’Alice tente de le berner.

La même chose se produit si un des bcx est inconsistant, mais cette fois seulement pour certaines lignes (certaines valeurs de j). Si un très petit nombre d’inconsistances existent, il se peut que le protocole réussisse mais la probabilité qu’il avorte s’approche exponentiellement de 1 avec le nombre d’inconsistances. Les bcx très inconsistants seront donc inutilisables. Nous reviendrons sur ce point.

Nous savons maintenant qu’Alice peut convaincre Bob de n’importe quelle relation linéaire entre des bcx. Malheureusement, cette opération consomme toutes les paires de bc qui le constituent. Pour être en mesure d’effectuer plusieurs preuves sur le même bcx, il faudra le copier. Les copies devront se faire elles aussi de façon privée et honnête, c’est-à-dire que le protocole ne devra révéler aucune information sur le bcx qui est copié et garantir que les copies ont toutes la même valeur que le bcx original.

Pour faire k copies d’un bcx b , Alice construira n(k+1) paires de bc représentant b et Bob les partitionnera aléatoirement en k + 1 bcx. Il en choisira ensuite un et demandera à Alice de montrer qu’il est égal à b .

Protocole: bcx-copie

Entrées Sorties

Alice : b :bcx Bob : b_{1} , ..., b_{k} : bcx Relations Propriétés ∀i b_{i} = b privé, honnête

1: Alice construit l’ensemble E = {(b̂_{iG}, b̂_{iD})|1 ≤ i ≤ n(k + 1), b_{iG} ⊕ b_{iD} = b}.

2: Bob partitionne aléatoirement E en k+1 ensembles de n paires qui formeront

les bcx { b_{0} , ..., b_{k} }.

3: Alice prouve à Bob que b ⊕ b_{0} = 0.

Ce protocole est évidemment correct, si Alice et Bob coopèrent, il y aura bien k copies de b à la fin du protocole. Le plus important est qu’Alice soit incapable de construire un bcx b_{i} ≠ b. Comme Bob partitionne les paires de façon aléatoire, à peu près autant de paires inconsistantes se retrouveront dans chaque bcx et donc aussi dans b_{0} . Si Alice construit assez de paires inconsistantes pour avoir une certaine probabilité de construire un bcx consistant ayant comme valeur b̄ elle échouera nécessairement le test de l’étape 3. De plus, si b est dès le départ inconsistant, Alice ne réussira tout simplement pas à le copier. Dans le pire cas, Alice réussira à construire des copies contenant de très petits nombres d’inconsistances, ce qui n’est pour elle d’aucun intérêt.

Avant d’effectuer une preuve sur des bcx, Alice en fera une copie, ce qui lui permettra de conserver les bcx pour un usage ultérieur. On obtient, preuve et copie confondues, que k bcx sont linéairement corrélables au prix de l’utilisation de O(nk) opérations élémentaires sur les bc qui les constituent.

2.3.4 Jumelable

Dans le cas où Alice désire s’engager à la même valeur envers plusieurs participants, il faudra porter une attention particulière lors de la création des bcx pour s’assurer qu’ils soient jumelables. Rappelons qu’un bcx est jumelable s’il est possible à Alice de s’engager envers plusieurs participants à une même valeur de telle façon que les participants honnêtes soient convaincus qu’Alice s’est effectivement engagée à la même valeur envers chacun d’entre eux. La consistance n’est pas très importante lors de la création. Nous avons vu que des bcx inconsistants, ne pouvant être ni ouverts, ni utilisés dans une preuve, sont aussi utiles que des bcx qu’Alice refuse d’utiliser.

La création de N − 1 bcx à la même valeur par Alice, un à chacun des autres participants d’un groupe^{1} P, se fera comme suit. Alice s’engage envers des mises en gage conventionnelles à 2n paires représentant le même bit b envers chaque participant. Le reste du protocole sera répété n fois. Tous les participants choisissent ensemble et aléatoirement une paire de bc appartenant a chaque bcx. Alice classe ces pairs en deux groupes de paires identiques. Puis, tous les participants choisissent aléatoirement de demander à Alice d’ouvrir les parties gauches ou les parties droites de chaque paire. Enfin les participants vérifient que tous les bc ouvert d’un même groupe sont égaux. Après avoir exécuté cela n fois, les participants honnêtes de P sont convaincus que les paires qui restent constituent des bcx ayant la même valeur pour chacun d’entre eux.

Une fois les bcx construits de façon jumelable, les opérations de copies et de preuves se feront individuellement avec chaque participant.

1. Pour simplifier la notation on suppose momentanément Alice exclu de P

Protocole: créer-bcxs

Entrées Sorties Alice : b : BIT ∀i ∈ P : b^{i} :bcx Relations Propriétés ∀ b = b^{i} privé, jumelable

1: ∀i ∈ P, pour j de 1 à n Alice s’engage envers i à (b̂_{jG}^{i}, b̂_{jD}^{i})

tel que b_{jG}^{i}, b_{jD}^{i} ∈_{R} {0, 1} et b_{jG}^{i} ⊕ b_{jD}^{i} = b. 2: ∀i ∈ P , i choisit aléatoirement une permutation

de ses 2n paires, la rend publique et renomme ses paires suivant la permutation.

3: Pour j de 1 à n

3.1: Alice construit V_{0} = { i | (b̂_{jG}^{i}, b̂_{jD}^{i}) = (ˆ0, b̂) } et

V_{1} = { i | (b̂_{jG}^{i}, b̂_{jD}^{i}) = (ˆ1, ˆ b̄) }.

3.2: Alice révèle E ∈_{R} {V_{0}, V_{1}}. 3.3: x = rnd({G, D}) 3.4: ∀i ∈ P, Alice ouvre b̂_{jX}^{i} à i qui diffuse sa valeur. 3.5: ∀i ∈ P, i vérifie que

∀j, k ∈ E, b_{jX}^{i} = b_{kX}^{i} et

∀j, k ∉ E, b_{jX}^{i} = b_{jX}^{i}.

4: ∀i ∈ P, {(b̂_{jG}^{i}, b̂_{jD}^{i})|s + 1 ≤ j ≤ 2s} formera le bcx b^{i} du participant i.

Chapitre 3

Transfert Inconscient Certifié

Ce chapitre est le plus important de ce mémoire. Nous y présentons le protocole de transfert inconscient certifié (“Commited Oblivious Transfer”, cot). Ce protocole cryptographique est d’une utilité incontestable, comme en témoignera le chapitre suivant où nous verrons comment il est le coeur du protocole d’évaluation multipartie d’une fonction sur données privées.

Le transfert inconscient certifié a été introduit en 1989 par Claude Crépeau [24] sous l’appellation “Verifiable Oblivious Transfer”. Un protocole en apparence plus efficace a été publié en 1989 par Goldwasser et Levin sous le nom de “Preprocess-Oblivious-Transfer” [36]. Malheureusement, une analyse attentive de leur protocole montre qu’il est possible pour les participants de tricher sans être repérés avec probabilité non négligeable. Bien qu’il ne soit pas trop difficile de remédier à ce problème, le protocole qui en résulterait serait encore moins efficace.

Le protocole cot que nous présentons dans ce chapitre est efficace et sûr. Il utilise la mise en gage (via les bcx) et le transfert inconscient ((_{2}^{1})-ot) sans toutefois faire de restriction sur leur mode d’implantation. Ceci permet d’adapter les protocoles utilisant cot aux multiples modèles dans lesquels évolue la cryptologie contemporaine. En l’occurrence, avec un transfert inconscient et une mise en gage basés sur l’existence d’un canal quantique, on réalise cot sans hypothèses calculatoires.

L’efficacité du protocole est liée à son utilisation avantageuse de propriétés des codes correcteurs. Ils sont utilisés dans le protocole, non pas pour corriger d’éventuelles erreurs de transmission, mais dans un but de sécurité et d’efficacité.

Dans les prochaines sections, nous allons définir formellement le transfert inconscient certifié (cot) et expliquer en détail son implantation pour deux participants ou à l’intérieur d’un groupe. Nous discuterons aussi de sa validité et de son efficacité.

3.1 Définition

Le transfert inconscient certifié (“Commited Oblivious Transfer”, cot) est la réunion logique de la mise en gage (bc) et du transfert inconscient ((_{2}^{1})-ot). En effet, un cot n’est rien d’autre qu’un (_{2}^{1})-ot où les bits en jeu sont des bcx.

[figure: Bob; Alice; COT; a_{0}; a_{1}; b; a_{b}]

Fig. 3.1 - Transfert inconscient certifié

Supposons qu’Alice soit engagée à a_{0} et a_{1} envers Bob et que lui soit engagée à b envers Alice. Après cot( a_{0} , a_{1} , b )( c ) Bob est engagée à c . De plus, le protocole sera:

– correct: Si Alice et Bob respectent le protocole, Bob sera engagée envers

Alice à c = a_{b}.

– honnête: Si Alice respecte le protocole, Bob ne peut être engagée à c = ā_{b}.

– privé: Si Alice respecte le protocole, Bob n’apprendra rien au sujet de ab̄, et si Bob respecte le protocole, Alice n’apprendra rien au sujet de b.

Voyons une implantation de cot s’appuyant sur une tierce partie honnête nommée Charles. Cette implantation naïve illustre bien les caractéristiques du protocole.

Protocole: cot naïf

Entrées Sorties Alice : a_{0} , a_{1} : bcx Bob : c : bcx

Bob : b : bcx

Relations Propriétés c = a_{b} privé, honnête

1: Alice s’engage à a_{0} et a_{1} envers Bob et Charles et Bob s’engage à b envers Alice et Charles si ce n’est pas déjà fait. ( n.b. des mises en gage jumelables sont utilisées)

2: Alice ouvre a_{0} et a_{1} à Charles en privé.

3: Bob ouvre b à Charles en privé. 4: Charles révèle a_{b} à Bob en privé. 5: Bob s’engage à c = a_{b} envers Alice et Charles. 6: Bob ouvre c à Charles en privé qui vérifie que c = a_{b}. 7: Charles oublie a_{0}, a_{1}, b et c.

3.2 Description informelle de cot

Intuitivement, pour accomplir cot( a_{0} , a_{1} , b )( c ) avec Bob, Alice réalise de façon imparfaite un transfert inconscient de chaîne sur deux mots de code w_{0} et w_{1}. On dit de ces transferts qu’ils sont imparfaits du fait que même si Bob est honnête, il apprendra de l’information au sujet des deux mots. Bob apprendra tous les bits du mot w_{b} et quelques bits de wb̄. Cela lui permettra de s’assurer que s’il avait effectué le protocole avec b ayant la valeur opposée, tout aurait aussi bien fonctionné. Si Bob n’effectuait pas cette vérification, Alice pourrait se comporter de telle façon que le protocole fonctionne seulement pour une valeur de b, ce qui lui permettrait, par la réussite ou l’échec du protocole, d’apprendre b. À la fin du protocole, Alice montrera une relation entre a_{0} et w_{0} ainsi qu’entre a_{1} et w_{1} , ce qui permettra à Bob d’apprendre a_{b} et de s’y engager via c . Il faut donc aussi s’assurer que Bob ne puisse avoir suffisamment d’information au sujet des deux chaînes pour apprendre les deux bits d’Alice.

Voici de façon plus détaillée les différentes étapes du protocole. Au début, Alice est engagée à a_{0} et a_{1} , Bob est engagée à b . Bob choisit un code avec de bonnes propriétés (voir sec. 3.4). Alice s’engage à w_{0} et w_{1} , deux mots de code choisis aléatoirement, et prouve qu’ils sont bien des mots de code. Ensuite, Alice transfère w_{0} et w_{1} de telle façon qu’en chaque position, Bob puisse choisir entre apprendre un bit de w_{0} ou de w_{1}, mais pas les deux. Bob choisira d’apprendre la plupart des bits du côté de w_{b} mais aussi quelques bits de wb̄. Pour se convaincre qu’Alice a bel et bien transmis les bits conformément à w_{0} et w_{1} , Bob lui demandera, pour un certain nombre de positions, d’ouvrir des bcx de w_{0} et w_{1} . Si Alice a triché lors de plusieurs transferts, Bob aura une très grande probabilité de s’en rendre compte à ce moment et d’avorter le protocole. Jusqu’à maintenant aucune information concernant a_{0} ou a_{1} n’a encore été révélée. De plus, si Bob refuse de continuer cela ne donne aucune information à Alice au sujet de b. Par contre, si Bob ne constate aucune inconsistance, il est certain qu’Alice n’a pu tricher sur un grand nombre de positions. Il utilisera le fait que w_{0} et w_{1} sont des mots de code pour repérer ces positions et les corriger, puis il s’engagera à w = w_{b}.

C’est maintenant à Bob de convaincre Alice que le mot auquel il est engagée est bien w_{b}. Pour ce faire, Bob prouve à Alice que w est un mot de code. Ensuite, Alice ouvre un certain nombre des positions de w_{0} et w_{1} et Bob lui prouve que pour ces positions, les bits de w sont égaux à ceux de w_{b} et ce, sans ouvrir ses bcx ni donner d’informations au sujet de b.

Même si Bob est engagé à w = w_{b}, il possède tout de même de l’information au sujet de wb̄, information qu’il obtient par les bits qu’il a appris et du fait qu’il sait que c’est un mot de code. Alice doit maintenant utiliser les deux mots w_{0} et w_{1} pour révéler à Bob a_{b}, sans toutefois donner d’information au sujet de ab̄. Pour ce faire, elle utilisera une fonction de distillation de secret (“privacy amplification” [7]) h tel que a_{0} = h(w_{0}) et a_{1} = h(w_{1}). Cette fonction, en l’occurrence le produit scalaire avec un mot m approprié, sera révélé à Bob. Il pourra alors calculer c = a_{b} = m · w et s’y engager sans pour autant pouvoir l’utiliser pour apprendre ab̄. Finalement, Bob doit prouver à Alice qu’il s’est bien engagé à c = m · w et

donc que c = a_{b}.

3.3 Description Formelle

Avant le protocole, Alice est engagée à a_{0} et a_{1} . De son coté, Bob est engagée à b et à la fin du protocole, il sera engagée à c = a_{b}. Alice et Bob s’engagent toujours à un bit en utilisant un bcx et ils s’engagent à une chaîne en s’engageant à chacun de ses bits. Le choix du code qui influence le choix des constantes α et ϵ est discuté dans la prochaine section et les preuves dans la section suivante. À n’importe quel moment du protocole, si une preuve ou une vérification échoue, le protocole est avorté.

Protocole: cot

Entrées Sorties

Alice : a_{0} , a_{1} : BCX Bob : c : BCX

Bob : b : BCX

Relations Propriétés c = a_{b} privé, honnête, juste

1: Bob choisit et annonce à Alice un code linéaire C [n, k, d] avec

k > (1/2 + 2σ)n et d > ϵn, corrigeant efficacement t ∈ Ω(n) erreurs. 2: Alice choisit w_{0}, w_{1} ∈_{R} C, s’y engage via w_{0} et w_{1}

et prouve que w_{0} ∈ C et w_{1} ∈ C. 3: Bob choisit I_{0}, I_{1} ⊂_{R} {1...n} avec |I_{0}| = |I_{1}| = σn, I_{1} ∩ I_{0} = ∅. 4: Pour i de 1 à n, si i ∈ I_{0} alors

Alice exécute (_{2}^{1})-ot(w_{0}^{i}, w_{1}^{i}, b̄) avec Bob qui reçoit w^{i} sinon Alice exécute (_{2}^{1})-ot(w_{0}^{i}, w_{1}^{i}, b) avec Bob qui reçoit w^{i}.

5: Bob annonce I = I_{0} ∪ I_{1} à Alice puis

∀i ∈ I, Alice ouvre w_{0}^{i} et w_{1}^{i} . 6: ∀i ∈ I_{0}, Bob vérifie que w^{i} = wi ; b̄ et affecte w^{i} ← w_{b}^{i},

∀i ∈ I_{1}, Bob vérifie que w^{i} = w_{b}^{i}. 7: Bob corrige w en utilisant l’algorithme de décodage de C,

s’engage à w et prouve que w ∈ C. 8: Alice choisit I_{2} ⊂_{R} {1...n} avec |I_{2}| = σn et I_{2} ∩ I = ∅,

annonce I_{2} et ouvre w_{0}^{i} et w_{1}^{i} , pour i ∈ I_{2}. 9: ∀i ∈ I_{2}, Bob prouve que w^{i} = wi ; b. 10: Alice choisit m ∈_{R} {0, 1}^{n} tel que

a_{0} = m · w_{0} et a_{1} = m · w_{1} et le prouve. 11: Bob s’engage à c ← m · w et le prouve.

3.4 Choix du code

Pour réaliser cot, certaines propriétés des codes seront mises à profit. Nous présentons ici les concepts essentiels pour la réalisation de cot mais le lecteur désirant avoir plus d’information pourra se référer à [43].

Un code linéaire^{1} C [n, k, d] est un sous-ensemble de {0, 1}^{n} tel que

1. |C| = 2^{k}

2. ∀ x, y ∈ C, x ≠ y ⇒ D(x, y) ≥ d. où D(x, y), la distance de Hamming, représente le nombre de positions différentes entre x et y.

3. ∀x, y ∈ C, x ⊕ y ∈ C.

Pour qu’une famille de codes soit intéressante, il faut qu’un algorithme efficace permettant de corriger αn erreurs lui soit associé, c’est-à-dire un algorithme permettant, à partir d’un mot de code x et d’un mot x′ tels que D(x, x′) ≤ αn, de retrouver x.

Dans le protocole cot, Bob devra choisir un code C [n, k, d] tel que

k > (1/2 + 2σ)n et d > ϵn.

De plus, il devra exister un algorithme efficace permettant de corriger une quantité d’erreurs proportionnelle à d. De tels codes existent; les codes concaténés [33] sont les codes les plus connus pouvant satisfaire ces exigences. Ils ne sont malheureusement pas suffisamment efficaces pour nos besoins.

Une publication récente de Spielman [53] introduit les “Superconcentrator Codes”, une nouvelle famille de codes ayant les propriétés qui nous intéressent et qui de plus sont très efficaces. Dans cet article, on trouve un algorithme de correction nécessitant uniquement l’évaluation de O(n) ou-exclusifs d’un nombre constant de bits. On peut aussi vérifier qu’un mot appartient au code avec le même nombre d’opérations.

1. Nous nous intéressons uniquement aux codes linéaires binaires

Comme, à la connaissance de l’auteur, aucune autre famille de codes plus efficace ayant les propriétés désirées n’existe, nous considérerons dans l’analyse de complexité et lors des preuves que les “Superconcentrator Codes” sont utilisés.

3.5 Preuves à divulgation nulle de cot

Dans le protocole, Alice et Bob effectuent un certain nombre de preuves à divulgation nulle. Rappelons qu’une preuve à divulgation nulle est un ensemble d’opérations qui permettent à un prouveur de convaincre un vérificateur que des bits sont reliés par une certaine relation sans révéler aucune autre information au sujet de ces bits. Toutes les preuves du protocole sont faciles à réaliser si les mises en gage utilisées sont des bcx. C’est d’ailleurs pourquoi dans le protocole on utilise ce type de mise en gage.

Aux l’étapes 2 et 7 un des participants doit prouver qu’un ensemble de bcx forme un mot de code. Comme nous l’avons dit précédemment, si le bon code est utilisé, cette opération peut être accomplie en montrant O(n) relations linéaires (ou-exclusif) d’un nombre constant de bits du mot de code. Ceci nécessite au total O(n) opérations élémentaires sur les bcx.

À l’étape 9, pour i ∈ I_{2}, Bob doit prouver à Alice que w^{i} = wi ; b. Pour chaque position où w_{0}^{i} = w_{1}^{i}, Bob n’a qu’à ouvrir w^{i} car dans ce cas w^{i} ne contient aucune information sur b. Si w_{0}^{i} = 0 et w_{1}^{i} = 1, on a que w_{b}^{i} = b et donc Bob prouve que w^{i} ⊕ b = 0. De la même façon, si w_{0}^{i} = 1 et w_{1}^{i} = 0 Bob prouve que w^{i} ⊕ b = 1. Aucune de ces preuves ne révèle d’information au sujet de b. Aux étapes 10 et 11, les preuves se font directement en utilisant les propriétés des bcx.

3.6 Validité de cot

Il existe une foule de façons pour Alice ou Bob d’avoir un comportement déviant lors de l’exécution du protocole. À n’importe quel moment, l’un ou l’autre peut décider de cesser la coopération ou tout simplement utiliser des valeurs erronées lors des transferts inconscients.

Dans cette section, nous allons montrer que le protocole est correct, honnête et privé.

3.6.1 cot est correct

Si Alice et Bob respectent le protocole à la lettre, il est assez facile de se convaincre que le protocole ne va pas avorter et qu’à la fin Bob sera engagée à c = a_{b}. À travers le protocole, Bob apprendra w_{b} puis a_{b}, ce qui lui permettra de s’engager à w = w_{b} et finalement à c = a_{b}.

Nous avons discuté dans la section 3.4 du fait qu’Bob puisse choisir à l’étape 1 un code avec les bonnes propriétés. Aux étapes 3, 4, 6, 7, 8, 10 et 11, Alice et Bob effectuent des calculs ou communiquent de l’information, ce qu’il réussiront sans peine. Les vérifications des étapes 2, 5, 7, 9, 10 et 11 pourront être réalisées correctement si Alice et Bob ont bien transféré et se sont engagés à ce qu’ils doivent.

3.6.2 cot est honnête

Si Alice respecte le protocole, Bob ne pourra s’engager à c ≠ a_{b}. Il est important de noter que nous ne pouvons pas forcer Bob à s’engager à c = a_{b}. Ce n’est d’ailleurs pas un problème car même si on le pouvait, en refusant de l’utiliser par la suite, Bob rendrait cette mise en gage bien inutile. C’est pourquoi l’important est que si Bob s’engage, il le fasse à la bonne valeur.

Voyons pourquoi cela est vrai. Supposons au contraire que Bob ait pu s’engager à c ≠ a_{b}. Cela signifie qu’il a prouvé à l’étape 11 que c = m · w , mais c ≠ a_{b} et a_{b} = m · w_{b} alors w ≠ w_{b}. Comme Bob a prouvé que w est un mot de code, le nombre de positions différentes entre w et w_{b} doit être supérieur à d > ϵn. Mais à l’étape 9, Alice lui a demandé de prouver que w et w_{b} sont égaux sur σn positions aléatoirement choisies, ce que Bob n’aurait pu faire, excepté avec probabilité exponentiellement faible en n. D’où la contradiction.

Il est aussi impossible à Alice d’utiliser le protocole de façon à ce que Bob s’engage à c ≠ a_{b} s’il est honnête. Du fait qu’Alice ait prouvé que a_{b} = m · w_{b} , il est évident que si w = w_{b} , Bob pourra s’engager à c = a_{b}. Supposons au contraire que w ≠ w_{b} . Comme ce sont deux mots de code, ils doivent avoir au moins d > ϵn position différentes. Mais si c’est le cas, le test qui s’effectue aux étapes 5 et 6 ne pourra avoir été réussi. Donc si Alice ou Bob est honnête, à la fin du protocole Bob ne pourra être engagée à c ≠ a_{b}, excepté avec probabilité exponentiellement faible en n.

3.6.3 cot est privé pour Bob

Montrons que, peu importe le comportement d’Alice, si Bob respecte le protocole, elle n’apprendra rien au sujet de b. Bob transmet de l’information à Alice seulement aux étapes 1, 5, 7, 9 et 11. Aux étapes 1 et 5, l’information transmise est indépendante de b. Aux étapes 7, 9 et 11, par définition de bcx et du fait que les preuves sont à divulgation nulle, Alice n’apprend rien au sujet de b. Le seul moyen qui reste à Alice pour obtenir de l’information consiste à faire en sorte que Bob agisse différemment dépendant de la valeur de b. Elle devra le forcer à refuser si b = 0 (b = 1) aux étapes 7 ou 9.

Heureusement, cela est impossible. Si Bob ne réussit pas les preuves de l’étape 7 ou 9, c’est que w ≠ w_{b} . Comme il a été prouvé à l’étape 2 que w_{b} est un mot de code, w et w_{b} doivent avoir au moins t positions différentes, sans quoi l’algorithme de décodage aurait trouvé w_{b}. Comme t ∈ Ω(n), la vérification de l’étape 6 ne pourra avoir été réussie qu’avec probabilité exponentiellement faible. Donc, si la vérification de l’étape 6 réussit, les preuves de l’étape 7 et 8 vont aussi réussir. Notons que la vérification de l’étape 6 a la même probabilité de succès peu importe b, et ce dû au fait que |I_{0}| = |I_{1}|.

3.6.4 cot est privé pour Alice

Si Alice respecte le protocole, Bob ne pourra rien apprendre au sujet ab̄, peu importe sa stratégie et ce, même s’il connaît déjà a_{b}.

Comme Alice choisit w_{0} et w_{1} aléatoirement, aucune information sur ab̄ ne parvient à Bob avant l’étape 10 où Alice révèle m et prouve que ab̄ = m · wb̄ . Pour en arriver là, Bob doit préalablement passer le test de l’étape 9 et convaincre Alice qu’il est engagé à w = w_{b}. Pour que Bob ait moins que 2^{σn/2} candidats pour w_{b} au moment de son engagement de l’étape 6, il doit avoir obtenu au moins n/2+3σn/2 des n+2σn bits de w_{b} durant les étapes 4 et 5. Ceci est dû au fait qu’il y a 2^{n/2+2σn} mots de code possibles, et donc après avoir appris n/2 + 3σn/2 bits supplémentaires, 2^{σn/2} d’entre eux sont encore possibles. Si c’est le cas, il y aura aussi 2^{σn/2} candidats pour wb̄ même après avoir appris σn bits supplémentaires à l’étape 8.

Donc, si Bob apprend seulement n/2 + 3σn/2 bits de w_{b}, il aura une probabilité d’au plus 2^{−σn/2} de s’engager au bon mot de code à l’étape 7. Comme tout mot de code erroné aura au moins ϵn positions différentes du bon mot, l’étape 9 aurait une chance exponentiellement faible d’être réussie dans ce cas. D’un autre côté, si Bob apprend aussi peu que n/2 + σn/2 bits de wb̄ il aura une probabilité d’au plus 2^{−σn/2} d’avoir une information, même minime, au sujet de ab̄ = m · wb̄ étant donné que m est aléatoire et ce, par un théorème de Bennett, Brassard et Robert [7].

3.7 cot à l’intérieur d’un groupe (gcot)

Si Alice et Bob sont engagés à leurs entrées envers tous les participants d’un groupe, il leur est possible d’effectuer gcot( a_{0} , a_{1} , b )( c ) de façon à ce qu’à la fin du protocole, Bob soit engagé à c envers tous les membres du groupe. Le protocole aura aussi les caractéristiques suivantes:

– correct: Si tous les participants respectent le protocole, Bob sera engagée envers tous à c = a_{b} (via bcx).

– honnête: Si au moins un participant respecte le protocole, Bob ne peut être engagée à c = ā_{b}.

– privé: Si Alice respecte le protocole, Bob et les autres participants n’apprendront rien au sujet de ab̄, et si Bob respecte le protocole, Alice et les autres participants n’apprendront rien au sujet de b.

Trois modifications au protocole cot sont nécessaires pour le transformer dans un protocole gcot :

– Le code correcteur C de l’étape 1 doit être accepté par l’ensemble des participants.

– Quand un participant s’engage ou prouve une relation, il le fait envers tous les participants.

– Le sous-ensemble I_{2} de l’étape 8 doit être choisi par tous les participants.

Pour choisir I_{2}, seulement O(n log(n)) bits aléatoires devront être choisis, au coût de O(Nn log(n)) bcs pour chaque participant. Quand plusieurs gcot sont effectués en parallèle, le même ensemble I_{2} peut être utilisé à chaque fois sans perte de sécurité. Ceci permettra une économie de ressources appréciable si les participants préparent I_{2} avant d’effectuer les gcot.

Le protocole de gcot est très semblable au cot, l’ensemble des participants jouant alternativement le rôle d’Alice et de Bob. Le protocole est correct, privé et honnête pour les mêmes raisons.

3.8 Complexité de gcot

La complexité de gcot dépend du type de bcx et de (_{2}^{1})-ot utilisés par les participants. C’est pourquoi nous discuterons de sa complexité en terme des protocoles déjà définis.

gcot utilise O(n) (_{2}^{1})-ot qui sont effectués quand w_{0} et w_{1} sont transférés. Le protocole nécessite O(n) opérations sur les bcx de la part d’Alice et Bob avec chaque participant pour s’engager respectivement au sujet de w_{0}, w_{1} et w et pour effectuer les différentes preuves. Alice et Bob effectuent donc O(Nn) opérations sur les bcx et les autres participants O(n). Nous n’avons pas tenu compte ici des tirages de O(n log n) bits aléatoires qui doivent être faits par les participants. Comme nous l’avons dit précédemment, ce tirage peut être effectué une seule fois pour plusieurs gcot. Nous en tiendrons compte plus tard.

Si les bc disponibles ne sont pas des bcx, alors la technique décrite dans le chapitre 2 permettant leur construction devra être utilisée. Dans ce cas, pour réaliser un gcot, O(Nn^{2}) opérations sur les bc seront effectuées par Alice et Bob et O(n^{2}) par les autres participants. Enfin, si seulement (_{2}^{1})-ot est disponible les bc devront être implantés à partir de cette procédure au coût de O(n) (_{2}^{1})-ot par bc et pour une complexité totale de O(Nn^{3}) (_{2}^{1})-ot pour Alice et Bob, et de O(n^{3}) (_{2}^{1})-ot pour les autres.

Chapitre 4

Calculs Multi-Parties sur des

données Privées

[figure: Bob; Charles; David; Edward; Frank; Zappa; Alice; ...; x_{1}; x_{2}; x_{3}; x_{4}; x_{5}; x_{6}; x_{P}; F (x_{1}, x_{2}, ..., x_{N})]

Fig. 4.1 - Calculs multi-parties

Dans ce chapitre, nous présentons un protocole de calculs multi-parties sur données privées conceptuellement simple et efficace. L’introduction de ce mémoire présente un survol des travaux déjà réalisés dans ce domaine. Rappelons que ce genre de protocole permet l’implantation du vote secret, du poker à l’aveugle (“Mental Poker”) [49, 21], des statistiques confidentielles et de tout autre protocole nécessitant des opérations sur des données secrètes réparties entre deux ou plusieurs individus [32].

Dans un protocole multi-parties, N participants ayant chacun une entrée secrète x_{i} désirent apprendre y = F (x_{1}, ..., x_{N}). Rappelons quatre caractéristiques propres à ce genre de protocole:

– On dit que le protocole est correct si N participants qui respectent le protocole réussissent à apprendre y.

– On dit que le protocole est privé si la seule information qu’un groupe de participants G peut apprendre au sujet des x_{i} des autres participants est y et ce qui peut en être logiquement déduit sachant F et les x_{i} tel que i ∈ G.

– Le protocole est honnête si un participant sait quand il n’apprend pas un résultat y valable. On dit que y est un résultat valable s’il existe {x′_{1}, ..., x′_{N}} tel que y = F (x′_{1}, ..., x′_{N}) et ∀i, x′_{i} = x_{i} si le participant i est honnête.

– Le protocole est juste si le fait qu’un participant apprenne de l’information au sujet de y à travers le protocole implique que tous les participants apprennent y.

Le reste du chapitre sera consacré à la présentation d’un protocole d’évaluation multi-parties de fonctions sur données privées (pmpc) correct, privé, juste et honnête basé sur l’existence d’un transfert inconscient ((_{2}^{1})-ot) entre chaque paire de participants et l’existence d’un canal de diffusion fiable les reliant tous. Aucune supposition ne sera faite quant à l’honnêteté des participants. Le protocole reposera aussi conceptuellement sur les bcx qui peuvent, comme nous l’avons vu dans le chapitre 2, être réalisés à l’aide du (_{2}^{1})-ot.

La procédure de transfert inconscient certifié (gcot) décrite au chapitre précédent et réalisée à partir d’(_{2}^{1})-ot et des bcx sera la pierre angulaire du protocole pmpc. Rappelons que les bcx peuvent (entre autres) être implantés à l’aide des bc qui eux-mêmes peuvent l’être à partir d’(_{2}^{1})-ot. De plus, notons que certaines implantations de (_{2}^{1})-ot permettent qu’il soit utilisé comme canal privé. Si par contre le (_{2}^{1})-ot utilisé n’a pas cette propriété, chaque paire de participants devra en plus disposer d’un canal privé ou d’une chaîne aléatoire secrète commune.

Le protocole pmpc n’est pas robuste, c’est-à-dire qu’un participant peut faire avorter le protocole même si celui-ci est déjà bien entamé. Ceci est inévitable étant donné qu’aucune hypothèse n’est faite quant à l’honnêteté des participants. Pour garantir que le protocole soit juste, chaque participant devra coopérer à chacune des étapes du protocole. Si un groupe de participants pouvait continuer l’évaluation du circuit sans la coopération de certains autres participants (même un seul), ceci leur permettrait de tricher le protocole en évaluant la fonction avec les données de tous sans partager le résultat, ce qui n’est pas permis dans un protocole juste. Ce n’est donc pas un inconvénient propre au protocole présenté ici mais bien une caractéristique intrinsèque de tous les protocoles de ce type.

Le protocole pmpc est constitué de trois phases. Premièrement, l’initialisation où les participants s’entendent sur le circuit et les paramètres du protocole. C’est aussi lors de l’initialisation que les participants vont préparer leurs bits privés de façon à pouvoir effectuer le calcul. Pendant la deuxième phase du protocole, les participants évaluent la fonction proprement dite. Le circuit calculant la fonction sera évalué une porte à la fois par un travail conjoint de tous les participants. La dernière étape est celle de la révélation graduelle du résultat. Cette étape a pour but d’éviter que certains participants n’apprennent le résultat pendant que d’autres restent dans l’ignorance. C’est surtout à ce moment que les participants se soucient du fait que le protocole soit juste.

4.1 Initialisation

L’initialisation est divisée en deux parties. Premièrement, les participants vont s’entendre sur un circuit calculant la fonction F ainsi que sur tous les paramètres des sous-protocoles. Les paramètres sont liés au type de bcx et de (_{2}^{1})-ot utilisés ainsi qu’au protocole cot où un code et plusieurs constantes doivent être choisis de façon consistante.

Dans un deuxième temps, les participants vont distribuer leurs bits d’entrée en utilisant des bcx. Ces bits distribués seront appelés dbc (“Distributed Bits Commitment” ou mise en gage distribuée) et c’est sur eux que seront effectuées les opérations permettant l’évaluation du circuit.

4.1.1 Mise en gage distribuée (DBC)

Pour chacun de ses bits d’entrée, chaque participant devra, avec la coopération des autres, construire une mise en gage distribuée (dbc). Comme leurs noms l’indiquent, les dbc sont des mises en gage dont la valeur est distribuée entre tous les participants. Un dbc est le ou-exclusif de N valeurs connues chacune par un participant et sur laquelle il est engagé envers tous par des bcx. Rappelons que les bcx sont jumelables. A partir de ce moment, à moins d’avis contraire, lorsqu’un participant s’engage à une valeur, cela signifie qu’il s’engage envers tous les participants en utilisant des bcx égaux.

Pour camoufler b avec un dbc B, un participant p demande à chaque participant i de s’engager à un bit aléatoire b_{i} et de l’ouvrir à p et uniquement à lui. Finalement p s’engagera à b_{p} = b ⊕ (⨁_{i≠p} b_{i}).

Protocole: créer-dbc

Entrées Sorties p : b BIT B : dbc Relations Propriétés B = b privé

1: ∀i ∈ P tel que i ≠ p, i s’engage à b_{i} ∈_{R} {0, 1}.

2: ∀i ∈ P tel que i ≠ p, i ouvre b_{i} à p et uniquement à lui.

3: p s’engage à b_{p} = b ⊕ ⨁_{i≠p} b_{i}

4: B = { b_{1} , b_{2} , ..., b_{N} }

Toutes les valeurs intermédiaires lors de l’évaluation du circuit seront des dbc. Pour avoir de l’information au sujet de la valeur d’un dbc, il faut connaître la valeur de tous les bits qui le constituent. Les dbc restent donc privés même contre une coalition de N − 1 participants.

On peut considérer les dbc comme des exemples de “secret sharing” parfait où tous les participants doivent coopérer pour récupérer la valeur du bit distribué. C’est d’ailleurs ce qui sera fait lors de la dernière étape du protocole pour permettre à tous d’apprendre le résultat de la fonction.

4.2 Évaluation

La deuxième étape du protocole pmpc est l’évaluation du circuit. Le circuit composé de not et and sera évalué une porte à la fois. Chaque porte aura comme entrée et comme sortie des dbc. L’évaluation d’une porte sera réalisée de façon à ne pas accroître l’information d’une éventuelle coalition malhonnête.

4.2.1 Évaluation du not

L’évaluation du not ne pose pas de problème particulier. On désire à partir d’un dbc A camouflant a construire un dbc B camouflant b tel que b = ā. Le protocole devra être:

– honnête: B ≠ A et tous les participants en seront convaincus.

– privé: Aucune coalition de moins de N participants ne peut obtenir d’information supplémentaire au sujet de A (ainsi que B) par le protocole.

Pour construire le dbc B camouflant b = ā, chaque participant s’engagera à une valeur égale à sa part de A, sauf un participant appelé ξ qui, lui, s’engagera à la valeur opposée. Chacun doit évidemment prouver qu’il s’est engagé à la bonne valeur. Comme la valeur d’un dbc est le ou-exclusif de toutes les parts le constituant, le dbc ainsi construit aura la valeur opposée au dbc original.

Protocole: not

Entrées Sorties

A = { a_{1} , ..., a_{N} } :dbc B = { b_{1} , ..., b_{N} } : dbc

Relations Propriétés A ≠ B privé, honnête

1: ∀i ∈ P tel que i ≠ ξ, i s’engage à b_{i} = a_{i} et le prouve.

2: Le participant ξ s’engage à b_{ξ} ≠ a_{ξ} et le prouve.

3: B = { b_{1} , b_{2} , ..., b_{N} }

Il est facile ici de voir que le protocole est privé et honnête.

4.2.2 Évaluation du and

L’évaluation du and est la partie la plus difficile d’un protocole pmpc. C’est pour évaluer cette porte asymétrique que le gcot et les dbc sont nécessaires.

Pour simplifier la présentation de l’évaluation du and, nous introduirons un protocole de and partiel (pand) réalisé entre deux participants sous la supervision du groupe. Au début du protocole pand, Alice est engagée à a et Bob à b . Après pand( a , b ) Alice sera engagée à c_{A} et Bob à c_{B} tels que c_{A} ⊕ c_{B} = a ∧ b . De plus le pand sera:

– honnête: a ∧ b = c_{A} ⊕ c_{B} et tous les participants en seront convaincus.

– privé: peu importe son comportement Alice n’apprend rien sur la valeur de b et de façon similaire Bob n’apprend rien sur la valeur de a.

L’implantation du pand est assez simple.

Protocole: pand

Entrées Sorties Alice : a :BCX Alice : c_{A} :BCX Bob : b :BCX Bob : c_{B} :BCX Relations Propriétés a ∧ b = c_{a} ⊕ c_{b} privé, honnête

1: Alice s’engage à c_{A} ∈_{R} {0, 1}.

2: Alice s’engage à t_{0} = c_{A} et à t_{1} = c_{A} ⊕ a et le prouve.

3: Alice et Bob effectuent GCOT ( t_{0} , t_{1} , b )( c_{B} ).

Voyons pourquoi le protocole est honnête. Comme gcot est correct, on a que si b = 0 alors c_{B} = t_{0} = c_{A} ⇒ c_{A} ⊕ c_{B} = 0 = a ∧ b et si b = 1 alors c_{B} = t_{1} = c_{A} ⊕ a ⇒ c_{A} ⊕ c_{B} = a = a ∧ b. Le protocole est privé du fait que gcot et bcx le sont.

Nous sommes maintenant en mesure de réaliser le protocole and qui à partir de deux dbc A et B construira le dbc C tel que A ∧ B = C. Le and sera privé et honnête de la même façon que le not.

Pour construire C =and(A, B), toutes les paires ordonnées de participants exécuteront un pand de leur part de A et B, puis chacun évaluera le ou-exclusif de toutes les valeurs auxquelles il s’est engagé en sortie des pand et s’y engagera. Toute ces bcx formeront C.

Protocole: and

Entrées Sorties

A = { a_{1} , ..., a_{N} } : dbc : C :DBC

B = { b_{1} , ..., b_{N} } : dbc

Relations Propriétés A ∧ B = C privé, honnête

1: ∀i, j ∈ P avec i ≠ j, i et j effectuent pand( a_{i} , b_{j} ) = ( g_{ij} , d_{ji} )

2: ∀i ∈ P, i s’engage à c_{i} = ⨁_{j=1}^{N}( g_{ij} ⊕ d_{ji} )

3: C = { c_{1} , c_{2} , ..., c_{N} }

Du fait que le pand est honnête et privé ainsi qu’en regard de l’équation

{⨁_{i=1}^{N} a_{i}} ∧ {⨁_{i=1}^{N} b_{i}} = ⨁_{i=1,j=1}^{N}(a_{i} ∧ b_{j}),

il est facile de se convaincre que le and est lui aussi honnête et privé.

L’évaluation d’un and nécessitera que chaque participant s’implique de façon active dans O(N) pand et de façon passive dans les O(N^{2}) autres. La complexité du pand étant essentiellement égale à celle du cot, on obtient que les participants seront activement impliqués dans O(N) cot et passivement dans O(N^{2}). De plus, nous devons tenir compte ici des O(n log n) bc nécessaires pour le choix du sous-ensemble aléatoire qui sera utilisé dans les O(N^{2}) cot. En combinant ces trois mesures, on obtient que chaque participant devra effectuer O(Nn) (_{2}^{1})-ot , O(N^{2}n) opérations sur des bcx et O(n log n) bc.

4.3 Révélation graduelle du résultat

Nous sommes maintenant au point où l’évaluation du circuit est terminée. Mais comme les bits résultants sont camouflés dans des dbc, personne n’a encore appris quoi que ce soit au sujet de y. Nous désirons que les participants apprennent cette valeur de façon juste, c’est-à-dire que si un participant apprend le résultat, tous l’apprennent. Cette étape est plus difficile qu’elle n’y paraît à première vue.

Si tous les participants ouvrent leur part du dbc simultanément, le protocole sera juste. En pratique, il est difficile d’accomplir une telle tâche, une coalition de participants malhonnêtes pouvant toujours se retirer au moment où ils apprennent les parts des autres participants et ainsi être seuls à apprendre le résultat de la fonction. Pour éviter qu’une telle chose ne se produise, le résultat sera réparti en un nombre polynomial de bits qui seront ouverts les uns après les autres alternativement par chaque participant. Chaque bit donnera peu d’information au sujet du résultat mais peu à peu l’incertitude se dissipera et à la fin tous les participants auront appris la valeur de la fonction avec certitude. À aucune étape, un groupe de participants n’aura d’avantage important sur les autres. Un groupe pourra seulement avoir un avantage de 1/P oly. Cet avantage peut être considéré par certains comme non négligeable. Cela est malheureusement inévitable, car si à chaque étape un groupe de participants ne peut avoir qu’un avantage exponentiellement faible sur les autres, il faudra une nombre exponentiel d’étapes pour que tous les participants apprennent le résultat de la fonction.

Il existe différentes techniques permettant de rendre un protocole comme pmpc juste. On trouve dans [42] et [20] des solutions intéressantes à ce problème. Ces solutions sont évidemment privées, honnêtes et justes selon des définitions consistantes avec celles du protocole pmpc. Le lecteur est invité à y référer pour plus d’information. La solution naturelle consiste à transformer le circuit S qui calcule F en un circuit S′ qui aura pour chaque bit de sortie de S, O(P oly(n)) bits de sortie qui ensemble lui seront équivalents. Ces bits de sortie devront être tels que leur révélation séquentielle divulgue lentement le résultat de F à tous.

4.4 Validité

Dans cette section, les propriétés du protocole d’évaluation de circuit multi-parties sur des données secrètes seront étudiées. Nous montrerons que le protocole est correct, privé, honnête et juste tel que défini au début du chapitre. Les arguments ne feront pas appel à des simulateurs comme c’est souvent le cas pour ce genre de protocole. Une approche plus directe sera utilisée. Les propriétés du pmpc seront déduites des propriétés des sous-protocoles qui sont nécessaires à sa réalisation. C’est cette approche qui a aussi été utilisée avec les sous-protocoles eux-mêmes. Ce processus récursif s’arrête avec les procédures de base, soit la mise en gage et le transfert inconscient, décrits dans le chapitre 2. Leur existence et leurs propriétés sont supposées et c’est sur eux que s’appuient tous les protocoles de ce mémoire. Rappelons que l’existence d’un canal de diffusion fiable est aussi supposée.

4.4.1 Le protocole est correct

Rappelons que le protocole est correct si en le respectant les P participants arrivent bien à apprendre y = F (x_{1}, ..., x_{N}). Les opérations not et and sont correctes et donc, si les participants suivent le protocole et évaluent le circuit calculant la fonction, il leur est garanti que ce qu’ils calculent est bien F (x_{1}, ..., x_{N}). Il suffit donc que le protocole de révélation utilisé soit correct pour que le protocole pmpc le soit aussi.

4.4.2 Le protocole est privé

Rappelons que le protocole est privé si la seule information qu’un groupe de participants G peut obtenir au sujet des x_{i} des autres participants est y et ce qui peut en être logiquement déduit connaissant F et les x_{i} tels que i ∈ G.

Le protocole est privé car avant la révélation, aucune information ne va transpirer. En effet, aucune information ne peut être connue au sujet des bits d’entrée par une coalition de moins de N participants du fait qu’ils sont camouflés dans des dbc. De plus, ni le not ni le and ne pourront être utilisés pour obtenir de l’information du fait que ces protocoles sont eux aussi privés. Il suffit donc que la phase de révélation ne dévoile que le résultat pour que le protocole soit privé.

4.4.3 Le protocole est honnête

Rappelons que le protocole est honnête si un participant sait quand il n’apprend pas le résultat de la fonction.

Ce qui est important ici est qu’il soit impossible à un groupe de participants de faire croire à un ou plusieurs participants que la fonction a été évaluée de façon correcte si ce n’est pas le cas. Il ne faut pas oublier que les participants peuvent s’engager à une valeur de leur choix au début du protocole. Ce sera donc la seule façon à leur disposition pour influencer le résultat de l’évaluation.

Une fois un dbc construit, il est impossible d’en changer la valeur. De plus, le and et le not sont honnêtes. Il suffit donc encore une fois que la phase de révélation soit elle-même honnête pour que pmpc le soit.

4.4.4 Le protocole est juste

Rappelons que le protocole est juste si le fait qu’un participant apprenne F (x_{1}, ..., x_{N}) implique que tous l’apprennent.

Cette caractéristique est surtout liée à la révélation du résultat. En fait, comme nous l’avons vu plus tôt, aucune information quelle qu’elle soit n’est révélée au sujet du résultat avant l’étape de révélation. Si le protocole s’arrête avant cette étape, aucun groupe de moins de N participants ne pourra apprendre le résultat de la fonction, sauf bien entendu si le résultat est parfaitement défini par leurs entrées. Donc le protocole sera juste si l’étape de révélation est faite de façon correcte.

4.5 Complexité

Le transfert inconscient ((_{2}^{1})-ot) est la procédure de base sur laquelle repose pmpc. En pratique, il est parfois plus facile d’implanter bc et même bcx que (_{2}^{1})-ot. Nous donnerons donc une analyse de complexité pour le cas où seulement (_{2}^{1})-ot est directement disponible, le cas où (_{2}^{1})-ot et bc sont disponibles et le cas où (_{2}^{1})-ot et bcx sont disponibles.

Il est facile de voir que l’évaluation du circuit F composé de m portes nécessitera: creation, not et and confondus, O(m) opération sur des dbc. L’opération la plus coûteuse sur les dbc est le and et donc la complexité du protocole est égale à l’évaluation de O(m) and.

Voici un tableau récapitulatif des coûts de chacun des sous-protocoles:

Procédure (_{2}^{1})-ot  (_{2}^{1})-ot  bc  (_{2}^{1})-ot  bcx
bc  O(n)  1  1
bcx  O(n^{2})  O(n)  1
gcot actif O(Nn^{3})  O(n)  O(Nn^{2})  O(n)  O(Nn)
gcot passif O(n^{3})  O(n^{2})  O(n)
pand passif O(Nn^{3})  O(n)  O(Nn^{2})  O(n)  O(Nn)
pand actif O(n^{3})  O(n^{2})  O(n)
AND  O(N^{2}n^{3})  O(Nn) O(N^{2}n^{2})  O(Nn) O(N^{2}n log n)
pmpc  O(mN^{2}n^{3}) O(mNn) O(mN^{2}n^{2}) O(mNn) O(m(N^{2}n + n log n))

Fig. 4.2 - Complexité

Chapitre 5

Conclusion

Durant le siècle dernier, l’homme a pris pleinement conscience de son pouvoir sur la matière. La vaste étendue de ses constructions en témoigne. Nous modifions notre environnement d’une façon de plus en plus profonde et il ne semble pas y avoir de limite à notre capacité créatrice. Ce n’est que plus récemment, particulièrement avec l’avènement de l’informatique, que nous avons pris conscience de l’importance d’une entité plus subtile mais tout aussi réelle: l’information.

L’information occupe de plus en plus de place dans nos vies. La fulgurante augmentation de notre capacité de communication associée à notre capacité de stockage, de gestion et de manipulation de cette matière malléable nous ouvre de nouveaux horizons. Nous vivons la révolution informatique.

La révolution industrielle a modifié nos vies d’une façon si dramatique qu’il nous est maintenant difficile d’en faire la pleine mesure. La révolution informatique pourrait s’avérer tout aussi marquante. Il est de plus en plus évident que l’information mène le monde moderne. Il faut prendre des décisions rapides et ceux qui contrôlent l’information contrôlent par extension les décisions que nous prenons.

Une savante manipulation de l’information peut changer le cours d’une guerre. Elle peut permettre à des empires de s’écrouler et à d’autres de naître. Sa judicieuse utilisation nous permettra de modeler notre avenir et ainsi, souhaitons-le, de mieux vivre.

Il faudra que la société s’adapte. La quantité de données concernant les individus qui se trouve stockée électroniquement est impressionnante. Si un quelconque être malicieux rassemblait toute l’information qui nous est associée, il connaîtrait sur notre vie des détails que même nos proches ignorent. Il aurait probablement accès à notre adresse, notre revenu, nos dépenses, nos voyages, les restaurants que nous fréquentons, à qui nous téléphonons, à quelle heure et combien de temps, quels sont les films que nous avons emprunter à notre club vidéo, notre dossier fiscal, judiciaire, médical, scolaire ou bancaire, si nous respectons les règles de stationnement, si nous avons eu des contraventions, quels sont les journaux, revues et périodiques auxquels nous sommes abonnés, de quel parti politique nous sommes membre, etc. Si de plus nous sommes connectés à un réseau informatique à notre travail, tout notre courrier, nos fichiers et notre horaire pourraient en être déduits.

Bref, aujourd’hui, pratiquement tout ce qui nous concerne est stocké quelque part et tout porte a croire que cela va s’accentuer. L’énumération qui précède est bien courte en comparaison avec ce que pourrait être la réalité. Et ce, sans compter les recoupements qui pourraient aussi être faits entre l’information concernant plusieurs individus et des techniques d’analyse statistique complexes qui pourraient permettre de percer encore plus profondément notre intimité.

Heureusement, il ne semble pas possible à un individu d’accéder à toute cette information. Il n’en demeure pas moins qu’il est assez facile d’en obtenir une bonne partie. Cela a d’ailleurs parfois des conséquences anodines comme la réception de publicité personnalisée ou d’autre forme de sollicitation. Mais jusqu’où cela peutil aller? Les gens s’interrogent déjà sur ces problèmes. Le cinéma est en général un bon indicateur social et les films comme: “The Conversation”, “Brazil”, “1984”, “Snickers”, “Johnny Mnemonique”, “The Net” témoignent de l’attention portée par la population à cette réalité.

D’un autre côté, il faut aussi réaliser que notre sécurité est parfois liée à la capacité de la société d’accéder à cette information. Nous désirons tous que les criminels dangereux puissent être repérés et mis hors d’état de nuire. Nous voudrions en fait pouvoir les repérer, prévoir et prévenir leurs actions. Mais si cela était possible, il serait insupportable qu’à chaque fois que nous dépassions la limite de vitesse légale en voiture, une contravention nous soit automatiquement facturée. Les lois et la capacité d’intervention des instances policières devront s’harmoniser avec notre capacité grandissante à repérer les contrevenants. Beaucoup d’interdictions dans nos sociétés ont pour but d’éviter les abus. Le contrôle total des individus n’est pas l’objectif à atteindre.

Comment la société peut-elle à la fois prévenir les actions néfastes de certains individus et se garder d’intervenir dans notre vie privée? Comme nous l’avons vu dans les chapitres précédents, la cryptologie apporte des solutions qui vont bien plus loin que la communication secrète. Les preuves à divulgation nulle et le calcul multi-parties pourront permettre à des organismes un traitement de l’information sans y avoir directement accès. Un individu accusé de meurtre pourrait, par exemple, prouver qu’il n’était pas sur les lieux du crime, sans révéler l’endroit où il se trouvait. De façon plus réaliste, on peut imaginer un dossier médical qui répond uniquement aux questions posées par un médecin en service et dûment autorisé. Il sera aussi possible d’effectuer des paiements dans l’anonymat et quand même recevoir la marchandise. Aussi, on pourra faire des statistiques sans poser de questions indiscrètes. En fait, une foule d’opérations qui nécessitent aujourd’hui l’accumulation d’informations pourront être réalisées de façon anonyme et fiable.

Dans un monde idéal, un certain nombre d’organismes, suffisamment large pour satisfaire toute la population et suffisamment restreint pour être pratique, pourrait gérer toute l’information qui nous concerne. Chez nous, ces organismes pourraient par exemple être les différents partis politiques, le gouvernement, les banques, les juges, les médecins, une association de protection des consommateurs, l’église et quelques autres. À eux tous, ils pourraient répondre aux requêtes nous concernant, mais isolés, ils ne pourraient rien manigancer. Ces institutions ne pourraient servir leurs intérêts aux dépends des autres mais surtout, il faudrait infiltrer simultanément tous ces organismes pour accéder à l’information qu’ils possèdent ensemble, ce qui est plus difficile que d’en infiltrer une seule, surtout pour leurs employés.

Il suffira d’avoir confiance en une seule de ces institutions pour dormir tranquille. L’important, c’est que l’information existe et puisse éventuellement être utilisée si cela est nécessaire, justifié et autorisé.

L’implantation de la cryptologie à grande échelle se heurte à des barrières techniques. Heureusement, ces difficultés peuvent être surmontées assez facilement. Le protocole pmpc présenté dans ce mémoire est d’ailleurs assez efficace et général pour répondre à des besoins réels. Il serait concevable pour un groupe d’institutions comme celui cité plus haut d’accumuler dans des dbc de l’information au sujet de chaque individu. Ils pourraient alors d’un commun accord effectuer les opérations nécessaires au bon fonctionnement de la société.

L’explosion démographique à l’intérieur du réseau Internet et l’accès plus facile à des ressources cryptographiques permettent d’espérer des changements majeurs dans le traitement de l’information. Nos notions de justice, de tolérance et de propriété devront s’ajuster à tous ces changements, mais tout cela se fera je l’espère dans le respect et le renforcement de la démocratie et de notre intimité.

Bibliographie

[1] D. Beaver. Secure multiparty protocols and zero-knowledge proof systems tolerating a faulty minority. Journal of Cryptology, 4(2), 1991.

[2] M. Bellare et S. Micali. Non-interactive oblivious transfer and applications. Dans G. Brassard, éditeur, Proc. CRYPTO 89, pages 547–559. Springer-Verlag, 1990. Lecture Notes in Computer Science No. 435.

[3] M. Ben-Or, S. Goldwasser, et A. Wigderson. Completeness theorems for fault-tolerant distributed computing. Dans Proc. 20th ACM Symp. on Theory of Computing, pages 1–10, Chicago, 1988. ACM.

[4] C. H. Bennett et G. Brassard. An update on quantum cryptography. Dans G. R. Blakley et D. C. Chaum, éditeurs, Proc. CRYPTO 84, pages 475–480. Springer-Verlag, 1985. Lecture Notes in Computer Science No. 196.

[5] C. H. Bennett, G. Brassard, S. Breidbard, et S. Wiesner. Quantum cryptography, or unforgeable subway tokens. Dans R. L. Rivest, A. Sherman, et D. Chaum, éditeurs, Proc. CRYPTO 82, pages 267–275, New York, 1983. Plenum Press.

[6] C. H. Bennett, G. Brassard, C. Crépeau, et M.-H. Skubiszewska. Practical quantum oblivious transfer. Dans J. Feigenbaum, éditeur, Proc. CRYPTO 91, pages 351–366. Springer-Verlag, 1992. Lecture Notes in Computer Science No. 576.

[7] C. H. Bennett, G. Brassard, et J.-M. Robert. Privacy amplification by public discussion. SIAM J. Computing, 17(2):210–229, Avr. 1988.

[8] M. Blum. Coin flipping by telephone. Dans Proc. IEEE Spring COMPCOM, pages 133–137. IEEE, 1982.

[9] G. Brassard. Cryptologie Contemporaine. Masson, 1993.

[10] G. Brassard. Cryptology column — quantum cryptography: A bibliography. Sigact News, 24(3), 1993.

[11] G. Brassard. A bibliography of quantum cryptography.

http://www.iro.umontreal.ca/people/crepeau/Biblio-QC.html, Laboratoire d’Informatique Théorique et Quantique, 1995.

[12] G. Brassard, D. Chaum, et C. Crépeau. Minimum disclosure proofs of knowledge. Journal of Computer and System Sciences, 37(2):156–189, 1988.

[13] G. Brassard et C. Crépeau. Quantum bit commitment and coin tossing protocols. Dans A. Menezes et S. A. Vanstone, éditeurs, Proc. CRYPTO 90, pages 49–61. Springer-Verlag, 1991. Lecture Notes in Computer Science No. 537.

[14] G. Brassard, C. Crépeau, et J.-M. Robert. All-or-nothing disclosure of secrets. Dans A. Odlyzko, éditeur, Proc. CRYPTO 86, pages 234–238. Springer-Verlag, 1987. Lecture Notes in Computer Science No. 263.

[15] G. Brassard, C. Crépeau, R. Jozsa, et D. Langlois. A quantum bit commitment scheme provably unbreakable by both parties. Dans Proc. 34th IEEE Symp. on Foundations of Comp. Science, pages 362–371. IEEE, 1992.

[16] D. Chaum. Untraceable electronic mail, return addresses, and digital pseudonyms. Communications of the ACM, 24:84–88, 1981.

[17] D. Chaum. The spymasters double-agent problem: Multiparty computations secure unconditionally from minorities and cryptographically from majorities. Dans G. Brassard, éditeur, Proc. CRYPTO 89, pages 591–603. Springer-Verlag, 1990. Lecture Notes in Computer Science No. 435.

[18] D. Chaum, C. Crépeau, et I. Damgård. Multi-party unconditionally secure protocols. Dans Proc. 20th ACM Symp. on Theory of Computing, Chicago, 1988. ACM.

[19] D. Chaum, I. Damgård, et J. van de Graaf. Multiparty computations ensuring privacy of each party’s input and correctness of the result. Dans Proc. CRYPTO 87. Springer-Verlag, 1988.

[20] R. Cleve. Controlled gradual disclosure schemes for random bits and their applications. Dans G. Brassard, éditeur, Proc. CRYPTO 89, pages 573–588. Springer-Verlag, 1990. Lecture Notes in Computer Science No. 435.

[21] C. Crépeau. A secure poker protocol that minimizes the effect of player coalitions. Dans H. C. Williams, éditeur, Proc. CRYPTO 85, pages 73–86. Springer-Verlag, 1986. Lecture Notes in Computer Science No. 218.

[22] C. Crépeau. Equivalence between two flavours of oblivious transfers. Dans C. Pomerance, éditeur, Proc. CRYPTO 87, pages 350–354. Springer-Verlag, 1988. Lecture Notes in Computer Science No. 293.

[23] C. Crépeau. Correct and Private Reductions Among Oblivious Transfers. PhD thesis, Massachusetts Institute of Technology, 1990.

[24] C. Crépeau. Verifiable disclosure of secrets and applications. Dans C. Pomerance, éditeur, Proc. EUROCRYPT 89, pages 181–191. Springer-Verlag, 1990.

[25] C. Crépeau. Cryptographic protocols based on noisy channel. En préparation, 1995.

[26] C. Crépeau et J. Kilian. Weakening security assumptions and oblivious transfer. Dans S. Goldwasser, éditeur, Proc. CRYPTO 88, pages 2–7. Springer-Verlag, 1988. Lecture Notes in Computer Science No. 403.

[27] C. Crépeau et L. Salvail. Quantum oblivious mutual identification. Dans Proc. EUROCRYPT 95, pages 133–147. Springer-Verlag, 1995.

[28] I. Damgård, T. P. Pedersen, et B. Pfitzmann. On the existence of statistically hiding bit commitment schemes and fail-stop signatures. Dans D. R. Stinson, éditeur, Proc. CRYPTO 93, pages 250–265. Springer, 1994. Lecture Notes in Computer Science No. 773.

[29] W. Diffie. The first ten years of public-key cryptography. 1992. dans [52].

[30] W. Diffie et M. E. Hellman. New directions in cryptography. IEEE Trans. Inform. Theory, IT-22:644–654, Nov. 1976.

[31] S. Even, O. Goldreich, et A. Lempel. A randomized protocol for signing contracts. Dans R. L. Rivest, A. Sherman, et D. Chaum, éditeurs, Proc. CRYPTO 82, pages 205–210, New York, 1983. Plenum Press.

[32] M. Franklin. Complexity and Security of Distributed Protocols. PhD thesis, Computer Science Department, Columbia University, New York, 1993.

[33] G.D.Forney. Concatenated Codes. M.I.T. Press, 1966.

[34] O. Goldreich, S. Micali, et A. Wigderson. How to play any mental game, or: A completeness theorem for protocols with honest majority. Dans Proc. 19th ACM Symp. on Theory of Computing, pages 218–229. ACM, 1987.

[35] O. Goldreich et R. Vainish. How to solve any protocol problem - an efficiency improvement. Dans C. Pomerance, éditeur, Proc. CRYPTO 87, pages 73–86. Springer-Verlag, 1988. Lecture Notes in Computer Science No. 293.

[36] S. Goldwasser et L. Levin. Fair computation of general functions in presence of immoral majority. Dans A. Menezes et S. A. Vanstone, éditeurs, Proc. CRYPTO 90, pages 77–93. Springer-Verlag, 1991. Lecture Notes in Computer Science No. 537.

[37] S. Goldwasser et S. Micali. Probabilistic encryption. Journal of Computer and System Sciences, 28(2):270–299, Avr. 1984.

[38] S. Goldwasser, S. Micali, et C. Rackoff. The knowledge complexity of interactive proof-systems. Dans Proc. 17th ACM Symp. on Theory of Computing, pages 291–304, Providence, 1985. ACM.

[39] J. Kilian. Founding cryptography on oblivious transfer. Dans Proc. 20th ACM Symp. on Theory of Computing, pages 20–31, Chicago, 1988. ACM.

[40] J. Kilian. Uses of Randomness in Algorithms and Protocols, chapitre 3. MIT Press, 1990.

[41] J. Kilian. On the complexity of bounded-interaction and noninteractive zeroknowledge proofs. Dans Proc. 26th ACM Symp. on Theory of Computing, pages 466–477, Santa Fe, 1994. IEEE.

[42] M. Luby, S. Micali, et C. Rackoff. How to simultaneously exchange a secret bit by flipping a symmetrically biased coin. Dans Proc. 24th IEEE Symp. on Foundations of Comp. Science, pages 11–22, Tucson, 1983. IEEE.

[43] F. J. MacWilliams et N. Sloane. The Theory of Error-Correcting Codes. North-Holland, 1977.

[44] M. Naor. Bit commitment using pseudo-randomness. Journal of Cryptology, 4(2):151–158, 1991.

[45] M. Naor, R. Ostrovsky, R. Venkatesan, et M. Yung. Perfect zero-knowledge arguments for np can be based on general complexity assumptions. Dans E. F. Brickell, éditeur, Proc. CRYPTO 92, pages 196–214. Springer-Verlag, 1992. Lecture Notes in Computer Science No. 740.

[46] M. Rabin. How to exchange secrets by oblivious transfer. Rapport Technique TR-81, Harvard Aiken Computation Laboratory, 1981.

[47] T. Rabin et M. Ben-Or. Verifiable secret sharing and multiparty protocols with honest majority. Dans STOC89, pages 73–85, 1989.

[48] R. L. Rivest, A. Shamir, et L. M. Adleman. A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM, 21(2):120–126, 1978.

[49] A. Shamir, R. L. Rivest, et L. M. Adleman. Mental poker. Dans D. Klarner, éditeur, The Mathematical Gardner, pages 37–43. Wadsworth, Belmont, California, 1981.

[50] C. E. Shannon. A mathematical theory of communication. Bell Sys. Tech. J., 27:623–656, 1948.

[51] C. E. Shannon. Communication theory of secrecy systems. Bell Sys. Tech. J., 28:657–715, 1949.

[52] G. Simmons, éditeur. Contemporary Cryptology: The science of Information Integrity. IEEE Press, 1992.

[53] D. A. Spielman. Linear-time encodable and decodable error-correcting codes. Dans Proc. 27th ACM Symp. on Theory of Computing, pages 388–498. ACM, 1995.

[54] S. Wiesner. Conjugate coding. Sigact News, 15(1):78–88, 1983.

[55] A. C.-C. Yao. Theory and application of trapdoor functions. Dans Proc. 23rd IEEE Symp. on Foundations of Comp. Science, pages 80–91, Chicago, 1982. IEEE.

[56] A. C.-C. Yao. Security of quantum protocols against coherent measurements. Dans Proc. 27th ACM Symp. on Theory of Computing, pages 67–82. ACM,