UC安全性证明中模拟器构造方法研究

张 妤，黄周晶

（1.解放军信息工程大学 电子技术学院，河南 郑州450004；2.73671部队，安徽 六安237008）

0 引 言

密码协议复杂度和规模的日益增加使人们开始广泛认识到组合方法在设计和分析密码协议时的重要性。通用可组合安全分析模型［1］（UC模型）是用组合方法分析密码协议的成功范例，由Ran Canetti于2001年提出。在该模型中被证明具有某个安全性质的协议，当作为任意更大协议的组件时，或者和许多协议 （甚至未知协议）同时运行时，仍能保持该安全性质。这对于密码协议的模块化设计和分析，以及在复杂甚至不可预测环境中 （比如因特网）协议的分析，是非常有利的。因此，国内外已有不少对于UC模型的研究成果，密码协议研究者在UC模型下针对特定密码学任务进行研究，提出具有UC安全性的协议方案，如UC安全的电子现金［2］、零知识证明［3］、不经意传输［4］、签密［5］、安全多方计算［6］、数字签名［7］、认证及密钥交换［8－17］。

由此可见，自从UC模型提出以来直到现在，提出并证明具有UC安全性的密码协议方案是国内外绝大多数研究者所作的工作。UC安全性证明使用的是模拟证明方法（UC模拟并非其它学术领域中所提到的软件模拟，而是利用计算复杂性进行的一种抽象模拟），其核心和难点是构造模拟器。目前，模拟器的构造是针对不同理想功能和协议进行的，尚没有比较通用的方法可循。加之模拟器是使用交互式图灵机的形式描述的，不能直观反映模拟的本质内容，即便它模拟了一部分应该模拟的操作，但是是否精确地模拟了全部应该模拟的操作却不容易检查出来。更严重的是，如果本来不存在的模拟器被错误构造出来 （因为目前大部分文献中模拟器的构造描述比较笼统无章，这种情况很可能出现），那本来不安全的协议就会得出UC安全的结论。本文正是在这样的背景下进行研究，提出了一种较为通用的方法来构造模拟器，使得遵循该方法构造出来的模拟器是完善的 （模拟了所有应该模拟的操作），并且错误的模拟器不会被构造出来。这对于降低UC模型协议安全性证明出错的概率是有意义的。

1 UC模型的基本概念

UC模型是基于不可区分性的计算复杂性理论模型，下面概述其中的基本概念。

UC模型中的计算模型是交互式图灵机 （interactive Turing machine，ITM）［18］的通信网络。协议π、敌手A和环境Z分别被建模为3个ITM。协议的执行模型被建模为ITM之间的通信。其中环境ITM是协议ITM （内部的各参与方又可被建模为子ITM）和敌手ITM的观察者，可以观察双方的所有本地输入和输出，但无法观察双方的通信。环境根据观察来得出结论：被观察者是理想协议和模拟器（定义见下文），抑或是现实协议和敌手，并用输出的一位二进制值来表示结论。

定义1（理想功能）一个理想功能F代表一个特定协议的期待功能。

技术上，一个理想功能是一个ITM，它的行为像许多不同ITM （被看成是多方协议的通信方）的一个子程序机器。一个理想功能的身份标识 （pid）被置为⊥，用于和其它ITM区分；并且一个理想功能只识别与自己的会话标识（sid）相同的ITM的输入，忽略其它输入。

定义2（理想协议）令F是理想功能。F的理想协议，表示为IDEALF，定义如下。每当通信方 （sid，pid）被输入v激活，它就将v写在F（sid，⊥）的输入纸带上。每当通信方在它的子程序返回值纸带上收到一个值v，它就把这个值写到Z的子程序返回值纸带上。被A传递的消息，包括攻陷消息，都被忽略 （因为假定攻陷消息被敌手直接发送给理想功能）。

定义3（不可区分性）两个二元分布X和Y是不可区分的 （记为X≈Y），如果对于任何c，d∈N，都存在k0∈N，使得对于所有满足k＞k0的k以及所有a∈∪K≤kd｛0，1｝K的a，都有

｜Pr（X （k，a）＝1）－Pr（Y （k，a）＝1）｜＜k－c

定义4（UC－模拟）令π和 是PPT的多方协议。我们说πUC－模拟了 ，如果对于针对π的任何PPT敌手A存在一个针对 的PPT敌手S，使得对于任何PPT环境Z我们有

式中：EXECπ，A，Z——总体

式中：EXECπ，A，Z（k，z）——环境的输出，是一个随机变量。我们通常称S为一个模拟器。

定义5（UC－实现）令F是一个理想功能，π是一个多方协议。我们说πUC－实现了F，如果πUC－模拟了F的理想协议。

定义6（混合协议）一个F混合协议π是一个包括调用F的理想协议的子程序的协议。

