Voir la source de Transfert inconscient

{{ébauche|cryptologie}}

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é ''{{langue|en|How to exchange secrets with oblivious transfer}}''{{sfn|Rabin|1981|loc=Le titre original est ''How to exchange secrets'', mais il est communément cité sous ce titre}}. 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 [[Shimon Even|Even]], [[Oded Goldreich|Goldreich]] et [[Abraham Lempel|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é]]{{sfn|Even|Goldreich|Lempel|1985}}. Ce résultat a ensuite été amélioré par Killian{{sfn|Killian|1988}}, en montrant que le transfert inconscient 1 parmi 2 suffisait à évaluer de manière multipartite n’importe quelle fonction [[P (complexité)|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{{sfn|Crépeau|1987}}. Des résultats similaires ont été montrés par Khurana, Maji et Sahai, en utilisant un [[Deuxième théorème de Shannon|canal bruité]]{{sfn|Khurana|Maji|Sahai|2016}} (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 [[algorithme]]s interactifs{{sfn|Naor|Pinkas|2001}}{{,}}{{sfn|Camenisch|Neven|shelat|2007}}: l’expéditeur <math>S</math> et le destinataire <math>R</math>. L’expéditeur prend en entrée deux messages <math>M_0</math> et <math>M_1</math>, tandis que de destinataire prend en entrée un [[bit (informatique)|bit]] σ. L’interaction entre les deux partis est notée <math>S^{M_0, M_1} \leftrightarrows R^{\sigma}</math>.

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 <math>S^{M_0, M_1} \leftrightarrows R^{0}</math> et <math>S^{M_0, M_1} \leftrightarrows R^{1}</math> 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é <math>M_\sigma</math> ne doit pas être capable de savoir quoi que ce soit sur le message <math>M_{1-\sigma}</math> à l’issue de l’échange.

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

# Alice propose d'envoyer a Bob un message parmi deux disponibles <math>M_0</math> et <math>M_1</math>. 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 <math>N</math>, un exposant public <math>e</math> et un exposant privé <math>d</math>.
# Elle génère également deux messages aléatoires <math>x_0</math> et <math>x_1</math> qu'elle envoie à Bob en même temps que sa clef publique <math>(N, e)</math>.
# Bob choisit le message qu'il souhaite recevoir, indiqué par <math>\sigma \in \{ 0, 1\}</math>. Il sélectionne donc la valeur correspondante <math>x_\sigma</math>.
# Bob génère un nombre aléatoire <math>k</math> et chiffre <math>k</math> avec <math>x_\sigma</math> en calculant <math>v = (x_\sigma + k^e) \mod N</math>, qu'il envoie à Alice.
# Pour Alice, il est impossible de déterminer si Bob a choisi <math>x_0</math> ou <math>x_1</math> pour calculer <math>v</math>, car elle ignore le nombre <math>k</math> généré par Bob . Elle calcule donc les deux valeurs possibles pour <math>k</math> à partir de <math>v</math>: <math>k_0  = (v - x_0)^d\mod N </math> et <math>k_1  = (v - x_1)^d\mod N</math>. L'une de ces deux valeurs est égale au <math>k</math> choisi par Bob (sans qu'Alice sache lequel) et l'autre est une valeur aléatoire qui ne fournit aucune information sur <math>k</math>.Ceci garantit la sécurité du destinataire.
# Alice masque les messages <math>M_0</math> et <math>M_1</math> avec les deux clefs possibles <math>k_0</math> et <math>k_1</math> pour donner <math>M'_0 = M_0 + k_0 </math> et <math>M'_1 = M_1 + k_1 </math>. Ces deux messages sont envoyés à Bob.
# Bob déchiffre le message <math>M'_\sigma</math> avec le <math>k</math> qu'il a choisi, pour obtenir <math>M_\sigma = M'_\sigma - k</math>. Bob est par ailleurs incapable de déchiffrer l'autre message. En effet, il faudrait qu'il puisse calculer l'autre valeur de <math>k</math>, c'est-à-dire <math>k_{1-\sigma}</math>, 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'' ===
{{...}}
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 <math>m</math> secrets <math>s_1, \dots, s_m</math> binaires valant tous soit 0 soit 1<ref group = "note">Dans cette implémentation le secret ne peut être que sur un bit, comme une réponse oui/non à une question fermée.</ref>. On suppose que Bob souhaite connaître le secret <math>s_i</math>.
Un protocole de transfert inconscient peut être le suivant<ref>{{Ouvrage|langue=fr|auteur1=Pascal Boyer|titre=Petit compagnon des nombres et de leurs applications|lieu=Paris|éditeur=Calvage et Mounet|année=2019|pages totales=648|isbn=978-2-916352-75-6|partie=VI. Cryptographie|numéro chapitre=7.8|titre chapitre=Transfert inconscient}}</ref>{{,}}<ref group = "note">Ce protocole est donné à titre pédagogique, il est en effet vulnérable à des attaques.</ref>:
# Alice choisit deux nombres premiers <math>p</math> et <math>q</math> et un nombre <math>a</math> qui n'est pas un [[résidu quadratique]] modulo <math>n = pq</math> et tel que le [[Symbole de Jacobi#Résidus|symbole de Jacobi]] <math>\left(\frac{a}n\right)</math> soit égal à 1<ref group="note">Cette condition est nécessaire pour s'assurer par la suite que Bob ne peut pas tricher : si <math>\left(\frac{a}n\right) = -1</math> ou <math>\left(\frac{a}n\right) = 0</math> Bob peut savoir si les nombres calculés dans la suite du protocole ne sont pas des résidus quadratiques modulo <math>n</math>, alors que si <math>\left(\frac{a}n\right) = 1</math> il ne peut pas conclure. Pour plus de détails, voir l'[[Symbole de Jacobi|article détaillé]].</ref>;
# Alice publie <math>a</math> et <math>n</math> ;
# Alice associe un nombre aléatoire <math>x_i \neq 0</math> à chaque secret <math>s_i</math> et envoie à Bob les <math>m</math> nombres <math>y_i := x_i^2 a^{s_i} \mod n</math> ;
# Bob génère un nombre aléatoire <math>r</math> ainsi qu'un bit aléatoire <math>b \in \{0,1\}</math> et envoie à Alice le nombre <math>\delta_i = y_i r^2 a^b</math><ref group="note">On a donc <math>\delta_i = x_i^2 a^{s_i + b} r^2</math></ref>;
# Alice dit à Bob si le nombre <math>\delta_i</math> est un résidu quadratique modulo <math>n</math>. Si oui, alors <math>s_i = b</math> sinon <math>s_i = 1 - b</math><ref group="note">Comme <math>\delta_i = x_i^2 a^{s_i + b} r^2</math>, <math>\delta_i</math> est un carré si et seulement si <math>s_i + b \in \{0, 2\}</math>.</ref>.

Ce protocole repose essentiellement sur l'idée que [[Problème de la résiduosité quadratique|décider si l'entier <math>\delta_i</math> est un résidu quadratique modulo <math>n</math>]] est aisé si les facteurs premiers de <math>n</math> sont connus<ref name = "shoup"/>, comme c'est le cas d'Alice, et impossible en un temps raisonnable sinon<ref name = "shoup">{{Ouvrage|langue=en|prénom1=Victor|nom1=Shoup|lien auteur1=Victor Shoup|titre=A computational introduction to number theory and algebra|éditeur=[[Cambridge University Press]]|année=2009|numéro d'édition=2|pages totales=580|passage=349|isbn=978-0-521-51644-0|isbn2=0521516447|oclc=277069279|lire en ligne=https://shoup.net/ntb/ntb-v2.pdf|consulté le=2020-02-26|partie=12. Quadratic reciprocity and computing modular square roots|numéro chapitre=4|titre chapitre=Testing quadratic residuosity}}.</ref>, comme dans le cas de Bob.

==== Comparaison avec les PIR ====
Le transfert inconscient 1 parmi ''n'' est donc plus restrictif que les protocoles PIR ({{Lien|langue=en|trad=Private information retrieval|fr=Private information retrieval}}'')'' 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 [[Application sous-linéaire|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''<ref>{{Article|prénom1=Gilles|nom1=Brassard|prénom2=Claude|nom2=Crépeau|prénom3=Jean-Marc|nom3=Robert|titre=All-or-nothing Disclosure of Secrets|périodique=Proceedings on Advances in cryptology—CRYPTO '86|éditeur=Springer-Verlag|date=1987|isbn=9780387180472|lire en ligne=http://dl.acm.org/citation.cfm?id=36664.36681|consulté le=2019-02-20|pages=234–238}}</ref>, 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 ==
{{sources de section|{{en}} ''Oblivious transfer with adaptive queries'' par Moni Naor et Benny Pinkas{{sfn|Naor|Pinkas|1999}}}}
{{...}}

== Notes et références ==
=== Notes ===
{{Traduction/Référence|en|Oblivious transfer|713900607|type=note}}
{{Références|group = "note"}}

=== Références ===
{{Références}}

== Annexes ==
=== Bibliographie ===
* {{article|auteur1=Jan Camenisch|auteur2=Gregory Neven|auteur3=abhi shelat|titre=Simulatable Adaptive Oblivious Transfer|périodique=Eurocrypt|année=2007|doi=10.1007/978-3-540-72540-4_33|libellé=Camenisch, Neven et shelat 2007|pages=573–590}}
* {{article|auteur=Claude Crépeau|titre=Equivalence between two flavours of oblivious transfer|périodique=Crypto|année=1987|pages=350–354|langue=en|libellé=Crépeau 1987|doi=10.1007/3-540-48184-2_30}}
* {{article|auteur1=Shimon Even|auteur2=Oded Goldreich|auteur3=Abraham Lempel|titre=A randomized protocol for signing contracts|doi=10.1145/3812.3818|langue=en|lire en ligne=http://www.lix.polytechnique.fr/~catuscia/teaching/papers_and_books/SigningContracts.pdf|format=PDF|libellé=Even, Goldreich et Lempel 1985|périodique=Communications of the ACM|volume=28|pages=637–647|année=1985}}
* {{article|auteur1=Dakshita Khurana|auteur2=Hemanta K. Maji|auteur3=[[Amit Sahai]]|titre=Secure Computation from Elastic Noisy Channels|périodique=Eurocrypt|année=2016|page=184–212|doi=10.1007/978-3-662-49896-5_7|langue=en|libellé=Khurana, Maji et Sahai 2016|résumé=https://www.youtube.com/watch?v=2d97ZKBUdw4}}
* {{article|auteur=Joe Killian|titre=Founding Cryptography on Oblivious Transfer|périodique=Symposium on the Theory of Computation (STOC)|année=1988|langue=en|doi=10.1145/62212.62215|pages=20–31|libellé=Killian 1988}}
* {{article|auteur1=Moni Naor|auteur2=Benny Pinkas|titre=Oblivious transfer with adaptive queries|périodique=Crypto|année=1999|pages=573–590|langue=en|doi=10.1007/3-540-48405-1_36|libellé=Naor et Pinkas 1999}}
* {{article|auteur1=Moni Naor|auteur2=Benny Pinkas|titre=Efficient Oblivious Transfer|périodique=Symposium on Discrete Algorithms (SODA)|année=2001|pages=448−457|langue=en|isbn=0-89871-490-7|libellé=Naor et Pinkas 2001|lire en ligne=http://www.pinkas.net/PAPERS/effot.ps|format=PS}}
* {{article|auteur=Michael O. Rabin|année=1981|titre=How To Exchange Secrets with Oblivious Transfer|périodique=IACR Museum of Historic Papers|lire en ligne=http://www.iacr.org/museum/rabin-obt.html|format=html|langue=en|libellé=Rabin 1981}}

=== Articles connexes ===
* [[Preuve à divulgation nulle de connaissance]]
* [[Cryptographie symétrique|Cryptographie à clef secrète]]
* [[Calcul multipartite sécurisé]]

{{Portail|Cryptologie}}

[[Catégorie:Primitive cryptographique]]