A theorem regarding statistically-hiding commitment schemes

Question

Let $C_n$ be a non-interactive statistically-hiding commitment scheme, able to commit to an $n$-bit string. To commit to $m \in \{0,1\}^n$, the sender picks a random $r$ (of proper length), and sends $C_n(m ; r)$ to the receiver. To decommit, he simply reveals $m$ and $r$. We let $C_n(m)$ denote the random variable obtained by uniformly and independently picking $r$ (of proper length) and computing $C_n(m ; r)$.

Finally, let $U_n$, $U_n'$, and $U_n''$ be i.i.d. random variables with uniform distribution over $\{0,1\}^n$. We assume that repeated use of a random variable results in the same sample. For example, $\langle U_n, U_n+1 \rangle$ means a pair, where we first sample $U_n$ to obtain an $n$-bit string $m$, and then let the pair be $\langle m, m+1 \rangle$.

I want to prove that the following distribution ensembles are statistically indistinguishable: $$\mathcal {X} = \{\langle U_n, C_n(U_n) \rangle\}_{n \in \mathbb{N}} \enspace,$$ $$\mathcal {Y} = \{\langle U_n', C_n(U_n'') \rangle\}_{n \in \mathbb{N}} \enspace.$$

Answer 1

This certainly follows for $n=1$.

Fix any algorithm $A$ that attempts to distinguish, and let $p_{a,b} = \Pr[A(\langle a, C(b) \rangle)=1]$, where $a,b\in \{0,1\}$. Now by the assumption that $C$ is statistically hiding, we have $p_{0,0} \approx p_{0,1}$ (for otherwise you could prepend the fixed constant 0 to any commitment and then use $A$ to break the hiding property) and we have $p_{1,0} \approx p_{1,1}$ (for a similar reason).

Expanding out the definitions, we have $\Pr[A(X)=1]=(p_{0,0}+p_{1,1})/2$ and $\Pr[A(Y)=1]=(p_{0,0}+p_{0,1}+p_{1,0}+p_{1,1})/4$ (where $X,Y$ are samples from your distributions ${\cal X},{\cal Y}$). But from the facts above, we have $2p_{0,0} + 2p_{1,1} \approx p_{0,0} + p_{0,1} + p_{1,1} + p_{1,0}$, i.e., $\Pr[A(X)=1]\approx \Pr[A(Y)=1]$, and thus $X,Y$ are statistically indistinguishable.

I think from this you should be able to see how this generalizes to $n>1$ as well. Basically, you note that

$$\Pr[A(X)=1]=1/2^n\sum_b \Pr[A(\langle b,C(b)\rangle)=1]\approx 1/2^{2n}\sum_{a,b} \Pr[A(\langle a,C(b)\rangle)=1] = \Pr[A(Y)=1],$$

using the fact that $\Pr[A(\langle a,C(b))\rangle)=1] \approx \Pr[A(\langle a,C(b')\rangle)=1]$ for all fixed $a,b,b'$ (otherwise you could distinguish $C(b)$ from $C(b')$ by simply prepending $a$ and then running $A$).