Suppose we have an "ideal" cryptographic hash function

$H: \{0,1\}^{n+k}\to \{0,1\}^{n}$

and a given bitstring $b\in \{0,1\}^{n}$, Can we estimate how many preimages $H^{-1}(b)$ there are?

With ideal I mean that it behaves like a random oracle.


I assume you mean behaves like a uniformly chosen function from the set of functions mapping $\{0,1\}^{n+k}$ to $\{0,1\}^n.$

Let $p_z$ be the probability that the random variable $Z=|H^{-1}(b)|=z,$ for $0\leq z\leq 2^{n+k}.$ Then $$p_0=(1-2^{-n})^{2^{n+k}}\approx \exp[-2^k]$$ which is the probability that a fixed $b$ is missed $2^{n+k}$ times. Of course $\mathbb{P}(|H^{-1}(b)|=z)$ is independent of $z$ and distributed binomially, i.e., $$\mathbb{P}(|H^{-1}(b)|=z)=\binom{2^{n+k}}{z}(1-2^{-n})^{2^{n+k}-z} (2^{-n})^{z}$$

With high probability, the distribution $p_z$ is concentrated around its expectation $Z=2^{k},$ for example via the Chernoff bound.

| improve this answer | |
  • $\begingroup$ So we can expect $b$ to have $2^k$ preimages on avarage? $\endgroup$ – Mark Neuhaus Dec 21 '18 at 2:34
  • 1
    $\begingroup$ Yes, that's correct, by a simple division, $2^{n+k}$ balls into $2^{n}$ bins means that there is on average $2^k$ in each bin. $\endgroup$ – kodlu Dec 21 '18 at 2:51

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.