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

13

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:SVxLr

  • die Ansicht von während der Interaktion mit dem Beweiser bei Eingabe und unter Verwendung der Zufälligkeit ; VPxr
  • die Ausgabe von an den Eingängen und , wenn Black-Box-Zugriff auf . SxrSV

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 .Sq(|x|)SxSV

Betrachten wir nun ein betrügerisches , das zuerst mal (bei willkürlichen Eingaben seiner Wahl) abfragt und dann willkürlich böswillig handelt.Vq(|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 'VSSPVV

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.

MS Dousti
quelle
Ich denke, Sie könnten "erschöpfend" statt "anstrengend" meinen.
Dave Clarke
Ich bin anderer Ansicht. Ich wollte damit sagen, dass ich einen Weg gefunden habe, um den Simulator der ZK-Protokolle zu "erschöpfen" ... Es gibt keinen "erschöpfenden" Simulator.
MS Dousti
Mein Fehler. Ich lese anstrengend als Adjektiv, nicht als Verb.
Dave Clarke

Antworten:

10

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|)time(V)poly(time(V))VVwird 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.VV

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 ∗ istpoly(time(V))V ist typischerweise ein fester Polynomalgorithmus, der einige Pseudozufallsfunktionen ausführt, während der Simulator eine beliebige polynomale Laufzeit haben kann.

Boaz Barak
quelle
1
Gilt das auch für "Universalsimulation" ZK? Schließlich ist Black-Box - ZK eine Art Universal-Simulation ZK, deren Laufzeit vor befestigt ist bestimmt wird. (Non-Black-Box ZK ist jedoch eine Art Universal-Simulation ZK, in der S die "Eingeweide" von V * betrachten kann)V
MS Dousti
Bitte beachten Sie die bearbeitete Frage für einige Referenzen.
MS Dousti
1
Für einen universellen (Nicht-Black-Box) Simulator, muss man Laufzeit Polynom in der Laufzeit von erlauben , da sonst der Simulator keine Zeit zu invoke hat V * . Aber im Allgemeinen ging es mir darum, dass "Black-Box-Zero-Wissen" keine kanonische Definition ist, sondern ein Werkzeug, und dieses Werkzeug kann im Kontext positiver oder negativer Ergebnisse unterschiedlich verwendet werden, um die Ergebnisse aussagekräftiger zu machen. VV
Boaz Barak
1
Ich habe die Beantwortung Ihres Kommentars verschoben, da ich mehr lesen wollte. Insbesondere las ich Yung und Zhaos Artikel (oben zitiert) und bemerkte, dass sie Blackbox ZK im RO-Modell für ein positives Ergebnis verwendeten, während Sie sagten: "Es macht keinen Sinn, von einem Zufalls-Orakel-Modell zu sprechen Simulator ist 'Black-Box'. " Ist ihr Ergebnis philosophisch problematisch oder sollten wir die Definition der Blackbox lockern?
MS Dousti
4

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.

David Cash
quelle
1
Danke für die Antwort David. Unabhängig von der Fähigkeit des Simulators, den RO zu programmieren, sollte er sie "überwachen" können. Jede Orakelabfrage von V * verschwendet also Ms Zeit um mindestens Zeit. Ihre große Idee ist es, das Modell so zu ändern, dass "der Simulator im Zeitpolynom in | x | und der Anzahl der von V * ausgegebenen RO-Abfragen ausgeführt wird". Das ist nicht das Standardmodell, aber ich sehe es als vernünftige Lösung. Dennoch denke ich, dass die "Giganten" in der Community zuerst die Echtheit eines solchen Modells anerkennen müssen ...
MS Dousti,
1
Können Sie eine Quelle nennen, die genau "das Standardmodell" definiert? (Dieser Begriff wird oft als Synonym für "keine zufälligen Orakel oder andere derartige Modifikationen im Berechnungsmodell vorhanden" verwendet, aber ich glaube nicht, dass Sie dies gemeint haben.) Ich gehe davon aus, dass ich die Definition skizziert habe von dem, was als Standard angesehen werden würde, und wenn nicht, dann können wir das herausfinden, ohne dass irgendwelche "Giganten" aktiv unsere Argumentation bestätigen.
David Cash
1
Sicher, mit "Standardmodell" meine ich die "Standarddefinition" von ZK unter dem RO-Modell. Sie können sich auf die Arbeit von Rafael Pass (in der Frage zitiert) oder seine Masterarbeit (mit dem Titel "Alternative Varianten von Zero-Knowledge Proofs") oder auf die Arbeit von Wee in AsiaCrypt 2009 ("Zero Knowledge im Random Oracle Model, Revisited") beziehen. . Keiner von ihnen definierte "Black-Box" -ZK im RO-Modell (alle erwähnten die Hilfseingabe ZK), obwohl keiner auf "Laufzeitpolynom in | x | und die Anzahl der von V * durchgeführten RO-Abfragen" Bezug nahm. Daher denke ich, dass Sie eine neue Definition
vorschlagen
Bitte beachten Sie die bearbeitete Frage für einige Referenzen.
MS Dousti