零知識(shí)證明課件

零知識(shí)證明零知識(shí)證明的概念 設(shè)P表示掌握某些信息，并希望證實(shí)這一事實(shí)的實(shí)體，設(shè)V是證明這一事實(shí)的實(shí)體。某個(gè)協(xié)議向V證明P的確掌握某些信息，但V無法推斷出這些信息是什么，我們稱P實(shí)現(xiàn)了最小泄露證明。如果V除了知道P能夠證明某一事實(shí)外，不能夠得到其他任何知識(shí)，我們稱P實(shí)現(xiàn)了零知識(shí)證明，相應(yīng)的協(xié)議稱作零知識(shí)協(xié)議。零知識(shí)證明的概念在最小泄露協(xié)議中滿足下述兩個(gè)性質(zhì)：(1)P無法欺騙V。換言之，若P不知道一個(gè)定理的證明方法，則P使V相信他會(huì)證明定理的概率很低。（正確性）(2)V無法欺騙P。換言之，若P知道一個(gè)定理的證明方法，則P使V以絕對(duì)優(yōu)勢(shì)的概率相信他能證明。（完備性）在零知識(shí)協(xié)議中，除滿足上述兩個(gè)條件以外，還滿足下述性質(zhì)：(3)V無法獲取任何額外的知識(shí)。（零知識(shí)性）零知識(shí)洞穴若P不知道咒語，則在B點(diǎn)，只有50%的機(jī)會(huì)猜中V的要求，協(xié)議執(zhí)行n次，則只有50%n次機(jī)會(huì)完全猜中。此洞穴問題可以轉(zhuǎn)化為數(shù)學(xué)問題，P知道解決某個(gè)難題的秘密信息，而V通過與P交互作用驗(yàn)證其真?zhèn)巍DBA6交互式零知識(shí)證明

證明者和驗(yàn)證者共享輸入

(函數(shù)或者是值)如果驗(yàn)證者檢查，對(duì)于每一個(gè)挑戰(zhàn)的響應(yīng)都是正確的，這個(gè)協(xié)議才輸出Accept，否則，輸出RejectP證明者V驗(yàn)證者承諾挑戰(zhàn)響應(yīng)Repeatstrounds輸入輸入平方根問題的零知識(shí)令N=PQ，P、Q為兩個(gè)大素?cái)?shù)，Y是modN的一個(gè)平方，且gcd(Y,N)=1，注意找到modN的平方根與分解N等價(jià)。Peggy聲稱他知道Y的一個(gè)平方根S，但他不愿意泄露S，Vector想證明Peggy是否真的知道。下面給出了這個(gè)問題的一個(gè)解決方案。Peggy選擇兩個(gè)隨機(jī)數(shù)R1和R2，滿足gcd(R1,N)=1，R2=SR1–1，R1

R2=S(modN)。Peggy計(jì)算X1=R12(modN)，X2=R22(modN)，并將X1、X2發(fā)送給Vector。Vector檢驗(yàn)X1

X2=Y(modN)，然后Vector隨機(jī)選擇X1（或X2）讓Peggy提供它的一個(gè)平方根，并檢驗(yàn)Peggy是否提供的是真的平方根。重復(fù)上面的過程直至Vector相信。這里，Peggy不知道Y的平方根，雖然他可能知道X1、X2的一個(gè)平方根，但不是全部。離散對(duì)數(shù)問題的零知識(shí)證明Peggy試圖向Vector證明他知道離散對(duì)數(shù)x，x=loggYmodp，Y=gx

modpCommitmentChallengeResponseProverVerifier證明ElGamal解密的正確性比如，Peggy試圖證明他的ElGamal解密是正確的。明文是m而不泄露他的私鑰x。Peggy的私鑰為Y=gx

modp；ElGamal加密為m

(U,V)，ElGamal解密為V/Ux

mPeggy只需證明下面的兩個(gè)離散對(duì)數(shù)相等即可：Y=gx，V/m=Ux，loggY=logU(V/m)。

