2
$\begingroup$

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

$\endgroup$
0

1 Answer 1

3
$\begingroup$

I think a pragmatic approach would be to use a PRF (see also here) 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.

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.

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