# Commitment scheme: hiding property

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

• 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$. – Maeher Dec 13 '18 at 7:36

## 2 Answers

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

• (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. – sam Dec 13 '18 at 2:16
• @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). – Shan Chen Dec 13 '18 at 2:23

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