Nicht klonbares, nicht interaktives Nullwissen im Quantum Random Oracle-Modell

Linktabelle

Zusammenfassung und Einführung

Technische Übersicht

Vorrunden

Nicht klonbares, nicht interaktives Zero-Knowledge im CRS-Modell

Nicht klonbares NIZK im Quantum Ramdon Oracle-Modell

Nicht klonbare Signaturen des Wissens

Verweise

5 Nicht klonbares NIZK im Quantum Random Oracle Model

5.1 Ein modifiziertes Sigma-Protokoll

Wir beginnen mit der Einführung eines leicht modifizierten Sigma-Protokolls. In den kommenden Abschnitten wird unsere Konstruktion die Anwendung von Fiat-Shamir auf dieses modifizierte Protokoll umfassen.

Nachweisen. Vollkommene Vollständigkeit Dies folgt direkt aus der vollkommenen Vollständigkeit von Π.

und jedes x mit zugehörigem λ ∈ N erfüllt

wir haben

Wir definieren Ext 3 mit Oracle-Zugriff auf Π.Ext und einige A wie folgt:

Eingabe: x, S.

(1) Gegeben (x, α, s) von AΠ: Sende α an Π.Ext, empfange β von Π.Ext und sende β an AΠ.

(2) Beim Empfang von γ von AΠ: γ an Π.Ext senden.

(3) Geben Sie das Ergebnis von Π.Ext als w aus.

Wir definieren den folgenden Parametersatz: c = cΠ, p(·) = pΠ(·), negl0 (·) = negl0,Π(·) und negl1 (·) = negl1,Π(·).

Es sei ein polynomialer Quantenkreis A = (A 0, A 1) und (x, S) gegeben, so dass

Wir definieren nun AΠ = (A0,Π, A1,Π) mit Oracle-Zugriff auf A. A0,Π ist fest mit S verbunden, nimmt Eingabe x, sendet (x, S) an A0, empfängt ((x, α, s ), |sti) aus A0 und gibt (α, |sti) aus. A1,Π ist mit S fest verdrahtet, nimmt Eingaben (x, |sti, β) entgegen, sendet ((x, S), |sti, β) an A1, empfängt γ von A1, gibt γ aus. Nach der Struktur unseres Beweises und der Definition unseres Verifizierers bedeutet dies Folgendes

was die Einschränkung in Gleichung (15) erfüllt. Dies bedeutet, dass wir in Kombination mit unserer Definition von Ext Folgendes haben

Dies zeigt, dass es sich bei unserem Protokoll um ein Proof of Knowledge-Protokoll handelt.

Computational Honest-Verifier Zero-Knowledge mit Quantum Simulator . Sei Π.Sim der rechnerische Zero-Knowledge-Quantensimulator mit ehrlichem Verifizierer für Π. Wir definieren Sim mit Oracle-Zugriff auf Π.Sim wie folgt:

Eingabe: x, S.

(1) Berechnen Sie (α, β, γ) ← Π.Sim(1λ , x)

(2) Proben von S.

(3) Ausgabe ((x, α, s), β, γ).

Gegeben seien ein Polynom p(·), ein Quantenschaltkreis D in Polynomgröße, λ ∈ N und ((x, S), w) ∈ R mit

Wir definieren eine Reduktion auf die Zero-Knowledge-Eigenschaft von Π wie folgt:

Reduktion: auf Nullwissen über Π bei gegebenem Oracle-Zugriff auf D.

Festverdrahtet mit: x, S.

(1) Erhalten Sie (real oder simuliert) (α, β, γ) vom Herausforderer.

(2) Proben von S.

(3) Sende ((x, α, s), β, γ) an D. Empfange b von D.

(4) Ausgabe b.

Wenn der Herausforderer einen echten (oder simulierten) Beweis für Π sendet, generiert die Reduktion einen Beweis, der mit dem echten (bzw. simulierten) Beweis identisch ist. Somit bleibt bei dieser Reduzierung der Unterscheidungsvorteil von D erhalten. Dies führt zu einem Widerspruch gegen die Nullwissenseigenschaft von Π. Daher muss unser Protokoll wissensfrei sein.

Nach der Definition des ehrlichen Prüfers P.Com,

Das ist ein Widerspruch. Daher muss unser Protokoll unvorhersehbare Verpflichtungen haben.

