比特承诺:

股票经纪人甲试图说服乙购买他的服务,甲表示,它已分析出若干支股票将会涨停,但在乙出钱购买它的服务之前,它不能透露如此有价值的信息,于是甲将这几支股票写在纸上,并锁进保险箱里,将保险箱交给乙,表示,一个月后将钥匙给乙,如果到时候打开保险柜,看看里面写的股票是否确实涨停,以此来判定甲的预测能力.

这便是比特承诺的概念.比特承诺包含两方:承诺者与验证者.

比特承诺包括以下几个阶段:

1. 承诺阶段:承诺者选择一个要承诺的比特$b\in\{0,1\}$,把能代表该比特的信息$c$发送给验证者
2. 打开阶段:承诺者把用于打开$c$的信息$d$和承诺的比特$b$发送给验证者,验证者用$d$打开$c$并验证是否是$b$

安全的比特承诺需要满足的性质:

1. 隐藏性:打开阶段开始前,验证者无法得到$b$,进一步地,称一个方案是完善隐蔽的,指验证者不能从$c$中获得任何关于$b$的信息.
2. 绑定性:承诺者不能在打开阶段之前改变自己承诺的比特.

类似于密码算法安全性的定义,比特承诺的属性分为计算上隐藏的,计算上绑定的,和信息论上隐藏的,信息论上绑定的.

常用比特承诺协议:

使用对称加密函数的比特承诺:

协议开始前,双方在TTP的帮助下协商出安全的加密算法$Enc_{(\cdot)}(\cdot)$和解密算法$Dec_{(\cdot)}(\cdot)$

(博主注:为何一定要在TTP帮助下协商呢,如果密钥是安全的,直接将加密解密算法公开不行吗)

注:用$||$表示字符串拼接

隐藏性:Bob不知道密钥$k$则无法解密$Enc_k(r||b)$ 

绑定性:如果消息不含$r$,则Alice随便就能找到一个密钥$k'$就可以使得解密后得到的值反转.而包含$r$后,虽然Alice也能通过穷举做到,但在计算上是不可行的.

使用单向哈希的比特承诺:

协议开始前,双方在TTP的帮助下协商出安全的哈希算法$Hash(\cdot)$

好处:Bob无需发送消息.

隐藏性:由于不知道$r_2$,Bob无法区分$Hash(r_1||r_2||0),Hash(r_1||r_2||1)$

绑定性:Alice要伪造承诺,需要计算哈希碰撞$Hash(r_1||r_2'||b')=Hash(r_1||r_2||b)$,这在计算上是不可行的.

使用伪随机数发生器的比特承诺:

双方在TTP的帮助下选择一个伪随机数发生器$G$,再选择一个足够长的随机串$R$

隐藏性:由于不知道$s$,Bob无法区分$G(s),G(s)\oplus R$

绑定性:要伪造承诺,则需计算$G(s')=G(s)\oplus R$或者$G(s')\oplus R=G(s)$,这在计算上是不可行的.

Pedersen承诺协议:

比特承诺协议也可以利用数论中的一些计算困难的问题来构造,例如该协议就是通过离散对数问题进行构造的.

双方在TTP的帮助下选择大素数$p$,$Z_p*$的生成元$p$(g\in[1,p-1]),随机数$y\in[1,p-1]$

隐藏性:因为$r$随机产生,因此Bob无法区分$c_0=g^r$和$c_1=g^ry$.

绑定性:若Alice要篡改自己的承诺(以将$b=1$篡改为$b=0$为例),则需要计算$r'$,使得

$$\begin{aligned}g^{r'}=&g^ry \\g^{r'-r} =& y \\r'=& \log_g y+r \mod p\end{aligned}$$

这需要计算离散对数问题,这在计算上是不可行的.

(博主注:以上几个协议的隐藏性都是信息论级别的,绑定性则只有计算复杂度级别)

如果要用比特承诺协议承诺多个比特,可以重复应用协议多次,而对Pedersen承诺协议而言,也可以直接将承诺的字符串$m$作为计算$c=g^ry^m \mod p$的指数应用.(注意,此时要求$m\in[1,q-1]$,否则需要对字符串进行分块.)