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