Folgerung 5.2. Die Fiat-Shamir-Heuristik, angewendet auf das in Satz 5.1 definierte Post-Quantum-Sigma-Protokoll, ergibt einen klassischen Post-Quantum-NIZKPoK Π′ im QROM (Definition 3.11).

Nachweisen . Dies folgt aus Satz 5.1 und Satz 3.12.

5.2 Definitionen der Nichtklonbarkeit

Nicht klonbare NIZKs im Quanten-Random-Oracle-Modell werden analog zum CRS-Modell definiert – der Vollständigkeit halber wiederholen wir diese Definitionen weiter unten im QRO-Modell.

Definition 5.3. (Nicht klonbare Sicherheit für harte Instanzen). Ein Beweis (P,V) erfüllt die nicht klonbare Sicherheit in Bezug auf ein Quantenzufallsorakel O, wenn für jede Sprache L mit der entsprechenden Beziehung RL, für jede Quantenschaltkreisfamilie in Polynomgröße {Cλ}λ∈N und für jede harte Verteilung {Xλ ,Wλ}λ∈N über RL gibt es eine vernachlässigbare Funktion negl1 (·), so dass für jedes λ ∈ N,

Definition 5.4 ((k−1)-to-k-Unclonable Extractable NIZK in QROM). Gegeben seien der Sicherheitsparameter λ ∈ N und die NP-Relation R mit entsprechender Sprache L. Sei Π = (P,V), so dass P und V Quantenalgorithmen in Poly(λ)-Größe sind. Wir haben, dass für jedes (x, ω) ∈ R P ein Instanz- und Zeugenpaar (x, ω) als Eingabe erhält und π ausgibt, und V eine Instanz x und einen Beweis π als Eingabe erhält und einen Wert in {0, 1}.

Π ist ein nicht interaktives (k − 1)-zu-k-nicht klonbares NIZKPoK-Protokoll für die Sprache L in Bezug auf ein Zufallsorakel O, wenn Folgendes gilt:

• Π ist ein NIZKPoK-Protokoll für die Sprache L im Quantenzufallsorakelmodell (Definition 3.11).

• (k−1)-zu-k-nicht klonbar mit Extraktion: Es gibt einen orakelgestützten Quantenschaltkreis E in Polynomgröße, so dass für jeden Quantenschaltkreis A in Polynomgröße, für jedes Tupel von k − 1 Instanz-Zeugen-Paaren ( x1, ω1), . . . ,(xk−1, ωk−1) ∈ R, für jedes x, wo wir definieren

so dass es ein Polynom p(·) gibt, wobei

dann gibt es auch ein Polynom q (·) mit

Ähnlich wie im vorherigen Abschnitt haben wir das folgende Lemma.

Lemma 5.5. Sei Π = (Setup, P,V) ein nicht interaktives 1-zu-2-nicht klonbares Zero-Knowledge-Quantenprotokoll (Definition 5.4). Dann erfüllt Π Definition 5.3.

Für einen Beweis von Lemma 5.5 verweisen wir auf Anhang A.

5.3 Nicht klonbares NIZK impliziert Quantengeld mit öffentlichem Schlüssel im QROM

Satz 5.6. Sei O ein Quantenzufallsorakel. Sei (X ,W) eine harte Verteilung über eine Sprache L ∈ NP. Sei Π = (P,V) ein 1-zu-2-nicht klonbares, nicht interaktives, vollkommen vollständiges, rechnerisch wissensfreies Protokoll für L im QRO-Modell (Definition 5.4).

Dann impliziert (P,V) ein Quantengeld-Minischema mit öffentlichem Schlüssel im QRO-Modell (Definition 3.15), wie in Abbildung 4 beschrieben.

Nachweisen . Perfekte Korrektheit . Dies folgt direkt aus der vollkommenen Vollständigkeit von Π. Unfälschbarkeit. Sei p(·) ein Polynom und A ein quantenpolynomialzeitlicher Gegner, sodass für unendlich viele λ ∈ N + gilt:

Wir konstruieren eine Reduktion, die die Nichtklonbarkeitsdefinition (Definition 5.3) bricht, von der wir (in Anhang A) zeigen, dass sie durch unsere Definition (Definition 5.4) impliziert wird. Der Herausforderer mit Zugriff auf das Zufallsorakel O probiert ein hartes Instanz-Zeugen-Paar (x, w) ← (X, Y) und einen Beweis π ← PO(x, w). Der Herausforderer leitet dann (x, π) an die Reduktion weiter, die auch Oracle-Zugriff auf O hat. Die Reduktion setzt dann |$i = π und s = x. Die Reduktion sendet (|$i, s) an den Gegner A, der zurückgibt (|$0, s0, |$1, s1). Die Reduktion analysiert dann und setzt πi = |$ii für i ∈ {0, 1}. Die Reduktion sendet dann π0 und π1 zurück an den Herausforderer.

