4
$\begingroup$

Let $F:\{0,1\}^n \times \{0,1\}^n \rightarrow \{0,1\}^n$ be a secure PRF (i.e. a PRF where the key space, input space, and output space are all $\{0,1\}^n$) and say $n=128$.

My assignment is to show that the function $F'(k,x) = F(k,x)$ when $x \ne 0^n$ and $F'(k,x)=k$ when $x=0^n$ is not a secure PRF, but the function $F''((k_1,k_2),x)) = F(k_1,x)$ when $x \ne 0$ and $F''((k_1,k_2,x)=k_2$ when $x=0^n$ is a secure PRF.

However, I think that both are secure PRFs. Because when the input is $0^n$, above $F'(k,x)$ and $F''((k1,k2),x)$ will return $k$ and $k_2$ which are randomly chosen from their keyspace. So, even though adversary inputs $0^n$ multiple times it can only find out some random $\{0,1\}^n$.

Can you tell me what's wrong with my reasoning?

Improve this question
$\endgroup$
2
  • $\begingroup$ in the third paragraph it should be "will return 𝑘 and 𝑘_2 which...." and not $k_1$. $\endgroup$
    – A.Solei
    Commented Apr 16, 2021 at 5:31
  • $\begingroup$ Imagine the second one as defining a special value for 0 independent of the main key. $\endgroup$
    – SEJPM
    Commented Apr 16, 2021 at 7:33

1 Answer 1

Reset to default
1
$\begingroup$

Informally, the security of a PRF is defined as follows:

The adversary is allowed to ask questions from its oracle. The oracle choose one of the functions $F$ or $f$ at the beginning, where $f$ is a truly random function with the same domain and image as $F$. When the adversary $A$ sends a query on $x$, the oracle returns the answer $F(k,x)$ or $f(x)$, depending on which one it has chosen at the beginning. We say that $F$ is a secure PRF if $A$ can not distinguish which function the oracle has chosen.

Now whit this explanation, for your first function, the adversary sends a query on a nonzero $x^*$, then a query on zero, when it receives $k$, it compute $F(k,x^*)$ if it was the same as the answer it has received for $x^*$ from the oracle, it distinguishes that the oracle has chosen $F$.

For the second function, the same attack does not work, because the adversary does not know the whole key yet.

Improve this answer
$\endgroup$
7
  • $\begingroup$ Thank you for your answer. But as far as i understand, F'(k1, x*) = F(k1, x*) and F'(k2, 0^n) = k2.(k1 and k2 are randomly chosen from their keyspace each) And the probability of k1 and k2 be equal is neglible. Since key space is 128 bits binary string. So that the advantage of adversary is negligible. Is their any wrong with it? $\endgroup$
    – blueMountain
    Commented Apr 16, 2021 at 8:04
  • $\begingroup$ More precisely, for the second function $F'((k_1,k_2),x^*)=F(k_1,x^*)$ and $F'((k_1,k_2),0^n)=k_2$ . And as you said in this case $k_2$ does not give any information about $k_1$ if the keyspace is big enough and keys are chosen randomly. $\endgroup$
    – A.Solei
    Commented Apr 16, 2021 at 8:58
  • $\begingroup$ I appreciate your kindness. But for this function $F'(k,x) = F(k,x)$ when $x \ne 0^n$ otherwise $k$, if i input $x^*$ it'll return $F(k, x^*)$ then if i input $0^n$ it'll return $k'$. Then how can it compute $F(k,x^*)$? It has no info about $k$ and the only info it has is $k'$. $\endgroup$
    – blueMountain
    Commented Apr 16, 2021 at 9:43
  • $\begingroup$ You are mistaken in your assumption that the key is sampled independently for each query. The key is sampled once and remains fixed for all queries. $\endgroup$
    – Maeher
    Commented Apr 16, 2021 at 9:50
  • $\begingroup$ Then, why $F''((k_1,k_2),x)) = F(k_1,x)$ when $x \ne 0$ and $F''((k_1,k_2,x)=k_2$ when $x=0^n$ is secure PRF? If i input $0^n$ it'll always return determined k2. So adversary can distinguish it from really random function. $\endgroup$
    – blueMountain
    Commented Apr 16, 2021 at 10:28

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.