0
$\begingroup$

Given two commitment schemes $Com_1, Com_2$ (both have the hiding property), I'd like to prove $Com_1(m) || Com_2(m)$ is also hiding.

I built these hybrids and want to show $H_0 =_c H_1 =_c H_2$.

\begin{align} H_0 &= Com_1(m) || Com_2(m) \\ H_1 &= R_1 || Com_2(m) \\ H_2 &= R_1 || R_2 \end{align}

For $H_1 =_c H_2$: If some $D$ tells apart $H_1$ from $H_2$ then we can distinguish $Com_2(m)$ and $R_2$ by prepending some random $R_1$ and then call $D$.

But how could we prove $H_0 =_c H_1$?

$\endgroup$
  • $\begingroup$ You should check the definition of hiding. A commitment scheme is not required to be pseudorandom. It can be trivial to distinguish a commitment from a random value, so your hybrids are not indistinguishable. Hiding is about not being able to distinguish between commitments of $m_0$ and $m_1$. $\endgroup$ – Maeher Dec 13 '18 at 7:36
1
$\begingroup$

I hope this is not homework. It should be almost the same as proving $H_1=_cH_2$. Just let the distinguisher (that distinguishes $Com_1(m)$ and $R_1$) generate and append $Com_2(m)$ in both worlds. This can perfectly simulate the view of the distinguisher that distinguishes $H_0$ and $H_1$.

$\endgroup$
  • $\begingroup$ (edited) Thanks Shan. This proof is part of a previously completed homework question which I am now reviewing. I previously missed that (1) the hiding property involves two different messages $m_0$ and $m_1$, and (2) the two message are be chosen by the adversary (and therefore adversary can compute $Com_1(m_b)$ and $Com_2(m_b)$ where $b\in \{0,1\}$) because in order to satisfy the hiding property, the commitment scheme must produce computationally indistinguishable ciphers for ALL pairs of messages. $\endgroup$ – sam Dec 13 '18 at 2:16
  • 1
    $\begingroup$ @sam My pleasure. Btw, I think for the commitment hiding property indistinguishability between two chosen messages can be implied by indistinguishability between one chosen message and a random string (as described in your question). $\endgroup$ – Shan Chen Dec 13 '18 at 2:23
0
$\begingroup$

The hybrids you came up with are not helpful for proving the statement. A commitment scheme is not required to have commitments be indistinguishable from random strings. For example, let $\operatorname{Com}$ be a (binding and hiding) commitment scheme, then $\operatorname{Com'}$ defined as $$\operatorname{Com'}(m) = 0\|\operatorname{Com}(m)$$ is also hiding and binding. But with $\operatorname{Com'}$ your hybrids are trivially distinguishable with probability $1/2$ by simply checking whether the first bit is zero (or the first bit of the second half for $H_1,H_2$).

The hiding experiment works by letting the adversary choose two messages $m_0,m_1$. The adversary then receives either $\operatorname{Com}(m_0)$ or $\operatorname{Com}(m_1)$ and should not be able to distinguish between the two cases with more than negligible probability.

To then prove the original statement from you question, that $\operatorname{Com}(m) = \operatorname{Com_1}(m)\|\operatorname{Com_2}(m)$ is hiding whenever both $\operatorname{Com_1}$ and $\operatorname{Com_2}$ are hiding you can indeed work with a hybrid argument.

Your extreme hybrids are the two cases of the hiding experiment. I.e., in hybrid $H_0$, the adversary will receive $\operatorname{Com_1}(m_0)\|\operatorname{Com_2}(m_0)$ and in $H_2$, the adversary will receive $\operatorname{Com_1}(m_1)\|\operatorname{Com_2}(m_1)$. You can then define an intermediate hybrid $H_1$, where the adversary receives $\operatorname{Com_1}(m_1)\|\operatorname{Com_2}(m_0)$ instead.

The reduction to show that each pair of hybrids is indistinguishable is very simple. Let $\mathcal{A}$ be an arbitrary PPT distinguisher against the hiding property of $\operatorname{Com}$.

We then construct a distinguisher $\mathcal{R}$ against the hiding property of $\operatorname{Com_1}$ as follows: $\mathcal{R}$ runs $\mathcal{A}$ and receives two messages $m_0,m_1$, that it also outputs to the outer hiding experiment, receiving a commitment $c_1$ as response. $\mathcal{R}$ then gives $c_1\|\operatorname{Com_2}(m_0)$ to $\mathcal{A}$. Eventually $\mathcal{A}$ outputs a bit $b'$, which $\mathcal{R}$ also outputs. Note that if $\mathcal{R}$ receives $c_1=\operatorname{Com_1}(m_0)$, then it perfectly simulates $H_0$. On the other hand if it receives $c_1=\operatorname{Com_1}(m_1)$, then it perfectly simulates $H_1$. Thus, $\mathcal{R}$ distinguishes those two cases with the same probability with which $\mathcal{A}$ distinguishes $H_0$ and $H_1$. By the assumption that $\operatorname{Com_1}$ is hiding, this implies that the probability must be negligible.

Similarly, we can construct a distinguisher $\mathcal{R}$ against the hiding property of $\operatorname{Com_2}$. $\mathcal{R}$ runs $\mathcal{A}$ and receives two messages $m_0,m_1$, that it also outputs to the outer hiding experiment, receiving a commitment $c_2$ as response. $\mathcal{R}$ then gives $\operatorname{Com_1}(m_1)\|c_2$ to $\mathcal{A}$. Eventually $\mathcal{A}$ outputs a bit $b'$, which $\mathcal{R}$ also outputs. Note that if $\mathcal{R}$ receives $c_2=\operatorname{Com_1}(m_0)$, then it perfectly simulates $H_1$. On the other hand if it receives $c_2=\operatorname{Com_1}(m_1)$, then it perfectly simulates $H_2$. Thus, $\mathcal{R}$ distinguishes those two cases with the same probability with which $\mathcal{A}$ distinguishes $H_1$ and $H_2$. By the assumption that $\operatorname{Com_2}$ is hiding, this implies that the probability must be negligible.

Using the triangle inequality we can then conclude that also $H_0$ and $H_2$ must be indistinguishable, thus proving hiding of $\operatorname{Com}$.

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