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$

closed as off-topic by fkraiem, kelalaka, AleksanderRas, yyyyyyy, Maarten Bodewes Aug 18 at 13:57

This question appears to be off-topic. The users who voted to close gave this specific reason:

If this question can be reworded to fit the rules in the help center, please edit the question.

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.

$\endgroup$

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