從博弈論角度看安全計(jì)算

1、從博弈論角度看安全計(jì)算Gilad Asharov Ran Canettiy Carmit HazayzMarch 17, 2011Department of Computer Science, Bar-Ilan University, Israel. Supported by the European Research Council aspart of the ERC project LAST. HYPERLINK mailto:asharogcs.biu.ac.il asharogcs.biu.ac.il摘 要：本文從博弈論概念和形式化的角度探討了密碼學(xué)的安全概念，在限制條 件。面對(duì)限制條

2、件苛刻的兩方安全協(xié)議的惡意-停止問題，我們首次引入理性參 與者，借助于博弈論的納什均衡概念解決傳統(tǒng)協(xié)議的保密性和正確性。其次，我 們集中研究這種意義下的公平性，在此我們基于博弈論提出兩個(gè)密碼學(xué)概念，并 證明它們是等價(jià)的。最后，對(duì)上術(shù)三個(gè)概念給出了模擬概念。上述的的相關(guān)概念 比現(xiàn)有的密碼學(xué)協(xié)議的安全性和公平性概念的要求減弱，尤其是，這些協(xié)議更符 合現(xiàn)實(shí)，同時(shí)解決了現(xiàn)有的公平性被證明是不可能實(shí)現(xiàn)的問題。ContentsIntroduction 2The Model and Solution Concepts 6 TOC o 1-5 h z Cryptographic De_nitions6Cryp

3、tographic Security7Game Theoretic De_nitions8Privacy and Correctness in Game Theoretic View 11Privacy in Game Theoretic view11Correctness in Game Theoretic view14Exploring Fairness in the Two-Party Setting 17Fairness in Game Theoretic View18A New Indistinguishability-Based Definition of Fairness19Th

4、e Gradual Release Property22A New Notion of Simulation Based Security26Simulation Based Security with Fairness28Simulation-Based De_nition Implies Game-Based Fairness31The Feasibility of Our De_nition34An Impossibility Result34A Positive Result36A Dealing with Expected Round Complexity 41博弈論和密碼協(xié)議都是致

5、力于解決多方協(xié)同的復(fù)雜性與利益欺詐問題，從這 個(gè)角度來說，這兩個(gè)研究分支的觀點(diǎn)是相同的：算法的設(shè)計(jì)及分析是解決參與者 的協(xié)作。然而，它們的目標(biāo)和形式有所不同，密碼學(xué)側(cè)重于在對(duì)手有惡意行為時(shí)， 設(shè)計(jì)協(xié)議算法解決保密性、正確性或公平性；而博弈論面對(duì)的環(huán)境更開放，參與 者從理性出發(fā)，對(duì)手通過定義目標(biāo)，從自私本性需求設(shè)計(jì)交互策略以獲得最大利 益。不過，盡管有這些不同點(diǎn)，但這兩個(gè)分支的交叉研究取得了一些非常豐富的 成果（24, 6 ）。一個(gè)很自然的方向是使用加密技術(shù)解決傳統(tǒng)的博弈論問題， 其中主要有 Dodis 等人5、Ismalkov 等人23，22 、Abraham 等人1，Halpern 和Pas

6、s 21 延著這條思路，探討了在一個(gè)安全多方計(jì)算協(xié)議的中如何使用加密技 術(shù)，取代可信設(shè)備或機(jī)制設(shè)計(jì)中的可信第三方。另一方面的研究是通過考慮密碼學(xué)的思想和所關(guān)注的需求，以及計(jì)算能力和 和計(jì)算代價(jià)的限制，擴(kuò)展傳統(tǒng)的博弈論的內(nèi)容以適應(yīng)密碼的需求5, 21，19。這種研究的目的是使用博弈論的概念和方法修改傳統(tǒng)密碼學(xué)的目標(biāo)，如安全 性和公平性。該研究的關(guān)鍵是定義合理的秘密信息的公平交換的概念（即被公認(rèn) 為是理性秘密共享）20，17，27，25，26，28，7，2。這里的目標(biāo)是設(shè)計(jì)一個(gè) 交換協(xié)議，理性參與者都會(huì)遵守協(xié)議的執(zhí)行，他希望能獲取其他參與者的秘密， 但又不希望他人得到自己的秘密。事實(shí)上，這是假設(shè)參

