Is this function a secure PRF?

Question

I have a PRF function $F(k, F(k,0)) = 0$. So that means, $k \times F(k,0) \rightarrow F(k, 0)$.

I hope you can help me understand if the function $F(k, F(k,0))$ is a secure PRF or no?

Thanks for considering my request!

Answer 1

I read the question as asking if $F$ can be a PRF, given that it is such that $F(k, F(k,0)) = 0$.

Assume you are given a black box that implements a function: given some input $x$, it outputs a result $y$, such that the same input $x$ always give the same output $y$. It is given that one of the following holds:

• 0: The box is a random oracle (equivalently: implements a Pseudo-Random Function); that is, the box outputs a random $y$ when given a new $x$, and otherwise outputs the same $y$ that it has output for that previously submitted $x$;
• 1: The box outputs $y=F(k,x)$ for some fixed unknown $k$, with $F$ your function such that $F(k, F(k,0)) = 0$.

You are free to use the box. Can you design an experiment to determine, with high confidence, which of 0 or 1 holds? If yes, what's that experiment? The definition of an experiment should include what input(s) it submits to the box under test, and what it performs with the box's output(s) and any other quantity that it manipulates in order to reach a decision/result that can be only be either 0 or 1. Such experiment would allow to recognize $F$ from a PRF, that is prove that $F$ is not a PRF.

More formally: you need to exhibit an experiment better than random at distinguishing 0 from 1, and prove that by showing it gives positive advantage (or, even more formally, non-vanishing advantage when the bit size of $F$ grows). The advantage (given by an experiment) is the difference between odds that the experiment concludes that 1 holds when 1 holds, minus odds that the experiment concludes 1 holds when 0 holds $$Adv=\Pr[\,\text{Exp}(1)=1\,]-\Pr[\,\text{Exp}(0)=1\,]$$ where the parenthesis after $\text{Exp}$ contains the situation in which the experiment is run. Reversing 0 and 1 leaves the advantage unchanged.

Many texts define the advantage with an absolute value: this addition is only there to fix an experiment that guesses wrong better than random, and consequently to allow simplifying the description of experiments by only telling the principle used to make some decision, leaving the decision itself unspecified.

Defining the experiment clearly is the first step in a proof involving computing its advantage. In the context, experiment has alternate names: algorithm is more formal; I find adversary more descriptive of reality, but it is known to create confusion with advantage.

Answer 2

Consider the Experiment where adversary sends m0 and m1 and gets encryption of either m0 or m1. Now he has to figure out he got encryption of m0 or m1. Adversary can proceed in following way

1. Adversary sends m0=0,m1(any random value) and gets m' which is encryption of either m0 or m1.
2. Now Adversary sends m' and m1, and get m'' which is either encryption of m' or m1

Since we know F(k,F(k,0))=0, if m''=0, then Adversary got encryption of m0 otherwise he got encryption of m1. Thus Adversary clearly wins the game.