Transfert inconscient

Cet article est une ébauche concernant la cryptologie.

Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

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é How to exchange secrets with oblivious transfer. 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é. Ce résultat a ensuite été amélioré par Killian, 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 2. Des résultats similaires ont été montrés par Khurana, Maji et Sahai, en utilisant un canal bruité (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 interactifs^,: 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})\mod N$		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{aligned}k_{0}&=(v-x_{0})^{d}\mod N\\k_{1}&=(v-x_{1})^{d}\mod N\end{aligned}}$
Envoi des deux messages à Bob		${\begin{aligned}M'_{0}=M_{0}+k_{0}\\M'_{1}=M_{1}+k_{1}\end{aligned}}$	$\Rightarrow$	$M'_{0},M'_{1}$		Réception des deux messages
					$M_{\sigma }=M'_{\sigma }-k$	Déchiffrement du message $M'_{\sigma }$ , grâce au $x_{\sigma }$ choisi précédemment .

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.
Alice génère une paire de clefs RSA, c'est-à-dire un modulo $N$ , un exposant public $e$ et un exposant privé $d$ .
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)$ .
Bob choisit le message qu'il souhaite recevoir, indiqué par $\sigma \in \{0,1\}$ . Il sélectionne donc la valeur correspondante $x_{\sigma }$ .
Bob génère un nombre aléatoire $k$ et chiffre $k$ avec $x_{\sigma }$ en calculant $v=(x_{\sigma }+k^{e})\mod N$ , qu'il envoie à Alice.
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}\mod N$ et $k_{1}=(v-x_{1})^{d}\mod N$ . 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.
Alice masque les messages $M_{0}$ et $M_{1}$ avec les deux clefs possibles $k_{0}$ et $k_{1}$ pour donner $M'_{0}=M_{0}+k_{0}$ et $M'_{1}=M_{1}+k_{1}$ . Ces deux messages sont envoyés à Bob.
Bob déchiffre le message $M'_{\sigma }$ avec le $k$ qu'il a choisi, pour obtenir $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 $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

Cette section est vide, insuffisamment détaillée ou incomplète. Votre aide est la bienvenue ! Comment faire ?

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 suivant^,:

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;
Alice publie $a$ et $n$ ;
Alice associe un nombre aléatoire $x_{i}\neq 0$ à chaque secret $s_{i}$ et envoie à Bob les $m$ nombres $y_{i}:=x_{i}^{2}a^{s_{i}}\mod n$ ;
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}$ ;
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 (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.

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

Requêtes adaptatives

Les informations suivantes proviennent principalement de (en) Oblivious transfer with adaptive queries par Moni Naor et Benny Pinkas.

Cette section est vide, insuffisamment détaillée ou incomplète. Votre aide est la bienvenue ! Comment faire ?

Notes et références

Notes

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Oblivious transfer » (voir la liste des auteurs).

↑ Dans cette implémentation le secret ne peut être que sur un bit, comme une réponse oui/non à une question fermée.
↑ Ce protocole est donné à titre pédagogique, il est en effet vulnérable à des attaques.
↑ Cette condition est nécessaire pour s'assurer par la suite que Bob ne peut pas tricher : si $\left({\frac {a}{n}}\right)=-1$ ou $\left({\frac {a}{n}}\right)=0$ Bob peut savoir si les nombres calculés dans la suite du protocole ne sont pas des résidus quadratiques modulo $n$ , alors que si $\left({\frac {a}{n}}\right)=1$ il ne peut pas conclure. Pour plus de détails, voir l'article détaillé.
↑ On a donc $\delta _{i}=x_{i}^{2}a^{s_{i}+b}r^{2}$
↑ Comme $\delta _{i}=x_{i}^{2}a^{s_{i}+b}r^{2}$ , $\delta _{i}$ est un carré si et seulement si $s_{i}+b\in \{0,2\}$ .

Références

↑ Rabin 1981, Le titre original est How to exchange secrets, mais il est communément cité sous ce titre.
↑ Even, Goldreich et Lempel 1985.
↑ Killian 1988.
↑ Crépeau 1987.
↑ Khurana, Maji et Sahai 2016.
↑ Naor et Pinkas 2001.
↑ Camenisch, Neven et shelat 2007.
↑ Pascal Boyer, Petit compagnon des nombres et de leurs applications, Paris, Calvage et Mounet, 2019, 648 p. (ISBN 978-2-916352-75-6), VI. Cryptographie, chap. 7.8 (« Transfert inconscient »)
1 2 (en) Victor Shoup, A computational introduction to number theory and algebra, Cambridge University Press, 2009, 2^e éd., 580 p. (ISBN 978-0-521-51644-0 et 0521516447, OCLC 277069279, lire en ligne), 12. Quadratic reciprocity and computing modular square roots, chap. 4 (« Testing quadratic residuosity »), p. 349.
↑ Gilles Brassard, Claude Crépeau et Jean-Marc Robert, « All-or-nothing Disclosure of Secrets », Proceedings on Advances in cryptology—CRYPTO '86, Springer-Verlag,‎ 1987, p. 234–238 (ISBN 9780387180472, lire en ligne, consulté le 20 février 2019)
↑ Naor et Pinkas 1999.

Annexes

Bibliographie

[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])

