Fehler in der Gesamtmitschrift zu MSS?

[Richie]

Hi,

ich bin mir nicht ganz sicher, ob ich nicht die Indizes durcheinander schmeiße, oder ob da ein Fehler im Script ist:
Es geht um 5.2 (MSS), Verification:
Ganz konkret geht es um die p_i:
mit p0 = g(Yc) rechne ich jetzt p1 aus (passend zum Beispiel davor):
l = floor(3/2) = 1 mod 2
Das heißt, dass das a_0, was aus der Signatur kommt, "nach links" muss (in der Konkatenation). Soweit so richtig.
Jetzt für p2:
l = floor(3/4) = 0 mod 2
Das heißt, dass das a_1, was aus der Signatur kommt, "nach rechts" muss. Im Beispielbaum steht das aber links.

Kann es sein, dass man zur Berechnung des l für p_h quasi mit (h-1) rechnen muss?
Oder bin ich einfach zu doof?

[Patr0rc]

Keine Angst, du bist nicht zu doof...

In der Vorlesungsmitschrift muss man zur Berechnung von p_h tatsächlich h-1 bei der Berechnung von l benutzen, was eigentlich auch klar ist in der Art, als dass zur Berechnung der Reihenfolge von \(a_{h-1}\) und \(p_{h-1}\) natürlicherweise der Index der Stufe h-1 genommen werden muss. Im Skript ist es angepasst worden (sowohl in der Einzel- als auch der Gesamtversion).

[marlic]

Ich schließe mich hier gerade mal an.

Seite 41 muss es bei der KeyGen von Niederreiter beim 4. Schritt (n-k) x (n-k) heißen, da H0 ja eine Parity check matrix des n,k, ... Goppa codes ist, und deshalb im (n-k) x n lebt.

Und auf Seite 47 soll es bei der oberen 2. wohl auch h(h(id_A) || i ) heißen. Ich denke, sonst kann es zu sowas kommen: http://xkcd.com/327/.
Außerdem ist das ja auch die normale CFS Methode.

[Patr0rc]

Erledigt und online.

[Felo]

Hallo,
also ich bin gerade ganz verwirrt: auf Seite 40 des Skripts wird die Parity Check Matrix zu einem (n, k) Code C (also mit einer k x n Generatormatrix G) als eine (n-k) x n Matrix definiert.

In Übung 10 ist die Partiy Check Matrix zu einem (n, k) Code C mit einer k x n Generatormatrix G wiederum als eine k x n Matrix dargestellt.

Im Niederreiter Scheme auf Seite 41 werden beim KeyGen die Matrizen S als k x k Matrix und P als n x n Matrix definiert, was ja bedeutet dass H_0 eine k x n Matrix sind.
Im Decrypt Schritt wird allerdings ein Ciphertext c angenommen, der aus F^(n-k)_2 stammt, was auch so nicht direkt von S^(-1) verarbeitet werden kann, da es ja eine k x k Matrix ist.

Überseh ich da irgendeinen wichtigen Zusammenhang oder ist es wirklich widersprüchlich?

Edit:
Wo ich gerade schon dabei bin - auf Seite 47 bei dem Stern Scheme wird bei den Schritten 1 für:
c1 = h(sigma || H * y^T)
und 4b:
H * y^T = ....
jeweils die Parity Check Matix H genommen, die allerdings nur die Authority kennt. Diese müssten durch H' ersetzt werden, da H' = SHP der öffentilche Schlüssel ist.

Viele Grüße,
Michael

[Patr0rc]

... auf Seite 40 des Skripts wird die Parity Check Matrix zu einem (n, k) Code C (also mit einer k x n Generatormatrix G) als eine (n-k) x n Matrix definiert.

Dies ist korrekt im Sinne des Verfassten.

In Übung 10 ist die Partiy Check Matrix zu einem (n, k) Code C mit einer k x n Generatormatrix G wiederum als eine k x n Matrix dargestellt.

Zufälligerweise ist hier \(n-k=k\) wegen \(n=8\) und \(k=4\).

Im Niederreiter Scheme auf Seite 41 werden beim KeyGen die Matrizen S als k x k Matrix und P als n x n Matrix definiert, was ja bedeutet dass H_0 eine k x n Matrix sind.
Im Decrypt Schritt wird allerdings ein Ciphertext c angenommen, der aus F^(n-k)_2 stammt, was auch so nicht direkt von S^(-1) verarbeitet werden kann, da es ja eine k x k Matrix ist.

