CCNS2015-專(zhuān)題3(匿名通信技術(shù))

1、專(zhuān)題三、匿名通信技術(shù)專(zhuān)題三、匿名通信技術(shù)周世杰周世杰電子科技大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院電子科技大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院School of Computer Science And Technology, UESTCThe Security Technology of Computer Network內(nèi)容內(nèi)容ABC基本概念基本概念經(jīng)典匿名協(xié)議經(jīng)典匿名協(xié)議概率匿名技術(shù)概率匿名技術(shù)D匿名協(xié)議的概率模型匿名協(xié)議的概率模型Every man should know that his conversations, his correspondence, and his personal life are p

2、rivate.-Lyndon B. Johnson, President of the United States, 1963-69n匿名性（匿名性（Anonymity）：在一定范圍內(nèi)無(wú)法）：在一定范圍內(nèi)無(wú)法確認(rèn)的狀態(tài)確認(rèn)的狀態(tài)n沒(méi)有絕對(duì)的匿名沒(méi)有絕對(duì)的匿名n不可關(guān)聯(lián)性（不可關(guān)聯(lián)性（Unlinkability）n操作與執(zhí)行該操作的主體的身份無(wú)關(guān)聯(lián)關(guān)系操作與執(zhí)行該操作的主體的身份無(wú)關(guān)聯(lián)關(guān)系n比如：郵件發(fā)送者和郵件本身在系統(tǒng)中無(wú)法比如：郵件發(fā)送者和郵件本身在系統(tǒng)中無(wú)法關(guān)聯(lián)起來(lái)關(guān)聯(lián)起來(lái)n不可觀(guān)測(cè)性（不可觀(guān)測(cè)性（Unobservability）n無(wú)法區(qū)分感興趣的東西和其他東西無(wú)法區(qū)分感興趣的東西和其他

3、東西“Anonymity is bullshit”基本概念基本概念n匿名（匿名（Anonymity）：）：n隱藏發(fā)送者、接收者的身份信息，或者無(wú)法關(guān)聯(lián)隱藏發(fā)送者、接收者的身份信息，或者無(wú)法關(guān)聯(lián)消息的發(fā)送者和接收者。消息的發(fā)送者和接收者。n匿名分類(lèi)：匿名分類(lèi)：n發(fā)送者匿名（發(fā)送者匿名（Sender Anonymity）n接收者匿名（接收者匿名（Receiver Anonymity）n發(fā)送者和接收者的無(wú)關(guān)聯(lián)性（發(fā)送者和接收者的無(wú)關(guān)聯(lián)性（Unlinkability of Sender and Receiver)基本概念基本概念n隱私隱私n網(wǎng)上交易、網(wǎng)上交易、WEB瀏覽等瀏覽等n數(shù)字現(xiàn)金（數(shù)字現(xiàn)金（D

4、igital cash）n電子貨幣電子貨幣n匿名投票（匿名投票（Anonymous electronic voting）n不可審計(jì)性出版（不可審計(jì)性出版（Censorship-resistant publishing）n不可追蹤電子郵件（不可追蹤電子郵件（Untraceable electronic mail）匿名技術(shù)大應(yīng)用匿名技術(shù)大應(yīng)用n1981年提出的年提出的Chaums MIX是最早的匿名是最早的匿名電子郵件通信方案，也是現(xiàn)代匿名通信系電子郵件通信方案，也是現(xiàn)代匿名通信系統(tǒng)的基礎(chǔ)之一統(tǒng)的基礎(chǔ)之一n該方案采用公鑰可信的郵件轉(zhuǎn)發(fā)網(wǎng)絡(luò)該方案采用公鑰可信的郵件轉(zhuǎn)發(fā)網(wǎng)絡(luò)David Chaum. “

