UC安全性證明中模擬器構(gòu)造方法研究

張 妤，黃周晶

（1.解放軍信息工程大學(xué) 電子技術(shù)學(xué)院，河南 鄭州450004；2.73671部隊，安徽 六安237008）

0 引 言

密碼協(xié)議復(fù)雜度和規(guī)模的日益增加使人們開始廣泛認識到組合方法在設(shè)計和分析密碼協(xié)議時的重要性。通用可組合安全分析模型［1］（UC模型）是用組合方法分析密碼協(xié)議的成功范例，由Ran Canetti于2001年提出。在該模型中被證明具有某個安全性質(zhì)的協(xié)議，當作為任意更大協(xié)議的組件時，或者和許多協(xié)議 （甚至未知協(xié)議）同時運行時，仍能保持該安全性質(zhì)。這對于密碼協(xié)議的模塊化設(shè)計和分析，以及在復(fù)雜甚至不可預(yù)測環(huán)境中 （比如因特網(wǎng)）協(xié)議的分析，是非常有利的。因此，國內(nèi)外已有不少對于UC模型的研究成果，密碼協(xié)議研究者在UC模型下針對特定密碼學(xué)任務(wù)進行研究，提出具有UC安全性的協(xié)議方案，如UC安全的電子現(xiàn)金［2］、零知識證明［3］、不經(jīng)意傳輸［4］、簽密［5］、安全多方計算［6］、數(shù)字簽名［7］、認證及密鑰交換［8－17］。

由此可見，自從UC模型提出以來直到現(xiàn)在，提出并證明具有UC安全性的密碼協(xié)議方案是國內(nèi)外絕大多數(shù)研究者所作的工作。UC安全性證明使用的是模擬證明方法（UC模擬并非其它學(xué)術(shù)領(lǐng)域中所提到的軟件模擬，而是利用計算復(fù)雜性進行的一種抽象模擬），其核心和難點是構(gòu)造模擬器。目前，模擬器的構(gòu)造是針對不同理想功能和協(xié)議進行的，尚沒有比較通用的方法可循。加之模擬器是使用交互式圖靈機的形式描述的，不能直觀反映模擬的本質(zhì)內(nèi)容，即便它模擬了一部分應(yīng)該模擬的操作，但是是否精確地模擬了全部應(yīng)該模擬的操作卻不容易檢查出來。更嚴重的是，如果本來不存在的模擬器被錯誤構(gòu)造出來 （因為目前大部分文獻中模擬器的構(gòu)造描述比較籠統(tǒng)無章，這種情況很可能出現(xiàn)），那本來不安全的協(xié)議就會得出UC安全的結(jié)論。本文正是在這樣的背景下進行研究，提出了一種較為通用的方法來構(gòu)造模擬器，使得遵循該方法構(gòu)造出來的模擬器是完善的 （模擬了所有應(yīng)該模擬的操作），并且錯誤的模擬器不會被構(gòu)造出來。這對于降低UC模型協(xié)議安全性證明出錯的概率是有意義的。

1 UC模型的基本概念

UC模型是基于不可區(qū)分性的計算復(fù)雜性理論模型，下面概述其中的基本概念。

UC模型中的計算模型是交互式圖靈機 （interactive Turing machine，ITM）［18］的通信網(wǎng)絡(luò)。協(xié)議π、敵手A和環(huán)境Z分別被建模為3個ITM。協(xié)議的執(zhí)行模型被建模為ITM之間的通信。其中環(huán)境ITM是協(xié)議ITM （內(nèi)部的各參與方又可被建模為子ITM）和敵手ITM的觀察者，可以觀察雙方的所有本地輸入和輸出，但無法觀察雙方的通信。環(huán)境根據(jù)觀察來得出結(jié)論：被觀察者是理想?yún)f(xié)議和模擬器（定義見下文），抑或是現(xiàn)實協(xié)議和敵手，并用輸出的一位二進制值來表示結(jié)論。

定義1（理想功能）一個理想功能F代表一個特定協(xié)議的期待功能。

