密码学笔记|Commitment Schema之比特承诺
比特承诺
最近读论文，涉及到一个密码学概念：Commitment Schema。字面意思就是承诺方案。
很难理解，查阅了相关资料，搜集了一些有用的资料，下面搬运一篇来自公众号：包罗万想 的推文，链接为：GCAC08 3.12比特承诺
抛出问题：
Alice和Bob约会。爱丽丝想看一部电影，鲍勃想看另一部电影。他们决定随机掷硬币选择电影。如果硬币正面朝上，它们将由爱丽丝选择；否则，他们将选择鲍勃的选择。当爱丽丝和鲍勃非常接近时，这很容易。他们都能验证结果。
但是当他们离得很远并且在电话里讲话时，这会变得更加困难。
鲍勃可以抛硬币，将结果告诉爱丽丝，但爱丽丝没有理由相信结果。
那么有什么办法来解决：让对方相信自己抛硬币的结果，并且自己无法篡改结果，在揭晓阶段又向对方证明自己确实是抛的正面/反面。
答案是 比特承诺！
0x01 概念
比特承诺是安全多方计算中最重要的基础协议之一，对构建更复杂的多方协议起着重要作用。
比特承诺(BitCommitment， BC)是密码学中的重要基础协议，其概念最早由 1995 年图灵奖得主 Blum提出。比特承诺方案可用于构建零知识证明、可验证秘密共享、硬币投掷等协议，同时和不经意传送一起构成两方安全计算的基础，是信息安全领域研究的热点。主要包含C,V两个算法。
0x02 基本思想
发送者 Alice 向接收者Bob 承诺一个比特b (如果是多个比特，即比特串t ，则称为比特 串承诺)，要求：
在第 1 阶段即承诺阶段 Alice 向 Bob 承诺这 个比特b ，但是 Bob 无法知道b 的信息；
在第 2 阶段即揭示阶段Alice 向 Bob 证实她在第 1 阶段承诺的确实是b，但是 Alice 无法欺骗 Bob(即不能在第 2 阶段篡改b的值)。
0x03 经典环境示例
Alice将待承诺的比特或秘密写在一张纸上，然后将这张纸锁进一个保险箱，该保险箱只有唯一的钥匙可以打开。
在承诺阶段， Alice将保险箱送给 Bob，但是保留钥匙；
到了揭示阶段，Alice将比特或秘密告诉 Bob，同时将钥匙传给 Bob 使其相信自己的承诺。
需要指出的是，保险箱不能被“暴力破解”的性质甚至允许Alice 在揭示阶段无需向 Bob 说明承诺的比特或秘密，只要将钥匙发送给 Bob 即可。
0x04 性质
一个比特承诺方案必须具备下列性质：
正确性：如果 Alice 和 Bob 均诚实地执行协议，那么在揭示阶段 Bob 将正确获得 Alice 承诺的比特b 。
保密性Hiding：在揭示阶段之前 Bob 不能获知b的信息。
绑定性Binding ：在承诺阶段结束之后，Bob只能在揭示阶段获得唯一的b (即 Alice 无法将b 反转，就好像 Alice 与b “绑定”在一起一样)。
如果一个比特承诺协议同时满足保密性和绑定性，且没有对攻击者的计算能力做任何限制性假设，则称该比特承诺协议是无条件安全的。
0x05 三方比特承诺
在该模型下，承诺者由一人变为二人Alice 与 Bob，由此二人共同向第三方Chris 承诺一个比特或比特串。
承诺阶段之前， Alice 与Bob 可以自由通信以商定承诺内容，但是在协议开始以后，要求 Alice 与 Bob 无法再进行通信。（考虑到量子计算环境，协议开始之后， Alice 与Bob 被物理隔离，无法再进行经典通信和量子通信，最多只允许对本地量子进行局域测量）。
该模型最重要的特点是揭示阶段由 Bob 负责向 Chris 揭示b 的信息，因此 Alice 没有任何作弊的可能，即无法破坏协议的绑定性。
应用
囚徒困境
三方参与的安全模型在实际生活中是有很多应用的，例如在博弈论的经典“囚徒困境”模型中，两个纵火嫌疑犯即可以视作证明者，他们在被抓住以前可以自由交流(例如商定问讯对策)，被抓以后将被警察(验证者)分开审讯。如果这两个嫌疑犯均“忠实”地在审讯过程中坚持否认纵火事实，那么他们将获得集体最优结果。又如，由两家单位合作来对某个大型项目进行投标(例如资金与技术的合作)，则这两家单位和招标方构成三方承诺模型。
安全多方计算
另外，一些安全多方计算的协议模型，其最基本的组成结构也经常是三方，而非两方。例如可验证秘密分享(Verifiable Secret Sharing，VSS)，除了一个秘密分发方外，秘密分享方至少是两方，因此一个秘密分享方案至少需要三方的参与。又如，在匿名通信的重要基础模型——密码学家就餐问题中，参与的密码学家至少为三个。
后续讲解Secret Sharing 秘密分享协议！
