更新：由于这篇文章的内容大部分是我的脑洞，所以我不能确保正确性，目前我已经把文章设为隐藏状态，如果你碰巧访问到这篇文章，请自行辨识内容的正确性。

PS：关于非交互承诺方案的一些更严谨的内容目前被写在了我的硕士论文中，在我大论文完成后我也会公开这些内容，所以，别急（

以下是正文：

最近在搞的Commitment，卡壳了，写个笔记整理下思路。

这一篇会讲普通的Commitment，还有更复杂的UC Commitment以后有机会再补（逃

另外，以下某些结论是我突然拍脑袋想出来的，所以有错也很正常，欢迎纠错

定义与安全定义·

简介——承诺和打开·

承诺方案（Commitment）如其名是在模拟一个承诺的过程，举个栗子，我要给你某个值（比如我银行卡密码，我也不知道为什么要给密码），但不能现在给（不然钱就被你拿走了），所以就先给你做个承诺，说我密码一定是123456（但是做承诺时不能暴露我的密码），等过了一段时间后（比如我把钱全拿出来了），再给你打开承诺（即把我密码123456发给你），你一看，这密码和我之前的承诺对上了，说明我没有骗你，一看对不上，就说明我撒谎了。

以上栗子由于是个生活中的栗子，所以会比较含糊，比如，“我”要怎么做到承诺但是不暴露我的密码呢？“你”又怎么做到根据“我”的承诺判断我密码真的是123456呢？“我”能不能做假的承诺来骗“你”呢？“你”又能不能从“我”的承诺中提取出“我”的密码呢？所以严格来说还需要一个具体的安全定义，比如定义一些安全属性。

说安全定义之前先要知道承诺方案的过程，如上面栗子加粗的，有承诺（Commit）和承诺打开（Open）两个阶段。习惯上会把承诺的信息记作mm；承诺时需要的随机数记作rr；承诺阶段会输出一个承诺值和打开值（反正英文时opening value），分别记作cc和dd。承诺打开阶段执行完后会输出接受或拒绝（Accept/Reject），以表示cc真的或假的承诺了mm。通常做承诺的那一方被叫作承诺方（Committer）打开承诺的一方叫作接收方（Receiver）。形式上这两个阶段是（这里画图更像非交互的承诺方案，实际上Commit和Open时是可以承诺方与接收方有多轮交互的）：

Committer(m)              Receiver(c,d)←Commit(m,r)⟶c⋮⟶m, dOpen(c,m,d)→Accept/Reject\begin{array}{|c|} \hline \\ \begin{array}{ccc} \mathrm{Committer}(m) & \ \ \ \ \ \ \ \ \ \ \ \ \ \ & \mathrm{Receiver} \\ \begin{array}{l} (c, d) \leftarrow \rm{Commit}(m, r) \end{array} & & \\ & \overset{c}{\longrightarrow} & \\ \vdots & & \\ & \overset{m,\ d}{\longrightarrow} & \\ & & \begin{array}{l} \rm{Open(c, m, d)} \rightarrow \text{Accept/Reject} \end{array} \\ \end{array} \\ \hline \end{array}

安全定义——绑定和隐藏·

接下来是安全定义，承诺方案需要满足两个安全属性：绑定（Binding）和隐藏（Hiding）。Binding即Commit承诺出来的cc绑定了mm，承诺方不能用另一个m′≠mm' \ne m使得接收方在Open时输出Accept，主要针对不诚实的承诺方；Hiding即cc隐藏了mm，接收方收到cc后，不能根据cc恢复出mm，主要针对不诚实的接收方。承诺方案的安全定义我翻了很多论文其实都没有详细说的，所以下面套一下wiki的定义：

  • Binding：不存在m′≠mm' \ne m，使得Commit(m,r)=Commit(m′,r′)\rm{Commit}(m, r)=\rm{Commit}(m', r')。
  • Hiding：令R\mathcal{R}是所有随机数的集合，对于所有m′≠mm' \ne m，都有{Commit(m,R)}≡{Commit(m′,R)}\{\rm{Commit}(m, \mathcal{R})\} \equiv \{\rm{Commit}(m', \mathcal{R})\}。

