What type of commitment scheme is it?

Question

I am having a task where I have to evaluate a commitment scheme. I checked already a few questions here, but they have not helped me :( I hope someone is able to help me out in that.

What do I have?

$commit_H$ - perfectly hiding and computationally binding

$commit_B$ - perfectly binding and computationally hiding

Here is $commit_1(m)$ step-by-step.

$commit_1(m)$:

1. compute $(c_H, d_h) := commit_H(m)$
2. compute $(c_B, d_B) := commit_B(c_H)$
3. output $(c_B, (d_B, d_H))$

The first question is if this is a commitment scheme. My answer would be yes, because we have a commitment ($c_B$) and open values $(d_B, d_H)$.

How to open the commitment? $open(open(c_B, d_B), d_H)$

I hope this is correct so far. Now comes the part where I have no clue. I have to decide what type of commitment it is. Is it type B (perfectly binding) or type H (perfectly hiding).

My first thought was that it is perfectly binding. In order to proof this, I am using contradiction.

Contradiction: There exists an algorithm A, such that

$((x_1),(x_2)) \leftarrow A(1^n) ~~(x_1 \neq x_2)$

$commit(x_1) = commit(x_2)$

$commit_B(commit_H(x_1)) = commit_B(commit_H(x_2))$

$commit_B(c_{H1}) = commit_B(c_{H2})$

This would be a contradiction, because $commit_B$ is perfectly binding.

The next step would be to show that it is not perfectly hiding, because my though is that it is type B.

This is where I am stuck. $commit_B$ is not perfectly hiding, which means that an computationally unbound attacker would be able to decommit the first part ($commit_B(c_H)$), but would be stuck at the second part ($commit(m)$), because it is perfectly hiding.

My question would be, what am I doing wrong? Did I misunderstood something? Could someone help me out?

Thanks

---

Edit: Thanks to the answer from poncho, I get the following solution. It is not completed yet, since I fell unsure about it. Would be nice if someone or even poncho could correct if necessary.

The commitment scheme $commit_1(m)$ is of type $H$. This means, it would be perfectly hiding and computationally binding.

There are 3 things I want to show:

1. Perfectly hiding
2. Computationally binding
3. Not perfectly binding

I would like to start with number 3 - not perfectly binding.

$commit_H$ is not perfectly binding, which means that $\exists m_1, m_2; m_1 \neq m_2$ such that

$c_{H1}=commit_H(m_1)=commit_H(m_2)=c_{H2}$.

$\implies commit_B(c_{H1}) = commit(c_{H2})$

Even $commit_B$ is perfectly binding, after opening $c_B$ it would be possible to open $c_H$ to either $m_1$ or $m_2$ (given unbounded computation) (Thanks poncho).

Next, I would like to show perfectly hiding. I used therefore a game, where an Attacker sends $m_1$ and $m_2$ to $commit_B$ and this is send to $commit_H$. Here is the game I had been thinking of:

We have an unbounded attacker $A$ with an advantage of $\epsilon(n)$.

The probability to win this game is:

$Pr[b=b'] = Pr[Challenger_H(n)=1] = Pr[Challenger_B(n)=b]$ since he passes the messages $m_0$ and $m_1$ without altering them.

$Pr[b=b'] = Pr[Challenger_H(n)=1] = Pr[Challenger_B(n)=b] = Pr[A(n)=b]$.

Since $commit_H$ is perfectly hiding, we get the following equation:

$\frac{1}{2} = Pr[A(n)=b] = \frac{1}{2} + \epsilon(n)$ $\Rightarrow \epsilon = 0$ otherwise it would be a contradiction.

The last thing (can I call it property?) to proof is computationally binding. I am not sure yet how to do that. I am thinking to prove it with computationally and statistically indistinguishability. I will crack me head later on that one too.

Answer 1

Regarding the solution in the edit, you are overcomplicating things a little. The first proof to show that it is not perfectly binding is fine. But you're doing double work there - when showing that the scheme is perfectly hiding, you get not perfectly binding for free.

In the second part: Doing a constructive proof is almost always longer than doing a proof by contradiction. And your proof is actually wrong: Assume $\mathcal{A}$ doesn't actually do anything with the challenge, he just answers with a uniform bit. Then the formulas are still the same, but it doesn't prove anything about the commitment scheme.

Assume your scheme is not perfectly hiding and that you have an (potentially unbounded) for breaking the hiding property. Lead this adversary to breaking the actual perfectly hiding scheme - which is a contradiction to the assumption. A rough sketch:

• You are the attacker on the scheme $commit_H$, and you have access to $\mathcal{A}$, which can break $commit_1$ with some non-zero advantage $\epsilon$ (any kind of advantage means it is not perfectly binding)
• The game starts: $\mathcal{A}$ sends you his challenges $m_1,m_2$. You have them over to your challenger.
• You get a challenge $c=com_H(m_b)$. You use the commitment scheme $com_B$ and send $com_B(c)$ to $\mathcal{A}$.
• $\mathcal{A}$ answers with $b'$, which you just relay to your challenger.
• Now you can argue that you have the same non-zero advantage as $\mathcal{A}$. However, if you have any advantage at all, $commit_H$ would not be perfectly hiding.

Edit: there was an error in the original argument

Imagine an adversary $\mathcal{A}$, who can break the computationally binding property. Computationally binding means, that it is had to find two inputs with the same commitment as its output. So $\mathcal{A}$ is a poly-time algorithm, who can generate the following output: $m_1,m_2,r_1,r_2$, and the probability $Pr[m_1 \neq m_2, Commit(m_1,r_1)= Commit(m_2,r_2)]$ is non-negligible and $m_1,m_2$ are the messages and $r_1,r_2$ the random coins (which are usually also the open values)

In your example, the values $r_1$ and $r_2$ are actually tuples and they are what you define as open values, so they are $(d_{B,1},d_{H,1})$ and $(d_{B,2},d_{H,2})$.

So $\mathcal{A}$ is able to generate values $m_1,m_2,(d_{B,1},d_{H,1}),(d_{B,2},d_{H,2})$ and with non-negligible probability $m_1 \neq m_2$ and $Commit_1(m_1,d_{B,1},d_{H,1}) = Commit_1(m_2,d_{B,2},d_{H,2})$. In general this does not mean that the intermediaty values $Commit_H(m_1,d_{H,1})$ and $Commit_H(m_2,d_{H,2})$ are equal. However, we also know that the outer binding is perfectly binding. So that means no (unbounded) adversary can generate two messages with the same commitment - and that means $Commit_B$ is injective for any given message. And then we can follow that for the output of $\mathcal{A}$ we have $Commit_H(m_1,d_{H,1}) = Commit_H(m_2,d_{H,2})$.

Answer 2

My first thought was that it is perfectly binding.

It's not.

$commit_B(C_{H1}) = commit_B(C_{H2})$

That's fine

This would be a contradiction, because $commit_B$ is perfectly binding.

Actually, that's not a contradiction, because it's possible that $C_{H1} = C_{H2}$

After all, $H$ is not perfectly binding; what that means is that you can have two different messages with the same commitment (one would hope that it is hard to find both sets of the random coins that would yield the common commitment; but we're talking about existence, not computational complexity). In fact, if $H$ is perfectly hiding, then any valid commitment could possibly correspond to any message (if there's a message that it could not reveal, then the receiver could deduce that message was not the committed one).

Hence, $commit_H(M_1) = commit_H(M_2)$ is perfectly possible, given the appropriate random coins.

And, so, when we open the larger scheme, the committer can (given unbounded computation) change his mind what he opens $H$, and so this is not perfectly binding.