Transfert inconscient

Le transfert inconscient (oblivious transfer, en anglais) est une primitive cryptographique où un expéditeur transmet une information, sélectionnée parmi plusieurs envois possibles, à un destinataire, sans que l'expéditeur puisse connaître le choix du destinataire, ni que le destinataire puisse connaître les informations qu'il n'a pas demandées. Par exemple, Wikipédia propose plusieurs articles ; avec le transfert inconscient, un utilisateur peut demander à consulter un article sans que Wikipédia puisse savoir quel article a été consulté.

Cette primitive a été introduite en 1981 par Michael Rabin, dans un manuscrit intitulé Modèle:LangueModèle:Sfn. Dans la version de Rabin, basée sur le chiffrement RSA, l’expéditeur transmet un message que le destinataire reçoit avec une probabilité de 1/2, sans que l'expéditeur puisse savoir si la réception a eu lieu ou non. En 1985, les travaux de Even, Goldreich et Lempel ont proposé une version améliorée du transfert inconscient 1 parmi 2 qui permettait de réaliser de manière sécurisée du calcul multipartite sécuriséModèle:Sfn. Ce résultat a ensuite été amélioré par KillianModèle:Sfn, en montrant que le transfert inconscient 1 parmi 2 suffisait à évaluer de manière multipartite n’importe quelle fonction en temps polynomial. Ce résultat est une des raisons de l’intérêt existant autour de cette primitive.

Définition

La définition de Michael Rabin consistait en un protocole tel que l'expéditeur envoyait un message M au destinataire, mais avec une probabilité 1/2 de perdre le message. L’expéditeur ne savait pas si son message était arrivé à bon port. Claude Crépeau a montré que cette définition était équivalente à celle utilisée dans sa définition courante: le transfert inconscient 1 parmi 2Modèle:Sfn. Des résultats similaires ont été montrés par Khurana, Maji et Sahai, en utilisant un canal bruitéModèle:Sfn (avec un taux d'erreur strictement inférieur à 1/2).

Transfert inconscient 1 parmi 2

Un schéma de transfert inconscient est donné par deux algorithmes interactifsModèle:SfnModèle:,Modèle:Sfn: l’expéditeur $S$ et le destinataire $R$. L’expéditeur prend en entrée deux messages $M_0$ et $M_1$, tandis que de destinataire prend en entrée un bit σ. L’interaction entre les deux partis est notée $S^{M_0,M_1}\leftrightarrows R^{\sigma }$.

Les notions de sécurité associées sont la sécurité de l’expéditeur et la sécurité du destinataire.

• La sécurité du destinataire requiert que les distributions $S^{M_0,M_1}\leftrightarrows R^0$ et $S^{M_0,M_1}\leftrightarrows R^1$ soient indistinguables. Ce qui traduit le fait que l’expéditeur est incapable de savoir quel message le destinataire a demandé.
• La sécurité de l’expéditeur quant-à-elle traduit le fait que l’expéditeur ayant demandé $M_{\sigma }$ ne doit pas être capable de savoir quoi que ce soit sur le message $M_{1-\sigma }$ à l’issue de l’échange.

Alice ($S$)				Bob ($R$)
Calculs	Secret	Public		Public	Secret	Calculs
Messages à envoyer	$M_0,M_1$
Création d'une paire de clefs RSA et envoi de la clef publique à Bob	$d$	$N,e$	$\Rightarrow$	$N,e$		Réception de la clef publique d'Alice
Génération de deux messages aléatoires		$x_0,x_1$	$\Rightarrow$	$x_0,x_1$		Réception de deux messages aléatoires
					$k,\sigma$	Choix de $\sigma \in \{0,1\}$ et génération d'un nombre aléatoire $k$
		$v$	$\Leftarrow$	$v=(x_{\sigma }+k^e)modN$		Calcul du chiffrement de $k$ avec $x_{\sigma }$ et envoi du résultat à Alice
Calcul des deux valeurs possibles pour $k$, dont une seule correspond à celle de Bob	$\begin{array}{cc}{k}_0& =(v-x_0{)}^{d}modN\\ k_1& =(v-x_1{)}^{d}modN\end{array}$
Envoi des deux messages à Bob		$\begin{array}{c}M{\text{'}}_0=M_0+k_0\\ M{\text{'}}_1=M_1+k_1\end{array}$	$\Rightarrow$	$M{\text{'}}_0,M{\text{'}}_1$		Réception des deux messages
					$M_{\sigma }=M{\text{'}}_{\sigma }-k$	Déchiffrement du message $M{\text{'}}_{\sigma }$, grâce au $x_{\sigma }$ choisi précédemment .

