密码学之承诺（Commitment Scheme）

密码学之承诺（Commitment Scheme）

背景和性质

承诺方案源于 Manuel Blum 的论文。在现实生活中有这么一个问题，“猜拳”游戏中，可能某人故意慢那么一点点，看到对方的出拳后，自己才出拳。如何避免这种作弊情况呢？本文的承诺方案可以解决这个问题。

简单思路，使用哈希函数解决“猜拳”游戏中的作弊问题。A 和 B可以按照下面的步骤进行猜拳游戏：

1. A 选择自己的出拳方案（如 $x_1=$"石头"/"剪刀"/"布"），另外再选择一个随机串 $r_1$ ，然后计算哈希值 $H(x_1||r_1)$ ，并把哈希值发送给 B。
2. B 选择自己的出拳方案 $x_2$，另外再选择一个随机串 $r_2$，然后计算哈希 $H(x_2||r_2)$，并把哈希值发送给 A。
3. A 和 B 都收到对方的哈希值后，他们可以把各自的出拳方案和随机串公开给对方并验证，这样，没有人可以作弊。

当然，如果有一个“公正的第三方”，则不用搞这么麻烦，直接 A 和 B 都把自己的出拳方案告诉“公正的第三方”即可。承诺方案的价值就在于：不需要公正的第三方，就可以解决这类问题。

前面例子中的 $r_1$ 和 $r_2$ 被称为随机因子，它们存在的目的是“避免别人通过穷举算出原始的秘密”。 假设 A 不加入随机因子，直接对出拳方案（ $x_1=$"石头"/"剪刀"/"布" ）计算哈希，则 B 可以先算出 3 种出拳方案的哈希，和 A 给出的哈希进行对比就可以知道 A 的出拳方案了，显然这不安全。

承诺的概念是密码学协议设计中的核心。承诺方案允许承诺者发布与消息 $m$ 相关的字符串，即对 $m$ 的承诺。随后承诺者可以选择打开承诺，从而显示 $m$，当然也可以选择不打开承诺。该方案必须是隐藏的（hiding），即承诺不能有助于接收者或者验证者计算关于 $m$ 的任何信息，也就是说对于两个不同的消息 $m_0,m_1$，它们的承诺 $Com(x_0)$ 和 $Com(x_1)$ 是不可区分的。它还必须是绑定的（binding），即承诺者产生一个对 $m$ 的承诺 $c$，但是该承诺不能揭示 $m'\ne m$ [1] ，也就是不能揭示 $m'$ 以外的消息。

主要性质：

• 完美绑定(Perfectly Binding)、计算隐藏(Computationally Hiding)\ 例如：$com(m)=g^m$ 其中 $g$ 是素阶群 $G$ 的生成元，这种承诺在离散对数问题困难性的条件下是完美绑定和计算隐藏的，因为离散对数问题是困难的，在多项式时间内给定 $m$ 的承诺计算出 $m$ 的概率是可忽略的，所以它是计算隐藏的；又因为 $m$ 的承诺无法在给出 $m'\ne m$进行打开，也就是说 $m$ 的承诺只有在消息 $m$ 处打开，在消息 $m$ 以外的消息处无法打开，所以它是完美绑定的。

• 计算绑定(Computationally Binding)、完美隐藏(Perfectly Hiding)\ 例如Pedersen承诺：$com(m;r)=g^mh^r$，$g,h$是素数阶群的生成元，$r$ 是一个随机数。这种承诺在离散对数问题困难性的条件下是计算绑定和完美隐藏的。这是因为，如果 $h=g^x$，那么 $com(m;r)=g^{m+x\cdot r}$，给定一个 $m'\ne m$，存在 $r'$，使得 $m'+r'\cdot x=m+r\cdot x$，也就是说$m$的承诺可以在$m'$处打开，所以它在离散对数困难条件下是计算绑定的；又因为，假设离散对数是容易的，给出承诺也无法获得关于m的任何信息，由于$r$是随机的，即使知道 $y=m+r\cdot x$，有无法计算出 $m$，所以完美隐藏了 $m$。

• 不可延展性(non-malleability)\ 对于某些应用场景来说，我们需要额外的安全属性。这种属性的一个例子就是是不可延展性，这是由Dolev， Dwork和Naor b[2]引入的概念。它防止攻击者根据已有的承诺构造出与原承诺相关的新承诺。

  承诺的不可延展性要求，攻击者即使看到一个对$m$的承诺，也无法构造出一个对$m'$的承诺，这里$m'$与$m$相关，例如$m'=f(m)$。怎么理解呢，还是上面的例子，假设 $com(m)=g^m$，那么我们可以构造一个$2m$的承诺，即$com(2m)=com(m)^2$，甚至可以构造 $m+1$ 的承诺，所以这种承诺是不具有不可延展性的。

