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.
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
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.
-
$\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$– kodluDec 21, 2018 at 2:51