0
$\begingroup$

Given $F$ a secure PRF with input size $\lambda$. Define $F'$ as

$F'(k,x||x') = F(k, 0||x)\oplus F(k, 1||x')$

with $x$ and $x'$ of $\lambda-1$ bits.

Is $F'$ a secure PRF?

$\endgroup$
0
$\begingroup$

No, $F'$ is not a secure PRF. There exists an efficient distinguisher $D$, which can distuingish between $F'$ and $f$ with overwhelming probability.

Imagine D asks her two oracles for the value of $F'(k,x'\mathbin\Vert x')$ and $f(x' \mathbin\Vert x')$.

$D$ additionally asks the following queries from her oracle: $$F'(k,x\mathbin\Vert x')=F(k,0\mathbin\Vert x)\oplus F(k,1\mathbin\Vert x')  $$ $$F'(k,x\mathbin\Vert x'')=F(k,0\mathbin\Vert x)\oplus F(k,1\mathbin\Vert x'')  $$ $$F'(k,x'\mathbin\Vert x'')=F(k,0\mathbin\Vert x')\oplus F(k,1\mathbin\Vert x'')  $$

Finally if she xor's all three of these values she can obtain $F'(k,x'\mathbin\Vert x')$: $$F'(k,x\mathbin\Vert x')\oplus F'(k,x\mathbin\Vert x'')\oplus F'(k,x'\mathbin\Vert x'')=F(k,0\mathbin\Vert x)\oplus F(k,1\mathbin\Vert x')\oplus F(k,0\mathbin\Vert x)\oplus F(k,1\mathbin\Vert x'')\oplus F(k,0\mathbin\Vert x')\oplus F(k,1\mathbin\Vert x'')=F(k,0\mathbin\Vert x')\oplus F(k,1\mathbin\Vert x')=F'(k,x'\mathbin\Vert x').$$

Therefore she can distinguish between $F'$ and $f$ with overwhelming probability. $D$ is trivially efficient (runs in polynomial time), as it only uses $3$ oracle queries.

| improve this answer | |
$\endgroup$

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