What type of commitment scheme is it? 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)$:


compute $(c_H, d_h) := commit_H(m)$
compute $(c_B, d_B) := commit_B(c_H)$
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:


Perfectly hiding
Computationally binding
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.
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.