事情是这样的,上次写的笔记内容被我用在某个期末作业上了,由于是写作业上的所以表述会正规一点,而且写的时候也加了新东西,所以可以再水一篇贴了。

正文

简介

承诺方案(Commitment Scheme)如其名,就是在模拟一个“作出承诺”和“兑现承诺”的过程,但和现实的承诺不同,密码学中的承诺通常是在承诺发送者不会改变某个值,然后在兑现承诺的时候把这个值发送给接收者,接收者收到后验证这个值是否真的没被改变。

承诺(Commitment)的概念最早由[B83]提出,而较正式的承诺方案则在[BCC88]提出,[BCC88]提出的是单比特的承诺方案(Bit Commitment Scheme),目前承诺方案被广泛应用于抛币协议、零知识证明、安全多方计算等协议中,在[C01]提出通用可组合框架(Universally Composable,下简称UC)以后,这些协议相继提出了UC模型下的版本,承诺方案也不例外,最先提出UC模型下承诺方案的是[CF01],目前(我所了解的)被认为最快的且在UC模型下、不使用Random Oracle的、可承诺任意比特的承诺方案是[Lin11]提出的承诺方案。

定义

承诺方案有两个参与者:发送方(Sender)和接收方(Receiver);承诺方案还有两个阶段:承诺(Commit)和打开(Open)。

在承诺阶段中,发送方承诺某个不会改变的值mm,利用mm和随机性rr计算并发送承诺值cc给接收方。在打开阶段中,发送方须发送值mm和一个用于辅助打开承诺的打开值(Opening Value)dd给接收方,接收方利用收到的mmddcc验证(Verify)mm是否没被发送方或其他攻击者更改,若验证通过则接受(Accept),否则拒绝(Reject)。大概过程见下图:

Commit:Open:Sender(m)              ReceiverCom(m,r)(c,d)cm, dVerify(c,m,d)Accept/Reject\begin{array}{|lc|} \hline \\ \begin{array}{c} \rm{Commit: } \\ \\ \\ \\ \rm{Open: } \end{array} & \begin{array}{lcl} \mathrm{Sender}(m) & \ \ \ \ \ \ \ \ \ \ \ \ \ \ & \mathrm{Receiver} \\ \begin{array}{l} \rm{Com}(m, r) \rightarrow (c, d) \end{array} & & \\ & \overset{c}{\longrightarrow} & \\ \vdots & & \\ & \overset{m,\ d}{\longrightarrow} & \\ & & \begin{array}{l} \rm{Verify(c, m, d)} \rightarrow \text{Accept/Reject} \end{array} \\ \end{array} \\ \hline \end{array}

作为一个协议,首先要拥有正确性,一个是取值范围的问题:假设消息的取值范围是M\mathcal{M}、随机数的取值范围是R\mathcal{R}、承诺值的范围是C\mathcal{C}、打开值得范围是D\mathcal{D},“$\overset{\$}{\leftarrow}”表示随机选取,则会有:

mM;   rR;Com(m,r)(c,d)cC;   dD;\begin{array}{ccc} \begin{array}{l} m \in \mathcal{M} \rm{;} \ \ \ r \in \mathcal{R} \rm{;} \\ \rm{Com}(m, r) \rightarrow (c, d) \end{array} & \Rightarrow & \begin{array}{l} c \in \mathcal{C} \rm{;} \ \ \ d \in \mathcal{D} \rm{;} \\ \end{array} \end{array}

另一个是,若承诺值和打开值是按正确流程生成的,则一定会通过验证:

mM;   rR;Com(m,r)(c,d)Verify(c,m,d)=Accept\begin{array}{ccc} \begin{array}{l} m \in \mathcal{M} \rm{;} \ \ \ r \in \mathcal{R} \rm{;} \\ \rm{Com}(m, r) \rightarrow (c, d) \end{array} & \Rightarrow & \begin{array}{l} \rm{Verify(c, m, d)} = \text{Accept} \end{array} \end{array}

安全属性

除了上面的流程,承诺方案还需要满足两个安全属性:绑定(Binding)和隐藏(Hiding),很遗憾在我目前看到的论文里都没有这两个安全属性的形式化定义,大多论文都选择使用自然语言去定义,目前看到最多的定义如下:

  • 绑定属性:定义一:承诺方不能用两个不同的mmm \ne m'承诺出同样的承诺值cc;定义二:承诺方生成的承诺值cc在打开时不能被两个不同的mmm \ne m'通过验证。
  • 隐藏属性:接收方不能根据接收到的承诺值cc恢复出mm

显然,绑定针对的是不诚实的承诺方,隐藏则是不诚实的接收方。

对绑定属性的一点看法

绑定属性的定义会有点歧义,在目前的论文里,定义一和定义二都有出现,但在我看来,定义二会更准确,因为定义一的安全性并不用考虑打开阶段。而且根据承诺方案的正确性,若有两个不同的mmm \ne m'承诺出同样的承诺值cc,那么cc也应该要被mmmm'通过验证,也即其逆否命题也成立:若一个承诺值cc不能被两个不同的mmm \ne m'通过验证,则不会有两个不同的mmm \ne m'承诺出同样的承诺值cc,符合定义二可推出符合定义一(② \Rightarrow ①)。

另外,感觉上如果只按照定义一实现绑定的话,可以在打开阶段设置后门,而达到设计虽符合了安全定义但是却不安全的协议。举个较极端的例子,假设我设计一个符合上述绑定属性定义一和隐藏属性的承诺方案(简单地用一个加密函数或者单向函数作Com\rm{Com}即可符合),但是在打开阶段的验证函数无论输入是什么都输出接受,即Verify(c,m,d)alwaysAccept\rm{Verify(c, m, d)} \overset{\text{always}}{\rightarrow} \text{Accept},根据加密函数或者单向函数性质,这个承诺方案都满足绑定属性的定义一和隐藏属性的定义,但显然这不是一个可以使用的承诺方案,因为无论承诺方承诺什么,接收方都只能接受。

上述的绑定属性定义一的出现,我认为是历史原因导致的。以往的承诺方案其实并不复杂,通常是发送方使用加密函数或者单向函数对信息mm进行加密或映射,在打开时接收方使用接收到的mm进行重加密或重映射,然后对比得到的结果是否跟cc一致,若一致则接受,否则拒绝。在这样的构造下,承诺阶段的操作与打开阶段的几乎一样,没有有两个不同的信息承诺出相同的承诺值的话自然也不会有一个承诺值可以被两个不同的信息通过验证,换句话说,在这种情况下,符合定义一可以推出符合定义二(② \Leftrightarrow ①)。

形式化定义的尝试

上面说了,目前我所看的论文里都没有出现绑定和隐藏这两个安全属性的形式化定义,但是根据自然语言的定义给出形式化定义其实是可行的,所以下面我就进行一番尝试,给出针对这两个安全属性的攻击者的优势(Advantage),可以理解为攻击者攻击成功的概率。假设消息的取值范围是M\mathcal{M}、随机数的取值范围是R\mathcal{R}、承诺值的范围是C\mathcal{C}、打开值得范围是D\mathcal{D},“ $\overset{\$}{\leftarrow} ”表示随机选取。