5、Untraceable electronic mail, return addresses, and digital pseudonyms”. Communications of the ACM, February 1981Chaums MIXnChaums MIX有四種情況有四種情況n不帶返回地址的單個(gè)不帶返回地址的單個(gè)MIXn帶返回地址的單個(gè)帶返回地址的單個(gè)MIXn不帶返回地址的多個(gè)級(jí)連不帶返回地址的多個(gè)級(jí)連MIXn帶返回地址的多個(gè)級(jí)連帶返回地址的多個(gè)級(jí)連MIXChaums MIXDC-MIX無(wú)返回地址無(wú)返回地址K1Alice (A)Carol (C)Malice (M)Bob (B)11

6、01, bKKRR MB1322,xKKRRMX1543, yKKRRMY01,bKRMB43,yKRMY22,xKRMXMIXChaums MIXDC-MIX帶返回地址帶返回地址K1Alice (A)Bob (B)111011, , ,bKKKaRRMBR AK1011, ,bKKaRMBR AKMIX102, ,aKRR MA1021, aKKR MR AChaums MIX級(jí)連級(jí)連DC-MIX無(wú)返回地址無(wú)返回地址Alice (A)Bob (B)111101,., ,.,bnnnnKKKKRRRR MBKnMIXKn-1MIX111101,., ,.,bnnKKKRRRMBK2MIX122

7、101, bKKKRRRMBK1MIX1101, bKKRR MB01, ,bKR MBChaums MIX級(jí)連級(jí)連DC-MIX帶返回地址帶返回地址Alice (A)Bob (B)KnMIXKn-1MIXK2MIXK1MIX111101,., ,.,bnnnnKKKKRRRRMB2112,.,. ,nnKKKaRRRAK111101,., ,.,bnnKKKRRR MB2112,., ,. ,nnKKKaRRR AK122101, bKKKRRR MB2112,., ,. ,nnKKKaRRRAK1101, bKKRR MB2112,., ,. ,nnKKKaRRR AK01,bKRMB211

8、2,.,.,nnKKKaRRRAKChaums MIX級(jí)連級(jí)連DC-MIX帶返回地址帶返回地址Alice (A)Bob (B)KnMIXKn-1MIXK2MIXK1MIX111101,., ,.,bnnnnKKKKRRRRMB2112,., ,. ,nnKKKaRRRAK111101,., ,.,bnnKKKRRRMB2112,., ,. ,nnKKKaRRR AK122101, bKKKRRRMB2112,., ,. ,nnKKKaRRR AK1101, bKKRRMB2112,., ,. ,nnKKKaRRR AK01,bKRMB2112,.,.,nnKKKaRRRAK210212, ,.

9、, ,. anKnKKKR MRRR A12022, ,., ,.anKRnKKR MRRA123023, ,., ,.anKRRnKKR MRR A1102., ., annKRRnKR MRA12102., ,. ,annKRRRRR MAChaums MIXK11101 , , , bKKR R MB1322 , , , xKKR R MX1543 , , , yKKR R MY01 , ,bKR MB43 , ,yKR MY22 , ,xKR MXK201 , ,bKR MBK201 , ,bKR MB43 , ,yKR MY22 , ,xKR MX43 , ,yKR MYK201 ,

10、 ,bKR MB43 , ,yKR MY22 , ,xKR MX22 , ,xKR MX消息通過(guò)級(jí)連消息通過(guò)級(jí)連MIX轉(zhuǎn)發(fā)轉(zhuǎn)發(fā)某些某些MIX可能被攻擊者控制可能被攻擊者控制只需要一個(gè)只需要一個(gè)MIX沒(méi)有被控制，即可保證匿名沒(méi)有被控制，即可保證匿名需要消息填充來(lái)提供時(shí)間關(guān)聯(lián)攻擊需要消息填充來(lái)提供時(shí)間關(guān)聯(lián)攻擊Chaums MIXn優(yōu)點(diǎn)：優(yōu)點(diǎn)：n缺點(diǎn)：缺點(diǎn)：Chaums MIXn密碼員進(jìn)餐問(wèn)題：密碼員進(jìn)餐問(wèn)題： Dining Cryptographers n是一個(gè)具有強(qiáng)安全屬性的發(fā)送者匿名方案是一個(gè)具有強(qiáng)安全屬性的發(fā)送者匿名方案:即即便攻擊者具有無(wú)窮計(jì)算能力，也不能破壞其便攻擊者具有無(wú)窮計(jì)算能力，也