技術(shù)上，一個理想功能是一個ITM，它的行為像許多不同ITM （被看成是多方協(xié)議的通信方）的一個子程序機器。一個理想功能的身份標識 （pid）被置為⊥，用于和其它ITM區(qū)分；并且一個理想功能只識別與自己的會話標識（sid）相同的ITM的輸入，忽略其它輸入。

定義2（理想?yún)f(xié)議）令F是理想功能。F的理想?yún)f(xié)議，表示為IDEALF，定義如下。每當通信方 （sid，pid）被輸入v激活，它就將v寫在F（sid，⊥）的輸入紙帶上。每當通信方在它的子程序返回值紙帶上收到一個值v，它就把這個值寫到Z的子程序返回值紙帶上。被A傳遞的消息，包括攻陷消息，都被忽略 （因為假定攻陷消息被敵手直接發(fā)送給理想功能）。

定義3（不可區(qū)分性）兩個二元分布X和Y是不可區(qū)分的 （記為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的多方協(xié)議。我們說πUC－模擬了 ，如果對于針對π的任何PPT敵手A存在一個針對 的PPT敵手S，使得對于任何PPT環(huán)境Z我們有

式中：EXECπ，A，Z——總體

式中：EXECπ，A，Z（k，z）——環(huán)境的輸出，是一個隨機變量。我們通常稱S為一個模擬器。

定義5（UC－實現(xiàn)）令F是一個理想功能，π是一個多方協(xié)議。我們說πUC－實現(xiàn)了F，如果πUC－模擬了F的理想?yún)f(xié)議。

定義6（混合協(xié)議）一個F混合協(xié)議π是一個包括調(diào)用F的理想?yún)f(xié)議的子程序的協(xié)議。

定義7（通用組合）給定協(xié)議 、協(xié)議π（它調(diào)用協(xié)議 ）、協(xié)議ρ（它UC－模擬協(xié)議 ），通用組合操作定義如下（通用組合操作后得到的協(xié)議記為πρ／）：

（1）若π中的一條指令為：傳送一個輸入到 （sid，pid），則用如下指令代替：傳送該輸入到ρ（sid，pid）。

（2）若πρ／收到一個從ρ （sid，pid’）傳來的輸出，它處理之如同π收到一個從 （sid，pid’）傳來的輸出。

當協(xié)議 是某個理想功能F的理想?yún)f(xié)議時，組合后的協(xié)議記為πρ／F。

定理1（組合定理）π、 和ρ是3個PPT的多方協(xié)議，π調(diào)用 ，ρUC－模擬 。那么協(xié)議πρ／UC－模擬協(xié)議ρ。

2 UC安全性證明中模擬器構(gòu)造方法研究

我們先來研究UC安全性的本質(zhì)要求，在此基礎(chǔ)上給出模擬器的存在條件和模擬內(nèi)容，最后提出構(gòu)造完善的模擬器的通用有效的方法。

2.1 UC安全性的本質(zhì)要求

雖然UC模型沒有直接給出UC安全性的定義，但聯(lián)系文獻 ［1］的上下文可以得出，作者定義的UC安全性（通用可組合安全性）實際上就是UC－實現(xiàn)：如果協(xié)議πUC－實現(xiàn)了理想功能F，則π具有F規(guī)定的安全性，并且該安全性在組合的條件下仍然保持。下文不妨設(shè)IDEALF＝ 。

依次運用定義5、定義4和定義3，我們得出，如果協(xié)議π具有F規(guī)定的組合安全性，則必然對于任何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）

即對于任何敵手，存在模擬器使得：對于足夠大的安全參數(shù)和安全參數(shù)的多項式長度的01序列輸入，運行協(xié)議π時環(huán)境的輸出的分布與運行理想?yún)f(xié)議 時環(huán)境的輸出的分布幾乎相同，其差別是可忽略的。

