第二十三講-零知識(shí)證明技術(shù)

1、第二十三講 零知識(shí)證明技術(shù) Peggy：“我知道聯(lián)邦儲(chǔ)備系統(tǒng)計(jì)算機(jī)的口令，McDonald的秘密調(diào)味汁的成分，以及Knuth第5卷的內(nèi)容?！?Victor：“不，你不知道?！?Peggy：“我知道?！?Victor：“你不知道！” Peggy：“我確實(shí)知道！” Victor：“請(qǐng)你證明這一點(diǎn)！” Peggy：“好吧，我告訴你！”她悄悄地說(shuō)出了口令。 Victor： “太有趣了！現(xiàn)在我也知道了。我要告訴華盛頓郵報(bào)?！?許多年前，有報(bào)道稱小偷在一個(gè)超市中放置假的ATM機(jī)。當(dāng)人們將銀行卡插入機(jī)器并輸入鑒別身份的秘密時(shí)，機(jī)器將這些信息記錄下來(lái)并反饋消息說(shuō)機(jī)器不能接受這種類型的銀行卡。小偷接下來(lái)就可以制

2、造假的銀行卡，并使用得到的身份鑒別秘密信息到真的ATM機(jī)上提取現(xiàn)金。 如何避免這一情況發(fā)生？在很多情況下需要出示鑒別身份的秘密或口令來(lái)完成交易。任何人在得到這個(gè)秘密再附加一些(幾乎公開(kāi)的)身份信息之后，就可以冒充這個(gè)人。我們需要解決的問(wèn)題就是使用秘密但在使用的過(guò)程中不留給攻擊者任何可以重復(fù)使用的信息。這就產(chǎn)生了零知識(shí)證明技術(shù)。本講提要q 零知識(shí)證明概念總攬q Fiat-Shamir鑒別協(xié)議q Feige-Fiat-Shamir鑒別協(xié)議q GQ鑒別協(xié)議q Schnorr鑒別協(xié)議1 零知識(shí)證明概念總攬1.1 思想 1.1 思想(續(xù)) Peggy知道這個(gè)洞穴的秘密。她想對(duì)Victor證明這一點(diǎn)，但她

3、不想泄露咒語(yǔ)。下面是她如何使Victor相信的過(guò)程： (1) Victor站在A點(diǎn)。 (2) Peggy一直走進(jìn)洞穴，到達(dá)點(diǎn)C或點(diǎn)D。 (3) 在Peggy消失在洞穴中之后，Victor 走到點(diǎn)B。 1.1 思想(續(xù)) (4) Victor向Peggy喊，要她： (4.1) 從左通道出來(lái)，或者； (4.2) 從右通道出來(lái). (5) Peggy答應(yīng)了，如果有必要她就用咒語(yǔ)打開(kāi)密門(mén)。 (6) Peggy和Victor重復(fù)第(1)到第(5)步n次。 1.1思想(續(xù)) 評(píng)述評(píng)述. 協(xié)議使用的技術(shù)叫做分割選擇技術(shù)(cut and choose)，因?yàn)樗愃迫缦聦⑷魏螙|西等分的經(jīng)典協(xié)議： (1) Pegg

4、y將東西切成兩半。 (2) Victor給自己選擇一半。 (3) Peggy拿走剩下的一半。 Peggy最關(guān)心的是第(1)步中的等分，因?yàn)閂ictor可以在第(2)步選擇他想要的那一半。 1.2 交互證明系統(tǒng)和零知識(shí)證明協(xié)議 零知識(shí)證明協(xié)議是交互證明系統(tǒng)的一個(gè)實(shí)例，這里一個(gè)證明者和一個(gè)驗(yàn)證者交互多輪。證明者的目標(biāo)是讓認(rèn)證者相信聲稱的正確性，例如，聲稱掌握一個(gè)秘密。驗(yàn)證者要么接受證明要么拒絕證明。這與傳統(tǒng)的數(shù)學(xué)概念的證明有所不同，交互游戲的證明是隨機(jī)而不是絕對(duì)的。由于這個(gè)原因，一個(gè)交互證明常常被稱為協(xié)議證明。 1.2 交互證明系統(tǒng)和零知識(shí)證明協(xié)議(續(xù)) 用于鑒別的交互證明可以被形式化為知識(shí)證明。