5.4 Konstruktion und Analyse

Lemma 5.7. Es seien λ, k ∈ N und ein Public-Key-Quantengeld-Minischema ( NoteGen,Ver ). Lassen Sie die Punkte q1, . . . , qk mit folgender Struktur gegeben sein: Ein Punkt q enthält eine nach NoteGen (1λ) abgetastete Seriennummer s.

Die Punkte q1, . . . , qk muss mit überwältigender Wahrscheinlichkeit verschieden sein.

Nachweisen . Jeder Punkt enthält eine Seriennummer, die gemäß dem Quantengeldgenerierungsalgorithmus NoteGen (1λ) abgetastet wird. Aufgrund der Unvorhersehbarkeit der Ordnungszahlen des Quantengeldes (Definition 3.13) müssen alle k ehrlich erzeugten Ordnungszahlen mit überwältigender Wahrscheinlichkeit verschieden sein. Daher werden diese k Punkte mit überwältigender Wahrscheinlichkeit unterschiedlich sein.

Wir stellen nun unsere Konstruktion in Abbildung 5 vor und beweisen den Hauptsatz dieses Abschnitts.

Satz 5.8. Sei k(·) ein Polynom. Gegeben sei die NP-Beziehung R mit der entsprechenden Sprache L.

Sei ( NoteGen, Ver ) ein Quantengeld-Minischema mit öffentlichem Schlüssel (Definition 3.13) und Π = (P,V) ein Post-Quantum-Sigma-Protokoll (Definition 3.4).

(P,V), wie in Abbildung 5 definiert, ist ein nicht interaktiver Wissenston, rechnerisch null Wissen und (k − 1)-zu-k-nicht klonbar mit Extraktionsprotokoll für L im Quanten-Zufalls-Orakel-Modell (Definition 3.11). ).

Nachweisen. Die Parameter und Grundelemente seien wie in der Theorem-Anweisung angegeben. Wir argumentieren, dass sich die Vollständigkeit aus der Protokollkonstruktion in Abbildung 5 ergibt, und beweisen die verbleibenden Eigenschaften unten.

wir haben

Der Quantenschaltkreis A und x sei in polynomischer Größe so gegeben, dass

Sei AF S mit Oracle-Zugriff auf einige A und O wie folgt definiert:

Eingabe: x, S.

(1) Gegeben sei eine Abfrage (x, α, s) von A: Sende (x, α, s) an O, empfange β von O und sende β an A.

(2) Beim Empfang von π = (|$i, s, α, β, γ) von A: Ausgabe πF S = ((x, α, s), β, γ).

Nach der Struktur unseres Beweises und der Definition unseres Verifizierers bedeutet dies Folgendes

was die Einschränkung in Gleichung (16) erfüllt. Dies bedeutet, dass wir in Kombination mit unserer Definition von Ext und S Folgendes haben

Dies zeigt, dass es sich bei unserem Protokoll um ein Proof of Knowledge-Protokoll handelt.

Null-Wissen. Sei SimF S der Simulator für Π′ in Korollar 5.2 (wobei Π Satz 5.1 instanziiert). Sei RF S die Beziehung für Π′ bezüglich R. Wir definieren Sim mit Orakelzugriff auf SimF S und programmieren den Zugriff auf ein beliebiges Orakel O wie folgt:

Eingabe: x (ignoriert alle möglicherweise empfangenen Zeugen).

Gegeben sei ein orakelgestützter Unterscheider D, der nur Abfragen (x, w) ∈ R durchführen kann, und ein Polynom p(·) mit so

Wir definieren eine Reduktion auf die Zero-Knowledge-Eigenschaft von Π′ wie folgt:

Reduktion: auf Nullwissen über Π′ bei Oracle-Zugriff auf D und Programmzugriff auf O.

Für jedes (x, w) aus D:

Die Ansicht von D entspricht der unseres Protokolls in Abbildung 5 oder Sim. Daher sollte unsere Reduktion den gleichen Vorteil haben, indem sie die Null-Wissens-Eigenschaft von Π′ aufhebt. Wir stoßen auf einen Widerspruch, daher muss unser Protokoll wissensfrei sein.

