How to prove that a pseudorandom generator is a pseudorandom generator or not

Asked Sep 14 '20 at 22:48

Active Sep 15 '20 at 14:09

Viewed 187 times

Let $F,G:\{0,1\}^n\rightarrow\{0,1\}^{2n}$ be pseudorandom generators. For each of the functions below, prove or disprove that $H$ is necessarily a pseudorandom generator.

$H(s_0s_1...s_{n-1}):=G(s_{n-1}s_{n-2}...s_0),$ where $s_0,s_1,...,s_{n-1}$ are single bits.

I know that above given $H$ is not a pseudorandom generator but can someone help me or give a start on how to prove this.

edited Sep 15 '20 at 14:09

Kenta S

16,151
15
26
53

asked Sep 14 '20 at 22:48

Krish

To start, what is your definition of a pseudorandom generator? – Sep 15 '20 at 00:45
@SenZen probably based on some distinguishing security game. – Henno Brandsma Sep 16 '20 at 05:21
Of course, of $G$ is secure, so is $H$. It just treats the inputs in different order. – Henno Brandsma Sep 16 '20 at 16:46

How to prove that a pseudorandom generator is a pseudorandom generator or not

0 Answers0