Transfert inconscient

Un schéma de transfert inconscient est donné par deux algorithmes interactifs[6][7]: l’expéditeur ${\displaystyle S}$ et le destinataire ${\displaystyle R}$. L’expéditeur prend en entrée deux messages ${\displaystyle M_{0}}$ et ${\displaystyle M_{1}}$, tandis que de destinataire prend en entrée un bit σ. L’interaction entre les deux partis est notée ${\displaystyle 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 ${\displaystyle S^{M_{0},M_{1}}\leftrightarrows R^{0}}$ et ${\displaystyle 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é ${\displaystyle M_{\sigma }}$ ne doit pas être capable de savoir quoi que ce soit sur le message ${\displaystyle M_{1-\sigma }}$ à l’issue de l’échange.

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

1. Alice propose d'envoyer a Bob un message parmi deux disponibles ${\displaystyle M_{0}}$ et ${\displaystyle 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 ${\displaystyle N}$, un exposant public ${\displaystyle e}$ et un exposant privé ${\displaystyle d}$.
3. Elle génère également deux messages aléatoires ${\displaystyle x_{0}}$ et ${\displaystyle x_{1}}$ qu'elle envoie à Bob en même temps que sa clef publique ${\displaystyle (N,e)}$.
4. Bob choisit le message qu'il souhaite recevoir, indiqué par ${\displaystyle \sigma \in \{0,1\}}$. Il sélectionne donc la valeur correspondante ${\displaystyle x_{\sigma }}$.
5. Bob génère un nombre aléatoire ${\displaystyle k}$ et chiffre ${\displaystyle k}$ avec ${\displaystyle x_{\sigma }}$ en calculant ${\displaystyle v=(x_{\sigma }+k^{e})\mod N}$, qu'il envoie à Alice.
6. Pour Alice, il est impossible de déterminer si Bob a choisi ${\displaystyle x_{0}}$ ou ${\displaystyle x_{1}}$ pour calculer ${\displaystyle v}$, car elle ignore le nombre ${\displaystyle k}$ généré par Bob . Elle calcule donc les deux valeurs possibles pour ${\displaystyle k}$ à partir de ${\displaystyle v}$: ${\displaystyle k_{0}=(v-x_{0})^{d}\mod N}$ et ${\displaystyle k_{1}=(v-x_{1})^{d}\mod N}$. L'une de ces deux valeurs est égale au ${\displaystyle k}$ choisi par Bob (sans qu'Alice sache lequel) et l'autre est une valeur aléatoire qui ne fournit aucune information sur ${\displaystyle k}$.Ceci garantit la sécurité du destinataire.
7. Alice masque les messages ${\displaystyle M_{0}}$ et ${\displaystyle M_{1}}$ avec les deux clefs possibles ${\displaystyle k_{0}}$ et ${\displaystyle k_{1}}$ pour donner ${\displaystyle M'_{0}=M_{0}+k_{0}}$ et ${\displaystyle M'_{1}=M_{1}+k_{1}}$. Ces deux messages sont envoyés à Bob.
8. Bob déchiffre le message ${\displaystyle M'_{\sigma }}$ avec le ${\displaystyle k}$ qu'il a choisi, pour obtenir ${\displaystyle M_{\sigma }=M'_{\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 ${\displaystyle k}$, c'est-à-dire ${\displaystyle 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.

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.

On suppose qu'Alice possède ${\displaystyle m}$ secrets ${\displaystyle s_{1},\dots ,s_{m}}$ binaires valant tous soit 0 soit 1[note 1]. On suppose que Bob souhaite connaître le secret ${\displaystyle s_{i}}$. Un protocole de transfert inconscient peut être le suivant[8] - [note 2]:

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

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

Le transfert inconscient 1 parmi n est donc plus restrictif que les protocoles PIR (Private information retrieval (en)) 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.

Gilles Brassard, Claude Crépeau et Jean-Marc Robert ont proposé une généralisation au transfert k parmi n[10], 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

• [Camenisch, Neven et shelat 2007] Jan Camenisch, Gregory Neven et abhi shelat, « Simulatable Adaptive Oblivious Transfer », Eurocrypt,‎ 2007, p. 573–590 (DOI 10.1007/978-3-540-72540-4_33)
• [Crépeau 1987] (en) Claude Crépeau, « Equivalence between two flavours of oblivious transfer », Crypto,‎ 1987, p. 350–354 (DOI 10.1007/3-540-48184-2_30)
• [Even, Goldreich et Lempel 1985] (en) Shimon Even, Oded Goldreich et Abraham Lempel, « A randomized protocol for signing contracts », Communications of the ACM, vol. 28,‎ 1985, p. 637–647 (DOI 10.1145/3812.3818, lire en ligne [PDF])
• [Khurana, Maji et Sahai 2016] (en) Dakshita Khurana, Hemanta K. Maji et Amit Sahai, « Secure Computation from Elastic Noisy Channels », Eurocrypt,‎ 2016, p. 184–212 (DOI 10.1007/978-3-662-49896-5_7, résumé)
• [Killian 1988] (en) Joe Killian, « Founding Cryptography on Oblivious Transfer », Symposium on the Theory of Computation (STOC),‎ 1988, p. 20–31 (DOI 10.1145/62212.62215)
• [Naor et Pinkas 1999] (en) Moni Naor et Benny Pinkas, « Oblivious transfer with adaptive queries », Crypto,‎ 1999, p. 573–590 (DOI 10.1007/3-540-48405-1_36)
• [Naor et Pinkas 2001] (en) Moni Naor et Benny Pinkas, « Efficient Oblivious Transfer », Symposium on Discrete Algorithms (SODA),‎ 2001, p. 448−457 (ISBN 0-89871-490-7, lire en ligne [ps])
• [Rabin 1981] (en) Michael O. Rabin, « How To Exchange Secrets with Oblivious Transfer », IACR Museum of Historic Papers,‎ 1981 (lire en ligne [html])

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