Ex. 1, Task 3

Moderator: Post Quantum Cryptography

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

Ex. 1, Task 3

Beitrag von \Hannes » 24. Okt 2009 16:06

Hallo.
Es geht um die Teilaufgabe b) von Aufgabe 3 vom ersten Übungsblatt, respektive die Musterlösung dazu. Konkret geht es um den zweiten, besseren Ansatz. Sehe ich das richtig, dass es im Prädikat \((x',h(x)) \in L\) heißen sollte?! Man will da doch schauen, ob zum Input x in das Prädikat ein x' aus der Liste mit selbem Hashwert existiert, d.h. ob ein Tupel (x',h(x)) existiert, was h(x) = h(x') bedeutet. Die zweite Bedingung stellt dann sicher, dass wir nicht zufällig x = x' selbst betrachten.

Und woher kommt \(|\{x \in X : P(x) = 1\}| = |X|\) ?
Ich dachte zu erst, das kommt daher, dass \(P(x) = 1 \, \forall x \in X\), aber das stimmt offenbar nicht (weder für das aktuelle Prädikat noch für das meiner Meinung nach korrigiert richtige, jedenfalls unter der Vorraussetzung, dass wir ja schon geprüft haben, ob L Kollisionen beinhaltet). Begründen wir das darauf, dass wir h weiter oben so ausgewählt haben, dass es auch tatsächlich Kollisionen gibt? Wieso gibt es aber dann genau |X|? Es ist doch gar nicht gesagt, dass wir zu jedem Element aus X tatsächlich eine Kollision finden (und wenn das so wäre, könnte es ja auch mehrere geben, d.h. es müsste \(\geq |X|\) heißen, oder?).

Danke schonmal,
Hannes

PS: Ich vermute auch mal, in der vorletzten Zeile sollte es \(O(|D|^\frac{1}{3})\) heißen.
Schwabbeldiwapp hier kommt die Grütze.

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

Re: Ex. 1, Task 3

Beitrag von \Hannes » 24. Okt 2009 16:23

Ah: nach recht aufwändiger Suche hab ich gefunden, was N-to-one bedeutet, damit hat sich die zweite Frage erledigt. Für die die's auch nicht wissen: Eine Funktion heißt genau dann N-to-one, wenn f(x) = f(a) für festes x genau N Lösungen (x inklusive) besitzt. Mit 2-to-1 gibt es also in der Tat genau die vermuteten Kollisionen. War 'n neuer Begriff für mich.

Ist denn so eine N-to-one Funktion dann nicht in der Tat eine ziemliche Einschränkung? Ich meine, von 'es existieren Kollisionen' zu 'es existieren zu jedem x N Kollisionen' ist doch ziemlich ordentlich, oder?

Sorry auch für die Selbstantwort, aber beim reineditieren wär ich mir so schizophren vorgekommen. ;)
Schwabbeldiwapp hier kommt die Grütze.

rueckert
Mausschubser
Mausschubser
Beiträge: 57
Registriert: 9. Apr 2008 09:25

Re: Ex. 1, Task 3

Beitrag von rueckert » 26. Okt 2009 09:43

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.

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

Re: Ex. 1, Task 3

Beitrag von \Hannes » 26. Okt 2009 18:13

Könntest du das 'groß genug wählen' vielleicht ein wenig ausführen? Ich sehe irgendwie noch nicht so wirklich, wie wir bei \(h : X = \{0,1\}^n \to \{0,1\}^n\) von 2-to-1 ausgehen können, bzw. bedeutet vergrößern des Definitionsbereiches doch auch, dass unsere Laufzeit wächst. Der Algorithmus läuft ja schließlich in \(O(|X|^\frac{1}{3}) = O(2^\frac{n}{3})\), d.h. wenn wir X zuviel größer machen, laufen wir doch am Ende evtl. noch schlechter als \(O(\sqrt{2^n}) = O(2^\frac{n}{2})\), zB. mit \(X = \{0,1\}^{2n}\), da wären wir ja bei \(O(2^\frac{2n}{3})\)?

Aus \(X = \{0,1\}^k\) und \(\frac{k}{3} \leq \frac{n}{2}\) erhalten wir \(k \leq \frac{3}{2}n\), d.h. für \(n \leq k \leq \frac{3}{2}n\) müssen wir eine 2-to-1 Funktion wählen können (wg. mir auch nicht größer als n, sofern das dann möglich ist?).
Schwabbeldiwapp hier kommt die Grütze.

Edoat
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 242
Registriert: 26. Feb 2007 15:10

Re: Ex. 1, Task 3

Beitrag von Edoat » 26. Okt 2009 18:48

\Hannes hat geschrieben:Sehe ich das richtig, dass es im Prädikat \((x',h(x)) \in L\) heißen sollte?! Man will da doch schauen, ob zum Input x in das Prädikat ein x' aus der Liste mit selbem Hashwert existiert [...]
Nein, denn falls man beim Sortieren eine Kollision gefunden hat, ist man fertig und braucht das Prädikat P gar nicht mehr. Das Prädikat P definieren wir nur, wenn wir keine Kollision gefunden haben. Das steht so auch in der Version des Übungsblattes, die ich habe.
\Hannes hat geschrieben:Und woher kommt \(|\{x \in X : P(x) = 1\}| = |X|\) ?
Ich dachte zu erst, das kommt daher, dass \(P(x) = 1 \, \forall x \in X\), aber das stimmt offenbar nicht (weder für das aktuelle Prädikat [...]
Für das aktuelle Prädikat stimmt das. \(P(x) = 1\) bedeutet, dass es keine Kollision für \(x\) gibt. Das gilt natürlich für alle \(x \in X\), sonst hätten wir ja bereits aufgehört (siehe oben). Vielleicht wird die Definition von P(x) klarer, wenn man sich sie schrittweise vorstellt:

1. Wähle ein \(x \in X\).
2. Wähle ein \(x'\). Damit P gelten kann, muss man ein \(x'\) wählen, dass ungleich \(x\) ist (2. Teil der Definition: \(x \neq x'\)).
3. Berechne \(h(x')\). Jetzt gibt es 2 Möglichkeiten:
3a) \(h(x') \neq h(x)\). Dann gilt \((x',h(x')) \in L\) und \((x',h(x)) \in L\) kann nicht gelten, da ein Element nur einen Hashwert haben kann.
3b) \(h(x') = h(x)\). Dann gilt \((x',h(x)) \in L\). Das wäre eine Kollision von \(x\), da \(x \neq x'\) und \(h(x) = h(x')\). Es kann aber keine Kollisionen in \(L\) geben (siehe oben).Dieser Fall tritt also nicht auf.

Edit: 3. etwas ausgeführt

Edoat
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 242
Registriert: 26. Feb 2007 15:10

Re: Ex. 1, Task 3

Beitrag von Edoat » 26. Okt 2009 19:18

\Hannes hat geschrieben:Könntest du das 'groß genug wählen' vielleicht ein wenig ausführen? Ich sehe irgendwie noch nicht so wirklich, wie wir bei \(h : X = \{0,1\}^n \to \{0,1\}^n\) von 2-to-1 ausgehen können
Ich nehme an, du meinst \(h : X = \{0,1\}^* \to \{0,1\}^n\), da du dich auf die b) beziehst. Ich würde vermuten, dass man bei kollisionsresistenten Hashfunktionen anstrebt, dass es zu jedem Hashwert ungefähr gleich viele Kollisionen gibt. Sonst wäre es für gewisse Hashwerte leichter Kollisionen zu finden. Wenn nichts über die tatsächliche Menge der Eingabedaten bekannt ist, wird man dieses Risiko wahrscheinlich nicht eingehen wollen.

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

Re: Ex. 1, Task 3

Beitrag von \Hannes » 26. Okt 2009 20:42

Uargh?! Ich glaube entweder reden wir komplett aneinander vorbei oder einer von uns beiden hat irgendwas nich verstanden (ich möchte hier nicht ausschließen, dass ich das bin :mrgreen:, hoffe aber nicht).
Edoat hat geschrieben:
\Hannes hat geschrieben:Sehe ich das richtig, dass es im Prädikat \((x',h(x)) \in L\) heißen sollte?! Man will da doch schauen, ob zum Input x in das Prädikat ein x' aus der Liste mit selbem Hashwert existiert [...]
Nein, denn falls man beim Sortieren eine Kollision gefunden hat, ist man fertig und braucht das Prädikat P gar nicht mehr. Das Prädikat P definieren wir nur, wenn wir keine Kollision gefunden haben. Das steht so auch in der Version des Übungsblattes, die ich habe.
Wut. Also zur gemeinsamen Kommunikation, ich verstehe das folgendermaßen:
Wir wählen \(X \subset D\) mit ungefähr \(|D|^\frac{1}{3}\) Elementen. Dazu berechnen wir die Hashwerte und speichern das Ganze in ner sortierten Liste. Sind da Kollisionen drin, bingo, fertig. Also weiter, wir nehmen an in X sind keine Kollisionen ersichtlich. Dem Grover geben wir dann aber G(P,D), d.h. die komplette Menge als Input. Und für diese komplette Menge überprüft/"sucht" der Grover dann diejenigen Elemente, für die das Prädikat 1 ergibt, also in unserem Fall (hoffentlich ;)) Kollisionen mit Elementen unserer Liste. Was das Prädikat meiner Meinung nach tun soll, habe ich ja im ersten Post schon erläutert.
Edoat hat geschrieben:
\Hannes hat geschrieben:Und woher kommt \(|\{x \in X : P(x) = 1\}| = |X|\) ?
Ich dachte zu erst, das kommt daher, dass \(P(x) = 1 \, \forall x \in X\), aber das stimmt offenbar nicht (weder für das aktuelle Prädikat [...]
Für das aktuelle Prädikat stimmt das. \(P(x) = 1\) bedeutet, dass es keine Kollision für \(x\) gibt. Das gilt natürlich für alle \(x \in X\), sonst hätten wir ja bereits aufgehört (siehe oben). Vielleicht wird die Definition von P(x) klarer, wenn man sich sie schrittweise vorstellt:

1. Wähle ein \(x \in X\).
2. Wähle ein \(x'\). Damit P gelten kann, muss man ein \(x'\) wählen, dass ungleich \(x\) ist (2. Teil der Definition: \(x \neq x'\)).
3. Berechne \(h(x')\). Jetzt gibt es 2 Möglichkeiten:
3a) \(h(x') \neq h(x)\). Dann gilt \((x',h(x')) \in L\) und \((x',h(x)) \in L\) kann nicht gelten, da ein Element nur einen Hashwert haben kann.
3b) \(h(x') = h(x)\). Dann gilt \((x',h(x)) \in L\). Das wäre eine Kollision von \(x\), da \(x \neq x'\) und \(h(x) = h(x')\). Es kann aber keine Kollisionen in \(L\) geben (siehe oben).Dieser Fall tritt also nicht auf.

Edit: 3. etwas ausgeführt
Wie oben schon geschrieben, gibt man dem Algorithmus die Menge \(D\) und nicht \(X\). D.h. wenn überhaupt wählen wir \(x \in D\), und woher soll \(x'\) nun stammen? Ausserdem hab ich doch schon im zweiten Post erklärt, woher meiner Meinung nach die Mächtigkeit der fraglichen Menge kommt. Ansonsten hätte die 2-to-1 Eigenschaft ja auch überhaupt keinen Nutzen. Und was soll überhaupt ein Prädikat nutzen, das mir keine Kollisionen sucht? Sorry, aber das klingt mir irgendwie nicht sehr plausibel..

Zu deinem zweiten Post: Ich meine in der Tat Teil b), allerdings wählen wir (auch laut der Musterlösung) konkret \(D = \{0,1\}^n\).
Schwabbeldiwapp hier kommt die Grütze.

Edoat
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 242
Registriert: 26. Feb 2007 15:10

Re: Ex. 1, Task 3

Beitrag von Edoat » 26. Okt 2009 23:08

\Hannes hat geschrieben:Uargh?! Ich glaube entweder reden wir komplett aneinander vorbei oder einer von uns beiden hat irgendwas nich verstanden
Es kann auch durchaus sein, dass ich es nicht verstanden habe. Vielleicht reden wir aber auch komplett aneinander vorbei und haben es beide nicht verstanden :wink: .
\Hannes hat geschrieben:Wut. Also zur gemeinsamen Kommunikation, ich verstehe das folgendermaßen:
Wir wählen \(X \subset D\) mit ungefähr \(|D|^\frac{1}{3}\) Elementen. Dazu berechnen wir die Hashwerte und speichern das Ganze in ner sortierten Liste. Sind da Kollisionen drin, bingo, fertig.
So habe ich diesen Teil der Lösung jedenfalls verstanden.
\Hannes hat geschrieben:Also weiter, wir nehmen an in X sind keine Kollisionen ersichtlich. Dem Grover geben wir dann aber G(P,D), d.h. die komplette Menge als Input. Und für diese komplette Menge überprüft/"sucht" der Grover dann diejenigen Elemente, für die das Prädikat 1 ergibt, also in unserem Fall (hoffentlich ;)) Kollisionen mit Elementen unserer Liste.
Bei diesem Teil habe ich noch Verständnisschwierigkeiten. Mir ist nicht klar, wie die Definition des Prädikats in D bei der Suche nach Kollisionen hilft, da ja nur L (und so auch X) als Menge darin auftaucht.
\Hannes hat geschrieben: [...] Und was soll überhaupt ein Prädikat nutzen, das mir keine Kollisionen sucht? Sorry, aber das klingt mir irgendwie nicht sehr plausibel..
Dieser Teil meiner Antwort bezog sich ausschließlich auf die von mir ursprünglich zitierte Passage, d.h. die Tatsache, dass das Prädikat \(P(x)\) für jedes Element der Menge \(X\) gilt. Außerdem basiert dieser Teil auf der Annahme, dass das Prädikat tatsächlich so definiert sein sollte, wie es in der Lösung steht. Konkret beziehe ich mich in diesem Teil meiner Antwort nur auf folgenden Satz:
Musterlösung hat geschrieben:Observe that \(|{x \in X : P(x) = 1}| = |X|\)
.

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

Re: Ex. 1, Task 3

Beitrag von \Hannes » 26. Okt 2009 23:39

Vielleicht liegt das an dem generellen Verständnis des Grover-Algorithmus. Für mich heißt G(P,D) dass die Menge D nach Elementen x durchsucht wird, für die P(x) = 1 gilt (mit Wahrscheinlichkeit 1/4 blabla noch dazu ^^). D.h. wenn der Algorithmus P(x) betrachtet, dann ist dieses x aus der Menge D und wir vergleichen mit dem Prädikat quasi die zweiten Einträge der Tupel \((x',h(x')) (x' \in X)\) mit den Hashwerten \(h(x), x \in D\) und schließen mit der zweiten Forderung aus, dass \(x\) schon in X war.
Aus der Notation in der Musterlösung wird aber irgendwie auch nicht ersichtlich, woher das \(x'\) im Prädikat stammen soll. Da es aber als erstes Element eines Tupels im Prädikat vorkommt, bin ich von \(x' \in X\) ausgegangen.

Zu der Mächtigkeit der Menge der x, die das Prädikat mit 1 erfüllen: Mea culpa, da steht in der Tat \(x \in X\) in der Menge. Das sieht mir aber stark nach kopiert von oben (Einleitungstext der Aufgabe) aus und müsste meiner Meinung nach \(x \in D\) heißen. Du hast aber recht, das steht wirklich so da, etwas ungeschickt dass in der Einleitung die 'große' Menge X ist und hier D..
Was sagen die Verfasser? ;)
Schwabbeldiwapp hier kommt die Grütze.

rueckert
Mausschubser
Mausschubser
Beiträge: 57
Registriert: 9. Apr 2008 09:25

Re: Ex. 1, Task 3

Beitrag von rueckert » 27. Okt 2009 09:45

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.

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

Re: Ex. 1, Task 3

Beitrag von \Hannes » 27. Okt 2009 11:22

Ja, schon klar, sorry Mathematiker hier ;) Sorry allgemein fuer das staendige Nachfragen, aber ich wuerde das halt schon ganz gerne verstehen.
Also muss es in der Tat \((x',h(x)) \in L\) im Praedikat und \(|\{x \in D : P(x) = 1\}| = |X|\) heissen?
Schwabbeldiwapp hier kommt die Grütze.

rueckert
Mausschubser
Mausschubser
Beiträge: 57
Registriert: 9. Apr 2008 09:25

Re: Ex. 1, Task 3

Beitrag von rueckert » 27. Okt 2009 13:17

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.

Antworten

Zurück zu „Post-Quantum Cryptography“