Fehler in der Gesamtmitschrift zu MSS?

Moderator: Post Quantum Cryptography

Richie
Mausschubser
Mausschubser
Beiträge: 92
Registriert: 25. Okt 2005 13:03
Wohnort: Darmstadt
Kontaktdaten:

Fehler in der Gesamtmitschrift zu MSS?

Beitrag von Richie » 16. Feb 2010 15:29

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?
There are only 10 types of people in the world:
Those who understand binary and those who don't

Benutzeravatar
Patr0rc
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 260
Registriert: 8. Feb 2008 11:43

Re: Fehler in der Gesamtmitschrift zu MSS?

Beitrag von Patr0rc » 17. Feb 2010 11:18

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).

Benutzeravatar
marlic
Computerversteher
Computerversteher
Beiträge: 365
Registriert: 5. Okt 2006 11:09
Wohnort: Dietesheim

Re: Fehler in der Gesamtmitschrift zu MSS?

Beitrag von marlic » 17. Feb 2010 14:01

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.
"Copy & Passed"

Wahlspruch der Plagiatoren

Benutzeravatar
Patr0rc
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 260
Registriert: 8. Feb 2008 11:43

Re: Fehler in der Gesamtmitschrift zu MSS?

Beitrag von Patr0rc » 17. Feb 2010 18:29

Erledigt und online.

Felo
Erstie
Erstie
Beiträge: 14
Registriert: 4. Jun 2009 13:28

Re: Fehler in der Gesamtmitschrift zu MSS?

Beitrag von Felo » 19. Feb 2010 14:59

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

Benutzeravatar
Patr0rc
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 260
Registriert: 8. Feb 2008 11:43

Re: Fehler in der Gesamtmitschrift zu MSS?

Beitrag von Patr0rc » 19. Feb 2010 16:41

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).

Richie
Mausschubser
Mausschubser
Beiträge: 92
Registriert: 25. Okt 2005 13:03
Wohnort: Darmstadt
Kontaktdaten:

Re: Fehler in der Gesamtmitschrift zu MSS?

Beitrag von Richie » 20. Feb 2010 11:25

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.
There are only 10 types of people in the world:
Those who understand binary and those who don't

Benutzeravatar
Patr0rc
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 260
Registriert: 8. Feb 2008 11:43

Re: Fehler in der Gesamtmitschrift zu MSS?

Beitrag von Patr0rc » 20. Feb 2010 12:11

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).

Benutzeravatar
marlic
Computerversteher
Computerversteher
Beiträge: 365
Registriert: 5. Okt 2006 11:09
Wohnort: Dietesheim

Re: Fehler in der Gesamtmitschrift zu MSS?

Beitrag von marlic » 20. Feb 2010 15:53

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.
"Copy & Passed"

Wahlspruch der Plagiatoren

Benutzeravatar
Patr0rc
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 260
Registriert: 8. Feb 2008 11:43

Re: Fehler in der Gesamtmitschrift zu MSS?

Beitrag von Patr0rc » 20. Feb 2010 16:03

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?

Benutzeravatar
marlic
Computerversteher
Computerversteher
Beiträge: 365
Registriert: 5. Okt 2006 11:09
Wohnort: Dietesheim

Re: Fehler in der Gesamtmitschrift zu MSS?

Beitrag von marlic » 20. Feb 2010 16:43

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

Benutzeravatar
\Hannes
Mausschubser
Mausschubser
Beiträge: 57
Registriert: 18. Nov 2005 17:24

Re: Fehler in der Gesamtmitschrift zu MSS?

Beitrag von \Hannes » 21. Feb 2010 20:20

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 ^^
Schwabbeldiwapp hier kommt die Grütze.

Benutzeravatar
C0RNi666
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 114
Registriert: 8. Jan 2008 12:51

Re: Fehler in der Gesamtmitschrift zu MSS?

Beitrag von C0RNi666 » 22. Feb 2010 11:02

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?
Win32: Reboot!
Unix: Be root!

Benutzeravatar
Patr0rc
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 260
Registriert: 8. Feb 2008 11:43

Re: Fehler in der Gesamtmitschrift zu MSS?

Beitrag von Patr0rc » 22. Feb 2010 12:43

\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

Benutzeravatar
\Hannes
Mausschubser
Mausschubser
Beiträge: 57
Registriert: 18. Nov 2005 17:24

Re: Fehler in der Gesamtmitschrift zu MSS?

Beitrag von \Hannes » 22. Feb 2010 22:05

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.
Schwabbeldiwapp hier kommt die Grütze.

Antworten

Zurück zu „Post-Quantum Cryptography“