5、 證明者A掌握某個(gè)秘密s，并通過(guò)正確的回答驗(yàn)證者B所提出的問(wèn)題(涉及的是公開(kāi)已知的輸入和協(xié)商一致的函數(shù))使其相信確實(shí)掌握秘密s，當(dāng)然，回答這些問(wèn)題需要秘密s。注意證明掌握秘密s不同于證明s存在。一個(gè)交互證明是知識(shí)證明如果證明滿足完備性和正確性屬性。 1.2 交互證明系統(tǒng)和零知識(shí)證明協(xié)議(續(xù)) 定義定義1 (完備屬性) 一個(gè)交互證明(協(xié)議)是完備的，如果給定一個(gè)誠(chéng)實(shí)的證明者和認(rèn)證者，協(xié)議就能以壓倒的概率獲得成功(也就是，驗(yàn)證者接受證明者的宣稱)。 評(píng)論評(píng)論. 完備性可以看作是協(xié)議在誠(chéng)實(shí)的參與者執(zhí)行的情況下的一般要求。對(duì)壓倒的概率的定義依賴具體應(yīng)用，但通常隱含失敗的概率無(wú)實(shí)際意義。 1.2 交互證

6、明系統(tǒng)和零知識(shí)證明協(xié)議(續(xù)) 定義定義2 (正確屬性) 一個(gè)交互證明(協(xié)議)是正確的，如果存在一個(gè)平均多項(xiàng)式時(shí)間算法M滿足如下性質(zhì)：如果一個(gè)不誠(chéng)實(shí)的證明者(A)可以以不可忽略的概率成功的與B執(zhí)行協(xié)議，M則可以用來(lái)得到這個(gè)證明者的知識(shí)(本質(zhì)上等于A的秘密)，這將使得后續(xù)的協(xié)議執(zhí)行以壓倒概率獲得成功。 1.2 交互證明系統(tǒng)和零知識(shí)證明協(xié)議(續(xù)) 由于任何有能力冒充A的一方都等同于知道A的秘密知識(shí)(M可以在多項(xiàng)式時(shí)間內(nèi)來(lái)計(jì)算它)，正確屬性保證了協(xié)議確實(shí)提供了對(duì)知識(shí)的證明知識(shí)等價(jià)于詢問(wèn)的正確應(yīng)答。正確屬性因此阻止了不誠(chéng)實(shí)的證明者使誠(chéng)實(shí)的驗(yàn)證者相信知識(shí)的可能。 1.2 交互證明系統(tǒng)和零知識(shí)證明協(xié)議(續(xù))

7、 定義定義3 (零知識(shí)屬性) 一個(gè)知識(shí)證明的協(xié)議有零知識(shí)屬性，如果協(xié)議可模擬如下功能：存在一個(gè)平均多項(xiàng)式算法(模擬器)，它可以不和真實(shí)的證明者交互就可以產(chǎn)生一些證明必要的交互消息。這些消息副本與同真實(shí)的證明者交互產(chǎn)生的結(jié)果不可區(qū)分。 1.2 交互證明系統(tǒng)和零知識(shí)證明協(xié)議(續(xù)) 評(píng)述評(píng)述. (1) 零知識(shí)屬性表明一個(gè)證明者執(zhí)行協(xié)議(即使與惡意驗(yàn)證者交互)不會(huì)透露任何信息 (即除了特定的聲稱正確以外的關(guān)于他的秘密知識(shí))，這無(wú)異于在多項(xiàng)式時(shí)間從公開(kāi)信息中計(jì)算。因此，參與者不會(huì)增加后續(xù)冒充成功的機(jī)會(huì)。 1.2 交互證明系統(tǒng)和零知識(shí)證明協(xié)議(續(xù)) (2) 考慮一個(gè)觀查者C觀測(cè)證明者A與驗(yàn)證者B (B C

8、)一個(gè)零知識(shí)證明協(xié)議交互過(guò)程，且B確定了A掌握某個(gè)知識(shí)。向B證明的過(guò)程并不能給C任何擔(dān)保。(事實(shí)上，A和B可能事先串通應(yīng)答內(nèi)容來(lái)欺騙 C。) 相似情況，記錄零知識(shí)證明協(xié)議的交互也不能進(jìn)行回放。這就是零知識(shí)屬性的基本思想，即證明過(guò)程可以由驗(yàn)證者單獨(dú)模擬完成。 1.2 交互證明系統(tǒng)和零知識(shí)證明協(xié)議(續(xù)) (3) 零知識(shí)屬性(定義定義3)不能保證協(xié)議是安全的 (也就是，獲得秘密知識(shí)的可能性可以忽略)。同樣，正確屬性(定義定義2)也不能保證協(xié)議安全。這兩個(gè)屬性只有在攻擊者面臨計(jì)算困難問(wèn)題的時(shí)候才有意義。1.3 零知識(shí)證明協(xié)議的一般結(jié)構(gòu)案。就限定了將來(lái)的可能答問(wèn)題的集合，因此，也回答在本次協(xié)議執(zhí)行中所能

