<p>This certainly follows for $n=1$.</p>

<p>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).</p>

<p>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.</p>

<p>I think from this you should be able to see how this generalizes to $n&gt;1$ as well. Basically, you note that</p>

<p>$$\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],$$</p>

<p>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$).</p>

CC BY-SA 3.0
2013-08-14T06:00:41.163Z
2013-08-14T06:07:39.700Z
2013-08-14T06:07:39.700Z
D.W.
<p>Let $C_n$ be a non-interactive <em>statistically-hiding</em> 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)$.</p>

<p>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$.</p>

<p>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.$$</p>

<cr.crypto-security><pr.probability><it.information-theory>
A theorem regarding statistically-hiding commitment schemes
Sadeq Dousti
# A theorem regarding statistically-hiding commitment schemes

(Asked by: username_0 on 2013-08-13)

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.$$

**Tags:** cr.crypto-security, pr.probability, it.information-theory

---

## 1 answers

### Answer by username_1 on 2013-08-14. Score: 1 | Accepted answer

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$).


---

