y, 和z。在各參數(shù)為指數(shù)規(guī)模時(shí),請(qǐng)?jiān)O(shè)計(jì)一個(gè)有效的算法計(jì)

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

2、在于高級(jí)安全協(xié)議的發(fā)展。這些協(xié)議可以讓用戶在網(wǎng)上解決現(xiàn)實(shí)世界中許多問題，進(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ì)告訴最為信任的雇員具體方法，但雇員如

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

4、法的一個(gè)碎片而他去為競(jìng)爭(zhēng)對(duì)手工作并將其碎片帶走，那么其他雇員就沒有那么幸運(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è)容易解決的問題。做一個(gè)機(jī)械發(fā)射控制器，給五個(gè)軍官每個(gè)人一把鑰匙，并且只有在至少三個(gè)軍官的鑰匙

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

6、消息(秘密配方，發(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正在渡假

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

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

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

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

12、的投幣(續(xù)),5電話撲克協(xié)議,一個(gè)類似于公平投幣的協(xié)議就是電話撲克協(xié)議，它允許Alice和Bob在電話兩端玩撲克。不同于處理“正面”和“反面”兩條消息，Bob需要處理分別代表每一張牌的52個(gè)數(shù)字c1， c2，...， c52 。如何保證在游戲中沒有欺詐？,5.1 思想 Bob用自己的加密密鑰加密牌c1，c2，...， c52發(fā)送給Alice。Alice隨機(jī)選擇5張牌，用自己的加密密鑰加密，發(fā)還給Bob。 Bob解密這些牌后發(fā)還給

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