注意這里觀察協(xié)議π和協(xié)議 的是同一個環(huán)境，環(huán)境公正且忠實于自己的觀察，環(huán)境的輸出代表環(huán)境認為自己觀察的是理想?yún)f(xié)議的執(zhí)行還是實際協(xié)議的執(zhí)行，不妨設(shè)前者輸出1，后者輸出0。對于F的理想?yún)f(xié)議 ，顯然在任何情況下環(huán)境都會輸出1，即有

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

也就是要求環(huán)境觀察協(xié)議π的實際運行后，在絕大多數(shù)情況下都認為這是理想?yún)f(xié)議的運行！即，UC安全性實際上是要求，對于任何PPT敵手A，在外界環(huán)境看來，實際協(xié)議的執(zhí)行和理想中的情況幾乎一樣好！

由上面分析可見，理想功能是UC安全性的規(guī)范，它描述了協(xié)議的功能要求和安全要求，安全要求規(guī)定了允許的攻擊。即理想功能是協(xié)議對外界所有實體的安全接口標準，外界包括同一協(xié)議的其它實例、其它協(xié)議以及敵手。因此UC安全性的本質(zhì)要求是：允許協(xié)議在理想功能的功能要求之外完成某些額外的功能，但決不允許實際敵手所能實施的攻擊超出了理想功能的允許范圍，即 “功不抵過”。

UC安全性的本質(zhì)要求實際上決定了模擬器的存在性和模擬內(nèi)容。這是由于UC安全性證明是由 “模擬”完成的，正是通過模擬將現(xiàn)實執(zhí)行過程歸約到理想功能，完成協(xié)議的UC安全性證明。模擬的核心要求是構(gòu)造一個模擬器，該模擬器必須能與理想功能配合模仿實際協(xié)議運行的所有情況，這樣的模擬器的存在性直接影響UC安全性證明的結(jié)論。如果這樣的模擬器無論如何都構(gòu)造不出來 （存在性不成立），則協(xié)議不具有UC安全性，此時可能有兩種情況：要么是模擬器需要模擬的實際敵手的操作對理想功能實施不了，即實際敵手可以對實際協(xié)議實施某些理想功能不允許的攻擊 （圖1協(xié)議不是UC安全的。實際協(xié)議完成了所要求的功能，但實際敵手所能實施的攻擊超出了被允許的范圍。）；要么是實際協(xié)議沒能完成理想功能要求的全部功能 （圖2協(xié)議不是UC安全的。實際敵手所能實施的攻擊在被允許的范圍之內(nèi)，但實際協(xié)議沒完成所要求的全部功能。），這種情況下任何模擬器都無能為力。當然也可能這兩種情況同時發(fā)生 （圖3協(xié)議不是UC安全的。實際協(xié)議沒完成所要求的全部功能，且實際敵手所能實施的攻擊超出了被允許的范圍。）。如果上面的兩種情況均不發(fā)生，則這樣的模擬器可以被構(gòu)造出來 （存在性成立），模擬內(nèi)容包括實際敵手的攻擊、協(xié)議超額完成的功能和面向外界環(huán)境的接口。此時協(xié)議是UC安全的 （圖4協(xié)議是UC安全的。實際協(xié)議完成了所要求的全部功能，且實際敵手所能實施的攻擊在被允許的范圍之內(nèi)。），并且這種安全性在組合的條件下仍然成立。（圖1－圖4中F所在的方框表示理想功能；IA所在的三角框表示理想功能允許的攻擊；π所在的方框表示實際協(xié)議；A所在的三角框表示實際敵手能實施的攻擊。）

2.2 構(gòu)造模擬器的方法

由上節(jié)分析得知，如果該模擬器能夠構(gòu)造出來，則它應(yīng)該具有兩部分能力：一個是能模仿敵手的所有攻擊；另一個是能完成理想功能雖未要求、但協(xié)議卻實現(xiàn)了的功能。在此基礎(chǔ)上，模擬器還應(yīng)該模擬協(xié)議實際執(zhí)行時的對外接口。這樣理想情況和現(xiàn)實情況對于環(huán)境的視圖才不可區(qū)分。據(jù)此，本文給出構(gòu)造模擬器的有效方法：

