Maximum entropy of a hash function?

Question

Let $H(h,k)$ be the expected entropy of some random oracle $X:\left\{0,1\right\}^h \to \left\{0,1\right\}^k$, where $h$ does not necessarily equal $k$.

1. Then, is it true that $\lim\limits_{h\to\infty}H(h,k) = k$ ? (for constant $k$)
2. If so, is the above still true if $h = 2k$? In other words, does $\lim\limits_{h\to\infty} h - H(2h,h) = 0$ ? (for common hash functions like SHA-256/512, the input block size is twice the bits of the output)

For #1, my hunch is that it is true simply by the Law of Large Numbers, where $X$ is more likely to become uniformly distributed in $\left\{0,1\right\}^k$ as $h\to\infty$.

For #2, I am not so sure. A uniform distribution in $\left\{0,1\right\}^k$ has variance $\sigma^2 \sim 2^{2k} = 2^h$, which may "cancel out" this effect of the Law of Large Numbers as $h\to\infty$.

---

*Edit -- to calculate the expected entropy, I followed fgrieu's approach from The effect of truncated hash on entropy, where fgrieu derived the expected entropy of a random $h=k$ oracle as $$H = h - \frac{1}{2^h}\sum_{j=1}^{2^h}n_jj\lg\left(j\right) \approx h - 0.8272453$$

However, for a more "general" random oracle (where possibly $h\ne k$), I obtained $$n_j = 2^k\binom{2^h}{j}\left(\frac{1}{2^k}\right)^j\left(1-\frac{1}{2^k}\right)^{2^h-j}$$ and so $$H = h - 2^{k-h}\sum_{j=1}^{2^h}\binom{2^h}{j}\left(\frac{1}{2^k}\right)^j\left(1-\frac{1}{2^k}\right)^{2^h-j}j\lg\left(j\right)$$ which does not seem to have a nice simple closed-form or approximation like in the $h = k$ case there.

---

*Edit #2 -- it seems Wolfram-Alpha also miscalculates the limits here. For example, in the simple case of a 1-bit random oracle $X:\{1,2,\ldots,n\}\to\{1,2\}$, the expected entropy would just be $$ H_n = -\frac{1}{2^n}\sum_{j=1}^{n-1}\binom{n}{j}\left[\left(\frac{j}{n}\right)\lg\left(\frac{j}{n}\right) + \left(1-\frac{j}{n}\right)\lg\left(1-\frac{j}{n}\right)\right]$$ (ignoring the two zero-entropy cases $j=0,n$, where $X$ either maps everything to $0$ or everything to $1$).

But, Wolfram-Alpha seems to suggest that $\lim\limits_{n\to\infty} H_n = 0$ (and even hangs when substituting $h=n$), when in fact actually $\lim\limits_{n\to\infty} H_n = 1$. This can be demonstrated by showing that $H_n$ is already bounded from below by a (much simpler) sum $$B_n = \frac{1}{2^n}\sum_{j=1}^{n-1}\binom{n}{j}\left[4\times\frac{j}{n}\left(1-\frac{j}{n}\right)\right] = 1 - \frac{1}{n}$$ such that $0 < B_n < H_n < 1$ for all $n > 1$, thus implying that $\lim\limits_{n\to\infty}H_n = 1$.

Answer 1

Notations and preliminaries

The random oracle implements a random function $X:\{0,1\}^h\to\{0,1\}^k$. For a given such $X$

• Let $j_i$ be the number of preimages in $\{0,1\}^h$ of a given element $i$ in $\{0,1\}^k$.

  It holds $0\le j_i\le 2^h\,$ and $$\sum_{i\in\{0,1\}^k}j_i\ =\ 2^h\label{fgrieu1}\tag{1}$$

  The entropy at the output of $X$ for uniformly random input is $$\begin{align}H&=\sum_{i\in\{0,1\}^k}\frac{j_i}{2^h}\log_2\left(\frac{2^h}{j_i}\right)\label{fgrieu2}\tag{2}\\ &=2^{-h}\sum_{i\in\{0,1\}^k}j_i\,\bigl(h-\log_2(j_i)\bigr)\label{fgrieu3}\tag{3}\\ \end{align}$$

• Let $n_j$ be the number of $i$ with $j_i=j$.

  It holds $$\displaystyle\sum_{j=0}^{2^h}n_j\ =\ 2^k\label{fgrieu4}\tag{4}$$ and by rearanging the terms in $\ref{fgrieu3}$ it comes $$H=2^{-h}\sum_{j=1}^{2^h}n_j\,j\,\bigl(h-\log_2(j)\bigr)\label{fgrieu5}\tag{5}$$

The distribution of $j_i$ over the $2^{2^h k}$ different $X$ is binomial, with mean $E(j_i)=\mu=2^{h-k}$ and standard deviation $\sigma=\sqrt{2^{h-k}(1-2^{-k})}$

