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?

  • $\begingroup$ 1 is correct. 2 is not, because the distinguisher is not given the seed, so it cannot compute $x_1 \vee x_2$. $\endgroup$ – fkraiem Mar 7 '16 at 16:10
  • $\begingroup$ And for 3, I don't understand your notation. $\endgroup$ – fkraiem Mar 7 '16 at 16:11
  • $\begingroup$ 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.) $\endgroup$ – Daniel Apon Mar 7 '16 at 16:22
  • $\begingroup$ @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 $\endgroup$ – Lemon Mar 7 '16 at 16:50
  • $\begingroup$ @DanielApon I'm not sure whether I fully understand your solution. Could you rephrase it? $\endgroup$ – Lemon Mar 7 '16 at 16:52

I have fully solved the questions now.

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.