（1）劃分協(xié)議的功能操作。根據(jù)理想功能要求的功能，將協(xié)議操作劃分為實現(xiàn)所要求功能的 “份內(nèi)”操作和實現(xiàn)要求外功能的 “額外”操作 （由于這一步只涉及功能而不涉及安全性，所以還是比較容易劃分的。比如密鑰交換協(xié)議的功能是參與者通過協(xié)議都得到一個密鑰，至于密鑰的一致性和機密性那是安全性要求，這一步先不考慮。這一步先保證每個參與者都得到一個密鑰，這就是 “份內(nèi)”功能）。如果無法劃分出完整的 “份內(nèi)”操作，則這樣的模擬器不存在，協(xié)議不安全，終止；如果可以劃分出完整的“份內(nèi)”操作 （可以沒有 “額外”操作），繼續(xù)進行下一步。

（2）模擬實際敵手的攻擊。對于實際敵手和實際協(xié)議操作的 “份內(nèi)”部分之間的消息傳遞，用模擬版敵手 （模擬敵手的全部功能）和理想功能進行預(yù)模擬，如果存在某個消息傳遞時理想功能不支持的情況，則模擬器不存在，協(xié)議不安全，終止；否則，模擬器S存在，繼續(xù)進行下一步。

（3）模擬協(xié)議超額完成的功能。模擬器S模擬協(xié)議的“額外”操作，我們稱之為模擬版 “額外”協(xié)議，繼續(xù)進行下一步。

（4）模擬協(xié)議實際執(zhí)行時的對外接口。模擬器S模擬消息傳遞過程，具體做法如下：

1）對于實際敵手和實際協(xié)議操作的 “份內(nèi)”部分之間的消息傳遞，模擬器用模擬版敵手和理想功能進行同樣的消息傳遞；

2）對于實際敵手和實際協(xié)議操作的 “額外”部分之間的消息傳遞，模擬器用模擬版敵手和模擬版 “額外”協(xié)議進行同樣的消息傳遞；

3）對于實際敵手和環(huán)境之間的消息傳遞，模擬器用模擬版敵手和環(huán)境進行同樣的消息傳遞；

4）對于實際協(xié)議操作的 “份內(nèi)”部分和環(huán)境之間的消息傳遞，模擬器用理想功能和環(huán)境進行同樣的消息傳遞；

5）對于實際協(xié)議操作的 “額外”部分和環(huán)境之間的消息傳遞，模擬器用模擬版 “額外”協(xié)議和環(huán)境進行同樣的消息傳遞。

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

模擬器構(gòu)造方法的正確性應(yīng)從兩個方面來檢查：一方面，協(xié)議不安全或沒完成全部目標功能時，使用該方法能夠排除構(gòu)造出模擬器的可能性；另一方面，當協(xié)議完成全部目標功能且安全時，使用該方法能夠確保構(gòu)造出的模擬器使環(huán)境對理想執(zhí)行和現(xiàn)實執(zhí)行的視圖是一樣的，即理想執(zhí)行和現(xiàn)實執(zhí)行是不可區(qū)分的。

我們從這兩個方面來分析本文所提出的方法。首先，當協(xié)議沒完成全部目標功能時，我們方法的第1步排除了構(gòu)造出模擬器的可能性；當協(xié)議不安全時，我們方法的第2步排除了構(gòu)造出模擬器的可能性；其次，當協(xié)議完成全部目標功能且安全時，我們方法的第2步還模仿了實際協(xié)議的敵手在理想執(zhí)行中所缺少的對應(yīng)物；我們方法的第3步模仿了實際協(xié)議的額外操作在理想執(zhí)行中所缺少的對應(yīng)物；我們方法的第4步則模仿了實際協(xié)議執(zhí)行的全部對外接口在理想執(zhí)行中的對應(yīng)物 （對應(yīng)圖5和圖6中箭頭旁邊的序號，圖中以兩方協(xié)議為例。具體模擬時，對于涉及到的各個參與者的消息傳遞應(yīng)分別模擬）。圖6中的網(wǎng)格陰影部分就是我們方法的全部模擬內(nèi)容。從圖5和圖6的對比可以看出，我們方法的模擬內(nèi)容加上理想功能，正好精確地模仿了現(xiàn)實協(xié)議的執(zhí)行。從環(huán)境的角度來看，這兩種情況的視圖 （即兩個圖中虛線以下的部分）是一樣的。

