零知识证明及承诺协议的不可延展性研究

摘要

上世纪七、八十年代，现代密码学迎来了蓬勃发展的新时期，产生了诸如公钥密码学、交互证明系统、伪随机发生器等一系列具有里程碑式意义的成果，并开启了现代密码学与计算复杂性理论相结合的道路。Goldwasser在1997年FOCS会议上曾发表了题为“Cryptography and Complexity Theory：A Match Made inHeaven”的特邀报告，她指出：现代密码学最重大的进展是将密码学建立在计算复杂性的基础之上，并且正是计算复杂性理论将密码学从一门艺术发展成为一门严谨的科学。而零知识证明则是密码学和复杂性理论相互交织、相互促进的最好见证。
　　 简言之，零知识证明系统是一个两方交互协议，其中证明者通过交互来向验证者证明某一个断言，并且确保不向验证者泄露任何额外的信息。零知识证明自提出以来一直处于密码学的中心位置，对密码学的发展起到关键作用。首先，零知识证明为密码协议安全性的形式化分析奠定了基础，其基于模拟不可区分性的证明思想已成为可证明安全理论的核心。更重要的是，零知识证明看似矛盾的独特性质令其集“保密性”和“认证性”于一身，因此广泛应用于各类密码算法和密码协议的构造，例如身份认证协议、抗选择密文攻击安全的加密方案、以及抵抗恶意敌手的安全多方计算协议。
　　 作为构造零知识证明系统以及其他安全计算协议的一个基本组件，承诺的思想先于零知识证明而被学者们用于设计电话投币、虚拟扑克等协议，并最终由Brassard等人给出了形式化的定义以及“承诺(commitment)”这个形象的名称。简言之，承诺协议是一类两方参与的两阶段交互协议。首先在承诺阶段，承诺者对一个字符串v承诺，发送给接收者，并且确保接受者得不到关于v的任何信息；随后在打开阶段，承诺者公开v，并证明其与第一阶段的一致性。承诺协议的两个基本性质分别称为隐藏性和绑定性。所谓隐藏性，是指在承诺阶段任意恶意的接收者都不能获取承诺字符串的信息；而绑定性是指在打开阶段，任意恶意的承诺者都不能将承诺打开为另外一个值，并且通过验证。
　　 在密码协议的设计中，承诺协议通常作为子协议来构造更为复杂的安全计算协议，其主要作用是固定参与者的输入，同时保证其隐私性。它通常与零知识证明系统配合来实现抵抗恶意敌手的安全多方计算协议。另外，承诺协议与零知识证明系统存在着内在的联系，并且两者的研究总是相互促进，共同发展的。
　　 近年来，随着互联网的兴起，密码协议在并发、异步的网络环境下的面临着更多的安全性冲击，协议基本的安全属性已经不足以应对复杂的网络环境和应用。如何建立合理的协议安全模型，以及设计满足更高安全性需求、适用于互联网应用的密码协议逐渐成为了密码学界关注的热点问题。
　　 其中，并发不可延展性定义了零知识证明及承诺协议在多次并发执行的过程中抵抗中间人攻击的能力。以零知识证明为例，考虑如下情景：一个中间人敌手并发的参与多个会话，执行同一个零知识证明协议，在其中一部分会话中，敌手作为验证者接收并验证诚实证明者对某些断言的证明，而在另一部分会话中，敌手作为证明者与诚实的验证者交互，试图构造对相关断言的证明。能够抵抗上述并发中间人攻击的零知识证明或者承诺协议称为并发不可延展的。研究者普遍认为，并发不可延展性在最大程度上反映了协议在开放网络环境下所要达到的安全性要求。
　　 本文的研究主要围绕并发不可延展的零知识证明系统以及承诺方案而展开，重点在与协议鲁棒性研究，具体包括以下方面：
　　 ·关于并发不可延展的零知识
　　 近期，Lin等人将承诺协议的不可延展性扩展到更一般化的形式，称为对任意k-轮协议的不可延展性，讨论承诺协议在以下场景中的安全性：敌手在左侧会话中参与任意一个k-轮协议，而在右侧与多个接收者交互，执行某个承诺协议。k-不可延展性反应了一个承诺协议与其他协议组合执行时的鲁棒性，即一个k-不可延展的承诺可以与任意轮数不超过k的协议组合执行，而不影响其安全性。因此，当与其他协议组合执行时，此类承诺协议的不可延展性更易于分析。
　　 本文受上述文献所启发，研究并发不可延展零知识的鲁棒性。在已有的不可延展零知识协议中，一部分使用了非黑盒的模拟机制，而缺乏鲁棒性正是非黑盒模拟机制自身的限制，尤其在并发环境下；另一部分虽然采用的黑盒模拟，但都是基于Goldreich-Kahan结构而构造，包含一个零知识子协议。由于零知识在并发组合下并不封闭，因此这些协议的鲁棒性难于分析。为此，本文提出了第一个具有鲁棒性并发不可延展零知识论证系统，具有如下特点：
　　 a)基于Feige-Shamir结构而构造，以具有鲁棒性的不可延展承诺协议以及巧妙设计的证据不可区分证明系统来实现零知识，并确保整个协议的鲁棒性。
　　 b)采用“茫然模拟(oblivious simulation)”的策略来模拟敌手的视图。
　　 c)在单向函数假设下，拥有最优的轮复杂度，即超对数。
　　 d)通过适当调整子协议的轮数，可以实现与任意协议的组合。
　　 ●关于并发不可延展的承诺
　　 承诺协议的不可延展性针对其两个阶段分别定义，即关于承诺阶段的不可延展性以及关于打开阶段的不可延展性，分别描述了两个阶段相对于自身的独立性。近期，在TCC’09的一项工作中，Ostrovsky等人研究了这两类不可延展性之间的关系，并指出，在基于模拟的不可延展性定义下，承诺阶段的不可延展性并不一定蕴含打开阶段的不可延展性，因此设计同时满足这两种性质的承诺协议具有重要的理论意义。文中同时构造了一个计算隐藏且计算绑定的承诺方案，同时满足承诺阶段和打开阶段的并发不可延展性。此后，在PKC’10中，Cao等人将该方案扩展并得到一个统计绑定的版本。然而，上述两方案(以及几乎所有已知的不可延展承诺方案)都存在一个共同的限制：承诺阶段和打开阶段在时间上不可重叠。因此，如何构造一个两阶段可重叠的完全并发不可延展的承诺方案仍然是一个公开问题。
　　 为此，本文作了如下工作：
　　 a)分析并指出在目前的不可延展性定义下，上述问题无法解决。同时，本文给出了一个新的并发不可延展性定义，它与原定义在本质上相同，但适用于两阶段可重叠的承诺协议。
　　 b)分析了上述问题存在的原因，并在此基础上构造了一个计算绑定且计算隐藏的承诺方案，同时满足承诺阶段和打开阶段的并发不可延展性，并且允许两阶段可重叠，解决了上述公开问题。在单向函数假设下，该方案的承诺阶段和打开阶段的轮复杂性均为超对数。