commitment scheme, digital analogue of a safe.

抛硬币引发的纠纷

《黑暗骑士》中歌谭市的检察官“光明骑士”哈维.丹特,黑化成反派“双面人”后,喜欢用抛硬币来决定一个人的生死。抛硬币是一个常见的生成真随机数的方式。哈维.丹特抛硬币决定别人命运的过程,可以叫做“朴素抛硬币”,参与决策过程的两个人物理上在同一个地点,可以当面检验结果,不存在作弊。

如果两个人不在同一个地方,事情立马变得复杂起来。想象alice和bob住的很远,有次他们对约会该看电影还是话剧产生了分歧,要通过抛硬币来决定结果。如何在没有第三方的参与下,完成一次公正的远程抛硬币行为?

承诺方案:一个远程抛硬币协议

alice和bob手足无措,只好向他们的好朋友密码学家求助。密码学家听完后,不负众望给出了一个远程抛硬币协议(Coin flip protocol):

1. alice从抛硬币的结果 {0,1} 中选择一个x,计算出一个commitment发送给bob;
2. bob执行抛硬币后,把结果y告诉alice,因为bob不能从commitment中推测出alice选了什么,所以他给的y是独立于x的;
3. alice揭示自己的x发送给bob;
4. bob验证x和commitment是否匹配;
5. 如果x,y相等,alice赢,否则bob赢;

上面过程的核心分为两步,commit-and-reveal,这个密码学原语也被叫做Commitment scheme(承诺方案)。

承诺方案通俗的解释是,发送者把一条信息放到盒子里锁上,再把这个盒子寄给接受者。发送者如果不提供钥匙,接受者无法打开盒子,不知道里面的信息。盒子已经在接受者这里,发送者也无法修改最初放进盒子里的那条信息。

可见,要保证这个协议的安全性,需要满足两个属性:

  1. 隐藏(hiding),commitment不能泄漏任何关于alice的选择x的信息,准确来说是用0计算出来的commitment的分布与用1计算出来的commitment的分布不可区分(indistinguishable);
  2. 绑定(binding),一旦alice给出了x的commitment,她揭示的时候不能用任何除了x外的值蒙混过关。

密码学家经常会构想出具有某种特性的primitive(原语),再去找构造的方式。下面就看看如何构造符合hiding和biding特性的密码学原语。

构造承诺方案的若干种方法

  1. 整数分解

    最早的承诺方案的构造出现在1981 Blum的论文《通过电话抛硬币—一个解决不可能问题的协议》,这篇论文中还没有出现Commitment scheme这个名词,毕竟那还是密码学新革命的早期——第一篇公开讨论公钥密码学的文章1976年才发表出来。Blum的方案基于整数分解的困难性假设,从论文标题中的“不可能”揣测,那个年代基于计算复杂度构造密码学原语是一件多么新奇的事情。

    二次剩余(quadratic residue): 在数论中,假设存在整数x,使得x^2和q关于模数n同余,则称q为模n二次剩余,否则称q为模n二次非剩余,称x为q的模平方根,如下:

    给定整数q和n,

    1. 如果n是质数或者质数的幂(eg.13,13^2),则可以使用Tonelli–Shanks algorithm计算x;
    2. 如果n是大素数的乘积,可以先分解出因子,再按照1中方式计算x,复杂度等同于整数分解问题。

    Blum协议基本流程:

    1. bob(或者任何中立方)生成n=p*q,将n发送给alice;
    2. alice选择一个1到n的数字x,计算q = x^2 (mod n),将q发送给bob,bob无法计算出x是多少(如果n=p*q是bob选的话,他能够计算出几个备选项,但依旧无法确定是哪个);
    3. bob把“抛硬币”结果发给alice;
    4. alice把x发给bob。

    具体的协议比这里描述的要复杂,比如p和q都需要是 3 mod 4的同余,以及一些额外的检测。

    这里利用了二次剩余求模平方根的困难性,bob无法计算出x的值(即使知道p和q也只能得出几个备选项,实现了hinding),alice无法伪造她的x(因为她不知道p和q,所以计算不出来除了x外的值x‘,使得x’^2 = x^2 (mod n) ,实现了binding)。

  2. 离散对数

    Pedersen在解决可验证密钥共享问题(Verifiable secret sharing,VSS)中,探索了使用离散对数问题构造承诺方案的方式。

    VSS协议是如何将密码s分割成n份,汇聚其中k份能够恢复出密钥,低于k份不能得到任何有用的信息,构造VSS协议参考如何分享秘密:从SSS到PVSS。为了让参与者能够验证收到的密钥分片的正确性,dealer需要先计算出s的commitment。朴素的构造方法是:

    这里g是循环群的生成元,c是群里的元素——在公钥密码学中,s等同于私钥,c等同于公钥。这个c会被分发给VSS协议的参与者,用于后续的验证。

    Pedersen对这个朴素的承诺方案进行了升级,构造出一个新的commitment:

    这里引入了另一个生成元h,以及随机数t,这就是我们今天熟悉的Pedersen commitment.

  3. 伪随机数生成器

    Naor(Blum的学生)给出了基于伪随机数生成器的方案,这是比整数分解、离散对数假设等更弱的假设。

    伪随机数生成器(Pseudo-random generator, PRG)是一个确定性算法,设 ,输入一个种子,输出;随机选择计算上不可区分。

    alice要计算的承诺,设构造过程:

    1. bob选择一个随机字符串,发送给alice;
    2. alice选择一个随机数字符串,计算,计算公式如下
    3. alice把 发送给bob但暂时保留
    4. bob把抛硬币结果发给alice;
    5. alice把发给bob,bob验证结果;

    由定义,(尽管bob知道r,但操作中只要有一个是均匀分布的,结果也会是均匀分布) 计算上不可区分,实现了隐藏的目的;

    如果,alice想要欺骗bob,则需要找到,使得

    也即

    变换后得到

    种可能结果,由于是随机选择的,则存在的概率使公式(3.4)有解,从而实现绑定属性。

  4. 密码学安全哈希函数

    Shai Halevi 和 Silvio Micali (图灵奖得主,也是区块链项目Algorand的创始人)提出了一个安全可证明的基于抗碰撞哈希函数的方案。

    错误的版本:直接hash

    修复的版本:加上随机数再hash

    可证明安全的版本:

总结

如同很多密码学原语,在提出之初是为了解决了某个特定问题,但慢慢的发现它可以成为其他系统的基础。Commitment scheme就是其中之一,它在密码学世界有着惊人广泛的应用,包括现在区块链领域最前沿的跨链原子交换(Atomic Swap)、兰伯特签名(Lamport Signature)、零知识证明(ZKP)、多方安全计算(SMPC)等。这些有趣的应用将会在后面的文章中逐一介绍。

参考

  1. Manuel Blum, Coin Flipping by Telephone: A Protocol for Solving Impossible Problems, ACM SIGACT, Vol.15, No.1, 1983.
  2. Pedersen. Non-Interactive and Information-Theoretic Secure Verifiable Secret Sharing. 1992.
  3. M. Naor. Bit commitment using pseudorandomness. In Journal of Cryptology, 1991.
  4. Shai Halevi , Silvio Micali, Practical and Provably-Secure Commitment Schemes from Collision-Free Hashing, Proceedings of the 16th Annual International Cryptology Conference on Advances in Cryptology, 1996.