 Hamming-weight leakage of a uniform bit string

Let $X$ be uniformly distributed over the $2^n$ bit strings of length $n$, and disclose only its Hamming weight $W$, the number of one-bits. This is a deterministic cryptographic leakage function. Its consequences depend on the observed weight, even though $W$ has only $n+1$ possible values. A permitted disclosure belongs in the security model; the existence of that model does not establish that the disclosure is harmless.^[ref]

There are $\left(\genfrac{}{}{0ex}{}{n}{w}\right)$ strings of weight $w$. Hence $W$ has a binomial distribution, and conditional probability givesfor each compatible string $x$. The optimal complete-string guess therefore succeeds with probability $1/\left(\genfrac{}{}{0ex}{}{n}{w}\right)$ after that observation. For $n=4$, observing $w=2$ leaves six equally likely strings; observing $w=0$ identifies 0000 exactly.

Averaging over disclosed weights yieldscompared with $2^{-n}$ before disclosure. For four bits this changes $1/16$ to $5/16$. The worst conditional outcome has success probability one. An average guarantee and a guarantee for every observation are consequently different claims.

The information entropy calculation answers another question. Since $W$ is determined by $X$, the mutual information satisfies $I(X;W)=H(W)$ andFor $n=4$, $H(W)\approx 2.03064$ bits and $H(X\mid W)\approx 1.96936$ bits. These entropy values are not obtained by taking the logarithm of the average guessing probability. All calculations here assume the uniform prior and no additional correlated observation.