2
$\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.

$\endgroup$
1
$\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.

$\endgroup$
  • $\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 '18 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 '18 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 '18 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$ – Jason Nov 27 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 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.

$\endgroup$
  • $\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 '18 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 '18 at 7:18
  • $\begingroup$ Also we sample $x \in \{0,1\}$ only once. $\endgroup$ – Shadowfirex Apr 18 '18 at 7:20

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.