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 Suche ergab 57 Treffer
- 21. Feb 2010 17:15
- Forum: Post-Quantum Cryptography
- Thema: Endlich gelöst: P ungleich NP?
- Antworten: 2
- Zugriffe: 1005
- 17. Feb 2010 07:56
- Forum: Post-Quantum Cryptography
- Thema: Punkte zur Hausübung
- Antworten: 0
- Zugriffe: 566
Punkte zur Hausübung
Die Liste der Hausübungspunkte hängt vor meinem Büro.
Frohes Weiterlernen wünsche ich...
Markus
Frohes Weiterlernen wünsche ich...
Markus
- 17. Dez 2009 18:20
- Forum: Post-Quantum Cryptography
- Thema: Ex. 08, Homework
- Antworten: 1
- Zugriffe: 726
Re: Ex. 08, Homework
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.
- 14. Nov 2009 13:39
- Forum: Post-Quantum Cryptography
- Thema: Ex. 04, Homework
- Antworten: 4
- Zugriffe: 862
Re: Ex. 04, Homework
Keine Panik, Patrick meldet sich bald mit ein paar klärenden Worten.
- 12. Nov 2009 18:05
- Forum: Post-Quantum Cryptography
- Thema: Ex. 03, Homework
- Antworten: 2
- Zugriffe: 749
Re: Ex. 03, Homework
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...
- 27. Okt 2009 13:17
- Forum: Post-Quantum Cryptography
- Thema: Ex. 1, Task 3
- Antworten: 11
- Zugriffe: 1662
Re: Ex. 1, Task 3
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.
- 27. Okt 2009 09:45
- Forum: Post-Quantum Cryptography
- Thema: Ex. 1, Task 3
- Antworten: 11
- Zugriffe: 1662
Re: Ex. 1, Task 3
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.
- 26. Okt 2009 09:43
- Forum: Post-Quantum Cryptography
- Thema: Ex. 1, Task 3
- Antworten: 11
- Zugriffe: 1662
Re: Ex. 1, Task 3
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.
Grades
The final grades for the exam are published next to B207.
- 16. Mär 2009 07:28
- Forum: Archiv
- Thema: Klausurangaben
- Antworten: 1
- Zugriffe: 690
Re: Klausurangaben
Kann ich noch nicht sagen.
- 4. Mär 2009 08:31
- Forum: Archiv
- Thema: Reduktion bei Buchbergers Algorythmus
- Antworten: 5
- Zugriffe: 1225
Re: Reduktion bei Buchbergers Algorythmus
Wir hatten das schon mehrmals erwähnt. Ihr müsst nur eine Gröbnerbasis ausgeben. Wenn ihr sie auch noch minimiert, fein.
Re: NTRU
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.
Re: NTRU
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.
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.
- 3. Mär 2009 16:24
- Forum: Archiv
- Thema: HKZ-Problem
- Antworten: 2
- Zugriffe: 609
Re: HKZ-Problem
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\)
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\)
- 1. Mär 2009 16:47
- Forum: Archiv
- Thema: Frage zu CR, EU-CMA, SU-CMA
- Antworten: 1
- Zugriffe: 625
Re: Frage zu CR, EU-CMA, SU-CMA
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...