承诺方案（Commitment）学习笔记 1.2

更新：由于这篇文章的内容大部分是我的脑洞，所以我不能确保正确性，目前我已经把文章设为隐藏状态，如果你碰巧访问到这篇文章，请自行辨识内容的正确性。

PS：关于非交互承诺方案的一些更严谨的内容目前被写在了我的硕士论文中，在我大论文完成后我也会公开这些内容，所以，别急（

以下是正文：

事情是这样的，上次写的笔记内容被我用在某个期末作业上了，由于是写作业上的所以表述会正规一点，而且写的时候也加了新东西，所以可以再水一篇贴了。

正文·

简介·

承诺方案（Commitment Scheme）如其名，就是在模拟一个“作出承诺”和“兑现承诺”的过程，但和现实的承诺不同，密码学中的承诺通常是在承诺发送者不会改变某个值，然后在兑现承诺的时候把这个值发送给接收者，接收者收到后验证这个值是否真的没被改变。

承诺（Commitment）的概念最早由[B83]提出，而较正式的承诺方案则在[BCC88]提出，[BCC88]提出的是单比特的承诺方案（Bit Commitment Scheme），目前承诺方案被广泛应用于抛币协议、零知识证明、安全多方计算等协议中，在[C01]提出通用可组合框架（Universally Composable，下简称UC）以后，这些协议相继提出了UC模型下的版本，承诺方案也不例外，最先提出UC模型下承诺方案的是[CF01]，目前（我所了解的）被认为最快的且在UC模型下、不使用Random Oracle的、可承诺任意比特的承诺方案是[Lin11]提出的承诺方案。

定义·

承诺方案有两个参与者：发送方（Sender）和接收方（Receiver）；承诺方案还有两个阶段：承诺（Commit）和打开（Open）。

在承诺阶段中，发送方承诺某个不会改变的值$m$，利用$m$和随机性$r$计算并发送承诺值$c$给接收方。在打开阶段中，发送方须发送值$m$和一个用于辅助打开承诺的打开值（Opening Value）$d$给接收方，接收方利用收到的$m$、$d$和$c$验证（Verify）$m$是否没被发送方或其他攻击者更改，若验证通过则接受（Accept），否则拒绝（Reject）。大概过程见下图：

$$\begin{array}{|lc|} \hline \\ \begin{array}{c} \rm{Commit: } \\ \\ \\ \\ \rm{Open: } \end{array} & \begin{array}{lcl} \mathrm{Sender}(m) & \ \ \ \ \ \ \ \ \ \ \ \ \ \ & \mathrm{Receiver} \\ \begin{array}{l} \rm{Com}(m, r) \rightarrow (c, d) \end{array} & & \\ & \overset{c}{\longrightarrow} & \\ \vdots & & \\ & \overset{m,\ d}{\longrightarrow} & \\ & & \begin{array}{l} \rm{Verify(c, m, d)} \rightarrow \text{Accept/Reject} \end{array} \\ \end{array} \\ \hline \end{array}$$

作为一个协议，首先要拥有正确性，一个是取值范围的问题：假设消息的取值范围是$\mathcal{M}$、随机数的取值范围是$\mathcal{R}$、承诺值的范围是$\mathcal{C}$、打开值得范围是$\mathcal{D}$，“$\overset{\$}{\leftarrow}$”表示随机选取，则会有：

$$\begin{array}{ccc} \begin{array}{l} m \in \mathcal{M} \rm{;} \ \ \ r \in \mathcal{R} \rm{;} \\ \rm{Com}(m, r) \rightarrow (c, d) \end{array} & \Rightarrow & \begin{array}{l} c \in \mathcal{C} \rm{;} \ \ \ d \in \mathcal{D} \rm{;} \\ \end{array} \end{array}$$

另一个是，若承诺值和打开值是按正确流程生成的，则一定会通过验证：

$$\begin{array}{ccc} \begin{array}{l} m \in \mathcal{M} \rm{;} \ \ \ r \in \mathcal{R} \rm{;} \\ \rm{Com}(m, r) \rightarrow (c, d) \end{array} & \Rightarrow & \begin{array}{l} \rm{Verify(c, m, d)} = \text{Accept} \end{array} \end{array}$$

安全属性·

除了上面的流程，承诺方案还需要满足两个安全属性：绑定（Binding）和隐藏（Hiding），很遗憾在我目前看到的论文里都没有这两个安全属性的形式化定义，大多论文都选择使用自然语言去定义，目前看到最多的定义如下：

• 绑定属性：定义一：承诺方不能用两个不同的$m \ne m'$承诺出同样的承诺值$c$；定义二：承诺方生成的承诺值$c$在打开时不能被两个不同的$m \ne m'$通过验证。
• 隐藏属性：接收方不能根据接收到的承诺值$c$恢复出$m$。

显然，绑定针对的是不诚实的承诺方，隐藏则是不诚实的接收方。

对绑定属性的一点看法·

绑定属性的定义会有点歧义，在目前的论文里，定义一和定义二都有出现，但在我看来，定义二会更准确，因为定义一的安全性并不用考虑打开阶段。而且根据承诺方案的正确性，若有两个不同的$m \ne m'$承诺出同样的承诺值$c$，那么$c$也应该要被$m$和$m'$通过验证，也即其逆否命题也成立：若一个承诺值$c$不能被两个不同的$m \ne m'$通过验证，则不会有两个不同的$m \ne m'$承诺出同样的承诺值$c$，符合定义二可推出符合定义一（$② \Rightarrow ①$）。

另外，感觉上如果只按照定义一实现绑定的话，可以在打开阶段设置后门，而达到设计虽符合了安全定义但是却不安全的协议。举个较极端的例子，假设我设计一个符合上述绑定属性定义一和隐藏属性的承诺方案（简单地用一个加密函数或者单向函数作$\rm{Com}$即可符合），但是在打开阶段的验证函数无论输入是什么都输出接受，即$\rm{Verify(c, m, d)} \overset{\text{always}}{\rightarrow} \text{Accept}$，根据加密函数或者单向函数性质，这个承诺方案都满足绑定属性的定义一和隐藏属性的定义，但显然这不是一个可以使用的承诺方案，因为无论承诺方承诺什么，接收方都只能接受。

上述的绑定属性定义一的出现，我认为是历史原因导致的。以往的承诺方案其实并不复杂，通常是发送方使用加密函数或者单向函数对信息$m$进行加密或映射，在打开时接收方使用接收到的$m$进行重加密或重映射，然后对比得到的结果是否跟$c$一致，若一致则接受，否则拒绝。在这样的构造下，承诺阶段的操作与打开阶段的几乎一样，没有有两个不同的信息承诺出相同的承诺值的话自然也不会有一个承诺值可以被两个不同的信息通过验证，换句话说，在这种情况下，符合定义一可以推出符合定义二（$② \Leftrightarrow ①$）。

