第二十二講秘密分享和游戲

第二十二講秘密分享和游戲

秘密分享方案是與密鑰建立相關(guān)的多方協(xié)議。秘密分享的原始動機是：為了保證密碼密鑰不丟失，希望產(chǎn)生密鑰備份，但是越多的密鑰備份，密鑰泄露的可能就越大；越少的密鑰備份，密鑰丟失的可能就越大。秘密分享方案就是用來提高密鑰可靠性而不增加泄露風險的方法?，F(xiàn)代密碼學的一個主要成就在于高級安全協(xié)議的發(fā)展。這些協(xié)議可以讓用戶在網(wǎng)上解決現(xiàn)實世界中許多問題，進行各種游戲，也能執(zhí)行各種有趣而復(fù)雜的分布任務(wù)。投幣和撲克協(xié)議將在這一講中做簡要介紹。本講提要秘密分享的應(yīng)用秘密分割門限方案投幣協(xié)議撲克協(xié)議1秘密分享的應(yīng)用1.1秘密分割假定你發(fā)明了一種烹飪食物方法。這一方法比目前已知的方法都好。對方法保密在市場競爭激烈的環(huán)境下十分重要。你可能僅會告訴最為信任的雇員具體方法，但雇員如果為競爭對手收買該怎么辦？可能人人都可以按照這一方法烹飪食物。1.1秘密分割(續(xù))

這就需要秘密分割。方法是將一個消息分割成碎片，每一個碎片沒有任何意義，但是合在一起就可以重現(xiàn)消息。有了秘密分割技術(shù)烹飪方法可以作為消息，而每個雇員只能拿到一個碎片，僅當他們聯(lián)合才能恢復(fù)出烹飪方法。如果任何雇員離職，他帶走的僅是自己的一個碎片，這一信息本身并無用處。

但是，這仍然存在問題：如果任意一個碎片丟失，則消息無法恢復(fù)。如果一個雇員有烹飪方法的一個碎片而他去為競爭對手工作并將其碎片帶走，那么其他雇員就沒有那么幸運了。離職雇員雖然不能產(chǎn)生烹飪方法，但他可以不在參與恢復(fù)烹飪方法。他的碎片與其它碎片一樣對恢復(fù)消息至關(guān)重要。1.2關(guān)于門限方案你在為核導(dǎo)彈安裝發(fā)射程序。你想確信一個瘋子是不能啟動發(fā)射，也不希望兩個瘋子就能啟動發(fā)射。在你允許發(fā)射前，五個軍官至少有三個是瘋子。這是一個容易解決的問題。做一個機械發(fā)射控制器，給五個軍官每個人一把鑰匙，并且只有在至少三個軍官的鑰匙插入適合的槽中才允許他們起爆。

我們甚至可以把問題變得更為復(fù)雜。也許將軍和兩個上校被授權(quán)發(fā)射導(dǎo)彈，但如果將軍正在打高爾夫球，那么啟動發(fā)射需要五名上校。制造一個發(fā)射控制器，該發(fā)射控制器需要5把鑰匙。給將軍3把，給每位上校1把。將軍和任意兩名上校，或者五名上校一起都可以發(fā)射導(dǎo)彈，然而，將軍和一名上校，或四名上校就不能。

一個稱為門限方案(thresholdscheme)的更復(fù)雜的秘密分享方案，可以在數(shù)學上做到這些甚至更多。起碼，可以取任意消息(秘密配方，發(fā)射代碼，洗衣價目表)并把它分成n部分，每個部分叫它的影子或分享，它們中的任何m部分能夠用來重構(gòu)消息。

