Ergibt Bit Commitment im informationstheoretischen Sicherheitsmodell eine vergessene Übertragung?

Angenommen, Sie haben zwei willkürlich mächtige Teilnehmer, die sich nicht vertrauen. Sie haben Zugriff auf Bit-Commitments (z. B. versiegelte Umschläge mit Daten, die ein Spieler dem anderen übergeben kann, die jedoch erst geöffnet werden können, wenn der erste Spieler dem zweiten einen Schlüssel gibt). Können Sie dies verwenden, um ein vergessenes Übertragungsprotokoll zu erstellen? Trifft dies auch dann zu, wenn die Spieler zustimmen, alle Umschläge am Ende zu öffnen, um Betrug zu erkennen (z. B. wenn die Pokerhand gespielt wurde, sind alle damit einverstanden, ihre Karten offen zu legen)?

Ich gehe davon aus, dass Sie aus Bit-Commitment keine vergessliche Übertragung machen können, da die vergessliche Übertragung kryptografisch universell ist, und ich kann keine Referenzen finden, aus denen hervorgeht, dass Bit-Commitment besteht, aber gibt es irgendwo einen Beweis, dass Sie dies nicht können?

Hat sich jemand das Problem angesehen, wenn die Spieler Quanten sind?

reference-request cr.crypto-security Peter Shor
quelle

In einem Kommentar zu einer Frage zu mathoverflow wird angegeben, dass die Quanten-Oblivious-Übertragung dem Quanten-Bit-Commitment (mit Referenzen) entspricht: mathoverflow.net/questions/32801/… .

M. Alaggan

Diese beiden Arbeiten zeigen, dass eine bedingungslos sichere Quantenbit-Commitment unmöglich ist. Wenn Sie eine quantenvergessene Übertragung durchführen könnten, würde dies bedeuten, dass Sie ein Quantenbit-Commitment durchführen könnten, sodass auch eine bedingungslos sichere quantenvergessene Übertragung nicht möglich ist. Ich frage mich, ob Sie (als Black Box) eine Bit-Zusage erhalten, die für Quantenprotokolle geeignet ist, und ob Sie für Quantenprotokolle auch eine vergessene Übertragung durchführen können.

Peter Shor

Vielleicht ist ein bisschen mehr Hintergrund notwendig. Ich denke, ich habe ein ziemlich einfaches Schema, das es bei gegebener Bit-Verpflichtung verwendet, um eine vergessene Übertragung in einem Quantenprotokoll zu erreichen. Ich wollte (1) wissen, wie die klassischen Beweise lauten, dass eine vergessene Übertragung strikt wirksamer ist, um sicherzustellen, dass sie nicht für den Quantenfall gilt, und (2) wissen, ob dies zuvor jemand beobachtet hat. Die Literatur zu quantenvergessenem Transfer und Bit-Commitment ist schwierig zu durchsuchen, da mehrere Sicherheitsbeweise auseinanderfielen, als Mayers und Lo und Chau ihr No-Go-Theorem bewiesen.

Peter Shor

Wenn man ein bisschen mehr in der Literatur recherchiert, gibt es ein gewisses Engagement ==> einen unbewussten Übertragungsnachweis im Quantenregime in einer Veröffentlichung von Bennett, Brassard, Crépeau und Skubiszewska (1991 ) ( springerlink.com/content/k6nye3kay7cm7yyx ), so dass dies bekannt ist.

Peter Shor

@M. Alaggan: Lassen Sie mich entschuldigen, dass ich Ihren obigen Kommentar so abrupt verworfen habe. Der Autor des MathOverflow-Kommentars, auf den Sie sich bezogen haben, wusste wahrscheinlich, dass sie gleichwertig sind, und tatsächlich hat dieser Kommentar mich auf die bibliografische Spur gebracht, die zu dem Referenzbeweis führte, den ich in meinem obigen Kommentar gefunden habe. Also vielen Dank.

Peter Shor

Antworten:

Nein, Engagement hat eine streng geringere Komplexität als OT. Ich denke, ein einfacher Weg, dies zu erkennen, ist der in Komplexität von Mehrparteien-Berechnungsproblemen verfolgte Ansatz : Der Fall der symmetrischen Bewertung sicherer Funktionen durch zwei Parteien von Maji, Prabhakaran, Rosulek in TCC 2009 (Haftungsausschluss: Eigenwerbung!). In diesem Artikel haben wir ein Ergebnis, das beschreibt, was Sie tun können, wenn Sie Zugriff auf das ideale Engagement im UC-Modell mit statistischer Sicherheit haben.

