1
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ But $F(k, F(k,0)) = 0$. Surely $0$ isn't a secure PRF? $\endgroup$ – squeamish ossifrage May 22 '17 at 6:11
  • $\begingroup$ @squeamishossifrage, can you give me more detail? $\endgroup$ – Pale May 22 '17 at 6:24
  • 2
    $\begingroup$ Well, zero is obviously not random, so neither is $F(k,F(k,0))$. Perhaps you meant to ask whether $F(k)$ can possibly be a PRF, given that $F(k,F(k,0)) = 0$? If so, I think @fgrieu has answered this question for you. $\endgroup$ – squeamish ossifrage May 22 '17 at 6:54
  • $\begingroup$ In the first line, there is an error: You wrote $k \times F(k,0) \rightarrow F(k,0)$, that's wrong. The righthand side of that should be $0$ - the arrow indicates the transformation under $F$. $\endgroup$ – tylo May 23 '17 at 12:50
  • $\begingroup$ @tylo , that I read from defining PRP and PRF. Thank you. $\endgroup$ – Pale May 24 '17 at 3:19
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks, @fgrieu. So in F(k,x), x equal F(k,0). But in defined, we need to calculate PRF advantage (Adv ). I still don't understand this step. $\endgroup$ – Pale May 22 '17 at 6:47
  • $\begingroup$ the advantage is 1. and Adv will win the game. For input x=0, output y=0, and for input x=1, output y=1 or some linear function of k i.e k * 1 $\endgroup$ – khan May 22 '17 at 7:02
  • $\begingroup$ we sent m0=0 and get output, then we send m1=1 and get its output, if output = 1 or output = k*K*1, then we can predict further outputs. i may be wrong but i would like to learn more about it. how to go about calculating advantage. $\endgroup$ – khan May 22 '17 at 7:11
  • $\begingroup$ @fgrieu, If F is a secure PRF if Adv[A,F] = |Pr[EXP(0)=1] – Pr[EXP(1)=1] | is negligible. But I still don't see the way how to prove that. I hope you can help me. $\endgroup$ – Pale May 24 '17 at 3:13
  • $\begingroup$ @fgrieu, PRF defined over (K, X, Y): F: K x X -> Y. From your help, i think k = K and X = F(k, 0) so if X = 0 to K x 0 -> 0 and if X = 1 to K x 1 -> 1. After that, advantage close to 1. That why F is not a secure PRF ? What do you think about this ? $\endgroup$ – Pale May 24 '17 at 6:47
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ @fgrieu, so I can confirm that F(k , F(k , 0)) not secure PRF, is that right ? $\endgroup$ – Pale May 24 '17 at 6:21
  • $\begingroup$ I do not understand the meaning/need for ",m1(any random value)" in step 1, nor for "and m1" in step 2. I propose the experiment : supply $m_0=0$ and get $m'$; then supply $m_1=m'$ and get $m''$; output $1$ iff $m''=0$, or $0$ otherwise. $m'$ is either the encryption of $0$ if the device under test if $F$, or random (possibly $0$) otherwise. $m''$ is $0$ if the device under test if $F$ or if random $m'$ was $0$, and $m''$ is random (possibly $0$) otherwise. If follows that $\Pr[\,\text{Exp}(1)=1\,]$ is $1$ and $\Pr[\,\text{Exp}(0)=1\,]$ is $1-(1-2^{-n})^2$ where $n$ is the number of bits. $\endgroup$ – fgrieu May 24 '17 at 10:11
  • $\begingroup$ i have defined the experiment as following, "dversary 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". if challenger decides to encrypt m0 or m1 truely randomly and cipher encrypts like random, then adversary cant correctly guess with probability more than 0.5. since in this case adversary has found a way to correctly guess that he was given encryption of m0 or m1 after just two queries, so adversary wins the game, and he has advantage near to 1 $\endgroup$ – khan May 24 '17 at 16:57
  • $\begingroup$ yeah you are right, game can be defined with query of single message (m0) too, $\endgroup$ – khan May 24 '17 at 16:59

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.