定义7（通用组合）给定协议 、协议π（它调用协议 ）、协议ρ（它UC－模拟协议 ），通用组合操作定义如下（通用组合操作后得到的协议记为πρ／）：

（1）若π中的一条指令为：传送一个输入到 （sid，pid），则用如下指令代替：传送该输入到ρ（sid，pid）。

（2）若πρ／收到一个从ρ （sid，pid’）传来的输出，它处理之如同π收到一个从 （sid，pid’）传来的输出。

当协议 是某个理想功能F的理想协议时，组合后的协议记为πρ／F。

定理1（组合定理）π、 和ρ是3个PPT的多方协议，π调用 ，ρUC－模拟 。那么协议πρ／UC－模拟协议ρ。

2 UC安全性证明中模拟器构造方法研究

我们先来研究UC安全性的本质要求，在此基础上给出模拟器的存在条件和模拟内容，最后提出构造完善的模拟器的通用有效的方法。

2.1 UC安全性的本质要求

虽然UC模型没有直接给出UC安全性的定义，但联系文献 ［1］的上下文可以得出，作者定义的UC安全性（通用可组合安全性）实际上就是UC－实现：如果协议πUC－实现了理想功能F，则π具有F规定的安全性，并且该安全性在组合的条件下仍然保持。下文不妨设IDEALF＝ 。

依次运用定义5、定义4和定义3，我们得出，如果协议π具有F规定的组合安全性，则必然对于任何PPT敌手A，存在模拟器S，使得下面的事实成立：

对于任何c，d∈N，都存在k0∈N，使得对于所有满足k＞k0的k以及所有a∈∪K≤kd｛0，1｝K的a，有

｜Pr（EXEC，S，Z（k，a）＝1）－Pr（EXECπ，A，Z（k，a）＝1）｜＜k－c（1）

即对于任何敌手，存在模拟器使得：对于足够大的安全参数和安全参数的多项式长度的01序列输入，运行协议π时环境的输出的分布与运行理想协议 时环境的输出的分布几乎相同，其差别是可忽略的。

注意这里观察协议π和协议 的是同一个环境，环境公正且忠实于自己的观察，环境的输出代表环境认为自己观察的是理想协议的执行还是实际协议的执行，不妨设前者输出1，后者输出0。对于F的理想协议 ，显然在任何情况下环境都会输出1，即有

如果式 （1）成立，则必然有

也就是要求环境观察协议π的实际运行后，在绝大多数情况下都认为这是理想协议的运行！即，UC安全性实际上是要求，对于任何PPT敌手A，在外界环境看来，实际协议的执行和理想中的情况几乎一样好！

由上面分析可见，理想功能是UC安全性的规范，它描述了协议的功能要求和安全要求，安全要求规定了允许的攻击。即理想功能是协议对外界所有实体的安全接口标准，外界包括同一协议的其它实例、其它协议以及敌手。因此UC安全性的本质要求是：允许协议在理想功能的功能要求之外完成某些额外的功能，但决不允许实际敌手所能实施的攻击超出了理想功能的允许范围，即 “功不抵过”。

UC安全性的本质要求实际上决定了模拟器的存在性和模拟内容。这是由于UC安全性证明是由 “模拟”完成的，正是通过模拟将现实执行过程归约到理想功能，完成协议的UC安全性证明。模拟的核心要求是构造一个模拟器，该模拟器必须能与理想功能配合模仿实际协议运行的所有情况，这样的模拟器的存在性直接影响UC安全性证明的结论。如果这样的模拟器无论如何都构造不出来 （存在性不成立），则协议不具有UC安全性，此时可能有两种情况：要么是模拟器需要模拟的实际敌手的操作对理想功能实施不了，即实际敌手可以对实际协议实施某些理想功能不允许的攻击 （图1协议不是UC安全的。实际协议完成了所要求的功能，但实际敌手所能实施的攻击超出了被允许的范围。）；要么是实际协议没能完成理想功能要求的全部功能 （图2协议不是UC安全的。实际敌手所能实施的攻击在被允许的范围之内，但实际协议没完成所要求的全部功能。），这种情况下任何模拟器都无能为力。当然也可能这两种情况同时发生 （图3协议不是UC安全的。实际协议没完成所要求的全部功能，且实际敌手所能实施的攻击超出了被允许的范围。）。如果上面的两种情况均不发生，则这样的模拟器可以被构造出来 （存在性成立），模拟内容包括实际敌手的攻击、协议超额完成的功能和面向外界环境的接口。此时协议是UC安全的 （图4协议是UC安全的。实际协议完成了所要求的全部功能，且实际敌手所能实施的攻击在被允许的范围之内。），并且这种安全性在组合的条件下仍然成立。（图1－图4中F所在的方框表示理想功能；IA所在的三角框表示理想功能允许的攻击；π所在的方框表示实际协议；A所在的三角框表示实际敌手能实施的攻击。）

