<p>I think a pragmatic approach would be to use a <a href="https://en.wikipedia.org/wiki/Pseudorandom_function_family" rel="nofollow noreferrer">PRF</a> (see also <a href="https://blog.cryptographyengineering.com/2023/05/08/prfs-prps-and-other-fantastic-things/" rel="nofollow noreferrer">here</a>) instead of a polynomial hash, because then you can say that the collision probability is <span class="math-container">$1/M$</span> (unless someone figures out how to break the crypto).  Or, alternatively, to use a 128-bit hash rather than a 64-bit hash; maybe <a href="https://en.wikipedia.org/wiki/Poly1305" rel="nofollow noreferrer">Poly1305</a>.</p>
<p>I wouldn't set your hopes too high on proving a better bound.  My intuition is that the collision probability is probably more like <span class="math-container">$(n-1)/M$</span>, not <span class="math-container">$1/M$</span>, as a random polynomial of degree <span class="math-container">$n-1$</span> has on average about <span class="math-container">$n-1$</span> unique roots modulo <span class="math-container">$M$</span>.  Note that the hashes can still be uniformly distributed across the codomain: it is the difference between the probability distribution with respect to a random choice of <span class="math-container">$B$</span>, vs the probability distribution with respect to a random choice of input string.</p>

CC BY-SA 4.0
2023-06-28T19:42:24.013Z
2023-06-28T19:42:24.013Z
D.W.
<p><span class="math-container">$\newcommand{\bigparen}[1]{\Bigl ( #1 \Bigr )}$</span></p>
<p>I'm working with polynomial hashes <span class="math-container">$H$</span> defined by the pair <span class="math-container">$(B, M)$</span> (base, modulo):</p>
<p><span class="math-container">$$H_{B, M}(s) \equiv \sum_{i=0}^{n-1} B^{n-1-i} \cdot conv(s_i) \, (mod \, M)$$</span></p>
<p>The conversion function is <code>conv(c) = c - 'a' + 1</code> (work only with lowercase letters). I work with strings of different lengths.</p>
<p>The scheme I use to guarantee a small enough collision probability takes a fixed modulo (in this case the largest Mersenne prime that fits in <span class="math-container">$8$</span> bytes, <span class="math-container">$2^{61} - 1$</span>), and chooses one uniformly random base from the set <span class="math-container">$\{26 + 1, ..., 2 ^ {61} - 2\}$</span>.</p>
<p>The probability for any two different strings <span class="math-container">$s$</span>, <span class="math-container">$t$</span>:</p>
<p><span class="math-container">$$P\bigparen{H(s) \equiv H(t) \, (mod \, M)} = P\bigparen{\sum_{i=0}^{n-1} B^{n-1-i} \cdot (conv(s_i) - conv(t_i)) \equiv 0 \, (mod \, M)} \leq \frac{n-1}{M}$$</span></p>
<p>Since the left side is a <span class="math-container">$n-1$</span>-degree polynomial in a randomly chosen variable, the base <span class="math-container">$B$</span> (Schwartz–Zippel lemma).</p>
<p>At one point in my algorithm I'm sorting <span class="math-container">$n \log_2 n$</span> hashes, so an upper bound for the probability of collision would be:</p>
<p><span class="math-container">$$1 - \bigparen{1 - \frac{n - 1}{M}} ^ {\lceil n \log_2 n \rceil \choose 2}$$</span></p>
<p>That is too high (for <span class="math-container">$n = 10^5$</span> it's <span class="math-container">$22\%$</span>). In order to get a good bound with this scheme, I need to randomly pick two distinct bases. I'd rather not do this because of the noticeable slowdown in memory access times.</p>
<p>However, in practice, I would expect the probability that two hashes would collide to be much closer to <span class="math-container">$\frac{1}{M}$</span> (uniform spread over the codomain) than <span class="math-container">$\frac{n-1}{M}$</span>.</p>
<p>Supposing that I can pick <span class="math-container">$B$</span> such that <span class="math-container">$B^i \not\equiv B^j \, (mod \, M) \,\, \forall \,\, 0 \leq i \lt j \lt n$</span>, could there be a better upper bound out there for the probability of the hashes (<span class="math-container">$H_{B, M}, B$</span> chosen randomly, <span class="math-container">$M$</span> fixed and prime) of any two strings colliding than <span class="math-container">$\frac{n-1}{M}$</span>? Maybe some other initial conditions could help.</p>
<p>Thank you.</p>

<polynomials><hash-function>
Lower bound for the Schwartz–Zippel lemma in Polynomial Hashing
catalyst
# Lower bound for the Schwartz–Zippel lemma in Polynomial Hashing

(Asked by: username_0 on 2023-06-28)

$\newcommand{\bigparen}[1]{\Bigl ( #1 \Bigr )}$

I'm working with polynomial hashes $H$ defined by the pair $(B, M)$ (base, modulo):

$$H\_{B, M}(s) \equiv \sum\_{i=0}^{n-1} B^{n-1-i} \cdot conv(s\_i) \, (mod \, M)$$

The conversion function is `conv(c) = c - 'a' + 1` (work only with lowercase letters). I work with strings of different lengths.

The scheme I use to guarantee a small enough collision probability takes a fixed modulo (in this case the largest Mersenne prime that fits in $8$ bytes, $2^{61} - 1$), and chooses one uniformly random base from the set $\{26 + 1, ..., 2 ^ {61} - 2\}$.

The probability for any two different strings $s$, $t$:

$$P\bigparen{H(s) \equiv H(t) \, (mod \, M)} = P\bigparen{\sum\_{i=0}^{n-1} B^{n-1-i} \cdot (conv(s\_i) - conv(t\_i)) \equiv 0 \, (mod \, M)} \leq \frac{n-1}{M}$$

Since the left side is a $n-1$-degree polynomial in a randomly chosen variable, the base $B$ (Schwartz–Zippel lemma).

At one point in my algorithm I'm sorting $n \log\_2 n$ hashes, so an upper bound for the probability of collision would be:

$$1 - \bigparen{1 - \frac{n - 1}{M}} ^ {\lceil n \log\_2 n \rceil \choose 2}$$

That is too high (for $n = 10^5$ it's $22\%$). In order to get a good bound with this scheme, I need to randomly pick two distinct bases. I'd rather not do this because of the noticeable slowdown in memory access times.

However, in practice, I would expect the probability that two hashes would collide to be much closer to $\frac{1}{M}$ (uniform spread over the codomain) than $\frac{n-1}{M}$.

Supposing that I can pick $B$ such that $B^i \not\equiv B^j \, (mod \, M) \,\, \forall \,\, 0 \leq i \lt j \lt n$, could there be a better upper bound out there for the probability of the hashes ($H\_{B, M}, B$ chosen randomly, $M$ fixed and prime) of any two strings colliding than $\frac{n-1}{M}$? Maybe some other initial conditions could help.

Thank you.

**Tags:** polynomials, hash-function


---

## 1 answers

### Answer by username_1 on 2023-06-28. Score: 3 | Accepted answer

I think a pragmatic approach would be to use a [PRF](https://en.wikipedia.org/wiki/Pseudorandom_function_family) (see also [here](https://blog.cryptographyengineering.com/2023/05/08/prfs-prps-and-other-fantastic-things/)) instead of a polynomial hash, because then you can say that the collision probability is $1/M$ (unless someone figures out how to break the crypto). Or, alternatively, to use a 128-bit hash rather than a 64-bit hash; maybe [Poly1305](https://en.wikipedia.org/wiki/Poly1305).

I wouldn't set your hopes too high on proving a better bound. My intuition is that the collision probability is probably more like $(n-1)/M$, not $1/M$, as a random polynomial of degree $n-1$ has on average about $n-1$ unique roots modulo $M$. Note that the hashes can still be uniformly distributed across the codomain: it is the difference between the probability distribution with respect to a random choice of $B$, vs the probability distribution with respect to a random choice of input string.


---