1. Alice propose d'envoyer a Bob un message parmi deux disponibles $M_0$ et $M_1$. Bob souhaite choisir l'un des deux messages à recevoir, sans qu'Alice puisse savoir lequel.
2. Alice génère une paire de clefs RSA, c'est-à-dire un modulo $N$, un exposant public $e$ et un exposant privé $d$.
3. Elle génère également deux messages aléatoires $x_0$ et $x_1$ qu'elle envoie à Bob en même temps que sa clef publique $(N,e)$.
4. Bob choisit le message qu'il souhaite recevoir, indiqué par $\sigma \in \{0,1\}$. Il sélectionne donc la valeur correspondante $x_{\sigma }$.
5. Bob génère un nombre aléatoire $k$ et chiffre $k$ avec $x_{\sigma }$ en calculant $v=(x_{\sigma }+k^e)modN$, qu'il envoie à Alice.
6. Pour Alice, il est impossible de déterminer si Bob a choisi $x_0$ ou $x_1$ pour calculer $v$, car elle ignore le nombre $k$ généré par Bob . Elle calcule donc les deux valeurs possibles pour $k$ à partir de $v$: $k_0=(v-x_0{)}^{d}modN$ et $k_1=(v-x_1{)}^{d}modN$. L'une de ces deux valeurs est égale au $k$ choisi par Bob (sans qu'Alice sache lequel) et l'autre est une valeur aléatoire qui ne fournit aucune information sur $k$.Ceci garantit la sécurité du destinataire.
7. Alice masque les messages $M_0$ et $M_1$ avec les deux clefs possibles $k_0$ et $k_1$ pour donner $M{\text{'}}_0=M_0+k_0$ et $M{\text{'}}_1=M_1+k_1$. Ces deux messages sont envoyés à Bob.
8. Bob déchiffre le message $M{\text{'}}_{\sigma }$ avec le $k$ qu'il a choisi, pour obtenir $M_{\sigma }=M{\text{'}}_{\sigma }-k$. Bob est par ailleurs incapable de déchiffrer l'autre message. En effet, il faudrait qu'il puisse calculer l'autre valeur de $k$, c'est-à-dire $k_{1-\sigma }$, ce qu'il ne peut faire sans la clef privée d'Alice. Ceci garantit la sécurité de l'expéditeur.

Transfert inconscient 1 parmi n et k parmi n

Modèle:... Le transfert inconscient 1 parmi n peut être généralisé à partir du protocole 1 parmi 2 détaillé ci-dessus. L’expéditeur dispose de n messages et le destinataire choisit un indice i entre 0 et n - 1 correspondant au message qu'il souhaite recevoir, toujours sans que l'expéditeur puisse savoir quel message a été choisi, ni que le destinataire puisse prendre connaissance d'un autre message que celui qu'il a sélectionné. D'autres implémentations sont également possibles.

Autre exemple d'implémentation de 1 parmi n

On suppose qu'Alice possède $m$ secrets $s_1,\dots ,s_m$ binaires valant tous soit 0 soit 1. On suppose que Bob souhaite connaître le secret $s_i$. Un protocole de transfert inconscient peut être le suivantModèle:,:

1. Alice choisit deux nombres premiers $p$ et $q$ et un nombre $a$ qui n'est pas un résidu quadratique modulo $n=pq$ et tel que le symbole de Jacobi $\left(\frac{a}{n}\right)$ soit égal à 1;
2. Alice publie $a$ et $n$ ;
3. Alice associe un nombre aléatoire $x_i\ne 0$ à chaque secret $s_i$ et envoie à Bob les $m$ nombres $y_i:=x_i^2{a}^{s_i}modn$ ;
4. Bob génère un nombre aléatoire $r$ ainsi qu'un bit aléatoire $b\in \{0,1\}$ et envoie à Alice le nombre ${\delta }_i=y_i{r}^2{a}^b$;
5. Alice dit à Bob si le nombre ${\delta }_i$ est un résidu quadratique modulo $n$. Si oui, alors $s_i=b$ sinon $s_i=1-b$.

Ce protocole repose essentiellement sur l'idée que décider si l'entier ${\delta }_i$ est un résidu quadratique modulo $n$ est aisé si les facteurs premiers de $n$ sont connus, comme c'est le cas d'Alice, et impossible en un temps raisonnable sinon, comme dans le cas de Bob.

Comparaison avec les PIR

Le transfert inconscient 1 parmi n est donc plus restrictif que les protocoles PIR (Modèle:Lien) qui n'exigent que la sécurité du destinataire (l'expéditeur ne peut savoir quel message a bien été transmis). En revanche, les protocoles PIR sont généralement plus économes en ce qui concerne la quantité de données effectivement transmises. En effet, dans le protocole 1 parmi n, Alice envoie nécessairement les n messages à Bob (même s'il ne peut en lire qu'un seul), alors que les protocoles PIR sont souvent sous-linéaire en n.

Généralisation

Gilles Brassard, Claude Crépeau et Jean-Marc Robert ont proposé une généralisation au transfert k parmi n, dans laquelle le destinataire peut sélectionner plus d'un message parmi ceux proposés par l'expéditeur. Les k messages peuvent être reçus simultanément ou consécutivement, chaque nouveau message pouvant être choisi selon les messages reçus précédemment

Annexes

Bibliographie

• Modèle:Article
• Modèle:Article
• Modèle:Article
• Modèle:Article
• Modèle:Article
• Modèle:Article
• Modèle:Article
• Modèle:Article

Articles connexes

• Preuve à divulgation nulle de connaissance
• Cryptographie à clef secrète
• Calcul multipartite sécurisé