Transfert inconscient

Le transfert inconscient (oblivious transfert 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 connaitre 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 ne 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[1]. 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 le transfert inconscient 1 parmi 2 qui permettait de réaliser de manière sécurisé du calcul multipartite sécurisé[2]. Ce résultat a ensuite été amélioré par Killian[3], 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éfinitionModifier

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[4]. Des résultats similaires ont été montrés par Khurana, Maji et Sahai, en utilisant un canal bruité[5] (avec un taux d'erreur strictement inférieur à 1/2).

Transfert inconscient 1 parmi 2Modifier

Un schéma de transfert inconscient est donné par deux algorithmes interactifs[6][7]: l’expéditeur   et le destinataire  . L’expéditeur prend en entrée deux messages   et  , tandis que de destinataire prend en entrée un bit σ. L’interaction entre les deux partis est noté  .

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   et   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é   ne doit pas être capable de savoir quoi que ce soit sur le message   à l’issue de l’échange.
Alice ( ) Bob ( )
Calculs Secret Public Public Secret Calculs
Messages à envoyer  
Création d'une paire de clefs RSA et envoi de la clef publique à Bob         Réception de la clef publique d'Alice
Génération de deux messages aléatoires       Réception de deux messages aléatoires
  Choix de   et génération d'un nombre aléatoire  
      Calcul du chiffrement de   avec   et envoi du résultat à Alice
Calcul des deux valeurs possibles pour  ,

dont une seule correspond à celle de Bob

 
Envoi des deux messages à Bob       Réception des deux messages
  Déchiffrement du message  , grâce au   choisi précédemment .
  1. Alice propose d'envoyer a Bob un message parmi deux disponibles   et  . 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  , un exposant public   et un exposant privé  .
  3. Elle génère également deux messages aléatoires   et   qu'elle envoie à Bob en même temps que sa clef publique  .
  4. Bob choisit le message qu'il souhaite recevoir, indiqué par  . Il sélectionne donc la valeur correspondante  .
  5. Bob génère un nombre aléatoire   et chiffre   avec   en calculant  , qu'il envoie à Alice.
  6. Pour Alice, il est impossible de déterminer si Bob a choisi   ou   pour calculer  , car elle ignore le nombre   généré par Bob . Elle calcule donc les deux valeurs possibles pour   à partir de  :   et  . L'une de ces deux valeurs est égale au   choisi par Bob (sans qu'Alice sache lequel) et l'autre est une valeur aléatoire qui ne fournit aucune information sur  .Ceci garantit la sécurité du destinataire.
  7. Alice masque les messages   et   avec les deux clefs possibles   et   pour donner   et  . Ces deux messages sont envoyés à Bob.
  8. Bob déchiffre le message   avec le   qu'il a choisi, pour obtenir  . Bob est par ailleurs incapable de déchiffrer l'autre message. En effet, il faudrait qu'il puisse calculer l'autre valeur de  , c'est-à-dire  , 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 nModifier

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 nModifier

On suppose qu'Alice possède   secrets   binaires valant tous soit 0 soit 1[note 1]. On suppose que Bob souhaite connaître le secret  . Un protocole de transfert inconscient peut être le suivant[8],[note 2]:

  1. Alice choisit deux nombres premiers   et   et un nombre   qui n'est pas un résidu quadratique modulo   et tel que le symbole de Jacobi   soit égal à 1[note 3];
  2. Alice publie   et   ;
  3. Alice associe un nombre aléatoire   à chaque secret   et envoie à Bob les   nombres   ;
  4. Bob génère un nombre aléatoire   ainsi qu'un bit aléatoire   et envoie à Alice le nombre  [note 4];
  5. Alice dit à Bob si le nombre   est un résidu quadratique modulo  . Si oui, alors   sinon  [note 5].

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

Comparaison avec les PIRModifier

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éralisationModifier

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

Requêtes adaptativesModifier

Notes et référencesModifier

NotesModifier

(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).
  1. Dans cette implémentation le secret ne peut être que sur un bit, comme une réponse oui/non à une question fermée.
  2. Ce protocole est donné à titre pédagogique, il est en effet vulnérable à des attaques.
  3. Cette condition est nécessaire pour s'assurer par la suite que Bob ne peut pas tricher : si   ou   Bob peut savoir si les nombres calculés dans la suite du protocole ne sont pas des résidus quadratiques modulo  , alors que si   il ne peut pas conclure. Pour plus de détails, voir l'article détaillé.
  4. On a donc  
  5. Comme  ,   est un carré si et seulement si  .

RéférencesModifier

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

AnnexesModifier

BibliographieModifier

  • [Camenisch, Neven et shelat 2007] Jan Camenisch, Gregory Neven et abhi shelat, « Simulatable Adaptive Oblivious Transfer », Eurocrypt,‎ , 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,‎ , 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,‎ , 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,‎ , 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),‎ , p. 20–31 (DOI 10.1145/62212.62215)
  • [Naor et Pinkas 1999] (en) Moni Naor et Benny Pinkas, « Oblivious transfer with adaptive queries », Crypto,‎ , 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),‎ , 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,‎ (lire en ligne [html])

Articles connexesModifier