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é . 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  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ée .

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 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.
 Alice génère une paire de clefs RSA, c'est-à-dire un modulo , un exposant public  et un exposant privé .
 Elle génère également deux messages aléatoires  et  qu'elle envoie à Bob en même temps que sa clef publique .
 Bob choisit le message qu'il souhaite recevoir, indiqué par . Il sélectionne donc la valeur correspondante .
 Bob génère un nombre aléatoire  et chiffre  avec  en calculant , qu'il envoie à Alice.
 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.
 Alice masque les messages  et  avec les deux clefs possibles  et  pour donner  et . Ces deux messages sont envoyés à Bob.
 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 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  secrets  binaires valant tous soit 0 soit 1. On suppose que Bob souhaite connaître le secret .
Un protocole de transfert inconscient peut être le suivant:
 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;
 Alice publie  et  ;
 Alice associe un nombre aléatoire  à chaque secret  et envoie à Bob les  nombres  ;
 Bob génère un nombre aléatoire  ainsi qu'un bit aléatoire  et envoie à Alice le nombre ;
 Alice dit à Bob si le nombre  est un résidu quadratique modulo . Si oui, alors  sinon .

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, 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 () 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

Notes et références

Notes

Références

Annexes

Bibliographie

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

Primitive cryptographique