Commitment

概述

密码学承诺是一个涉及两方的二阶段交互协议，双方分别为承诺方和接收方。简述来说，它的功能涵盖不可更改性和确定性。
承诺方发送的消息密文，一旦发出就意味着不会再更改，而接收方收到这个消息可以进行验证结果。
特点就是无需第三方就可以进行验证。

举个例子：猜拳问题

假设有人在猜拳中老是不按时出拳，那么在看到对方的结果再出拳，显然是不公平的，在没有第三方的情况下，怎样保证无人作弊呢？那就是承诺。
这里使用一个哈希函数构造一个简单的承诺方案，双方选取一个足够安全的哈希函数H(x)H(x)H(x)，将猜拳的三种出拳方法定为一组数字如x1,x2,x3x_1,x_2,x_3x1​,x2​,x3​。那么方案如下，

• 选手一选择一个出拳方法xix_ixi​（如x1x_1x1​）,再选取一个随机数rir_iri​如（r1r_1r1​），计算承诺H(x1∣∣r1)H(x_1||r_1)H(x1​∣∣r1​)，并把它发送给选手二。
• 选手二也选择一个出拳方法（如x3x_3x3​）,同样也选择一个随机数r2r_2r2​,计算承诺H(x2∣∣r2)H(x_2||r_2)H(x2​∣∣r2​)，并把它发送给选手一。
• 双方都收到承诺后，都公布自己的xix_ixi​和rir_iri​，然后进行验证即可

选择添加随机数的原因主要预防某一方直接算出三种出拳方式的哈希，然后接收到了另一方的哈希后，直接进行对比作弊。
可以看到承诺主要分为两个阶段

1. Commit Phase：把暂时不想公开的消息（即前面的出拳方案）再加一个随机数，加密后（如前面的计算哈希）发送给对方；
2. Reveal Phase：公开秘密和随机数。

性质

承诺具有两个基本性质：隐藏性(Hiding)和绑定性（Binding），隐藏也就是承诺值是不会泄漏有关原消息的任何信息的，而绑定就是接收方可以确信收到的消息是该承诺对应的消息，不可能再找到一个不同的消息从而诞生同一个承诺。
而衡量性质强度一般有两个标准 Perfectly和Computationally，前者代表即便有无穷计算能力也不能破坏掉该性质，后者则是以目前的计算能力在可忍受的时间里是不能破坏该性质的。
但不存在Perfectly Hiding和Perfectly Binding，假设存在一个Perfectly Hiding，那么为了不泄露原消息，一定会有多个消息能计算出同一个承诺，这恰好违背了Binding的性质。

常用方案

主要是拥有Perfectly hiding and computationally binding的Pedersen Commitment 和 拥有Perfectly binding but computationally hiding的 ElGamal Commitment

Pedersen Commitment

DL（离散对数)

选择一个阶为qqq的乘法群GGG，再选择两个元素g,h∈Gqg,h \in G_qg,h∈Gq​，xxx是消息，rrr是随机数

• Commit Phase：Commit(x,r)=gxhrCommit(x,r)=g^xh^rCommit(x,r)=gxhr
• Reveal Phase：公开x,rx,rx,r

加同态
Commit(x1,r1)×Commit(x2,r2)=gx1hr1×gx2hr2=gx1+x2hr1+r2=Commit(x1+x2,r1+r2)\begin{aligned} Commit(x_1,r_1) \times Commit(x_2,r_2) &= g^{x_1}h^{r_1} \times g^{x_2}h^{r_2}\\ &=g^{x_1+x_2}h^{r_1+r_2} \\ &=Commit(x_1+x_2,r_1+r_2) \end{aligned}Commit(x1​,r1​)×Commit(x2​,r2​)​=gx1​hr1​×gx2​hr2​=gx1​+x2​hr1​+r2​=Commit(x1​+x2​,r1​+r2​)​

ECC（椭圆曲线）

选择椭圆曲线上的一个基点GGG和随机一个点HHH

• Commit Phase：Commit(x,r)=Gx+HrCommit(x,r)=Gx+HrCommit(x,r)=Gx+Hr
• Reveal Phase：公开x,rx,rx,r

加同态
$\begin{aligned}

\end{aligned}$Commit(x1,r1)+Commit(x2,r2)=Gx1+Hr1+Gx2+Hr2=(x1+x2)G+(r1+r2)H=Commit(x1+x2,r1+r2)\begin{aligned} Commit(x_1,r_1) + Commit(x_2,r_2) &= Gx_1+Hr_1 + Gx_2+Hr_2 \\ &=(x_1+x_2)G+(r_1+r_2)H \\ &=Commit(x_1+x_2,r_1+r_2) \end{aligned}Commit(x1​,r1​)+Commit(x2​,r2​)​=Gx1​+Hr1​+Gx2​+Hr2​=(x1​+x2​)G+(r1​+r2​)H=Commit(x1​+x2​,r1​+r2​)​

ElGamal Commitment

假设GGG是阶为qqq的循环群，而g,hg,hg,h是GGG的两个随机生成元。消息m∈Gm \in Gm∈G，随机数r∈Zqr \in \mathbb{Z}_qr∈Zq​

• Commit Phase：Commit=(gr,mhr)Commit=(g^r,mh^r)Commit=(gr,mhr)
• Reveal Phase：公开(m,r)(m,r)(m,r)

参考

密码学承诺之Pedersen commitment原理及应用
Commitment Scheme
Pedersen, T. P. (1991). Non-Interactive and Information-Theoretic Secure Verifiable Secret Sharing. Advances in Cryptology - CRYPTO '91, 129-140. doi: 10.1007/3-540-46766-1_9