張引兵，王 慧

（淮北師范大學(xué) 數(shù)學(xué)科學(xué)學(xué)院，安徽 淮北 235000）

零知識(shí)證明協(xié)議研究

張引兵，王 慧

（淮北師范大學(xué) 數(shù)學(xué)科學(xué)學(xué)院，安徽 淮北 235000）

在當(dāng)代密碼學(xué)中，零知識(shí)證明占據(jù)著重要的位置.已經(jīng)成為信息安全領(lǐng)域身份認(rèn)證的關(guān)鍵技術(shù)之一,吸引了許多學(xué)者的注意，并得到了一系列的重要研究成果.文章首先闡述了零知識(shí)證明的主要思想、零知識(shí)證明協(xié)議的性質(zhì)以及零知識(shí)證明協(xié)議所主要基于的幾類數(shù)學(xué)問(wèn)題.接著，著重研究了零知識(shí)證明在相關(guān)問(wèn)題中的應(yīng)用.最后，對(duì)本文進(jìn)行了總結(jié),以期能夠吸引更多的學(xué)者在更廣泛的領(lǐng)域?qū)α阒R(shí)證明協(xié)議進(jìn)行研究.

密碼學(xué)；零知識(shí)證明；數(shù)獨(dú)；多項(xiàng)式函數(shù)根；身份認(rèn)證

1 引言

“零知識(shí)證明”－zero-knowledge proof，這一概念是由Goldwasser等人[1,2]在20世紀(jì)80年代初提出的.從提出到現(xiàn)在已經(jīng)有30多年的時(shí)間了，在零知識(shí)證明的研究中，已經(jīng)取得了許多重要的成果，但仍有許多問(wèn)題有待進(jìn)一步的研究，近年來(lái)已經(jīng)成為密碼學(xué)研究中的熱點(diǎn)問(wèn)題之一.零知識(shí)證明的思想是許多密碼學(xué)協(xié)議的基礎(chǔ)，在安全協(xié)議的設(shè)計(jì)中有著比較廣泛的應(yīng)用.

2 零知識(shí)證明相關(guān)概念

2.1 零知識(shí)證明的主要思想

零知識(shí)證明指的的就是一方(證明者)能夠在不向另一方(驗(yàn)證者)提供任何有用的信息的前提下，也能使得另一方能夠相信某個(gè)論斷是正確的.其本質(zhì)上是一種涉及兩方的協(xié)議，其中的一方稱為證明者，一般用P表示，另一方稱為驗(yàn)證者，一般用V表示.在協(xié)議的執(zhí)行過(guò)程中，證明者P向驗(yàn)證者V聲稱其已經(jīng)掌握了某種信息，證明者P和驗(yàn)證者V通過(guò)一系列的交互，使得驗(yàn)證者V或者相信了證明者P的聲稱，或者拒絕了證明者P的聲稱，而在這個(gè)過(guò)程中，驗(yàn)證者V沒(méi)有獲得證明者P聲稱的所掌握信息的具體內(nèi)容，這是一種全新的思想.

2.2 零知識(shí)證明協(xié)議的性質(zhì)

一般說(shuō)來(lái)，一個(gè)零知識(shí)證明協(xié)議應(yīng)該下面三個(gè)條件：

(1)可行性：如果P對(duì)V的聲稱是真的，則V以一個(gè)大的概率接受P的聲稱.

(2)可靠性：如果P對(duì)V的聲稱是假的，則V以一個(gè)大的概率拒絕P的聲稱.

(3)零知識(shí)性：如果P對(duì)V的聲稱是真的，在V沒(méi)有違反協(xié)議的前提下，則無(wú)論V采用任何方法，V除了能夠接受P的聲稱外，而無(wú)法獲有關(guān)P所聲稱內(nèi)容的任何信息[3].

2.3 零知識(shí)證明協(xié)議主要基于的幾類數(shù)學(xué)問(wèn)題