对于Binding属性，个人感觉现在的定义应该更像是：给定(c,d)←Commit(m,r)(c, d) \leftarrow \rm{Commit}(m, r)，不存在m′≠mm' \ne m和d′d'，使得Open(c,m′,d′)=Accept\rm{Open}(c, m', d')=\rm{Accept}（即上面的中文描述）。而对于上面的定义，感觉上是一些古老的Commitment方法（比如[DN02]，另外这里用等号表示Commit出的cc，懒得写dd了-）在Open时直接检测c=?Commit(m,r)c \overset{?}{=} \rm{Commit}(m, r)，而不存在m′≠mm' \ne m，使得Commit(m,r)=Commit(m′,r′)\rm{Commit}(m, r)=\rm{Commit}(m', r')就不存在m′m'使得Open输出Accept了。而对于现在各种Open花里胡哨的Commitment，“不存在m′≠mm' \ne m，使得Commit(m,r)=Commit(m′,r′)\rm{Commit}(m, r)=\rm{Commit}(m', r')”感觉只是个必要条件，而不充分（个人感觉），不过如果Open设计的好的话估计也可以做到充分（吧

对于Hiding属性，{Commit(m,R)}≡{Commit(m′,R)}\{\rm{Commit}(m, \mathcal{R})\} \equiv \{\rm{Commit}(m', \mathcal{R})\}的意思是，对于所有m′≠mm' \ne m，拿所有的ri∈Rr_i \in \mathcal{R}分别跟mm和m′m'做Commit后，它们的结果的集合相同，即给定一个cc，它有可能由任意一个mi∈Mm_i \in \mathcal{M}承诺出来的（这里的M\mathcal{M}指明文空间），所以知道了cc也不会泄露mm的任何信息。

上述的Binding和Hiding定义中，其实还有安全性的强弱之分的。如果Binding定义中的“不存在”是真的不存在，那就是完美绑定（Perfectly Binding），即即使攻击者具有无限的能力（Unbounded，比如可以遍历整个明文空间M\mathcal{M}，之类的）也不能找到两个承诺值相同的消息；如果只是计算上的不存在，那就是计算上的绑定（Computational Binding），即可能存在m′≠mm' \ne m，使得Commit(m,r)=Commit(m′,r′)\rm{Commit}(m, r)=\rm{Commit}(m', r')，但是不能在多项式时间内计算出来（但是Unbounded的攻击者可以找到）。类似地，如果Hiding定义中的“≡\equiv”是真的相等，那就是完美隐藏（Perfectly Hiding），即Unbounded的攻击者也不能根据cc恢复mm；如果“≡\equiv”是计算上的相等（即≡c\overset{c}{\equiv}），那就是计算上的隐藏（Computational Hiding），即不能在多项式时间内恢复mm（同样，Unbounded的可以）。（PS：不知道以后会不会弄出个Quantum Binding / Quantum Hiding，逃

Perfect的安全性显然比Computational的高，但坏消息是，Binding和Hiding是不能同时做到Perfect的，这个可以简单从定义上推出，即不存在m′≠mm' \ne m，使得Commit(m,r)=Commit(m′,r′)\rm{Commit}(m, r)=\rm{Commit}(m', r')的话，就不会有{Commit(m,R)}≡{Commit(m′,R)}\{\rm{Commit}(m, \mathcal{R})\} \equiv \{\rm{Commit}(m', \mathcal{R})\}；相似地，若对于所有m′≠mm' \ne m，都有{Commit(m,R)}≡{Commit(m′,R)}\{\rm{Commit}(m, \mathcal{R})\} \equiv \{\rm{Commit}(m', \mathcal{R})\}，即会存在m′≠mm' \ne m，使得Commit(m,r)=Commit(m′,r′)\rm{Commit}(m, r)=\rm{Commit}(m', r')。也可参考这里。