Nicht klonbare Extrahierbarkeit. Sei Ext der Quantenschaltkreis des Extraktors, den wir zuvor definiert haben (in unserem Beweis, dass Abbildung 5 ein Wissensbeweis ist). Sei Sim die Quantenschaltung des Simulators, den wir zuvor definiert haben (in unserem Beweis, dass Abbildung 5 ein Zero-Knowledge-Protokoll ist). Wir definieren einen Extraktor E mit Oracle-Zugriff auf einige A wie folgt:

Fest verdrahtet mit: einer Auswahl von I ⊆ [k − 1], J ⊆ [k], x1, . . . , xk−1 ∈ R, x.

(1) Stichproben ℓ ∈ J gleichmäßig und zufällig.

(2) Instanziiert ein simulierbares und extrahierbares Zufallsorakel O. Führt Ext auf O während der gesamten Interaktion mit A aus (was ein Zurückspulen beinhalten kann; in diesem Fall würden wir A zurückspulen und die folgenden Schritte wiederholen). Fordern Sie, dass Ext in Bezug auf den von A ausgegebenen ℓten Beweis extrahiert.

(3) Berechnen Sie πι ← Sim(xι) für ι ∈ [k − 1], wobei wir alle Punkte speichern, die Sim in eine Liste P programmieren würde.

(4) Sende {πι}ι∈[k−1] an A.

(5) Für jede Anfrage von A, wenn die Anfrage in P ist, dann antworte mit der Antwort von P. Andernfalls leite die Anfrage an O weiter und sende die Antwort zurück an A. Sei Ob dieses modifizierte Zufallsorakel.

(7) Gibt das Ergebnis von Ext als w aus.

Angesichts der Gleichung (24) können wir uns in einem der beiden folgenden Fälle befinden: Entweder A generiert zwei akzeptierende Beweise, die dieselbe Seriennummer wie ein ehrlich generierter Beweis haben, oder A generiert dies nicht. Wir betrachten diese beiden Szenarien getrennt und zeigen, dass jedes auf einen Widerspruch stößt.

Szenario eins

Angenommen, A generiert zwei akzeptierende Beweise, die dieselbe Seriennummer haben wie ein ehrlich erstellter Beweis. Durch die Anwendung einer an Gleichung (24) gebundenen Vereinigung haben wir, dass dieses Ereignis mit einer Wahrscheinlichkeit von mindestens 1/2p(λ) eintreten könnte. Symbolisch,

Szenario zwei

Nehmen wir alternativ an, dass A nicht zwei akzeptierende Beweise generiert, die dieselbe Seriennummer haben wie ein ehrlich erstellter Beweis. Nach dem Schubladenprinzip bedeutet dies, dass A einen Akzeptierungsbeweis mit einer Seriennummer erstellt, die nicht zu der gehört, die er erhalten hat. Durch die Anwendung einer an Gleichung (24) gebundenen Vereinigung haben wir, dass dieses Ereignis mit einer Wahrscheinlichkeit von mindestens 1/2p(λ) eintreten könnte. Zusammenfassend haben wir das

Durch ein Mittelungsargument können wir den Index j ∈ J festlegen, was uns das gleiche Ereignis mit einem Vorteil von 1/(2kp(λ)) liefert. Wir wechseln nun zu einem Hybrid, bei dem wir A simulierte Beweise bei den Indizes I liefern.

Anspruch 5.9. Es gibt ein Polynom q (·), so dass

Wir werden später einen Beweis für Anspruch 5.9 sehen. Unter der Annahme, dass diese Behauptung gilt, können wir vorerst einen Gegner definieren, aus dem Ext einen gültigen Zeugen für x extrahieren kann.

Anspruch 5.10. Es gibt ein Polynom q ′ (·) mit

Wir werden bald einen Beweis für Behauptung 5.10 sehen. Wenn diese Behauptung wahr ist, dann haben wir einen direkten Widerspruch zu Gleichung (19). Somit müssen nur noch die beiden Behauptungen bewiesen werden: Behauptung 5.9 und Behauptung 5.10. Wir beginnen mit dem Beweis der ersteren Behauptung.

