# is XOR-hash difference-unpredictable

Let $F$ be a PRF.

The $XOR\text{-hash}$ is defined as:

XOR-hash(k, m):    //m=(a₀, a₁, ..., aᵥ)
t = 0ⁿ
for each aᵢ ∈ m:
t = t ⊕ F(k, aᵢ)
return t


Suppose an attacker $\mathcal{A}$ can send 3-uples $(m_0, m_1, \delta)$.

A function $f$ will be difference-unpredictable if $\mathcal{A}$ cannot guess a 3-uple such that $f(k,m_0) - f(k,m_1) = \delta \;$ with more than negligible chance.

How can I show that $XOR\text{-hash}$ is difference-unpredictable?

I think the argument relies on the fact that $\oplus$ keep all the bits pseudo-random, so that the difference $d$ will look like a subtraction of two random results, hence the probability of some bit of $d$ match some bit of $\delta$ will be $\small\sim$$0.5$ and the probability of $d = \delta$ would be negligible.

• I assume $m_0$ and $m_1$ must be distinct. $(0 \mathbin\Vert 1, 1 \mathbin\Vert 0, 0)$? – Squeamish Ossifrage May 15 '18 at 3:32

You cannot prove that this is difference unpredictable since it is not. Take $\delta=0$ and set $m_0=(a_0,a_1)$ and $m_1=(a_1,a_0)$.