1
$\begingroup$

Let $H(k,m)$ an universal hash function that is difference-unpredictable.

Let $\mathcal{A}$ be an attacker who sends tuples $(m_0, m_1, \delta)$, and $\mathcal{A}$ wins the game if one of the tuples satisfy $H(k,m_1) -H(k,m_0) = \delta$.

$H$ will be difference-unpredictable when the chance of $\mathcal{A}$ win is negligible.

Suppose $H$ is difference-unpredictable, how can I show that the function $H'((k,x),m) = H(k,m) + x$ will also be?

Both functions' image is all naturals smaller than a given prime $p$, one can think of the functions like $H(k,m) = (...)\bmod p$.


I think the proof remains on this argument:

  • the attacker chooses $(m_0, m_1, \delta)$

  • let $H(k, m_0) = h_0$ and $H(k, m_1) = h_1$

  • let $d$ be the "wrapping" distance from $h_0$ to $h_1$, that is:

    • $d = h_1 - h_0\;$ if $\;h_0 \leq h_1$

    • $d = p - h_0 + h_1\;$ if $\;h_0 > h_1$

If $H'$ only offsets $h_0$ and $h_1$ by $x$, the "wrapping" distance will be the same and it will give no better chance for the attacker to guess a difference change in the results and his chance will remain negligible.

$\endgroup$
0

1 Answer 1

0
$\begingroup$

What's $H'((k, x), m_0) - H'((k, x), m_1)$?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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