Warum ist Feige-Fiat-Shamir nicht Zero Knowledge ohne Vorzeichen?

In Kapitel 10 von HAC (10.4.2) sehen wir das bekannte Feige-Fiat-Shamir-Identifikationsprotokoll, das auf einem Null-Wissens-Beweis basiert, der die (angenommene) Schwierigkeit nutzt, Quadratwurzeln zu extrahieren, die modulo ein Composite sind, das schwer zu faktorisieren ist. Ich werde das Schema in meinen eigenen Worten wiedergeben (und es hoffentlich richtig machen).

Beginnen wir mit einem einfacheren Schema: Sei eine Blum-Ganzzahl (also n = p q und jedes von p und q ist 3 mod 4) mit einer ausreichend großen Größe, dass Factoring unlösbar ist. Da n eine ganze Zahl von Blum ist, haben die Hälfte der Elemente von Z ∗ n das Jacobi-Symbol +1 und die andere Hälfte -1. Für die + 1-Elemente hat die Hälfte davon Quadratwurzeln, und jedes Element mit einer Quadratwurzel hat vier von ihnen, wobei genau eines selbst ein Quadrat ist.$n$$n=pq$$p$$q$$n$$Z_n^*$

Nun wählt Peggy ein zufälliges Element aus Z ∗ n aus und setzt v = s 2 . Sie schickt dann v an Victor. Als nächstes folgt das Protokoll: Victor möchte überprüfen, ob Peggy eine Quadratwurzel von v kennt, und Peggy möchte es ihm beweisen, ohne etwas über s preiszugeben, das über die Tatsache hinausgeht, dass sie ein solches s kennt .$s$$Z_n^*$$v=s^2$$v$$v$$s$$s$

1. Peggy wählt ein zufälliges in Z ∗ n und schickt r 2 an Victor.$r$$Z_n^*$$r^2$
2. Victor schickt wahrscheinlich oder b = 1 zurück zu Peggy.$b=0$$b=1$
3. Peggy sendet zu Victor.$rs^b$

Victor kann überprüfen, ob Peggy die richtige Antwort gesendet hat, indem er das, was er erhält, quadriert und mit dem richtigen Ergebnis vergleicht. Natürlich wiederholen wir diese Interaktion, um die Wahrscheinlichkeit zu verringern, dass Peggy nur eine glückliche Vermutung ist. Dieses Protokoll soll ZK sein; Ein Beweis kann an verschiedenen Stellen gefunden werden (z. B. in Boaz Baraks Vorlesungsnotizen ).

Wenn wir dieses Protokoll erweitern, um es effizienter zu gestalten, wird es Feige-Fiat-Shamir genannt. es ist sehr ähnlich wie oben. Wir beginnen Peggy mit Zufallswerten s 1 ⋯ s k und Zufallszeichen t 1 = ± 1 , ⋯ t k = ± 1. Sie veröffentlicht ihre Quadrate als v 1 = t 1 s 2 1 , ⋯ , v k = t k s 2 k . Mit anderen Worten, wir negieren zufällig einige der $k$$s_1\cdots s_k$$t_1 = \pm 1, \cdots t_k = \pm 1$$v_1=t_1s_1^2, \cdots, v_k = t_ks_k^2$ . Jetzt$v_i$

1. Peggy wählt ein zufälliges in Z ∗ n und schickt r 2 an Victor.$r$$Z_n^*$$r^2$
2. Victor sendet wahrscheinlich Werte b i von { 0 , 1 } zurück an Peggy.$k$$b_i$$\{0,1\}$
3. Peggy schickt an Victor.$r\Pi_{i=1}^ks_i^{b_i}$

Meine Frage: Warum sind die -Zeichenbits erforderlich? In Klammern weist HAC darauf hin, dass dies eine technische Voraussetzung ist, um zu beweisen, dass keine geheimen Informationen weitergegeben werden. Die Wikipedia-Seite für Feige-Fiat-Shamir (was das Protokoll falsch macht) impliziert, dass ohne dies ein bisschen durchgesickert ist.$t_i$

Ich kann keine Attacke finden, die Peggy etwas entzieht, wenn sie die Zeichen auslässt.

Das Feige-Fiat-Shamir (FFS) -Identifizierungsprotokoll ist ein Wissensnachweis (PoK), in dem die Prüferin (Peggy) ihr Wissen über die Quadratwurzeln der dem Prüfer (Victor) gegebenen Eingaben nachweist.

FFS möchte PoK von Beweisen für die Zugehörigkeit zu einer Sprache unterscheiden , in denen Peggy nachweist, dass die Eingabe eine bestimmte Eigenschaft hat (formeller gesagt , die Eingabe gehört zu einer bestimmten Sprache).

Wenn wir die negativen Vorzeichen nicht verwenden, ist es möglich, dass die Eingänge keine Quadratwurzel besitzen. Zum Beispiel hat die Zahl 20 keine Quadratwurzel mod 21. Da das Unterscheiden von Quadraten und Nichtquadraten ein bekanntes Problem ist , vermeidet FFS es, indem die Eingabe das Plus oder Minus einer quadratischen Zahl sein lässt. In ihren eigenen Worten (ein bisschen geändert):

Indem entweder plus oder minus ein Quadrat modulo a sein Blum integer , stellen wir sicher , dass v i mit allen Zahlen -umspannen kann Jacobi - Symbol + $v_i$$v_i$ und somit die s i existiere (von V-Sicht) unabhängig von v i Charakter, wie in uneingeschränkter Eingabe Null-Wissensbeweise des Wissens erforderlich.$+1 \bmod n$$s_i$$v_i$

Mit der uneingeschränkten Eingabe von wissensfreien Nachweisen von Wissen ist ein ZK PoK gemeint, dessen entsprechender Nachweis der Sprachzugehörigkeit trivial ist. Das heißt, V kann selbst entscheiden, ob die Eingabe das Plus oder das Minus eines Quadrats ist (indem nur das Jacobi-Symbol angekreuzt wird).