形式化定义的尝试·

上面说了，目前我所看的论文里都没有出现绑定和隐藏这两个安全属性的形式化定义，但是根据自然语言的定义给出形式化定义其实是可行的，所以下面我就进行一番尝试，给出针对这两个安全属性的攻击者的优势（Advantage），可以理解为攻击者攻击成功的概率。假设消息的取值范围是$\mathcal{M}$、随机数的取值范围是$\mathcal{R}$、承诺值的范围是$\mathcal{C}$、打开值得范围是$\mathcal{D}$，“ $\overset{\$}{\leftarrow}$ ”表示随机选取。

不诚实得发送者$\text{A}_\text{S}$攻破绑定属性的优势可以表示为：

$$\text{Adv}_\text{Binding}(A_S) = \text{Pr}\begin{bmatrix} \begin{array}{ccc} \begin{array}{l} \rm{Verify(c, m, d)} = \text{Accept} \\ \rm{Verify(c, m', d')} = \text{Accept} \end{array} & \rm{:} & \begin{array}{l} (c, m, m', d, d') \leftarrow \text{A}_\text{S} \rm{;} \\ m, m' \in \mathcal{M} \rm{;} \ \ \ m \ne m' \rm{;} \\ d, d' \in \mathcal{D} \rm{;} \ \ c \in \mathcal{C} \end{array} \end{array} \end{bmatrix}$$

不诚实的接收者$\text{A}_\text{R}$攻破隐藏属性的优势可以表示为：

$$\text{Adv}_\text{Hiding}(\text{A}_\text{R}) = \text{Pr}\begin{bmatrix} \begin{array}{ccc} \begin{array}{l} m = m' \end{array} & \rm{:} & \begin{array}{l} m \overset{\$}{\leftarrow} \mathcal{M} \rm{;} \ r \overset{\$}{\leftarrow} \mathcal{R} \rm{;} \\ (c, d) \leftarrow \rm{Com}(m, r) \rm{;} \\ m' \leftarrow \text{A}_\text{R}(c) \end{array} \end{array} \end{bmatrix}$$

除了上述我编的定义，记$c_{m, r}$为$\rm{Com}(m, r)$得到的承诺值，目前还流传着其他的定义，常见的如（这里为了与上面的表述相一致，在不改变意思的情况下做了修改）：

• 绑定属性（定义一）：$\forall m,m' \in \mathcal{M},\ \forall r,r' \in \mathcal{R},\ m' \ne m \Rightarrow c_{m, r} \ne c_{m', r'}$。按我的理解，还可以被写作：

  $$\text{Adv}^{'}_\text{Binding}() = \text{Pr}\begin{bmatrix} \begin{array}{ccc} \begin{array}{l} c = c' \end{array} & \rm{:} & \begin{array}{l} m \ne m' \overset{\$}{\leftarrow} \mathcal{M} \rm{;} \ \ r, r' \overset{\$}{\leftarrow} \mathcal{R} \rm{;} \\ (c, d) \leftarrow \rm{Com}(m, r) \rm{;} \\ (c', d') \leftarrow \rm{Com}(m', r') \end{array} \end{array} \end{bmatrix}$$

• 隐藏属性：通常会被简化表述为$\forall m,m' \in \mathcal{M},\ \{c_{m, \mathcal{R}}\} = \{c_{m', \mathcal{R}}\}$。按我的理解，还可以被写作（在$\text{Adv}_\text{Hiding}(\text{A}_\text{R})=0$时等号成立）：

  $$\text{Adv}_\text{Hiding}(\text{A}_\text{R}) \le \text{Adv}^{'}_\text{Hiding}() = \text{Pr}\begin{bmatrix} \begin{array}{ccc} \begin{array}{l} \mathcal{C}_m \ne \mathcal{C}_{m'} \end{array} & \rm{:} & \begin{array}{l} m \ne m' \overset{\$}{\leftarrow} \mathcal{M} \rm{;} \\ \mathcal{C}_m = \{c\ |\ (c, d) \leftarrow \rm{Com}(m, r)\rm{;}\ r \in \mathcal{R} \} \\ \mathcal{C}_{m'} = \{c'\ |\ (c', d') \leftarrow \rm{Com}(m', r')\rm{;}\ r' \in \mathcal{R} \} \end{array} \end{array} \end{bmatrix}$$

