1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\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 acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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