Zu der Mitschrift vom 13.1.

Moderator: Post Quantum Cryptography

Benutzeravatar
blowfish
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 241
Registriert: 18. Okt 2006 16:00

Zu der Mitschrift vom 13.1.

Beitrag von blowfish » 30. Jan 2010 14:32

Hi,
ich möchte ein paar Dinge zu der Mitschrift vom 13.1. loswerden:

CFS:
Ich hatte hier mit dem Verständnis etwas zu kämpfen, da einige Dinge unklar formuliert sind. Wenn ich das jetzt richtig verstehe, ist die Nachricht \(h(h(m)||i)\) ein Syndrom, welches mit Hilfe von \(\gamma\) dekodiert wird. Es wäre schön, wenn \(\gamma\) entsprechend als "syndrome decoding algorithm" bezeichnet wird und auch wie in der vorherigen Mitschrift als \(\gamma_H\). Figure 1 ist dabei auch irritierend. Es sieht nämlich so aus, als wären die Punkte in der Skizze Codewörter und die Kreis darum die dekodierbaren Wörter. Laut Algorithmus müssten die Punkte aber alle Wörter (Vektoren im \(\Re^n\)) mit Gewicht t sein und die Kreise alle Syndrome der jeweiligen Wörter.
Diese Dinge führen dazu, dass man CFS leicht als auf McEliece basierend versteht, dabei basiert es eigentlich auf Niederreiter (, wenn ich es jetzt richtig verstanden habe).

Stern Identification Scheme:
Das Geheimnis \(s\) wird hier als Syndrom bezeichnet. Laut Definition ist aber eigentlich das öffentliche \(i\) das Syndrom von \(s\). Wenn man im Umgang mit den Begriffen "Syndrom", "Parity Check Matrix" usw noch nicht so sicher ist, verwirren solche vermeintlich kleinen Fehler ziemlich.
Ein Hemd ist Einstellungssache!

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

Re: Zu der Mitschrift vom 13.1.

Beitrag von Patr0rc » 1. Feb 2010 11:30

Da gebe ich dir Recht und es tut mir leid. Aber das beruht darauf, dass ich selbst auch nicht so firm mit den Dingen bin, da "Code-based Cryptography" beim letzten Mal nicht dran kam. Ich werde es nach Möglichkeit heute ändern...

Benutzeravatar
blowfish
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 241
Registriert: 18. Okt 2006 16:00

Re: Zu der Mitschrift vom 13.1.

Beitrag von blowfish » 1. Feb 2010 17:32

Dazu gleich noch ne Bemerkung zu der Mitschrift vom 16.12.:
Zum Gilbert-Varshamov-Bound steht da die Formel: \(q^{n-k} \geq \sum_{i=0}^{d-2}{n \choose i}(q-1)^i\). Wenn ich die Übung 10, Task 2c) richtig verstehe, haben wir da aber sogar \(q^{n-k} \geq \sum_{i=0}^{d-1}{n \choose i}(q-1)^i\) bewiesen, oder?
Ein Hemd ist Einstellungssache!

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

Re: Zu der Mitschrift vom 13.1.

Beitrag von Patr0rc » 2. Feb 2010 00:03

Zwei Sachen:
1. \(\gamma\) war vorher schon als "decoding algorithm" ausgewiesen, wurde nun zum "syndrome decoding algorithm" \(\gamma_H\) korrigiert.
2. Die Gilbert Varshamov Schrank wurde zu der Formulierung in Übung 10, Aufgabe 2c) angepasst. (Wenn man unter Wikipedia sieht, wird man feststellen, dass die vorherige Aussage für Primpotenzen q (fast) richtig war, siehe http://en.wikipedia.org/wiki/Gilbert-Va ... power_case).
--> Neue Version ist online.

Benutzeravatar
blowfish
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 241
Registriert: 18. Okt 2006 16:00

Re: Zu der Mitschrift vom 13.1.

Beitrag von blowfish » 2. Feb 2010 18:23

Hi,
nochmal zu der CFS-Geschichte:
Mitschrift 13.1. hat geschrieben: Therefore we use Goppa codes [...] with small t such that the probability for a random element to be decodable (to be in a ball of radius t of a codeword) is about \(\frac{1}{t!}\).
Ich denke, die Bemerkung in den Klammern ist falsch. Wenn dies tatsächlich der Fall wäre, müsste man t möglichst groß machen, um die Wahrscheinlichkeit zu erhöhen, dass ein zufällig gewähltes Wort dekodierbar ist. Wie bereits erwähnt interpretiert man die Hashes als Syndrome (Ciphertexte von Niederreiter), die dekodierbar sein müssen, nicht als "fehlerhaft übertragene" Codewörter (bzw. McEliece Ciphertexte).
Ein Hemd ist Einstellungssache!

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

Re: Zu der Mitschrift vom 13.1.

Beitrag von Patr0rc » 3. Feb 2010 11:22

Die Bemerkung in den Klammern wurde entfernt.

Antworten

Zurück zu „Post-Quantum Cryptography“