Dieses Dokument ist auf arxiv unter der CC 4.0-Lizenz verfügbar.   Autoren:  (1) Ruta Jawale;  (2) Dakshita Khurana.  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.       Dies folgt direkt aus der vollkommenen Vollständigkeit von Π.  Nachweisen. Vollkommene Vollständigkeit  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.    Gegeben (x, α, s) von AΠ: Sende α an Π.Ext, empfange β von Π.Ext und sende β an AΠ. (1)    Beim Empfang von γ von AΠ: γ an Π.Ext senden. (2)    Geben Sie das Ergebnis von Π.Ext als w aus. (3)  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.    . Sei Π.Sim der rechnerische Zero-Knowledge-Quantensimulator mit ehrlichem Verifizierer für Π. Wir definieren Sim mit Oracle-Zugriff auf Π.Sim wie folgt: Computational Honest-Verifier Zero-Knowledge mit Quantum Simulator  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   erhalten. Dies führt zu einem Widerspruch gegen die Nullwissenseigenschaft von Π. Daher muss unser Protokoll wissensfrei sein.  D  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).    . Dies folgt aus Satz 5.1 und Satz 3.12. Nachweisen  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.    (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.3.  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   (·) mit  q  Ähnlich wie im vorherigen Abschnitt haben wir das folgende Lemma.    Sei Π = (Setup, P,V) ein nicht interaktives 1-zu-2-nicht klonbares Zero-Knowledge-Quantenprotokoll (Definition 5.4). Dann erfüllt Π Definition 5.3. Lemma 5.5.  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.    .   . 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:  Nachweisen Perfekte Korrektheit  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    Es seien λ, k ∈ N und ein Public-Key-Quantengeld-Minischema (   ). Lassen Sie die Punkte q1, . . . , qk mit folgender Struktur gegeben sein: Ein Punkt q enthält eine nach   (1λ) abgetastete Seriennummer s. Lemma 5.7. NoteGen,Ver NoteGen  Die Punkte q1, . . . , qk muss mit überwältigender Wahrscheinlichkeit verschieden sein.    . Jeder Punkt enthält eine Seriennummer, die gemäß dem Quantengeldgenerierungsalgorithmus   (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. Nachweisen NoteGen  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). ).    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.  Nachweisen.  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:    (ignoriert alle möglicherweise empfangenen Zeugen).  Eingabe: x  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.    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: Nicht klonbare Extrahierbarkeit.  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   liefern. I    Es gibt ein Polynom   (·), so dass  Anspruch 5.9. q  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.    Es gibt ein Polynom   ′ (·) mit  Anspruch 5.10. q  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.   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 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  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.    5.10. Angesichts der Tatsache, dass Anspruch 5.9 gilt, impliziert dies Folgendes  Anspruchsnachweis  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.    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). Folgerung 5.11.    Dies folgt aus Satz 3.14 und Satz 5.8. Nachweisen.  Wir haben somit gezeigt, dass Abbildung 5 ein nicht klonbarer NIZK-PoK im ROM-Modell ist, wie gemäß unserer Nichtklonbarkeitsdefinition Definition 5.4 definiert.

EScholar Technologies

EScholar

Dieses Audio ist in der Originalsprache der Geschichte produziert!

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

About Author

KOMMENTARE

Hängeetiketten

DIESER ARTIKEL WURDE VORGESTELLT IN

Related Stories

Starting 2025 with New Features: Settings Dashboard, HackerNoon Decoded, Updated Search UI, and More

HackerNoon Decoded 2024: Wir feiern die Community unserer Technologieunternehmen!

HackerNoon Decoded 2024: Celebrating Our Tech Stories Community!

HackerNoon Decoded: The Top 10 Countries Where HackerNoon Is the Most Active

Starting 2025 with New Features: Settings Dashboard, HackerNoon Decoded, Updated Search UI, and More

HackerNoon Decoded 2024: Wir feiern die Community unserer Technologieunternehmen!

HackerNoon Decoded 2024: Celebrating Our Tech Stories Community!

HackerNoon Decoded: The Top 10 Countries Where HackerNoon Is the Most Active

Light-Mode

Classic

Newspaper

Minty

Dark-Mode

Neon Noir

Minty

HN StartUps