How to show the PRF in 2. is secure?

LJCOUC

2/25/23, 4:21 AM

Let F be a PRF defined over F:{0,1}n×{0,1}n→Y.

1.We say that F is XOR-malleable if F(k,x⊕c)=F(k,x)⊕c for all k,x,c∈{0,1}n.

2.We say that F is key XOR-malleable if F(k⊕c,x)=F(k,x)⊕c for all k,x,c∈{0,1}n.

Clearly an XOR-malleable PRF cannot be secure: malleability lets an attacker distinguish the PRF from a random function.Show that the same holds for a key XOR-malleable PRF.

Remark: In contrast, we note that there are secure PRFs where F(k1⊕k2,x)=F(k1,x)⊕F(k2,x).

I've done it. Next, I'll put my ideas in the comments.

0 + 0

pseudo-random-function

LJCOUC

2/25/23, 4:26 AM

Let k'=k⊕c, then F(k',x)=F(k⊕c,x)=F(0n,x)⊕k⊕c; Construct experiment 0 and Experiment 1. The attacker sends x to the Challenger respectively. In experiment 0, the Challenger returns y=F(k',x) to the attacker. In Experiment 1, the attacker returns a pseudo-random sequence to the attacker. The attacker can calculate the key according to k'=k⊕c=F(k',x)⊕F(0n,x), so as to distinguish the two experiments.

Manish Adhikari

2/25/23, 10:45 AM

This is a repeat question. Anyway, you got it. But you can simply say $F(k,x)=F(0^n,x)⊕k$, and make it simple revealing the key $k$ in a single query. I meant to say to use $k'=0^n$ to make it simple