1. commitment scheme

commitment scheme是密码学中必不可少的primitive，存在2个角色——committer和receiver： committer 将a value put in a locked box，将该locked box给receiver，因此除committer外无人知道具体的value值（即hiding属性），由于locked box已在receiver手上，该committer不能open出2个不同的value值for the same commitment（即binding属性）。

同时，可以在不泄露具体value值的情况下，证明relations between committed values。

通常，a non-interactive commitment scheme中包含3个基本算法：

$Setup(1^k)$：输入为security parameter $k$，输出为系统需要的public parameters。$Commit(m,r)$：输入为待commit的message $m$，随机值$r$，输出为commitment $c$和an opening value $d$。$Verify(c,m,d)$：输入为commitment $c$、message $m$ 和 an opening value $d$，输出为yes or no，即表示验证是否通过。

其中，commitment $c$ is sent to the receiver at the commit time，而opening value $d$ is sent together with the message $m$ at the opening time to allow verification。

hiding 属性：是指commitment $c$不会泄露$m$ (either perfect secrecy, or computational indistinguishability)。binding 属性：是指no adversary (either powerful or computationally bounded) can generate $c,m\ne m^{\prime },d,d^{\prime }$使得$Verify(c,m,d)$和$Verify(c,m^{\prime },d^{\prime })$都成立。

接下来将介绍2个简单的commitment schemes，二者具有互补特性，可结合使用形成powerful commitment scheme：

Pedersen CommitmentEIGamal Commitment

2. Pedersen commitment

考虑$\mathbb{G}=<g>$ 为a cyclic group of prime order $q$，2个随机generators $g,h\in \mathbb{G}$。 Pedersen commitment允许commit to scalar elements from ${\mathbb{Z}}_q$：

Commitment： 为了commit to a scalar $m\in {\mathbb{Z}}_q$，one 选择a random $r\leftarrow {\mathbb{Z}}_q$，设置$c\leftarrow g^m{h}^r$，相应的opening value为$r$。

Opening： 为了open a commitment $c\in \mathbb{G}$，one reveal the pair $(m,r)$。若$c=g^m{h}^r$成立，则receiver accepts the opening to $m$，否则拒绝。

Q-1: Pedersen commitment具有perfectly hiding属性——even a powerful adversary cannot have any idea about the committed value。 Q-2: Pedersen commitment具有computationally binding属性——除非one can break a problem (to be specified), 否则 adversary can not open a commitment in two different ways。 Q-3: Pedersen commitment 是equivocal 模棱两可的：simulator 使用a trapdoor (仅simulator本人知道) 来生成 parameters $(g,h)$时（与Setup算法无法区分），该simulator可生成a commitment $c\in \mathbb{G}$，然后open成任意的值。【其实应该就是指若simulator知道$g^a=h$，其中$a$为trapdoor，则该simulator可生成a commitment $c$，并将其open为任意值。】 Q-4: 何时可在a security proof中使用Pedersen commitment的binding属性 和 equivocality 模棱两可? Q-5: 何时可在a security proof中使用Pedersen commitment的hiding属性 和 equivocality 模棱两可?

3. EIGamal commitment

考虑$\mathbb{G}=<g>$ 为a cyclic group of prime order $q$，2个随机generators $g,h\in \mathbb{G}$。 EIGamal commitment允许commit to group elements from $\mathbb{G}$：

Commitment： 为了commit to a group element $M\in \mathbb{G}$，one 选择a random $r\leftarrow {\mathbb{Z}}_q$，设置$c\leftarrow (c_0=g^r,c_1=M{h}^r)$，相应的opening value为$r$。Opening： 为了open a commitment $c\in \mathbb{G}$，one reveal the pair $(M,r)$。若$c=(g^r,M{h}^r)$成立，则receiver accepts the opening to $M$，否则拒绝。

