4
$\begingroup$

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: Perfectly Hiding

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.

$\endgroup$
  • $\begingroup$ I'm having a bit of a problem parsing what the proposed combination method is. You note that $d_H$ opens $c_H$; you don't state what $c_H$ is (or what is being committed). Is what you're doing is generating a $D$-commitment for $M$; and then generating a $C$-commitment for that commitment? Or, are both commitments done on $M$ (in parallel)? $\endgroup$ – poncho May 4 '17 at 22:36
  • $\begingroup$ I added a step-by-step description of $commit_1(m)$ at the end. Does that help? $\endgroup$ – Donut May 4 '17 at 23:02
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thx for your information. I will work on it and correct it. There is one question I have regarding the second part. You are saying that my solution is wrong. Do you mean, that the probability is wrong or everything in the second part is wrong? It sounds to me, that your sketch looks like the game I have, when I understood it correct. $\endgroup$ – Donut May 5 '17 at 18:22
  • $\begingroup$ I edited the probability. Does this look better? I am not sure how your sketch differs from my game. $\endgroup$ – Donut May 7 '17 at 12:00
  • $\begingroup$ I think I read your explanation for the last point like 100 times but I don't get it. So far I get the following: $\endgroup$ – Donut May 7 '17 at 13:12
  • $\begingroup$ I think I read your explanation for the last point like 100 times but I don't get it. So far I get the following: 1) We assume an algorithm exists which outputs us 2 commitments and two open values. The probability that they open to the same value is $\gt negl$. 2)Removing outer layer: we would get $c_{H1}$ and $c_{H2}$. You are saying that we have 4 values. Do you mean $c_{H1}, c_{H2}, c_{B1}, c_{B2}$? $\endgroup$ – Donut May 7 '17 at 13:42
  • $\begingroup$ @Donut The proof is wrong in the sense that your attacker might not even try to solve the problem and still you could end up with equal probabilities. In general: If two events $A$ and $B$ have the same probability, that is no guarantee for any kind of correlation. So arguing via probabilities alone does not necessarily provide you with any meaningful result. As I said, if $\mathcal{A}$ ignored the input and just outputs a bit with probability $0.5$, your argument is still true - while saying nothing about the actual commitment scheme. $\endgroup$ – tylo May 8 '17 at 6:48
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Ok, thank you for it. I will try to do it again and add it then. $\endgroup$ – Donut May 5 '17 at 8:25

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.