身份鑒別方案在一個(gè)安全的身份認(rèn)證協(xié)議中，我們希望被認(rèn)證者P能向驗(yàn)證者V電子地證明他的身份，而又不向P泄露他的認(rèn)證信息Feige-Fiat-Shamir身份鑒別方案Guillo-Quisquater身份鑒別方案Schnorr身份鑒別方案簡(jiǎn)化的Feige-Fiat-Shamir身份鑒別方案實(shí)施身份證明的協(xié)議如下：(1)用戶P取隨機(jī)數(shù)r（r<m），計(jì)算x=(x2)modn，送給驗(yàn)證方V： (2)V將隨機(jī)比特b送給P； (3)若b=0，則P將r送給V；若b=1，則將y=rsmodn送給V； (4)若b=0，則V驗(yàn)證x=r2modn，從而證明P知道sqrt(x)；若b=1，則V驗(yàn)證x=y2

vmodn，從而證明P知道s。這是一輪認(rèn)證，P和V可將此協(xié)議重復(fù)t次，直到V確信P知道s為止。BA簡(jiǎn)化的Feige-Fiat-Shamir身份鑒別方案簡(jiǎn)化的Feige-Fiat-Shamir身份鑒別方案安全性討論如下：P欺騙V的可能性。P不知道s，他也可選取隨機(jī)數(shù)r，將x=r2modn發(fā)給V，V發(fā)送隨機(jī)比特b給P，P可將r送出。當(dāng)b=0時(shí)，則V讓P通過檢驗(yàn)而受騙；當(dāng)b=1時(shí)，則V可發(fā)現(xiàn)P不知道s。V受騙的概率為1/2，但連續(xù)t次受騙的概率將僅為2–1。V偽裝P的可能性。V和其他驗(yàn)證者W開始一個(gè)協(xié)議。第一步他可用P用過的隨機(jī)數(shù)r，若W所選的b值恰與以前發(fā)給P的一樣，則V可將在第(3)步所發(fā)的r或y重發(fā)給W，從而可成功的偽裝P。但W可能隨機(jī)地選b為0或1，故這種工具成功的概率為1/2，執(zhí)行t次，則可使其將為2–t?？尚刨囍俨梅竭xn=p1×p2，p1、p2為兩個(gè)大素?cái)?shù)，并選k個(gè)不同的隨機(jī)數(shù)v1,v2,…,vk，各vi是modn的平方剩余，且有逆。以v1,v2,…,vk為被驗(yàn)證方P的公鑰，計(jì)算最小正整數(shù)si，使si=modn，將s1,s2,…,sk作為P的私人密鑰。Feige-Fiat-Shamir身份鑒別方案Feige-Fiat-Shamir身份鑒別方案協(xié)議如下：(1)P選隨機(jī)數(shù)r（r<m），計(jì)算x=r2modn并發(fā)送給驗(yàn)證方V；(2)V選k比特隨機(jī)二進(jìn)制串b1,b2,…,bk傳送給P；(3)P計(jì)算y=r×(s1b1×s2b2×…×skbk

)modn，并送給V；(4)V驗(yàn)證x=y2×(v1b1×v2b2×…×vkbk

)modn。此協(xié)議可執(zhí)行t次，直到V相信P知道s1,s2,…,sk，P欺騙V的機(jī)會(huì)為2–kt。Guillo-Quisquater身份鑒別方案Guillo和Quisquater給出一種身份認(rèn)證方案，這個(gè)協(xié)議需要三方參與、三次傳送，利用公鑰體制實(shí)現(xiàn)?？尚刨囍俨梅絋先選定RSA的秘密參數(shù)p和q，生成大整數(shù)模n=p

q。公鑰指數(shù)有e≥3，其中g(shù)cd(φ,e)=1，φ=(p–1)(q–1)。計(jì)算出秘密指數(shù)d=e–1modφ，公開(e,n)，各用戶選定自己的參數(shù)。用戶A的唯一性身份IA，通過散列函數(shù)H變換得出相應(yīng)散列值JA

=H(IA)，I<JA<n，gcd(JA,φ)=1，T向A分配密鑰函數(shù)SA

=(JA)–dmodn。

