Seite 1 von 2

Fehler in der Gesamtmitschrift zu MSS?

Verfasst: 16. Feb 2010 15:29
von 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?

Re: Fehler in der Gesamtmitschrift zu MSS?

Verfasst: 17. Feb 2010 11:18
von 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).

Re: Fehler in der Gesamtmitschrift zu MSS?

Verfasst: 17. Feb 2010 14:01
von 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.

Re: Fehler in der Gesamtmitschrift zu MSS?

Verfasst: 17. Feb 2010 18:29
von Patr0rc
Erledigt und online.

Re: Fehler in der Gesamtmitschrift zu MSS?

Verfasst: 19. Feb 2010 14:59
von 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

Re: Fehler in der Gesamtmitschrift zu MSS?

Verfasst: 19. Feb 2010 16:41
von Patr0rc
Felo hat geschrieben:... 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.
Felo hat geschrieben: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\).
Felo hat geschrieben: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.
Felo hat geschrieben: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).

Re: Fehler in der Gesamtmitschrift zu MSS?

Verfasst: 20. Feb 2010 11:25
von 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.

Re: Fehler in der Gesamtmitschrift zu MSS?

Verfasst: 20. Feb 2010 12:11
von Patr0rc
Richie hat geschrieben: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).

Re: Fehler in der Gesamtmitschrift zu MSS?

Verfasst: 20. Feb 2010 15:53
von 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.

Re: Fehler in der Gesamtmitschrift zu MSS?

Verfasst: 20. Feb 2010 16:03
von Patr0rc
marlic hat geschrieben: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?

Re: Fehler in der Gesamtmitschrift zu MSS?

Verfasst: 20. Feb 2010 16:43
von 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).

Re: Fehler in der Gesamtmitschrift zu MSS?

Verfasst: 21. Feb 2010 20:20
von \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 ^^

Re: Fehler in der Gesamtmitschrift zu MSS?

Verfasst: 22. Feb 2010 11:02
von 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?

Re: Fehler in der Gesamtmitschrift zu MSS?

Verfasst: 22. Feb 2010 12:43
von Patr0rc
\Hannes hat geschrieben:- S.7 sollten wohl \(|w_0|^2\) bzw. \(|w_1|^2\) die Wahrscheinlichkeiten sein
-> geändert
\Hannes hat geschrieben:- 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.
\Hannes hat geschrieben:- S.40 are baseD statt are baseS
-> geändert
\Hannes hat geschrieben:- 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...
\Hannes hat geschrieben:- S.51 im Diagramm, die \(S\) und \(T\) sind aber eigentlich nicht wirklich linear, sondern affin linear, oder?
Korrekt, leicht geändert.
\Hannes hat geschrieben:- 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
\Hannes hat geschrieben:- 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
\Hannes hat geschrieben:- 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
\Hannes hat geschrieben:- 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
C0RNi666 hat geschrieben: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

Re: Fehler in der Gesamtmitschrift zu MSS?

Verfasst: 22. Feb 2010 22:05
von \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.