通常零知識(shí)證明協(xié)議所基于的數(shù)學(xué)問(wèn)題，類似于密碼學(xué)中的公鑰密碼體制，都是主要基于如下幾類數(shù)學(xué)問(wèn)題的.

2.3.1 模n平方根問(wèn)題

設(shè)n是一個(gè)正整數(shù)，若存在一個(gè)x，使得x2≡y (modn)，則稱x是y的模n平方根.其中：1

2.3.2 大整數(shù)分解問(wèn)題

大整數(shù)分解問(wèn)題是指，給定兩個(gè)素?cái)?shù)p,q，計(jì)算乘積p*q=n很容易；但是，反過(guò)來(lái)給定整數(shù)n,求n的素因數(shù)p,q使得n=p*q非常困難.大整數(shù)的分解問(wèn)題至今還沒(méi)有很好的快速分解的方法.在現(xiàn)有的條件下，若n足夠大，并且有時(shí)間的限制，則想要破解大整數(shù)問(wèn)題將是非常困難的.

2.3.3 離散對(duì)數(shù)問(wèn)題

離散對(duì)數(shù)問(wèn)題指的是整數(shù)中一種基于同余運(yùn)算和原根的對(duì)數(shù)運(yùn)算，也可以按照如下方式進(jìn)行簡(jiǎn)單描述：任意給定一個(gè)質(zhì)數(shù)p，和有限域Zp上的一個(gè)本原元a，對(duì)于有限域Zp上整數(shù)b，可以找到唯一的一個(gè)整數(shù)c，使a∧c≡(modp)成立.一般來(lái)說(shuō)，如果選擇p恰當(dāng)，則得到該問(wèn)題的解是困難的，且至今計(jì)算離散對(duì)數(shù)問(wèn)題的多項(xiàng)式時(shí)間算法還沒(méi)有找到.為了抵抗已知的攻擊，p至少應(yīng)該是150位的二進(jìn)制整數(shù)，且p-1至少有一個(gè)大的素?cái)?shù)因子.

3 幾種零知識(shí)證明協(xié)議

3.1 零知識(shí)證明的基本協(xié)議

由Quisquater等人[4]最先給出了有關(guān)零知識(shí)證明解釋的通俗例子，如圖1所示,在位置C與位置D之間有一個(gè)秘密的通道，而這個(gè)秘密通道只有知道相應(yīng)咒語(yǔ)的人才可以通過(guò).如果證明者P知道通過(guò)秘密通道的咒語(yǔ)，他如何在不泄露咒語(yǔ)的前提下向驗(yàn)證者V證明他知道咒語(yǔ)呢？可以按照如下協(xié)議的步驟執(zhí)行：

圖1 零知識(shí)洞穴

協(xié)議：

(1)首先讓驗(yàn)證者V走到A處；

(2)接著讓證明者P進(jìn)入洞穴，走到圖中的C處或D處；

(3)然后驗(yàn)證者V再走到圖中的B處；

(4)驗(yàn)證者V要求證明者P或者從左側(cè)通道出來(lái)或者從右側(cè)通道出來(lái)；

(5)證明者P按照驗(yàn)證者V的要求從相應(yīng)的通道出來(lái)(若有必要，可以用咒語(yǔ)打開通道)；

(6)證明者P和驗(yàn)證者V可以反復(fù)執(zhí)行(1)～(5) n輪.

在上述的零知識(shí)洞穴的例子中，若P沒(méi)有掌握秘密通道的咒語(yǔ)，則他只能從他原來(lái)進(jìn)入通道的一側(cè)出來(lái).若P靠猜測(cè)，在整個(gè)協(xié)議執(zhí)行的n輪過(guò)程中，P在每一輪中均能按照V的要求從相應(yīng)的一側(cè)出來(lái)的概率只有.經(jīng)過(guò)16輪后，P只有65536分之一的機(jī)會(huì)猜中.若進(jìn)過(guò)16輪的驗(yàn)證，P在每一輪中均能按照V的要求從相應(yīng)的一側(cè)出來(lái)，那么V就可以得出結(jié)論，P一定掌握了通過(guò)秘密通道的咒語(yǔ).