Guillo-Quisquater身份鑒別方案單輪（t=1）GQ協(xié)議三次傳輸?shù)南椋?1)A→B：IA，x=remodn，其中r是A選擇的秘密隨機(jī)數(shù)；(2)B→A：B選隨機(jī)數(shù)u，u≥1；(3)A→B：y=r·SA

umodn。具體協(xié)議描述如下：(1)A選擇隨機(jī)數(shù)r，1≤r≤n–1，計(jì)算x=remodn，A將(IA,x)送給B；(2)B選擇隨機(jī)數(shù)u，1≤u≤e，將u送給A；(3)A計(jì)算y=r·SA

umodn，送給B；(4)B收到y(tǒng)后，從IA計(jì)算JA=H(IA)，并計(jì)算JA

u

·Yemodn。若結(jié)果不為0且等于x，則可確認(rèn)A的身份；否則拒絕A。Schnorr身份鑒別方案以上方案有一定的缺陷：實(shí)時(shí)計(jì)算量、消息交換量和所需存儲(chǔ)量較大，Schnorr提出的一種安全性基于計(jì)算離散對(duì)數(shù)的困難性的鑒別方案，可以做預(yù)計(jì)算來降低實(shí)時(shí)計(jì)算量，所需傳送的數(shù)據(jù)量亦減少許多，特別適用于計(jì)算能力有限的情況。ClausSchnorr的認(rèn)證方案的安全性建立在計(jì)算離散對(duì)數(shù)的難度上。為了產(chǎn)生密鑰對(duì)，首先選定系統(tǒng)的參數(shù)：素?cái)?shù)p及素?cái)?shù)q，q是p–1的素?cái)?shù)因子。p21024，q>2160，元素g為q階元素，l≤g≤p–1。令a為GF(p)的生成元，則得到g=a(p–1)/qmodq。由可信賴的第三方T向各用戶分發(fā)系統(tǒng)參數(shù)(p,q,g)和驗(yàn)證函數(shù)（即T的公鑰），用此驗(yàn)證T對(duì)消息的簽字。Schnorr身份鑒別方案對(duì)每個(gè)用戶給定惟一身份I，用戶A選定秘密密鑰s，0≤s≤q–1，并計(jì)算v=g–smodp；A將IA和v可靠地送給T，并從T獲得證書，CA=(IA,v,ST

(IA,v))。協(xié)議如下：（1）選定隨機(jī)數(shù)r，1≤r≤q–1，計(jì)算x=gr

modp，這是預(yù)處理步驟，可在B出現(xiàn)之前完成；（2）A將(CA,x)送給B；（3）B以T的公鑰解ST(IA,v)，實(shí)現(xiàn)對(duì)A的身份IA和公鑰v認(rèn)證，并傳送一個(gè)介于0到2t–1之間的隨機(jī)數(shù)e給A；（4）A驗(yàn)證1≤e≤2t，計(jì)算y=(s

e+r)modq，并將y送給B；（5）B驗(yàn)證x=gyve

modp，若該等式成立，則認(rèn)可A的身份合法。安全性基于參數(shù)t，t要選得足夠大以使正確猜對(duì)e的概率2–t足夠小。Schnorr建議t為72位，p大約為512位，q為140位。此協(xié)議是一種對(duì)s的零知識(shí)證明，在認(rèn)證過程中沒有暴露有關(guān)s的任何有用信息。

復(fù)雜性理論在計(jì)算機(jī)學(xué)科中，存在多項(xiàng)式時(shí)間的算法的一類問題，稱之為P類問題；而向旅行商問題、命題表達(dá)式可滿足問題這類，至今沒有找到多項(xiàng)式時(shí)間算法解的一類問題，稱之為NP類問題。NP問題中最難的稱之為NP完全問題（1）旅行商問題（2）三方匹配問題（3）三方滿足問題NP與零知識(shí)證明每一個(gè)NP問題都存在一個(gè)零知識(shí)證明GMR(Goldwasser,Micali,Rackoff)“Theknowledgecomplexityofinteractive-proofsystems”,Proc.of17thACMSym.onTheoryofComputation,pp.