The commitment schemes like Pedersen's or Hash based, either have information theoretic hiding and computational binding or computational hiding and information theoretic binding. So can we ever get both information theoretic hiding and binding? Is it ever possible to do, or it is proven to be impossible?
$\begingroup$
$\endgroup$
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
1
It's impossible. In order to be perfectly hiding, it must be the case that two different messages can produce the same commitment string. But then that commitment can be opened in two ways (by an unbounded committer), so the scheme is not perfectly binding.
answered Nov 26, 2016 at 13:07
-
$\begingroup$ This is good, can explan why first message is Unconditional , we should need Computational for next message? $\endgroup$ Commented Jul 7, 2023 at 12:36
$\begingroup$
$\endgroup$
1
Another way to look at it informally is this;
If it is perfectly hiding, then you cannot tell what made the final value. It could equally be any combination.
If it is perfectly binding, then there is only one combination that produces the final value, essentially binding the final value to that one combination.
Let's say we are talking about addition, and I give you the number 10.
What two numbers gave the number 10?
It could be (5,5), (1, 9),(6,4) ....
This is perfectly hiding because it could be any of those combinations that make the number 10.
Let's now say we are talking about multiplication, and the number is always prime.
So I give you 19.
What two numbers multiplied together, gave 19?
There is only one possibility: (19,1)
This can be seen as perfectly binding. Essentially binding the final value to that specific value.
It might be easier to see now, why the two cannot be both satisfied simultaneously.
If the scheme is not binding, but there is no easy way to find what the exact combination is. Then we can say it is computationally binding.
-
$\begingroup$ This is a useful answer, thanks. $\endgroup$ Commented Jul 7, 2023 at 20:11
$\begingroup$
$\endgroup$
To be a little more formal, consider the notation provided by Iftach, where $S$ denotes the commitment sender and $R$ denotes the receiver.
Assume a commitment scheme $(S,R)$ is statistically hiding. This means that a computationally unbounded $R$ is unable to get any information about $m$ from the commitment $c$. Since the process of computing a commitment is known to both parties, this means that there must exist $(m,d)\neq (m',d')$ such that both $(m,d)$ and $(m',d')$ produce $c$ as a commitment. If this wasn't the case, $R$ would be able to obtain a unique $(m, d)$ from $c$. But, the existence of these multiple solutions show that a computationally unbounded $S$ can produce either $(m, d)$ or $(m', d')$ in the reveal phase, meaning that $(S, R)$ can't be statistically binding.
