2
$\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 Answer 1

2
$\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$
2
  • $\begingroup$ So we can expect $b$ to have $2^k$ preimages on avarage? $\endgroup$ Dec 21, 2018 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, 2018 at 2:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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