作者：@warm3snow https://github.com/warm3snow
微信公众号：密码应用技术实战
博客园首页：https://www.cnblogs.com/informatics/
标签：技术分享模板
目录
简介
答应方案(Commitment Scheme)是一个重要的密码学原语(cryptographic primitive), 答应方案是一种加密协议，允许发送者答应一个选择的值（或声明），同时对接收者保持隐藏，而接收者能够在稍后验证所答应的值。答应方案通常可以分为两个阶段。
- 答应阶段(Commitment Phase): 发送方发送一个答应值给接收方，这个值是发送方选择的，接收方无法知道这个值的内容。
- 打开阶段(Opening Phase): 发送方打开这个答应，接收方可以验证这个值的内容。
密码学答应方案在多个领域有广泛的应用，以下是一些主要的应用场景：
- 电子投票：在电子投票体系中，答应方案可以确保选民在投票时能够保密其选择，同时在投票结束后能够验证其投票的有用性。
- 拍卖：在拍卖中，答应方案可以让竞标者在拍卖开始时提交他们的出价，而不透露具体的出价金额。拍卖结束时，全部出价可以被揭示并验证，以确保竞标者的出价是诚实的。
- 安全多方盘算：在多方盘算中，参与者可以使用答应方案来答应他们的输入，而不需要在盘算过程中透露这些输入。这有助于掩护参与者的隐私。
- 数字署名：答应方案可以用于构建数字署名方案，确保消息的完备性和不可否认性。
- 区块链和加密钱币：在区块链技术中，答应方案可以用于确保生意业务的隐私和安全性。例如，某些隐私币（如Zcash）使用答应方案来隐藏生意业务金额和发送者信息。
- 身份验证：答应方案可以用于身份验证协议中，允许用户在不透露其身份信息的情况下证明其身份。
- 游戏理论：在博弈论中，答应方案可以用于设计机制，使参与者能够在不透露其计谋的情况下进行合作或竞争。
答应方案原理
符号定义
- \(C\): 答应值
- \(m\): 明文
- \(r\): 随机数，需要保证每次答应的随机数不同
- \(H\): 哈希函数
- \(||\): 字符勾通接
- \([m]\): 明文\(m\)的答应值
- \([m;r]\): 明文\(m\)和随机数\(r\)的答应值
- \(G_p\): 模素数\(p\)的阶为\(q\)的循环群
- \(g\): \(G_p\)的天生元
- \(h\): \(G_p\)的天生元, 与\(g\)为独立天生元，即g和h天生的子群相互独立
- \(G\): 椭圆曲线上的点,即\((G_x, G_y)\), 通常情况下\(G\)是椭圆曲线的天生元
- \(H\): 椭圆曲线上的点,即\((H_x, H_y)\), 通常境况下\(H\)随机选取
- 明文\(m\)的Pedersen答应值：\([m;r] = g^m \cdot h^r\)
方案定义
答应方案是一个三元组, 包含\((Commit, Open, Verify)\)，此中：
- \(Commit\)：发送方的答应算法，通常发送方选择一个明文\(m\)和一个随机数\(r\)，盘算答应值\(C\)。
- \(Open\)：发送方的打开算法， 通常发送方揭示明文\(m\)和随机数\(r\)。
- \(Verify\)：接收方的验证算法， 通常接收方验证答应的正确性。
答应值有两个属性：
- 隐藏性(Hiding)：接收方无法知道发送方的答应值对应的明文。
- 绑定性(Binding)：发送方无法在答应值打开之后更改明文。
注：以上两种描述并不严谨
答应方案一样平常涉及到两方，发送方和接收方。发送方选择一个明文\(m\)和一个随机数\(r\)，盘算答应值\(C\)，并发送\(C\)给接收方。在某个时候，发送方打开答应，揭示\(m\)和\(r\)。接收方使用\(C\)和揭示的\(m\)和\(r\)验证答应的正确性。
常见答应方案和原理
常见的答应方案有 哈希答应、ElGamal答应、Pedersen答应和 Sigma答应等。固然答应方案的实现方式不同，但其基本原理相似。
关键流程如下：
[01] 发送答应：Sender选取随机数\(r\), 并盘算\(m\)的答应值\(C\)，发送给Receiver。(这里的随机数\(r\)是为了保证每次答应的值不同)
[02] 打开答应：Sender打开答应，揭示\(m\)和\(r\)。
[03] 验证答应：Receiver重新盘算答应值\(C^{'}\)，并验证\(C^{'}\)和\(C\)是否相当。相当则认为答应验证通过，否则答应验证失败。
哈希答应
哈希答应是一种简单的答应方案，通过哈希函数来实现答应。假设\(H\)是一个哈希函数，\(m\)是明文。
哈希答应的构造如下：
- 答应阶段：发送方选择一个明文\(m\)，盘算答应值\(C = H(m)\)，并发送\(C\)给接收方。
- 打开阶段：发送方揭示明文\(m\)。
- 验证阶段：接收方重新盘算答应值\(C^{'} = H(m)\)，并验证\(C^{'}\)和\(C\)是否相当。
哈希答应的隐藏性和绑定性是基于哈希函数的性质，哈希函数是单向函数，接收方无法从答应值\(C\)推导出明文\(m\)。同时，哈希函数是抗碰撞的，发送方无法找到两个不同的\(m\)，使得\(C = H(m)\)。
哈希答应隐藏性较差，在明文空间有限的情况下，大概会发生碰撞; 哈希答应对于雷同的明文\(m\)，答应值\(C\)是固定的，固然引入随机数\(r\)可以办理这个题目，但会破坏绑定性，因为发送方可以在保证\(m||r\)稳固的情况下，随便更改\(m\)和\(r\)的值。
ElGamal答应
ElGamal答应是一种基于离散对数题目的困难性假设构造的答应方案。假设\(G_p\)是阶为\(q\)的循环群，\(g, h\)是天生元, \(m\)是明文
ElGamal答应的构造如下：
- 答应阶段：发送方选择一个明文\(m\)和一个随机数\(r\)，盘算答应值\(C = (g^r, m \cdot h^r)\)，并发送\(C\)给接收方。
- 打开阶段：发送方揭示明文\(m\)和随机数\(r\)。
- 验证阶段：接收方重新盘算答应值\(C^{'} = (g^r, m \cdot h^r)\)，并验证\(C^{'}\)和\(C\)是否相当。
ElGamal答应的隐藏性和绑定性是基于离散对数题目的困难性假设，接收方无法从答应值\(C\)推导出明文\(m\)，发送方无法找到两个不同的\((r_1, m_1)\)和\((r_2, m_2)\)，使得\(C = (g^{r_1}, m_1 \cdot h^{r_1}) = (g^{r_2}, m_2 \cdot h^{r_2})\)。
假设发送方找到两个不同的\((r_1, m_1)\)和\((r_2, m_2)\)，使得\(C = (g^{r_1}, m_1 \cdot h^{r_1}) = (g^{r_2}, m_2 \cdot h^{r_2})\)，则有：
\[g^{r_1} = g^{r_2} \Rightarrow r_1 = r_2\]
\[m_1 \cdot h^{r_1} = m_2 \cdot h^{r_2} \Rightarrow m_1 \cdot h^{r_1} = m_2 \cdot h^{r_1} \Rightarrow m_1 = m_2\]
与假设矛盾，因此ElGamal答应具有绑定性。
Pedersen答应
Pedersen答应是一种基于离散对数题目的困难性假设构造的答应方案。假设\(G_p\)是阶为\(q\)的乘法群，\(g, h\)是独立天生元，\(m\)是明文。
Pedersen答应的构造如下：
- 答应阶段：发送方选择一个明文\(m\)和一个随机数\(r\)，盘算答应值¥C = g^m \cdot h^r\(，并发送\)C$给接收方。
- 打开阶段：发送方揭示明文\(m\)和随机数\(r\)。
- 验证阶段：接收方重新盘算答应值\(C^{'} = g^m \cdot h^r\)，并验证\(C^{'}\)和\(C\)是否相当。
Pedersen答应的隐藏性和绑定性是基于离散对数题目的困难性假设，接收方无法从答应值\(C\)推导出明文\(m\)，发送方无法找到两个不同的\((r_1, m_1)\)和\((r_2, m_2)\)，使得\(C = g^{m_1} \cdot h^{r_1} = g^{m_2} \cdot h^{r_2}\)。
假设发送方找到两个不同的\((r_1, m_1)\)和\((r_2, m_2)\)，使得\(C = g^{m_1} \cdot h^{r_1} = g^{m_2} \cdot h^{r_2}\)，则有：
\[g^{m_1} \cdot h^{r_1} = g^{m_2} \cdot h^{r_2} \Rightarrow g^{m_1 - m_2} = h^{r_2 - r_1} mod p\]
由于\(g\)和\(h\)是独立天生元, 即它们天生的子群没有重叠，这意味着\(g^{m_1 - m_2} = h^{r_2 - r_1}\)只有在\(_1 - m_2 = 0\)和\(r_2 - r_1 = 0\)时才成立，即：
\[m_1 - m_2 = 0 \Rightarrow m_1 = m_2\]
\[r_2 - r_1 = 0 \Rightarrow r_2 = r_1\]
与假设矛盾，因此Pedersen答应具有绑定性。
Pedersen答应也可以基于ECC构造，假设\(G\)和\(H\)是椭圆曲线上的点，\(m\)是明文，\(r\)是随机数。
- 答应阶段：发送方选择一个明文\(m\)和一个随机数\(r\)，盘算答应值\(C = mG + rH\)，并发送\(C\)给接收方。
- 打开阶段：发送方揭示明文\(m\)和随机数\(r\)。
- 验证阶段：接收方重新盘算答应值\(C^{'} = mG + rH\)，并验证\(C^{'}\)和\(C\)是否相当。
隐藏性和绑定性略，与上述类似。
Pedersen答应有一个重要的性质：同态性。即两个Pedersen答应的和即是明文的和的Pedersen答应。假设\(C_1 = g^{m_1} \cdot h^{r_1}\)和\(C_2 = g^{m_2} \cdot h^{r_2}\)是两个Pedersen答应，\(m_1, m_2\)是明文，\(r_1, r_2\)是随机数。则有：
\[C_1 \cdot C_2 = g^{m_1} \cdot h^{r_1} \cdot g^{m_2} \cdot h^{r_2} = g^{m_1 + m_2} \cdot h^{r_1 + r_2}\]
\[commit(m_1, r_1) \cdot commit(m_2, r_2) = commit(m_1 + m_2, r_1 + r_2)\]
使用ECC构造的Pedersen答应也具有同样的性质。如下：
\[m_1G + r_1H + m_2G + r_2H = (m_1 + m_2)G + (r_1 + r_2)H\]
\[commit(m_1, r_1) + commit(m_2, r_2) = commit(m_1 + m_2, r_1 + r_2)\]
Pedersen答应的同态性可以用于保证密态的加法性，即两个密文的和即是明文的和的密文。如在门罗币中，矿工节点通过验证Pedersen答应可以查抄生意业务UTXO的输入和是否即是输出和（是否凭空产生门罗币）。
零知识证明答应
在上一章中介绍的答应方案中，发送方和接收方之间的通讯是明文的，即接收方可以得到发送方的明文信息。在某些情况下，发送方希望向接收方证明本身拥有某个明文，而不透露明文的具体内容。这时，可以使用 零知识证明答应方案。
零知识证明答应是一种特殊的答应方案，允许发送方向接收方证明本身拥有某个明文，而不透露明文的具体内容。零知识证明答应方案根据在证明阶段是否交互可以分为：
- 交互式零知识证明答应：发送方和接收方之间需要交互，发送方向接收方发送证明，接收方验证证明。
- 非交互式零知识证明答应：发送方可以在不与接收方交互的情况下天生证明，接收方可以验证证明。
Sigma答应
Sigma答应是一种基于离散对数题目的困难性假设构造的零知识答应方案。Sigma答应的交互式证明流程如下：
- [01] 发送答应：Sender选取随机数\(r\)，并天生答应\(C = r.G\)，发送\(C\)给Receiver。
- [02] 发送挑衅：Receiver发送一个随机挑衅\(e\)给Sender;
- [03] 发送挑衅：Sender盘算证明\(z = m + er\)，并发送给Receiver。(注这里的proof是z，用于隐藏r和m)
- [04] 答应验证：Receiver验证Proof， 即验证\(z.G == C + e.Q\)。
Sigma答应正确性证明
\[z.G = (r + e.m).G = r.G + e.m.G = C + e.Q\]
等式左边即是等式右边，因此按照Sigma答应协议流程，验证方Receiver可以正确验证
Sigma答应隐藏性证明
非严酷证明，由于Receiver仅知道\(C\)，根据离散对数题目的困难性假设，Receiver无法盘算出\(r\)的值，保证了答应的隐藏性。
Sigma答应绑定性证明
假设Receiver可以找到两个不同的\((r_1)\)和\((r_2)\)，使得\(C = r_1.G = r_2.G\)，则有：
\[r_1.G = r_2.G \Rightarrow r_1 = r_2\]
与假设矛盾，因此Sigma答应具有绑定性。
Sigma答应零知识性证明
非严酷证明，由于Receiver仅知道\((Q, C, e, z)\)，而且基于该已知信息，无法盘算出\(m\)的值，保证了答应的零知识性
Sigma非交互式零知识证明答应
Sigma答应也可以使用Fiat-Shamir heuristic构造为非交互式零知识证明答应。具体流程如下：
- [01] 盘算答应：Sender选取随机数\(r\)，并天生答应\(C = r.G\);
- [02] 盘算挑衅：Sender盘算挑衅\(e = H(Q, C)\)，并盘算证明\(z = r + e.m\);
- [03] 发送(e, z)：Sender发送挑衅\(e\)和证明\(z\)给Receiver;
- [04] 验证：Receiver盘算\(A = z.G - e.Q\)，并验证\(e == H(Q, A)\)。
Sigma答应的非交互式零知识证明答应的正确性、隐藏性、绑定性和零知识性证明与交互式零知识证明答应类似。需要注意的是：
- 非交互式零知识证明答应的安全性与哈希函数的选择有关，需要选择一个安全的哈希函数。
- 与交互式零知识证明答应相比，非交互式零知识证明答应的性能更好，因为发送方和接收方之间不需要交互。
- 与交互式零知识证明答应相比，非交互式零知识证明答应发送的数据量更小，数据量只有挑衅\(e\)和证明\(z\)，不需要发送答应值\(C\)。
Pedersen零知识答应
Pedersen答应也可以构造为零知识答应方案。 下面我们直接介绍非交互式版本的Pedersen零知识答应方案。
- [01] 发送答应：Sender选取随机数\(r\)，并天生答应\(C = m.G + r.H\)，发送\(C\)给Receiver。（答应阶段稳固）
- [02] 天生挑衅：Sender天生两个随机数\(x\)和\(y\);
- [03] 天生证明：Sender盘算\(P = x.G + y.H\)，并盘算\(h = H(P)\)，然后盘算\(x^{'} = x + h.m\)和\(y^{'} = y + h.r\);
- [04] 发送证明：Sender发送证明\((P, x^{'}, y^{'})\)给Receiver;
- [05] 验证：Receiver验证证明，盘算\(h = H(P)\)，并验证\(P + h.C == x^{'}G + y^{'}H\)。
Pedersen零知识答应的隐藏性、绑定性与Pedersen答应类似。需要注意的是：
- Pedersen零知识答应的安全性与哈希函数的选择有关，需要选择一个安全的哈希函数。
Pedersen零知识答应的正确性证明
\[P + h.C = (x.G + y.H) + h.(m.G + r.H) \newline= x.G + y.H + h.m.G + h.r.H\newline= (x + h.m).G + (y + h.r).H\newline= x^{'}G + y^{'}H\]
等式左边即是等式右边，因此按照Pedersen零知识答应协议流程，验证方Receiver可以正确验证.
Pedersen零知识答应的零知识性证明
非严酷证明，由于Receiver仅知道\((C, P, x^{'}, y^{'})\)，而且基于该已知信息，无法盘算出\(m\)和\(r\)的值，保证了答应的零知识性。
答应方案对比
下表对比了哈希答应、ElGamal答应、Pedersen答应和Sigma答应的性质：
答应方案隐藏性绑定性同态性零知识性性能 ｜哈希答应差差否否高ElGamal答应好好是否较高Pedersen答应好好是否较高Sigma答应-交互式好好是是一样平常Sigma答应-非交互式好好是是较高Pedersen零知识答应-非交互式好好是是较高通过对比发现，Pedersen答应和Sigma答应是比较良好的答应方案，具有隐藏性、绑定性和同态性。Sigma答应是一种零知识答应方案，可以保证发送方向接收方证明本身拥有某个明文，而不透露明文的具体内容。Pedersen答应具有同态性，可以用于保证密文的加法性。因此，Pedersen答应和Sigma答应在实际应用中具有广泛的应用。
总结
本文介绍了答应方案的基本原理和常见的答应方案，包括哈希答应、ElGamal答应、Pedersen答应和Sigma答应。答应方案是一种重要的密码学原语，可以用于保证发送方的答应值对应的明文，同时隐藏明文的具体内容。答应方案在多个领域有广泛的应用，包括电子投票、拍卖、安全多方盘算、数字署名、区块链和加密钱币、身份验证和游戏理论等。通过对比发现，Pedersen答应和Sigma答应是比较良好的答应方案，具有隐藏性、绑定性和同态性。Pedersen答应具有同态性，可以用于保证密文的加法性。Sigma答应是一种零知识答应方案，可以保证发送方向接收方证明本身拥有某个明文，而不透露明文的具体内容。因此，Pedersen答应和Sigma答应在实际应用中具有广泛的应用。
希望通过本文的介绍，读者对答应方案有一个更深入的了解，为实际应用提供参考。
参考文献
转载请注明原文链接：https://www.cnblogs.com/informatics/p/18428017 本文版权归作者和博客园共有，欢迎转载，但未经作者同意必须在文章页面给出原文毗连，否则保留追究法律责任的权利。
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。 |