Anspruchsnachweis 5.9. Wir müssen zunächst argumentieren, dass unsere Strategie klar definiert ist und dass wir in der Lage sein werden, diese k Punkte unabhängig zu programmieren. Dann können wir argumentieren, dass es nicht unterscheidbar ist, einzeln auf simulierte Beweise umzusteigen. Wir werden argumentieren, dass unser Simulator in der erwarteten Polynomzeit läuft. Nach Lemma 5.7 werden die k Punkte, die unser Simulator programmieren wird, mit überwältigender Wahrscheinlichkeit verschieden sein. Da wir außerdem davon ausgegangen sind, dass unser Quantenzufallsorakel an mehreren unterschiedlichen Punkten programmiert werden kann (Definition 3.10), ist unser Simulator wohldefiniert.

Wir argumentieren nun mit einem Hybridargument für die Ununterscheidbarkeit der simulierten Beweise von den ehrlich generierten Beweisen. Nehmen wir aus Gründen der Widersprüchlichkeit an, dass die Wahrscheinlichkeitsdifferenz zwischen Gleichung (21) und Gleichung (22) für ein Polynom p ′ (·) 1/p′ (λ) beträgt. Wir konstruieren eine Reihe aufeinanderfolgender Hybriden für jedes i ∈ [k − 1], wobei wir den i-ten Beweis von „Beweis generiert“ auf „Simuliert“ umstellen. Nach diesem Hybridargument muss es eine Position ℓ ∈ [k − 1] geben, an der das Wechseln des ℓ-ten Beweises eine Wahrscheinlichkeitsdifferenz von mindestens 1/(kp′ (λ)) hat. Wir formalisieren nun eine Reduktion, die zwischen diesen beiden Einstellungen unterscheiden kann:

Wir argumentieren zunächst, dass die Ansicht, die die Reduktion auf A liefert, mit einem der Spiele übereinstimmt: bei denen alle Beweise bis zum ℓ-ten simuliert werden oder bei denen alle Beweise bis einschließlich dem ℓ-ten simuliert werden. Nach Lemma 5.7 unterscheidet sich der vom Herausforderer berechnete oder programmierte Punkt von den Punkten, die die Reduktion programmiert. Daher ist es der Reduktion gestattet, das Orakel zu modifizieren, mit dem A eine Schnittstelle bildet (siehe Schritt (4)). Zusammenfassend wird A Zugang zu einem Orakel gewährt, das mit allen Beweisen, die es erhält, übereinstimmt.

Vorausgesetzt, dass A eine Ansicht hat, die direkt mit seiner erwarteten Ansicht in beiden Spielen übereinstimmt, dann ist der Vorteil der Reduzierung derselbe wie der Vorteil von A, der mindestens 1/(kp′ (λ)) beträgt. Dies steht im Widerspruch zur Zero-Knowledge-Eigenschaft unseres Protokolls. Daher muss unsere ursprüngliche Behauptung wahr sein.

Nun fahren wir mit dem Beweis der letztgenannten Behauptung fort.

Anspruchsnachweis 5.10. Angesichts der Tatsache, dass Anspruch 5.9 gilt, impliziert dies Folgendes

Zunächst müssen wir argumentieren, dass die Ansicht von A mit dem Spiel identisch bleibt, das sowohl in Gleichung (24) als auch in Gleichung (25) erscheint. Das Orakel, mit dem A interagiert (siehe Schritt (4)), stimmt mit allen Beweisen überein, die es erhält.

Durch Gleichung (25) kommen wir zu dem Schluss, dass

Durch die Definition eines Wissensbeweises (Definition 3.11), der einige Parameterpolynome p ∗ (·) und vernachlässigbare Funktionen negl0 (·) und negl1 (·) hat, haben wir, dass es ein Polynom q ′ (·) gibt, so dass

was den Beweis unserer Behauptung vervollständigt.

Indem wir die Beweise unserer Behauptungen abschließen, haben wir den Beweis unserer Satzaussage abgeschlossen.

Folgerung 5.11. Unter der Annahme, dass die injektiven Einwegfunktionen existieren und Post-Quantum-iO existiert, gibt es einen nicht-interaktiven Wissensklang, rechnerisch Null-Wissen und (k − 1)-zu-kunklonierbar mit Extraktionsprotokoll für NP im Quantenzufallsorakel Modell (Definition 5.4).

Nachweisen. Dies folgt aus Satz 3.14 und Satz 5.8.

Wir haben somit gezeigt, dass Abbildung 5 ein nicht klonbarer NIZK-PoK im ROM-Modell ist, wie gemäß unserer Nichtklonbarkeitsdefinition Definition 5.4 definiert.