1、令G為某個乘法群，a, b, 和c?G，并有正整數(shù)x, y, 和z。在各參數(shù)為指數(shù)規(guī)模時，請設計一個有效的算法計算axbycz并分析其計算效率。,第十五講 秘密分享與游戲,秘密分享方案是與密鑰建立相關的多方協(xié)議。秘密分享的原始動機是：為了保證密碼密鑰不丟失，希望產(chǎn)生密鑰備份，但是越多的密鑰備份，密鑰泄露的可能就越大；越少的密鑰備份，密鑰丟失的可能就越大。秘密分享方案就是用來提高密鑰可靠性而不增加泄露風險的方法。,現(xiàn)代密碼學的一個主要成就

2、在于高級安全協(xié)議的發(fā)展。這些協(xié)議可以讓用戶在網(wǎng)上解決現(xiàn)實世界中許多問題，進行各種游戲，也能執(zhí)行各種有趣而復雜的分布任務。電話投幣和撲克協(xié)議將在這一講中做簡要介紹。,本講提要,秘密分享的應用 秘密分割 門限方案 電話投幣協(xié)議 電話撲克協(xié)議,1 秘密分享的應用,1.1 秘密分割 假定你發(fā)明了一種烹飪食物方法。這一方法比目前已知的方法都好。對方法保密在市場競爭激烈的環(huán)境下十分重要。你可能僅會告訴最為信任的雇員具體方法，但雇員如

3、果為競爭對手收買該怎么辦？可能人人都可以按照這一方法烹飪食物。,1.1 秘密分割(續(xù)) 這就需要秘密分割。方法是將一個消息分割成碎片，每一個碎片沒有任何意義，但是合在一起就可以重現(xiàn)消息。有了秘密分割技術烹飪方法可以作為消息，而每個雇員只能拿到一個碎片，僅當他們聯(lián)合才能恢復出烹飪方法。如果任何雇員離職，他帶走的僅是自己的一個碎片，這一信息本身并無用處。,但是，這仍然存在問題：如果任意一個碎片丟失，則消息無法恢復。如果一個雇員有烹飪方

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

5、插入適合的槽中才允許他們起爆。,我們甚至可以把問題變得更為復雜。也許將軍和兩個上校被授權發(fā)射導彈，但如果將軍正在打高爾夫球，那么啟動發(fā)射需要五名上校。制造一個發(fā)射控制器，該發(fā)射控制器需要5把鑰匙。給將軍3把，給每位上校1把。將軍和任意兩名上校，或者五名上校一起都可以發(fā)射導彈，然而，將軍和一名上校，或四名上校就不能。,一個稱為門限方案(threshold scheme)的更復雜的秘密分享方案，可以在數(shù)學上做到這些甚至更多。起碼，可以取任意

6、消息(秘密配方，發(fā)射代碼，洗衣價目表)并把它分成n部分，每個部分叫它的影子或分享，它們中的任何m部分能夠用來重構(gòu)消息。,我們可以將烹飪方法分給Alice，Bob，Carol，和Dave，這樣把他們中的任意三個影子放在一起就能重構(gòu)消息。如果Carol正在渡假，那么Alice，Bob，和Dave可以考慮做這件事情；如果Bob被汽車撞了，那么Alice，Carol，和Dave可以考慮做這件事情。然而，如果Bob被汽車撞了并且Carol正在渡假

7、，Alice和Dave 就不可能重構(gòu)消息。,2 秘密分割,2.1 使用模加的二重控制,2.1 使用模加的二重控制(續(xù)),2.2使用模加的一致同意控制,2.2 使用模加的一致同意控制(續(xù)),3 門限方案,3.1 Shamir的門限方案,3.1 Shamir的門限方案(續(xù)),3.1 Shamir的門限方案(續(xù)),3.1 Shamir的門限方案(續(xù)),3.1 Shamir的門限方案(續(xù)),3.1 Shamir的門限方案(續(xù)),3.1 Sham

8、ir的門限方案(續(xù)),3.1 Shamir的門限方案(續(xù)),3.1 Shamir的門限方案(續(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ā)射導彈，我們要根除邪惡國家?！?Alice，Bob，和Carol

9、出示他們的分享，但Carol拿出的只是一個隨機數(shù)。她實際是一個和平主義者，不想發(fā)射導彈。由于Carol的錯誤輸入信息，他們恢復出來錯誤的秘密。導彈還停留在發(fā)射井里。更糟糕的是，沒人知道究竟是誰在其中搗鬼。,3.3 存在騙子的秘密分享(續(xù)),3.3 存在騙子的秘密分享(續(xù)),3.3 存在騙子的秘密分享(續(xù)),4 電話投幣協(xié)議,4.1 應用實例 一個朋友沒有意識到Alice和Bob不在一個地方，留給他們了一輛汽車。他們將怎樣決定汽車的

10、歸屬呢？Bob打個電話給Alice建議由他投幣來決定。Alice說選擇“背面”，但Bob說我投出的是“正面”。于是車歸了Bob。這里Alice完全有理由懷疑Bob的誠實。下一次，她可能選擇別的辦法決定這一問題。,4.2 一個解決方法 這里有一個思路，就是Alice隨機的選擇一個比特b1發(fā)給Bob， Bob也隨機的選擇一個比特b2發(fā)給Alice，投幣的結(jié)果就是b1 ? b2。問題就是誰先發(fā)送，如果Alice先，Bob將可以選擇b2來

11、控制投幣的結(jié)果。這并不公平。,4.3 公平投幣的要求 (1) Bob必須在聽到Alice猜測之前就已經(jīng)投幣。 (2) Bob不能夠在聽到Alice猜測之后重復投幣。 (3) Alice不能在其猜測之前得到投幣結(jié)果。,4.4 使用平方根的投幣,4.4 使用平方根的投幣(續(xù)),4.4 使用平方根的投幣(續(xù)),4.4 使用平方根的投幣(續(xù)),4.4 使用平方根的投幣(續(xù)),4.4 使用平方根的投幣(續(xù)),4.4 使用平方根

12、的投幣(續(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ā)還給

13、Alice，她再解密決定自己手中的5張牌。 Alice再隨機選擇5張牌發(fā)給Bob。 Bob解密它們得到自己的5張牌。,5.1思想(續(xù)) 在游戲的過程中，剩下的牌可以按照同樣的方法發(fā)出。在游戲結(jié)束后，Alice和Bob都公布自己的牌和密鑰對以確定沒有人在游戲中欺騙。,5.2 基于離散對數(shù)的撲克,5.2 基于離散對數(shù)的撲克(續(xù)),5.2 基于離散對數(shù)的撲克(續(xù)),5.2 基于離散對數(shù)的撲克(續(xù)),5.2 基于離散對數(shù)的撲克(續(xù)),5.