Seite 1 von 1

1. Übung, Task 4

Verfasst: 24. Feb 2009 14:55
von DMT
Hallo ihr Gitterheroes,
wir machen uns grade Gedanken über die Lösung von Aufgabe 4 b) aus Übung 1. Generell haben wir uns überlegt, dass die Identität eigentlich ein besseres Beispiel
wäre für eine collisionsresitente Funktion, die aber nicht One-way ist.

Uns ist nicht so ganz klar, dass die Lösung so stimmt, weil der Angreifer nur mit der Wahrscheinlichkeit Pr[ |x|=n-1 ] ein gültiges Urbild erzeugen kann. Wir haben aber x zufällig gewählt und somit ist die Wahrscheinlichkeit, dass x grade die Länge n-1 hat, eher gering...

Re: 1. Übung, Task 4

Verfasst: 24. Feb 2009 15:28
von rueckert
DMT hat geschrieben:Hallo ihr Gitterheroes,
wir machen uns grade Gedanken über die Lösung von Aufgabe 4 b) aus Übung 1. Generell haben wir uns überlegt, dass die Identität eigentlich ein besseres Beispiel
wäre für eine collisionsresitente Funktion, die aber nicht One-way ist.
Korrekt. Solche Separationsresultate werden aber typischerweise mit Black-box Transformationen gemacht. Also angenommen, es existiert eine CR Funktion f, dann bauen wir eine CR Funktion f' und f' ist nicht mehr OW, auch wenn f es war. Das ist etwas stärker als ein einfaches Gegenbeispiel zu geben.

DMT hat geschrieben:Uns ist nicht so ganz klar, dass die Lösung so stimmt, weil der Angreifer nur mit der Wahrscheinlichkeit Pr[ |x|=n-1 ] ein gütiges Urbild erzeugen kann. Wir haben aber x zufällig gewählt und somit ist die Wahrscheinlichkeit, dass x grade die Länge n-1 hat, eher gering...
Im OW Experiment bekommt man ein zufälliges Bild der Länge n. Die Wsk, dass das erste Bit 1 ist, ist 1/2. Daraus ergibt sich die Erfolgswsk. 1/2 für den Angreifer auf OW.

Re: 1. Übung, Task 4

Verfasst: 24. Feb 2009 17:09
von Patr0rc
rueckert hat geschrieben:
DMT hat geschrieben:Uns ist nicht so ganz klar, dass die Lösung so stimmt, weil der Angreifer nur mit der Wahrscheinlichkeit Pr[ |x|=n-1 ] ein gütiges Urbild erzeugen kann. Wir haben aber x zufällig gewählt und somit ist die Wahrscheinlichkeit, dass x grade die Länge n-1 hat, eher gering...
Im OW Experiment bekommt man ein zufälliges Bild der Länge n. Die Wsk, dass das erste Bit 1 ist, ist 1/2. Daraus ergibt sich die Erfolgswsk. 1/2 für den Angreifer auf OW.
Dass die Erfolgswahrscheinlichkeit dafür, dass das erste Bit eine "1" ist, 1/2 ist, ist klar. Die Sache ist nur, dass doch die Wahrscheinlichkeit auch über die Zufallsbits von x gebildet wird, also über das Urbild dazu, siehe Folie 2 von https://www.cdc.informatik.tu-darmstadt ... ypto01.pdf, oder wo liegt der Fehler in der Überlegung?

---- EDIT: Kann es sein, dass wir einfach ein Urbild x finden müssen, für das die Wahrscheinlichkeit, dass wir dieses Urbild aus seinem Bild rekonstruieren können, nicht vernachlässigbar ist? Ich glaube, hier hakt es bei unserer Überlegung ein wenig...

Re: 1. Übung, Task 4

Verfasst: 25. Feb 2009 07:51
von rueckert
So kann man es auch sagen. Beachtet aber bitte, dass wir eine etwas andere Definition von OW haben.
Der Angreifer bekommt direkt ein Bild y und soll ein Urbild x finden. Für y weiß man, wie groß die Wsk für eine 1 an der ersten Stelle ist. In diesem Fall, also mit Wsk 1/2, kann man das Urbild ganz einfach ablesen. Bitte nochmal in Ruhe darüber nachdenken.

Re: 1. Übung, Task 4

Verfasst: 25. Feb 2009 11:39
von DMT
Ok aber ist das nicht ziemlich komisch, sich DIREKT das y zu wählen... Ich meine, dann könnten wir auch eine konstante Funktion nehmen und wenn dann nur y zufällig gewählt wird, wird es ziemlich schwer, ein Urbild zu finden, weil das y mit sehr großer Wahrscheinlichkeit kein Urbild besitzt.
Unserer Meinung nach MUSS man sich ein x zufällig wählen, das dann in die one-way Funktion gesteckt wird und dieses Bild f(x) bekommt dann der Angreifer...

Re: 1. Übung, Task 4

Verfasst: 25. Feb 2009 14:09
von rueckert
Wie gesagt, es gibt beide Definitionen und beide machen "irgendwie" Sinn. Bei beiden gibt es aber hin und wieder kleine Probleme. Die Separation OW <=/=> CR funktioniert aber in beiden Modellen. Die Erfolgswsk. ist ggf. anders. Das macht aber nicht, wie du schon richtig bemerkt hast. Sie muss lediglich nicht vernachlässigbar sein.