后门——提取和模棱两可·

提取和模棱两可是一些后门属性，主要用于UC的Commitment方案证明中（深入了解的可参考[CF01]）。

  • 提取（extractability）即在知道某个后门的情况下可以从cc提取出mm；
  • 模棱两可（equivocality）即在知道某个后门的情况下根据m,r,m′≠mm, r, m' \ne m可以计算出r′r'使得cc是m′m'的承诺，让接收方Open时由c=Commit(m,r)c=\rm{Commit}(m, r)接受m′m'。

首先说一下这个后门（Trapdoor），其实可以看成是某个私钥，即会有一个生成函数KeyGen→(pk,td)\rm{KeyGen} \rightarrow (pk, td)生成一对公私钥，这个私钥tdtd可以看作是一个后门，上面说的Commit\rm{Commit}和Open\rm{Open}都会输入公钥pkpk并使用pkpk进行承诺和承诺打开，即应该写为Commitpk(m,r)\rm{Commit}_{pk}(m, r)和Openpk(c,m,d)\rm{Open}_{pk}(c, m, d)。咋一看留个后门好像会影响安全性，但其实在UCCom中KeyGen\rm{KeyGen}是由一个可信第三方调用的，所以承诺方和接收方都不知道tdtd，而tdtd也并不能在多项式时间内被计算出来。由于翻了好几篇论文都没有找到准确的形式化定义，所以下面我就自己编几个了（以后找到的话再补，留坑）：

  • 密钥生成：KeyGen(1k)→(pk,td)\rm{KeyGen}(1^k) \rightarrow (pk, td)，这里的1k1^k是安全参数；
  • 提取：(c,d)←Commitpk(m,r)(c, d) \leftarrow \rm{Commit_{pk}(m, r)}，则Extratd(c)→m\rm{Extra_{td}(c)} \rightarrow m；
  • 模棱两可：(c,d)←Commitpk(m,r)(c, d) \leftarrow \rm{Commit_{pk}(m, r)}，给定m′≠mm' \ne m，则Equivtd(m,r,m′)→(r′,d′)\rm{Equiv_{td}(m, r, m')} \rightarrow (r', d')，使得(c,d′)←Commitpk(m′,r′)(c, d') \leftarrow \rm{Commit}_{pk}(m', r')且Open(c,m′,d′)=Accept\rm{Open}(c, m', d')=\rm{Accept}。（PS：其实很多文章都是说输出r′r'的，不过套我这上一节的定义的话这里是d′d'，感觉输出d′d'更加广义，输出r′r'是d′=r′d'=r'时的一种特殊情况）。

上面也说了，tdtd需要“不能在多项式时间内被计算出来”，也就是Unbounded的攻击者其实是可以计算出tdtd的，而很明显Extractability和Hiding是冲突的，Equivocality和Binding是冲突的。如果存在提取的后门的话，Unbounded的攻击者就可算出这个后门，然后攻破Hiding属性；同样如果存在模棱两可的后门的话，Unbounded的攻击者就可算出这个后门然后攻破Binding属性。所以若Perfectly Binding则没有Equivocality；若Perfectly Hiding则没有Extractability。

更进一步，其实是：有了Perfectly Binding才有Extractability；有了Perfectly Hiding才有Equivocality。简单来说，反证法：如果存在m′≠mm' \ne m，使得Commitpk(m,r)=Commitpk(m′,r′)\rm{Commit}_{pk}(m, r)=\rm{Commit}_{pk}(m', r')的话，Extratd(c)\rm{Extra_{td}(c)}出来就有mm和m′m'两种可能，而且不能知道哪一个才是真正的消息，所以就不能提取了，所以要能提取则必不存在这样的m′≠mm' \ne m，即Perfectly Binding；如果存在m′≠mm' \ne m，使得{Commitpk(m,R)}≠{Commitpk(m′,R)}\{\rm{Commit}_{pk}(m, \mathcal{R})\} \neq \{\rm{Commit}_{pk}(m', \mathcal{R})\}，则存在某个cc落在其中一个集合中且不落在另一个集合中，不妨设c=Commitpk(m,r)c = \rm{Commit}_{pk}(m, r)（即c∈{Commitpk(m,R)}c \in \{\rm{Commit}_{pk}(m, \mathcal{R})\}且c∉{Commitpk(m′,R)}c \notin \{\rm{Commit}_{pk}(m', \mathcal{R})\}），则对于m′m'，不存在r′∈Rr' \in \mathcal{R}使得Commitpk(m,r)=Commitpk(m′,r′)\rm{Commit}_{pk}(m, r)=\rm{Commit}_{pk}(m', r')，也就不能模棱两可了，所以要能模棱两可则不存在这样的m′≠mm' \ne m，即Perfectly Hiding。

从函数性质的角度看·

上面的定义始终是个定义，直接从定义入手构造一个Commitment的话似乎有点难，所以看看从映射（或者说函数性质，比如单射、满射）上出发会怎么样，即看看要满足Binding和Hiding属性需要满足怎样的函数性质。

单射->Perfectly Binding？·

看一下Binding的定义，“不存在m′≠mm' \ne m，使得Commit(m,r)=Commit(m′,r′)\rm{Commit}(m, r)=\rm{Commit}(m', r')”，换一种方式写就是“∀m,m′∈M,m′≠m⇒Commit(m,r)≠Commit(m′,r′)\forall m,m' \in \mathcal{M}, m' \ne m \Rightarrow \rm{Commit}(m, r) \ne \rm{Commit}(m', r')”，即单射的定义？（上面提了这好像不是Binding的充要条件，但至少是个必要条件，即要Perfectly Binding的话至少要符合这个条件）

不同点在于Commit\rm{Commit}的输入有两个，这可以直接把输入看作一个元组（Tuple），那就是单输入了，或者可以换个看法，把Commit\rm{Commit}看成一个函数簇，不同的rr即从这个函数簇中选出不同的Commitr\rm{Commit}_r，如果可以构造出每个Commitr(m)\rm{Commit}_r(m)是单射的，而且每个{Commitr(M)}\{\rm{Commit}_r(\mathcal{M})\}不相交（也就是一个划分），即可以构造出单射的Commit(m,r)\rm{Commit}(m, r)。形式化：

  • ∀r,∀m,m′∈M,m≠m′⇒Commitr(m)≠Commitr(m′)\forall r, \forall m, m' \in \mathcal{M}, m \ne m' \Rightarrow \rm{Commit}_r(m) \ne \rm{Commit}_r(m')；
  • $\forall r, r’ \in \mathcal{R}, r \ne r’ \Rightarrow {\rm{Commit_r(\mathcal{M})}} \cap {\rm{Commit_{r’}(\mathcal{M})}} = \empty $。

简单证明一下，第二点可以推出，若有Commit(m,r)=Commit(m′,r′)\rm{Commit}(m, r)=\rm{Commit}(m', r')，由于两个集合无交集，则r=r′r=r'，也即只能Commit(m,r)=Commit(m′,r)\rm{Commit}(m, r)=\rm{Commit}(m', r)；第一点把rr移回括号中，推出若Commit(m,r)=Commit(m′,r)\rm{Commit}(m, r)=\rm{Commit}(m', r)，则m=m′m=m'，也即只能Commit(m,r)=Commit(m,r)\rm{Commit}(m, r)=\rm{Commit}(m, r)。综上，对于所有m,m′≠m∈Mm, m' \ne m \in \mathcal{M}，不存在r,r′∈Rr, r' \in \mathcal{R}，使得Commit(m,r)=Commit(m′,r′)\rm{Commit}(m, r)=\rm{Commit}(m', r')。

（PS：当然，如果看成是Commitm\rm{Commit}_m的函数簇也是可以的，反正最后给不同的(m,r)(m,r)可以射到不同的点就好了。另挖坑有空补个图）

用函数簇定义的话，首先第一点的单射函数是比较容易构造的，比较麻烦的是第二点的划分。对于划分，如果是Commitr\rm{Commit}_r的函数簇的话，可以用一个“绑定”的操作绑定rr，即不能让承诺方选择其他的r′r'，假设这个操作是Bind(r)\rm{Bind}(r)的话，从定义上只需要Bind\rm{Bind}是一个单射函数就可以了。类似地如果是Commitm\rm{Commit}_m的话，就是Bind(m)\rm{Bind}(m)。假设F∗F_*是一个单射函数（准确地，为了有Hiding，还应该是一个One-way Function，Bind(r)\rm{Bind}(r)同），则可以粗略地构造出一种Perfectly Binding的协议：

Committer(m)              Receiverr←$Rc=Fr(m)b=Bind(r)⟶b, c⋮⟶m, rb=?Bind(r)c=?Fr(m)\begin{array}{|c|} \hline \\ \begin{array}{ccc} \mathrm{Committer}(m) & \ \ \ \ \ \ \ \ \ \ \ \ \ \ & \mathrm{Receiver} \\ \begin{array}{l} r \overset{\$}{\leftarrow} \mathcal{R} \\ c = F_r(m) \\ b = \rm{Bind}(r) \end{array} & & \\ & \overset{b,\ c}{\longrightarrow} & \\ \vdots & & \\ & \overset{m,\ r}{\longrightarrow} & \\ & & \begin{array}{l} b \overset{?}{=} \rm{Bind}(r) \\ c \overset{?}{=} F_r(m) \end{array} \\ \end{array} \\ \hline \end{array}

证明也挺直观，Bind\rm{Bind}是单射的所以承诺方不能用别的Fr′F_{r'}，FrF_r是单射的所以承诺方也不能用别的m′m'，具体证明略。以上换成FmF_m和Bind(m)\rm{Bind}(m)也是类似的，就不多画一个图了，而且感觉上Bind(r)\rm{Bind}(r)好像会更合理一点。

满射->Perfect Hiding？·

同样，看一下Hiding的定义，“对于所有m′≠mm' \ne m，都有{Commit(m,R)}≡{Commit(m′,R)}\{\rm{Commit}(m, \mathcal{R})\} \equiv \{\rm{Commit}(m', \mathcal{R})\}”，也同样把Commit\rm{Commit}看成一个函数簇，每个mm取出一个函数Commitm(r)\rm{Commit}_m(r)，设{Commit(M,R)}=C\{\rm{Commit(\mathcal{M}, \mathcal{R})}\} = \mathcal{C}，即C\mathcal{C}是所有承诺cc的集合，若对于所有的m∈Mm \in \mathcal{M}都有Commitm(r)\rm{Commit}_m(r)满射到C\mathcal{C}，不就很自然地对于所有m′≠mm' \ne m，有{Commit(m,R)}≡{Commit(m′,R)}\{\rm{Commit}(m, \mathcal{R})\} \equiv \{\rm{Commit}(m', \mathcal{R})\}？形式化：

  • ∀m∈M,{Commitm(R)}=C\forall m \in \mathcal{M}, \{\rm{Commit_m(\mathcal{R})}\} = \mathcal{C}。

