1
$\begingroup$

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?

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

1 Answer 1

1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking β€œPost Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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