承诺方案 | Codeboy's Blog

形式陈述

非交互承诺方案为每个安全参数固定消息空间 $\mathcal M_\lambda$ ，并包含

pp\leftarrow\operatorname{Setup}(1^\lambda),\qquad (c,d)\leftarrow\operatorname{Commit}(pp,m),

\operatorname{VerifyOpen}(pp,c,m,d)\in\{0,1\}.

正确性要求对每个 $m\in\mathcal M_\lambda$ ，概率

\Pr\!\left[ \operatorname{VerifyOpen}(pp,c,m,d)=1: \begin{array}{l} pp\leftarrow\operatorname{Setup}(1^\lambda),\\ (c,d)\leftarrow\operatorname{Commit}(pp,m) \end{array} \right] \ge1-\operatorname{negl}(\lambda),

完美正确性则把右侧换成 $1$ 。

隐藏实验先生成 $pp$ ，让攻击者 $\mathcal A_0(pp)$ 输出等长消息 $m_0,m_1$ 和状态 $st$ ；挑战者均匀采样 $b$ ，生成 $(c,d)\leftarrow\operatorname{Commit}(pp,m_b)$ ，只把 $(st,c)$ 交给 $\mathcal A_1$ 猜测 $b'$ 。在计算安全层次，计算隐藏要求每个 PPT $\mathcal A$ 的优势

\left|\Pr[b'=b]-\frac12\right|

可忽略。统计隐藏要求对任意 $m_0,m_1$ ，联合分布 $(pp,c_0)$ 与 $(pp,c_1)$ 的统计距离可忽略；完美隐藏则要求二者完全同分布。

绑定实验生成 $pp$ 后，让攻击者输出

(c,m_0,d_0,m_1,d_1),\qquad m_0\ne m_1,

并在两个 $\operatorname{VerifyOpen}$ 调用都接受时获胜。计算绑定量化所有 PPT 攻击者并要求成功概率可忽略；统计绑定允许计算无界攻击者，但成功概率仍须可忽略；完美绑定要求对每个 Setup 支持中的 $pp$ 都不存在可同时验证的两种不同打开。

参数 $pp$ 的来源是安全模型的一部分：它可以是无陷门公开参数、CRS 或可验证群描述，并须说明任何 setup trapdoor 由谁掌握。extractable binding 要求提取器，equivocal commitment 允许带陷门模拟器改变打开；二者都超出普通绑定与隐藏。若承诺阶段是交互式协议， $c,d$ 接口必须改成双方 view 的交互实验。

直觉

承诺像把消息放进只能稍后打开的保险箱：隐藏性防接收者提前得知内容，绑定性防发送者事后改口。两项性质面对不同攻击者，也使用不同实验；“承诺看起来随机”与“目前找不到第二种打开”都不能替代量词化定义。

无额外假设的经典非交互承诺通常不能同时完美隐藏且完美绑定，因此实际方案会让其中至少一侧依赖计算假设、可信 setup 或交互。

例子与边界

哈希承诺可写成 $c=H(\operatorname{encode}(r,m))$ ，开放时公布 $(r,m)$ 。足够长的随机盐 $r$ 可阻止低熵消息被直接枚举，抗碰撞或适当的第二原像性质帮助绑定；但结论依赖具体哈希模型。编码若有歧义，同一字符串可能解析为不同 $(r,m)$ ；随机性复用、盐太短或参数后门也会破坏安全。

Pedersen 承诺 $g^mh^r$ 在离散对数关系未知时完美隐藏、计算绑定，并具有同态性。承诺不等于加密：接收者通常不持有解密密钥，协议目标是“先固定、后揭示”，而不是长期恢复机密消息。

推论与应用

承诺用于零知识、抛硬币、安全多方计算、拍卖和区块链协议。抗碰撞性与群困难假设可实现不同承诺，零知识证明常用承诺固定挑战前的选择；coin flipping、MPC 与 Sigma 协议编译都依赖“先锁定、后揭示”的时序。

参考资料

Jonathan Katz and Yehuda Lindell, Introduction to Modern Cryptography, 3rd ed., CRC Press, 2020, Chapters 4–5.
Oded Goldreich, Foundations of Cryptography, Vol. 1, Cambridge University Press, 2001, Chapters 2–4.

形式陈述 ​

反向链接

形式陈述