不诚实得发送者AS\text{A}_\text{S}攻破绑定属性的优势可以表示为:

AdvBinding(AS)=Pr[Verify(c,m,d)=AcceptVerify(c,m,d)=Accept:(c,m,m,d,d)AS;m,mM;   mm;d,dD;  cC]\text{Adv}_\text{Binding}(A_S) = \text{Pr}\begin{bmatrix} \begin{array}{ccc} \begin{array}{l} \rm{Verify(c, m, d)} = \text{Accept} \\ \rm{Verify(c, m', d')} = \text{Accept} \end{array} & \rm{:} & \begin{array}{l} (c, m, m', d, d') \leftarrow \text{A}_\text{S} \rm{;} \\ m, m' \in \mathcal{M} \rm{;} \ \ \ m \ne m' \rm{;} \\ d, d' \in \mathcal{D} \rm{;} \ \ c \in \mathcal{C} \end{array} \end{array} \end{bmatrix}

不诚实的接收者AR\text{A}_\text{R}攻破隐藏属性的优势可以表示为:

AdvHiding(AR)=Pr[m=m:m$M; r$R;(c,d)Com(m,r);mAR(c)]\text{Adv}_\text{Hiding}(\text{A}_\text{R}) = \text{Pr}\begin{bmatrix} \begin{array}{ccc} \begin{array}{l} m = m' \end{array} & \rm{:} & \begin{array}{l} m \overset{\$}{\leftarrow} \mathcal{M} \rm{;} \ r \overset{\$}{\leftarrow} \mathcal{R} \rm{;} \\ (c, d) \leftarrow \rm{Com}(m, r) \rm{;} \\ m' \leftarrow \text{A}_\text{R}(c) \end{array} \end{array} \end{bmatrix}

除了上述我编的定义,记cm,rc_{m, r}Com(m,r)\rm{Com}(m, r)得到的承诺值,目前还流传着其他的定义,常见的如(这里为了与上面的表述相一致,在不改变意思的情况下做了修改):

  • 绑定属性(定义一):m,mM, r,rR, mmcm,rcm,r\forall m,m' \in \mathcal{M},\ \forall r,r' \in \mathcal{R},\ m' \ne m \Rightarrow c_{m, r} \ne c_{m', r'}。按我的理解,还可以被写作:

    AdvBinding()=Pr[c=c:mm$M;  r,r$R;(c,d)Com(m,r);(c,d)Com(m,r)]\text{Adv}^{'}_\text{Binding}() = \text{Pr}\begin{bmatrix} \begin{array}{ccc} \begin{array}{l} c = c' \end{array} & \rm{:} & \begin{array}{l} m \ne m' \overset{\$}{\leftarrow} \mathcal{M} \rm{;} \ \ r, r' \overset{\$}{\leftarrow} \mathcal{R} \rm{;} \\ (c, d) \leftarrow \rm{Com}(m, r) \rm{;} \\ (c', d') \leftarrow \rm{Com}(m', r') \end{array} \end{array} \end{bmatrix}

  • 隐藏属性:通常会被简化表述为m,mM, {cm,R}={cm,R}\forall m,m' \in \mathcal{M},\ \{c_{m, \mathcal{R}}\} = \{c_{m', \mathcal{R}}\}。按我的理解,还可以被写作(在AdvHiding(AR)=0\text{Adv}_\text{Hiding}(\text{A}_\text{R})=0时等号成立):

    AdvHiding(AR)AdvHiding()=Pr[CmCm:mm$M;Cm={c  (c,d)Com(m,r); rR}Cm={c  (c,d)Com(m,r); rR}]\text{Adv}_\text{Hiding}(\text{A}_\text{R}) \le \text{Adv}^{'}_\text{Hiding}() = \text{Pr}\begin{bmatrix} \begin{array}{ccc} \begin{array}{l} \mathcal{C}_m \ne \mathcal{C}_{m'} \end{array} & \rm{:} & \begin{array}{l} m \ne m' \overset{\$}{\leftarrow} \mathcal{M} \rm{;} \\ \mathcal{C}_m = \{c\ |\ (c, d) \leftarrow \rm{Com}(m, r)\rm{;}\ r \in \mathcal{R} \} \\ \mathcal{C}_{m'} = \{c'\ |\ (c', d') \leftarrow \rm{Com}(m', r')\rm{;}\ r' \in \mathcal{R} \} \end{array} \end{array} \end{bmatrix}

