這是零知識證明ppt，包括了身份證明技術(shù)，交互式證明，交互證明與數(shù)學(xué)證明的區(qū)別，身份識別方案的要求，Guillou-Quisquater身份識別方案，零知識證明，哈米爾頓回路等內(nèi)容，歡迎點(diǎn)擊下載。

零知識證明ppt是由紅軟PPT免費(fèi)下載網(wǎng)推薦的一款課件PPT類型的PowerPoint.

第九章身份識別和零知識證明  一、身份證明技術(shù) 傳統(tǒng)的身份證明： 一般是通過檢驗(yàn)“物”的有效性來確認(rèn)持該物的人身份。徽章、工作證、信用卡、駕駛執(zhí)照、身份證、護(hù)照等，卡上含有個人照片(易于換成指紋、視網(wǎng)膜圖樣、牙齒等)。 信息系統(tǒng)常用方式： 用戶名和口令 交互式證明 兩方參與 示證者P(Prover)，知道某一秘密，使V相信自己掌握這一秘密； 驗(yàn)證者V(Verifier)，驗(yàn)證P掌握秘密；每輪V向P發(fā)出一詢問，P向V做應(yīng)答。V檢查P是否每一輪都能正確應(yīng)答。 交互證明與數(shù)學(xué)證明的區(qū)別 數(shù)學(xué)證明的證明者可自己獨(dú)立的完成證明 交互證明由P產(chǎn)生證明，V驗(yàn)證證明的有效性來實(shí)現(xiàn)，雙方之間要有通信 交互系統(tǒng)應(yīng)滿足 完備性：如果P知道某一秘密，V將接收P的證明 正確性：如果P能以一定的概率使V相信P的證明，則P知道相應(yīng)的秘密 身份識別方案的要求 假設(shè)A和B是通信的雙方，當(dāng)A與B進(jìn)行通信時， A首先要向B證明自己的身份。 一個安全的身份識別方案至少應(yīng)該滿足以下兩 個要求： (1)A能向B證明自己的確是A (2)當(dāng)A向B證明了自己的身份后，B得不到任何用于模仿A的有用信息，B無法向第三方聲稱自己是A. Guillou-Quisquater身份識別方案 Guillou-Quisquater身份識別方案的安全 性主要是基于RSA公鑰密碼體制的安全性. Guillou-Quisquater身份識別方案需要一 個可信當(dāng)局，簡稱TA. Guillou-Quisquater身份識別方案 參數(shù)的選�。� (1)TA選取兩個大素數(shù)p和q，計算n=pq，p和q保密，而n公開. (2)TA選取一個大素數(shù)b作為安全參數(shù)，b公開，b所起的作用相當(dāng)于RSA公鑰密碼體制中的加密密鑰，可以防止攻擊者模仿A. (3)TA選取一個Hash函數(shù)和一個簽名方案. 假設(shè)TA的保密的簽名算法為SigTA 。公開的簽名驗(yàn) 證算法為VerTA .TA在對一個消息進(jìn)行簽名之前，首先 對消息做Hash變換，然后對Hash變換后的消息進(jìn)行 簽名。 Guillou-Quisquater身份識別方案 在Guillou-Quisquater身份識別方案中，用戶A需要一個證書，證書中包含了經(jīng)由TA簽名的有關(guān)A的身份的一些信息，用戶A的證書由TA頒發(fā).證書是公開的，TA向用戶A頒發(fā)證書的協(xié)議如下： (1)TA建立用戶A的身份并產(chǎn)生一個表示A身份的字符串ID(A) (2)A秘密選取一個與n互素的整數(shù)u(0≤u≤n-1).A計算 v=(u-1)b modn，并將v傳送給TA (3)TA產(chǎn)生簽名 s=SigTA(ID(A)，v)， 并將證書C(A)=(ID(A)，v，s)傳送給A Guillou-Quisquater身份識別方案 當(dāng)A要向B證明自己的身份時，A和B執(zhí)行下面的協(xié)議： (1)A隨機(jī)選取整數(shù)k(0≤k≤n-1)，然后A計算 r=kb modn (2)A將其證書C(A)=(ID(A)，v，s)和r傳送給B (3)B利用TA公開的簽名驗(yàn)證算法來檢驗(yàn)s是否為TA對 (ID(A)，v)的簽名 (4)B隨機(jī)選取整數(shù)t (0≤t≤b-1)，B將t傳送給A (5)A計算 y=kut modn，A將y傳送給B (6)B驗(yàn)證 r=vt yb modn是否成立.如果上式成立則B接受A的身份證明；否則拒絕A的身份證明. 二、零知識證明 最小泄露證明和零知識證明： 以一種有效的數(shù)學(xué)方法，使V可以檢驗(yàn)每一步成立，最終確信P知道其秘密，而又能保證不泄露P所知道的信息。 零知識證明的基本協(xié)議 例[Quisquater等1989] 。 零知識證明的基本協(xié)議 (1) V站在A點(diǎn)； (2) P進(jìn)入洞中任一點(diǎn)C或D； (3) 當(dāng)P進(jìn)洞之后，V走到B點(diǎn)； (4) V叫P從左邊出來，或從右邊出來； (5) P按要求實(shí)現(xiàn)(以咒語，即解數(shù)學(xué)難題幫助)； (6) P和V重復(fù)執(zhí)行 (1)～(5)共n次。 若P不知咒語，則在B點(diǎn)，只有50 %的機(jī)會猜中V的要求，協(xié)議執(zhí)行n次，則只有2-n的機(jī)會完全猜中，若n=16，則若每次均通過V的檢驗(yàn)，V受騙機(jī)會僅為1/65 536 零知識證明的基本協(xié)議 說明： 在上述協(xié)議的執(zhí)行過程中，V沒有得到關(guān)于 咒語的任何信息，因此上述協(xié)議是一個零知 識證明協(xié)議. 零知識證明的基本協(xié)議 哈米爾頓回路 圖論中有一個著名問題，對有n個頂點(diǎn)的全連通圖G，若有一條通路可通過且僅通過各頂點(diǎn)一次，則稱其為哈米爾頓回路。Blum[1986] 最早將其用于零知識證明。當(dāng)n大時，要想找到一條Hamilton回路，用計算機(jī)做也要好多年，它是一種單向函數(shù)問題。若A知道一條回路，如何使B相信他知道，且不告訴他具體回路？ 哈米爾頓回路 (1) A將G進(jìn)行隨機(jī)置換，對其頂點(diǎn)進(jìn)行移動，并改變其標(biāo)號得到一個新的有限圖H。因 ，故G上的Hamilton回路與H上的Hamilton回路一一對應(yīng)。已知G上的Hamilton回路易于找出H上的相應(yīng)回路； (2)A將H的復(fù)本給B； (3) B向A提出下述問題之一：(a) 出示證明G和H同構(gòu)，(b) 出示H上的Hamilton回路； (4) A執(zhí)行下述任務(wù)之一：(a) 證明G和H同構(gòu)，但不出示H上的Hamilton回路，(b) 出示H上的Hamilton回路但不證明G和H同構(gòu)； (5) A和B重復(fù)執(zhí)行 (1)～(4)共n次。 零知識證明 設(shè)p和q是兩個大素數(shù)，n=pq.假設(shè)P知道n的因 子.如果P想讓V相信他知道n的因子，并且P不 想讓V知道n的因子，則P和V可以執(zhí)行怎樣的 協(xié)議？ 零知識證明 (1) V隨機(jī)選取一個大整數(shù)x，計算 y=x4 modn V將結(jié)果y告訴P (2) P計算 Z= modn P將結(jié)果z告訴V (3)V驗(yàn)證 z=x2 modn 是否成立. 上述協(xié)議可以重復(fù)執(zhí)行多次，如果P每次都能正確地計 算 modn，則V就可以相信P知道n的因子p和q. 零知識證明 說明： 計算 modn等價于對n進(jìn)行因子分解.如果P不知道n的因子p和q，則計算 modn是一個困難的問題.因此，如果P不知道n的因子，則在多次重復(fù)執(zhí)行上述協(xié)議的情況下，P每次都能正確地計算 modn的概率是非常小的。顯然，在上述協(xié)議中，V沒有得到關(guān)于n的因子p和q的任何信息，因此上述協(xié)議是一個零知識證明協(xié)議.2V0紅軟基地