7、與者有特定的偏好及對(duì)偏 好先驗(yàn)知識(shí)的量化方法，這種事先了解先驗(yàn)知識(shí)是必不可少的，否則不可能得到 結(jié)果2, 4。這些工作給出了解決有合作又有競爭的參與者方的協(xié)議理論和方法，但同 時(shí)，也指出了博弈論和密碼學(xué)是兩種基本不兼容的理論形式。例如，博弈論在工 程中使用于理性的秘密共享似乎不適合于密碼學(xué)的初衷，如加密的語義安全。相 反，這些工作提出更簡單的概念更難兼容傳統(tǒng)的密碼學(xué)。特別是，現(xiàn)有的建模是 將要交換的秘密視為一個(gè)原子單位，這樣的話任何一方要么得到完整的秘密，要 么什么也得不到。與傳統(tǒng)的加密建模不同，這里考慮通過執(zhí)行協(xié)議傳輸部分秘密 的問題。本文工作。我們研究兩個(gè)形式化問題。首先是我們?nèi)绾卫貌┺?/p>

8、理論形式化 傳統(tǒng)密碼學(xué)協(xié)議的安全性定義，我們集中考慮兩方協(xié)議和失敗-停止攻擊模型。 研究的核心是當(dāng)有惡意攻擊時(shí)，如何實(shí)現(xiàn)協(xié)議的保密性、正確性和公平性。在論文中，我們首先分別給出博弈理論意義下的保密性和正確性概念，正確 地評(píng)價(jià)fail-stop確定性函數(shù)設(shè)置（文獻(xiàn)10）。然后我們將注意力轉(zhuǎn)向公平性，這 種情況更復(fù)雜的，我們形式化一個(gè)自然的博弈論觀念下的公平性，它比現(xiàn)有的兩 方協(xié)議的公平性的要求條件要弱。然后我們提出基于博弈論意義下的密碼協(xié)議的 定義，然后從仿真的角度評(píng)估上述三個(gè)內(nèi)容。結(jié)果，我們發(fā)現(xiàn)這些新觀念下的公 平性在特定意義是可以實(shí)現(xiàn)的，而對(duì)于傳統(tǒng)密碼協(xié)議的公平性卻是不能達(dá)到的。更詳細(xì)的結(jié)果

9、討論?；镜乃枷肴缦拢寒?dāng)且僅當(dāng)某對(duì)策略（來源于協(xié)議）是 在一個(gè)計(jì)算納什均衡的條件下，我們探討如何將傳統(tǒng)的密碼協(xié)議轉(zhuǎn)換博弈意義下 的一套協(xié)議理論，它允許用博弈語言實(shí)現(xiàn)密碼中的提問與應(yīng)答。更確切地說，給 定一個(gè)協(xié)議，我們考慮了不完全信息的擴(kuò)展形式博弈的情況，每一步中局中人能 決定要么繼續(xù)運(yùn)行這個(gè)協(xié)議，或者終止協(xié)議執(zhí)行，我們可以通過一對(duì)策略，在一 個(gè)（計(jì)算）納什均衡條件下指導(dǎo)局中人繼續(xù)該議的完成。每一個(gè)密碼特性可以在用 一個(gè)合適的效用函數(shù)和輸入分配選擇下得滿足，包括：保密性。一個(gè)給定的協(xié)議是保密的（類似10）當(dāng)且僅當(dāng)在如下的效用函數(shù)和輸 入分布下，具有不中斷該協(xié)議的博弈策略。在每一對(duì)策略集中，我們定

10、義一 個(gè)分配算法為每一方隨機(jī)從策略對(duì)中選擇一個(gè)策略，由于得到相同利益輸出 值使得另一方無法猜出選擇哪一個(gè)策略，這可以認(rèn)為是第一次給出博弈觀念 下的傳統(tǒng)密碼系統(tǒng)的保密性（在文獻(xiàn)14）的工作是關(guān)于理性的秘密共享，但它 未給出這一層次的保密性概念。正確性。一個(gè)協(xié)議能正確計(jì)算一個(gè)確定性的函數(shù)當(dāng)且僅當(dāng)在給定的效用函數(shù) 和選擇輸入分配下，具有不中斷該協(xié)議的博弈策略，且只有正確的函數(shù)輸出 值時(shí)才獲得高回報(bào)，而在流產(chǎn)協(xié)議中斷前，不正確的函數(shù)輸出值是不能得到 任何利益回報(bào)的。公平性。這是本文的主要工作。我們首先給定基本設(shè)置：雙方在各自輸入的 基礎(chǔ)上，通過交換信息以計(jì)算函數(shù)f，唯一允許偏離協(xié)議是中止，在雙方都 得