2.2 构造模拟器的方法

由上节分析得知，如果该模拟器能够构造出来，则它应该具有两部分能力：一个是能模仿敌手的所有攻击；另一个是能完成理想功能虽未要求、但协议却实现了的功能。在此基础上，模拟器还应该模拟协议实际执行时的对外接口。这样理想情况和现实情况对于环境的视图才不可区分。据此，本文给出构造模拟器的有效方法：

（1）划分协议的功能操作。根据理想功能要求的功能，将协议操作划分为实现所要求功能的 “份内”操作和实现要求外功能的 “额外”操作 （由于这一步只涉及功能而不涉及安全性，所以还是比较容易划分的。比如密钥交换协议的功能是参与者通过协议都得到一个密钥，至于密钥的一致性和机密性那是安全性要求，这一步先不考虑。这一步先保证每个参与者都得到一个密钥，这就是 “份内”功能）。如果无法划分出完整的 “份内”操作，则这样的模拟器不存在，协议不安全，终止；如果可以划分出完整的“份内”操作 （可以没有 “额外”操作），继续进行下一步。

（2）模拟实际敌手的攻击。对于实际敌手和实际协议操作的 “份内”部分之间的消息传递，用模拟版敌手 （模拟敌手的全部功能）和理想功能进行预模拟，如果存在某个消息传递时理想功能不支持的情况，则模拟器不存在，协议不安全，终止；否则，模拟器S存在，继续进行下一步。

（3）模拟协议超额完成的功能。模拟器S模拟协议的“额外”操作，我们称之为模拟版 “额外”协议，继续进行下一步。

（4）模拟协议实际执行时的对外接口。模拟器S模拟消息传递过程，具体做法如下：

1）对于实际敌手和实际协议操作的 “份内”部分之间的消息传递，模拟器用模拟版敌手和理想功能进行同样的消息传递；

2）对于实际敌手和实际协议操作的 “额外”部分之间的消息传递，模拟器用模拟版敌手和模拟版 “额外”协议进行同样的消息传递；

3）对于实际敌手和环境之间的消息传递，模拟器用模拟版敌手和环境进行同样的消息传递；

4）对于实际协议操作的 “份内”部分和环境之间的消息传递，模拟器用理想功能和环境进行同样的消息传递；

5）对于实际协议操作的 “额外”部分和环境之间的消息传递，模拟器用模拟版 “额外”协议和环境进行同样的消息传递。

2.3 上面所提方法的正确性分析

模拟器构造方法的正确性应从两个方面来检查：一方面，协议不安全或没完成全部目标功能时，使用该方法能够排除构造出模拟器的可能性；另一方面，当协议完成全部目标功能且安全时，使用该方法能够确保构造出的模拟器使环境对理想执行和现实执行的视图是一样的，即理想执行和现实执行是不可区分的。

我们从这两个方面来分析本文所提出的方法。首先，当协议没完成全部目标功能时，我们方法的第1步排除了构造出模拟器的可能性；当协议不安全时，我们方法的第2步排除了构造出模拟器的可能性；其次，当协议完成全部目标功能且安全时，我们方法的第2步还模仿了实际协议的敌手在理想执行中所缺少的对应物；我们方法的第3步模仿了实际协议的额外操作在理想执行中所缺少的对应物；我们方法的第4步则模仿了实际协议执行的全部对外接口在理想执行中的对应物 （对应图5和图6中箭头旁边的序号，图中以两方协议为例。具体模拟时，对于涉及到的各个参与者的消息传递应分别模拟）。图6中的网格阴影部分就是我们方法的全部模拟内容。从图5和图6的对比可以看出，我们方法的模拟内容加上理想功能，正好精确地模仿了现实协议的执行。从环境的角度来看，这两种情况的视图 （即两个图中虚线以下的部分）是一样的。

根据上面的分析，本文提出的模拟器构造方法是正确有效的。

3 结束语

通过本文的研究得出，UC模型的通用可组合安全性的本质与其它理论模型或工程系统中模块化设计和分析的思路是一致的——即提供通用标准接口，而接口标准化是模块化设计和分析所有系统的前提。可见，虽然UC模型高度抽象，但是抽丝剥茧的分析表明它和其它系统的模块化思想不谋而合。因此我们有理由相信，UC模型是一套有实际意义和发展前途的理论。特别是在传统的分析密码协议的非组合型模型在分析大型复合密码协议时逐渐力不从心的情况下，UC模型这种组合型模型则优势渐显。然而，这种优势的代价是模型自身比较复杂，而且还在不断的发展完善之中。希望本文对于UC模型的基本构建原理和安全性证明方法的研究在一定程度上能给以同行基础思路上的启示和借鉴。未来的研究工作将围绕UC模型和Dolev－Yao［19］模型的结合开展研究。