Dies (das Fettgedruckte) ist ein Fehler im Skript, der nun korrigiert wurde.

Wo ich gerade schon dabei bin - auf Seite 47 bei dem Stern Scheme wird bei den Schritten 1 für:
c1 = h(sigma || H * y^T)
und 4b:
H * y^T = ....
jeweils die Parity Check Matix H genommen, die allerdings nur die Authority kennt. Diese müssten durch H' ersetzt werden, da H' = SHP der öffentilche Schlüssel ist.

Dieser Fehler ist ebenfalls korrigiert worden (H' statt vorher H).

[Richie]

Ich glaube im Abschnitt 21. (How to create...) ist auch noch ein kleiner Fehler
dort steht, dass man die Elemente identifiziere mit: 0 = 0*1 + 1*x [...] x = 0*1 + 1*x. Das hieße ja dann, dass 0 = x wäre. Außerdem hätten wir (0,0) nicht identifiziert, ich vermute mal stark, dass es 0 = 0*1 + 0*x heißen soll.

[Patr0rc]

Ich glaube im Abschnitt 21. (How to create...) ist auch noch ein kleiner Fehler
dort steht, dass man die Elemente identifiziere mit: 0 = 0*1 + 1*x [...] x = 0*1 + 1*x. Das hieße ja dann, dass 0 = x wäre. Außerdem hätten wir (0,0) nicht identifiziert, ich vermute mal stark, dass es 0 = 0*1 + 0*x heißen soll.

Ist korrigiert (in Gesamt- und Einzelversion).

[marlic]

Noch was zum Rainbow Scheme:

Auf Seite 56 steht "Note: If there is no solution for the oil variables on one of the layers, return to the layer above and choose other random values for the vinegar variables."

Ist das so gemeint, dass man bei nicht eindeutiger Lösung, eine zufällige Lösung aus dem Lösungsraum wählen soll?
Geht man nämlich davon aus, dass alle Lösungen eindeutig sein sollen, dann wird nur in der ersten Ebene zufällig gewählt.

[Patr0rc]

Ist das so gemeint, dass man bei nicht eindeutiger Lösung, eine zufällige Lösung aus dem Lösungsraum wählen soll?

Ja, das ist gemeint. Es handelt sich ja um ein Signaturverfahren, bei dem man eine Signatur zu einer Nachrichten angeben will. Alle Lösungen, die über die Verifikationsgleichung gültig sind, sind also korrekte Signaturen der Nachricht. Es muss also nicht zwangsläufig eindeutige Signaturen zu einer Nachricht geben. So ist zumindest mein Verständnis davon.
Beantwortet das die Frage zufriedenstellend?

[marlic]

Naja, ich bin davon ausgegangen, dass die Matrizen der einzelnen LGS die man löst, regulär sein sollten (und man ansonsten nochmal wählt). Das einzige was dann zufällig gewählt würde, wären die vinegar Variablen im ersten Schritt (widersprüchlich zur Aussage aus dem Skript, dass man zur vorherigen Ebene gehen soll).

[\Hannes]

Wieso müssen die regulär sein? Hauptsache, sie spucken irgendne Lösung aus, dachte ich.


Ansonsten, kurze Liste was mir so beim Lesen aufgefallen ist:

- S.7 sollten wohl \(|w_0|^2\) bzw. \(|w_1|^2\) die Wahrscheinlichkeiten sein
- S.27 die Herkunft von \(\mu_{2,1}^{\text{new}}\) und dem \(x\) und \(y\) ist sehr ominös
- S.40 are baseD statt are baseS
- S.40 werden \((n,k,2t+1)\) codes Goppa-Codes genannt, auf S.42 in 14.2.1 was anderes bzw. spezielleres..?
- S.51 im Diagramm, die \(S\) und \(T\) sind aber eigentlich nicht wirklich linear, sondern affin linear, oder?
- S.52 ganz oben, es heißt zwar \(n=m\), aber in \(\mathbb{F}_q^m\) sollten dann auch die Koeffizienten bis \(a_{m-1}\) gehen, nicht bis \(a_{n-1}\) (und schon gar nicht bis \(a_n\), so wie momentan )
- S.52 unten, der "in general, bilinear forms look like", das hinter dem e.g. - das \(F(x_1,x_2,y_1,y_2)\) was da steht bildet nicht in \(\mathbb{K}\) ab, sondern in \(\mathbb{K}^2\), was es allerdings als Beispiel für \(x^T A y\) etwas ungeeignet macht (jede Komponente von dem \(F=(F_1,F_2)\) sieht so aus)
- S.53 der Frobenius AutOmorphismus. Und wieso hat \(\mathbb{F}_{q^n}\) Charakteristik \(q\), nicht \(p\). Wenn das Allgemein mit dem \(p\) stehen bleiben soll (dann sollte man aber auch allgemeine Körper \(\mathbb{K}\) benutzen), sollte man es auch bei den 2 folgenden Abbildungen der Art \(x^{q^\alpha}\) anpassen.
- S.55 bei der Definition der Polynome in \(P_l\), die dritte Summe, sollte das nicht \(i \in V_{l+1}\) statt \(i \in S_{l+1}\) heißen?

Glaub das wars erstma ^^

[C0RNi666]

Bisher stimme ich hannes zu, habe noch eine kleine ergänzung:

seite 54 General Oil and Vinegar Scheme. Beim oil & vinegar polynom q sollte doch die Summe über d_j * x_j bis v statt bis o laufen, oder?

[Patr0rc]

- S.7 sollten wohl \(|w_0|^2\) bzw. \(|w_1|^2\) die Wahrscheinlichkeiten sein

-> geändert

- S.27 die Herkunft von \(\mu_{2,1}^{\text{new}}\) und dem \(x\) und \(y\) ist sehr ominös

Ist einfach der Faktor, der mittels GS-Prozess ermittelt wird, dann natürlich noch für Ganzzahligkeit gerundet.

- S.40 are baseD statt are baseS

-> geändert

- S.40 werden \((n,k,2t+1)\) codes Goppa-Codes genannt, auf S.42 in 14.2.1 was anderes bzw. spezielleres..?

Bin mir auch nicht ganz sicher bei der genauen Definition von Goppa Codes, die hier erstgenannten sind binäre Goppa Codes, die scheinbar die Form von 14.2.1 haben...

- S.51 im Diagramm, die \(S\) und \(T\) sind aber eigentlich nicht wirklich linear, sondern affin linear, oder?

Korrekt, leicht geändert.

- S.52 ganz oben, es heißt zwar \(n=m\), aber in \(\mathbb{F}_q^m\) sollten dann auch die Koeffizienten bis \(a_{m-1}\) gehen, nicht bis \(a_{n-1}\) (und schon gar nicht bis \(a_n\), so wie momentan )

-> geändert

- S.52 unten, der "in general, bilinear forms look like", das hinter dem e.g. - das \(F(x_1,x_2,y_1,y_2)\) was da steht bildet nicht in \(\mathbb{K}\) ab, sondern in \(\mathbb{K}^2\), was es allerdings als Beispiel für \(x^T A y\) etwas ungeeignet macht (jede Komponente von dem \(F=(F_1,F_2)\) sieht so aus)

-> geändert

- S.53 der Frobenius AutOmorphismus. Und wieso hat \(\mathbb{F}_{q^n}\) Charakteristik \(q\), nicht \(p\). Wenn das Allgemein mit dem \(p\) stehen bleiben soll (dann sollte man aber auch allgemeine Körper \(\mathbb{K}\) benutzen), sollte man es auch bei den 2 folgenden Abbildungen der Art \(x^{q^\alpha}\) anpassen.

-> geändert

- S.55 bei der Definition der Polynome in \(P_l\), die dritte Summe, sollte das nicht \(i \in V_{l+1}\) statt \(i \in S_{l+1}\) heißen?

Sollte es -> geändert

seite 54 General Oil and Vinegar Scheme. Beim oil & vinegar polynom q sollte doch die Summe über d_j * x_j bis v statt bis o laufen, oder?

Korrekt -> geändert

[\Hannes]

Ich benutze das hier einfach mal als generisches Fragentopic für kleinere Fragen.

Auf S.18 in Abschnitt 5.7 geht's irgendwie für meinen Geschmack sehr durcheinander mit den \(\omega\) und \(t\). Wieso ist \(X_0[0]\) \(\omega\) lang?! Es steht doch oben, dass \(\text{PRNG}: \{0,1\}^n \to \{0,1\}^{2n}\) abbildet (hier könnte man btw die Konkatenation (spelling?) mal noch zu nem Komma ändern, wie's später immer da steht). Ich verstehe einfach überhaupt nicht, was die \(\omega\) da tun.