这两个定义的好处是并不用考虑攻击者，即只要构造符合某种属性的$\rm{Com}$就可以构造出安全的承诺方案，而且使用在各种证明中都会更简洁，但遗憾的是目前并没有找到绑定属性中定义二的类似表述。$\text{Adv}^{'}_\text{Binding}()$的表述很直观，几乎只是大白话的翻译。$\text{Adv}^{'}_\text{Hiding}()$的大概意思是，若攻击者可以找到$m \ne m'$使得$\mathcal{C}_m \ne \mathcal{C}_{m'}$，那么就会存在$r, r' \in \mathcal{R}$，使得$c_{m, r}$、$c_{m', r'}$可以区分$m$、$m'$。$\text{Adv}^{'}_\text{Hiding}()=0$时，$\mathcal{M}$中的每个$m$承诺出来的承诺值分布都一样，那么攻击者拿到任何一个$c \in \mathcal{C}$也不会知道是由哪一个或者哪几个$m \in \mathcal{M}$产生的，自然也无法恢复出消息$m$，也即$\text{Adv}_\text{Hiding}(\text{A}_\text{R})=0$。

也许还可以写出另一个区分性的版本：

$$\text{Adv}_\text{Hiding}(\text{A}_\text{R}) \le \text{Adv}^{''}_\text{Hiding}(\text{A}_\text{R}) = \begin{vmatrix} Pr\begin{bmatrix} \begin{array}{ccc} \begin{array}{l} b = b^* \end{array} & \rm{:} & \begin{array}{l} m_0 \ne m_1 \leftarrow \text{A}_\text{R}() \rm{;} \\ b^* \overset{\$}{\leftarrow} \{0, 1\} \rm{;} \ r \overset{\$}{\leftarrow} \mathcal{R} \rm{;} \\ (c^*, d) \leftarrow \rm{Com}(m_{b^*}, r) \rm{;} \\ b \leftarrow \text{A}_\text{R}^{\rm{Ora}(·)}(c^*) \end{array} \end{array} \end{bmatrix} - \frac{1}{2} \end{vmatrix}$$

其中

$$\rm{Ora}(m) := \begin{Bmatrix} \begin{array}{l} r \overset{\$}{\leftarrow} \mathcal{R} \rm{;} \ (c, d) \leftarrow \rm{Com}(m, r) \rm{;} \\ \text{Output: } (c, d) \end{array} \end{Bmatrix}$$

完美安全和计算上安全·

上述的绑定和隐藏属性其实还各自分两个安全等级：完美（Perfect）安全和计算上（Computational）安全。所谓完美安全，就是即使是有无限能力（Unbounding）的攻击者也不可能攻破这个安全属性；所谓计算上安全，就是攻击者能攻破该属性的概率可以被忽略，或者说攻击者在多项式时间内不可能攻破。

有了上面的几个定义，这两个安全等级就很好解释了：

• 完美绑定（Perfectly Binding）：$\text{Adv}_\text{Binding}(\text{A}_\text{S}) = 0$，或者至少需要$\text{Adv}^{'}_\text{Binding}() = 0$，因为前面说了$\rm{定义二} \Rightarrow \rm{定义一}$，定义一是定义二的一个必然条件；
• 计算上绑定（Computationally Binding）：$\text{Adv}_\text{Binding}(\text{A}_\text{S}) = \rm{negl}$，或者至少需要$\text{Adv}^{'}_\text{Binding}() = \rm{negl}$，其中$\rm{negl}$为可忽略（Negligible）；
• 完美隐藏（Perfectly Hiding）：$\text{Adv}_\text{Hiding}(\text{A}_\text{R}) = 0$，或者$\text{Adv}^{'}_\text{Hiding}() = 0$；
• 计算上隐藏（Computationally Hiding）：$\text{Adv}_\text{Hiding}(\text{A}_\text{R}) = \rm{negl}$，或者$\text{Adv}^{'}_\text{Hiding}() = \rm{negl}$。

明显，完美安全的安全性比计算上安全的安全性高，但坏消息是，不能同时实现完美绑定和完美隐藏，粗略的论证如下：假设$\text{Adv}^{'}_\text{Binding}() = 0$且$\text{Adv}^{'}_\text{Hiding}() = 0$，首先根据$\text{Adv}^{'}_\text{Hiding}() = 0$会有：

$$\forall m \ne m' \in \mathcal{M} \rm{;} \\ \{c\ |\ (c, d) \leftarrow \rm{Com}(m, r)\rm{;}\ r \in \mathcal{R} \} = \{c'\ |\ (c', d') \leftarrow \rm{Com}(m', r')\rm{;}\ r' \in \mathcal{R} \}$$

由两个集合的相等可以推出：

$$\forall m \ne m' \in \mathcal{M} \rm{;} \ \ \exist r, r' \in \mathcal{R} \rm{;} \\ s.t.\ \ c = c' \rm{;}\ \ (c, d) \leftarrow \rm{Com}(m, r)\rm{;}\ \ (c', d') \leftarrow \rm{Com}(m', r')$$

而\rm{Adv}^{'}_\rm{Binding}() = 0会有：

$$\forall m \ne m' \in \mathcal{M} \rm{;} \ \ \forall r, r' \in \mathcal{R} \rm{;} \\ c \ne c' \rm{;}\ \ (c, d) \leftarrow \rm{Com}(m, r)\rm{;}\ \ (c', d') \leftarrow \rm{Com}(m', r')$$

两者矛盾，所以$\text{Adv}^{'}_\text{Binding}() = 0$和$\text{Adv}^{'}_\text{Hiding}() = 0$不能同时成立，完美绑定和完美隐藏不能同时实现。

所以在构造承诺方案时，通常会选择“完美绑定+计算上隐藏”或者“计算上绑定+完美隐藏”的组合，实在没办法的情况下才会选择“计算上绑定+计算上隐藏”的组合。

模棱两可和提取·

模棱两可和提取是两个后门属性，常用于构造通用可组合（UC）安全的承诺方案：

• 模棱两可（Equivocality）属性：指在知道且仅在知道某个后门值时，可以对一个已经对一个消息$m$做出的承诺在打开时解释为任意不同消息$m'$的承诺，且不被接收方发现，即根据$m \ne m' \in \mathcal{M}\text{;}$ $r \in \mathcal{R}\text{;}$，可以计算出$d' \in \mathcal{D}$，使得$\text{Verify}(c_{m, r}, m', d') = \text{Accept}$。
• 提取（Extractability）属性：指在知道且仅在知道某个后门值时，可以仅根据承诺值$c_{m, ·}$提取消息$m$。

由于后门的存在，构造满足模棱两可或提取的承诺方案通常会使用公钥系统，即会有一个密钥生成函数$\rm{Gen}$生成一个公钥和后门的对$(pk, td)$，在仅知道公钥$pk$的情况下无法（或计算上不能）恢复后门$td$，$\rm{Com}$操作和$\rm{Verify}$操作均需要使用公钥$pk$，记作$\rm{Com}_{pk}$和$\rm{Verify}_{pk}$。

下面说一下形式化定义，同样由于在现有文献中没找到详细的定义，于是就按照自己的理解编一个：

• 密钥生成：$(pk, td) \leftarrow \rm{Gen}(1^\kappa)$，其中$1^\kappa$为安全系数；
• 模棱两可：$(c, d) \leftarrow \rm{Com}_{pk}(m, r)$，$m \ne m' \in \mathcal{M}$，$r \in \mathcal{R}$，$(c, d) \leftarrow \rm{Com}(m, r)$，则$d' \leftarrow \rm{Equiv}_{td}(m, m', d)$，其中$d' \in \mathcal{D}$且$\rm{Verify}_{pk}(c, m', d') = \text{Accept}$，由于不能被接收方发现做了假承诺，还需要$\exist r' \in \mathcal{R}\ s.t.\ \rm{Com}_{pk}(m', r') = (c, d')$（或者说不存在这样的$r'$的概率可忽略？又或者存在但是接收方能找到的概率可忽略？）；
• 提取：$(c, d) \leftarrow \rm{Com}_{pk}(m, r)$，$m \ne m' \in \mathcal{M}$，$r \in \mathcal{R}$，则$m \leftarrow \rm{Extra}_{td}(c)$。

由于在通用可组合框架中，$\rm{Equiv}_{td}$和$\rm{Extra}_{td}$都是由模拟者（Simulator）操作的，结合通用可组合框架中的证明套路，还可以借助模拟者的优势给出定义：

• 模拟者的模棱两可优势：

  $$\text{Adv}_\text{Equiv}(\text{S}_\text{S}) = Pr\begin{bmatrix} \begin{array}{ccc} \begin{array}{l} \rm{Verify}_{pk}(c, m', d') = \text{Accept} \end{array} & \rm{:} & \begin{array}{l} c \leftarrow \text{S}_\text{S}() \rm{;} \ c \in \mathcal{C} \rm{;} \\ m' \overset{\$}{\leftarrow} \mathcal{M} \rm{;} \\ d' \leftarrow \text{S}_\text{S}^{td}(m') \end{array} \end{array} \end{bmatrix} \ge 1 - \rm{negl}$$

• 模拟者的提取优势：

  $$\text{Adv}_\text{Extra}(\text{S}_\text{R}) = Pr\begin{bmatrix} \begin{array}{ccc} \begin{array}{l} m = m' \end{array} & \rm{:} & \begin{array}{l} m \overset{\$}{\leftarrow} \mathcal{M} \rm{;} \ \ r \overset{\$}{\leftarrow} \mathcal{R} \rm{;} \\ (c, d) \leftarrow \rm{Com}_{pk}(m, r) \rm{;} \\ m' \leftarrow \text{S}_\text{S}^{td}(c) \end{array} \end{array} \end{bmatrix} \ge 1 - \rm{negl}$$

模棱两可和提取属性的存在直观上好像会分别和前文的绑定属性和隐藏属性相矛盾，从而影响协议的安全性，但其实不然，因为模棱两可和提取均需要知道后门，而在实际的协议设计中，密钥是由一个安全的第三方生成、分发和保管的（如UC框架中的承诺方案），安全第三方并不会泄露后门，而仅知道公钥$pk$的情况下后门无法（或计算上不能）被恢复，所以$\rm{Equiv}_{td}$和$\rm{Extra}_{td}$方法仅有安全第三方可以使用，但这个第三方并不会攻击协议的参与方，所以协议还是安全的。

但是后门的存在会对完美安全属性有影响，结果是，若承诺方案可模棱两可，则不能实现完美绑定；若可提取，则不能实现完美隐藏。完美安全要求的是“无限能力的攻击者也不可能攻破”，而无限能力的攻击者是可以算出后门的，所以自然地，若协议有模棱两可属性，则无限能力的攻击者可以实现$\rm{Equiv}_{td}$，从而可以对不同的消息做出相同的承诺，攻破完美绑定属性；类似地，若协议有提取属性，则无限能力的攻击者可以实现$\rm{Extra}_{td}$，从而可以根据承诺值恢复消息，攻破完美隐藏属性。

更进一步，直觉上（其实这里的证明我也不太确定是否正确，所以只是直觉上），只有实现了完美绑定才会有提取属性；只有实现了完美隐藏才会有模棱两可。首先假设协议拥有提取属性，但是没有完美绑定属性，则会存在$m \ne m' \in \mathcal{M}$和$r, r' \in \mathcal{R}$，使得$c_{m, r} = c_{m', r'}$，那么在提取$c_{m, r}$或者$c_{m', r'}$时，就会有$m$和$m'$两种可能，攻击者无法分辨哪个才是诚实发送方真正承诺的消息，所以若没有完美绑定属性则没有提取属性；类似地，假设协议拥有模棱两可属性，但是没有隐藏属性，则会存在$m,m' \in \mathcal{M}$使得$\ \{c_{m, \mathcal{R}}\} \ne \{c_{m', \mathcal{R}}\}$，也即存在$r \in \mathcal{R}$，使得$c_{m, r} \not\in \{c_{m', \mathcal{R}}\}$，则不存在$r' \in \mathcal{R}$使得$\rm{Com}_{pk}(m', r') = (c, d')$，即如果恰好选择到这样的$m$和$m'$时，模棱两可会被接收者发现进而失败，所以若没有完美隐藏属性则没有模棱两可属性。

由于前文论证了“不能同时实现完美绑定和完美隐藏”，所以结合可以推出提取属性和模棱两可属性直觉上也不能同时实现。

从函数性质看安全属性·

下面给出一些可能的非通用可组合框架（Plain Model）下的承诺方案构造思路，这里首先分析完美绑定或者完美隐藏的一些特性。

从单射函数到完美绑定·

复习一下完美绑定的一个必要条件，$\forall m,m' \in \mathcal{M},\ \forall r,r' \in \mathcal{R},\ m' \ne m \Rightarrow c_{m, r} \ne c_{m', r'}$，然后对比一下单射函数的定义：

$$\forall a, b \in \mathcal{X},\ a \ne b \Rightarrow f(a) \ne f(b)$$

可以看出两者的表述是相似的，也就是说，如果令$\rm{Com}^c(m, r) \rightarrow c_{m, r}$，只有$\rm{Com}^c(m, r)$可被构造为一个单射函数，该承诺方案才会拥有完美绑定属性。或者换个说法，令$\rm{Com}_{r}^c(m) \rightarrow c_{m, r}$，需要符合下面两点：

• $\forall m, m' \in \mathcal{M}\rm{;}\ \forall r \in \mathcal{R}\rm{;}\ m \ne m' \Rightarrow \rm{Com}_{r}^c(m) \ne \rm{Com}_{r}^c(m')$；

• $\forall r, r' \in \mathcal{R}, r \ne r' \Rightarrow \{\rm{Com}_{r}^c(\mathcal{M})\} \cap \{\rm{Com}_{r'}^c(\mathcal{M})\} = \empty$。

简单论证一下：假设存在$m \ne m' \in \mathcal{M}$和$r, r' \in \mathcal{R}$使得$\rm{Com}_{r}^c(m) = \rm{Com}_{r'}^c(m')$，由第二点的两集合无交集可得只能$r = r'$，即$\rm{Com}_{r}^c(m) = \rm{Com}_{r}^c(m')$，由第一点的单射可得只能$m = m'$，与假设矛盾，所以这样不同的$m$和$m'$不存在，即推出$\forall m,m' \in \mathcal{M},\ \forall r,r' \in \mathcal{R},\ m' \ne m \Rightarrow c_{m, r} \ne c_{m', r'}$。另外，若令$\rm{Com}_{m}^c(r) \rightarrow c_{m, r}$，也可以推出类似的条件。

根据以上推出的特性，可以尝试粗略地设计一种完美绑定的承诺方案的通用构造。假设$F$是一个函数簇，对于所有的$r\in \mathcal{R}$，$F_r:\mathcal{M} \rightarrow \mathcal{F}$，$G: \mathcal{R} \rightarrow \mathcal{G}$是两个单射的函数，则一种完美绑定的承诺方案可以这样设计：

$$\text{A Toy Commitment Scheme with Perfectly Binding} \\ \begin{array}{|lc|} \hline \\ \begin{array}{c} \rm{Commit: } \\ \\ \\ \\ \\ \\ \\ \rm{Open: } \\ \\ \\ \\ \end{array} & \begin{array}{lcl} \mathrm{Sender}(m) & \ \ \ \ \ \ \ \ \ \ \ \ \ \ & \mathrm{Receiver} \\ \begin{array}{l} r \overset{\$}{\leftarrow} \mathcal{R} \\ f = F_r(m) \\ g = G(r) \\ c = (f, g) \end{array} & & \\ & \overset{c}{\longrightarrow} & \\ \vdots & & \\ \\ \begin{array}{l} d = r \end{array} & & \\ & \overset{m,\ d}{\longrightarrow} & \\ & & \begin{array}{lll} \text{If } f = F_d(m) \text{ and } g = G(d) & \rightarrow & \text{Accept} \\ \text{Otherwise} & \rightarrow & \text{Reject} \end{array} \\ \end{array} \\ \hline \end{array}$$

注：以上的构造只能保证完美绑定属性，如果还要计算上隐藏属性的话，还需要$F$和$G$拥有其他的性质。

以上完美绑定属性的论证并不难，首先假设攻击者可攻破完美绑定属性，则可以找到一个与$m$不同的$m' \in \mathcal{M}$，使得接收者输出接受；而若接收者输出接受则必须$f = F_d(m)$且$g = G(d)$，由于$G$是单射的且$d=r$，即$f = F_r(m)$；所以若攻击者可以攻破完美绑定，即可以找到$m' \ne m$使得$F_r(m') = f = F_r(m)$，和$F_r$的单射属性相矛盾，所以不存在这样的攻击者。

可以参考实际的例子，ElGamal承诺方案就是利用类似的思路构造的。令$\mathbb{G} = <g>$是一个素数$q$阶的循环群，$h, g \in \mathbb{G}$是两个随机的生成元，消息$m \in \mathbb{G}$，则ElGamal承诺方案可以表示为：

$$\text{ElGamal Commitment Scheme} \\ \begin{array}{|lc|} \hline \\ \begin{array}{c} \rm{Commit: } \\ \\ \\ \\ \\ \\ \\ \rm{Open: } \\ \\ \\ \\ \end{array} & \begin{array}{lcl} \mathrm{Sender}(m) & \ \ \ \ \ \ \ \ \ \ \ \ \ \ & \mathrm{Receiver} \\ \begin{array}{l} r \overset{\$}{\leftarrow} \mathbb{Z}_q \\ c_0 = mh^r \\ c_1 = g^r \\ c = (c_0, c_1) \end{array} & & \\ & \overset{c}{\longrightarrow} & \\ \vdots & & \\ \\ \begin{array}{l} d = r \end{array} & & \\ & \overset{m,\ d}{\longrightarrow} & \\ & & \begin{array}{lll} \text{If } c = (mh^r, g^r) & \rightarrow & \text{Accept} \\ \text{Otherwise} & \rightarrow & \text{Reject} \end{array} \\ \end{array} \\ \hline \end{array}$$

令$F_r(m) = mh^r$、$G(r) = g^r$这就是上面通用构造的一个实例化，显然$F_r(m)$和$G(r)$都是单射函数。

从满射函数到完美隐藏·

先复习一下完美隐藏的定义：$\forall m,m' \in \mathcal{M},\ \{c_{m, \mathcal{R}}\} = \{c_{m', \mathcal{R}}\}$，这里假设$\mathcal{C}$中不包含多余的承诺值，即$\mathcal{C} = \{ c_{m, r}\ |\ m \in \mathcal{M}\rm{;}\ r \in \mathcal{R} \}$，则可以得到$\forall m \in \mathcal{M},\ \{c_{m, \mathcal{R}}\} = \mathcal{C}$，也即$\forall m \in \mathcal{M}\rm{;}\ \forall c \in \mathcal{C}\rm{;}$ $\exist r \in \mathcal{R}$ $s.t.\ c_{m, r} = c$。类似地，对比满射的定义，设$F: \mathcal{X} \to \mathcal{Y}$，则：

$$\forall y \in \mathcal{Y}\rm{;}\ \exist x \in \mathcal{X}\rm{;}\ s.t.\ F(x)=y$$

两个表述是相似的，如果令$\rm{Com}_{m}^c(r) \rightarrow c_{m, r}$，则当且仅当对所有$m \in \mathcal{M}$，$\rm{Com}_{m}^c(r)$满射到$\mathcal{C}$时，承诺方案拥有完美隐藏属性。

首先论证$\Rightarrow$方向：若对所有$m \in \mathcal{M}$，$\rm{Com}_{m}^c(r)$满射到$\mathcal{C}$，则$\forall m \in \mathcal{M}\rm{;}\ \forall c \in \mathcal{C}\rm{;}\ \exist r \in \mathcal{R}\ s.t. \rm{Com}_{m}^c(r)=c$，即符合上面的完美隐藏定义推导；

接着论证$\Leftarrow$方向：假设存在某个$m \in \mathcal{M}$使得$\rm{Com}_{m}^c(r)$不满射到$\mathcal{C}$，则存在$m' \in \mathcal{M}$和$r' \in \mathcal{R}$，使得$c' = \rm{Com}_{m'}^c(r') \not\in \{ \rm{Com}_{m}^c(\mathcal{R}) \}$，可得$c' \in (\{ \rm{Com}_{m'}^c(\mathcal{R}) \} - \{ \rm{Com}_{m}^c(\mathcal{R}) \}) \ne \empty$，即存在$m' \in \mathcal{M}$和$r' \in \mathcal{R}$，使得$\{ \rm{Com}_{m'}^c(\mathcal{R}) \} \ne \{ \rm{Com}_{m}^c(\mathcal{R}) \}$，和完美隐藏的定义相悖，所以不存在这样的$m$。

根据以上推出的特性，下面尝试粗略地设计一种完美隐藏的承诺方案的通用构造。假设$F$是一个函数簇，对于所有的$m\in \mathcal{M}$，$F_m$都能从$\mathcal{R}$满射到$\mathcal{C}$，则一种完美隐藏的承诺方案可以这样设计：

$$\text{A Toy Commitment Scheme with Perfectly Hiding} \\ \begin{array}{|lc|} \hline \\ \begin{array}{c} \rm{Commit: } \\ \\ \\ \\ \\ \\ \rm{Open: } \\ \\ \\ \\ \end{array} & \begin{array}{lcl} \mathrm{Sender}(m) & \ \ \ \ \ \ \ \ \ \ \ \ \ \ & \mathrm{Receiver} \\ \begin{array}{l} r \overset{\$}{\leftarrow} \mathcal{R} \\ c = F_m(r) \end{array} & & \\ & \overset{c}{\longrightarrow} & \\ \vdots & & \\ \\ \begin{array}{l} d = r \end{array} & & \\ & \overset{m,\ d}{\longrightarrow} & \\ & & \begin{array}{lll} \text{If } c = F_m(d) & \rightarrow & \text{Accept} \\ \text{Otherwise} & \rightarrow & \text{Reject} \end{array} \\ \end{array} \\ \hline \end{array}$$

注：以上的构造只能保证完美隐藏属性，如果还要计算上隐藏属性的话，还需要$F$拥有其他的性质。

以上完美隐藏属性的论证也不难，假设攻击者可以攻破完美隐藏属性，则可以仅根据$c = F_m(r)$恢复$m$，但由于$\forall m^* \in \mathcal{M}$，$F_{m^*}$满射到$\mathcal{C}$，即对于任意的$m^* \in \mathcal{M}$，都可能存在$r^* \in \mathcal{R}$使得$F_{m^*}(r^*) = c$，所以攻击者不可能知道$c$是由哪个$m^*$选出的函数所映射的。

来个实际的例子，Pedersen承诺方案就是利用类似的思路构造承诺方案的。令$\mathbb{G} = <g>$是一个素数$q$阶的循环群，$h, g \in \mathbb{G}$是两个随机的生成元，消息$m \in \mathbb{Z}_q$，则Pedersen承诺方案可以表示为：

$$\text{Pedersen Commitment Scheme} \\ \begin{array}{|lc|} \hline \\ \begin{array}{c} \rm{Commit: } \\ \\ \\ \\ \\ \\ \\ \rm{Open: } \\ \\ \\ \\ \end{array} & \begin{array}{lcl} \mathrm{Sender}(m) & \ \ \ \ \ \ \ \ \ \ \ \ \ \ & \mathrm{Receiver} \\ \begin{array}{l} r \overset{\$}{\leftarrow} \mathbb{Z}_q \\ c = g^mh^r \end{array} & & \\ & \overset{c}{\longrightarrow} & \\ \vdots & & \\ \\ \begin{array}{l} d = r \end{array} & & \\ & \overset{m,\ d}{\longrightarrow} & \\ & & \begin{array}{lll} \text{If } c = g^mh^d & \rightarrow & \text{Accept} \\ \text{Otherwise} & \rightarrow & \text{Reject} \end{array} \\ \end{array} \\ \hline \end{array}$$

令$F_m(r) = g^mh^r$，这就是上面构造的一个实例化。显然对于所有$m \in \mathbb{Z}_q$，$F_m$满射到$\mathbb{G}$，因为$|\mathbb{Z}_q| = |\mathbb{G}| = q$，假设存在某个$m \in \mathbb{G}$使得$F_m$不满射到$\mathbb{G}$，则存在$r \ne r' \in \mathbb{Z}_q$，使得$F_m(r) = F_m(r')$，即$g^mh^r \equiv g^mh^{r'}$ $(\rm{in}\ \mathbb{G})$，也即$h^r \equiv h^{r'}\ (\rm{in}\ \mathbb{G})$，由于$h$是$\mathbb{G}$的生成元，即当且仅当$r = r'$时成立，与假设矛盾。

从单向函数到计算上安全·

计算上安全的构造则没有那么直观，因为计算上安全要求是攻击成功的概率可忽略，就需要把安全性规约到某个难题上，但现有的难题五花八门，很难找到一种“模板”的构造方法。但也许可以用单向函数（One-way Function）做个尝试，首先看一下单向函数的定义：若函数$f: \mathcal{X} \to \mathcal{Y}$是单向函数，则任何多项式算法$F$算出$f$的伪逆（Pseudo Inverse）的概率可忽略，即

$$\rm{Pr}[f(F(f(x))) = f(x)] \le \rm{negl}$$

首先单向函数可以很直观地推出计算上隐藏属性，假设$\rm{Com}_r^c(m): \mathcal{M} \to \mathcal{C}$是单向函数，若攻击者$\text{A}_\text{R}$可以在多项式时间内攻破隐藏属性，则会有$\text{A}_\text{R}(\rm{Com}_r^c(m)) = m$，即$\rm{Pr}[\rm{Com}_r^c(\text{A}_\text{R}(\rm{Com}_r^c(m))) = \rm{Com}_r^c(m)] > \rm{negl}$，可以调用$\text{A}_\text{R}$攻击$\rm{Com}_r^c(m)$的单向性，即计算上隐藏的安全性可规约到$\rm{Com}_r^c(m)$的单向性。

计算上绑定的规约则每那么直观，可能需要先定义一个更宽松的绑定属性，在$\text{Adv}_\text{Binding}$的定义中，攻击者$\text{A}_\text{S}$需要在同一时间给出$m$和$m'$，但承诺方案中真正攻击的流程也许并不是这样的，比如在通用可组合框架的证明过程中的模拟者，需要先生成一个承诺值$c \in \mathcal{C}$，然后由环境给出消息$m' \in \mathcal{M}$，然后再由模拟者生成$d'$把$c$打开为$m'$的承诺。根据这个流程，可以给出以下定义：

$$\text{Adv}^\text{lossy}_\text{Binding}(\text{A}_\text{S}) = Pr\begin{bmatrix} \begin{array}{ccc} \begin{array}{l} \rm{Verify(c, m', d')} = \text{Accept} \end{array} & \rm{:} & \begin{array}{l} c \leftarrow \text{A}_\text{S}() \rm{;} \ \ c \in \mathcal{C} \rm{;} \\ m' \overset{\$}{\leftarrow} \mathcal{M} \rm{;} \\ d' \leftarrow \text{A}^{m'}_\text{S}(c) \rm{;} \ \ d' \in \mathcal{D} \rm{;} \\ \end{array} \end{array} \end{bmatrix}$$

这里由于$m'$是随机选择而不是让攻击者选择，所以定义变宽松了而且安全性也变弱，但是证明时的可操作空间也更大。现在假设$\rm{Com}_m^c(r): \mathcal{R} \to \mathcal{C}$是单向函数，且假设在构造时令$d=r$（或者使用类似的构造），假设$\rm{Verify}(c^*, m, r) := \rm{Com}_m^c(r) \overset{?}{=} c$的运算并对比得出的值是否和承诺值$c$相等。因为$\text{A}_\text{S}$在生成$c$时并不知道$m'$的任何信息，所以对于$\rm{Com}_{m'}$来说$c$是一个完全随机的像，而在选出$m'$后，若$\text{A}_\text{S}$输出的$d'$可以通过验证，则$\rm{Com}_{m'}(d') = c$，即有$\rm{Pr}[\rm{Com}_{m'}^c(\text{A}_\text{S}(c)) = c] > \rm{negl}$，和$\rm{Com}_m^c$是单向函数的假设冲突。虽然论证如是说，但由于不能自由控制$c$的选取，并不能直观地进行规约，所以这里的证明能否通过还需要斟酌。

从陷门置换到后门属性·

由于模棱两可和提取这两个后门属性都需要一个后门值，所以考虑后门属性的构造时，最先想到的会是陷门函数（Trapdoor Function）。陷门函数本身也是一个单向函数，单向函数要求求出伪逆的概率可忽略，而陷门函数则说，如果知道后门的话，则存在可以容易地求出逆（或伪逆）的逆函数，假设$F: \mathcal{X} \to \mathcal{Y}$是陷门函数、$\rm{Gen}$是密钥生成函数、$\rm{Invert}$是逆函数，则：

• $(pk, td) \leftarrow \rm{Gen}(1^\kappa)$；
• $x' \leftarrow \rm{Invert}_{td}(F_{pk}(x)),\ F_{pk}(x) = F_{pk}(x')$。

陷门置换（Trapdoor Permutation）则是双射的陷门函数。

利用陷门置换构造提取属性是直观的，假设$\rm{Com}_{pk,r}^c(m): \mathcal{M} \to \mathcal{C}$是一个陷门置换，令

$$\rm{Extra}_{td}(c) := \rm{Invert}^{\rm{Com}_{pk,r}^c}_{td}(c)$$

即可实现提取操作。由于$\rm{Com}_{pk,r}^c(m)$是双射的，即至少是单射的，也即不存在$m' \ne m \in \mathcal{M}$使得$\rm{Com}_{pk,r}^c(m')=c$，自然$\rm{Extra}_{td}$提取出$m' \ne m$，即提取出来的是真实的逆，不是伪逆。

然后是利用陷门置换构造模棱两可属性，假设$\rm{Com}_{pk,m}^c(r): \mathcal{R} \to \mathcal{C}$是陷门置换，且假设在构造时令$d=r$（或者使用类似的构造），假设$\rm{Verify}_{pk}(c^*, m, r) := \rm{Com}_{pk, m}^c(r) \overset{?}{=} c^*$的运算并对比得出的值是否和承诺值$c$相等。令

$$\rm{Equiv}_{td}(m, m', r) := \rm{Invert}^{\rm{Com}_{pk,m'}^c}_{td}(\rm{Com}_{pk,m}^c(r))$$

即可实现模棱两可操作。由于$\rm{Com}_{pk,m}^c$双射到$\mathcal{C}$，即$c = \rm{Com}_{pk,m}^c(r) \in \mathcal{C}$，且存在唯一的$r' \in \mathcal{R}$使得$\rm{Com}_{pk,m'}^c(r') = c$，可得$r' = \rm{Equiv}_{td}(m, m', r) = \rm{Invert}^{\rm{Com}_{pk,m'}^c}_{td}(\rm{Com}_{pk,m}^c(r))$，代入$\rm{Verify}_{pk}(c, m', r')$，根据陷门函数的性质可得

$$\rm{Com}_{pk, m'}^c(r') = \rm{Com}_{pk, m'}^c(\rm{Invert}^{\rm{Com}_{pk,m'}^c}_{td}(\rm{Com}_{pk,m}^c(r))) = \rm{Com}_{pk,m}^c(r) = c$$

验证通过。

例子·

以下利用上述构造思路构造两种承诺方案，并给出相应的证明。

例子一·

首先尝试构造计算上绑定、完美隐藏且拥有模棱两可属性的承诺方案。假设$F: \mathcal{R} \to \mathcal{F}$是一个陷门置换，公钥为$pk$、后门为$td$；设$G$是一个置换的簇，由$m \in \mathcal{M}$选出一个置换函数$G_m: \mathcal{F} \to \mathcal{C}$，且在知道$m$时存在多项式算法$G_m^{-1}$计算置换的逆，则该承诺方案可以构造为：

$$\begin{array}{|lc|} \hline \\ \begin{array}{c} \rm{Commit: } \\ \\ \\ \\ \\ \\ \\ \rm{Open: } \\ \\ \\ \\ \end{array} & \begin{array}{lcl} \mathrm{Sender}(m) & \ \ \ \ \ \ \ \ \ \ \ \ \ \ & \mathrm{Receiver} \\ \begin{array}{l} r \overset{\$}{\leftarrow} \mathcal{R} \\ c = G_m(F_{pk}(r)) \end{array} & & \\ & \overset{c}{\longrightarrow} & \\ \vdots & & \\ \\ \begin{array}{l} d = r \end{array} & & \\ & \overset{m,\ d}{\longrightarrow} & \\ & & \begin{array}{lll} \text{If } c = G_m(F_{pk}(d)) & \rightarrow & \text{Accept} \\ \text{Otherwise} & \rightarrow & \text{Reject} \end{array} \\ \end{array} \\ \hline \end{array}$$

下面作简略证明：

• 计算上绑定：假设多项式时间的攻击者$\text{A}_\text{S}$的$\text{Adv}_\text{Binding}(\text{A}_\text{S})$优势不可忽略，则可以找到$m \ne m' \in \mathcal{M}$和$r, r' \in \mathcal{R}$使得$G_m(F_{pk}(r)) = G_{m'}(F_{pk}(r'))$，则在不知道$td$的情况下有不可忽略的概率可以算出$r’ \in \mathcal{R}$使得$F_{pk}(r') = G_{m'}^{-1}(G_{m}(F_{pk}(r)))$即，

  $$\rm{Pr}[F_{pk}(\text{A}_\text{S}(F_{pk}(r))) = F_{pk}(r)] > \rm{negl}$$

  从而攻破$F_{pk}$的单向性。

• 完美隐藏：由于$F_{pk}$和$G_m$都双射，所以对于任意$m \ne m' \in \mathcal{M}$，

  $$\{ G_m(F_{pk}(\mathcal{R})) \} = \{ G_m(\mathcal{F}) \} = \mathcal{C} = \{ G_{m'}(\mathcal{F}) \} = \{ G_{m'}(F_{pk}(\mathcal{R})) \}$$

  $\text{Adv}_\text{Hiding}(\text{A}_\text{R})=0$。

• 模棱两可：和计算上绑定的证明类似，但知道$td$的情况下可以对$F_{pk}$求逆，

  $$\rm{Equiv}_{td}(m, m', d) := \rm{Invert}_{td}^{F}(G_{m'}^{-1}(G_{m}(F_{pk}(r))))$$