The question is about the expected $H(h,k)=E(H)$ over the $2^{2^h k}$ different $X$. Expectation is linear, thus even though the $n_j$ are dependent, equations $\ref{fgrieu4}$ and $\ref{fgrieu5}$ rigorously yield $$\displaystyle\sum_{j=0}^{2^h}E(n_j)\ =\ 2^k\label{fgrieu6}\tag{6}$$ $$H(h,k)=2^{-h}\sum_{j=1}^{2^h}E(n_j)\,j\,\bigl(h-\log_2(j)\bigr)\label{fgrieu7}\tag{7}$$

This can lead to at least asymptotic formulas for $H(h,k)$. I used this approach there to derive $\lim\limits_{h\to\infty}h-H(h,h)=0.82724538915300508343173\ldots^+$ bit.

Answer

1. Yes, for fixed $k$, $\lim\limits_{h\to\infty}H(h,k)=k$.

   Intuitive argument: as $h$ goes to infinity, the binomial distribution of the $j_i$ degenerates to Gaussian with same mean $\mu$ and standard deviation $\sigma$ as above. $\lim\limits_{h\to\infty}\sigma/\mu=0$. This implies that in $\ref{fgrieu7}$, the terms of the sum that matter are those with $j$ close to $\mu=2^{h-k}$. Replacing $j$ with $2^{h-k}$ in $\ref{fgrieu7}$, then applying $\ref{fgrieu6}$, we get $$\begin{align}\lim\limits_{h\to\infty}H(h,k)&=2^{-h}\sum_{j=1}^{2^h}E(n_j)\,2^{h-k}\,\bigl(h-(h-k)\bigr)\\ &=2^{-k}\,k\sum_{j=1}^{2^h}E(n_j)\\ &=k\\ \end{align}$$ ^{I wish I knew how to properly justify "This implies".}

2. Thinking about rigorously proving $\lim\limits_{h\to\infty}h-H(2h,h)=0^+$.

   ^{But don't hold your breath.}

Answer 2

fgrieu has shown that $\lim\limits_{h\to\infty} H(h,k) = k$ for any fixed $k$, so I will try to address the second question, that is, whether or not $$\lim\limits_{h\to\infty} h - H(2h,h) = 0$$ In particular, if we let $n = 2^h$, then we are asking whether $$\lim\limits_{n\to\infty} \lg(n) - n\sum_{j=0}^{n^2}\binom{n^2}{j}\left(\frac{1}{n}\right)^j\left(1-\frac{1}{n}\right)^{n^2-j}\left[\left(\frac{j}{n^2}\right)\lg\left(\frac{n^2}{j}\right)\right] = 0$$ or equivalently, whether $$\lim\limits_{n\to\infty} \sum_{j=0}^{n^2}\binom{n^2}{j}\left(\frac{1}{n}\right)^j\left(1-\frac{1}{n}\right)^{n^2-j}\left[\lg(n)+\left(\frac{j}{n}\right)\lg\left(\frac{j}{n^2}\right)\right] = 0$$ Note that as $n\to\infty$, the quantity inside the sum $$\binom{n^2}{j}\left(\frac{1}{n}\right)^j\left(1-\frac{1}{n}\right)^{n^2-j} \approx \mathcal{N}(j \,\vert\, n,n-1)$$ where $\mathcal{N}(x \,\vert\, \mu,\sigma^2)$ is the PDF of the normal distribution with mean $\mu$ and variance $\sigma^2$.

Which we can simply plug into Wolfram Alpha to obtain: $$\lim\limits_{n\to\infty} \sum_{j=0}^{n^2}\mathcal{N}(j \,\vert\, n,n-1)\times\left[\lg(n)+\left(\frac{j}{n}\right)\lg\left(\frac{j}{n^2}\right)\right] = 0$$

---

**Edit -- using "Wolfram Alpha" to obtain an answer is not a very rigorous approach (as @kodlu has also pointed out in the comments as well). So, I'll attempt a more rigorous solution here below...

In particular, where $n = 2^h$ just as above, we can express $$ H(2h, h) = \sum_{j=0}^{n^2}\binom{n^2}{j}\left(\frac{1}{n}\right)^j\left(1-\frac{1}{n}\right)^{n^2-j}\left[\left(\frac{j}{n}\right)\lg\left(\frac{n^2}{j}\right)\right] $$ and observe that this quantity from inside the sum $$\left[\left(\frac{j}{n}\right)\lg\left(\frac{n^2}{j}\right)\right]$$ is bounded from below by the slightly different quantity $$\frac{1}{\ln 2}\times\left[-2\left(\frac{j}{n}\right)^2 + \left(3+\ln n\right)\left(\frac{j}{n}\right) - 1\right]$$ such that $$ H(2h,h) \ge \sum_{j=0}^{n^2}\binom{n^2}{j}\left(\frac{1}{n}\right)^j\left(1-\frac{1}{n}\right)^{n^2-j}\times\frac{1}{\ln 2}\left[-2\left(\frac{j}{n}\right)^2 + \left(3+\ln n\right)\left(\frac{j}{n}\right) - 1\right] \\ = \lg(n) - 2\left(\frac{n - 1}{n^2\ln 2}\right) = h - 2\left(\frac{2^h - 1}{4^h\ln 2}\right)$$ and so $$\lim\limits_{h\to\infty} h - H(2h,h) \le \lim\limits_{h\to\infty} 2\left(\frac{2^h - 1}{4^h\ln 2}\right) = \boxed{0}$$

---

**Edit #2 -- it seems the same "lower-bound" approach can also be used to answer the first question (demonstrate that $\lim\limits_{h\to\infty} H(h,k) = k$ for any fixed $k$) as well!

In particular, where $n = 2^h$ just as above, and $m = 2^k$, we can express $$H(h,k) = m\sum_{j=0}^{n}\binom{n}{j}\left(\frac{1}{m}\right)^j\left(1-\frac{1}{m}\right)^{n-j}\left[\left(\frac{j}{n}\right)\lg\left(\frac{n}{j}\right)\right]$$ and observe that this quantity from inside the sum $$\left[\left(\frac{j}{n}\right)\lg\left(\frac{n}{j}\right)\right]$$ is bounded from below by the slightly different quantity $$\frac{1}{\ln 2}\times\left(\frac{j}{n}\right)\left[-m\left(\frac{j}{n}\right) + \ln(m) + 1\right]$$ such that $$ H(h,k) \ge m\sum_{j=0}^{n}\binom{n}{j}\left(\frac{1}{m}\right)^j\left(1-\frac{1}{m}\right)^{n-j}\times\frac{1}{\ln 2}\left(\frac{j}{n}\right)\left[-m\left(\frac{j}{n}\right) + \ln(m) + 1\right] \\ = \lg(m) - \frac{m-1}{n\ln 2} = k - \frac{2^k-1}{2^h\ln 2}$$ and so $$\lim\limits_{h\to\infty} H(h,k) \ge \lim\limits_{h\to\infty} k - \frac{2^k-1}{2^h\ln 2} = \boxed{k}$$

Answer 3

Edit: I was wrong below, as pointed out in the comments by @ManRow:

@ManRow, unfortunately you cannot use the Normal approximation to the binomial for answering Question 2. This is because}<\strike> the usual rule of thumb (see these stats notes, scroll to the bottom) for using this approximation (based on the deMoivre Laplace approximation Wikipedia) which is $$ np(1-p)\geq 10,\quad or \quad np(1-p)\geq 5~(\mathrm{less~ stringently}) $$ does not hold for $p=1/n.$