或者更准确地：

  • ∀m∈M,∀c∈C,∃r∈R,s.t.Commitm(r)=c\forall m \in \mathcal{M}, \forall c \in \mathcal{C}, \exists r \in \mathcal{R}, s.t. \rm{Commit}_m(r)=c。

显然对于所有mi,mj∈Mm_i, m_j \in \mathcal{M}，都有{Commitmi(R)}={Commitmj(R)}=C\{\rm{Commit_{m_i}(\mathcal{R})}\} = \{\rm{Commit_{m_j}(\mathcal{R})}\} = \mathcal{C}，自然就是Perfectly hiding了。更进一步，还可以证明只有符合这个性质的才能做到Perfect Hiding：假设存在某个mm使得Commitm\rm{Commit}_{m}不是满射到C\mathcal{C}，则存在某个m′∈Mm' \in \mathcal{M}和r′∈Rr' \in \mathcal{R}，使得Commitm′(r′)=c′\rm{Commit}_{m'}(r')=c'且c′∉{Commitm(R)}c' \notin \{\rm{Commit}_m(\mathcal{R})\}（即必存在c′∈(C−{Commitm(R)})⊆Cc' \in (\mathcal{C} - \{\rm{Commit}_m(\mathcal{R})\}) \subseteq \mathcal{C} ，这个c′c'就是Commitm\rm{Commit}_m没射到的那个），则c′∈({Commitm′(R)}−{Commitm(R)})≠∅c' \in (\{\rm{Commit}_{m'}(\mathcal{R})\} - \{\rm{Commit}_m(\mathcal{R})\}) \ne \empty，也即{Commit(m′,R)}≠{Commit(m,R)}\{\rm{Commit}(m', \mathcal{R})\} \ne \{\rm{Commit}(m, \mathcal{R})\}，和Perfect Hiding的定义冲突。

所以如果存在这样的函数簇的话，Perfect Hiding的Commitment（好像）也挺好构造。假设FF就是这样的函数簇，粗略地构造个Perfect Hiding的协议：

Committer(m)              Receiverr←$Rc=Fm(r)⟶c⋮⟶m, rc=?Fm(r)\begin{array}{|c|} \hline \\ \begin{array}{ccc} \mathrm{Committer}(m) & \ \ \ \ \ \ \ \ \ \ \ \ \ \ & \mathrm{Receiver} \\ \begin{array}{l} r \overset{\$}{\leftarrow} \mathcal{R} \\ c = F_m(r) \\ \end{array} & & \\ & \overset{c}{\longrightarrow} & \\ \vdots & & \\ & \overset{m,\ r}{\longrightarrow} & \\ & & \begin{array}{l} c \overset{?}{=} F_m(r) \end{array} \\ \end{array} \\ \hline \end{array}

Hiding的证明在上面分析的基础上其实是显然的，但是这时Binding就没这么显然了（或者说其实这样构造的话根本没有Binding？）

另外，根据上一章的结论，也可推出Equivocality，证明类似，略。

OWF->Computational？·

OWF即上面提到过的One-way Function，简单来说是一类正向求解容易，逆向求解困难的函数，准确点说则是：在多项式时间内求出伪逆（Pseudo-inverse）的概率可以忽略（换句话说就是计算上不可能），以下摘抄了wiki上的定义。

简单论述以下，现在假设Commitr∗\rm{Commit}_{r^*}是一个OWF，假设攻击者可以攻破Computational Hiding，即可以算出Commitr(m)\rm{Commit}_r(m)的逆（伪逆包含了逆），也就攻破了这个OWF，由于OWF不能被Computational地被攻破，所以Hiding也不能被Computational地被攻破（一种规约，但攻击者其实只用算出mm而不用算出rr，好像不好证）。

类似地，假设Commitm∗\rm{Commit_{m^*}}是一个OWF，假设攻击者可以攻破Computational Binding，则给定c=Commitm(r)c=\rm{Commit_m(r)}和m′≠mm' \ne m，攻击者可以找到一个r′r'，使得Commitm′(r′)=c\rm{Commit_{m'}(r')} = c，即找到Commitm′\rm{Commit}_{m'}的一个逆，从而攻破OWF。不过由于攻击者可以知道mm和rr，也就是多了额外的信息，所以似乎是还不能直接规约到OWF，这里先留个坑（逃

而且用OWF的话还有个问题是，原项的取值需要足够的多，不然若攻击者可以遍历所有原项，就自然可以找到逆了，所以像bit Commitment就不能用OWF了（应该）。

双射TF->Extractability/Equivocality？·

这里的TF指后门函数（Trapdoor Function），即在OWF的基础上多了个后门，在知道后门的情况下可以有效地求解出逆（或伪逆），大概意思是（符号我乱取的- -）：

  • (pk,td)←TFGen(1k)(pk, td) \leftarrow \rm{TFGen}(1^k)；
  • y=TFInverttd(TFpk(x))y = \rm{TFInvert}_{td}(\rm{TF}_{pk}(x))，其中TFpk(x)=TFpk(y)\rm{TF}_{pk}(x)=\rm{TF}_{pk}(y) 。

结合上一节，如果上一节能证的话（如果），若Commitr∗(m)\rm{Commit}_{r^*}(m)是TF的话，则可通过后门提取mm；若Commitm∗(r)\rm{Commit_{m^*}}(r)是TF的话，则可根据Commitm′(r′)=Commitm(r)\rm{Commit}_{m'}(r')=\rm{Commit}_m(r)提取r′r'。

其中，需要TF是双射是因为，提取是需要提取出的是真正的逆而不是伪逆，所以需要单射；模棱两可时需要Commitm(r)\rm{Commit}_m(r)能被Commitm′\rm{Commit}_{m'}映射到，所以需要满射。

当然，目前只是一个想法，有可能下一版更新就删掉了（逃

栗子·

我瞎编的栗子·

根据上面的思路，编了两个栗子：

Perfect Hinding 的栗子·

Committer(m)              Receiverr←$Rc=Perm(TFpk(r))⟶c⋮⟶m, rc=?Perm(TFpk(r))\begin{array}{|c|} \hline \\ \begin{array}{ccc} \mathrm{Committer}(m) & \ \ \ \ \ \ \ \ \ \ \ \ \ \ & \mathrm{Receiver} \\ \begin{array}{l} r \overset{\$}{\leftarrow} \mathcal{R} \\ c = \rm{Per}_m( \rm{TF}_{pk}(r) ) \\ \end{array} & & \\ & \overset{c}{\longrightarrow} & \\ \vdots & & \\ & \overset{m,\ r}{\longrightarrow} & \\ & & \begin{array}{l} c \overset{?}{=} \rm{Per}_m( \rm{TF}_{pk}(r) ) \end{array} \\ \end{array} \\ \hline \end{array}

其中，TFpk:R→T\rm{TF}_{pk}: \mathcal{R} \to \mathcal{T}是一个双射的Trapdoor Function；Per\rm{Per}是一个排列（Permutation）簇（或者说一个双射函数，也行？），由m∗m^*选择出一个排列Perm∗:T→C\rm{Per}_{m^*}: \mathcal{T} \to \mathcal{C}，假设存在有效算法PerInvertm∗\rm{PerInvert}_{m^*}可求出这个排列的逆（排列是双射，所以存在逆）。下面简要证明：

  • Perfect Hiding：简单转换一下可得Commit(m,R)=Perm(TFpk(R))\rm{Commit}(m, \mathcal{R})=\rm{Per}_m( \rm{TF}_{pk}(\mathcal{R}) )，由于TFpk\rm{TF}_{pk}双射，即Commit(m,R)=Perm(T)\rm{Commit}(m, \mathcal{R})=\rm{Per}_m(\mathcal{T} )，由于排列肯定双射，即Commit(m,R)=C\rm{Commit}(m, \mathcal{R})=\mathcal{C}，所以对于所有m′≠mm' \ne m，都有{Commit(m,R)}≡{Commit(m′,R)}=C\{\rm{Commit}(m, \mathcal{R})\} \equiv \{\rm{Commit}(m', \mathcal{R})\} = \mathcal{C}；
  • Computational Binding：假设给定(m,r)(m, r)和足够随机（反正m′m'攻击者不可控，应该也合理？）的m′≠mm' \ne m，攻击者可以找到r′r'使得Commit(m′,r′)=Commit(m,r)\rm{Commit}(m', r')=\rm{Commit(m, r)}，即使得Perm′(TFpk(r′))=Perm(TFpk(r))\rm{Per}_{m'}( \rm{TF}_{pk}(r') ) = \rm{Per}_m( \rm{TF}_{pk}(r) )，即使得r′=TFpk−1(Perm′−1(Perm(TFpk(r))))r' = \rm{TF}_{pk}^{-1}( \rm{Per}_{m'}^{-1}( \rm{Per}_m( \rm{TF}_{pk}(r) )))，由于m′m'足够随机，即Perm′−1(Perm(TFpk(r)))\rm{Per}_{m'}^{-1}( \rm{Per}_m( \rm{TF}_{pk}(r) ))足够随机，攻击者在不知道trapdoor的情况下对一个Trapdoor Function求一个足够随机的数的逆，计算上不可能；
  • Equivocality：与Binding的证明类似，但模拟者可以知道tdtd，也即可以通过r′=TFInverttd−1(PerInvertm′(Perm(TFpk(r))))r' = \rm{TFInvert}_{td}^{-1}( \rm{PerInvert}_{m'}( \rm{Per}_m( \rm{TF}_{pk}(r) )) )求得r′r'实现模棱两可。由于TF\rm{TF}是双射的，所以总能求得这样的r′r'。

（PS：不好实例化。。。）

Perfect Binding的栗子·

Committer(m)              Receiverr←$Rc=m⨁rb=Bindpk(r)⟶b, c⋮⟶m, rb=?Bindpk(r)c=?m⨁r\begin{array}{|c|} \hline \\ \begin{array}{ccc} \mathrm{Committer}(m) & \ \ \ \ \ \ \ \ \ \ \ \ \ \ & \mathrm{Receiver} \\ \begin{array}{l} r \overset{\$}{\leftarrow} \mathcal{R} \\ c = m \bigoplus r \\ b = \rm{Bind}_{pk}( r ) \end{array} & & \\ & \overset{b,\ c}{\longrightarrow} & \\ \vdots & & \\ & \overset{m,\ r}{\longrightarrow} & \\ & & \begin{array}{l} b \overset{?}{=} \rm{Bind}_{pk}( r ) \\ c \overset{?}{=} m \bigoplus r \end{array} \\ \end{array} \\ \hline \end{array}

其中，⨁\bigoplus是异或（或者某种pad？）；Bindpk\rm{Bind}_{pk}是单射的Trapdoor Function，存在BindInverttd\rm{BindInvert}_{td}高效求逆。下面简要证明：

  • Perfect Binding：由于Bindpk\rm{Bind}_{pk}单射，Bindpk(r)=Bindpk(r′)⇒r=r′\rm{Bind}_{pk}(r) = \rm{Bind}_{pk}(r') \Rightarrow r = r'，所以不存在r′≠rr' \ne r，使得b=?Bindpk(r)b \overset{?}{=} \rm{Bind}_{pk}( r )通过；假设存在m′≠mm' \ne m使得c=m⨁r=m′⨁rc = m \bigoplus r = m' \bigoplus r，则m=m′=c⨁rm = m' = c \bigoplus r，矛盾，所以不存在m′≠mm' \ne m使得c=?m⨁rc \overset{?}{=} m \bigoplus r通过；综上，不存在m′≠mm' \ne m使得Open时输出Accept。
  • Computational Hiding：假设攻击者可以根据bb和cc算出mm，则可以算出r=c⨁mr = c \bigoplus m从而在没有tdtd的情况下根据b=Bindpk(r)b = \rm{Bind}_{pk}( r )算出rr，规约到TF上计算不可能；
  • Extractability：给定bb和cc，模拟这可以使用tdtd计算出r=BindInverttd(b)r = \rm{BindInvert}_{td}(b)，然后m=c⨁rm = c \bigoplus r。

比较著名的栗子·

Perfect Hiding的Pedersen Commitment：

Perfect Binding的ElGamal Commitment：

参考·

[CF01] Canetti R, Fischlin M. Universally composable commitments[C]//Annual International Cryptology Conference. Springer, Berlin, Heidelberg, 2001: 19-40.

[DN02] Damgård I, Nielsen J B. Perfect hiding and perfect binding universally composable commitment schemes with constant expansion factor[C]//Annual International Cryptology Conference. Springer, Berlin, Heidelberg, 2002: 581-596.

… …