9、隨機(jī)性，并限定了一個(gè)每一次協(xié)議執(zhí)行的的公開(kāi)證據(jù)。這提供了承諾，并從中計(jì)算相關(guān)合上的元素做一個(gè)秘密擇一個(gè)在事先定義的集結(jié)構(gòu)：證明者隨機(jī)的選交互零知識(shí)協(xié)議的一般以上描述了一大類三次：ABABABA回答提問(wèn) 證據(jù)1.3 零知識(shí)證明協(xié)議的一般結(jié)構(gòu)(續(xù))的概率。功制循環(huán)次數(shù)降低欺騙成果需要，就可以通過(guò)控一個(gè)循環(huán)執(zhí)行過(guò)程，如檢查是否正確。協(xié)議是做出回答，而，給接著選擇一個(gè)問(wèn)題提交的秘密知識(shí)。幫助分析回答一個(gè)問(wèn)題，并不能開(kāi)證據(jù)提出的問(wèn)題，而有能力回答所有根據(jù)公才道秘密知識(shí)的合法根據(jù)協(xié)議設(shè)計(jì)，只有知BAABAA 1.4 零知識(shí)協(xié)議VS. 非對(duì)稱協(xié)議 (1) 使用不退化：協(xié)議具有零知識(shí)屬性因此不會(huì)因?yàn)橹貜?fù)使用而

10、降低安全性并可阻止選擇消息攻擊。這可能是零知識(shí)技術(shù)在實(shí)踐中最吸引人之處。 (2) 無(wú)需加密：許多零知識(shí)技術(shù)都不需要使用加密算法。 (3) 效率：雖然一些零知識(shí)基技術(shù)非常有效，但是具有零知識(shí)屬性的協(xié)議通常比沒(méi)有零知識(shí)屬性的非對(duì)稱協(xié)議需要更多通信和計(jì)算開(kāi)銷(xiāo)。更為有效的實(shí)用零知識(shí)基方案通常源于交互證明的特性，而不是它的零知識(shí)特性。 1.4 零知識(shí)協(xié)議VS. 非對(duì)稱協(xié)議(續(xù)) (4) 沒(méi)有證明的假設(shè)：許多零知識(shí)協(xié)議 (“證明知識(shí)”)本身依賴于和非對(duì)稱技術(shù)一樣的未經(jīng)證明的假設(shè)(例如，分解的困難)。 (5) 零知識(shí)基與零知識(shí)：雖然有著嚴(yán)謹(jǐn)?shù)睦碚撝С?，許多基于零知識(shí)概念的技術(shù)在實(shí)踐中缺少形式化的零知識(shí)和/或

