geradlinige Simulierbarkeit

11

Kennt irgendein Körper eine gute Referenz für die Bedeutung der geradlinigen Simulierbarkeit? Ich befinde mich derzeit intensiv mit dem Universal Composability (UC) -Framework von Canetti, kann jedoch keine gute Referenz für die Bedeutung der geradlinigen Simulierbarkeit finden. Jede Hilfe wird geschätzt.

Yasser Sobhdel
quelle

Antworten:

10

Hier wird "geradlinig" dem "Zurückspulen" gegenübergestellt. Ein Simulator ist "geradlinig", wenn er die Partei, für die er die Simulation durchführt, nicht "zurückspult".

Beispielsweise spult der Simulator in einem Protokoll ohne Wissen normalerweise den "Verifizierer" zurück. Im "geradlinigen" Sinne findet dieses Zurückspulen nicht statt.

Ich habe den Begriff "geradliniger Simulator" zum ersten Mal in Rafael Passs Artikel ( Über Deniabililty in den Common Reference String- und Random Oracle-Modellen (CRYPTO'03) ) und M.Sc. Diplomarbeit ( Alternative Varianten von Zero-Knowledge-Proofs ).

Bearbeiten: Ich habe ein früheres Papier gefunden: Concurrent Zero-Knowledge: Reduzieren der Notwendigkeit von Timing-Einschränkungen von Cynthia Dwork und Amit Sahai aus dem Jahr 1998. Weitere Hinweise finden Sie in Alon Rosens Kommentar unten.

MS Dousti
quelle
Ich kenne den Begriff "geradliniger Simulator" nicht, aber für mich steht "geradlinig" im Gegensatz zu "Verzweigung", analog zu zeitlicher Logik von linearer Zeit zu verzweigter Zeit und Spurenäquivalenz zu (Verzweigungs-) Bisimulationsäquivalenz. Gibt es etwas dazu?
Dave Clarke
Das glaube ich nicht. Ich habe eine andere Referenz gefunden , die meiner Definition entspricht.
MS Dousti
Die Erklärung von Sadeq ist dieselbe wie in jedem Kontext, in dem ich die verwendeten Begriffe gehört habe. Hier sind einige Vorlesungsnotizen der NYU aus einer Klasse in Adv Crypto aus dem letzten Jahr, in denen das Thema behandelt wird. siehe insbesondere Anspruch 8.
Daniel Apon
Deterministisch klingt nach einem möglichen Synonym.
Dave Clarke
5
Frühere Verwendungen des Konzepts der geradlinigen Simulierbarkeit (obwohl möglicherweise nicht unter dieser Terminologie) finden sich in: (1) Ran Canetti, Oded Goldreich, Shafi Goldwasser, Silvio Micali: Zurücksetzbares Nullwissen (erweiterte Zusammenfassung). STOC 2000: 235-244 und (2) Ran Canetti, Marc Fischlin: Universally Composable Commitments. CRYPTO 2001: 19 & ndash; 40. Der Begriff taucht in der Definition von UC auf, da es nicht möglich ist, die "Umgebung" zurückzuspulen. Es kam früher in einem anderen Kontext bei gleichzeitiger Null-Kenntnis auf, wo ein Rückspul-Simulator in Schwierigkeiten geraten kann.
Alon Rosen
3

Es gibt keine formale Definition dessen, was es bedeutet, ein geradliniger Simulator zu sein. Es ist nur eine intuitive Idee, mit der Dinge auf informelle Weise beschrieben werden können. Ich bin sehr skeptisch, ob man überhaupt definieren kann, was es bedeutet, eine Maschine nicht zurückzuspulen . In der Tat ist das Zurückspulen einer Maschine selbst ein informeller Begriff! Was wir unter Umverdienen einer Maschine wirklich verstehen, ist, dass wir viele mögliche Ausführungspfade einer Maschine aus einem bestimmten Zustand heraus untersuchen können. Formale Argumente basieren dann auf der Anzahl solcher Hinrichtungen, die wir untersuchen müssen, bevor wir eine Falltür oder andere Informationen erhalten können, die wir benötigen, um unseren Beweis weiter fortzusetzen.


quelle