11、不能破壞其匿名性（匿名性（Guarantees information-theoretic anonymity for message senders）David Chaum. “The dining cryptographers problem: unconditional sender and recipient untraceability.” Journal of Cryptology, 1988密碼員進(jìn)餐問(wèn)題密碼員進(jìn)餐問(wèn)題密碼員進(jìn)餐問(wèn)題：密碼員進(jìn)餐問(wèn)題：A，B，C希望匿名支付帳單；可能一個(gè)密碼員正在付帳，也可能是由希望匿名支付帳單；可能一個(gè)密碼員正在付帳，也可能是由NSA(國(guó)家國(guó)家安

12、全局）付帳。安全局）付帳。A、B和和C尊重彼此的匿名支付的權(quán)利，但是需要知道是否是尊重彼此的匿名支付的權(quán)利，但是需要知道是否是NSA付帳。付帳。比較左右兩邊的比較左右兩邊的數(shù)，并報(bào)結(jié)果：數(shù)，并報(bào)結(jié)果：相同和不相同。相同和不相同。規(guī)則：如果自己沒(méi)有付帳，規(guī)則：如果自己沒(méi)有付帳，則報(bào)正確結(jié)果；如果自己正則報(bào)正確結(jié)果；如果自己正在支付，則報(bào)相反的結(jié)果在支付，則報(bào)相反的結(jié)果答案：如果報(bào)不相同的人數(shù)為奇數(shù)，則表明有一個(gè)密碼員在付帳；如果為偶數(shù)，答案：如果報(bào)不相同的人數(shù)為奇數(shù)，則表明有一個(gè)密碼員在付帳；如果為偶數(shù)，則是則是NSA在付帳。在付帳。方法：每個(gè)密碼員在他右邊拋一個(gè)硬幣（用正面和反面表示），結(jié)果只

13、能被自己方法：每個(gè)密碼員在他右邊拋一個(gè)硬幣（用正面和反面表示），結(jié)果只能被自己和自己右邊的密碼員看到。和自己右邊的密碼員看到。密碼員進(jìn)餐問(wèn)題密碼員進(jìn)餐問(wèn)題Bob (B)Carol (C)正正正相同相同Alice (A)相同答案：報(bào)不相同的為偶數(shù)，答案：報(bào)不相同的為偶數(shù)，NSA付帳。付帳。密碼員進(jìn)餐問(wèn)題密碼員進(jìn)餐問(wèn)題Alice (A)Bob (B)Carol (C)正正正不相同相同相同答案：報(bào)不相同的為奇數(shù)，一個(gè)密碼員付帳。答案：報(bào)不相同的為奇數(shù)，一個(gè)密碼員付帳。密碼員進(jìn)餐問(wèn)題密碼員進(jìn)餐問(wèn)題Alice (A)Bob (B)Carol (C)正正正不相同相同相同問(wèn)題：其他密碼員能否知道是問(wèn)題：其他

14、密碼員能否知道是Carol付帳？付帳？密碼員進(jìn)餐問(wèn)題密碼員進(jìn)餐問(wèn)題Alice (A)Bob (B)Carol (C)正正正不相同相同相同（1）密碼員支付，且）密碼員支付，且Alice看看到相同的結(jié)果到相同的結(jié)果要么要么Bob說(shuō)相同，說(shuō)相同，Carol說(shuō)不同；要么說(shuō)不同；要么Bob說(shuō)不同，說(shuō)不同，Carol說(shuō)說(shuō)相同。說(shuō)不同的是支付者。但是由于概率相同，相同。說(shuō)不同的是支付者。但是由于概率相同，Alice無(wú)法無(wú)法區(qū)分。區(qū)分。密碼員進(jìn)餐問(wèn)題密碼員進(jìn)餐問(wèn)題Alice (A)Bob (B)Carol (C)正反正不相同不相同不相同（2）密碼員支付，且）密碼員支付，且Alice看看到不同的結(jié)果到不同的結(jié)果

15、要么要么Bob和和Carol說(shuō)相同，要么說(shuō)相同，要么Bob和和Carol說(shuō)不同。但是由說(shuō)不同。但是由于概率相同，于概率相同，Alice無(wú)法區(qū)分。無(wú)法區(qū)分。密碼員進(jìn)餐問(wèn)題密碼員進(jìn)餐問(wèn)題Alice (A)Bob (B)Carol (C)正正正不相同相同相同問(wèn)題：其他密碼員能否知道是問(wèn)題：其他密碼員能否知道是Carol付帳？付帳？答案：比如答案：比如Alice，如果要想知道是，如果要想知道是Carol付帳，付帳，則需要知道則需要知道Carol和和Bob之間的拋幣情況。之間的拋幣情況。密碼員進(jìn)餐問(wèn)題密碼員進(jìn)餐問(wèn)題n問(wèn)題：如何通用化上述協(xié)議，并用來(lái)匿名傳送問(wèn)題：如何通用化上述協(xié)議，并用來(lái)匿名傳送消息？消

16、息？n方法：方法：n參與通信的用戶(hù)排成一個(gè)邏輯圓參與通信的用戶(hù)排成一個(gè)邏輯圓n在一定時(shí)間間隔內(nèi)，相鄰用戶(hù)之間拋幣（必須防在一定時(shí)間間隔內(nèi)，相鄰用戶(hù)之間拋幣（必須防止竊聽(tīng)）止竊聽(tīng)）n每次拋幣后用戶(hù)都說(shuō)相同或者不同每次拋幣后用戶(hù)都說(shuō)相同或者不同密碼員進(jìn)餐問(wèn)題密碼員進(jìn)餐問(wèn)題n比如比如Alice想匿名發(fā)送消息想匿名發(fā)送消息Mn過(guò)程：過(guò)程：n將將M二進(jìn)制化：二進(jìn)制化：1001n對(duì)于對(duì)于1，Alice采用顛倒說(shuō)法；對(duì)于采用顛倒說(shuō)法；對(duì)于0，Alice采用正常說(shuō)法：采用正常說(shuō)法：n比如比如Alice看到的是看到的是“不同不同”、“相同相同”、“相同相同”、“相同相同”，則則Alice說(shuō)說(shuō)“相同相同”、“相同

17、相同”、“相同相同”、“不同不同”。n如果如果Alice發(fā)現(xiàn)協(xié)議的結(jié)果與自己所期望的不同，則表示其發(fā)現(xiàn)協(xié)議的結(jié)果與自己所期望的不同，則表示其他人也在發(fā)送消息，因此她等待一段時(shí)間后再發(fā)送。他人也在發(fā)送消息，因此她等待一段時(shí)間后再發(fā)送。密碼員進(jìn)餐問(wèn)題密碼員進(jìn)餐問(wèn)題Alice (A)Bob (B)Carol (C)正正正相同相同不相同第一輪：第一輪：Alice發(fā)送發(fā)送1由于報(bào)不同的人數(shù)為奇數(shù)，因此由于報(bào)不同的人數(shù)為奇數(shù)，因此Bob和和Carol知知道有人說(shuō)道有人說(shuō)1Alice要發(fā)送要發(fā)送1001密碼員進(jìn)餐問(wèn)題密碼員進(jìn)餐問(wèn)題Alice (A)Bob (B)Carol (C)正正正相同相同相同第二輪：第

18、二輪：Alice發(fā)送發(fā)送0由于報(bào)不同的人數(shù)為偶數(shù)，因此由于報(bào)不同的人數(shù)為偶數(shù)，因此Bob和和Carol知知道有人說(shuō)道有人說(shuō)0Alice要發(fā)送要發(fā)送1001密碼員進(jìn)餐問(wèn)題密碼員進(jìn)餐問(wèn)題Alice (A)Bob (B)Carol (C)正正正相同相同相同第三輪：第三輪：Alice發(fā)送發(fā)送0由于報(bào)不同的人數(shù)為偶數(shù)，因此由于報(bào)不同的人數(shù)為偶數(shù)，因此Bob和和Carol知知道有人說(shuō)道有人說(shuō)0Alice要發(fā)送要發(fā)送1001密碼員進(jìn)餐問(wèn)題密碼員進(jìn)餐問(wèn)題Alice (A)Bob (B)Carol (C)正正正相同相同不相同第四輪：第四輪：Alice發(fā)送發(fā)送1由于報(bào)不同的人數(shù)為奇數(shù)，因此由于報(bào)不同的人數(shù)為奇數(shù)，

19、因此Bob和和Carol知知道有人說(shuō)道有人說(shuō)1Alice要發(fā)送要發(fā)送1001密碼員進(jìn)餐問(wèn)題密碼員進(jìn)餐問(wèn)題Alice (A)Bob (B)Carol (C)正正正不相同相同不相同第四輪：第四輪：Alice發(fā)送發(fā)送1、Carol發(fā)送發(fā)送1由于報(bào)不同的人數(shù)為偶數(shù)，因此由于報(bào)不同的人數(shù)為偶數(shù)，因此Alice、Bob和和Carol知道有人說(shuō)知道有人說(shuō)0這與這與Alice要發(fā)送的消息不一致，因此要發(fā)送的消息不一致，因此Alice等待等待一段時(shí)間后重發(fā)一段時(shí)間后重發(fā)Alice要發(fā)送要發(fā)送1001密碼員進(jìn)餐問(wèn)題密碼員進(jìn)餐問(wèn)題Alice (A)Bob (B)Carol (C)正正正相同Kb相同Kb不相同KbAl

20、ice要向要向Bob發(fā)送發(fā)送1001問(wèn)題問(wèn)題1：如何拋幣？：如何拋幣？方法：公正拋幣協(xié)議方法：公正拋幣協(xié)議問(wèn)題問(wèn)題2：如何將消息發(fā)送給指：如何將消息發(fā)送給指定的人（比如定的人（比如Bob）？）？方法：用方法：用Bob的公鑰加密結(jié)果的公鑰加密結(jié)果密碼員進(jìn)餐問(wèn)題密碼員進(jìn)餐問(wèn)題Alice (A)Bob (B)Carol (C)正正正不相同相同不相同Bob說(shuō)謊，導(dǎo)致結(jié)果為說(shuō)謊，導(dǎo)致結(jié)果為NSA付帳，實(shí)際上是付帳，實(shí)際上是Carol在付帳。在付帳。密碼員進(jìn)餐問(wèn)題是否存在問(wèn)題？密碼員進(jìn)餐問(wèn)題是否存在問(wèn)題？問(wèn)題：如何檢測(cè)這種惡意破壞？問(wèn)題：如何檢測(cè)這種惡意破壞？密碼員進(jìn)餐問(wèn)題密碼員進(jìn)餐問(wèn)題n更一般的推廣更一

21、般的推廣n對(duì)每一位將要發(fā)送的消息，每個(gè)用戶(hù)產(chǎn)生一個(gè)隨機(jī)位，并發(fā)送給一個(gè)對(duì)每一位將要發(fā)送的消息，每個(gè)用戶(hù)產(chǎn)生一個(gè)隨機(jī)位，并發(fā)送給一個(gè)鄰居節(jié)點(diǎn)鄰居節(jié)點(diǎn)n任一節(jié)點(diǎn)任一節(jié)點(diǎn)i知道兩位信息：自己選擇的隨機(jī)位知道兩位信息：自己選擇的隨機(jī)位bi和一個(gè)鄰居節(jié)點(diǎn)和一個(gè)鄰居節(jié)點(diǎn)j的隨機(jī)位的隨機(jī)位bjn每一個(gè)節(jié)點(diǎn)（除發(fā)送節(jié)點(diǎn)外）通告自己所知道的的兩個(gè)位的異或值結(jié)每一個(gè)節(jié)點(diǎn)（除發(fā)送節(jié)點(diǎn)外）通告自己所知道的的兩個(gè)位的異或值結(jié)果：果：Cibi XOR bjn發(fā)送者發(fā)送者x通告以下結(jié)果：通告以下結(jié)果：Cx=bx XOR bk XOR Mxn所有通告結(jié)果的異或值就是消息位所有通告結(jié)果的異或值就是消息位原因：每一位出現(xiàn)兩次，在

22、異或操作中被抵消原因：每一位出現(xiàn)兩次，在異或操作中被抵消12.xnMCCC密碼員進(jìn)餐問(wèn)題密碼員進(jìn)餐問(wèn)題n上述協(xié)議的優(yōu)點(diǎn)：上述協(xié)議的優(yōu)點(diǎn)：n匿名性很健壯：即便部分主體合謀，也不能破壞匿名匿名性很健壯：即便部分主體合謀，也不能破壞匿名性性n每一個(gè)協(xié)議主體均很難通過(guò)分析協(xié)議過(guò)程中的知識(shí)來(lái)每一個(gè)協(xié)議主體均很難通過(guò)分析協(xié)議過(guò)程中的知識(shí)來(lái)破壞匿名性破壞匿名性n上述協(xié)議的缺點(diǎn)：上述協(xié)議的缺點(diǎn)：n成員間需要一個(gè)需要一個(gè)成對(duì)的信道（否則隨機(jī)位信成員間需要一個(gè)需要一個(gè)成對(duì)的信道（否則隨機(jī)位信息無(wú)法被共享）息無(wú)法被共享）n需要大量的通信和大量的隨機(jī)位需要大量的通信和大量的隨機(jī)位n需要可靠廣播信道需要可靠廣播信道n無(wú)

23、法抵抗惡意破壞者無(wú)法抵抗惡意破壞者密碼員進(jìn)餐問(wèn)題密碼員進(jìn)餐問(wèn)題n問(wèn)題的提出：?jiǎn)栴}的提出：n協(xié)議參與者之間無(wú)法得到可靠的廣播信道協(xié)議參與者之間無(wú)法得到可靠的廣播信道Disco舞廳內(nèi)的嘈雜使得密碼員之間無(wú)法聽(tīng)清楚舞廳內(nèi)的嘈雜使得密碼員之間無(wú)法聽(tīng)清楚別人的宣告內(nèi)容。別人的宣告內(nèi)容。DiscoDisco舞廳密碼員進(jìn)餐問(wèn)題舞廳密碼員進(jìn)餐問(wèn)題n問(wèn)題的提出：?jiǎn)栴}的提出：n協(xié)議參與者之間無(wú)法得到可靠的廣播信道協(xié)議參與者之間無(wú)法得到可靠的廣播信道Disco舞廳內(nèi)的嘈雜使得密碼員之間無(wú)法聽(tīng)清楚舞廳內(nèi)的嘈雜使得密碼員之間無(wú)法聽(tīng)清楚別人的宣告內(nèi)容。別人的宣告內(nèi)容。DiscoDisco舞廳密碼員進(jìn)餐問(wèn)題舞廳密碼員進(jìn)餐問(wèn)

