# Determine whether a given function is a pseudorandom generator/function

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

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

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

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

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

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

3. 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 '16 at 16:10
• And for 3, I don't understand your notation. – fkraiem Mar 7 '16 at 16:11
• 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 '16 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 '16 at 16:50
• @DanielApon I'm not sure whether I fully understand your solution. Could you rephrase it? – Lemon Mar 7 '16 at 16:52

1. 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$.
2. 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}$.
3. 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}$.