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.