11、正確屬性的支撐，導(dǎo)致這一切的是出于效率或其它原因的參數(shù)選擇問(wèn)題。事實(shí)上，許多這類概念是漸進(jìn)的，并不能直接應(yīng)用到實(shí)用協(xié)議中來(lái)。2 Fiat-Shamir鑒別協(xié)議。掌握秘密接受證明認(rèn)為次都成功完成，。如果連續(xù)且獨(dú)立次如下的步驟循環(huán)執(zhí)行協(xié)議執(zhí)行作為公開(kāi)密鑰。登記，并向計(jì)算，互素的秘密選擇一個(gè)與每一個(gè)聲稱者保密。和素?cái)?shù)，但將型的模選擇并公布一個(gè)信任中心一次性建立過(guò)程。其掌握知識(shí)證明次向驗(yàn)證者輪協(xié)議通過(guò)執(zhí)行一個(gè)：證明者鑒別協(xié)議sABttvTn svnssnAqpqpnTsBtA)( . (2) ) mod( 1 1 (1.2) RSA (1.1). (1) 3Shamir-Fiat2摘摘要要 協(xié)協(xié)議議1

12、 12 Fiat-Shamir 鑒別協(xié)議(續(xù))0 0 ) (mod) (mod ( ) (mod 0 (2.4)1) ( ) (mod 0) ( )( (2.3) 1 0 )( (2.2) ) (mod )(1 1 )( (2.1)(Shamir-Fiat22222的情況。是為了排除。注意驗(yàn)證，由于或者，得根據(jù)就可以接受證明。了拒絕證明，否則，驗(yàn)證，如果。如果者或如果，回答計(jì)算并發(fā)送給。給發(fā)送并，或者比特問(wèn)題隨機(jī)的選擇一個(gè)。給證據(jù)發(fā)送，并且，承諾選擇一個(gè)隨機(jī)數(shù)續(xù)鑒別協(xié)議rynsvnvxy xyenvxyByensryeryyBAAeeeBBnrxnrrAe 協(xié)協(xié)議議1 1BA) (mod 2n

13、rx ) (mod 0 2證明。拒絕接受證明；否則則，并如果BBnvxyye1 0，e)(mod ns ry e2 Fiat-Shamir 鑒別協(xié)議(續(xù))2 Fiat-Shamir鑒別協(xié)議(續(xù))的身份。受回答正確的情況下才接都輪個(gè)問(wèn)題只有在全部次，協(xié)議需要執(zhí)行或例如，的小數(shù)值可能性到一個(gè)可以接受為了減少欺騙的可能可以不被發(fā)現(xiàn)。問(wèn)題，因此有的一個(gè)他人只能至多回答其中回答兩個(gè)問(wèn)題，但是其的證明者可以個(gè)知道是用來(lái)阻止欺騙的。一者而言對(duì)誠(chéng)實(shí)證明，另一個(gè)容易的問(wèn)題她掌握的秘密知識(shí)其中一個(gè)需要有能力回答兩個(gè)問(wèn)題，要求或測(cè)試證明。提問(wèn)做如下解釋和非正式的可以對(duì)AttBtttssAet)( )40 = 20

14、= (21/2)()( 協(xié)議(1)1 評(píng)評(píng)述述. .2 Fiat-Shamir鑒別協(xié)議(續(xù))不能預(yù)測(cè)實(shí)時(shí)問(wèn)題。并，因?yàn)椴⒉荒苊俺涔芸梢阅M證明過(guò)程，就是零知識(shí)屬性。盡產(chǎn)生的對(duì)不可區(qū)分，這的概率分布實(shí)際上與，信息對(duì)的方法，但對(duì)建立。雖然這并不是或定義，選擇自己很好的模擬：隨機(jī)好可以為驗(yàn)證者恰，產(chǎn)生的信息對(duì)。由并不知道隨機(jī)數(shù)的信息，因?yàn)橐矝](méi)有提供任何關(guān)于，然而答案的秘密是獨(dú)立于答案BABAyxAnv yyx yByxArBsns rysAry ) () mod(/ ) () mod( (2)續(xù)(22 評(píng)評(píng)述述. .3 Feige-Fiat-Shamir鑒別協(xié)議。，這里計(jì)算的分解。否則將導(dǎo)致可以得到

15、保證，但是這一點(diǎn)幾乎肯定，要求原因，由于技術(shù)，個(gè)隨機(jī)整數(shù)選擇做如下步驟每個(gè)實(shí)體每個(gè)實(shí)體秘密參數(shù)選擇為定義的安全參數(shù)。和分解困難。整數(shù)，并且滿足向所有用戶公開(kāi)公共模信任中心系統(tǒng)參數(shù)選擇自己的身份。證明輪協(xié)議向驗(yàn)證者次執(zhí)行一個(gè)通過(guò)摘要：證明者鑒別協(xié)議kinsvnnsnsssskAtknqpnTBtAiiiik 1 ) (mod (2.2)1 )( ( 1 1 . . . (2.1). . (2) . (1)3Shamir-Fiat-Feige 221協(xié)協(xié)議議2 23 Feige-Fiat-Shamir鑒別協(xié)議(續(xù))0 (0 ) (mod (3.4)( ) (mod )( (3.3) . . . (

16、)( (3.2) )( )mod( 11 (3.1) . . . ( . (3) . . . () . . . ( ) ( (2.3)(Shamir-Fiat-Feige 121212212121的情況。者選擇后一條是為了防止攻擊。和，并驗(yàn)證計(jì)算。的乘積問(wèn)中的和定義在提：答案計(jì)算并發(fā)送給。，比特向量一個(gè)提問(wèn)發(fā)送給。給證據(jù)發(fā)送，并并計(jì)算，選擇一個(gè)隨機(jī)整數(shù)。；，的真實(shí)公開(kāi)密鑰知道輪都能成功。假定的身份，如果全部將接受次。下面的步驟執(zhí)行協(xié)議執(zhí)行程。這是一次性的建立過(guò)，密密鑰知道自己的秘的公開(kāi)密鑰，當(dāng)然只有登記為；，將就這樣認(rèn)證自己的身份，照片例如，通過(guò)非密碼手段向續(xù)鑒別協(xié)議rzxznvyzBsrns

17、ryBAeeekABBx n rxnrrAnvvvABtABtsssAAnvvvTTAkjejjkjejkkkkjj協(xié)協(xié)議議2 23 Feige-Fiat-Shamir鑒別協(xié)議(續(xù))AB) (mod 2nrx 拒絕證明。否則，接受證明；則，并且如果BBxznvyzjjeej ) 0(mod 12 1 0 ) . . . (1，ikeee) (mod 1nsryjej3 Feige-Fiat-Shamir鑒別協(xié)議(續(xù))。和因?yàn)榈纳矸?，這是并接受計(jì)算。數(shù)值計(jì)算并發(fā)送給。，比特向量一個(gè)發(fā)送給。，并發(fā)送它給，計(jì)算選擇。，密鑰是，秘密；，公開(kāi)密鑰是。，和，計(jì)算。，個(gè)隨機(jī)整數(shù)選擇做如下步驟實(shí)體被定義為安全

18、參數(shù)。和。整數(shù)，并公布，選擇素?cái)?shù)信任中心明選擇小的參數(shù)以利于說(shuō)0528015 ) (mod (3.4)403104 ) mod ( (3.3)1) 0 (0 3 (3.2)528015 1279 (3.1) (3)4646) 43215 (157553913) 429490 338402 (112068 (2.3)429490 338402 112068 (2.2)4646 43215 1573 ) (2.1. (2)1 3 553913 811 683 (1)(323321321zxzAnvyzBnsryBAABBxrAvvvsssAtkqpnqpT 例例子子1 13 Feige-Fiat-

19、Shamir鑒別協(xié)議(續(xù))。和數(shù)知識(shí)證明，這里假定參況下是對(duì)知識(shí)的一個(gè)零議在有可信服務(wù)器的情零知識(shí)和正確屬性。協(xié)的分解問(wèn)題。算。這個(gè)問(wèn)題等價(jià)于計(jì)的模平方根的困難問(wèn)題合數(shù)賴于計(jì)算未知分解的大安全假設(shè)需求。安全依的概率保證冒充成功。擊也只有是困難的，最好的攻分解安全的，也就是，如果息攻擊可以證明是抵抗選擇消偽造概率。)(log ) log O(log (3) (2)2協(xié)議 (1)ntnknnntk2 評(píng)評(píng)述述. .3 Feige-Fiat-Shamir鑒別協(xié)議(續(xù))。意味著減少作為常數(shù)，增加信開(kāi)銷(xiāo)。乘積行，可以減少計(jì)算和通協(xié)議執(zhí)全參數(shù)使得僅需要一輪安全平衡。通過(guò)平衡安。，的安全：；，的安全：對(duì)于參

20、數(shù)選擇，是適合的選擇。具體的和通信的平衡，算，存儲(chǔ)，試已經(jīng)足夠。考慮到計(jì)用戶防御冒充的鑒別測(cè)對(duì)于個(gè)人萬(wàn)分之一，這在現(xiàn)實(shí)中冒充成功的概率只有百就可以保證滿足和數(shù)參數(shù)選擇。選擇安全參tktktktkktktk (5)5 6 2 4 5 2181 20 (4)續(xù)(3020評(píng)評(píng)述述. .3 Feige-Fiat-Shamir鑒別協(xié)議(續(xù))，但并不增加輪數(shù)。偽造可以降低錯(cuò)誤率行循環(huán)相對(duì)于串執(zhí)行在交互證明中這種并行這樣做仍然是安全的。條消息并行執(zhí)行，輪的讓全部協(xié)議的平行版本，可以少。那么通信復(fù)雜度可以減的驗(yàn)證也做相應(yīng)修改，而不是值一個(gè)比特例如，發(fā)送給如果的模聯(lián)系起來(lái)。需要將每個(gè)用戶和他們?nèi)匀蛔约旱哪＃龈?/p>

21、變，每個(gè)用戶選擇步的第修改考慮。)()(3 (6.3)(Hash)128( (6.2) (1) (6.1) (6)續(xù)(tBxxhBAT協(xié)協(xié)議議2 2評(píng)評(píng)述述. .3 Feige-Fiat-Shamir鑒別協(xié)議(續(xù))。并將其交給的平方根就可以計(jì)算的分解，知道。由于信任中心是一個(gè)適當(dāng)?shù)墓_(kāi)函數(shù)計(jì)算出來(lái)，這里，用和其他實(shí)體可以由，的公開(kāi)值。的信息或其它驗(yàn)證者希望驗(yàn)證例如，名字，地址，的身份不同位串識(shí)每個(gè)實(shí)體分配一個(gè)標(biāo)份基方案。方案可以改造成如下身AsvnTfiIfvBTkivAIATiiAiiA )( 1 )( (6.4)續(xù)(評(píng)述.評(píng)述.3 Feige-Fiat-Shamir鑒別協(xié)議(續(xù))的離線攻擊

22、。須適當(dāng)增加以防止對(duì)的比特長(zhǎng)度必方案，提問(wèn)以變成一個(gè)非交互簽名交互鑒別方案就可。通過(guò)這一變換，一個(gè)者的作用基本起到一個(gè)驗(yàn)證的一個(gè)連接與被簽名消息據(jù)代替，這里是證值用單向隨機(jī)提問(wèn)者的數(shù)字簽名方案：將驗(yàn)證順序的鑒別協(xié)議轉(zhuǎn)變?yōu)榛卮鹛釂?wèn)一個(gè)證據(jù)如下的一般方法可以將Hash )()|( Hash (6.5)續(xù)(ehmxmxhee評(píng)評(píng)述述. .4 GQ鑒別協(xié)議。并保證其真實(shí)性，統(tǒng)參數(shù)所有用戶都可以獲得系。，并計(jì)算他的秘密指數(shù)，這里，滿足定義一個(gè)公開(kāi)指數(shù)必定不可能。，分解作為。并產(chǎn)生模和型素?cái)?shù)選擇一個(gè)秘密的隨機(jī)綁定。身份負(fù)責(zé)將公開(kāi)密鑰與用戶一個(gè)為各方信任的權(quán)威系統(tǒng)參數(shù)選擇。通過(guò)掌握知識(shí)份證明自己的身輪協(xié)議向

23、驗(yàn)證者通過(guò)一個(gè)摘要：證明者鑒別協(xié)議 )( )( (1.3) (mod 1)1)( 1 )(3 (1.2)RSA( RSA (1.1). (1)(3GQ 1nvvsqpvvTnqpnqpTTsBAA協(xié)協(xié)議議3 34 GQ鑒別協(xié)議(續(xù))接受其身份。次執(zhí)行都成功的情況下僅在證明自己的身份；次執(zhí)行如下步驟向通過(guò)協(xié)議執(zhí)行。交給審定合格的數(shù)據(jù)將秘密。，困難隱含了假定分解一個(gè)公開(kāi)的冗余函數(shù)。是，這里滿足，冗余身份可以計(jì)算，從這個(gè)身份值被賦予唯一一個(gè)身份每個(gè)用戶每個(gè)用戶參數(shù)選擇續(xù)鑒別協(xié)議tBBtAAnJsTnJnfnJIfJIAsAAAAAAA . (3) (mod)( )( (2.2)1 )( ( 1 )(

24、 )( (2.1). (2)(GQ 協(xié)議3協(xié)議34 GQ鑒別協(xié)議(續(xù)) )0 (0 )(mod )( (3.5) )()(mod (3.4)1 )( (3.3) ( (3.2) (mod )(1 1 )( (3.1)(GQ 。攻擊者選擇后一種情況是為了阻止身份的證明。對(duì)其，就接受和，并且如果，計(jì)算建立從見(jiàn)上面之后，用收到。回答給計(jì)算并發(fā)送。，給，提問(wèn)數(shù)選擇并發(fā)送一個(gè)隨機(jī)整。給，發(fā)送整數(shù)對(duì)。證據(jù)，并且計(jì)算，承諾選擇一個(gè)隨機(jī)整數(shù)續(xù)鑒別協(xié)議rAzxznyJzJIfyBBnsryAAveeBBxIAnrxnrrAveAAAeAAv協(xié)議3協(xié)議34 GQ鑒別協(xié)議(續(xù))BA) (mod nrxIvA，拒絕證

25、明。否則，接受證明；則并且如果BBxznyJzveA , ) 0(mod vee1 ，這里) (mod nsryeA4 GQ鑒別協(xié)議(續(xù))。和的身份，這是因?yàn)椴⒔邮苡?jì)算。給發(fā)送。給發(fā)送隨機(jī)提問(wèn)。給，發(fā)送整數(shù)對(duì)。并計(jì)算選擇。發(fā)給將審定合格的數(shù)據(jù)。的冗余身份參數(shù)是假定讓全體用戶得到。，系統(tǒng)參數(shù)。，并且計(jì)算，選擇計(jì)算。，并且計(jì)算，選擇素?cái)?shù)權(quán)威使用小參數(shù)并且0 89525 )(mod (3.5)83551 ) (mod (3.4)38980 (3.3) 89525) ( (3.2)89525 ) (mod 65446 (3.1) (3)403154 ) (mod )( (2.2)34579 (2.1)

26、 (2)420491) (54955 (1.3)233875 mod 54955 419184 1)1)( (1.2)420491 739 569 (1.1) (1)1) ( 1zxzAnyJz BBnsryAAeBBIAnrxrAAnJsTJAvsvqpTqpnqpTtveAeAAvsAAA例例子子2 24 GQ鑒別協(xié)議(續(xù))是困難的。的因子情況下通常認(rèn)為知道更困難，但在不這并不比分解是攻擊協(xié)議的方法；問(wèn)題解也就是，求次平方根的模合整數(shù)需要的安全假設(shè)。計(jì)算者存在的環(huán)境而定。比特長(zhǎng)度應(yīng)該根據(jù)攻擊的攻擊協(xié)議。推薦的計(jì)算并進(jìn)一步像驗(yàn)證者一樣的概率成功事先猜測(cè)證明者可以有效計(jì)算。一個(gè)冒充的有利于一些

27、值如；卻需要許多輪交互協(xié)議，這里比較決定安全等級(jí)，中偽造的概率。在評(píng)述nnvnvyJxevvvvveA )RSA( (2)( / 112 )2 Shamir-Fiat( 協(xié)議 (1)163.4 GQ鑒別協(xié)議(續(xù))誤審定合格的數(shù)據(jù)。假身份的錯(cuò)止攻擊者計(jì)算出對(duì)應(yīng)虛使用冗余函數(shù)的目是阻的多項(xiàng)式。必須不大于為常數(shù)的情況，對(duì)于的漸進(jìn)上限：是一個(gè)整數(shù)，考慮，這里要求方案的零知識(shí)屬性對(duì)于相反，零知識(shí)屬性。與正確性。必須漸進(jìn)增加快于要求是，技術(shù)上對(duì)于正確屬性的是一個(gè)常數(shù)，。如果，偽造的概率是，對(duì)于一般參數(shù)比特素?cái)?shù)。是一個(gè)而方案建議正確屬性。在實(shí)踐中，評(píng)述 (5) log ) O(log GQ (4)loglo

28、g)(1 GQ (3)續(xù)(ntvt cnvt ntvvtvnkvtct.5 Schnorr身份鑒別關(guān)聯(lián)得到。與秘密知識(shí)鑰密通過(guò)認(rèn)證證書(shū)將其公開(kāi)，鑒別不給出知識(shí)來(lái)證明其掌握秘密根據(jù)一個(gè)提問(wèn)個(gè)時(shí)變的方式以一?；舅枷胧亲C明者也使得交互的數(shù)據(jù)減少。當(dāng)然，使用這種群的乘法群，這里階為的改進(jìn)源于使用整數(shù)模進(jìn)一步重要的計(jì)算效率。者計(jì)算能力有限的情況開(kāi)銷(xiāo)，這非常適合證明算算以減少證明者實(shí)時(shí)計(jì)難性。設(shè)計(jì)允許預(yù)先計(jì)離散對(duì)數(shù)問(wèn)題的困鑒別協(xié)議的安全性依賴avAaaeApqqp)()(1)( |Schnorr5 Schnorr身份鑒別(續(xù))Hash()( )( (1.3)1 1 (1.2)(1 (1.1). (1)3

29、Schnorr 。數(shù)和任意一個(gè)簽名機(jī)制函適當(dāng)?shù)墓_(kāi)涉及在簽名之前的一個(gè)。簽名的對(duì)消息，它可以驗(yàn)證的驗(yàn)證公開(kāi)密鑰的函數(shù)中心和信任，系統(tǒng)參數(shù)每一方得到一份真實(shí)的。，的元選擇一個(gè)乘法階為可能。的離散對(duì)數(shù)在計(jì)算上不保證模整除?？梢员涣硪粋€(gè)素?cái)?shù)滿足選擇一個(gè)適當(dāng)?shù)乃財(cái)?shù)系統(tǒng)參數(shù)選擇身份。證明自己的輪協(xié)議向驗(yàn)證者通過(guò)一個(gè)摘要：證明者鑒別協(xié)議TTSmSmTTqppqpqppBA協(xié)議4協(xié)議45 Schnorr身份鑒別(續(xù))綁定。和將，書(shū)頒發(fā)的證，最后得到一個(gè)由傳遞給份，接著將真實(shí)的驗(yàn)證自己的身例如，出示護(hù)照通過(guò)傳統(tǒng)方式向。，并計(jì)算，選擇一個(gè)秘密密鑰。選擇一個(gè)唯一身份每個(gè)實(shí)體每個(gè)用戶參數(shù)選擇。全等級(jí)定義一個(gè)安，例如，選擇一個(gè)安全參數(shù)續(xù)鑒別協(xié)議vIvISvIcertTTvTApvqaaAIAqttAATAAaAtt)( ( )( (2.3) (mod 1 0 (2.2) (2.1). (2)2( 2 40) ( (1.4)(Schnorr 協(xié)議4協(xié)議45 Schnorr身份鑒別(續(xù))的身份。，接受，如果計(jì)算。給回答并發(fā)送檢查。，給，提問(wèn)隨機(jī)數(shù)從未使用過(guò)的實(shí)性，接著發(fā)送一個(gè)的真的公開(kāi)密鑰中的簽名驗(yàn)證在證書(shū)通過(guò)。給，并發(fā)送證據(jù)計(jì)算，承諾選擇一個(gè)隨機(jī)數(shù)驗(yàn)證自己的身份。按如下步驟向協(xié)議執(zhí)行續(xù)鑒別協(xié)議AxzpvzBBqreayeAAeevAcertTBBxcertpxqr