Articles connexes

Portail de la cryptologie

[8] Dans cette implémentation le secret ne peut être que sur un bit, comme une réponse oui/non à une question fermée.

[10] Ce protocole est donné à titre pédagogique, il est en effet vulnérable à des attaques.

[11] Cette condition est nécessaire pour s'assurer par la suite que Bob ne peut pas tricher : si $\left({\frac {a}{n}}\right)=-1$ ou $\left({\frac {a}{n}}\right)=0$ Bob peut savoir si les nombres calculés dans la suite du protocole ne sont pas des résidus quadratiques modulo $n$ , alors que si $\left({\frac {a}{n}}\right)=1$ il ne peut pas conclure. Pour plus de détails, voir l'article détaillé.

[12] On a donc $\delta _{i}=x_{i}^{2}a^{s_{i}+b}r^{2}$

[13] Comme $\delta _{i}=x_{i}^{2}a^{s_{i}+b}r^{2}$ , $\delta _{i}$ est un carré si et seulement si $s_{i}+b\in \{0,2\}$ .

[Rabin1981Le_titre_original_est_''How_to_exchange_secrets'',_mais_il_est_communément_cité_sous_ce_titre-1] Rabin 1981, Le titre original est How to exchange secrets, mais il est communément cité sous ce titre.

[EvenGoldreichLempel1985-2] Even, Goldreich et Lempel 1985.

[Killian1988-3] Killian 1988.

[Crépeau1987-4] Crépeau 1987.

[KhuranaMajiSahai2016-5] Khurana, Maji et Sahai 2016.

[NaorPinkas2001-6] Naor et Pinkas 2001.

[CamenischNevenshelat2007-7] Camenisch, Neven et shelat 2007.

[9] Pascal Boyer, Petit compagnon des nombres et de leurs applications, Paris, Calvage et Mounet, 2019, 648 p. (ISBN 978-2-916352-75-6), VI. Cryptographie, chap. 7.8 (« Transfert inconscient »)

[shoup-14] 1 2 (en) Victor Shoup, A computational introduction to number theory and algebra, Cambridge University Press, 2009, 2^e éd., 580 p. (ISBN 978-0-521-51644-0 et 0521516447, OCLC 277069279, lire en ligne), 12. Quadratic reciprocity and computing modular square roots, chap. 4 (« Testing quadratic residuosity »), p. 349.

[15] Gilles Brassard, Claude Crépeau et Jean-Marc Robert, « All-or-nothing Disclosure of Secrets », Proceedings on Advances in cryptology—CRYPTO '86, Springer-Verlag,‎ 1987, p. 234–238 (ISBN 9780387180472, lire en ligne, consulté le 20 février 2019)

[NaorPinkas1999-16] Naor et Pinkas 1999.