L'engagement de bits entraîne-t-il un transfert inconscient dans le modèle de sécurité théorique de l'information?

Supposons que vous ayez deux participants arbitrairement puissants qui ne se font pas confiance. Ils ont accès à l'engagement de bits (par exemple, des enveloppes scellées contenant des données qu'un joueur peut remettre à l'autre mais qui ne peuvent pas être ouvertes jusqu'à ce que le premier joueur donne au second une clé). Pouvez-vous l'utiliser pour créer un protocole de transfert inconscient. Est-ce vrai même si les joueurs acceptent d'ouvrir toutes les enveloppes à la fin pour détecter la tricherie (par exemple, une fois la main de poker jouée, tout le monde accepte de révéler ses cartes)?

Je suppose que vous ne pouvez pas obtenir le transfert inconscient de l'engagement de bits, car le transfert inconscient est cryptographiquement universel, et je ne trouve aucune référence qui dit que l'engagement de bits est, mais y a-t-il une preuve quelque part que vous ne pouvez pas le faire?

Enfin, quelqu'un a-t-il examiné le problème si les joueurs sont quantiques?

reference-request cr.crypto-security Peter Shor
la source

Dans un commentaire sur une question sur mathoverflow, il est indiqué que quantum Oblivious Transfer est équivalent à quantum Bit Commitment (avec références): mathoverflow.net/questions/32801/… .

M. Alaggan

Ces deux articles montrent qu'un engagement quantique de bits sans condition est impossible. Si vous pouviez faire un transfert quantique inconscient, cela impliquerait que vous puissiez faire un engagement quantique de bits, de sorte qu'ils montrent également que le transfert quantique inconscient sécurisé est également impossible. Ce que je me demande, c'est si on vous donne (sous forme de boîte noire) un engagement de bit qui fonctionne pour les protocoles quantiques, pourriez-vous également faire un transfert inconscient pour les protocoles quantiques.

Peter Shor

Peut-être qu'un peu plus de contexte est nécessaire. Je pense avoir un schéma assez simple qui, avec un peu d'engagement, l'utilise pour réaliser un transfert inconscient dans un protocole quantique. Je voulais (1) savoir quelles étaient les preuves classiques que le transfert inconscient est strictement plus puissant, pour m'assurer qu'elles ne s'appliquent pas au cas quantique, et (2) savoir si quelqu'un l'a déjà observé auparavant. La littérature sur le transfert quantique inconscient et l'engagement de bits est difficile à rechercher car plusieurs preuves de sécurité se sont effondrées lorsque Mayers et Lo et Chau ont prouvé leur théorème d'interdiction.

Peter Shor

En recherchant un peu plus dans la littérature, il y a un peu d'engagement ==> preuve de transfert inconsciente dans le régime quantique dans un article de Bennett, Brassard, Crépeau et Skubiszewska de 1991 ( springerlink.com/content/k6nye3kay7cm7yyx ), donc cela est connu.

Peter Shor

@M. Alaggan: Permettez-moi de m'excuser d'avoir rejeté si brusquement votre commentaire ci-dessus. L'auteur du commentaire MathOverflow auquel vous avez fait référence savait probablement qu'ils étaient équivalents, et en fait, ce commentaire m'a mis sur la piste bibliographique qui a conduit à la preuve de référence que j'ai trouvée dans mon commentaire ci-dessus. Merci beaucoup.

Peter Shor

Réponses:

Non, l'engagement a une complexité strictement inférieure à celle de l'OT. Je pense qu'un moyen facile de voir cela est l'approche adoptée dans Complexity of Multiparty Computation Problems: The Case of 2-Party Symmetric Secure Function Evaluation par Maji, Prabhakaran, Rosulek dans TCC 2009 (avertissement: auto-promotion!). Dans cet article, nous avons un résultat caractérisant ce que vous pouvez faire en donnant accès à un engagement idéal dans le modèle UC avec une sécurité statistique.

Supposons qu'il existe un protocole statistiquement sécurisé (contre les adversaires malveillants) pour OT utilisant l'accès à l'engagement de bits de boîte noire idéal. Ensuite, doit également être protégé contre des adversaires honnêtes mais curieux (pas aussi trivial que cela puisse paraître, mais pas très difficile à montrer non plus). Mais vous pouvez composer avec le protocole d'engagement trivial honnête mais curieux et avoir un protocole OT honnête mais curieux qui est statistiquement sécurisé sans configuration. Mais cela est connu pour être impossible. $\pi$ $\pi$ $\pi$

Une autre façon de le voir est à travers Impagliazzo-Rudich . Si vous avez des parties sans limite de calcul et un oracle aléatoire, vous pouvez faire un engagement (car tout ce dont vous avez besoin sont des fonctions à sens unique) mais vous ne pouvez pas faire des choses comme l'accord clé, et donc pas OT.

mikero
la source

@Mikero: c'est une preuve vraiment sympa et simple.

Peter Shor

Pour OT de bits classiques (c'est-à-dire le monde idéal classique), l'argument passera par les protocoles quantiques / adversaires. Si l'OT manipule des qbits, il peut y avoir des complications. L'étape «pas aussi banale que cela puisse paraître mais pas difficile» consiste à dire que WLOG le simulateur utilise toujours l'entrée fournie par l'environnement. C'est une propriété d'OT qui doit être montrée (si le simulateur n'a pas envoyé ce qui a été donné, les sorties seraient incorrectes avec une probabilité perceptible, donc la simulation n'est pas saine), et devraient être argumentées si l'environnement peut donner / recevoir des qbits d'OT.

mikero

@Mikero: Je ne comprends pas votre commentaire précédent. Qu'est-ce que cela signifie pour l'OT de ne pas manipuler les qubits? Voulez-vous dire que les deux parties communiquent simplement avec des bits classiques, mais peuvent avoir des processeurs quantiques? Cela découlerait du fait qu'il n'existe aucun protocole sécurisé de théorie de l'information pour OT, même avec un engagement de bits.

Peter Shor

J'examine si un "protocole OT quantique" signifie OT classique (la fonctionnalité OT ne connaît que les bits) avec un protocole éventuellement quantique, ou un OT dans lequel l'environnement connaît les qubits et l'OT envoie / reçoit des qubits. Dans le premier cas, je pense que le même argument n'est pas modifié. Vraisemblablement, vous voulez dire le dernier cas. Ensuite, s'il y a vraiment un contre-exemple dans le monde quantique, cela signifierait que l'OT des qubits n'a pas la propriété que WLOG la simulation mappe des adversaires du monde réel honnêtes mais curieux à des adversaires idéaux honnêtes mais curieux. Intéressant!

mikero

Si je comprends bien votre question, Bennett et al. papier et ma preuve sont pour OT classique, avec des messages quantiques entre les participants pour mettre en œuvre l'OT.

Peter Shor

Dans le cas quantique, le premier protocole à construire un transfert inconscient (classique) basé sur l'engagement de bits (classique) utilisant un protocole quantique a été proposé en 1991 par Bennett, Brassard, Crépeau et Skubiszewska (http://www.springerlink.com/content / k6nye3kay7cm7yyx /), mais une preuve complète de sécurité n'a été donnée que récemment par Damgaard, Fehr, Lunemann, Salvail et Schaffner dans http://arxiv.org/abs/0902.3918

Pour une extension du calcul multipartite et une preuve dans le cadre de compasabilité universel, voir le travail d'Unruh: http://arxiv.org/abs/0910.2912

Christian Schaffner
la source