If we use the Poisson approximation, see David Pollard's notes at Yale here. We can replace $\mathrm{Bin}(n,p)$ by $\mathrm{Poi}(np),$ and LeCam has famously shown that $$ \sum_{k=0}^\infty |P(X=k)-P(Y=k)|\leq 4p $$ if $X\sim \mathrm{Bin}(n,p),$ and $Y\sim \mathrm{Poi}(np)$ which is amazing since you are summing over all natural numbers; recall that for us $p=1/n$.

Another technique we can use is the so-called Poissonization. The balls in Bins process is negatively correlated when you consider distinct bins, if a bin has more balls, another one has fewer. This is quite technical and delicate (Mitzenmacher and Upfal's Probability and Computing book discusses it, but I will skip the details). This actually means that if we pretend that the number of balls falling in distinct bins arrive at some fixed poisson rate $np,$ the approximations we need still hold in a very strong sense.

Therefore, we can approximate the binomial distribution in this problem with the relevant Poisson distribution. Recall that we have $m=n^2$ balls into $n$ bins thus we have the rate $\lambda=mp=n^2(1/n)=n.$

The recent paper https://arxiv.org/pdf/1001.2897.pdf has tight upper and lower bounds on the entropy of the Poisson distribution. This essentially means that for any $\lambda>0,$ we have (bottom of page 2) the approximation to the Poisson entropy $$ H(\lambda)=\frac{1}{2}\ln(2\pi \lambda)+\frac{1}{2} -\frac{1}{12\lambda}-\frac{1}{24 \lambda^2} +O(\lambda^{-3}), $$ and for $\lambda=n$ large ($n=2^h$) we obtain the approximation $$ H\approx \frac{1}{2} \ln(2 \pi n)+\frac{1}{2}\approx \frac{1}{2}(\ln 2\pi + \ln n) \approx \frac{1}{2 \ln 2} \lg n \approx 0.72 \lg n=0.72 h $$ which does not quite get us to the desired $$ \lim\limits_{h\to\infty}h-H(2h,h)=0^+ $$ since we can only conclude that the limit is $0.28 h.$ Maybe this is the real answer.