0
$\begingroup$

Given a commitment scheme which is computationally binding (based on some conjectured hard problem, say), does it also imply that the scheme is unconditionally hiding?

My idea was: Since the scheme is computationally binding, it can be broken by an unbounded adversary, who can produce two openings to the same commitment. But this would make the scheme perfectly hiding, because even an unrestricted attacker cannot distinguish between the two (or more) openings of the same commitment by any means.

Is this correct? If not, are there any schemes that prove otherwise?

$\endgroup$
3
$\begingroup$

This is not correct. It could be not binding since you can open a commitment into two options. You can quite easily construct such a scheme artificially. For example, take any perfectly binding scheme $C_b$ and any perfectly hiding scheme $C_h$. Then, commit to a message $m$ by committing to $C_b(m)||C_h(0)$ or by committing to $C_b(\overline{m})||C_h(1)$. Then, when you decommit, if the perfectly hiding part is 0, take the message $m$ in the perfectly binding part. In contrast, if the perfectly hiding part is 1, take the complement of the message in the perfectly binding part.

Clearly, this is a computationally binding scheme only, since an all-powerful committer can break the binding of the perfectly hiding part, and so can recommit to either the message or its complement. In addition, the scheme is clearly only computationally hiding as well.

| improve this answer | |
$\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.