令G為某個(gè)乘法群-a-b-和cG-并有正整數(shù)x-y-和z在

令G為某個(gè)乘法群,a,b,和cG,并有正整數(shù)x,y,和z。在.ppt第十五講秘密分享與游戲秘密分享方案是與密鑰建立相關(guān)的多方協(xié)議。秘密分享的原始動(dòng)機(jī)是：為了保證密碼密鑰不丟失，希望產(chǎn)生密鑰備份，但是越多的密鑰備份，密鑰泄露的可能就越大；越少的密鑰備份，密鑰丟失的可能就越大。秘密分享方案就是用來(lái)提高密鑰可靠性而不增加泄露風(fēng)險(xiǎn)的方法?，F(xiàn)代密碼學(xué)的一個(gè)主要成就在于高級(jí)安全協(xié)議的發(fā)展。這些協(xié)議可以讓用戶在網(wǎng)上解決現(xiàn)實(shí)世界中許多問(wèn)題，進(jìn)行各種游戲，也能執(zhí)行各種有趣而復(fù)雜的分布任務(wù)。電話投幣和撲克協(xié)議將在這一講中做簡(jiǎn)要介紹。本講提要秘密分享的應(yīng)用秘密分割門限方案電話投幣協(xié)議電話撲克協(xié)議1秘密分享的應(yīng)用1.1秘密分割假定你發(fā)明了一種烹飪食物方法。這一方法比目前已知的方法都好。對(duì)方法保密在市場(chǎng)競(jìng)爭(zhēng)激烈的環(huán)境下十分重要。你可能僅會(huì)告訴最為信任的雇員具體方法，但雇員如果為競(jìng)爭(zhēng)對(duì)手收買該怎么辦？可能人人都可以按照這一方法烹飪食物。1.1秘密分割(續(xù))這就需要秘密分割。方法是將一個(gè)消息分割成碎片，每一個(gè)碎片沒(méi)有任何意義，但是合在一起就可以重現(xiàn)消息。有了秘密分割技術(shù)烹飪方法可以作為消息，而每個(gè)雇員只能拿到一個(gè)碎片，僅當(dāng)他們聯(lián)合才能恢復(fù)出烹飪方法。如果任何雇員離職，他帶走的僅是自己的一個(gè)碎片，這一信息本身并無(wú)用處。但是，這仍然存在問(wèn)題：如果任意一個(gè)碎片丟失，則消息無(wú)法恢復(fù)。如果一個(gè)雇員有烹飪方法的一個(gè)碎片而他去為競(jìng)爭(zhēng)對(duì)手工作并將其碎片帶走，那么其他雇員就沒(méi)有那么幸運(yùn)了。離職雇員雖然不能產(chǎn)生烹飪方法，但他可以不在參與恢復(fù)烹飪方法。他的碎片與其它碎片一樣對(duì)恢復(fù)消息至關(guān)重要。1.2關(guān)于門限方案你在為核導(dǎo)彈安裝發(fā)射程序。你想確信一個(gè)瘋子是不能啟動(dòng)發(fā)射，也不希望兩個(gè)瘋子就能啟動(dòng)發(fā)射。在你允許發(fā)射前，五個(gè)軍官至少有三個(gè)是瘋子。這是一個(gè)容易解決的問(wèn)題。做一個(gè)機(jī)械發(fā)射控制器，給五個(gè)軍官每個(gè)人一把鑰匙，并且只有在至少三個(gè)軍官的鑰匙插入適合的槽中才允許他們起爆。我們甚至可以把問(wèn)題變得更為復(fù)雜。也許將軍和兩個(gè)上校被授權(quán)發(fā)射導(dǎo)彈，但如果將軍正在打高爾夫球，那么啟動(dòng)發(fā)射需要五名上校。制造一個(gè)發(fā)射控制器，該發(fā)射控制器需要5把鑰匙。給將軍3把，給每位上校1把。將軍和任意兩名上校，或者五名上校一起都可以發(fā)射導(dǎo)彈，然而，將軍和一名上校，或四名上校就不能。一個(gè)稱為門限方案(thresholdscheme)的更復(fù)雜的秘密分享方案，可以在數(shù)學(xué)上做到這些甚至更多。起碼，可以取任意消息(秘密配方，發(fā)射代碼，洗衣價(jià)目表)并把它分成n部分，每個(gè)部分叫它的影子或分享，它們中的任何m部分能夠用來(lái)重構(gòu)消息。我們可以將烹飪方法分給Alice，Bob，Carol，和Dave，這樣把他們中的任意三個(gè)影子放在一起就能重構(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在某個(gè)隔離區(qū)很深的地下掩體中。一天，他們從總統(tǒng)那里得到密碼消息：“發(fā)射導(dǎo)彈，我們要根除邪惡國(guó)家?！盇lice，Bob，和Carol出示他們的分享，但Carol拿出的只是一個(gè)隨機(jī)數(shù)。她實(shí)際是一個(gè)和平主義者，不想發(fā)射導(dǎo)彈。由于Carol的錯(cuò)誤輸入信息，他們恢復(fù)出來(lái)錯(cuò)誤的秘密。導(dǎo)彈還停留在發(fā)射井里。更糟糕的是，沒(méi)人知道究竟是誰(shuí)在其中搗鬼。3.3存在騙子的秘密分享(續(xù))3.3存在騙子的秘密分享(續(xù))3.3存在騙子的秘密分享(續(xù))4電話投幣協(xié)議4.1應(yīng)用實(shí)例一個(gè)朋友沒(méi)有意識(shí)到Alice和Bob不在一個(gè)地方，留給他們了一輛汽車。他們將怎樣決定汽車的歸屬呢？Bob打個(gè)電話給Alice建議由他投幣來(lái)決定。Alice說(shuō)選擇“背面”，但Bob說(shuō)我投出的是“正面”。于是車歸了Bob。這里Alice完全有理由懷疑Bob的誠(chéng)實(shí)。下一次，她可能選擇別的辦法決定這一問(wèn)題。4.2一個(gè)解決方法這里有一個(gè)思路，就是Alice隨機(jī)的選擇一個(gè)比特b1發(fā)給Bob，Bob也隨機(jī)的選擇一個(gè)比特b2發(fā)給Alice，投幣的結(jié)果就是b1

b2。問(wèn)題就是誰(shuí)先發(fā)送，如果Alice先，Bob將可以選擇b2來(lái)控制投幣的結(jié)果。這并不公平。4.3公平投幣的要求(1)Bob必須在聽(tīng)到Alice猜測(cè)之前就已經(jīng)投幣。(2)Bob不能夠在聽(tīng)到Alice猜測(cè)之后重復(fù)投幣。(3)Alice不能在其猜測(cè)之前得到投幣結(jié)果。4.4使用平方根的投幣AliceBob4.4使用平方根的投幣(續(xù))4.4使用平方根的投幣(續(xù))4.4使用平方根的投幣(續(xù))4.4使用平方根的投幣(續(xù))4.4使用平方根的投幣(續(xù))4.4使用平方根的投幣(續(xù))5電話撲克協(xié)議一個(gè)類似于公平投幣的協(xié)議就是電話撲克協(xié)議，它允許Alice和Bob在電話兩端玩撲克。不同于處理“正面”和“反面”兩條消息，Bob需要處理分別代表每一張牌的52個(gè)數(shù)字c1，c2，...，c52。如何保證在游戲中沒(méi)有欺詐？5.1思想Bob用自己的加密密鑰加密牌c1，c2，...，c52發(fā)送給Alice。Alice隨機(jī)選擇5張牌，用自己的加密密鑰加密，發(fā)還給Bob。Bob解密這些牌后發(fā)還給Alice，她再解密決定自己手中的5張牌。Alice再隨機(jī)選擇5張牌發(fā)給Bob。Bob解密它們得到自己的5張牌。5.1思想(續(xù))在游戲的過(guò)程中，剩下的牌可以按照同樣的方法發(fā)出。在游戲結(jié)束后，Alice和Bob都公布自己的牌和密鑰對(duì)以確定沒(méi)有人在游戲中欺騙。5.2基于離散對(duì)數(shù)的撲克5.2基于離散對(duì)數(shù)的撲克