0
$\begingroup$

For context, an $\epsilon$-almost delta universal ($\epsilon$-ADU) hash function family $\mathcal{H} = \{h : M \to D\}$ hashes inputs from $M$ to digests in $D$ such that for any distinct $m, m' \in M$ and any $\delta \in D$ we have $$\Pr[h(m) \ominus h(m') = \delta] \leq \epsilon$$ where $\ominus$ is subtraction over some group structure in $D$, and $h$ is sampled uniformly at random from $\mathcal{H}$. When the group structure is XOR over bitstrings this is sometimes refered to as $\epsilon$-AXU.

In Faster 64-bit universal hashing using carry-less multiplications by Daniel Lemire and Owen Kaser we find Lemma 3 (paraphrased, slightly generalized and formalized):

If $\mathcal{H} = \{h : \Sigma^* \to D\} $ is $\epsilon$-ADU when restricted to strings of a single length $\ell$ at a time, for any $\ell \in L$, and $\mathcal{G} = \{g : L \to D\}$ is $\epsilon$-ADU over the same group $D$ as $\mathcal{H}$, then family $\mathcal{F} = \{f(m) = h(m) \oplus g(|m|)\mid h\in\mathcal{H},g\in\mathcal{G}\}$ is $\epsilon$-ADU over all strings $\bigcup_{\ell\in L}\Sigma^\ell$.

That is, in plain english, if $h$ and $g$ are $\epsilon$-ADU hash function families then $h(m) \oplus g(|m|)$ is $\epsilon$-ADU without having to worry about different-length strings colliding. My problem is that the provided proof makes a claim that I believe is false, and I don't know if this means the lemma is false or if the proof can be fixed. The proof (paraphrased, dubious claim highlighted):

If $|m| = |m'|$ we find that $$\Pr[f(m) \ominus f(m') = \delta] = \Pr[h(m) \ominus h(m') = \delta]\leq \epsilon$$ as $\mathcal{H}$ is $\epsilon$-ADU for same-length strings. If $|m| \neq |m'|$ we find that because $\mathcal{G}$ is $\epsilon$-ADU that $$\Pr[f(m) \ominus f(m') = \delta] = \Pr[g(|m|) \ominus g(|m'|) = \delta'] \leq \epsilon$$ where we set $\delta' = \delta \ominus h(m) \oplus h(m')$, $\color{red}{\textrm{a value independent from }|m|\textrm{ and }|m'|}$.

Now, let's study the hash family $\mathcal{H} = \{h_a : \{0, 1\}^* \to \mathbb{F}_p \mid 0 \leq a < p\}$ where $h(m) = (a\cdot \mathrm{int(m)} + |m|) \bmod p$, $\mathrm{int}$ interprets the binary string as an unsigned integer and $p$ is prime, say, $2^{61} - 1$. For any fixed length $\ell < 61$ we find that $\mathcal{H}$ is $\epsilon$-ADU. However, for input string $0^k$ we find that the output is $k$. Thus disproving that in general $h(m)$ is independent from $|m|$ for any $m$ even if $h$ is $\epsilon$-ADU.

Can the proof be fixed? Or am I misunderstanding what's being meant with independence? Or is the lemma simply not true?

$\endgroup$

2 Answers 2

0
$\begingroup$

I believe the proof survives if you remove the suspect phrase. The reason is that the phrase is asserting the independence of $\delta’$ when the definition of $\epsilon$-ADU for $g$ doesn’t require it: the definition applies to arbitrary $\delta’$.

$\endgroup$
2
  • $\begingroup$ I think we still need to be a bit careful. I was a bit sloppy here and $\Pr$ should really be $\Pr_{f\in\mathcal{F}}$. And the arbitrary $\delta$ must still be independent from the choice of $f \in \mathcal{F}$ otherwise you might choose $\delta = f(m) \ominus f(m')$ and disprove any $\epsilon$ bound as you'd end up with probability 1. So $$\Pr_{f\in\mathcal{F}}[f(m) \ominus f(m') = \delta] = \Pr_{f\in\mathcal{F}}[g(|m|) \ominus g(|m'|) = \delta'] \leq \epsilon$$ is still problematic I believe, since $\delta' = \delta\ominus h(m)\oplus h(m')$ still depends on $f \in \mathcal{F}$. $\endgroup$
    – orlp
    Jul 22, 2023 at 9:43
  • $\begingroup$ I resolved my concerns in the other answer I posted. $\endgroup$
    – orlp
    Jul 22, 2023 at 11:26
0
$\begingroup$

We can elucidate the independence referenced to in the proof formally if we explicitly write out the event probability using the Iverson bracket. Then what we're trying to prove is that for any distinct $m, m'$ and any $\delta$ we have

$$\Pr_\mathcal{f \in F}[f(m) \ominus f(m') = \delta] = \frac{1}{|\mathcal{H}|\cdot|\mathcal{G}|}\sum_{h\in\mathcal{H}}\sum_{g\in\mathcal{G}} [f(m) \ominus f(m') = \delta] \leq \epsilon$$

We when $|m| \neq |m'|$ the above gets bounded as

$$\frac{1}{|\mathcal{H}|\cdot|\mathcal{G}|}\sum_{h\in\mathcal{H}}\sum_{g\in\mathcal{G}} [g(|m|) \ominus g(|m'|) = \delta \ominus h(m) \oplus h(m')] =$$ $$\frac{1}{|\mathcal{H}|}\sum_{h\in\mathcal{H}}p(|m|, |m'|, \delta \ominus h(m) \oplus h(m')) \leq \frac{1}{|\mathcal{H}|}\sum_{h\in\mathcal{H}}\epsilon\leq \epsilon$$

where $p(\ell, \ell', \delta') = \frac{1}{|\mathcal{G}|}\sum_{g \in\mathcal{G}} [g(\ell) \ominus g(\ell') = \delta'] \leq \epsilon$ now clearly holds as $\mathcal{G}$ is $\epsilon$-ADU.

In essence, we are (by the ability to freely interchange sums) free to first pick $h \in \mathcal{H}$, after which $\delta' = \delta \ominus h(m) \oplus h(m')$ is effectively constant and the $\epsilon$-ADU bound of $g$ is valid, despite the event delta containing terms depending on $m$. I expect the original authors meant this with "a value independent of", but it was not clear to me.

$\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.