令G為某個乘法群-a-b-和cG-并有正整數x-y-和z在

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

b2。問題就是誰先發(fā)送，如果Alice先，Bob將可以選擇b2來控制投幣的結果。這并不公平。4.3公平投幣的要求(1)Bob必須在聽到Alice猜測之前就已經投幣。(2)Bob不能夠在聽到Alice猜測之后重復投幣。(3)Alice不能在其猜測之前得到投幣結果。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個數字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ā)出。在游戲結束后，Alice和Bob都公布自己的牌和密鑰對以確定沒有人在游戲中欺騙。5.2基于離散對數的撲克5.2基于離散對數的撲克