D120.de/forum

1) Mit NP vollständig hat die Aufgabe nichts zu tun.
2) Man beweist nicht, dass \(L \not\in \mathcal{P}\) sondern, dass \(Factoring \not\in \mathcal{P} \Rightarrow L \not\in \mathcal{P}\). Wenn man die Bedingung glaubt, hat man \(\mathcal{P} \neq \mathcal{NP}\), aber das weiß man natürlich nicht.

Die Liste der Hausübungspunkte hängt vor meinem Büro.

Frohes Weiterlernen wünsche ich...
Markus

Actually, the point is that you have to show that the equation holds over the integers without the reduction mod q. In other words, reducing mod q must not change anything.

Keine Panik, Patrick meldet sich bald mit ein paar klärenden Worten.

Du konstruierst in beiden Fällen einen Reduktionsalgorithmus. Ob er erfolgreich ist, hängt von der Erfolgswahrscheinlichkeit des Merkle-Forgers und vom Angreifertyp ab. Bei a) und b) wird jeweils angenommen, dass man es mit dem richtigen Angreifertyp zu tun hat. Der Beweis ist aber erst sinnvoll und...

Richtig beobachtet. An dieser Stelle ist die MuLö ungenau. Das Prädikat hilft beim Suchen auf \(D\). Die Werte für \(X\) kennen wir ja schon aus dem klassischen Schritt.

Das \(x^\prime\) im Prädikat kommt aus der Liste \(L\). Man überprüft ob man ein \(x\) mit "bekanntem" Hashwert vorliegen hat. Dann testet man noch, dass es eine echte Kollision, \(x \neq x^\prime\), ist. Irgendeinen Namen muss man dem ersten Teil des Tupels eben geben.

Eine N-to-1 Funktion erreicht man automatisch, wenn man den Definitionsbereich groß genug wählt. Ist keine Einschränkung, die die Funktion betrifft. Eine Hashfunktion ist sogar "\(\infty\)-to-one", da sie als \(H: \{0,1\}^* \rightarrow \{0,1\}^n\) definiert ist.

The final grades for the exam are published next to B207.

Kann ich noch nicht sagen.

Wir hatten das schon mehrmals erwähnt. Ihr müsst nur eine Gröbnerbasis ausgeben. Wenn ihr sie auch noch minimiert, fein.

An die -3 kann ich mich erinnern. Die minimale Gröbnerbasis müsste also {1} sein. Da ihr nicht minimieren oder sonst irgendwie optimieren solltet, wurde auch in der Lösung nur ein Zwischenergebnis angegeben.

Wenn ich die Frage zu Buchberger richtig verstehe, ist die Antwort:

ein konstantes Polynom a kann man immer zum Polynom 1 machen. Sobald 1 in der Idealbasis ist, kann man alle anderen vergessen, denn <1> = R.

L_i sollte das Gitter sein, bei dem alle Vektoren auf\(span(b_1, ..., b_{i-1})^\perp\) projiziert wurden.
In der PI Schreibweise aus meiner Vorlesung wäre das

\(B := (b_1, \ldots, b_n)\)
\(L := L(B)\)
\(L_i := \pi_i(L) := L(\pi_i(b_i), \ldots, \pi_i(b_n))\)
Die Dimension is dort also \((n-i)+1\)

Hallo, wir haben ein paar Fragen zur den Aufgaben aus Exercise 1: Zu SU-CMA. Angenommen wir signieren zwei unterschiedliche Nachrichten m_1 und m_2 und bekommen die Signaturen s_1 und s_2 zurück mit s_1=s_2. Ist dann (m_1,s_2) bzw. (m_2,s_1) eine gültige Fälschung gegen SU-CMA? Unserer Meinung nach...