3.2 游戲中的零知識(shí)證明—數(shù)獨(dú)的零知識(shí)證明協(xié)議

數(shù)獨(dú)顧名思義——每個(gè)數(shù)字只能出現(xiàn)一次.數(shù)獨(dú)盤面是個(gè)九宮，每一宮又分為九個(gè)小格，一共是九行九列，共八十一個(gè)小格.數(shù)獨(dú)問(wèn)題就是在這八十一個(gè)小格中首先給出一些已知的數(shù)字和相關(guān)的解題條件，利用邏輯和推理的方式，在其余空余的空格上填入1-9中相應(yīng)的數(shù)字.使得1-9中所有的數(shù)字在每一行，每一列，每一個(gè)宮中都出現(xiàn)一次，且僅出現(xiàn)一次.數(shù)獨(dú)游戲能夠全面考察做題的人的觀察能力、邏輯推理與判斷的能力，雖然規(guī)則不復(fù)雜，做題也不是太難，但1-9相應(yīng)的數(shù)字的排列卻是千變?nèi)f化的，有許多教育家認(rèn)為數(shù)獨(dú)是一種訓(xùn)練孩子思維邏輯的一種不錯(cuò)的形式.在數(shù)獨(dú)問(wèn)題中，任一道合格的數(shù)獨(dú)謎題都有唯一確定的答案，邏輯推理過(guò)程也是以此為基礎(chǔ)的，所有無(wú)解或多解的數(shù)獨(dú)謎題都是不合要求的.下面給出的是一種基于比特承諾的零知識(shí)證明方案.

協(xié)議：數(shù)獨(dú)的零知識(shí)證明協(xié)議[5]

證明者：

(1)證明者隨機(jī)選擇一個(gè)置換σ:{1,2,…,9}a{1,2,…,9}；

(2)對(duì)于每個(gè)單元(i,j)的值v，證明者發(fā)送σ(v)給驗(yàn)證者；

驗(yàn)證者：

驗(yàn)證者隨機(jī)選擇下列可能性中的一種:或者一行、或者一列、或者一個(gè)子網(wǎng)格,或直接打開已經(jīng)填充好的一個(gè)單元格,并要求證明者公開相應(yīng)的承諾.當(dāng)驗(yàn)證者做出回應(yīng)后,如果驗(yàn)證者選擇了一行、一列或一個(gè)子網(wǎng)格,驗(yàn)證者檢查其中的所有的值是否確實(shí)是不同的.如果驗(yàn)證者選擇的是直接打開已經(jīng)填充好的一個(gè)單元格，驗(yàn)證者將所填充的單元格中的數(shù)據(jù)與證明者所發(fā)送的數(shù)據(jù)做比較，與原來(lái)相同的現(xiàn)在仍然相同，與原來(lái)不同的現(xiàn)在仍然不同，這樣就可以說(shuō)明σ的確是單元格中所填充數(shù)字的一種置換.

3.3 多項(xiàng)式函數(shù)根的零知識(shí)證明協(xié)議

多項(xiàng)式函數(shù)是數(shù)學(xué)中許多重要研究?jī)?nèi)容之一,在計(jì)算機(jī)科學(xué)中，多項(xiàng)式函數(shù)的研究也有著舉足輕重的作用.假如P已經(jīng)知道了某個(gè)整系數(shù)高次f(x)的一個(gè)整數(shù)根x0,現(xiàn)在他想向V證明自己已經(jīng)知道了多項(xiàng)式函數(shù)f(x)的某一個(gè)根,但又不想讓V了解有關(guān)x0的任何相關(guān)信息，這個(gè)問(wèn)題就是多項(xiàng)式函數(shù)根的零知識(shí)證明問(wèn)題.假設(shè)某整系數(shù)高次多項(xiàng)式函數(shù)其主要證明過(guò)程如下：