根據(jù)上面的分析，本文提出的模擬器構(gòu)造方法是正確有效的。

3 結(jié)束語

通過本文的研究得出，UC模型的通用可組合安全性的本質(zhì)與其它理論模型或工程系統(tǒng)中模塊化設(shè)計和分析的思路是一致的——即提供通用標準接口，而接口標準化是模塊化設(shè)計和分析所有系統(tǒng)的前提?？梢?，雖然UC模型高度抽象，但是抽絲剝繭的分析表明它和其它系統(tǒng)的模塊化思想不謀而合。因此我們有理由相信，UC模型是一套有實際意義和發(fā)展前途的理論。特別是在傳統(tǒng)的分析密碼協(xié)議的非組合型模型在分析大型復(fù)合密碼協(xié)議時逐漸力不從心的情況下，UC模型這種組合型模型則優(yōu)勢漸顯。然而，這種優(yōu)勢的代價是模型自身比較復(fù)雜，而且還在不斷的發(fā)展完善之中。希望本文對于UC模型的基本構(gòu)建原理和安全性證明方法的研究在一定程度上能給以同行基礎(chǔ)思路上的啟示和借鑒。未來的研究工作將圍繞UC模型和Dolev－Yao［19］模型的結(jié)合開展研究。

［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安全理論及應(yīng)用研究 ［D］.濟南：山東大學(xué)，2009.］

［6］LEI Feiyu.Studies on UC secure multiparty computation and its applications［D］.Shanghai：Shanghai Jiaotong University，2007（in Chinese）.［雷飛宇.UC安全多方計算模型及其典型應(yīng)用研究 ［D］.上海：上海交通大學(xué)，2007.］

［7］HONG Xuan.Studies on universally composable digital signature and its key problems［D］.Shanghai：Shanghai Jiaotong University，2008（in Chinese）.［洪璇.通用可組合數(shù)字簽名模型及其關(guān)鍵問題研究 ［D］.上海：上海交通大學(xué)，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安全的空間網(wǎng)絡(luò)雙向認證與密鑰協(xié)商協(xié)議 ［J］.電子學(xué)報，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）.［李亞暉，馬建峰.一種基于融合網(wǎng)絡(luò)通用可組合安全的漫游認證協(xié)議 ［J］.計算機科學(xué)，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）.［賈洪勇，卿斯?jié)h，谷利澤，等.通用可組合的組密鑰交換協(xié)議 ［J］.電子與信息學(xué)報，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）.［張帆.無線網(wǎng)絡(luò)安全協(xié)議的形式化分析方法［D］.西安：西安電子科技大學(xué)，2007.］

［14］YANG Chao.Analysis and design of wireless network protocols ［D］.Xi’an：Xi’an University，2008 （in Chinese）.［楊超.無線網(wǎng)絡(luò)協(xié)議的形式化分析與設(shè)計 ［D］.西安：西安電子科技大學(xué)，2008.］

［15］ZHANG Junwei.Composition security of cryptographic protocols［D］.Xi’an：Xidian University，2010 （in Chinese）.張俊偉.密碼協(xié)議的可組合安全 ［D］.西安：西安電子科技大學(xué)，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）.［鄧淼磊，王玉磊，周利華.通用可組合的三方口令認證密鑰交換協(xié)議 ［J］.電子與信息學(xué)報，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）.［曹春杰.可證明安全的認證及密鑰交換協(xié)議設(shè)計與分析 ［D］.西安：西安電子科技大學(xué)，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.