1
$\begingroup$

Given a cryptographic hashing function, with say a $256$ bit-length, I want to calculate the probability that out of $n$ hashes we have at least $k$ hashes that collide in the first $32$-bit (assuming the $n$ hashes are uniformly distributed over all $2^{32}$ possible prefixes). Assume $k$ and $n$ are very high, something like $k=2^{32},n=2^{64}$. This reminds me of the birthday paradox but for more than $2$ people. I found this post, which suggest using an poisson approximation which from my understanding would result in the formula:

$$ P(\text{at least $k$ hashes in $n$ trials share the same prefix}) =$$ $$ 1 - \exp \left (-{n \choose k}/(2^{32})^{(k-1)} \right )$$

because if we would check every combination of $k$ hashes in the set $n$ hashes, we would on average have $\lambda = {n \choose k}/(2^{32})^{(k-1)}$ combinations that share the same $32$ bit prefix.

The problem with that that formula is that the calculations take too long. For example, calculating the number $(2^{32})^{2^{32}-1}$ is simply too complex. Is there any other way I can approximate this probability while remaining in the computationally feasible area?

$\endgroup$
  • $\begingroup$ Why do you think that it is complex? $\endgroup$ – kelalaka Apr 20 at 18:37
  • $\begingroup$ @fgrieu do you mean $x^y=e^{y \ln x}$ $\endgroup$ – kelalaka Apr 20 at 19:41
  • $\begingroup$ @kelalaka: yes. $\endgroup$ – fgrieu Apr 20 at 19:59
  • $\begingroup$ @kelalaka I tried this NumberFormat[(2^32)^(2^32-1)] and this 1- e^(-Binomial[2**64,2**32]/((2^32)^(2^32-1))) in mathematica and it apparently exceeds the memory limit for my "basic plan". Python with the decimal package also takes too long for the calculations. Any software/bignum library you would recommend using for this? $\endgroup$ – securitymensch Apr 20 at 20:53
  • $\begingroup$ @fgrieu Could you elaborate? How can I use that to simplify the formula? $\endgroup$ – securitymensch Apr 20 at 20:54
1
$\begingroup$

For large $k$ growing with $n$ the binomial coefficient needs to be approximated.

Let $h(x)=-x\ln x-(1-x)\ln (1-x)$ be the binary entropy function in nats, then for $k\in [1,n-1]\cap \mathbb{Z}$ we have $$ \sqrt{\frac{n}{8k(n-k)}}\exp\{nh(k/n)\} \leq \binom{n}{k} \leq \sqrt{\frac{n}{2\pi k(n-k)}}\exp\{nh(k/n)\} $$ where the upper bound approaches equality if $k$ and $n-k$ are both large. This is obtained from Stirling and then some other manipulation, and covers the whole range of $k$.

This result appears, e.g., in Bob Gallager's book Information Theory and Reliable Communications.

This will give a good approximation if you use the upper bound.

So, you have $$ 1-\exp\left[-\frac{\sqrt{\frac{n}{2\pi k(n-k)}}\exp\{nh(k/n)\}}{\exp\{(k-1)\ln 2^{32}\}}\right] $$ and can further take differences of the exponential function arguments inside and simplify for $n=2^{64},k=2^{32},$ to $$ 1-\exp\left[-\sqrt{\frac{n}{2\pi k(n-k)}}\exp\left(nh(k/n)-(k-1)\ln 2^{32}\right)\right]\approx$$ $$\approx 1-\exp\left[-\sqrt{\frac{k}{2\pi}} \exp\left(nh(1/k)-(k-1)\ln 2^{32}\right)\right] $$ or $$\approx 1-\exp\left[-\sqrt{\frac{k}{2\pi}} \exp\left(nh(2^{-32})-2^{32}\ln 2^{32}\right)\right] $$ and since for large $k$, $h(1/k)\approx \ln k,$ $$\approx 1-\exp\left[-\sqrt{\frac{k}{2\pi}} \exp\left(n \ln 2^{32})-2^{32}\ln 2^{32}\right)\right] $$ $$ \approx 1-\exp\left[-\sqrt{\frac{k}{2\pi}} \exp\left((2^{64}-2^{32}) \ln 2^{32}\right)\right]\approx $$ $$ \approx 1-\exp\left[-\sqrt{\frac{k}{2\pi}} \exp\left(2^{64} \times 32 \ln 2 \right)\right] $$

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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