Determine whether a given function is a pseudorandom generator/function

Question

I am trying to solve the following three tasks (for exam practice, not as a homework):

Define $𝐺 : \{0,1\}^* \rightarrow \{0,1\}^*$ by $G(x_1,...,x_n) = 𝑥_1 \oplus 𝑥_2,𝑥_1,⋅⋅⋅,x_n.$ Prove that this $G$ is not a pseudorandom generator.
Let $G$ be a pseudorandom generator, and define $G'(x_1, ..., x_n) = G(x_1, ..., x_n)|(x_1 \vee x_2)$. Is $G'$ a pseudorandom generator?
Define $𝐹 : \{0,1\}^* × \{0,1\}^* \rightarrow \{0,1\}^*$ as follows: $𝐹_{𝑘_1,...,𝑘_𝑛} (𝑥_1,..., 𝑥_𝑛) = \bigoplus_i 𝑘_𝑖 𝑥_𝑖$, where $𝑘_𝑖, 𝑥_𝑖 \in \{0,1\}^*$ (Note that, different from the usual convention, $F$ takes an n-bit key and an n-bit input, but has only a single-bit output). Prove that this 𝐹 is not a pseudorandom function.

My guesses are:

Not a pseudorandom generator since a distinguisher can always distinguish G(s) from a truly random string because the first bit of G(s) is always equal to the XOR of the second and third bit.
Not a pseudorandom generator because a distinguisher could simply check whether the last bit of the string equals $x_1 \vee x_2$ and could thus distinguish G(s) from a truly random string.
I cannot determine how to solve this.

Are my guesses correct? Can someone provide an idea for 3?

1 is correct. 2 is not, because the distinguisher is not given the seed, so it cannot compute $x_1 \vee x_2$. — fkraiem, Mar 7, 2016 at 16:10
3- the intuition should be that the one-time pad (i.e. XOR'ing bits) is no longer secure if the 'secret randomness' (the $k_i$ here) is re-used. (Focus on the case of $x_i, k_i\in\{0,1\}$. Among other approaches to this.. consider an Adv that asks for many samples $x_i$ in different 'directions' e.g. $x_1 = (1, 0, 0...), x_2 =(0, 1, 0, ...), x_3 = (0, 0, 1, ..), ...$ then once it's saturated the space, queries once more anywhere.) — Daniel Apon, Mar 7, 2016 at 16:22
@fkraiem, regarding 2. So this is a PRG? Or it is not but my solution is incorrect? regarding 3. I have added a sentence that was part of the original question — Lemon, Mar 7, 2016 at 16:50
@DanielApon I'm not sure whether I fully understand your solution. Could you rephrase it? — Lemon, Mar 7, 2016 at 16:52

Lemon · Accepted Answer · 2016-03-09 15:03:28Z

I have fully solved the questions now.

Not a pseudorandom generator since the first bit of $G(s)$ is always equal to the XOR of the second and third bit, i.e. a distinguisher can easily tell $G(s)$ apart from a truly random string $r$.
Not a pseudorandom generator. We can for example construct a distinguisher $D$ that, on input of a string $w$, outputs 1 if and only if the final bit is 0. If $w$ is uniformly distributed then the final bit is 0 with probability $\frac{1}{2}$ but if $w = G(s)$ for a uniformly distributed seed s the final bit will be 0 with probability $\frac{1}{4}$.
Not a pseudorandom function. A distinguisher D could tell $F_k$ apart from a truly random function $f$ in the following way: Given access to an oracle $W$, D queries $W(0...0)$. If $W = F_k$ then the result will always be 0, but if $W$ is a random function then it should be 0 only with probability $\frac{1}{2}$.

1 Answer 1