commitment
A player in protocol choose a value from some sets and commit to his choice such that he cannot change his mind. He may reveal his choice at some later time. Call prover P and verifier V.
binding and hiding
binding
binding: once P commit to his choice, he cannot change. It’s a limitation on the ability of P.
Unconditional/Perfect binding: Even with infinite computing power, P cannot change his mind after commiting, which means in $c = Commit_{pp}(b;r)$ there is at most one $b$ such that commitment is c for any c.
Conditional Binding: For any probabilistic polynomial algorithm $p^$, given $pp$ generated by $Gen(1^\lambda)$, let the probability $p^$ outputs $c, b, b’, r, r’$ such that $b \neq b’$ and $commit(b;r) = commit(b’;r’)$ be $\epsilon(\lambda)$. Then it should be negligible in $\lambda$. Negligible menas for any polynomial p, there exists some constant $\lambda_0$ such that $\epsilon(\lambda) < 1/p(\lambda)$ for $\lambda > \lambda_0$.
hiding
hinding: V cannot tell what the choice is before P decide to give V the key. It’s a limitation on the ability of V.
We need additional concept called indistinguishability for two distribution.
Perfect indistinguishable: for any x, $U_x = V_x$
| Statistically indis: for any x, $SD(U_x, V_x)$ is negligible of length of x. $SD(U, V) = 1/2 \sum | P(y) - Q(y) | $, P(y) is the probability of output y. 一个可行的含义，来自随机算法$\sum | P(y) -Q(y) | > max | P(y) - Q(y) | $，也就是说，对于每个输出，最坏的advantage也是negligible的. |
Computational indis: For any PPT D, D(U_x) and D(V_x) is stat dis. Then U and V is Comput indis. Or we can define it by advantage. For any ppt, the advantage tell which one is output from is negligible.
Computational hiding: (pp, Commit(0;r)) and (pp, Commit(1;r’)) is comput indis, where r and r’ are uniformly distributed over ${0,1}^\lambda$. We require V is computing power limited.
Uncomputational hiding: V may have infinite computing power.
Stat hiding: Commit(0;r) and Commit(1;r’) is stat indis.
Perfect hiding: Commit(0;r) and commit(1;r’) is perfect indis.
Both uncon hiding and uncon biding is impossible.
如果存在的话，对于c = commit(0;r)来说，不能存在commit(1;r’) = c，否则违背unconditional binding；但对于V来说，他得到了一个commitment不可能由1commit出来，则他得到了P的choice是0，因此矛盾。
因此，只有uncon binding和con hiding，或者con binding和uncon hiding.
对于前者，只要是正确的pp，P就没有办法作弊，但是V可能控制pp的生成，获得优势，因此我们让P执行Gen，V check。
对于后者，只要PP正确，V就没办法作弊，因此让V执行Gen，P check。