協(xié)議：多項(xiàng)式函數(shù)根的零知識(shí)證明協(xié)議[6]

(3)V要求p證明他擁有一個(gè)數(shù)x0，使得(modp),(i=1,2,…,n）；

(6)重復(fù)執(zhí)行(1)～(5)k輪.

3.4 圖論中的零知識(shí)證明—圖的同構(gòu)的零知識(shí)證明協(xié)議

圖的同構(gòu)問(wèn)題：有兩個(gè)圖G0(V0,E0)和G1(V1,E1)，其中這兩個(gè)圖的頂點(diǎn)數(shù)和邊數(shù)都相同，并且存在一個(gè)置換π，當(dāng)(u,v)∈E0時(shí)，(π(u),π(v))∈E1，則稱圖G0和圖G1同構(gòu)，記作G1=πG0.

協(xié)議：圖的同構(gòu)的零知識(shí)證明協(xié)議[7]

公共輸入：初始化數(shù)據(jù)：兩個(gè)圖G0(V0,E0)和G1(V1,E1)，并且G0=φ(G1)使用獨(dú)立的隨機(jī)擲幣協(xié)議執(zhí)行如下4步m輪. (1)P隨機(jī)選擇一個(gè)置換π生成圖G0的一個(gè)置換圖H，即：H=π(G0),并將H發(fā)送給V；

(2)V隨機(jī)選擇α∈{0,1}，并將α發(fā)送給P；

(3)如果α=0，P將置換π發(fā)送給V;否則，如果α≠0，P將置換π·φ-1發(fā)送給V;

(4)V驗(yàn)證H=ψ(Gα)(其中當(dāng)α=0時(shí)，ψ=π；當(dāng)α≠0時(shí)，ψ=π·φ-1)是否成立，若成立則繼續(xù)，否則，拒絕P的聲稱.

如果如上協(xié)議成功執(zhí)行了m輪，V則接受P的證明.

在上述協(xié)議中，若P確實(shí)掌握了圖G0和圖G1的同構(gòu)關(guān)系G1=φ(G0)，則對(duì)所有的置換πφ總有H=π(G0)=π(φ(G1))，又因?yàn)橹脫Qπ是隨機(jī)選擇的，所以整個(gè)過(guò)程中沒(méi)有泄露有關(guān)置換?的任何信息.又因?yàn)閂要求證明H與圖G0同構(gòu)或與圖G1同構(gòu)是隨機(jī)的，所以P只有掌握了置換φ才能或者證明(H,G0)同構(gòu)或者證明(H,G1)同構(gòu).

3.5 身份認(rèn)證中的零知識(shí)證明—F-S身份認(rèn)證協(xié)議

在密碼學(xué)中，零知識(shí)證明最早是作為實(shí)體認(rèn)證的一種方法進(jìn)行應(yīng)用的.Fiat和Shamir在1986年首先給出了這種身份認(rèn)證的零知識(shí)證明方法，也就是F-S認(rèn)證協(xié)議.F-S認(rèn)證協(xié)議一般不單獨(dú)應(yīng)用于現(xiàn)在的認(rèn)證系統(tǒng)中，但它當(dāng)今應(yīng)用的零知識(shí)證明身份認(rèn)證系統(tǒng)的基礎(chǔ)，像Feige-Fiat-Shamir和Guillou-Quisquater中，都用到了F-S認(rèn)證協(xié)議.

在F-S認(rèn)證協(xié)議中，首先找一個(gè)證明者和驗(yàn)證者兩方都信任的第三方，第三方選取兩個(gè)大的素?cái)?shù)p和q，然后計(jì)算n=p×q，其中n的值是公開的，而p和q的值是不公開的.P選取一個(gè)私鑰s(1≤s≤n-1)，接著計(jì)算v=smod n，將v作為公鑰由可信的第三方保存.V可以按照如下步驟對(duì)P進(jìn)行認(rèn)證：

協(xié)議：F—S身份認(rèn)證協(xié)議[8]

