Fehler in der Gesamtmitschrift zu MSS?
Moderator: Post Quantum Cryptography
Fehler in der Gesamtmitschrift zu MSS?
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?
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?
There are only 10 types of people in the world:
Those who understand binary and those who don't
Those who understand binary and those who don't
Re: Fehler in der Gesamtmitschrift zu MSS?
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).
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?
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.
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.
"Copy & Passed"
Wahlspruch der Plagiatoren
Wahlspruch der Plagiatoren
Re: Fehler in der Gesamtmitschrift zu MSS?
Erledigt und online.
Re: Fehler in der Gesamtmitschrift zu MSS?
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
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?
Dies ist korrekt im Sinne des Verfassten.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.
Zufälligerweise ist hier \(n-k=k\) wegen \(n=8\) und \(k=4\).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.
Dies (das Fettgedruckte) ist ein Fehler im Skript, der nun korrigiert wurde.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.
Dieser Fehler ist ebenfalls korrigiert worden (H' statt vorher H).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.
Re: Fehler in der Gesamtmitschrift zu MSS?
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.
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.
There are only 10 types of people in the world:
Those who understand binary and those who don't
Those who understand binary and those who don't
Re: Fehler in der Gesamtmitschrift zu MSS?
Ist korrigiert (in Gesamt- und Einzelversion).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.
Re: Fehler in der Gesamtmitschrift zu MSS?
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.
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.
"Copy & Passed"
Wahlspruch der Plagiatoren
Wahlspruch der Plagiatoren
Re: Fehler in der Gesamtmitschrift zu MSS?
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.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?
Beantwortet das die Frage zufriedenstellend?
Re: Fehler in der Gesamtmitschrift zu MSS?
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).
"Copy & Passed"
Wahlspruch der Plagiatoren
Wahlspruch der Plagiatoren
Re: Fehler in der Gesamtmitschrift zu MSS?
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 ^^
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 ^^
Schwabbeldiwapp hier kommt die Grütze.
Re: Fehler in der Gesamtmitschrift zu MSS?
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?
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?
Win32: Reboot!
Unix: Be root!
Unix: Be root!
Re: Fehler in der Gesamtmitschrift zu MSS?
-> geändert\Hannes hat geschrieben:- S.7 sollten wohl \(|w_0|^2\) bzw. \(|w_1|^2\) die Wahrscheinlichkeiten sein
Ist einfach der Faktor, der mittels GS-Prozess ermittelt wird, dann natürlich noch für Ganzzahligkeit gerundet.\Hannes hat geschrieben:- S.27 die Herkunft von \(\mu_{2,1}^{\text{new}}\) und dem \(x\) und \(y\) ist sehr ominös
-> geändert\Hannes hat geschrieben:- S.40 are baseD statt are baseS
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.40 werden \((n,k,2t+1)\) codes Goppa-Codes genannt, auf S.42 in 14.2.1 was anderes bzw. spezielleres..?
Korrekt, leicht geändert.\Hannes hat geschrieben:- S.51 im Diagramm, die \(S\) und \(T\) sind aber eigentlich nicht wirklich linear, sondern affin linear, oder?
-> 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.
Sollte es -> 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?
Korrekt -> geändertC0RNi666 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?
Re: Fehler in der Gesamtmitschrift zu MSS?
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.
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.
Schwabbeldiwapp hier kommt die Grütze.