我們可以將烹飪方法分給Alice，Bob，Carol，和Dave，這樣把他們中的任意三個影子放在一起就能重構(gòu)消息。如果Carol正在渡假，那么Alice，Bob，和Dave可以考慮做這件事情；如果Bob被汽車撞了，那么Alice，Carol，和Dave可以考慮做這件事情。然而，如果Bob被汽車撞了并且Carol正在渡假，Alice和Dave就不可能重構(gòu)消息。2秘密分割2.1使用模加的二重控制2.1使用模加的二重控制(續(xù))2.2使用模加的一致同意控制2.2使用模加的一致同意控制(續(xù))3門限方案3.1Shamir的門限方案3.1Shamir的門限方案(續(xù))3.1Shamir的門限方案(續(xù))3.1Shamir的門限方案(續(xù))3.1Shamir的門限方案(續(xù))3.1Shamir的門限方案(續(xù))3.1Shamir的門限方案(續(xù))3.1Shamir的門限方案(續(xù))3.1Shamir的門限方案(續(xù))3.2向量方案3.2向量方案(續(xù))3.2向量方案(續(xù))3.2向量方案(續(xù))3.2向量方案(續(xù))3.2向量方案(續(xù))3.3存在騙子的秘密分享

上校Alice，Bob，和Carol在某個隔離區(qū)很深的地下掩體中。一天，他們從總統(tǒng)那里得到密碼消息：“發(fā)射導(dǎo)彈，我們要根除邪惡國家?！?/p>

Alice，Bob，和Carol出示他們的分享，但Carol拿出的只是一個隨機數(shù)。她實際是一個和平主義者，不想發(fā)射導(dǎo)彈。由于Carol的錯誤輸入信息，他們恢復(fù)出來錯誤的秘密。導(dǎo)彈還停留在發(fā)射井里。更糟糕的是，沒人知道究竟是誰在其中搗鬼。3.3存在騙子的秘密分享(續(xù))3.3存在騙子的秘密分享(續(xù))3.3存在騙子的秘密分享(續(xù))4投幣協(xié)議4.1應(yīng)用實例一個朋友沒有意識到Alice和Bob不在一個地方，留給他們了一輛汽車。他們將怎樣決定汽車的歸屬呢？Bob打個給Alice建議由他投幣來決定。Alice說選擇“背面”，但Bob說我投出的是“正面”。于是車歸了Bob。這里Alice完全有理由懷疑Bob的誠實。下一次，她可能選擇別的辦法決定這一問題。4.2一個解決方法這里有一個思路，就是Alice隨機的選擇一個比特b1發(fā)給Bob，Bob也隨機的選擇一個比特b2發(fā)給Alice，投幣的結(jié)果就是b1

b2。問題就是隨先發(fā)送，如果Alice先，Bob將可以選擇b2來控制投幣的結(jié)果。這并不公平。4.3公平投幣的要求

(1)Bob必須在聽到Alice猜測之前就已經(jīng)投幣。

(2)Bob不能夠在聽到Alice猜測之后重復(fù)投幣。

(3)Alice不能在其猜測之前得到投幣結(jié)果。4.4使用平方根的投幣AliceBob4.4使用平方根的投幣(續(xù))4.4使用平方根的投幣(續(xù))4.4使用平方根的投幣(續(xù))4.4使用平方根的投幣(續(xù))4.4使用平方根的投幣(續(xù))4.4使用平方根的投幣(續(xù))5撲克協(xié)議一個類似于公平投幣的協(xié)議就是撲克協(xié)議，它允許Alice和Bob在兩端玩撲克。不同于處理“正面”和“反面”兩條消息，Bob需要處理分別代表每一張牌的52個數(shù)字c1，c2，...，c52。如何保證在游戲中沒有欺詐？5.1思想

Bob用自己的加密密鑰加密牌c1，c2，...，c52發(fā)送給Alice。Alice隨機選擇5張牌，用自己的加密密鑰加密，發(fā)還給Bob。Bob解密這些牌后發(fā)還給Alice，她再解密決定自己手中的5張牌。Alice再隨機選擇5張牌發(fā)給Bob。Bob解密它們得到自己的5張牌。5.1思想(續(xù))

在游戲的過程中，剩下的牌可以按照同樣的方法發(fā)出。在游戲結(jié)束后，Alice和Bob都公布自己的牌和密鑰對以確定沒有人在游戲中欺騙。5.2基于離散對數(shù)的撲