(1)P從0到n-1中隨機(jī)選取一個(gè)數(shù)r，并計(jì)算x=r2modn；

(2)P將x發(fā)送給V；

(3)V將c發(fā)送給P，其中c為0或1；

(4)P計(jì)算y=rsc，其中r是在(1)中P選取的一個(gè)隨機(jī)數(shù)，s是P的私鑰；

(5)P將y再發(fā)送給V，從而證明其知道其所聲稱的私鑰s；

(6)V計(jì)算y2modn和xvc，如果y2modn=xvc，則P或者知道s的值(P是誠(chéng)實(shí)的)或者P已經(jīng)用其他的方法計(jì)算出了y的值(P是不誠(chéng)實(shí)的)，因?yàn)?

如上六步構(gòu)成一輪，每一輪讓c為0或1，重復(fù)執(zhí)行若干輪后，P只有每一輪都通過(guò)驗(yàn)證，才能通過(guò)V的驗(yàn)證；如果在某一輪的執(zhí)行過(guò)程中，P沒(méi)有通過(guò)驗(yàn)證，則整個(gè)認(rèn)證過(guò)程終止，P沒(méi)有通過(guò)認(rèn)證.

3.6 云存儲(chǔ)中的零知識(shí)證明

由于云存儲(chǔ)能夠提供安全、可靠和實(shí)用的存儲(chǔ)服務(wù)，使得其得到更廣泛的應(yīng)用.為了得到用戶的信任，云存儲(chǔ)的服務(wù)提供商必須為用戶提供可恢復(fù)性證明POR(proof of retrievability)[9]，證明數(shù)據(jù)的完整性和安全性.

對(duì)于可恢復(fù)性證明的安全性，這里主要從如下兩點(diǎn)來(lái)進(jìn)行說(shuō)明：

(1)在認(rèn)證過(guò)程中，怎樣才能防止證明者通過(guò)篡改數(shù)據(jù)進(jìn)行欺騙？

(2)對(duì)于公開可驗(yàn)證的POR協(xié)議，如何避免在應(yīng)答的過(guò)程中惡意的驗(yàn)證者通過(guò)分析而存儲(chǔ)相關(guān)數(shù)據(jù)？

基于以上兩類安全問(wèn)題，在POR協(xié)議中，可以考慮使用零知識(shí)證明協(xié)議來(lái)完成.零知識(shí)證明的完整性和可靠性可滿足第一點(diǎn)要求，零知識(shí)證明的零知識(shí)性可滿足第二點(diǎn)要求.在文獻(xiàn)[10]中，作者所提出的零知識(shí)數(shù)據(jù)可恢復(fù)性證明協(xié)議模型，可以防止證明者欺騙或者是泄露相關(guān)的認(rèn)證數(shù)據(jù).而整個(gè)思想主要是依據(jù)雙線性映射群s=(p,G,GT,e),其中G, GT為群p中兩個(gè)有序的隨機(jī)大素?cái)?shù)，并且需要驗(yàn)證數(shù)據(jù)文件F備份到一個(gè)分區(qū)每個(gè)子塊的秘密數(shù)據(jù){mi,j}由隨機(jī)數(shù)λj∈Zp保護(hù)，{σi}由隨機(jī)數(shù)γ∈Zp保護(hù).同時(shí)，為了避免惡意驗(yàn)證者獲得{λ}和γ，證明者可以利用承諾的方法通過(guò)Hλ和

j1)來(lái)保護(hù)這些數(shù)據(jù)，其中β是屬于Zp的隨機(jī)數(shù)，h是一個(gè)防碰撞散列函數(shù)，是屬于Zp的隨機(jī)數(shù)，且i=1，…s，e為雙線性映射的群映射群系統(tǒng)[11].

4 結(jié)束

