Erschöpfender Simulator von Zero-Knowledge-Protokollen im Random Oracle-Modell

In einem Artikel mit dem Titel "On Deniability in the Common Reference String und Random Oracle Model" schreibt Rafael Pass:

Wir stellen fest, dass der Simulator beim Nachweis der Sicherheit gemäß der standardmäßigen Zero-Knowledge-Definition im RO-Modell (Random Oracle) zwei Vorteile gegenüber einem einfachen Modellsimulator aufweist, nämlich

1. Der Simulator kann sehen, auf welchen Werten Parteien das Orakel abfragen.
2. Der Simulator kann diese Fragen auf beliebige Weise beantworten, solange die Antworten in Ordnung sind.

Die erste Technik, nämlich die Fähigkeit, Anfragen an den RO zu "überwachen", ist in allen Arbeiten, die sich auf das Konzept des Null-Wissens im RO-Modell beziehen, sehr verbreitet.

Betrachten Sie nun die Definition von Black-Box- Zero-Knowledge ( PPT steht für probabilistic, polynomial-time Turing machine ):

ein PPT-Simulator S , so dass(möglicherweise betrügerischen) PPT-Verifizierer,gemeinsamen EingabenundZufälligkeitenFolgendes nicht zu unterscheiden ist:$\exists$$S$$\forall$$V^*$$\forall$$x\in L$$\forall$$r$

• die Ansicht von während der Interaktion mit dem Beweiser bei Eingabe und unter Verwendung der Zufälligkeit ; $V^*$$P$$x$$r$
• die Ausgabe von an den Eingängen und , wenn Black-Box-Zugriff auf . $S$$x$$r$$S$$V^*$

Hier möchte ich einen Betrugsprüfer ausstellen , dessen Aufgabe es ist, jeden Simulator zu erschöpfen, der versucht, RO-Abfragen zu überwachen:$V'$

Sei der Simulator, der durch den Existenzquantifizierer in der Definition des Black-Box-Nullwissens garantiert wird, und sei ein Polynom, das die Laufzeit von am Eingang . Angenommen, versucht, die Abfragen von an die RO zu überwachen .$S$$q(|x|)$$S$$x$$S$$V^*$

Betrachten wir nun ein betrügerisches , das zuerst mal (bei willkürlichen Eingaben seiner Wahl) abfragt und dann willkürlich böswillig handelt.$V'$$q(|x|)+1$

Offensichtlich erschöpft den Simulator . Ein einfacher Weg für besteht darin, ein solches böswilliges Verhalten abzulehnen. Auf diese Weise kann ein Distinguist die reale Interaktion leicht von der simulierten unterscheiden. (Da in der realen Interaktion der Prüfer die Abfragen von nicht überwachen kann und daher nicht aufgrund der bloßen Tatsache ablehnt, dass zu viel abfragt.) S S P V ' V $V'$$S$$S$$P$$V'$$V'$

Was ist die Problemumgehung für das obige Problem?

Bearbeiten:

Eine gute Quelle für das Studium von ZK im RO-Modell ist:

Martin Gagné, Eine Studie des Zufalls-Orakel-Modells, Ph.D. Dissertation, University of California, Davis , 2008, 109 Seiten. Verfügbar bei ProQuest: http://gradworks.umi.com/33/36/3336254.html

Insbesondere enthält es Definitionen der Blackbox ZK im RO-Modell in Abschnitt 3.3 (Seite 20), die Yung und Zhao zugeschrieben werden:

Moti Yung und Yunlei Zhao. Interaktives Nullwissen mit eingeschränkten zufälligen Orakeln. In Theory of Cryptography - TCC 2006 , LNCS 3876, S. 21-40, 2006.

Es stellt sich die Frage, warum man Black-Box ZK im Zufalls-Orakel-Modell definieren möchte. Es gibt mindestens zwei Gründe, warum die Leute die Definition von Black-Box-Zero-Wissen vorgeschlagen haben:

