密码学 | 承诺：绑定性 + 隐藏性

🥑原文：承诺方案（Commitment）学习笔记
🥑写在前面： 本文属搬运博客，自己留存学习。本文只会讲承诺的两个安全属性，不会再讲解承诺的定义。

正文

承诺方案需要满足两个安全属性：绑定、隐藏。

• 绑定属性： 是指承诺 $c$ 绑定了消息 $m$。承诺方不能用假消息 $m^{\prime }\ne m$ 使得接收方在揭示时输出接受。绑定属性 主要针对不诚实的承诺方。
• 隐藏属性： 是指承诺 $c$ 隐藏了消息 $m$。接收方收到 $c$ 后，不能根据 $c$ 恢复出 $m$。隐藏属性 主要针对不诚实的接收方。

承诺方案的安全定义我翻了很多论文其实都没有详细说的，所以下面给出 WIKI 的定义：

• 绑定属性： 不存在$m^{\prime }\ne m$，使得 $\mathrm{Commit}(\mathrm{m},\mathrm{r})=\mathrm{Commit}({\mathrm{m}}^{\prime },{\mathrm{r}}^{\prime })$。
• 隐藏属性： 令 $\mathcal{R}$ 是所有随机数的集合，对于所有 $m^{\prime }\ne m$，都有 { C o m m i t ( m , R ) } ≡ { C o m m i t ( m ′ , R ) } \{\rm{Commit}(m, \mathcal{R})\} \equiv \{\rm{Commit}(m', \mathcal{R})\} {Commit(m,R)}≡{Commit(m′,R)}。

$Commit()$ 代表生成承诺的方法。看不懂没关系，原博接着就会细讲。

1 绑定的定义

对于绑定，个人感觉现在的定义应该更像是：

给定 $(c,d)\leftarrow \mathrm{Commit}(\mathrm{m},\mathrm{r})$，不存在 $m^{\prime }\ne m$ 和 $d^{\prime }$，使得 $\mathrm{Open}(\mathrm{c},{\mathrm{m}}^{\prime },{\mathrm{d}}^{\prime })=\mathrm{Accept}$。

其中，$c$ 和 $d$ 分别代表承诺值和揭示值。

个人理解：在我之前看到的一些基础承诺方案中，使用的揭示值显然就是 $(m,r)$。但在某些情况下，承诺方可能不希望揭示消息的明文 $m$。因此，承诺方在揭示阶段给接收方一个 $d$ 值，即所谓的揭示值，通过零知识证明来告诉接收方它刚刚传的确实是消息 $m$。

而对于上面的定义，感觉上是一些古老的承诺方案，比如 [DN02]。

在这些古老的承诺方案中，接收方在揭示阶段直接检测：

$$c\stackrel{?}{=}\mathrm{Commit}(\mathrm{m},\mathrm{r})$$

只要不存在$m^{\prime }\ne m$，使得 $\mathrm{Commit}(\mathrm{m},\mathrm{r})=\mathrm{Commit}({\mathrm{m}}^{\prime },{\mathrm{r}}^{\prime })$，就不存在 $m^{\prime }$ 使得揭示阶段输出接受。

而对于现在各种花里胡哨的承诺方案，“不存在 $m^{\prime }\ne m$，使得 $\mathrm{Commit}(\mathrm{m},\mathrm{r})=\mathrm{Commit}({\mathrm{m}}^{\prime },{\mathrm{r}}^{\prime })$” 感觉只是个必要而不充分条件，不过如果揭示阶段设计得好的话估计也可以做到必要充分吧。

2 隐藏的定义

对于隐藏， { C o m m i t ( m , R ) } ≡ { C o m m i t ( m ′ , R ) } \{\rm{Commit}(m, \mathcal{R})\} \equiv \{\rm{Commit}(m', \mathcal{R})\} {Commit(m,R)}≡{Commit(m′,R)}的意思是：

对于所有 $m^{\prime }\ne m$，拿所有的随机数 $r_i\in \mathcal{R}$ 分别跟 $m$ 和 $m^{\prime }$ 生成承诺，它们结果的集合相同。换句话说，给定一个承诺值 $c$，它有可能由任意一个 $m_i\in \mathcal{M}$ 承诺出来的，其中 $\mathcal{M}$ 是指明文空间。所以知道了 $c$ 也不会泄露 $m$ 的任何信息。

个人理解：对于消息 $m$，假设 $m$ 和所有随机数 $r_i$ 生成的承诺值 $c=Commit(m,r_i)$ 的集合为 $\mathcal{C}$。那么对于消息 $m^{\prime }\ne m$，$m^{\prime }$ 和所有随机数 $r_i$ 生成的承诺值 $c=Commit(m^{\prime },r_i)$ 的集合等于 $\mathcal{C}$。因此，对于集合 $\mathcal{C}$ 中的一个 $c$ 值，任何一个 $m$ 都能生成它。

下面是本人画的示意图，但不知道对不对：
上图表示，$m_i\in \mathcal{M}$ 和所有随机数 $r_i\in \mathcal{R}$ 生成的承诺值 $c_i=Commit(m_i,r_i)$ 构成集合 $\mathcal{C}$。蓝线和红线表示，不同的消息 $m$ 和 $m^{\prime }$，与不同的随机数 $r$ 和 $r^{\prime }$，能够生成相同的承诺 $c$。

这里我把随机数和承诺值的个数画成了一样的。因为我觉得，一个消息 $m$ 和不同的随机数 $r$ 生成的 $c$ 应该不会存在重复的情况吧？所以画成了 $r$ 和 $c$ 一对一的关系。

3 完美绑定和计算绑定

在上述绑定和隐藏的定义中，其实还有安全性的强弱之分。

如果绑定定义中的 “不存在” 是真的 “不存在”，那就是 完美绑定。也就是说，即使攻击者具有无限计算能力，比如可以遍历整个明文空间 $\mathcal{M}$ 之类的，也不能找到两个承诺值相同的消息。

如果只是计算上的 “不存在”，那就是 计算绑定。也就是说，可能存在 $m^{\prime }\ne m$，使得 $\mathrm{Commit}(\mathrm{m},\mathrm{r})=\mathrm{Commit}({\mathrm{m}}^{\prime },{\mathrm{r}}^{\prime })$，但是不能在多项式时间内计算出来。

但是具有无限计算能力的攻击者可以找到这样的 $m^{\prime }$。

4 完美隐藏和计算隐藏

如果隐藏定义中的 “$\equiv$” 是真的 “相等”，那就是 完美隐藏。也就是说，具有无限计算能力的攻击者也不能根据 $c$ 恢复 $m$。

如果 “$\equiv$” 只是计算上的 “相等”（即 $\stackrel{c}{\equiv }$），那就是 计算隐藏。也就是说，但是不能在多项式时间内恢复 $m$。

同样地，具有无限计算能力的攻击者可以找到这样的 $m^{\prime }$。

5 二者不可兼得

完美的安全性显然比计算上的安全性高。但坏消息是，绑定和隐藏是不能同时做到完美的。

这个可以简单从定义上推出：

如果不存在 $m^{\prime }\ne m$，使得 $\mathrm{Commit}(\mathrm{m},\mathrm{r})=\mathrm{Commit}({\mathrm{m}}^{\prime },{\mathrm{r}}^{\prime })$，那么就不会有 { C o m m i t ( m , R ) } ≡ { C o m m i t ( m ′ , R ) } \{\rm{Commit}(m, \mathcal{R})\} \equiv \{\rm{Commit}(m', \mathcal{R})\} {Commit(m,R)}≡{Commit(m′,R)}。

个人理解：如果 $m^{\prime }$ 和 $m$ 能各自生成不同的承诺值，那么它们的承诺值集合 $\mathcal{C}$ 必不相同。

下面是本人画的示意图，但不知道对不对：

如上图所示，完美绑定 应该是要求 $m_1$ 和 $m_2$ 各自的承诺值集合 $C_1$ 和 $C_2$ 毫无交集。

相似地，如果对于所有 $m^{\prime }\ne m$，都有 { C o m m i t ( m , R ) } ≡ { C o m m i t ( m ′ , R ) } \{\rm{Commit}(m, \mathcal{R})\} \equiv \{\rm{Commit}(m', \mathcal{R})\} {Commit(m,R)}≡{Commit(m′,R)}，那么就会存在 $m^{\prime }\ne m$，使得 $\mathrm{Commit}(\mathrm{m},\mathrm{r})=\mathrm{Commit}({\mathrm{m}}^{\prime },{\mathrm{r}}^{\prime })$。

个人理解：同样地，如果 $m^{\prime }$ 和 $m$ 的承诺值集合 $\mathcal{C}$ 相同，那么它们肯定能生成相同的承诺值 $c$，不管它们分别是跟哪个 $r_i$ 生的。

6 论文写法举例

🥑原文：Toward Achieving Anonymous NFT Trading

There are two properties of the Pederson commitment: perfectly binding and computational hiding.

翻译：Pederson 承诺具有两个属性：完美绑定性和计算隐藏性。

Perfectly binding represents that for Alice, the possibility of outputting $Commit(m,r)=Commit(m^{\prime },r^{\prime })$ where $m\ne m^{\prime }$ is negligible even if Alice has unbounded computational power. This means once a commitment is made, the commitment $com$ is uniquely linked to the commit message $m$.

翻译：完美绑定性表示，即使对于具有无限计算能力的 Alice 来说，她能找到 $Commit(m,r)=Commit(m^{\prime },r^{\prime })$ 且 $m\ne m^{\prime }$ 的概率也是微乎其微的。这意味着一旦一个承诺被做出，这个承诺 $com$ 唯一地与消息 $m$ 相关联。

On the other hand, computational hiding represents that for $m\ne m^{\prime }$, the probability ensembles $Commit(m,R)$ and $Commit(m^{\prime },R)$ with $R$ being a uniform distribution over $2^k$ are computationally indistinguishable. It means for a probabilistic polynomial-time adversary, it cannot extract any useful information about $m$ before the opening.

翻译：另一方面，计算隐藏性表示对于任意的 $m\ne m^{\prime }$，当 $R$ 是在 $2^k$ 上的均匀分布时，承诺值集合 $Commit(m,R)$ 和 $Commit(m^{\prime },R)$ 在计算上是不可区分的。这意味着对于一个概率多项式时间的敌手来说，在揭示阶段之前，它无法提取关于 $m$ 的任何有用信息。

附：中英文对照

• 隐藏 - hiding
• 绑定 - binding
• 完美隐藏/绑定 - perfectly hiding/binding
• 计算隐藏/绑定 - computational hiding/binding
• 无限计算能力 - unbounded computational power
• 概率多项式时间 - probabilistic polynomial-time
• 敌手 - adversary