= Hamming-weight leakage of a uniform bit string
{c}
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.<Universally Composable Security: A Tutorial by Ran Canetti>[PDF pp. 25 and 33, permitted leakage and message-length disclosure]{ref}
There are $\binom nw$ strings of weight $w$. Hence $W$ has a <binomial distribution>, and <conditional probability> gives
$$
\Pr(W=w)=\frac{\binom nw}{2^n},\qquad
\Pr(X=x\mid W=w)=\frac1{\binom nw}
$$
for each compatible string $x$. The optimal complete-string guess therefore succeeds with probability $1/\binom nw$ after that observation. For $n=4$, observing $w=2$ leaves six equally likely strings; observing $w=0$ identifies `0000` exactly.
Averaging over disclosed weights yields
$$
p_{\mathrm{guess}}(X\mid W)
=\sum_{w=0}^n\frac{\binom nw}{2^n}\frac1{\binom nw}
=\frac{n+1}{2^n},
$$
compared 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)$ and
$$
H(X\mid W)=n-H(W)
=\sum_{w=0}^n\frac{\binom nw}{2^n}\log_2\binom nw.
$$
For $n=4$, $H(W)\approx2.03064$ bits and $H(X\mid W)\approx1.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.
Back to article page