1) Für ein positives Ergebnis, wenn Sie sagen , dass ein Simulator ist "Black-Box - Zero - Knowledge" es gibt Ihnen automatisch ein schönen gebunden an seiner Laufzeit (dh im Gegensatz zu p o l y ( t i m e ( V * ) ) ) , und es kann auch nützlich sein zu wissen , dass der Simulator nicht „Blick auf den Eingeweiden von V * und schert mich nicht , wenn V $poly(|x|) \cdot time(V*)$$poly(time(V*))$$V*$$V*$wird unter Verwendung von RAM, Schaltung usw. implementiert. Während ein Zufalls-Orakel-Modellsimulator effizient sein kann, ist er offensichtlich keine Black-Box, da er die Ausführung von irgendwie betrachten und daraus verstehen soll, wenn V ∗ ausgewertet wird eine Hash-Funktion. Aus diesem Grund ist es in gewissem Sinne nicht sinnvoll zu sagen, dass ein Zufalls-Orakel-Modellsimulator eine "Black-Box" ist.$V*$$V*$

2) Für ein negatives Ergebnis verwenden die Leute den "Black-Box-Simulator", um eine große Klasse von Beweistechniken zu erfassen. In diesem Fall können Sie den Black-Box-Simulator auch im Zufalls-Orakel-Modell definieren, und die Definition, die Sinn macht, ist das, was David sagte. In der Tat, für ein negatives Ergebnis auch nicht in dem Random Oracle Modell, ist es am besten , wenn das Ergebnis auch hält , wenn Sie den Simulator erlauben Laufzeit. In der Tat, obwohl es nicht immer angegeben wird, haben die negativen Ergebnisse, die mir bekannt sind, alle diese Eigenschaft, da der Betrugsprüfer V $poly(time(V*))$$V*$ ist typischerweise ein fester Polynomalgorithmus, der einige Pseudozufallsfunktionen ausführt, während der Simulator eine beliebige polynomale Laufzeit haben kann.

Hier ist meine Sicht auf das Problem. Ich habe in letzter Zeit keine Artikel gelesen, die sich mit Black-Box-Zero-Knowledge im Zufalls-Orakel-Modell (RO) befassen, daher rate ich nur, was sie bedeuten und nicht, was dort geschrieben steht. Die kurze Antwort (Schätzung) ist, dass BB-ZK im RO-Modell den Simulator im Zeitpolynom in | x | laufen lassen soll und die Anzahl der RO-Abfragen, die von V *, dem Betrugsprüfer, ausgegeben wurden.

Versuchen wir, diese Vermutung zu rechtfertigen. Eine erste Beobachtung ist, dass der Begriff "Black-Box-Zero-Knowledge-Beweise im Zufalls-Orakel-Modell" genauer betrachtet werden muss, um ihn richtig zu definieren. Black-Box-Simulatoren funktionieren mit jedem Orakel (dh der Betrugsprüfer als Black-Box), und ihre einzige Schnittstelle ist über die Orakeleingabe / -ausgabe. Wenn wir dieses Modell nur erweitern, um allen Parteien einen RO zu geben (möglicherweise indem wir ihren Schaltkreisen erlauben, RO-Gatter zu haben), erhalten wir ein Modell, bei dem der Simulator den RO nicht programmieren kann - bei einer Orakelabfrage alles (einschließlich RO-Abfragen) nur geschieht "innerhalb" des V * -Orakels und gibt dann seine nächste Nachricht zurück. Wenn wir die RO-Programmierung zulassen möchten, müssen wir die Schnittstellen ändern: Der Simulator erhält jetzt ein Eingabe- / Ausgabe-Orakel für V * und kein zufälliges Orakel. Bei jedem Anruf beim V * Orakel Anstatt die nächste Nachricht zu erzeugen, kann das Orakel stattdessen die nächste Anfrage an den RO erzeugen, und der Simulator kann ihm die RO-Antwort geben, indem er das Orakel erneut aufruft. Dies ermöglicht nun die RO-Programmierung, und wir können auch zulassen, dass die Laufzeit des Simulators von der Anzahl der Anfragen an den RO abhängt.

Jede weitere Untersuchung der Bedeutung dieser Definitionen bleibt dem Leser überlassen. Ich denke syntaktisch.