Übung 4 Aufgabe 2c: PRGs

Benutzeravatar
ob1
Windoof-User
Windoof-User
Beiträge: 37
Registriert: 10. Dez 2012 14:30

Übung 4 Aufgabe 2c: PRGs

Beitrag von ob1 » 4. Feb 2015 16:24

Hallo,

ich hätte eine Frage zur Übung 4 Aufgabe 2c ((Pseudozufallsgeneratoren).

Die Frage war, wenn G PRG ist, ist dann auch G*: x1||x2 -> G(x1)||G(x2) ein PRG?

Würde es hier nicht reichen wenn man argumentiert, dass G(x1) und G(x2) jeweils uniform verteilt sind auf {0,1}^2n (weil PRG, damit fällt aus meiner Sicht der "Hinweis" schon mal weg da trivial), und G(x1)||G(x2) daher ebenfalls uniform auf {0,1}^4n verteilt sein muss? Was dann ja wiederum heißt, G*(x) ist ununterscheidbar zu jeder anderen uniformen Verteilung und damit PRG.

Könnte man das so ohne weiteren Beweis benutzen? Ich frage deshalb, weil mir so eine Abkürzung in der Klausur natürlich sehr viel Zeit sparen würde :D Ich finde es etwas lästig immer über einen Unterscheider D zu argumentieren, wobei der Beweis ja für alle uniformen Verteilungen gleich aussieht (--> nicht unterscheidbar).

Viele Grüße, Philipp

Zurück zu „Archiv“