let $F(k,x)$ be a secure Pseudo-Random Function defined over $\{0,1\}^n$, that means:

$F: \{0,1\}^n \times \{0,1\}^n \rightarrow \{0,1\}^n$

define a $G(k,x) = F(k,x) \; \Vert \; 0$

how can one prove that $G$ is not secure?

in my point of view, as $F$ is secure, $G$ would always result in some secure output followed by 0, in other words I mean:

if you can't guess what $X$ is, you won't guess what $\;X \; \Vert \; 0\;$ is.

but as I'm asked to prove $G$ isn't secure, obviously there's something wrong with my thoughts.


The problem is that $G$ is easily distinguishable from the random function. Suppose we have an oracle that either applies a random function or your PRF (selected at the beginning of the game). We query the oracle $n$-times with $n$ different inputs, if all last bits are $0$ then we say that oracle uses PRF. To prove the insecurity you need to calculate

$Adv_F(A):=Pr[\text{you guess it's G | Oracle uses G}]-Pr[\text{you guess it's G | Oracle uses random RF}]$.

The first probability is equal to $1$ (if $A$=attacker using suggested approach). The second probability goes to zero exponentially thus with $n$ sufficiently high (in this case even $n=4$ provides sufficient advantage) the advantage $\textit{significantly}$ differs from RF's advantage.

"Real" world example: suppose you use your F(k,x) as a block-cipher in counter mode. Then you effectively know every last bit of the plaintext just by looking at the ciphertext.

  • $\begingroup$ could you explain why "the second probability goes to zero exponentially" ? $\endgroup$ – Daniel Apr 17 '18 at 1:00
  • $\begingroup$ Since in the second case a RF is used then the $Pr[\text{last bit of RF's output = 1}]=1/2$ and the outputs are independent (as random variables, provided $A$ uses different inputs). If we want the probability of getting a sequence of $n$ zeroes from RF then we just have to take $(1/2)^n$. $\endgroup$ – boethius Apr 18 '18 at 5:19

You are confusing secure with pseudo random. If you can mount a pre image atrack or collision attack on G you can do the same on F.

However is G pseudo random? Can you distinguish between it and something random?

  • $\begingroup$ no, I'm not confusing anything... a secure pseudo-random function is a function such that the adversary's advantage is negligible for all efficient adversaries, as stated here at page 131 $\endgroup$ – Daniel Apr 14 '18 at 5:12
  • $\begingroup$ As this looked like homework, I was trying to stop short of giving the answer. Secure, is many things in different setups. In different setups you have various requirements such as pre image resistance. The strongest requirement is indistinguishable from random. And that is what you can show. The output of G is clearly not random. $\endgroup$ – Meir Maor Apr 14 '18 at 5:24

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.