1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.