24、題n基本思路：基本思路：n（1）構(gòu)造一個(gè)可靠廣播信道：）構(gòu)造一個(gè)可靠廣播信道：Byzantine General Problemn（2）去除可靠廣播信道的要求）去除可靠廣播信道的要求n（3）信道預(yù)留技術(shù)）信道預(yù)留技術(shù)n兩個(gè)階段：第一階段預(yù)留信道，第二階段發(fā)送消息兩個(gè)階段：第一階段預(yù)留信道，第二階段發(fā)送消息DiscoDisco舞廳密碼員進(jìn)餐問(wèn)題舞廳密碼員進(jìn)餐問(wèn)題n通過(guò)隨機(jī)路由來(lái)隱藏消息源通過(guò)隨機(jī)路由來(lái)隱藏消息源nCrowds, Freenet, Onion routingn路由節(jié)點(diǎn)無(wú)法區(qū)分所收到的消息是來(lái)自真實(shí)路由節(jié)點(diǎn)無(wú)法區(qū)分所收到的消息是來(lái)自真實(shí)的發(fā)送者或者來(lái)自其他路由節(jié)點(diǎn)的發(fā)送者或者來(lái)自其他

25、路由節(jié)點(diǎn)發(fā)送者接收者匿名與隨機(jī)路由匿名與隨機(jī)路由WEB服務(wù)器p1-pp1-p（1）路由節(jié)點(diǎn)形成一個(gè)隨機(jī)路由路徑）路由節(jié)點(diǎn)形成一個(gè)隨機(jī)路由路徑（2）誠(chéng)實(shí)的路由節(jié)點(diǎn)采用拋幣的方式?jīng)Q定將）誠(chéng)實(shí)的路由節(jié)點(diǎn)采用拋幣的方式?jīng)Q定將請(qǐng)求發(fā)送到請(qǐng)求發(fā)送到web服務(wù)器或繼續(xù)轉(zhuǎn)發(fā)服務(wù)器或繼續(xù)轉(zhuǎn)發(fā)RoutersCrowds SystemCrowds SystemnCrowds的匿名性：的匿名性：n觀(guān)察者無(wú)法確定提交觀(guān)察者無(wú)法確定提交web訪(fǎng)問(wèn)請(qǐng)求的用戶(hù)是訪(fǎng)問(wèn)請(qǐng)求的用戶(hù)是真正的發(fā)送者還是一個(gè)轉(zhuǎn)發(fā)者真正的發(fā)送者還是一個(gè)轉(zhuǎn)發(fā)者n觀(guān)察者所看到的觀(guān)察者所看到的web請(qǐng)求的提交者是真正發(fā)請(qǐng)求的提交者是真正發(fā)送者的概率不會(huì)超過(guò)送者