在零知識(shí)證明過(guò)程中，證明者使驗(yàn)證者相信某個(gè)斷言或定理是真實(shí)的，而除此之外，驗(yàn)證者沒(méi)有獲得有關(guān)斷言或定理的任何有用信息.零知識(shí)證明的思想是許多密碼學(xué)協(xié)議的基礎(chǔ)，在安全協(xié)議的設(shè)計(jì)中有著比較廣泛的應(yīng)用.本文在介紹零知識(shí)證明協(xié)議相關(guān)知識(shí)的基礎(chǔ)上，對(duì)零知識(shí)證明的相關(guān)應(yīng)用進(jìn)行了研究，但沒(méi)有涉及一些最近發(fā)展起來(lái)的高級(jí)課題.近年來(lái)，國(guó)內(nèi)許多學(xué)者在零知識(shí)證明理論研究方面取得了一系列國(guó)際領(lǐng)先的研究成果[12]-[14]，希望通過(guò)本文，能夠吸引更多的學(xué)者在更廣泛的領(lǐng)域?qū)α阒R(shí)證明進(jìn)行研究.

〔1〕Goldwasser S,M icali S,Rackoff C.The know ledge complexity of interactive proofsystems, Proceedingsof the17th ACM [C],Symposium on the theory ofComputing,1985:291-304.

〔2〕Goldwasser S,M icali S,Rackoff C.The know ledge complexity of interactive proof systems,SIAM J.Comput,18(1989):186-208.

〔3〕李順東，王道順．現(xiàn)代密碼學(xué)：理論、方法與研究前沿[M]．北京：科學(xué)出版社，2009.157-192.

〔4〕王育民，劉建偉.通信網(wǎng)的安全——理論與技術(shù)[M]．西安：西安電子科技大學(xué)出版社，1999.309-319.

〔5〕Ronen Gradwohl,Moni Naor,Benny Pinkas, Guy N.Rothblum.Cryptographic and Physical Zero-Know ledge Proof Systems for Solutions of Sudoku Puzzles. Theory Comput Syst (2009)44:245–268.

〔6〕李曦,王道順．多項(xiàng)式函數(shù)根的零知識(shí)證明協(xié)議[J].清華大學(xué)學(xué)報(bào)，2009, 49（7）:1015-1018.

〔7〕Oded Goldreich,Silvio M icali,Avi W igderson. Proofs that yield nothing but their validity. Journal of the ACM[C],volume 38,issue 3, July 1991:690-728.

〔8〕Feige U,Fiat A,Sham ir A.Zero-know ledge proofs of identity. Proceedings of the nineteenth annual ACM conference on Theory of computing[C],1987:210-217.

〔9〕Juels A,Kaliski-Jr B S.Pors. Proofs of retrievability for large files.Proceedings of the 2007 ACM Conference on Computer and Communications Security [C],CCS 2007. Alexandria:ACM,2007:584-597.

〔10〕Zhu y,W ang HX,Hu ZX,Ahn GJ,Hu HX.Zero-know ledge proofs of retrievability. Science China-Information Sciences[J].54(8), 2011:1608-1617.

〔11〕W Huqing,S Zhixin;Research on Zero-Know ledge Proof Protocol.IJCSI International Journal of Computer Science Issues[J],Vol. 10,Issue 1,No 1,January 2013:194-200.

〔12〕Deng Yi,Lin Dongdai.Instance-Dependent Verifiable Random Functions and Their Application to Simultaneous Resettability[C]. EUROCRYPT 2007:148-168.

〔13〕Deng Yi, Giovanni Di Crescenzo, Lin Dongdai,Feng Dengguo.Concurrently Nonmalleable Black Box Zero Know ledge in the Bare Public-Key M odel[C].CSR 2009:80-91.

〔14〕Deng Yi,Vipul Goyal,Am it Sahai.Resolving the Simultaneous Resettability Conjecture and a New Non-Black-Box Simulation Strategy [C].FOCS 2009:251-260.

TP393.08

A

1673-260X（2014）04-0006-04

2011年安徽省高校省級(jí)自然科學(xué)研究項(xiàng)目(KJ2011Z332)；2012年淮北師范大學(xué)青年科學(xué)研究項(xiàng)目（2012xq54）