# Number of preimages of hash function from bounded domain

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.
• So we can expect $b$ to have $2^k$ preimages on avarage? Dec 21 '18 at 2:34
• 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. Dec 21 '18 at 2:51