不过， 一个 Commitment Scheme 不可能同时满足 Perfectly Hiding 和 Perfectly Binding。 为什么呢？假设一个方案满足 Perfectly Hiding，那么一定存在多个 $m$，对应同一个 $Com(m)$ ，因为存在随机性 $r$，很容易凑出另外的 $m'$ 的承诺就是 $m$ 的承诺。那么一个算力无穷的机器通过穷举可以算出 $Com(m) 背后的那个 $m$ 。而多个 $m$ 对应同一个 $Com(m)$ ，这显然违背了 Perfectly Binding。

实现方法总结

实现不可延展性承诺（Non-Malleable Commitments）的方法通常基于密码学假设（如离散对数、整数分解、哈希函数等），并通过特定的构造技巧确保不能延展出与承诺相关的新承诺。以下是几种经典的具体实现方法：

基于离散对数假设的构造（Pedersen 承诺的扩展）

Pedersen 承诺是一种常见的承诺方案，通过扩展其结构可实现不可延展性。

核心思想：利用素阶群上的离散对数困难问题，引入额外的随机性和约束，使攻击者难以从一个承诺 “变形” 出相关承诺。

构造细节如下:

• 设 $G$ 是大素数阶 $q$ 循环群，$g,h$都是 $G$ 上的生成元。
• 承诺阶段：假设要承诺的消息是 $m$ ，从 $Z_q$ 种选择一个随机数 $r$，计算$c=g^mh^r \text{mod } p$。
• 打开阶段：承诺者公开 $m,r$，验证 $c\xlongequal{?}g^mh^r$。
• 不可延展性分析：若攻击者试图从m的承诺$c=g^mh^r$中构造出$x'=f(x)$的相关承诺$c'=g^{x'}h^{r'}=g^{f(x)}h^{r'}$，需要找到一个与$r$相关的$r'$，由于离散对数的困难性，难以从$c$中提取$r$，从而难以构造与$c$相关的承诺。
• 具有加同态性质

基于 RSA 假设的构造（Fujisaki-Okamoto 承诺[3]）

Fujisaki-Okamoto 承诺方案是一种基于大整数分解难题的密码学承诺方案，由 Eiichiro Fujisaki 和 Tatsuaki Okamoto 在 1997 年提出。

构造细节：

• 选择两个大素数$p,q$（保密），计算$n=pq$，$g\in Z_n^*$，$h\in <g>$（由$g$生成的循环子群），$log_gh$离散对数困难。
• 承诺阶段：输入消息$m$，选择一个随机数$r$，计算 $c=c$ 。
• 打开阶段：验证 $c\xlongequal{?} g^m\cdot h^r \text{mod n}$。

基于哈希函数的构造（带随机化的哈希承诺）

基于哈希函数的承诺是一种高效的承诺方案，构造细节如下：

• 选择一个抗碰撞的hash函数
• 承诺阶段：输入一个消息$m$，选择一个随机串 $r$，计算承诺 $c=hash(m||r)$
• 打开阶段：公开 $m,r$ ，验证者重新计算哈希值验证。

由于hash函数输出的随机性，给出一个与$m$相关的消息$m'$，无法构造出相关承诺。

基于 Trapdoor 承诺的构造

基于 Trapdoor Commitment（陷门承诺）的构造是密码学中一个重要的概念，它在普通承诺方案的基础上增加了一个“陷门”知识，允许知道这个陷门的人能够以不同的方式“打开”承诺，使其对任意消息看起来有效。这在某些特定的协议（如零知识证明、安全多方计算、可否认认证、可编辑区块链等）中非常有用。

陷门承诺方案允许承诺者以信息论安全的方式进行承诺消息，也就是说，给出一个承诺，接收者即使有无限的计算能力，也不会有比随机猜测更好的算法来提取承诺信息。另一方面，当打开消息时，发送方仅在计算上绑定到已承诺的消息。事实上，该方案承认存在一个陷门即知识，它允许以任何可能的方式打开一个承诺（我们也将其称为模糊承诺），这个陷门应该很难有效地被计算。

陷门承诺方案 (Trapdoor Commitment Scheme):

• 在普通承诺方案的基础上，额外引入一个 陷门 (trapdoor) $td$

• 陷门是在系统初始化阶段由某个可信方（或通过分布式协议）生成的秘密信息

• 关键能力：知道陷门 $td$ 的人（称为陷门持有者）可以：

  • 对任意消息 $m$ 生成一个承诺 $com$
  • 可以“打开”这个承诺 $com$ 为任意另一个消息 $m'$（$m'≠m$ 或 $m'=m$），并提供一个有效的打开证据 $(m',r')$ 使得 $Open(com,m',r')$ 接受。
  • 安全属性：
  • 隐藏性(Hiding): 保持不变。知道陷门的人以及不知道陷门的人都无法区分对 $m_0$ 的承诺和对 $m_1$ 的承诺，即无法从承诺中获取关于消息 $m$ 的任何信息。
  • 陷门绑定性 (Trapdoor Binding): 对于不知道陷门 $td$ 的人来说，绑定性仍然成立（他们无法改变承诺）。但是，对于知道陷门 $td$ 的人来说，绑定性被“打破”——他们可以自由地打开承诺为任何消息。

• 基于离散对数问题的陷门承诺构造

  1. 系统参数生成 (Setup - 由可信方执行):
     • 选择一个阶为大素数 $q$ 的循环群 $G$（例如，一个椭圆曲线群），$g$ 是一个生成元。
     • 生成陷门 $td$：选择一个随机数 $x\in Z_q$ 作为陷门。
     • 计算 $h=g^x$。
     • 公开参数$(G,q,g,h)$，保密参数 $td=x$ (陷门)
     • 注意：对外部世界来说，$h$ 看起来像是从群中随机选取的另一个生成元。只有陷门持有者知道 $h=g^x$ 这个关系（即知道离散对数 $x$ ）。

2. 承诺阶段 (Commit):

   • 承诺者想承诺消息 $m\in Z_q$。
   • 选择一个随机数 $r\in Z_q$。
   • 计算承诺：$com = g^m \cdot h^r$
   • 将 $com$ 发送给验证者。

3. 打开阶段 (Open - 普通用户):

   • 承诺者揭示消息 $m$ 和随机数 $r$。
   • 验证者检查：$com\xlongequal{?} g^m \cdot h^r$
   • 如果相等，则接受打开；否则拒绝。

4. 陷门持有者的能力 (Fake Opening):

   • 假设陷门持有者之前（或现在）创建了一个承诺 $com$（可能是用某个 $m$ 和 $r$ 生成的，也可能不是）。
   • 陷门持有者现在想将这个承诺 com “打开”为任意目标消息 $m'\in Z_q$。
   • 利用陷门 $x$ 计算一个伪造的随机数 $r'$：
     • 陷门持有者知道 $com=g^m\cdot h^r$（如果 $com$ 是他自己生成的），或者他可以直接利用陷门关系操作 $com$。
     • 需要找到 $r'$ 使得：$com=g^{m'}\cdot h^{r'}$，代入 $h=g^x$ 得 $g^m\cdot h^r =g^{m'+x\cdot r'}$，因为$g$是生成元，所以指数必相等 $m+xr=m'+xr'$。
     • 解出 $r'：r'=(m-m'+xr)x^{-1}\text{ mod } q$
     • 陷门持有者输出伪造的打开证据 $(m',r')$，它成功地打开了 $com$ 为任意消息 m'。

• 安全性分析 (针对上述构造)
  1. 隐藏性 (Hiding):
     • 承诺 $com = g^m h^r$。
     • 因为 $r$ 是随机选择的，$h^r$ 是群 $G$ 中的一个随机元素（假设 $h$ 也是生成元）。
     • 因此，$g^m h^r$ 也是群中的一个均匀随机元素，完全掩盖了消息 $m$。这提供了完美隐藏性(perfectly hiding)。

2. 绑定性 (Binding - 对不知道陷门的人):

   • 假设攻击者（不知道陷门 $x$）想找到两对 $(m,r)$ 和 $(m', r')$ 且 $m \ne m'$，使得 $g^m h^r = g^{m'} h^{r'}$。这意味着 $g^{m - m'} = h^{r' - r}$。
   • 因为 $h = g^x$ (但攻击者不知道 $x$)，所以 $g^{m - m'} = (g^x)^{r' - r} = g^{x(r' - r)}$。所以，$m - m' = x(r' - r) \text{ mod } q$。
   • 如果攻击者能找到这样的 $m, m', r, r'$ (且 $m \ne m'$)，则意味着 $x=(m-m')(r'-r)^{-1} \text{ mod } q$。
   • 这等价于攻击者计算出了 $x = log_g(h)$，即解决了离散对数问题 (DLP)。
   • 因此，在 DLP 困难的假设下，对于不知道陷门 $x$ 的攻击者来说，该方案是计算上绑定的。

3. 陷门绑定性 (Trapdoor Binding - 对知道陷门的人):

   • 如上面“陷门持有者的能力”部分所示，知道 $x$ 的人可以轻松地为任意消息 $m'$ 计算出一个有效的打开随机数 $r'$，使得承诺 $com$ 被验证为 $m'$。因此，绑定性对他们无效。

ElGamal 承诺（Computationally Hiding, Perfectly Binding）

假设 $G$ 是阶为 $q$ 的循环群，而 $g,h$ 是 $G$ 的两个随机生成元。

ElGamal 承诺的两个阶段：

1. 承诺阶段：待承诺得消息为 $m$，它是 $G$ 中元素，即 $m\in G$ ；在 $Z_q$ 中随机选择 $r$，计算 $com=(g^r,mh^r)$，并将 $com$ 发给对方；
2. 打开阶段：公开 $(m,r)$ ，如果 $com=(g^r,mh^r)$ 成立，则接受它。

为什么 ElGamal 承诺是 Perfectly Binding 的呢？因为公开 $g^r$ 时，$r$ 就唯一确定的了（只是还没有“打开”前暂时不知道）；$r$ 确定后，公开 $mh^r$ 时，$m$ 就唯一确定了。也就是当 $(m,r)$ 不同时，它的承诺一定不一样，所以是完美绑定的。为什么是 Computationally Hiding 的呢？因为假设$c_1=g^r,c_2=mh^r$，若敌手能解离散对数问题（DLP），则 $r=log_gc_1$，$m=c_2\cdot (h^r)^{-1}$，进而求出 $m$，所以基于 DLP 假设，概率多项式时间的敌手只能以一个可忽略的概率获取 $m$。

应用场景

1. 零知识证明 (Zero-Knowledge Proofs):

   在模拟器中，陷门允许模拟器在不提前知道真实证据的情况下产生承诺，并在证明过程中根据需要“打开”它们以满足验证条件，从而证明模拟的零知识性。

2. 安全多方计算 (Secure Multi-Party Computation - MPC):

   某些 MPC 协议使用陷门承诺来实现输入提交阶段的可选绑定性，或者在出现作弊时允许诚实方利用陷门“纠正”协议状态。

3. 可否认认证 (Deniable Authentication):

   接收者（持有陷门）可以否认自己收到过某个特定消息，因为他总能声称发送者后来“打开”了承诺为另一个消息（即使发送者没有这么做）。

4. 可编辑区块链 (Chameleon Hashes):

   陷门承诺的一种特殊形式。陷门持有者（如特定权限节点）可以修改链上特定区块的内容（消息 $m$）并重新计算一个与原始承诺匹配的新随机数 $r'$，而无需改变承诺值（区块哈希），维持链的连续性。

5. 身份管理:

   用于构造可撤销匿名凭证或群签名方案，其中管理员（陷门持有者）在需要时可以“打开”匿名承诺以揭示用户身份。

重要考虑

1. 陷门管理: 陷门 td 是极其敏感的信息。谁持有它？如何安全地生成、存储、分发（如果需要多人持有，如门限方案）？泄露陷门会彻底破坏承诺的绑定性。

2. 绑定性的弱化: 陷门承诺方案的核心特点就是对陷门持有者而言绑定性失效。协议设计者必须明确理解并接受这种弱化的绑定性，并确保它在协议上下文中不会引入安全漏洞（或者引入的安全风险是可控且符合设计目标的）。

3. 构造选择: 基于离散对数的 Pedersen 类构造因其简洁、高效和在标准群（如椭圆曲线）上的易实现性而非常流行。选择哪种构造取决于具体应用需求（如所需的假设、效率、后量子安全性等）。

总结

基于 Trapdoor 的承诺方案通过在系统参数中嵌入一个秘密陷门 $td$，使得陷门持有者能够打破承诺的绑定性，为任意承诺值 $com$ 生成对任意消息 $m'$ 的有效打开证据。经典的 Pedersen-like 构造利用 $h = g^x$ 的离散对数关系实现这一特性，在离散对数问题困难的假设下，对不知道 $x$ 的用户保持隐藏性和计算绑定性。这种方案在零知识证明、安全多方计算、可否认认证和可编辑区块链等高级密码协议中扮演着关键角色，但其安全性高度依赖于陷门的安全管理和对弱化绑定性的正确认识与应用。

文献

[1] Damgard, I., Groth, J.: Non-interactive and reusable non-malleable commitment schemes. In: Proceedings of the thirty-fifth annual ACM symposium on Theory of computing. pp. 426–437. ACM (2003)

[2] Danny Dolev, Cynthia Dwork and Moni Naor: Non-malleable Cryptography, SIAM J.Computing, vol. 30, pp. 391-437, 2000. (Earlier version STOC 1991.)

[3] E. Fujisaki and T. Okamoto: Statistical Zero-Knowledge Protocols to prove Modular Polynomial Relations, In Crypto 97, LNCS 1294, 1997.

[4] https://aandds.com/blog/commitment-scheme.html