零知識證明的概念

設P表示掌握某些信息，并希望證實這一事實的實體，設V是證明這一事實的實體。某個協(xié)議向V證明P的確掌握某些信息，但V無法推斷出這些信息是什么，我們稱P實現(xiàn)了最小泄露證明。如果V除了知道P能夠證明某一事實外，不能夠得到其他任何知識，我們稱P實現(xiàn)了零知識證明，相應的協(xié)議稱作零知識協(xié)議。零知識證明的概念在最小泄露協(xié)議中滿足下述兩個性質(zhì)：(1)P無法欺騙V。換言之，若P不知道一個定理的證明方法，則P使V相信他會證明定理的概率很低。（正確性）(2)V無法欺騙P。換言之，若P知道一個定理的證明方法，則P使V以絕對優(yōu)勢的概率相信他能證明。（完備性）在零知識協(xié)議中，除滿足上述兩個條件以外，還滿足下述性質(zhì)：(3)V無法獲取任何額外的知識。（零知識性）零知識洞穴設P知道咒語，可打開C和D之間的秘密門，不知道者則走向死胡同?，F(xiàn)在來看P如何向V出示證明使其相信他知道這個秘密，但又不告訴V有關咒語。協(xié)議1：洞穴協(xié)議

V站在A點；P進入任一點C或D；當P進洞之后，V走向B點；V叫P：(a)從左邊出來，或(b)從右邊出來P按照要求實現(xiàn)（有咒語）；P和V重復執(zhí)行(1)~(5)共n次。零知識洞穴若P不知道咒語，則在B點，只有50%的機會猜中V的要求，協(xié)議執(zhí)行n次，則只有2?n次機會完全猜中。此洞穴問題可以轉(zhuǎn)化為數(shù)學問題，P知道解決某個難題的秘密信息，而V通過與P交互作用驗證其真?zhèn)?。CDBA5零知識證明可以向另一方證明自己擁有某種信息而無需暴露該信息給對方。6交互式零知識證明

證明者和驗證者共享輸入

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

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

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

modpCommitmentChallengeResponseProverVerifierPeggy試圖向Vector證明兩個離散對數(shù)相等而不泄露x，Y=gx，Z=cx，loggY=logc

ZCommitmentChallengeResponseProverVerifier離散對數(shù)問題的零知識證明證明ElGamal解密的正確性比如，Peggy試圖證明他的ElGamal解密是正確的。明文是m而不泄露他的私鑰x。

Peggy的私鑰為Y=gx

modp；ElGamal加密為m

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

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

使用

Fiat-ShamirHeuristic的非交互零知識證明

(NIZK)

非交互零知識證明

ProverVerifier身份鑒別方案在一個安全的身份認證協(xié)議中，我們希望被認證者P能向驗證者V電子地證明他的身份，而又不向P泄露他的認證信息Feige-Fiat-Shamir身份鑒別方案Guillo-Quisquater身份鑒別方案Schnorr身份鑒別方案簡化的Feige-Fiat-Shamir身份鑒別方案可信賴仲裁方選定一個隨機模數(shù)n=p1×p2，p1、p2為兩個大素數(shù)。實際中n至少為512比特，盡量長達1024比特。仲裁方可實施公鑰和私鑰的分配。他產(chǎn)生隨機數(shù)v（v為對模n的二次剩余）。換言之，選擇v使得x2=vmodn有一個解并且v–1modn

存在。以v作為被驗證方的公鑰，而后計算最小的整數(shù)s：s≡sqrt(v–1)modn，將它作為被驗方P的私人密鑰而分發(fā)給他。簡化的Feige-Fiat-Shamir身份鑒別方案實施身份證明的協(xié)議如下：

(1)用戶P取隨機數(shù)r（r<m），計算x=(x2)modn，送給驗證方V：

(2)V將隨機比特b送給P；

(3)若b=0，則P將r送給V；若b=1，則將y=rsmodn送給V；

(4)若b=0，則V驗證x=r2modn，從而證明P知道sqrt(x)；若b=1，則V驗證x=y2

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

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

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

q。公鑰指數(shù)有e≥3，其中gcd(φ,e)=1，φ=(p–1)(q–1)。計算出秘密指數(shù)d=e–1modφ

，公開(e,n)，各用戶選定自己的參數(shù)。用戶A的唯一性身份IA，通過散列函數(shù)H變換得出相應散列值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選擇的秘密隨機數(shù)；(2)B→A：B選隨機數(shù)u，u≥1；(3)A→B：y=r·SA

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

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

u

·Yemodn。若結(jié)果不為0且等于x，則可確認A的身份；否則拒絕A。Guillo-Quisquater身份鑒別方案BASchnorr身份鑒別方案以上方案有一定的缺陷：實時計算量、消息交換量和所需存儲量較大，Schnorr提出的一種安全性基于計算離散對數(shù)的困難性的鑒別方案，可以做預計算來降低實時計算量，所需傳送的數(shù)據(jù)量亦減少許多，特別適用于計算能力有限的情況。ClausSchnorr的認證方案的安全性建立在計算離散對數(shù)的難度上。為了產(chǎn)生密鑰對，首先選定系統(tǒng)的參數(shù)：素數(shù)p及素數(shù)q，q是p–1的素數(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)和驗證函數(shù)（即T的公鑰），用此驗證T對消息的簽字。Schnorr身份鑒別方案對每個用戶給定惟一身份I，用戶A選定秘密密鑰s，0≤s≤q–1，并計算v=g–smodp；A將IA和v可靠地送給T，并從T獲得證書，CA=(IA,v,ST

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

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

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

modp，若該等式成立，則認可A的身份合法。安全性基于參數(shù)t，t要選得足夠大以使正確猜對e的概率2–t足夠小。Schnorr建議t為72位，p大約為512位，q為140位。此協(xié)議是一種對s的零