这两个定义的好处是并不用考虑攻击者,即只要构造符合某种属性的Com\rm{Com}就可以构造出安全的承诺方案,而且使用在各种证明中都会更简洁,但遗憾的是目前并没有找到绑定属性中定义二的类似表述。AdvBinding()\text{Adv}^{'}_\text{Binding}()的表述很直观,几乎只是大白话的翻译。\rm{Adv}^{'}_\rm{Hiding}()的大概意思是,若攻击者可以找到mmm \ne m'使得CmCm\mathcal{C}_m \ne \mathcal{C}_{m'},那么就会存在r,rRr, r' \in \mathcal{R},使得cm,rc_{m, r}cm,rc_{m', r'}可以区分mmmm'AdvHiding()=0\text{Adv}^{'}_\text{Hiding}()=0时,M\mathcal{M}中的每个mm承诺出来的承诺值分布都一样,那么攻击者拿到任何一个cCc \in \mathcal{C}也不会知道是由哪一个或者哪几个mMm \in \mathcal{M}产生的,自然也无法恢复出消息mm,也即AdvHiding(AR)=0\text{Adv}_\text{Hiding}(\text{A}_\text{R})=0

也许还可以写出另一个区分性的版本:

AdvHiding(AR)AdvHiding(AR)=Pr[b=b:m0m1AR();b${0,1}; r$R;(c,d)Com(mb,r);bAROra()(c)]12\text{Adv}_\text{Hiding}(\text{A}_\text{R}) \le \text{Adv}^{''}_\text{Hiding}(\text{A}_\text{R}) = \begin{vmatrix} Pr\begin{bmatrix} \begin{array}{ccc} \begin{array}{l} b = b^* \end{array} & \rm{:} & \begin{array}{l} m_0 \ne m_1 \leftarrow \text{A}_\text{R}() \rm{;} \\ b^* \overset{\$}{\leftarrow} \{0, 1\} \rm{;} \ r \overset{\$}{\leftarrow} \mathcal{R} \rm{;} \\ (c^*, d) \leftarrow \rm{Com}(m_{b^*}, r) \rm{;} \\ b \leftarrow \text{A}_\text{R}^{\rm{Ora}(·)}(c^*) \end{array} \end{array} \end{bmatrix} - \frac{1}{2} \end{vmatrix}

其中

Ora(m):={r$R; (c,d)Com(m,r);Output: (c,d)}\rm{Ora}(m) := \begin{Bmatrix} \begin{array}{l} r \overset{\$}{\leftarrow} \mathcal{R} \rm{;} \ (c, d) \leftarrow \rm{Com}(m, r) \rm{;} \\ \text{Output: } (c, d) \end{array} \end{Bmatrix}

完美安全和计算上安全

上述的绑定和隐藏属性其实还各自分两个安全等级:完美(Perfect)安全和计算上(Computational)安全。所谓完美安全,就是即使是有无限能力(Unbounding)的攻击者也不可能攻破这个安全属性;所谓计算上安全,就是攻击者能攻破该属性的概率可以被忽略,或者说攻击者在多项式时间内不可能攻破。

有了上面的几个定义,这两个安全等级就很好解释了:

  • 完美绑定(Perfectly Binding):AdvBinding(AS)=0\text{Adv}_\text{Binding}(\text{A}_\text{S}) = 0,或者至少需要AdvBinding()=0\text{Adv}^{'}_\text{Binding}() = 0,因为前面说了定义二定义一\rm{定义二} \Rightarrow \rm{定义一},定义一是定义二的一个必然条件;
  • 计算上绑定(Computationally Binding):AdvBinding(AS)=negl\text{Adv}_\text{Binding}(\text{A}_\text{S}) = \rm{negl},或者至少需要AdvBinding()=negl\text{Adv}^{'}_\text{Binding}() = \rm{negl},其中negl\rm{negl}为可忽略(Negligible);
  • 完美隐藏(Perfectly Hiding):AdvHiding(AR)=0\text{Adv}_\text{Hiding}(\text{A}_\text{R}) = 0,或者AdvHiding()=0\text{Adv}^{'}_\text{Hiding}() = 0
  • 计算上隐藏(Computationally Hiding):AdvHiding(AR)=negl\text{Adv}_\text{Hiding}(\text{A}_\text{R}) = \rm{negl},或者AdvHiding()=negl\text{Adv}^{'}_\text{Hiding}() = \rm{negl}

明显,完美安全的安全性比计算上安全的安全性高,但坏消息是,不能同时实现完美绑定和完美隐藏,粗略的论证如下:假设AdvBinding()=0\text{Adv}^{'}_\text{Binding}() = 0AdvHiding()=0\text{Adv}^{'}_\text{Hiding}() = 0,首先根据AdvHiding()=0\text{Adv}^{'}_\text{Hiding}() = 0会有:

mmM;{c  (c,d)Com(m,r); rR}={c  (c,d)Com(m,r); rR}\forall m \ne m' \in \mathcal{M} \rm{;} \\ \{c\ |\ (c, d) \leftarrow \rm{Com}(m, r)\rm{;}\ r \in \mathcal{R} \} = \{c'\ |\ (c', d') \leftarrow \rm{Com}(m', r')\rm{;}\ r' \in \mathcal{R} \}

由两个集合的相等可以推出:

mmM;  r,rR;s.t.  c=c;  (c,d)Com(m,r);  (c,d)Com(m,r)\forall m \ne m' \in \mathcal{M} \rm{;} \ \ \exist r, r' \in \mathcal{R} \rm{;} \\ s.t.\ \ c = c' \rm{;}\ \ (c, d) \leftarrow \rm{Com}(m, r)\rm{;}\ \ (c', d') \leftarrow \rm{Com}(m', r')

而\rm{Adv}^{'}_\rm{Binding}() = 0会有:

mmM;  r,rR;cc;  (c,d)Com(m,r);  (c,d)Com(m,r)\forall m \ne m' \in \mathcal{M} \rm{;} \ \ \forall r, r' \in \mathcal{R} \rm{;} \\ c \ne c' \rm{;}\ \ (c, d) \leftarrow \rm{Com}(m, r)\rm{;}\ \ (c', d') \leftarrow \rm{Com}(m', r')

两者矛盾,所以AdvBinding()=0\text{Adv}^{'}_\text{Binding}() = 0AdvHiding()=0\text{Adv}^{'}_\text{Hiding}() = 0不能同时成立,完美绑定和完美隐藏不能同时实现。

所以在构造承诺方案时,通常会选择“完美绑定+计算上隐藏”或者“计算上绑定+完美隐藏”的组合,实在没办法的情况下才会选择“计算上绑定+计算上隐藏”的组合。

模棱两可和提取

模棱两可和提取是两个后门属性,常用于构造通用可组合(UC)安全的承诺方案:

  • 模棱两可(Equivocality)属性:指在知道且仅在知道某个后门值时,可以对一个已经对一个消息mm做出的承诺在打开时解释为任意不同消息mm'的承诺,且不被接收方发现,即根据mmM;m \ne m' \in \mathcal{M}\text{;} rR;r \in \mathcal{R}\text{;},可以计算出dDd' \in \mathcal{D},使得Verify(cm,r,m,d)=Accept\text{Verify}(c_{m, r}, m', d') = \text{Accept}
  • 提取(Extractability)属性:指在知道且仅在知道某个后门值时,可以仅根据承诺值cm,c_{m, ·}提取消息mm

由于后门的存在,构造满足模棱两可或提取的承诺方案通常会使用公钥系统,即会有一个密钥生成函数Gen\rm{Gen}生成一个公钥和后门的对(pk,td)(pk, td),在仅知道公钥pkpk的情况下无法(或计算上不能)恢复后门tdtdCom\rm{Com}操作和Verify\rm{Verify}操作均需要使用公钥pkpk,记作Compk\rm{Com}_{pk}Verifypk\rm{Verify}_{pk}

下面说一下形式化定义,同样由于在现有文献中没找到详细的定义,于是就按照自己的理解编一个:

  • 密钥生成:(pk,td)Gen(1κ)(pk, td) \leftarrow \rm{Gen}(1^\kappa),其中1κ1^\kappa为安全系数;
  • 模棱两可:(c,d)Compk(m,r)(c, d) \leftarrow \rm{Com}_{pk}(m, r)mmMm \ne m' \in \mathcal{M}rRr \in \mathcal{R}(c,d)Com(m,r)(c, d) \leftarrow \rm{Com}(m, r),则dEquivtd(m,m,d)d' \leftarrow \rm{Equiv}_{td}(m, m', d),其中dDd' \in \mathcal{D}Verifypk(c,m,d)=Accept\rm{Verify}_{pk}(c, m', d') = \text{Accept},由于不能被接收方发现做了假承诺,还需要rR s.t. Compk(m,r)=(c,d)\exist r' \in \mathcal{R}\ s.t.\ \rm{Com}_{pk}(m', r') = (c, d')(或者说不存在这样的rr'的概率可忽略?又或者存在但是接收方能找到的概率可忽略?);
  • 提取:(c,d)Compk(m,r)(c, d) \leftarrow \rm{Com}_{pk}(m, r)mmMm \ne m' \in \mathcal{M}rRr \in \mathcal{R},则mExtratd(c)m \leftarrow \rm{Extra}_{td}(c)

由于在通用可组合框架中,Equivtd\rm{Equiv}_{td}Extratd\rm{Extra}_{td}都是由模拟者(Simulator)操作的,结合通用可组合框架中的证明套路,还可以借助模拟者的优势给出定义:

  • 模拟者的模棱两可优势:

    AdvEquiv(SS)=Pr[Verifypk(c,m,d)=Accept:cSS(); cC;m$M;dSStd(m)]1negl\text{Adv}_\text{Equiv}(\text{S}_\text{S}) = Pr\begin{bmatrix} \begin{array}{ccc} \begin{array}{l} \rm{Verify}_{pk}(c, m', d') = \text{Accept} \end{array} & \rm{:} & \begin{array}{l} c \leftarrow \text{S}_\text{S}() \rm{;} \ c \in \mathcal{C} \rm{;} \\ m' \overset{\$}{\leftarrow} \mathcal{M} \rm{;} \\ d' \leftarrow \text{S}_\text{S}^{td}(m') \end{array} \end{array} \end{bmatrix} \ge 1 - \rm{negl}

  • 模拟者的提取优势:

    AdvExtra(SR)=Pr[m=m:m$M;  r$R;(c,d)Compk(m,r);mSStd(c)]1negl\text{Adv}_\text{Extra}(\text{S}_\text{R}) = Pr\begin{bmatrix} \begin{array}{ccc} \begin{array}{l} m = m' \end{array} & \rm{:} & \begin{array}{l} m \overset{\$}{\leftarrow} \mathcal{M} \rm{;} \ \ r \overset{\$}{\leftarrow} \mathcal{R} \rm{;} \\ (c, d) \leftarrow \rm{Com}_{pk}(m, r) \rm{;} \\ m' \leftarrow \text{S}_\text{S}^{td}(c) \end{array} \end{array} \end{bmatrix} \ge 1 - \rm{negl}

模棱两可和提取属性的存在直观上好像会分别和前文的绑定属性和隐藏属性相矛盾,从而影响协议的安全性,但其实不然,因为模棱两可和提取均需要知道后门,而在实际的协议设计中,密钥是由一个安全的第三方生成、分发和保管的(如UC框架中的承诺方案),安全第三方并不会泄露后门,而仅知道公钥pkpk的情况下后门无法(或计算上不能)被恢复,所以Equivtd\rm{Equiv}_{td}Extratd\rm{Extra}_{td}方法仅有安全第三方可以使用,但这个第三方并不会攻击协议的参与方,所以协议还是安全的。

但是后门的存在会对完美安全属性有影响,结果是,若承诺方案可模棱两可,则不能实现完美绑定;若可提取,则不能实现完美隐藏。完美安全要求的是“无限能力的攻击者也不可能攻破”,而无限能力的攻击者是可以算出后门的,所以自然地,若协议有模棱两可属性,则无限能力的攻击者可以实现Equivtd\rm{Equiv}_{td},从而可以对不同的消息做出相同的承诺,攻破完美绑定属性;类似地,若协议有提取属性,则无限能力的攻击者可以实现Extratd\rm{Extra}_{td},从而可以根据承诺值恢复消息,攻破完美隐藏属性。

更进一步,直觉上(其实这里的证明我也不太确定是否正确,所以只是直觉上),只有实现了完美绑定才会有提取属性;只有实现了完美隐藏才会有模棱两可。首先假设协议拥有提取属性,但是没有完美绑定属性,则会存在mmMm \ne m' \in \mathcal{M}r,rRr, r' \in \mathcal{R},使得cm,r=cm,rc_{m, r} = c_{m', r'},那么在提取cm,rc_{m, r}或者cm,rc_{m', r'}时,就会有mmmm'两种可能,攻击者无法分辨哪个才是诚实发送方真正承诺的消息,所以若没有完美绑定属性则没有提取属性;类似地,假设协议拥有模棱两可属性,但是没有隐藏属性,则会存在m,mMm,m' \in \mathcal{M}使得 {cm,R}{cm,R}\ \{c_{m, \mathcal{R}}\} \ne \{c_{m', \mathcal{R}}\},也即存在rRr \in \mathcal{R},使得cm,r∉{cm,R}c_{m, r} \not\in \{c_{m', \mathcal{R}}\},则不存在rRr' \in \mathcal{R}使得Compk(m,r)=(c,d)\rm{Com}_{pk}(m', r') = (c, d'),即如果恰好选择到这样的mmmm'时,模棱两可会被接收者发现进而失败,所以若没有完美隐藏属性则没有模棱两可属性。

由于前文论证了“不能同时实现完美绑定和完美隐藏”,所以结合可以推出提取属性和模棱两可属性直觉上也不能同时实现。

从函数性质看安全属性

下面给出一些可能的非通用可组合框架(Plain Model)下的承诺方案构造思路,这里首先分析完美绑定或者完美隐藏的一些特性。

从单射函数到完美绑定

复习一下完美绑定的一个必要条件,m,mM, r,rR, mmcm,rcm,r\forall m,m' \in \mathcal{M},\ \forall r,r' \in \mathcal{R},\ m' \ne m \Rightarrow c_{m, r} \ne c_{m', r'},然后对比一下单射函数的定义:

a,bX, abf(a)f(b)\forall a, b \in \mathcal{X},\ a \ne b \Rightarrow f(a) \ne f(b)

可以看出两者的表述是相似的,也就是说,如果令Comc(m,r)cm,r\rm{Com}^c(m, r) \rightarrow c_{m, r},只有Comc(m,r)\rm{Com}^c(m, r)可被构造为一个单射函数,该承诺方案才会拥有完美绑定属性。或者换个说法,令Comrc(m)cm,r\rm{Com}_{r}^c(m) \rightarrow c_{m, r},需要符合下面两点:

  • m,mM; rR; mmComrc(m)Comrc(m)\forall m, m' \in \mathcal{M}\rm{;}\ \forall r \in \mathcal{R}\rm{;}\ m \ne m' \Rightarrow \rm{Com}_{r}^c(m) \ne \rm{Com}_{r}^c(m')

  • r,rR,rr{Comrc(M)}{Comrc(M)}=\forall r, r' \in \mathcal{R}, r \ne r' \Rightarrow \{\rm{Com}_{r}^c(\mathcal{M})\} \cap \{\rm{Com}_{r'}^c(\mathcal{M})\} = \empty

简单论证一下:假设存在mmMm \ne m' \in \mathcal{M}r,rRr, r' \in \mathcal{R}使得Comrc(m)=Comrc(m)\rm{Com}_{r}^c(m) = \rm{Com}_{r'}^c(m'),由第二点的两集合无交集可得只能r=rr = r',即Comrc(m)=Comrc(m)\rm{Com}_{r}^c(m) = \rm{Com}_{r}^c(m'),由第一点的单射可得只能m=mm = m',与假设矛盾,所以这样不同的mmmm'不存在,即推出m,mM, r,rR, mmcm,rcm,r\forall m,m' \in \mathcal{M},\ \forall r,r' \in \mathcal{R},\ m' \ne m \Rightarrow c_{m, r} \ne c_{m', r'}。另外,若令Commc(r)cm,r\rm{Com}_{m}^c(r) \rightarrow c_{m, r},也可以推出类似的条件。

根据以上推出的特性,可以尝试粗略地设计一种完美绑定的承诺方案的通用构造。假设FF是一个函数簇,对于所有的rRr\in \mathcal{R}Fr:MFF_r:\mathcal{M} \rightarrow \mathcal{F}G:RGG: \mathcal{R} \rightarrow \mathcal{G}是两个单射的函数,则一种完美绑定的承诺方案可以这样设计:

A Toy Commitment Scheme with Perfectly BindingCommit:Open:Sender(m)              Receiverr$Rf=Fr(m)g=G(r)c=(f,g)cd=rm, dIf f=Fd(m) and g=G(d)AcceptOtherwiseReject\text{A Toy Commitment Scheme with Perfectly Binding} \\ \begin{array}{|lc|} \hline \\ \begin{array}{c} \rm{Commit: } \\ \\ \\ \\ \\ \\ \\ \rm{Open: } \\ \\ \\ \\ \end{array} & \begin{array}{lcl} \mathrm{Sender}(m) & \ \ \ \ \ \ \ \ \ \ \ \ \ \ & \mathrm{Receiver} \\ \begin{array}{l} r \overset{\$}{\leftarrow} \mathcal{R} \\ f = F_r(m) \\ g = G(r) \\ c = (f, g) \end{array} & & \\ & \overset{c}{\longrightarrow} & \\ \vdots & & \\ \\ \begin{array}{l} d = r \end{array} & & \\ & \overset{m,\ d}{\longrightarrow} & \\ & & \begin{array}{lll} \text{If } f = F_d(m) \text{ and } g = G(d) & \rightarrow & \text{Accept} \\ \text{Otherwise} & \rightarrow & \text{Reject} \end{array} \\ \end{array} \\ \hline \end{array}

注:以上的构造只能保证完美绑定属性,如果还要计算上隐藏属性的话,还需要FFGG拥有其他的性质。

以上完美绑定属性的论证并不难,首先假设攻击者可攻破完美绑定属性,则可以找到一个与mm不同的mMm' \in \mathcal{M},使得接收者输出接受;而若接收者输出接受则必须f=Fd(m)f = F_d(m)g=G(d)g = G(d),由于GG是单射的且d=rd=r,即f=Fr(m)f = F_r(m);所以若攻击者可以攻破完美绑定,即可以找到mmm' \ne m使得Fr(m)=f=Fr(m)F_r(m') = f = F_r(m),和FrF_r的单射属性相矛盾,所以不存在这样的攻击者。

可以参考实际的例子,ElGamal承诺方案就是利用类似的思路构造的。令G=<g>\mathbb{G} = <g>是一个素数qq阶的循环群,h,gGh, g \in \mathbb{G}是两个随机的生成元,消息mGm \in \mathbb{G},则ElGamal承诺方案可以表示为:

ElGamal Commitment SchemeCommit:Open:Sender(m)              Receiverr$Zqc0=mhrc1=grc=(c0,c1)cd=rm, dIf c=(mhr,gr)AcceptOtherwiseReject\text{ElGamal Commitment Scheme} \\ \begin{array}{|lc|} \hline \\ \begin{array}{c} \rm{Commit: } \\ \\ \\ \\ \\ \\ \\ \rm{Open: } \\ \\ \\ \\ \end{array} & \begin{array}{lcl} \mathrm{Sender}(m) & \ \ \ \ \ \ \ \ \ \ \ \ \ \ & \mathrm{Receiver} \\ \begin{array}{l} r \overset{\$}{\leftarrow} \mathbb{Z}_q \\ c_0 = mh^r \\ c_1 = g^r \\ c = (c_0, c_1) \end{array} & & \\ & \overset{c}{\longrightarrow} & \\ \vdots & & \\ \\ \begin{array}{l} d = r \end{array} & & \\ & \overset{m,\ d}{\longrightarrow} & \\ & & \begin{array}{lll} \text{If } c = (mh^r, g^r) & \rightarrow & \text{Accept} \\ \text{Otherwise} & \rightarrow & \text{Reject} \end{array} \\ \end{array} \\ \hline \end{array}

Fr(m)=mhrF_r(m) = mh^rG(r)=grG(r) = g^r这就是上面通用构造的一个实例化,显然Fr(m)F_r(m)G(r)G(r)都是单射函数。

从满射函数到完美隐藏

先复习一下完美隐藏的定义:m,mM, {cm,R}={cm,R}\forall m,m' \in \mathcal{M},\ \{c_{m, \mathcal{R}}\} = \{c_{m', \mathcal{R}}\},这里假设C\mathcal{C}中不包含多余的承诺值,即C={cm,r  mM; rR}\mathcal{C} = \{ c_{m, r}\ |\ m \in \mathcal{M}\rm{;}\ r \in \mathcal{R} \},则可以得到mM, {cm,R}=C\forall m \in \mathcal{M},\ \{c_{m, \mathcal{R}}\} = \mathcal{C},也即mM; cC;\forall m \in \mathcal{M}\rm{;}\ \forall c \in \mathcal{C}\rm{;} rR\exist r \in \mathcal{R} s.t. cm,r=cs.t.\ c_{m, r} = c。类似地,对比满射的定义,设F:XYF: \mathcal{X} \to \mathcal{Y},则:

yY; xX; s.t. F(x)=y\forall y \in \mathcal{Y}\rm{;}\ \exist x \in \mathcal{X}\rm{;}\ s.t.\ F(x)=y

两个表述是相似的,如果令Commc(r)cm,r\rm{Com}_{m}^c(r) \rightarrow c_{m, r},则当且仅当对所有mMm \in \mathcal{M}Commc(r)\rm{Com}_{m}^c(r)满射到C\mathcal{C}时,承诺方案拥有完美隐藏属性。

首先论证\Rightarrow方向:若对所有mMm \in \mathcal{M}Commc(r)\rm{Com}_{m}^c(r)满射到C\mathcal{C},则mM; cC; rR s.t.Commc(r)=c\forall m \in \mathcal{M}\rm{;}\ \forall c \in \mathcal{C}\rm{;}\ \exist r \in \mathcal{R}\ s.t. \rm{Com}_{m}^c(r)=c,即符合上面的完美隐藏定义推导;

接着论证\Leftarrow方向:假设存在某个mMm \in \mathcal{M}使得Commc(r)\rm{Com}_{m}^c(r)不满射到C\mathcal{C},则存在mMm' \in \mathcal{M}rRr' \in \mathcal{R},使得c=Commc(r)∉{Commc(R)}c' = \rm{Com}_{m'}^c(r') \not\in \{ \rm{Com}_{m}^c(\mathcal{R}) \},可得c({Commc(R)}{Commc(R)})c' \in (\{ \rm{Com}_{m'}^c(\mathcal{R}) \} - \{ \rm{Com}_{m}^c(\mathcal{R}) \}) \ne \empty,即存在mMm' \in \mathcal{M}rRr' \in \mathcal{R},使得{Commc(R)}{Commc(R)}\{ \rm{Com}_{m'}^c(\mathcal{R}) \} \ne \{ \rm{Com}_{m}^c(\mathcal{R}) \},和完美隐藏的定义相悖,所以不存在这样的mm

根据以上推出的特性,下面尝试粗略地设计一种完美隐藏的承诺方案的通用构造。假设FF是一个函数簇,对于所有的mMm\in \mathcal{M}FmF_m都能从R\mathcal{R}满射到C\mathcal{C},则一种完美隐藏的承诺方案可以这样设计:

A Toy Commitment Scheme with Perfectly HidingCommit:Open:Sender(m)              Receiverr$Rc=Fm(r)cd=rm, dIf c=Fm(d)AcceptOtherwiseReject\text{A Toy Commitment Scheme with Perfectly Hiding} \\ \begin{array}{|lc|} \hline \\ \begin{array}{c} \rm{Commit: } \\ \\ \\ \\ \\ \\ \rm{Open: } \\ \\ \\ \\ \end{array} & \begin{array}{lcl} \mathrm{Sender}(m) & \ \ \ \ \ \ \ \ \ \ \ \ \ \ & \mathrm{Receiver} \\ \begin{array}{l} r \overset{\$}{\leftarrow} \mathcal{R} \\ c = F_m(r) \end{array} & & \\ & \overset{c}{\longrightarrow} & \\ \vdots & & \\ \\ \begin{array}{l} d = r \end{array} & & \\ & \overset{m,\ d}{\longrightarrow} & \\ & & \begin{array}{lll} \text{If } c = F_m(d) & \rightarrow & \text{Accept} \\ \text{Otherwise} & \rightarrow & \text{Reject} \end{array} \\ \end{array} \\ \hline \end{array}

注:以上的构造只能保证完美隐藏属性,如果还要计算上隐藏属性的话,还需要FF拥有其他的性质。

以上完美隐藏属性的论证也不难,假设攻击者可以攻破完美隐藏属性,则可以仅根据c=Fm(r)c = F_m(r)恢复mm,但由于mM\forall m^* \in \mathcal{M}FmF_{m^*}满射到C\mathcal{C},即对于任意的mMm^* \in \mathcal{M},都可能存在rRr^* \in \mathcal{R}使得Fm(r)=cF_{m^*}(r^*) = c,所以攻击者不可能知道cc是由哪个mm^*选出的函数所映射的。

来个实际的例子,Pedersen承诺方案就是利用类似的思路构造承诺方案的。令G=<g>\mathbb{G} = <g>是一个素数qq阶的循环群,h,gGh, g \in \mathbb{G}是两个随机的生成元,消息mZqm \in \mathbb{Z}_q,则Pedersen承诺方案可以表示为:

Pedersen Commitment SchemeCommit:Open:Sender(m)              Receiverr$Zqc=gmhrcd=rm, dIf c=gmhdAcceptOtherwiseReject\text{Pedersen Commitment Scheme} \\ \begin{array}{|lc|} \hline \\ \begin{array}{c} \rm{Commit: } \\ \\ \\ \\ \\ \\ \\ \rm{Open: } \\ \\ \\ \\ \end{array} & \begin{array}{lcl} \mathrm{Sender}(m) & \ \ \ \ \ \ \ \ \ \ \ \ \ \ & \mathrm{Receiver} \\ \begin{array}{l} r \overset{\$}{\leftarrow} \mathbb{Z}_q \\ c = g^mh^r \end{array} & & \\ & \overset{c}{\longrightarrow} & \\ \vdots & & \\ \\ \begin{array}{l} d = r \end{array} & & \\ & \overset{m,\ d}{\longrightarrow} & \\ & & \begin{array}{lll} \text{If } c = g^mh^d & \rightarrow & \text{Accept} \\ \text{Otherwise} & \rightarrow & \text{Reject} \end{array} \\ \end{array} \\ \hline \end{array}

Fm(r)=gmhrF_m(r) = g^mh^r,这就是上面构造的一个实例化。显然对于所有mZqm \in \mathbb{Z}_qFmF_m满射到G\mathbb{G},因为Zq=G=q|\mathbb{Z}_q| = |\mathbb{G}| = q,假设存在某个mGm \in \mathbb{G}使得FmF_m不满射到G\mathbb{G},则存在rrZqr \ne r' \in \mathbb{Z}_q,使得Fm(r)=Fm(r)F_m(r) = F_m(r'),即gmhrgmhrg^mh^r \equiv g^mh^{r'} (in G)(\rm{in}\ \mathbb{G}),也即hrhr (in G)h^r \equiv h^{r'}\ (\rm{in}\ \mathbb{G}),由于hhG\mathbb{G}的生成元,即当且仅当r=rr = r'时成立,与假设矛盾。

从单向函数到计算上安全

计算上安全的构造则没有那么直观,因为计算上安全要求是攻击成功的概率可忽略,就需要把安全性规约到某个难题上,但现有的难题五花八门,很难找到一种“模板”的构造方法。但也许可以用单向函数(One-way Function)做个尝试,首先看一下单向函数的定义:若函数f:XYf: \mathcal{X} \to \mathcal{Y}是单向函数,则任何多项式算法FF算出ff的伪逆(Pseudo Inverse)的概率可忽略,即

Pr[f(F(f(x)))=f(x)]negl\rm{Pr}[f(F(f(x))) = f(x)] \le \rm{negl}

首先单向函数可以很直观地推出计算上隐藏属性,假设Comrc(m):MC\rm{Com}_r^c(m): \mathcal{M} \to \mathcal{C}是单向函数,若攻击者AR\text{A}_\text{R}可以在多项式时间内攻破隐藏属性,则会有AR(Comrc(m))=m\text{A}_\text{R}(\rm{Com}_r^c(m)) = m,即Pr[Comrc(AR(Comrc(m)))=Comrc(m)]>negl\rm{Pr}[\rm{Com}_r^c(\text{A}_\text{R}(\rm{Com}_r^c(m))) = \rm{Com}_r^c(m)] > \rm{negl},可以调用AR\text{A}_\text{R}攻击Comrc(m)\rm{Com}_r^c(m)的单向性,即计算上隐藏的安全性可规约到Comrc(m)\rm{Com}_r^c(m)的单向性。

计算上绑定的规约则每那么直观,可能需要先定义一个更宽松的绑定属性,在AdvBinding\text{Adv}_\text{Binding}的定义中,攻击者AS\text{A}_\text{S}需要在同一时间给出mmmm',但承诺方案中真正攻击的流程也许并不是这样的,比如在通用可组合框架的证明过程中的模拟者,需要先生成一个承诺值cCc \in \mathcal{C},然后由环境给出消息mMm' \in \mathcal{M},然后再由模拟者生成dd'cc打开为mm'的承诺。根据这个流程,可以给出以下定义:

AdvBindinglossy(AS)=Pr[Verify(c,m,d)=Accept:cAS();  cC;m$M;dASm(c);  dD;]\text{Adv}^\text{lossy}_\text{Binding}(\text{A}_\text{S}) = Pr\begin{bmatrix} \begin{array}{ccc} \begin{array}{l} \rm{Verify(c, m', d')} = \text{Accept} \end{array} & \rm{:} & \begin{array}{l} c \leftarrow \text{A}_\text{S}() \rm{;} \ \ c \in \mathcal{C} \rm{;} \\ m' \overset{\$}{\leftarrow} \mathcal{M} \rm{;} \\ d' \leftarrow \text{A}^{m'}_\text{S}(c) \rm{;} \ \ d' \in \mathcal{D} \rm{;} \\ \end{array} \end{array} \end{bmatrix}

这里由于mm'是随机选择而不是让攻击者选择,所以定义变宽松了而且安全性也变弱,但是证明时的可操作空间也更大。现在假设Commc(r):RC\rm{Com}_m^c(r): \mathcal{R} \to \mathcal{C}是单向函数,且假设在构造时令d=rd=r(或者使用类似的构造),假设Verify(c,m,r):=Commc(r)=?c\rm{Verify}(c^*, m, r) := \rm{Com}_m^c(r) \overset{?}{=} c的运算并对比得出的值是否和承诺值cc相等。因为AS\text{A}_\text{S}在生成cc时并不知道mm'的任何信息,所以对于Comm\rm{Com}_{m'}来说cc是一个完全随机的像,而在选出mm'后,若AS\text{A}_\text{S}输出的dd'可以通过验证,则Comm(d)=c\rm{Com}_{m'}(d') = c,即有Pr[Commc(AS(c))=c]>negl\rm{Pr}[\rm{Com}_{m'}^c(\text{A}_\text{S}(c)) = c] > \rm{negl},和Commc\rm{Com}_m^c是单向函数的假设冲突。虽然论证如是说,但由于不能自由控制cc的选取,并不能直观地进行规约,所以这里的证明能否通过还需要斟酌。

从陷门置换到后门属性

由于模棱两可和提取这两个后门属性都需要一个后门值,所以考虑后门属性的构造时,最先想到的会是陷门函数(Trapdoor Function)。陷门函数本身也是一个单向函数,单向函数要求求出伪逆的概率可忽略,而陷门函数则说,如果知道后门的话,则存在可以容易地求出逆(或伪逆)的逆函数,假设F:XYF: \mathcal{X} \to \mathcal{Y}是陷门函数、Gen\rm{Gen}是密钥生成函数、Invert\rm{Invert}是逆函数,则:

  • (pk,td)Gen(1κ)(pk, td) \leftarrow \rm{Gen}(1^\kappa)
  • xInverttd(Fpk(x)), Fpk(x)=Fpk(x)x' \leftarrow \rm{Invert}_{td}(F_{pk}(x)),\ F_{pk}(x) = F_{pk}(x')

陷门置换(Trapdoor Permutation)则是双射的陷门函数。

利用陷门置换构造提取属性是直观的,假设Compk,rc(m):MC\rm{Com}_{pk,r}^c(m): \mathcal{M} \to \mathcal{C}是一个陷门置换,令

Extratd(c):=InverttdCompk,rc(c)\rm{Extra}_{td}(c) := \rm{Invert}^{\rm{Com}_{pk,r}^c}_{td}(c)

即可实现提取操作。由于Compk,rc(m)\rm{Com}_{pk,r}^c(m)是双射的,即至少是单射的,也即不存在mmMm' \ne m \in \mathcal{M}使得Compk,rc(m)=c\rm{Com}_{pk,r}^c(m')=c,自然Extratd\rm{Extra}_{td}提取出mmm' \ne m,即提取出来的是真实的逆,不是伪逆。

然后是利用陷门置换构造模棱两可属性,假设Compk,mc(r):RC\rm{Com}_{pk,m}^c(r): \mathcal{R} \to \mathcal{C}是陷门置换,且假设在构造时令d=rd=r(或者使用类似的构造),假设Verifypk(c,m,r):=Compk,mc(r)=?c\rm{Verify}_{pk}(c^*, m, r) := \rm{Com}_{pk, m}^c(r) \overset{?}{=} c^*的运算并对比得出的值是否和承诺值cc相等。令

Equivtd(m,m,r):=InverttdCompk,mc(Compk,mc(r))\rm{Equiv}_{td}(m, m', r) := \rm{Invert}^{\rm{Com}_{pk,m'}^c}_{td}(\rm{Com}_{pk,m}^c(r))

即可实现模棱两可操作。由于Compk,mc\rm{Com}_{pk,m}^c双射到C\mathcal{C},即c=Compk,mc(r)Cc = \rm{Com}_{pk,m}^c(r) \in \mathcal{C},且存在唯一的rRr' \in \mathcal{R}使得Compk,mc(r)=c\rm{Com}_{pk,m'}^c(r') = c,可得r=Equivtd(m,m,r)=InverttdCompk,mc(Compk,mc(r))r' = \rm{Equiv}_{td}(m, m', r) = \rm{Invert}^{\rm{Com}_{pk,m'}^c}_{td}(\rm{Com}_{pk,m}^c(r)),代入Verifypk(c,m,r)\rm{Verify}_{pk}(c, m', r'),根据陷门函数的性质可得

Compk,mc(r)=Compk,mc(InverttdCompk,mc(Compk,mc(r)))=Compk,mc(r)=c\rm{Com}_{pk, m'}^c(r') = \rm{Com}_{pk, m'}^c(\rm{Invert}^{\rm{Com}_{pk,m'}^c}_{td}(\rm{Com}_{pk,m}^c(r))) = \rm{Com}_{pk,m}^c(r) = c

验证通过。

例子

以下利用上述构造思路构造两种承诺方案,并给出相应的证明。

例子一

首先尝试构造计算上绑定、完美隐藏且拥有模棱两可属性的承诺方案。假设F:RFF: \mathcal{R} \to \mathcal{F}是一个陷门置换,公钥为pkpk、后门为tdtd;设GG是一个置换的簇,由mMm \in \mathcal{M}选出一个置换函数Gm:FCG_m: \mathcal{F} \to \mathcal{C},且在知道mm时存在多项式算法Gm1G_m^{-1}计算置换的逆,则该承诺方案可以构造为:

Commit:Open:Sender(m)              Receiverr$Rc=Gm(Fpk(r))cd=rm, dIf c=Gm(Fpk(d))AcceptOtherwiseReject\begin{array}{|lc|} \hline \\ \begin{array}{c} \rm{Commit: } \\ \\ \\ \\ \\ \\ \\ \rm{Open: } \\ \\ \\ \\ \end{array} & \begin{array}{lcl} \mathrm{Sender}(m) & \ \ \ \ \ \ \ \ \ \ \ \ \ \ & \mathrm{Receiver} \\ \begin{array}{l} r \overset{\$}{\leftarrow} \mathcal{R} \\ c = G_m(F_{pk}(r)) \end{array} & & \\ & \overset{c}{\longrightarrow} & \\ \vdots & & \\ \\ \begin{array}{l} d = r \end{array} & & \\ & \overset{m,\ d}{\longrightarrow} & \\ & & \begin{array}{lll} \text{If } c = G_m(F_{pk}(d)) & \rightarrow & \text{Accept} \\ \text{Otherwise} & \rightarrow & \text{Reject} \end{array} \\ \end{array} \\ \hline \end{array}

下面作简略证明:

  • 计算上绑定:假设多项式时间的攻击者AS\text{A}_\text{S}AdvBinding(AS)\text{Adv}_\text{Binding}(\text{A}_\text{S})优势不可忽略,则可以找到mmMm \ne m' \in \mathcal{M}r,rRr, r' \in \mathcal{R}使得Gm(Fpk(r))=Gm(Fpk(r))G_m(F_{pk}(r)) = G_{m'}(F_{pk}(r')),则在不知道tdtd的情况下有不可忽略的概率可以算出rRr’ \in \mathcal{R}使得Fpk(r)=Gm1(Gm(Fpk(r)))F_{pk}(r') = G_{m'}^{-1}(G_{m}(F_{pk}(r)))即,

    Pr[Fpk(AS(Fpk(r)))=Fpk(r)]>negl\rm{Pr}[F_{pk}(\text{A}_\text{S}(F_{pk}(r))) = F_{pk}(r)] > \rm{negl}

    从而攻破FpkF_{pk}的单向性。

  • 完美隐藏:由于FpkF_{pk}GmG_m都双射,所以对于任意mmMm \ne m' \in \mathcal{M}

    {Gm(Fpk(R))}={Gm(F)}=C={Gm(F)}={Gm(Fpk(R))}\{ G_m(F_{pk}(\mathcal{R})) \} = \{ G_m(\mathcal{F}) \} = \mathcal{C} = \{ G_{m'}(\mathcal{F}) \} = \{ G_{m'}(F_{pk}(\mathcal{R})) \}

    AdvHiding(AR)=0\text{Adv}_\text{Hiding}(\text{A}_\text{R})=0

  • 模棱两可:和计算上绑定的证明类似,但知道tdtd的情况下可以对FpkF_{pk}求逆,

    Equivtd(m,m,d):=InverttdF(Gm1(Gm(Fpk(r))))\rm{Equiv}_{td}(m, m', d) := \rm{Invert}_{td}^{F}(G_{m'}^{-1}(G_{m}(F_{pk}(r))))

例子二

接下来尝试构造完美绑定、计算上隐藏且拥有提取属性的承诺方案。假设FF是一个函数簇,对于所有的rRr\in \mathcal{R}Fr:MFF_r:\mathcal{M} \rightarrow \mathcal{F}是单射函数,且在知道mm时存在多项式算法IndexF(m):=r\rm{Index}^F(m) := r计算选择函数的值,在知道rr时存在多项式算法Fr1F_r^{-1}计算函数的逆;G:RGG: \mathcal{R} \rightarrow \mathcal{G}是单射的陷门函数,公钥为pkpk、私钥为tdtd,则该承诺方案可以构造为:

Commit:Open:Sender(m)              Receiverr$Rf=Fr(m)g=Gpk(r)c=(f,g)cd=rm, dIf f=Fd(m) and g=Gpk(d)AcceptOtherwiseReject\begin{array}{|lc|} \hline \\ \begin{array}{c} \rm{Commit: } \\ \\ \\ \\ \\ \\ \\ \rm{Open: } \\ \\ \\ \\ \end{array} & \begin{array}{lcl} \mathrm{Sender}(m) & \ \ \ \ \ \ \ \ \ \ \ \ \ \ & \mathrm{Receiver} \\ \begin{array}{l} r \overset{\$}{\leftarrow} \mathcal{R} \\ f = F_r(m) \\ g = G_{pk}(r) \\ c = (f, g) \end{array} & & \\ & \overset{c}{\longrightarrow} & \\ \vdots & & \\ \\ \begin{array}{l} d = r \end{array} & & \\ & \overset{m,\ d}{\longrightarrow} & \\ & & \begin{array}{lll} \text{If } f = F_d(m) \text{ and } g = G_{pk}(d) & \rightarrow & \text{Accept} \\ \text{Otherwise} & \rightarrow & \text{Reject} \end{array} \\ \end{array} \\ \hline \end{array}

以下作简略证明:

  • 完美绑定:假设AdvBinding(AS)0\text{Adv}_\text{Binding}(\text{A}_\text{S})\ne 0,则存在mmMm \ne m' \in \mathcal{M}r,rRr, r' \in \mathcal{R}使得Fr(m)=Fr(m)F_r(m) = F_{r'}(m')Gpk(r)=Gpk(r)G_{pk}(r) = G_{pk}(r'),由于GpkG_{pk}是单射函数,所以r=rr = r',即Fr(m)=Fr(m)F_r(m) = F_{r}(m'),由于FrF_r也是单射函数,所以m=mm = m',与假设矛盾,所以AdvBinding(AS)=0\text{Adv}_\text{Binding}(\text{A}_\text{S}) = 0

  • 计算上隐藏:假设多项式时间的攻击者AR\text{A}_\text{R}AdvHiding(AR)\text{Adv}_\text{Hiding}(\text{A}_\text{R})优势不可忽略,则可以在不知道tdtd的情况下根据Fr(m)F_r(m)Gpk(r)G_{pk}(r)算出mm,随即可以算出r=IndexF(m)r = \rm{Index}^F(m),即

    Pr[Gpk(AR(Gpk(r)))=Gpk(r)]>negl\rm{Pr}[G_{pk}(\text{A}_\text{R}(G_{pk}(r))) = G_{pk}(r)] > \rm{negl}

    从而攻破GpkG_{pk}的单向性。

  • 提取:和计算上隐藏的证明类似,但在知道tdtd的情况下可以对GpkG_{pk}求逆:

    Extratd(c):=FInverttdG(g)1(c)\rm{Extra}_{td}(c) := F^{-1}_{\rm{Invert}_{td}^G(g)}(c)

额外的思路

异或

例子一中的GG函数和例子二的FF函数其实都可以利用异或操作构造。

首先,当nZ+n \in \mathbb{Z^+}a,b{0,1}na,b \in \{0, 1\}^n时,函数Fa(b):=abF_a(b) := a \bigoplus b是一个{0,1}n{0,1}n\{0, 1\}^n \to \{0, 1\}^n的置换:

  • 单射性:假设存在bb{0,1}nb \ne b' \in \{0, 1\}^n使得Fa(b)=Fa(b)F_a(b) = F_a(b'),则ab=aba \bigoplus b = a \bigoplus b',则b=bb = b',矛盾。所以

    a{0,1}n; b,b{0,1}n; bbFa(b)Fa(b)\forall a \in \{0, 1\}^n \rm{;}\ \forall b, b' \in \{0, 1\}^n \rm{;}\ b \ne b' \Rightarrow F_a(b) \ne F_a(b')

  • 满射性:假设存在c{0,1}nc \in \{0, 1\}^n使得b{0,1}n, Fa(b)c\forall b \in \{0, 1\}^n,\ F_a(b) \ne c,由于FaF_a定义域与值域相同,则bb s.t. Fa(b)=Fa(b)\exist b \ne b'\ s.t.\ F_a(b) = F_a(b'),即bb s.t. ab=ab\exist b \ne b'\ s.t.\ a \bigoplus b = a \bigoplus b',当且仅当bb s.t. b=b\exist b \ne b'\ s.t.\ b = b',矛盾,所以

    c{0,1}n; b{0,1}n s.t.  Fa(b)=c\forall c \in \{0, 1\}^n\rm{;}\ \exist b \in \{0, 1\}^n\ s.t.\ \ F_a(b) = c