例子二·

接下来尝试构造完美绑定、计算上隐藏且拥有提取属性的承诺方案。假设$F$是一个函数簇，对于所有的$r\in \mathcal{R}$，$F_r:\mathcal{M} \rightarrow \mathcal{F}$是单射函数，且在知道$m$时存在多项式算法$\rm{Index}^F(m) := r$计算选择函数的值，在知道$r$时存在多项式算法$F_r^{-1}$计算函数的逆；$G: \mathcal{R} \rightarrow \mathcal{G}$是单射的陷门函数，公钥为$pk$、私钥为$td$，则该承诺方案可以构造为：

$$\begin{array}{|lc|} \hline \\ \begin{array}{c} \rm{Commit: } \\ \\ \\ \\ \\ \\ \\ \rm{Open: } \\ \\ \\ \\ \end{array} & \begin{array}{lcl} \mathrm{Sender}(m) & \ \ \ \ \ \ \ \ \ \ \ \ \ \ & \mathrm{Receiver} \\ \begin{array}{l} r \overset{\$}{\leftarrow} \mathcal{R} \\ f = F_r(m) \\ g = G_{pk}(r) \\ c = (f, g) \end{array} & & \\ & \overset{c}{\longrightarrow} & \\ \vdots & & \\ \\ \begin{array}{l} d = r \end{array} & & \\ & \overset{m,\ d}{\longrightarrow} & \\ & & \begin{array}{lll} \text{If } f = F_d(m) \text{ and } g = G_{pk}(d) & \rightarrow & \text{Accept} \\ \text{Otherwise} & \rightarrow & \text{Reject} \end{array} \\ \end{array} \\ \hline \end{array}$$