Q-6: EIGamal commitment具有perfectly binding属性——even a powerful adversary cannot open a commitment in two different ways。【对于group order $q$，若存在$r\ne r^{\prime }\mathrm{m}\mathrm{o}\mathrm{d}q$，则$g^r\ne g^{r^{\prime }}$，对应的$x=r^{\prime }-r\mathrm{m}\mathrm{o}\mathrm{d}q$，$x$为non-zero modulo $q$。因此有$g^{r^{\prime }}=g^{r+x}=g^r\cdot g^x$，若$x$为not zero or a multiple of the group order，则不存在$r\ne r^{\prime }\mathrm{m}\mathrm{o}\mathrm{d}q$，使得$g^r=g^{r^{\prime }}$成立。因此，EIGamal具有perfectly binding属性。】 Q-7: EIGamal commitment具有computationally hiding属性——除非one can break a problem (to be specified), 否则 adversary can not distinguish commitments to $M_0$ or $M_1$ of its choice。【即an unbounded adversary can simply try all possible $r\in {\mathbb{Z}}_q$ till it matches $g^r$，然后根据已知的$r$ 可找到 $M\in \mathbb{G}$ matches $M{h}^r$。】 Q-8: EIGamal commitment 是extractable可提取的：simulator 使用a trapdoor (仅simulator本人知道) 来生成 parameters $(g,h)$时（与Setup算法无法区分），则该simulator可extract the committed value in any $c\in \mathbb{G}$。【其实应该就是指若simulator知道$g^a=h$，其中$a$为trapdoor，则该simulator可extract $M=B/A^a$。】 Q-9: 何时可在a security proof中使用EIGamal commitment的binding属性 和 extractability可提取? Q-10: 何时可在a security proof中使用EIGamal commitment的hiding属性 和 extractability可提取? Q-11: EIGamal commitment之所以称为”EIGamal” commitment，是因为这其实就是EIGamal encryption。（具体可参见博客 EIGamal encryption VS Pairing encryption） How one could make the hiding property and the extractability compatible without any limitation？

4. Non-interactive commitments （Pedersen commitment + EIGamal commitment）

Pedersen commitment：

perfectly hidingcomputationally binding

EIGamal commitment：

computationally hidingperfectly binding

Q-12: 由此可知，a non-interactive commitment 不可能同时具有perfectly hiding和perfectly binding属性。（which would mean both hiding and binding against powerful adversaries。）

an efficient construction in the random oracle model为： $c=Commit(m,r)=H(m,r)$ 其中$H$为hash函数 $H:\{0,1{\}}^{\ast }\to \{0,1{\}}^{2k}$，on the message $m\in \{0,1{\}}^{\ast }$ to commit, with random coins $r\in \{0,1,{\}}^{3k}$，for security parameter $k$，相应的opening value为 $r$。 Q-13: 以上random oracle model下的构建确实是a non-interactive commitment scheme (具有hiding和binding属性)，and say under which assumptions (some limit or not on the number of queries to the random oracle)。 Q-14: Show that it is also extractable and equivocal for a simulator that can access the list of query-answer pairs and that can program the random oracle in an indistinguishable way。

为了在standard model（而不是random oracle model）情况下，实现类似以上的具有equivocal和extractable的commitment scheme，具体的构建思路为：

an equivocal bit-commitment scheme $Commi{t}_{eq}(b,r)$，for a bit $b\in \{0,1\}$ and random coins $r$，输出为a commitment $c$，和 opening value $d\in \{0,1{\}}^{2k}$。（可参见博客 水银承诺mercurial commitment 中的chameleon hash function。其本质可为Pedersen commitment。）an extractable commitment scheme $Commi{t}_{ext}(D,r^{\prime })$, for a bitstring $D\in \{0,1{\}}^{2k}$ 安定random coins $r^{\prime }$，输出为commitment $c^{\prime }$和opening value $O$。

注意以上两种commitment scheme中，$Commi{t}_{eq}$的输出opening value $d$ 为 $Commi{t}_{ext}$ 的输入$D$，两者都在the same space $\{0,1{\}}^{2k}$

On a message $m=(m_1,\cdots ,m_l)\in \{0,1{\}}^l$ ，整个commitment 算法 $Commit(m,((r_i{)}_i,(D_i^{\prime }{)}_i,(r_{i,b}^{\prime }{)}_{i,b}))$流程为：

for random coins $r_i$ for $i=1,\cdots ,l$，设置$(c_i,D_i)\leftarrow Commi{t}_{eq}(m_i,r_i)$；for random coins $D_i^{\prime }\leftarrow \{0,1{\}}^{2k}$，设置$d_{i,m_i}\leftarrow D_i,d_{i,1-m_i}\leftarrow D_i^{\prime }$ for $i=1,\cdots ,l$；for random coins $r_{i,b}^{\prime }$，设置$(c_{i,b}^{\prime },O_{i,b})\leftarrow Commi{t}_{ext}(d_{i,b},r_{i,b}^{\prime })$ for $i=1,\cdots ,l$ and $b=0,1$；output the commitment $(c_i,(c_{i,b}^{\prime }{)}_b{)}_i$，opening value $(d_{i,m},O_{i,m_i}{)}_i$。

Q-15: Explain how works the Verify 算法。 Q-16: Show this is indeed a commitment scheme: with both hiding and binding properties。 Q-17: Show this commitment scheme is also both equivocal and extractable。

参考资料：

[1] Difference between Pedersen commitment and commitment based on ElGamal [2] David Pointcheval 的课件Commiments Schemes [3] Why is the El Gamal commitment scheme information theoretically binding?