1. Übung, Task 4

DMT
Windoof-User
Windoof-User
Beiträge: 25
Registriert: 18. Dez 2007 23:54

1. Übung, Task 4

Beitrag von DMT » 24. Feb 2009 14:55

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...
"Quis custodiet ipsos custodes?"
~Juvenal

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

Re: 1. Übung, Task 4

Beitrag von rueckert » 24. Feb 2009 15:28

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.

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

Re: 1. Übung, Task 4

Beitrag von Patr0rc » 24. Feb 2009 17:09

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...

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

Re: 1. Übung, Task 4

Beitrag von rueckert » 25. Feb 2009 07:51

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.

DMT
Windoof-User
Windoof-User
Beiträge: 25
Registriert: 18. Dez 2007 23:54

Re: 1. Übung, Task 4

Beitrag von DMT » 25. Feb 2009 11:39

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...
"Quis custodiet ipsos custodes?"
~Juvenal

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

Re: 1. Übung, Task 4

Beitrag von rueckert » 25. Feb 2009 14:09

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.

Antworten

Zurück zu „Archiv“