Skip to main content
added 556 characters in body
Source Link
tylo
  • 12.8k
  • 25
  • 39

There are actually two different ways to do this, I will give hints for both, with additional hints in the spoilers:

First approach: Think about the definition of the security game again, and how many queries can a distinguisher make to the oracle?

You can query the function on two values. If you compare those two results, are there similarities? And how would a truly random function behave?

Second approach: As others have stated in the comments, what happens if you query $F'(0^n)$$F_k'(0^n)$?

Since $F_k(0^n)$ is a PRF, you can just assume that this one is actually a truly random function. What happens if you query a truly random function twice? Is that visible in some way in $F'(0^n)$$F_k'(0^n)$?

From your last comment, I guess this isn't clear yet: The distinguisher can query the function for any kind of $x$, as often as he wants - with the limitation of being a polynomial time algorithm. And he has to find out whether the results he gets back are from a truly random function or from $F_k'(.)$, with just $k$ being drawn randomly. So the distinguisher can only do one thing: Choose $x$ in a clever way, so that some structure appears within one result or over several results, if it is $F_k'$ - and the random function does not have that.

There are actually two different ways to do this, I will give hints for both, with additional hints in the spoilers:

First approach: Think about the definition of the security game again, and how many queries can a distinguisher make to the oracle?

You can query the function on two values. If you compare those two results, are there similarities? And how would a truly random function behave?

Second approach: As others have stated in the comments, what happens if you query $F'(0^n)$?

Since $F_k(0^n)$ is a PRF, you can just assume that this one is actually a truly random function. What happens if you query a truly random function twice? Is that visible in some way in $F'(0^n)$?

There are actually two different ways to do this, I will give hints for both, with additional hints in the spoilers:

First approach: Think about the definition of the security game again, and how many queries can a distinguisher make to the oracle?

You can query the function on two values. If you compare those two results, are there similarities? And how would a truly random function behave?

Second approach: As others have stated in the comments, what happens if you query $F_k'(0^n)$?

Since $F_k(0^n)$ is a PRF, you can just assume that this one is actually a truly random function. What happens if you query a truly random function twice? Is that visible in some way in $F_k'(0^n)$?

From your last comment, I guess this isn't clear yet: The distinguisher can query the function for any kind of $x$, as often as he wants - with the limitation of being a polynomial time algorithm. And he has to find out whether the results he gets back are from a truly random function or from $F_k'(.)$, with just $k$ being drawn randomly. So the distinguisher can only do one thing: Choose $x$ in a clever way, so that some structure appears within one result or over several results, if it is $F_k'$ - and the random function does not have that.

Source Link
tylo
  • 12.8k
  • 25
  • 39

There are actually two different ways to do this, I will give hints for both, with additional hints in the spoilers:

First approach: Think about the definition of the security game again, and how many queries can a distinguisher make to the oracle?

You can query the function on two values. If you compare those two results, are there similarities? And how would a truly random function behave?

Second approach: As others have stated in the comments, what happens if you query $F'(0^n)$?

Since $F_k(0^n)$ is a PRF, you can just assume that this one is actually a truly random function. What happens if you query a truly random function twice? Is that visible in some way in $F'(0^n)$?