3
$\begingroup$

Let $F(k,x)$ be a secure PRF over $(\mathcal{K},\mathcal{X},\mathcal{Y})$ where $\mathcal{K} = \mathcal{X} = \mathcal{Y} = \{0,1\}^n$.

Let $F'(k, x) = F(F(k, 0^n), x) \; \Vert \; F(k, x)$.

$a \; \Vert \; b$ means $a$ concatenated to $b$.

How can I show that $F'$ is not a secure PRF? I've been trying to build an adversary that could find some pattern but I couldn't. My best guess was to initially use $x = 0^n$, so the output would be something like $F(k', 0^n) \; \Vert \; k'$ (where $k' = F(k, 0^n)$, which is the key of the left side) and I would be able to use $k'$ for the next calculations, but it didn't seem to be enought to find any pattern in the sequence of outputs.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
2
$\begingroup$

Query $0^n$ to your oracle, receive $a\Vert b$ as a response. If $F(b,0^n) = a$ output $1$, otherwise output $0$.

In the case that the oracle is $F'$, since $F'(k,x)$ is defined as $F(F(k,0^n),x)\Vert F(k,x)$ your response will be $a\Vert b = F(F(k,0^n),0^n)\Vert F(k,0^n) = F(k',0^n)\Vert k'$, it will always be true that $F(b,0^n) = a$. I.e. $$\Pr_k[\mathcal{A}^{F'(k,\cdot)}(1^n)=1] = 1.$$

In the case that the oracle is a truly random function $g : \{0,1\}^n \times \{0,1\}^n \to \{0,1\}^n$, $a$ is distributed uniformly and independently of $b$. Therefore the probability of $F(b,0^n) = a$ is $2^{-n}$. Thus, $$\Pr_g[\mathcal{A}^{g(\cdot)}(1^n)=1] = 2^{-n}.$$

And therefore

$$\left|\Pr_k[\mathcal{A}^{F'(k,\cdot)}(1^n)=1]-\Pr_g[\mathcal{A}^{g(\cdot)}(1^n)=1]\right|=1-2^{-n},$$ which is clearly non-negligible.

Improve this answer
$\endgroup$
5
  • $\begingroup$ What's the meaning of this first line? You call the output $a \Vert b$ and then ask if $F(b, 0^n) = a$, but you just defined $F(b, 0^n) = a$ when you said the output was $a \Vert b$, it looks to me like comparing $x$ with $x$. $\endgroup$
    – Daniel
    Apr 17, 2018 at 20:53
  • $\begingroup$ I did not define $F(b,0^n)=a$. I defined $a\Vert b$ as the output of the oracle. The oracle is either the PRF with a uniformly chosen random key (in which case it happens to be true that $F(b,0^n)=a$) or it is a truly random function (in which case it is highly unlikely). And your distinguisher needs to distinguish between those two cases. I get the feeling that maybe your problem is a misunderstanding of the definition of a PRF? $\endgroup$
    – Maeher
    Apr 17, 2018 at 22:12
  • $\begingroup$ The function $F$ is known and both inputs are known (the key is $b$ and the input is $0^n$). So you just compute the value. $\endgroup$
    – Maeher
    Apr 18, 2018 at 1:36
  • $\begingroup$ @Maeher do we have oracle access to $F(k,x)$ by the PRF definition for every $k$ of our choice? It seems to me as if the definition only gives $F(k,x)$ with a fixed $k$ (uniformly random, not of our choice) or $f(x)$: random... Where is my misunderstanding? $\endgroup$
    – user16972
    Nov 27, 2019 at 0:31
  • $\begingroup$ @Jason if you choose the key, you don't need an oracle. You know the description of the algorithm for computing $F$, so just follow it for the key and input of your choice. $\endgroup$
    – Maeher
    Nov 27, 2019 at 7:16
0
$\begingroup$

Let $F_k(x)=F(k,x)$ and $F'_k(x)=F'(k,x)$.

A PPT distinguisher $\mathcal{D}$ with access to an oracle $\mathcal{O}(x)=F'_k(x)$ can query it for $$F'_k(0^n)=F_{F_k(0^n)}(0^n)||\overbrace{F_k(0^n)}^a \in \{0,1\}^{2n}$$ we ignore the first part and keep part $a$

Then pick random input $x\in \{0,1\}^n$ and compute the value $b=F_{a}(x)=F_{F_k(0^n)}(x)$

Lastly $\mathcal{D}$ can query $\mathcal{O}$ for $F'_k(x)=\overbrace{F_{F_k(0^n)}(x)}^c||F_k(x)$ and output $1$ if $b=c$, 0 otherwise.

Clearly, this distinguisher runs in polynomial time and distinguishes $F'_k(x)$ from a random function $f(x)\in Func_{2n}$ with non-negligable probability.

Improve this answer
$\endgroup$
3
  • $\begingroup$ didn't make sense for me... in the middle step you pick random input $x$ and say $b = F_{F_k(0^n)}(x)$ and in the last step you pick input $x$ and say $c = F_{F_k(0^n)}(x)$, so what's the meaning at comparing $b$ and $c$ if they are obviously equal? $\endgroup$
    – Daniel
    Apr 17, 2018 at 20:47
  • $\begingroup$ $b$ and $c$ are equal when the oracle is equal to $F'_k$ and with negligible probability when the oracle is a uniform function $f$. This allows $\mathcal{D}$ to distinguish $F'_k$ from $f$ and thus $F'_k$ is not a PRF. $\endgroup$
    – Shadowfirex
    Apr 18, 2018 at 7:18
  • $\begingroup$ Also we sample $x \in \{0,1\}$ only once. $\endgroup$
    – Shadowfirex
    Apr 18, 2018 at 7:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.