［1］RAN Canetti.Universal composable security：A new paradigmfor cryptographic protocols［C］.Proceedings 42nd IEEE Symposium on Foundations of Computer Science，2001：136－145.

［2］M rten Trolin.A universally composable scheme for electronic cash ［C］.Proceedings of INDOCRYPT，2005：347－360.

［3］Aggelos Kiayias，ZHOU Hongsheng.Trading static for adaptive security in universally composable zero－knowledge ［C］.Proceedings of ICALP，2007：316－327.

［4］Matthew Green，Susan Hohenberger.Universally composable adaptive oblivious transfer ［C］.International Crytology Conference－ASIACRYPT，2008：179－197.

［5］SU Ting.Theory and application study on universally composable security ［D］.Jinan：Shandong University，2009 （in Chinese）.［苏婷.UC安全理论及应用研究 ［D］.济南：山东大学，2009.］

［6］LEI Feiyu.Studies on UC secure multiparty computation and its applications［D］.Shanghai：Shanghai Jiaotong University，2007（in Chinese）.［雷飞宇.UC安全多方计算模型及其典型应用研究 ［D］.上海：上海交通大学，2007.］

［7］HONG Xuan.Studies on universally composable digital signature and its key problems［D］.Shanghai：Shanghai Jiaotong University，2008（in Chinese）.［洪璇.通用可组合数字签名模型及其关键问题研究 ［D］.上海：上海交通大学，2008.］

［8］Mike Burmester，Tri Van Le，Breno De Medeiros，et al.Universally composable RFID identification and authentication protocols ［J］.ACM Transactions on Information and System Security－TISSEC，2009，12 （4）：1－33.

［9］Choudary Gorantla M，Colin Boyd，Juan Manuel González Nieto.Universally composable contributory group key exchange ［C］.Computer and Communications Security，2009：146－156.

［10］GUO Yuanbo，WANG Chao，WANG Liangmin.Universally composable authentication and key exchange protocol for access control in spatial information networks ［J］.ACTA Electronica Sinica，2010，38 （10）：2358－2364 （in Chinese）.［郭渊博，王超，王良民.UC安全的空间网络双向认证与密钥协商协议 ［J］.电子学报，2010，38 （10）：2358－2364.］

［11］LI Yahui，MA Jianfeng.Universally composable secure roaming authentication protocol for interworking networks ［J］.Computer Science，2010，37 （1）：47－50 （in Chinese）.［李亚晖，马建峰.一种基于融合网络通用可组合安全的漫游认证协议 ［J］.计算机科学，2010，37 （1）：47－50.］

［12］JIA Hongyong，QING Sihan，GU Lize，et al.Universally composable group key exchange protocol［J］.Journal of Electronics ＆ Information Technology，2009，31 （7）：1571－1575（in Chinese）.［贾洪勇，卿斯汉，谷利泽，等.通用可组合的组密钥交换协议 ［J］.电子与信息学报，2009，31（7）：1571－1575.］

［13］ZHANG Fan.The formal analysis methods of wireless network security protocol［D］.Xi’an：Xidian University，2007（in Chinese）.［张帆.无线网络安全协议的形式化分析方法［D］.西安：西安电子科技大学，2007.］

［14］YANG Chao.Analysis and design of wireless network protocols ［D］.Xi’an：Xi’an University，2008 （in Chinese）.［杨超.无线网络协议的形式化分析与设计 ［D］.西安：西安电子科技大学，2008.］

［15］ZHANG Junwei.Composition security of cryptographic protocols［D］.Xi’an：Xidian University，2010 （in Chinese）.张俊伟.密码协议的可组合安全 ［D］.西安：西安电子科技大学，2010.］

［16］DENG Miaolei，WANG Yulei，ZHOU Lihua.Universally composable three party password－authenticated key exchange protocol［J］.Journal of Electronics ＆Information Technology，2010，32 （8）：1948－1952 （in Chinese）.［邓淼磊，王玉磊，周利华.通用可组合的三方口令认证密钥交换协议 ［J］.电子与信息学报，2010，32 （8）：1948－1952.］

［17］CAO Chunjie.Design and analysis of provably secure authentication and key exchange protocols ［D］.Xi’an：Xidian University，2008（in Chinese）.［曹春杰.可证明安全的认证及密钥交换协议设计与分析 ［D］.西安：西安电子科技大学，2008.］

［18］Goldwasser S，Micali S，Rackoff C.The knowledge complexity of interactive proof systems ［J］.SIAM Journal on Comput，1989，18 （1）：186－208.

［19］Danny Dolev，Andrew，Yao C.On the security of public key protocols ［J］.IEEE Transactions on Information Theory，1983，29 （2）：198－208.