26、的概率不會(huì)超過(guò)50%概率清白（概率清白（Probable innocence ）：真正發(fā)送者被）：真正發(fā)送者被視作發(fā)送者和非發(fā)送者的概率相同視作發(fā)送者和非發(fā)送者的概率相同Crowds SystemCrowds SystemnCrowds協(xié)議協(xié)議STEP 1：發(fā)送者隨機(jī)算則一個(gè)：發(fā)送者隨機(jī)算則一個(gè)Crowds中的節(jié)點(diǎn)，中的節(jié)點(diǎn)，采用其加密后發(fā)送給該節(jié)點(diǎn)采用其加密后發(fā)送給該節(jié)點(diǎn)STEP 2：誠(chéng)實(shí)節(jié)點(diǎn)收到消息后，利用公正拋幣協(xié)議：誠(chéng)實(shí)節(jié)點(diǎn)收到消息后，利用公正拋幣協(xié)議以概率以概率p繼續(xù)轉(zhuǎn)發(fā)，則轉(zhuǎn)繼續(xù)轉(zhuǎn)發(fā)，則轉(zhuǎn)STEP1；以概率；以概率1p將消將消息直接提交給信宿。息直接提交給信宿。Crowds的結(jié)論：的結(jié)論：Crowds中的節(jié)點(diǎn)數(shù)位中的節(jié)點(diǎn)數(shù)位n，其中有，其中有c個(gè)壞節(jié)點(diǎn)了；誠(chéng)實(shí)個(gè)壞節(jié)點(diǎn)了；誠(chéng)實(shí)節(jié)點(diǎn)轉(zhuǎn)發(fā)消息的概率為節(jié)點(diǎn)轉(zhuǎn)發(fā)消息的概率為Pf，則如果滿(mǎn)足以下條件，則如果滿(mǎn)足以下條件，Crowds滿(mǎn)足概率清白：滿(mǎn)足概率清白：12(1)ffPncpCrowds Sy