以下作简略证明：

• 完美绑定：假设$\text{Adv}_\text{Binding}(\text{A}_\text{S})\ne 0$，则存在$m \ne m' \in \mathcal{M}$和$r, r' \in \mathcal{R}$使得$F_r(m) = F_{r'}(m')$和$G_{pk}(r) = G_{pk}(r')$，由于$G_{pk}$是单射函数，所以$r = r'$，即$F_r(m) = F_{r}(m')$，由于$F_r$也是单射函数，所以$m = m'$，与假设矛盾，所以$\text{Adv}_\text{Binding}(\text{A}_\text{S}) = 0$。

• 计算上隐藏：假设多项式时间的攻击者$\text{A}_\text{R}$的$\text{Adv}_\text{Hiding}(\text{A}_\text{R})$优势不可忽略，则可以在不知道$td$的情况下根据$F_r(m)$和$G_{pk}(r)$算出$m$，随即可以算出$r = \rm{Index}^F(m)$，即

  $$\rm{Pr}[G_{pk}(\text{A}_\text{R}(G_{pk}(r))) = G_{pk}(r)] > \rm{negl}$$

  从而攻破$G_{pk}$的单向性。

• 提取：和计算上隐藏的证明类似，但在知道$td$的情况下可以对$G_{pk}$求逆：

  $$\rm{Extra}_{td}(c) := F^{-1}_{\rm{Invert}_{td}^G(g)}(c)$$

额外的思路·

异或·

例子一中的$G$函数和例子二的$F$函数其实都可以利用异或操作构造。

首先，当$n \in \mathbb{Z^+}$、$a,b \in \{0, 1\}^n$时，函数$F_a(b) := a \bigoplus b$是一个$\{0, 1\}^n \to \{0, 1\}^n$的置换：

• 单射性：假设存在$b \ne b' \in \{0, 1\}^n$使得$F_a(b) = F_a(b')$，则$a \bigoplus b = a \bigoplus b'$，则$b = b'$，矛盾。所以

  $$\forall a \in \{0, 1\}^n \rm{;}\ \forall b, b' \in \{0, 1\}^n \rm{;}\ b \ne b' \Rightarrow F_a(b) \ne F_a(b')$$

• 满射性：假设存在$c \in \{0, 1\}^n$使得$\forall b \in \{0, 1\}^n,\ F_a(b) \ne c$，由于$F_a$定义域与值域相同，则$\exist b \ne b'\ s.t.\ F_a(b) = F_a(b')$，即$\exist b \ne b'\ s.t.\ a \bigoplus b = a \bigoplus b'$，当且仅当$\exist b \ne b'\ s.t.\ b = b'$，矛盾，所以

  $$\forall c \in \{0, 1\}^n\rm{;}\ \exist b \in \{0, 1\}^n\ s.t.\ \ F_a(b) = c$$

然后证明若$F_a(b) = c = a \bigoplus b$，例子二的两个性质存在：

• $\rm{Index}^{F}(b, c) := b \bigoplus c = a$
• $F_a^{-1}(c) := c \bigoplus a$

通用可组合下的承诺方案·

（如无意外下次可以写这个了，留坑）

参考·

Crypto wiki：https://cryptography.fandom.com/wiki/Commitment_scheme

[B83] Blum M. Coin flipping by telephone a protocol for solving impossible problems[J]. ACM SIGACT News, 1983, 15(1): 23-27.

[BCC88] Brassard G, Chaum D, Crépeau C. Minimum disclosure proofs of knowledge[J]. Journal of computer and system sciences, 1988, 37(2): 156-189.

[BCP+13] Blazy O, Chevalier C, Pointcheval D, et al. Analysis and improvement of Lindell’s UC-secure commitment schemes[C]//International Conference on Applied Cryptography and Network Security. Springer, Berlin, Heidelberg, 2013: 534-551.

[BGM19] Branco P, Goulão M, Mateus P. UC-Commitment Schemes with Phase-Adaptive Security from Trapdoor Functions[J]. Cryptology ePrint Archive, 2019.

[C01] Canetti R. Universally composable security: A new paradigm for cryptographic protocols[C]//Proceedings 42nd IEEE Symposium on Foundations of Computer Science. IEEE, 2001: 136-145.

[CF01] Canetti R, Fischlin M. Universally composable commitments[C]//Annual International Cryptology Conference. Springer, Berlin, Heidelberg, 2001: 19-40.

[CJS14] Canetti R, Jain A, Scafuro A. Practical UC security with a global random oracle[C]//Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security. 2014: 597-608.

[CLOS02] Canetti R, Lindell Y, Ostrovsky R, et al. Universally composable two-party and multi-party secure computation[C]//Proceedings of the thiry-fourth annual ACM symposium on Theory of computing. 2002: 494-503.

[DN02] Damgård I, Nielsen J B. Perfect hiding and perfect binding universally composable commitment schemes with constant expansion factor[C]//Annual International Cryptology Conference. Springer, Berlin, Heidelberg, 2002: 581-596.

[Lin11] Lindell Y. Highly-efficient universally-composable commitments based on the DDH assumption[C]//Annual International Conference on the Theory and Applications of Cryptographic Techniques. Springer, Berlin, Heidelberg, 2011: 446-466.