<p>I believe the proof survives if you remove the suspect phrase. The reason is that the phrase is asserting the independence of <span class="math-container">$\delta’$</span> when the definition of <span class="math-container">$\epsilon$</span>-ADU for <span class="math-container">$g$</span> doesn’t require it: the definition applies to <em>arbitrary</em> <span class="math-container">$\delta’$</span>.</p>

CC BY-SA 4.0
2023-07-22T09:43:26.270Z
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}$.
orlp
CC BY-SA 4.0
2023-07-22T11:26:49.090Z
I resolved my concerns in the other answer I posted.
orlp
CC BY-SA 4.0
2023-07-22T02:54:28.823Z
2023-07-22T02:54:28.823Z
jbapple
<p>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 <span class="math-container">$m, m'$</span> and any <span class="math-container">$\delta$</span> we have</p>
<p><span class="math-container">$$\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$$</span></p>
<p>We when <span class="math-container">$|m| \neq |m'|$</span> the above gets bounded as</p>
<p><span class="math-container">$$\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')] =$$</span>
<span class="math-container">$$\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$$</span></p>
<p>where <span class="math-container">$p(\ell, \ell', \delta') = \frac{1}{|\mathcal{G}|}\sum_{g \in\mathcal{G}} [g(\ell) \ominus g(\ell') = \delta'] \leq \epsilon$</span> now clearly holds as <span class="math-container">$\mathcal{G}$</span> is <span class="math-container">$\epsilon$</span>-ADU.</p>
<p>In essence, we are (by the ability to freely interchange sums) free to <em>first</em> pick <span class="math-container">$h \in \mathcal{H}$</span>, after which <span class="math-container">$\delta' = \delta \ominus h(m) \oplus h(m')$</span> is effectively constant and the <span class="math-container">$\epsilon$</span>-ADU bound of <span class="math-container">$g$</span> is valid, despite the event delta containing terms depending on <span class="math-container">$m$</span>. I expect the original authors meant this with &quot;a value independent of&quot;, but it was not clear to me.</p>

CC BY-SA 4.0
2023-07-22T11:22:11.563Z
2023-07-22T11:37:20.873Z
2023-07-22T11:37:20.873Z
orlp
<p>For context, an <span class="math-container">$\epsilon$</span>-almost delta universal (<span class="math-container">$\epsilon$</span>-ADU) hash function family <span class="math-container">$\mathcal{H} = \{h : M \to D\}$</span> hashes inputs from <span class="math-container">$M$</span> to digests in <span class="math-container">$D$</span> such that
for any distinct <span class="math-container">$m, m' \in M$</span> and any <span class="math-container">$\delta \in D$</span> we have
<span class="math-container">$$\Pr[h(m) \ominus h(m') = \delta] \leq \epsilon$$</span>
where <span class="math-container">$\ominus$</span> is subtraction over some group structure in <span class="math-container">$D$</span>, and <span class="math-container">$h$</span> is sampled uniformly at random from <span class="math-container">$\mathcal{H}$</span>. When the group structure is XOR over bitstrings this is sometimes refered to as <span class="math-container">$\epsilon$</span>-AXU.</p>
<p>In <a href="https://arxiv.org/abs/1503.03465" rel="nofollow noreferrer"><em>Faster 64-bit universal hashing using carry-less multiplications</em></a> by Daniel Lemire and Owen Kaser we find Lemma 3 (paraphrased, slightly generalized and formalized):</p>
<blockquote>
<p>If <span class="math-container">$\mathcal{H} = \{h : \Sigma^* \to D\} $</span> is <span class="math-container">$\epsilon$</span>-ADU when restricted to strings of a single length <span class="math-container">$\ell$</span> at a time, for any <span class="math-container">$\ell \in L$</span>, and <span class="math-container">$\mathcal{G} = \{g : L \to D\}$</span> is <span class="math-container">$\epsilon$</span>-ADU over the same group <span class="math-container">$D$</span> as <span class="math-container">$\mathcal{H}$</span>, then family <span class="math-container">$\mathcal{F} = \{f(m) = h(m) \oplus g(|m|)\mid h\in\mathcal{H},g\in\mathcal{G}\}$</span> is <span class="math-container">$\epsilon$</span>-ADU over all strings <span class="math-container">$\bigcup_{\ell\in L}\Sigma^\ell$</span>.</p>
</blockquote>
<p>That is, in plain english, if <span class="math-container">$h$</span> and <span class="math-container">$g$</span> are <span class="math-container">$\epsilon$</span>-ADU hash function families then  <span class="math-container">$h(m) \oplus g(|m|)$</span> is <span class="math-container">$\epsilon$</span>-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):</p>
<blockquote>
<p>If <span class="math-container">$|m| = |m'|$</span> we find that
<span class="math-container">$$\Pr[f(m) \ominus f(m') = \delta] = \Pr[h(m) \ominus h(m') = \delta]\leq \epsilon$$</span>
as <span class="math-container">$\mathcal{H}$</span> is <span class="math-container">$\epsilon$</span>-ADU for same-length strings. If <span class="math-container">$|m| \neq |m'|$</span> we find that because <span class="math-container">$\mathcal{G}$</span> is <span class="math-container">$\epsilon$</span>-ADU that
<span class="math-container">$$\Pr[f(m) \ominus f(m') = \delta] = \Pr[g(|m|) \ominus g(|m'|) = \delta'] \leq \epsilon$$</span>
where we set <span class="math-container">$\delta' = \delta \ominus h(m) \oplus h(m')$</span>, <span class="math-container">$\color{red}{\textrm{a value independent from }|m|\textrm{ and }|m'|}$</span>.</p>
</blockquote>
<p>Now, let's study the hash family <span class="math-container">$\mathcal{H} = \{h_a : \{0, 1\}^* \to \mathbb{F}_p \mid 0 \leq a &lt; p\}$</span> where <span class="math-container">$h(m) = (a\cdot \mathrm{int(m)} + |m|) \bmod p$</span>, <span class="math-container">$\mathrm{int}$</span> interprets the binary string as an unsigned integer and <span class="math-container">$p$</span> is prime, say, <span class="math-container">$2^{61} - 1$</span>. For any fixed length <span class="math-container">$\ell &lt; 61$</span> we find that <span class="math-container">$\mathcal{H}$</span> is <span class="math-container">$\epsilon$</span>-ADU. However, for input string <span class="math-container">$0^k$</span> we find that the output is <span class="math-container">$k$</span>. Thus disproving that in general <span class="math-container">$h(m)$</span> is independent from <span class="math-container">$|m|$</span> for any <span class="math-container">$m$</span> even if <span class="math-container">$h$</span> is <span class="math-container">$\epsilon$</span>-ADU.</p>
<p>Can the proof be fixed? Or am I misunderstanding what's being meant with independence? Or is the lemma simply not true?</p>

<proofs><hash-function><independence>
Combining different length epsilon-ADU hash function families
orlp
# Combining different length epsilon-ADU hash function families

(Asked by: username_0 on 2023-07-22)

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*](https://arxiv.org/abs/1503.03465) 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?

**Tags:** proofs, hash-function, independence

---

## 2 answers

### Answer by username_1 on 2023-07-22. Score: 0

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

> **Comments:**
> **username_0**: 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}$.  
> **username_0**: I resolved my concerns in the other answer I posted.  

---

### Answer by username_0 on 2023-07-22. Score: 0

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.


---