11、到協(xié)議的輸出的情況下被中止。因此，一個(gè)協(xié)議在該模型中應(yīng)該明確，除 了發(fā)送到下一個(gè)信息外，預(yù)測輸出值應(yīng)該中止。（雖然這個(gè)設(shè)置對(duì)任何函數(shù)不 一有意義，但它有助于記憶公平交換函數(shù)，以避免某一方用其它方的輸出作 為輸入）。目前的公平性概念是將雙方的完整輸出作為一個(gè)計(jì)算點(diǎn)（例如，18, 16）， 雙方不能從沒有任何的輸出值狀態(tài)慢慢轉(zhuǎn)移到它獲得一個(gè)完整的知識(shí)。這是一個(gè) 很強(qiáng)的要求，在許多情況下這是不可能實(shí)現(xiàn)的。相反，我們想探討更寬松的公平 性概念，讓雙方通過逐步了解其預(yù)期的部分輸出信息到獲得期望的完整輸出，這 種過程也理解為公平，事實(shí)上，這樣的做法是合理的，無論是從博弈理論觀點(diǎn)（可 看作為一個(gè)零-和博弈）

12、還是從逐步釋放的方式的密碼學(xué)觀點(diǎn)（見3, 13, 9, 18, 2）來看。該公平性概念首先要注意的是，雙方的輸入可能成為對(duì)方敏感的潛在先驗(yàn) 知識(shí)。的確，一個(gè)逐步釋放協(xié)議，在一方比另一方獲得更多知識(shí)的情況下，沒有 先驗(yàn)知識(shí)的公平協(xié)議可能會(huì)變得不公平，反之亦然。在此我們明確我們的安全概念，每一方都給出輸入值，每一方除了自身的輸 入外，不知道對(duì)方任何額外的輸入信息。此外，為了簡化問題，我們假設(shè)在雙方 平等的基礎(chǔ)上，參與者的輸入信息只包含兩個(gè)可能值輸入，這樣每一方得到三個(gè) 值：自己的輸入、對(duì)方的兩個(gè)可能的輸入值。事實(shí)上，這種信息捕捉自然的情況 下，域可能投入?。ɡ纾M(jìn)制）。形式主義也可以自然地?cái)U(kuò)展

13、處理領(lǐng)域的小 尺寸大于2。4 Exploring Fairness in the Two-Party Setting 17Fairness in Game Theoretic View從博弈論的觀點(diǎn)建立了協(xié)議的隱私性和正確性的概念，下面我們將從博弈 論的觀點(diǎn)建立協(xié)議的公平性。然而，這在原來是很棘手的，這主要是由于高度對(duì) 等的這一要求的微妙性質(zhì)。進(jìn)一步說就是，公平性就是要實(shí)現(xiàn)這樣的簡單需求： 兩方中的一方得到正確輸出，當(dāng)且僅當(dāng)另一方也得到正確的輸出。然而，自然看 起來，這個(gè)定義是有缺陷，因?yàn)樗サ氖敲恳环降恼w輸出作為一個(gè)原子單元， 沒有考慮部分通過部分信息輸出后進(jìn)行收集成整體的情況，這樣的話，

14、參與者要 么得到完整信息，要么一點(diǎn)信息都得不到。所以，這里我們更愿意給出另一個(gè)定 義，稱協(xié)議是公平的，如果雙方在執(zhí)行到任何一點(diǎn)上，都可以通過收集得到各自 的輸出的部分信息。出于以上討論，我們將引入博弈論進(jìn)來，目的是給出一個(gè)更任命實(shí)際意義 的公平性定義，正如我們定義的隱私性和正確性那樣。舉例來說，這將允許調(diào)查 已知一個(gè)新的光下是不可能的結(jié)果。我們的出發(fā)點(diǎn)是在游戲過程中，每一個(gè)黨失 去ominatively其他黨猜測其輸出的成功概率的定義，檢查有關(guān)其輸出各方獲得 的信息。（這是出于同樣的道理，在隱私）。為了得到這一點(diǎn)，我們首先定義一 個(gè)新的公平，而我們需要游戲?qū)⒓{什的效用函數(shù)設(shè)置為完整的細(xì)節(jié)，見4.1節(jié)。在理性參與的各方定義公平性，我們要研究其密碼攻擊的強(qiáng)度。因此，我們?yōu)閮?方協(xié)議引入一個(gè)新的基于博弈的公平性形式化定義，實(shí)際上，是相當(dāng)于博弈論定 義。然后，我們提供了一個(gè)逐步釋放的新定義，即相當(dāng)于博弈論為主體的博弈公 平定義。最后，我們基于該定義提出了模擬概念，基于此研究新的公平性理念的 實(shí)現(xiàn)。這里包括了一個(gè)逐步釋放屬性的新定義（參見4.3節(jié)），根據(jù)我們的相關(guān) 公平概念，提出具有此屬性的協(xié)議是