Angenommen , ein statistisch sicheres Protokoll (gegen bösartige Gegner) war für OT mit Zugang zum idealen Black-Box - Bit - Engagement. Dann muss auch vor ehrlichen, aber neugierigen Gegnern sicher sein (nicht so trivial, wie es wahrscheinlich klingt, aber auch nicht sehr schwer zu zeigen). Aber Sie könnten mit dem trivialen, ehrlichen, aber merkwürdigen Protokoll für Commitment komponieren und ein ehrliches, aber merkwürdiges OT-Protokoll verwenden, das statistisch sicher ist, ohne dass Setups erforderlich sind. Dies ist jedoch bekanntermaßen unmöglich. $\pi$ $\pi$ $\pi$

Eine andere Möglichkeit ist Impagliazzo-Rudich . Wenn Sie rechnerisch unbegrenzte Parteien und ein zufälliges Orakel haben, können Sie sich verpflichten (alles, was Sie brauchen, sind Einwegfunktionen), aber Sie können Dinge wie die Schlüsselvereinbarung und damit nicht OT nicht tun.

mikero
quelle

@ Mikero: Das ist ein wirklich schöner und einfacher Beweis.

Peter Shor

Für die OT der klassischen Bits (dh der klassischen idealen Welt) wird das Argument für Quantenprotokolle / Gegner durchlaufen. Wenn das OT Qbit manipuliert, kann es zu Komplikationen kommen. Der Schritt, der "nicht so trivial ist, wie es sich anhört, aber nicht schwierig", besteht darin, dass der Simulator WLOG immer die von der Umgebung bereitgestellten Eingaben verwendet. Dies ist eine Eigenschaft von OT, die gezeigt werden muss (wenn der Simulator nicht gesendet hat, was gegeben wurde, wären die Ausgaben mit wahrnehmbarer Wahrscheinlichkeit falsch, daher wäre die Simulation fehlerhaft) und erneut diskutiert werden müssten, wenn die Umgebung geben kann Ich erhalte Qbits von OT.

Mikero

@ Mikero: Ich verstehe deinen vorherigen Kommentar nicht. Was bedeutet es für das OT, Qubits nicht zu manipulieren? Meinen Sie damit, dass beide Parteien nur mit klassischen Bits kommunizieren, aber möglicherweise Quantenprozessoren haben? Dies würde sich aus der Tatsache ergeben, dass auch bei Bit-Commitment kein informationstheoretisch sicheres Protokoll für OT existiert.

Peter Shor

Ich überlege, ob ein "Quanten-OT-Protokoll" ein klassisches OT (OT-Funktionalität kennt nur Bits) mit einem möglicherweise Quantenprotokoll bedeutet oder ein OT, in dem die Umgebung Qubits kennt und das OT Qubits sendet / empfängt. Im ersteren Fall denke ich, dass das gleiche Argument unverändert durchgeht. Vermutlich meinen Sie den letzteren Fall. Wenn es dann wirklich ein Gegenbeispiel in der Quantenwelt gibt, würde dies bedeuten, dass das OT von Qubits nicht die Eigenschaft hat, dass die WLOG-Simulation ehrliche, aber neugierige reale Gegner ehrlichen, aber neugierigen idealen Gegnern zuordnet. Interessant!

Mikero

Wenn ich Ihre Frage richtig verstehe, haben sowohl Bennett et al. Papier und mein Beweis sind für die klassische OT, mit Quantenbotschaften zwischen den Teilnehmern, um die OT zu implementieren.

Peter Shor

Im Quantenfall wurde 1991 von Bennett, Brassard, Crépeau und Skubiszewska (http://www.springerlink.com/content) das erste Protokoll vorgeschlagen, das eine (klassische) vergessene Übertragung basierend auf (klassischem) Bit-Commitment unter Verwendung eines Quantenprotokolls aufbaute / k6nye3kay7cm7yyx /), aber ein vollständiger Sicherheitsnachweis wurde erst kürzlich von Damgaard, Fehr, Lunemann, Salvail und Schaffner unter http://arxiv.org/abs/0902.3918 erbracht

Eine Erweiterung der Mehrparteienberechnung und einen Beweis im universellen Kompasabilitätsrahmen finden Sie in der Arbeit von Unruh: http://arxiv.org/abs/0910.2912

Christian Schaffner
quelle