8.1秘密共享與門限密碼體制

8.2零知識(shí)證明

8.3安全多方計(jì)算第8章多方密碼協(xié)議8.1秘密共享與門限密碼體制8.1.1秘密共享

1.秘密共享概述秘密共享(secretsharing)是指在多個(gè)參與方之間共享秘密s的策略，每個(gè)參與方p得到的信息S(p)是秘密的一部分，稱為一個(gè)份額或影子(share/shadow)，設(shè)P為參與方集合，則只有P的某些特定的子集集合Γ2P能利用其掌握的份額集合重構(gòu)秘密，這些子集的集合被稱為訪問結(jié)構(gòu)或存取結(jié)構(gòu)(accessstructure)。如果非授權(quán)集中的參與方無法得到秘密s的任何信息，則稱這樣的秘密共享方案為完善的(perfect)。對A∈Γ，如果A

B

P時(shí)必有B∈Γ，則稱訪問結(jié)構(gòu)Γ是單調(diào)的。此時(shí)如果令Γm表示Γ中最小元素之集，則由Γm可以確定出Γ的全部元素，稱Γm為訪問結(jié)構(gòu)Γ的基(basis)?，F(xiàn)有的秘密共享體制主要有以下幾種分類方法：

(1)按照分發(fā)份額及重構(gòu)秘密時(shí)有無可信任的仲裁者參與，分為有仲裁的秘密共享和無仲裁的秘密共享；

(2)按照參與方的非授權(quán)子集是否能得到秘密的部分信息，分為完善秘密共享和非完善秘密共享，或理論安全和計(jì)算安全的秘密共享；

(3)按照秘密的數(shù)量，可分為單個(gè)秘密共享和多重秘密共享；

(4)按照有無驗(yàn)證機(jī)制，可分為可驗(yàn)證的秘密共享和不可驗(yàn)證的秘密共享。除此之外，人們還根據(jù)不同的應(yīng)用需求而有針對性地設(shè)計(jì)了許多其它秘密共享方法，這里不再一一列舉。

秘密共享技術(shù)實(shí)現(xiàn)了“不把雞蛋放在同一個(gè)籃子里”的目的，從而當(dāng)某個(gè)參與者實(shí)施欺騙或者其手中的份額丟失時(shí)，仍可恢復(fù)秘密，這實(shí)際上是通過引入冗余來提高數(shù)據(jù)服務(wù)的可靠性。同時(shí)，大多數(shù)秘密共享還可以實(shí)現(xiàn)無條件的安全性，即其安全性不是建立在某個(gè)計(jì)算上困難的問題之上，而是可以從Shannon信息論的角度證明無信息泄露，即使攻擊者有無限的計(jì)算資源和時(shí)間，也無法得到秘密的任何信息。秘密共享因?yàn)樯鲜鰞?yōu)點(diǎn)而在國內(nèi)外得到了非常廣泛的研究和關(guān)注，主要有以下幾方面的研究工作。

1)對一般形式的訪問結(jié)構(gòu)構(gòu)造秘密共享方案

在秘密共享方面最早的研究是(k,n)門限方案的構(gòu)造，后來人們開始關(guān)注更為通用的方案，Saito和Nishizeki證明了對任意的訪問結(jié)構(gòu)，均存在可以實(shí)現(xiàn)它的秘密共享方案［3］。Benaloh和Leichterr提出了更為簡單和有效的秘密共享方案，可以在任何單調(diào)訪問結(jié)構(gòu)中實(shí)現(xiàn)［4］。

2)秘密共享的效率

算法的效率主要用計(jì)算量和占用的存儲(chǔ)空間來衡量。在現(xiàn)有的線性門限方案中，份額計(jì)算和秘密重構(gòu)算法均為多項(xiàng)式時(shí)間復(fù)雜度，因而份額長度成為影響效率的關(guān)鍵因素。秘密共享實(shí)際上是一種冗余機(jī)制，在實(shí)際應(yīng)用中，為了提高安全性，同時(shí)降低存儲(chǔ)量，秘密份額的長度應(yīng)盡量小，人們提出了許多方法使份額的長度保持在適當(dāng)范圍內(nèi)。秘密共享方案Λ的一個(gè)重要參數(shù)是其信息率(informationrate)。信息率ρ(Δ,Γ,S)定義為共享秘密的長度與份額的最大長度之比：

這里,S為所有可能的秘密集合。如果ρ(Λ)=1，則稱Λ為理想的(ideal)秘密共享方案，通常ρ(Λ)≤1。

設(shè)Γ為訪問結(jié)構(gòu)，如果存在一個(gè)理想的秘密共享方案能實(shí)現(xiàn)Γ，則稱Γ是理想的訪問結(jié)構(gòu)。在(k,n)門限方案中，份額與秘密具有相同規(guī)模，然而在對一般訪問結(jié)構(gòu)構(gòu)造的方案中，份額長度通常大于秘密長度。以下例子給出了一個(gè)簡單的理想秘密共享方案［5］。

例8-1

設(shè)秘密空間與份額空間均為GF(3)，參與者集合為{a,b,c}，訪問結(jié)構(gòu)Γ={{a,b},{b,c},{a,b,c}}。構(gòu)造秘密共享方案如表8-1所示。表中，D為原始秘密；Sa,Sb,Sc分別為a,b,c的份額。注意到在每行中，D=Sa－Sb=Sb－Sc，然而由于每行的Sa與Sc均相等，因此a與c組合將得不到D的任何信息。構(gòu)造理想的秘密共享方案是秘密共享方面的重要研究課題，后面介紹的Balkley方案和Shamir門限方案均為理想的秘密共享體制。除此之外，這方面還有許多文獻(xiàn)［6-7］。參考文獻(xiàn)［6］中利用向量空間構(gòu)造證明了判定理想訪問結(jié)構(gòu)的充分條件；參考文獻(xiàn)［7］中則利用擬陣的方法給出了必要條件。

對于任意給定的訪問結(jié)構(gòu)，尋找理想的秘密共享方案是不太現(xiàn)實(shí)的，因而人們只能試圖找到使信息率盡可能大的方案。訪問結(jié)構(gòu)Γ的最佳信息率(optimalinformationrate)定義為

ρ*(Γ)＝sup(ρ(Λ,Γ,S))

這里,sup()是指對所有可能的秘密集合|S|≥2和所有能實(shí)現(xiàn)Γ的秘密共享方案Λ求極大值。顯然，理想的訪問結(jié)構(gòu)的最佳信息率為1。尋找任意訪問結(jié)構(gòu)的最佳信息率，并求出其上、下界也是一個(gè)尚未解決的重要研究內(nèi)容。

為了減少秘密份額的長度，人們將秘密共享與其它技術(shù)相結(jié)合，構(gòu)造了一些新的方案，如Rabin的IDA(InformationDispersalAlgorithm)［8］和Krawczyk的“短”秘密共享方案［9］(將在8.1.2節(jié)介紹)。

3)安全性

秘密共享中的不安全因素包括：某個(gè)合法參與者拒絕提供份額而無法恢復(fù)秘密；非授權(quán)成員偽裝為合法成員騙取秘密份額以及仲裁者分發(fā)給參與者錯(cuò)誤份額，等等。針對不同安全問題，人們提出了不同的解決方法。比如構(gòu)造完善的秘密共享方案，使得非授權(quán)的參與方集合無法得到秘密的任何信息；對現(xiàn)有的門限方案進(jìn)行改進(jìn)，使其具有預(yù)防欺騙的功能；在分發(fā)秘密份額時(shí)加入仲裁者的簽名信息，等等。8.1.2節(jié)將詳細(xì)討論如何在門限方案中防止欺騙。

4)應(yīng)用

在應(yīng)用方面，一個(gè)典型的例子是門限數(shù)字簽名。門限簽名是群簽名的一種，在群簽名中，通過設(shè)計(jì)適當(dāng)?shù)膮f(xié)議，可以使群中的某個(gè)成員代表整個(gè)群體進(jìn)行簽名，而門限簽名則要求群中參與簽名的人數(shù)必須大于某個(gè)門限值，從而防止個(gè)別不誠實(shí)的參與方進(jìn)行欺騙。門限簽名可以用秘密共享技術(shù)實(shí)現(xiàn)。除此之外，秘密共享還在信息系統(tǒng)可生存性研究及數(shù)據(jù)的分布式存儲(chǔ)中有著重要應(yīng)用。

2.(k,n)門限方案

(k,n)門限方案是一類特殊的秘密共享方案，Shamir和Blakley于1979年各自獨(dú)立地提出了門限方案的思想，并采用不同方法將之實(shí)現(xiàn)［10-11］。在(k,n)門限方案中，n表示參與方個(gè)數(shù)，k表示要重構(gòu)秘密需要的最少份額數(shù)，其訪問結(jié)構(gòu)是所有k元素子集構(gòu)成的集合。門限方案是理想的秘密共享方案。

定義8-1

設(shè)D為取自有限集S的某一秘密數(shù)據(jù)，又設(shè)n個(gè)參與者各自擁有份額Di，Di∈S，i=1,2,…,n。集合稱為一個(gè)(k,n)門限方案，如果以下兩個(gè)條件成立：

(1)利用任意k個(gè)不同的份額均可容易地求得D，從Shannon信息論的角度，即

(2)利用任意小于k個(gè)不同的份額都無法有效地求得D，即

門限方案可以寫成更一般的形式，即(t,k,n)門限方案，其中任意k個(gè)不同的份額可以容易地重構(gòu)秘密，而當(dāng)份額數(shù)量不大于t時(shí)，將得不到關(guān)于秘密D的任何信息?，F(xiàn)有的方案中，一般令k=t+1。

(k,n)門限方案可以利用不同領(lǐng)域的數(shù)學(xué)知識(shí)來構(gòu)造，其中比較著名的有Shamir的基于有限域上的拉格朗日插值多項(xiàng)式方案［10］、McEliece的基于Reed-Solomon碼的門限方案［12］、基于中國剩余定理的Asmuth-Bloom方案［13］、利用超平面構(gòu)造的Blakley方案［11］以及Karnin-Greene-Hellman方案［14］，等等。Kothari證明了上述五種方案均可看做一般線性門限體制的某種特例［15］，他還使用線性幾何的概念，給出了一般線性門限體制的定義。下面我們一一介紹這些方案。

1)Shamir的插值多項(xiàng)式構(gòu)造方案

設(shè)q為素?cái)?shù)的冪，α是有限域GF(q)中的本原元，設(shè)要共享的秘密為D∈GF(q)，隨機(jī)選取GF(q)上的k－1次多項(xiàng)式f(x),使得

f(x)=D+a1x+a2x2+…+ak－1xk－1

其中,ai∈GF(q)，i=1,2,…,k－1，且ak－1≠0。對n個(gè)互不相同的αi，i=1,2,…,n，計(jì)算di=f(αi)，則集合即構(gòu)成一個(gè)(k,n)門限方案。

證明：假設(shè)k個(gè)參與者提供了k個(gè)份額di，i=1,2,…,k，則根據(jù)拉格朗日插值公式，有

進(jìn)而得到f(x)的常數(shù)項(xiàng)，即秘密D=f(0)，并且每個(gè)參與者αi均可利用自己掌握的份額di來驗(yàn)證所求得的f(x)是否正確，從而可以發(fā)現(xiàn)其它參與方的欺騙行為。另一方面，當(dāng)份額數(shù)量r<k時(shí)，要確定k－1次多項(xiàng)式f(x)的全部系數(shù)，必須另外找到k－r個(gè)插值點(diǎn)，這需要在有限域GF(q)中窮盡搜索qk－r次，從而存在qk－r個(gè)多項(xiàng)式f(x)滿足f(αi)=di，i=1,2,…,r，因而確定秘密數(shù)據(jù)D的取值成為一個(gè)計(jì)算上困難的問題。

Shamir指出這種方案具有以下特點(diǎn)：

(1)在參與者集合中成員總數(shù)不超過q的條件下可以增加新成員，即計(jì)算新的秘密份額不會(huì)改變已有的秘密份額；

(2)通過選用常數(shù)項(xiàng)不變的另一個(gè)新的k－1次多項(xiàng)式，可以撤銷舊的秘密份額；

(3)可以根據(jù)成員的重要性分給不同個(gè)數(shù)的份額，實(shí)現(xiàn)分級的秘密共享；

(4)恢復(fù)秘密S的算法是多項(xiàng)式時(shí)間的，其時(shí)間復(fù)雜度為O(t3)。

2)McElice方案

McElice方案是多項(xiàng)式插值方案的變種，主要解決由于部分參與者的欺騙而無法重構(gòu)數(shù)據(jù)的情形。

設(shè)碼長為n，能糾正t個(gè)錯(cuò)誤的Reed-Solomon(RS)碼的碼字為(d1,d2,…,dn)，則集合構(gòu)成一個(gè)(k,n)門限方案。如果有m個(gè)參與者提供份額，但其中有t個(gè)是錯(cuò)誤的，則當(dāng)m≥k+2t時(shí)，仍可以正確恢復(fù)秘密信息。McEliece方案利用RS碼的糾錯(cuò)能力來消除錯(cuò)誤份額的影響。

引理8-1

設(shè)碼長為n的分組碼的最小距離為d，則當(dāng)d≥2t+r+1時(shí)，可以同時(shí)糾正t位錯(cuò)誤和r位刪除。

定理8-1

設(shè)q為素?cái)?shù)的冪，n=q－1，記GF(q)的全部非零元為α1,α2,…,αn，設(shè)D∈GF(q)為秘密數(shù)據(jù)，定義k－1次多項(xiàng)式f(x)為

f(x)=D+a1x+a2x2+…+ak－1xk－1令di=f(αi)，則集合構(gòu)成一個(gè)(k,n)門限方案。如果有m個(gè)參與者提供了其掌握的份額

，其中有t個(gè)

，則只要m≥k+2t，便能容易地求出秘密數(shù)據(jù)D。

證明：事實(shí)上，矢量(d1,d2,…,dn)構(gòu)成Reed-Solomon碼的一個(gè)碼字，其碼長為n，維數(shù)為k，最小距離d=n－k+1。由引理8-1知，當(dāng)n－k≥2t+r時(shí)可以同時(shí)糾正t位錯(cuò)誤和r位刪除。如果將n－m個(gè)未知份額視為r=n－m個(gè)刪除，于是n－k≥2t+r等價(jià)于n－k≥n－m+2t，即m≥k+2t。因此，存在有效的譯碼算法，譯碼的結(jié)果即為(d1,d2,…,dn)，并能查出錯(cuò)誤數(shù)

據(jù)

，秘密數(shù)據(jù)D則可通過計(jì)算而求得，即

3)Asmuth-Bloom方案

Asmuth等提出了基于中國剩余定理的(k,n)門限方案，該方案的詳細(xì)描述如下所述。

選取大素?cái)?shù)p，正整數(shù)Q，n個(gè)正整數(shù)mi(i=1,…,n)，滿足以下條件：

(1)p>Q；

(2)m1<m2<…<mn且當(dāng)i≠j時(shí)，(mi,mj)=1；

(3)對i，(p,mi)=1；

(4)令N=m1…mk，且大于任取的k－1個(gè)不同mi之積，由于m1,m2,…,mn按增序排列，故N>p·mn－k+2mn－k+3…mn。

對于i=1,…,n，令Mi=M/mi，且設(shè)是Mimodmi的逆，則。由于(Mi,mi)=1，因此這個(gè)逆存在而且可以用Euclid算法求出。由中國剩余定理可知，同余方程組x≡aimodmi，i=1,…,n，有解

，并且在模M的意義上，該解是唯一的，這里0≤ai＜mi，i=1,…,n。隨機(jī)選取正整數(shù)，定義秘密數(shù)據(jù)為

D=Q+rp，且D<N。令ai=(Dmodmi)，i=1,…,n，則有定理8-2。

定理8-2

集合{(mi,ai)}ni=1構(gòu)成關(guān)于秘密D的一個(gè)(k,n)門限方案。

證明：假設(shè)k個(gè)參與者提供的份額為(mi1,ai1),…,(mik,aik),令M=mi1…mik，Mj=M/mij，i=1,…,k，而且設(shè)是

Mjmodmij的逆。定義

，由中國剩余定理求得y≡DmodM，因?yàn)镈<N，故D=ymodM。這說明利用(mi1,ai1),…,(mik,aik)可以重構(gòu)D。另一方面，若只有k－1個(gè)參與者，則只能求得D′≡DmodN′，其中N′為k－1個(gè)模數(shù)mi的乘積，由條件(4)得

。

因?yàn)?N′,p)=1，而根據(jù)以上討論得，故方程ymodN′=D′的解不唯一。事實(shí)上，y的取值將在modp的所有同余類中均勻分布，因此無法確定D。

4)Blakley方案

設(shè)參與者為Ai，i=1,2,…,n，仲裁者為D，V為GF(q)上的k維向量，其中q為素?cái)?shù)冪。Blakley構(gòu)造的(k,n)門限方案包含以下步驟：

(1)D固定V中的一條線l，將其對所有參與者公開，而l上的所有q個(gè)點(diǎn)即為q個(gè)可能的秘密值；

(2)設(shè)秘密為p，D首先隨機(jī)地構(gòu)造k－1維子空間H，H與l相交于某個(gè)點(diǎn)，然后D構(gòu)造超平面Hp=H+p，注意Hp∩l=p；

(3)D在Hp中隨機(jī)選擇n個(gè)點(diǎn)si，i=1,2,…,n，使得集合{p}∪{si：i=1,2,…,n}中的任意j(j≤k)個(gè)不會(huì)位于同一個(gè)j－2維超平面中；

(4)D將si作為秘密份額分發(fā)給Ai，i=1,2,…,n。

假設(shè)有k個(gè)參與者提供了份額，則可以唯一地確定超平面Hp，再通過計(jì)算Hp∩l就能得到原始秘密p。然而任意k′(k′<k)個(gè)參與者只能由其份額構(gòu)造出k′－1維超平面F，且F包含在Hp中，對于l中的任意一個(gè)點(diǎn)p′，存在超平面Hp′同時(shí)包含了F和p′，因此k′個(gè)參與者將得不到p的任何信息。

5)Karnin-Greene-Hellman方案

Karnin等利用有限域GF(q)中的矩陣運(yùn)算構(gòu)造了一類門限方案［14］，并證明了Shamir和Blakley的方案是這種方案的特例。

設(shè)正整數(shù)n=km，k>1。隨機(jī)選取n維行矢量u=(u1,u2,…,un)，求出n+1個(gè)n×m階矩陣A0,A1,…,An，要求其中任意k個(gè)拼成的n×n階矩陣B滿足:

為滿秩矩陣。將秘密數(shù)據(jù)表示為m維矢量d=uA0，每個(gè)用戶的秘密份額為di=uAi，i=1,2,…,n，A0為公用信息，于是構(gòu)成一個(gè)(k,n)門限方案。

當(dāng)k個(gè)參與者提供了秘密份額

時(shí)，構(gòu)造未知量為u的方程組如下：

(8-1)由于n=km，因此可將式(8-1)改寫為

(8-2)這個(gè)方程組有n個(gè)未知量u1,u2,…，un，其系數(shù)矩陣為滿秩矩陣，存在唯一的解，即u=(u1,u2,…,un)。于是可以得到秘密信息d=uA0。

當(dāng)份額數(shù)量小于k時(shí)，將無法構(gòu)造具有唯一解u的方程組，即式(8-2)，因而無法確定秘密數(shù)據(jù)d。

6)一般線性門限方案

Kothari對上述幾種方案進(jìn)行了概括，提出一般線性門限體制的構(gòu)造。

以下將GF(q)n視為有限域GF(q)上的線性空間。

定義8-2

設(shè)S

GF(q)n，如果存在n個(gè)變元的線性函數(shù)集合fi(x1,x2,…,xn)，i=1,2,…,m，使得

S={(a1,a2,…,an)∈GF(q)n|f

i(a1,a2,…,an)=0,i=1,2,…,m}

則稱S為GF(q)n的一個(gè)線性變量。

定義8-3

給定線性變量S，定義

則E(S)為GF(q)n的子空間。

定義8-4

若S為GF(q)n中的線性變量，dim(E(S))=1，則稱S為超平面。其中dim(E(S))表示矢量空間E(S)的維數(shù)。

定理8-3(對偶原理)

設(shè)V為GF(q)上的n維矢量空間，為V中的線性函數(shù)集合，則也構(gòu)成一個(gè)n維矢量空間，稱為V的對偶空間。

定理8-4

設(shè)V為有限域GF(q)上的n維矢量空間，給定矢量v∈V，a∈GF(q)，定義H(v,a)={L∈

|L(V)=a}，則H(v,a)構(gòu)成上的超平面。類似地，設(shè)f為線性函數(shù)，定義

H(f,a)={v∈V|f(v)=a}，則H(f,a)構(gòu)成V上的超平面。一般線性(k,n)門限方案的構(gòu)造如下：

設(shè)V為d+k維矢量空間，S為GF(q)n中的d維線性變量，秘密數(shù)據(jù)α則為S中的標(biāo)量。選擇線性函數(shù)f，使得對v∈S，f(v)=α。將線性變量S保密，函數(shù)f對所有的參與者公開。

選擇n個(gè)超平面H(f,α)表示n個(gè)秘密份額，且其中任意k個(gè)的交集為S。

給定任意k個(gè)份額，則秘密S可以通過計(jì)算超平面的交集來恢復(fù)。若已知的份額數(shù)量小于k，則計(jì)算出的交集為線性變量S′，S

S′。并且可以證明，由S′得不到關(guān)于S的任何信息［15］。8.1.2門限方案的變體

針對不同的應(yīng)用需求，人們對上述的各種門限方案進(jìn)行改進(jìn)，提出了多種門限方案的變體。包括為了提高安全性而設(shè)計(jì)的不暴露秘密的秘密共享、防止欺騙的可證實(shí)秘密共享、為提高效率而設(shè)計(jì)的IDA和“短”秘密共享以及更為靈活的多重秘密共享。以下著重討論可預(yù)防欺騙的秘密共享以及為減少存儲(chǔ)量而設(shè)計(jì)的“短”秘密共享。

1.有騙子的秘密共享體制(secretsharingschemewith

cheaters)

秘密共享體制中的參與者可能實(shí)施欺騙，如故意傳來錯(cuò)誤份額。在有仲裁的秘密共享體制中，仲裁者本身也有進(jìn)行欺騙的可能，使得由不同的k個(gè)份額恢復(fù)的秘密也不相同。如果欺騙是單個(gè)參與者的行為，則稱為破壞(disruption)；如果是多個(gè)參與者聯(lián)合起來進(jìn)行欺騙，則稱為共謀(collusion)。對于參與者的破壞或共謀攻擊，通過構(gòu)造安全性較強(qiáng)的方案或?yàn)槊總€(gè)份額加入數(shù)字簽名等方法，可以檢測出錯(cuò)誤份額。8.1.1節(jié)的McEliece方案是具有糾錯(cuò)能力的門限方案。此外還有一些改進(jìn)方案，可以在不暴露秘密的情況下揭露騙子。Tompa和Woll［19］、Simmons［20］、Chaum等對此進(jìn)行了研究。Chor［21］和Benaloh［22］等則討論了如何預(yù)防仲裁者的欺騙。下面用Shamir方案來說明參與者的欺騙行為及Tompa和Woll提供的應(yīng)對措施。

假設(shè)k個(gè)參與者i1,i2,…,ik參與重構(gòu)秘密，其中i1決定欺騙。欺騙步驟如下：

(1)i1構(gòu)造k－1次多項(xiàng)式Δ(x)，使得Δ(0)=－1，Δ(i2)=Δ(i3)=…=Δ(ik)=0，這樣的Δ(x)可以很容易地用Lagrange插值公式構(gòu)造；

(2)i1將自己的份額

改為

；

(3)利用k個(gè)份額執(zhí)行重構(gòu)算法，得到多項(xiàng)式f(x)+Δ(x)，其常數(shù)項(xiàng)f(0)+Δ(0)=D－1被認(rèn)為是原始秘密。

除非原始秘密D=0，否則這樣的欺騙行為將不會(huì)被其他參與者察覺。

為了避免上述情形，需要對(k,n)門限方案作一些強(qiáng)化。首先，給定義8-1中的(k,n)門限方案增加一個(gè)條件(3)：只有很小的概率可以從任意k個(gè)份額(其中有k-1個(gè)是偽造的)中得到合法但卻是錯(cuò)誤的秘密D′，D′∈S且D′≠D。

Tompa和Woll構(gòu)造了一種改進(jìn)的(k,n)門限方案，可以防止參與者的欺騙行為。這種方案可以在任何一種門限方案中實(shí)施，下面僅給出了其在Shamir方案中的實(shí)例。設(shè)秘密數(shù)據(jù)在整數(shù)(1,2,…,s)中選擇，ε>0，改進(jìn)的Shamir方案如下：

(1)選擇一個(gè)素?cái)?shù)p，

；

(2)在Zp中隨機(jī)、均勻、獨(dú)立地選擇a1,a2,…,ak－1，構(gòu)造k－1次多項(xiàng)式f(x),使得

f(x)=D+a1x+a2x2+…+ak－1xk－1

(3)隨機(jī)、均勻地選擇x1,x2,…,xn∈{1,2,…,p－1}，令di=f(xi)，Di=(xi,di)，i=1,2,…,n，則Di即為各個(gè)秘密份額。

使用上述方案共享秘密時(shí)，成功欺騙的概率將小于ε。

可以證明，這種方案滿足(k,n)門限方案的條件(1)、(2)和(3)。證明：

(1)由于x1,x2,…,xn各不相同，所以任意k個(gè)參與者可以利用插值定理成功恢復(fù)秘密。

(2)假設(shè)有k－1個(gè)參與者i1,i2,…,ik－1要恢復(fù)秘密，當(dāng)原始秘密D和隨機(jī)數(shù)x1,x2,…,xk－1的值固定時(shí)，f(i1),f(i2),…,f(ik－1)是隨機(jī)變量a1,a2,…,ak－1的函數(shù)。由于a1,a2,…,ak－1互相

獨(dú)立，因此利用插值定理直接可證f(i1),f(i2),…,f(ik－1)是均勻分布且相互獨(dú)立的，從而秘密份額不能提供關(guān)于D的任何信息。

(3)下面我們將要證明，在改進(jìn)的Shamir方案中，即使k－1個(gè)欺騙者已經(jīng)知道了f(x)，或者說，即使欺騙者已經(jīng)得到了原始秘密D，條件(3)仍然成立。假設(shè)i1,i2,…,ik－1為k－1個(gè)欺騙者，偽造了份額，

而參與者ik提供了正確份額。對于每個(gè)可能的秘密值D′∈{0,1,…,s}，均存在k－1次多項(xiàng)式fD′(x)，滿足fD′(0)=D′且，j=1,2,…,k－1。若D′≠D，則這樣的多項(xiàng)式fD′(x)與f(x)在最多k－1個(gè)點(diǎn)取值相同，因而當(dāng)且僅當(dāng)

且D′≠D時(shí)，參與者ik才能通過重構(gòu)算法得到D′。因?yàn)槭窃?/p>

中隨機(jī)取值的，對任意

D′≠D，

的概率不超過。共有s－1個(gè)錯(cuò)誤但合法的秘密D′，所以偽造的份額能提供s－1個(gè)多項(xiàng)式，而這些多項(xiàng)式中任意一個(gè)能成功欺騙參與者ik的概率最多為，總的成功欺騙概率則為。通過以上討論可以看到，改進(jìn)的(k,n)門限方案在不增加系統(tǒng)計(jì)算代價(jià)的同時(shí)，可以有效地預(yù)防系統(tǒng)中的欺騙。

上述改進(jìn)的門限方案以及McEliece方案均能檢測出欺騙并正確恢復(fù)秘密，然而合法的參與者只能檢測到欺騙，無法確定哪些參與者是騙子，Brickell和Stinson的方案則可以確定哪些參與者是騙子，詳見參考文獻(xiàn)［23］。

2.“短”秘密共享

份額的長度直接影響著秘密共享體制的效率，在所有的完善秘密共享方案中，份額的長度不能小于原始秘密的長度。此外，還存在著一些訪問結(jié)構(gòu)，使得在其中實(shí)現(xiàn)的任何秘密共享方案中份額長度必須大于秘密長度［4］。有關(guān)份額長度的討論可分為兩類，一類是從理論安全的角度出發(fā)，用信息論方法證明份額長度的下界；另一類則是從計(jì)算安全的角度設(shè)計(jì)有實(shí)用價(jià)值的算法，使份額長度盡量小。本節(jié)重點(diǎn)介紹后一種。

Rabin提出了一種實(shí)用的信息分散算法IDA(InformationDispersalAlgorithm)［8］。IDA以容錯(cuò)為出發(fā)點(diǎn)，其基本思路是將秘密信息D分解為n個(gè)片段(segments)D1,D2,…,Dn，送入n個(gè)服務(wù)器保存，n個(gè)服務(wù)器中的任意k個(gè)可以重構(gòu)D，當(dāng)系統(tǒng)中有t個(gè)服務(wù)器無法工作時(shí)，仍然能夠恢復(fù)信息。IDA中每個(gè)份額的長度為，總的存儲(chǔ)量為。

設(shè)p為素?cái)?shù)，原始數(shù)據(jù)為GF(p)上的串D=d1d2…dN,di∈GF(p)，i=1,2,…,N。IDA的份額計(jì)算過程如下：

(1)選擇整數(shù)k，使得n=k+m且；

(2)選擇GF(p)中的n個(gè)k維向量ai=(ai1，ai2，…,aik),i=1,2,…,n,其中任意k個(gè)向量線性無關(guān)；

(3)將D分成長度為k的片段:

D=(d1…dk)(dk+1…d2k)…

記S1=(d1…dk)，對i=1,2,…,n，計(jì)算

其中,cij=ai·Sj=ai1d

(j－1)k+1+ai2d(j－1)k+2+…+aikdjk。這里Di(i=1,2,…,n)即為n個(gè)份額。假設(shè)有k個(gè)參與者提供了份額，不妨設(shè)其為D1,…,Dk，則可按如下方法重構(gòu)秘密：

構(gòu)造k×k階矩陣A=(aij)1≤i,j≤k，即A以向量ai作為第i行，易知

從而

若將A－1的第i行記作(ai1,ai2,…,aik)，則對，有

dj=ai1c1r+…+aikckr

j=1,2,…,N

這樣就恢復(fù)了原始數(shù)據(jù)D。當(dāng)k較大時(shí)，求矩陣A的逆是比較復(fù)雜的，但可以通過適當(dāng)?shù)剡x擇行向量，使計(jì)算A－1的時(shí)間復(fù)雜度保持在O(k2)。同時(shí)，在需要多次重構(gòu)秘密時(shí)，只計(jì)算一次A－1即可。

1993年，Krawczyk在IDA的基礎(chǔ)上，將加密與門限技術(shù)相結(jié)合，提出了“短”秘密共享方案［9］。該方案采用隨機(jī)密鑰加密信息，再用一般的門限方案保存隨機(jī)密鑰，并將密文用IDA方案處理。設(shè)秘密為S，利用該方案計(jì)算出的各份額長度為

，其中a為與|S|無關(guān)的安全參數(shù)。在介紹Krawczyk的方案之前，首先給出幾個(gè)定義。

定義8-5

設(shè)ENC為對稱加密算法，M為一個(gè)明文，{ENCK(M)}K表示對M用所有可能的密鑰加密后的密文集合，DENC(M)表示對M用不同密鑰加密后的密文在{ENCK(M)}K中的概率分布。如果對任意一對長度相同的明文M和M′，概率分布DENC(M)與DENC(M′)是多項(xiàng)式不可區(qū)分的，那么稱對稱密碼體制ENC是安全的。

定義8-6

設(shè)CSS為一個(gè)(k,n)門限方案，對任意秘密S及下標(biāo)集合1≤i1≤…≤ir≤n，1≤r≤n，用DCSS(S,i1,i2,…,ir)表示CSS(S)的輸出在份額集合中的概率分布。如果對任意一對長度相同的秘密S和S′及下標(biāo)集合i1,i2,…,ir，概率分布DCSS(S,i1,i2,…,ir)與DCSS(S′,i1,i2,…,ir)是多項(xiàng)式不可區(qū)分的，那么稱門限方案CSS是計(jì)算安全的。

設(shè)ENC為對稱加密算法，S為原始秘密，PSS為一個(gè)完善秘密共享方案(如Shamir方案)，

Krawczyk方案的秘密分配過程如下：

(1)選擇隨機(jī)加密密鑰K，用ENC對S加密，密文E=ENCK(S)；

(2)利用IDA將E分割為n個(gè)片段E1,E2,…,En；

(3)利用PSS生成密鑰K的n個(gè)份額K1,K2,…,Kn；

(4)將Si=(Ei,Ki)，i=1,2,…,n，傳送給參與者Pi,作為秘密份額，其中Ki是通過秘密渠道(如采用加密手段)傳遞的。秘密重構(gòu)算法如下：

(1)收集k個(gè)參與者

的份額；

(2)利用IDA由(j=1,2,…,k)重構(gòu)E；

(3)利用PSS由(j=1,2,…,k)重構(gòu)密鑰K；

(4)用K和ENC對E解密，得到S。

定理8-5

當(dāng)ENC是安全加密體制,且PSS是完善秘密共享算法時(shí)，上述算法構(gòu)成一個(gè)計(jì)算安全的(k,n)門限方案，每個(gè)份額的長度為。

證明:IDA及PSS的使用保證了能夠正確重構(gòu)E和K，而由E和K通過解密直接可以得到S，所以該方案構(gòu)成一個(gè)(k,n)門限體制。份額長度根據(jù)IDA也可以直接證明，因而只需利用形式化方法證明該方案是計(jì)算安全的即可。假設(shè)存在一對長度相同的秘密S和S′，存在算法A可以以不可忽略的優(yōu)勢區(qū)分S與S′的份額空間，我們構(gòu)造算法B，能夠攻破加密體制ENC。

首先，B的輸入為對S或S′加密后的密文，設(shè)其為E，然后利用IDA生成E的n個(gè)片段E1,E2,…,En，再根據(jù)概率分布隨機(jī)生成k－1個(gè)密鑰份額，將這些份額及片段E1,E2,…,En作為A的輸入。A猜測E是對S或S′加密后的密文，輸出猜測結(jié)果，B也輸出這個(gè)結(jié)果。由于A能以不可忽略的優(yōu)勢區(qū)分S與S′的份額空間，因而正確猜測的概率大于1/2，從而B也能以同樣的概率猜測成功，這說明B能得到正確的密鑰，進(jìn)而攻破了ENC。除了上面所討論的方案，門限方案還有以下幾種類型的變體：

(1)無仲裁參與的秘密共享體制(secretsharingwithouttrend)。詳見參考文獻(xiàn)［24］。

(2)不泄露份額的秘密共享體制(sharingasecretwithoutrevealingtheshare)。

在一般的門限方案中，k個(gè)參與者在重構(gòu)秘密的同時(shí)，每人也知道了原始秘密，為了避免這一點(diǎn)，可以設(shè)計(jì)特殊的算法。如果共享秘密是私鑰，那么n個(gè)參與方中的每一個(gè)都可以完成一部分簽名，在第k部分簽名后，文件已經(jīng)用私鑰簽名了，并且參與者中沒有人了解秘密。這樣，構(gòu)造的方案可以重復(fù)使用份額。詳見參考文獻(xiàn)［25］。

(3)可證實(shí)的秘密共享體制(verifiablesecretsharing)。在有仲裁的秘密共享體制中，仲裁者分發(fā)給每個(gè)參與者的份額是否有效，要等到合格子集成員一起重構(gòu)出秘密后才能證實(shí)，可證實(shí)秘密共享則允許每個(gè)成員能夠在不重構(gòu)秘密時(shí)證實(shí)所得到的份額是否有效。詳見參考文獻(xiàn)［26-27］。

(4)可阻止恢復(fù)秘密的秘密共享體制(secretsharingschemeswithprevention)。這種門限方案中任意k個(gè)份額可以恢復(fù)秘密，而m>k個(gè)參與者能阻止秘密的恢復(fù)。Beutelspacher為這種應(yīng)用提出了解決方法：為每個(gè)參與者分發(fā)兩種份額，一種為“是”；另一種為“否”。當(dāng)決定是否能恢復(fù)秘密時(shí)，參與者可以采取投票方式，當(dāng)且僅當(dāng)“是”的個(gè)數(shù)多于k，且“否”的個(gè)數(shù)少于m時(shí)，可以重構(gòu)秘密［28］。

(5)可除名的秘密共享體制(secretsharingwithdisenrollment)。當(dāng)某個(gè)參與者已不能信賴時(shí)，可以將其掌握的份額吊銷，從而將參與者減少為n－1人。詳見參考文獻(xiàn)［29］。

(6)多重秘密共享體制(multithresholdschemes)。

在一組參與者中共享多個(gè)秘密，每個(gè)秘密可以按所設(shè)計(jì)的參與者子集進(jìn)行重構(gòu)。詳見參考文獻(xiàn)［30-31］等。8.1.3秘密共享的應(yīng)用

隨著研究的逐漸深入，秘密共享已成為密碼學(xué)中的一個(gè)重要分支。1987年，Desmedt提出了門限密碼體制的概念［32］。門限密碼體制有著廣泛的應(yīng)用背景，比如在分布式證明、群簽名、容錯(cuò)以及信息系統(tǒng)的可生存性方面都起著關(guān)鍵作用。

1.門限數(shù)字簽名

門限簽名體制由Desmedt和Frankel于1991年首次提出［33］。門限簽名是群簽名的一種。(k,n)門限群簽名是指在有n個(gè)參與方的群體中，任意k個(gè)參與方合作可以生成代表整個(gè)群的有效簽名。作為(k,n)門限方案的典型應(yīng)用，門限簽名可以在不暴露秘密密鑰的情況下對消息進(jìn)行簽名，因而得到了廣泛的研究。人們提出了許多門限群簽名方案，詳見參考文獻(xiàn)［34-40］等?，F(xiàn)有的門限群簽名體制可進(jìn)行如下分類［38］：

(1)根據(jù)數(shù)學(xué)基礎(chǔ)，可分為基于大整數(shù)分解問題與基于離散對數(shù)問題的簽名體制；

(2)根據(jù)是否可以追查簽名者身份，可分為可以追查簽名者或不能追查簽名者的簽名體制；

(3)根據(jù)系統(tǒng)構(gòu)造，可分為有仲裁者和無仲裁者的簽名體制以及交互式和非交互式的簽名體制。王貴林等［36］指出，性能良好的群簽名體制應(yīng)具有如下特點(diǎn)：

(1)群簽名特性：只有群體中的成員才可以生成有效的部分簽名，非群成員無法偽造有效的部分簽名；

(2)門限特性：只有當(dāng)簽名人數(shù)不少于門限時(shí)，才可以產(chǎn)生出有效的門限群簽名；

(3)防冒充性：任何小組不能假冒其它小組生成群簽名；

(4)簽名驗(yàn)證的簡單性：簽名的驗(yàn)證者可以方便而簡單地驗(yàn)證簽名是否有效；

(5)匿名性：簽名的驗(yàn)證者不知道該簽名是由群中哪些成員簽署的；

(6)身份的可追查性：發(fā)生糾紛時(shí)，可以追查出簽名者的身份；

(7)健壯性：惡意成員大于等于門限時(shí)仍然無法獲取系統(tǒng)秘密參數(shù)；

(8)系統(tǒng)的穩(wěn)定性：剔除違規(guī)成員或加入新成員時(shí)，勿需或只需少量改變系統(tǒng)參數(shù)和現(xiàn)有成員參數(shù)。

門限簽名本質(zhì)上是數(shù)字簽名技術(shù)與秘密共享技術(shù)的結(jié)合，用于簽名的私鑰作為原始秘密被分為各個(gè)參與方的份額，因此要抵御共謀攻擊是很難的。事實(shí)上，目前提出的所有門限簽名體制都不具備上述全部的特性，所以設(shè)計(jì)性能良好的門限群簽名體制被認(rèn)為是一個(gè)公開問題。有代表性的(k,n)門限簽名體制包括Desmedt和Frankel提出的基于RSA的門限簽名方案［33］、Wang和Lin等提出的可追查簽名者的門限簽名方案［39］，以及由Shoup提出的門限RSA簽名體制［37］，等等。Gennaro、Frankel及Rabin等也對門限RSA簽名進(jìn)行了研究，提出了更為安全和健壯的RSA門限簽名方案，詳見參考文獻(xiàn)［42-44］等。Guillou和Quisquater提出的GQ門限簽名方案［45］也在許多場合得到了應(yīng)用。

下面詳細(xì)分析兩種基于RSA體制的門限簽名方案，一種由Desmedt和Frankel提出，記作DF方案；另一種由Shoup提出，記作Shoup方案。

1)DF方案

DF方案是一種非交互式、有仲裁者的(k,l)門限簽名方案，其中使用了兩個(gè)可信任的仲裁者SDC和DC，SDC(ShareDistributionCenter)表示可信任的份額分發(fā)中心，DC表示簽名合成中心。

系統(tǒng)中的參與方集合為{P1,…,Pl}，并賦予每個(gè)參與方一個(gè)表示身份的參數(shù)xi，i=1,2,…,l。

DF方案包括初始化、簽名生成及簽名驗(yàn)證三個(gè)階段。

初始化階段

SDC選擇安全素?cái)?shù)p和q，計(jì)算n=pq，這里安全素?cái)?shù)意味著存在大素?cái)?shù)p′和q′，使得p=2p′+1及q=2q′+1。計(jì)算n的Carmichael函數(shù)λ(n)=2p′q′。隨機(jī)選擇私鑰d，使得gcd(d,λ(n))=1，并計(jì)算滿足ed≡1modλ(n)的公開密鑰e，由于λ(n)是偶數(shù)，因此d為奇數(shù)。SDC選擇k－1次多項(xiàng)式:

f(x)=a0+a1x+…+ak－1xk－1

其中,a0=d－1=f(0)。再計(jì)算參與方Pi的份額，為

這里,要求xi均為奇數(shù)而f(xi)均為偶數(shù)。SDC將Ki分發(fā)給各個(gè)參與方。系統(tǒng)中的公開參數(shù)為(n,e)，其它均保密。

簽名生成階段

假設(shè)有k個(gè)成員(不妨設(shè)其為P1,P2,…,Pk)要對消息m簽名。首先，每個(gè)成員Pi計(jì)算一個(gè)修正的份額yi:

(8-3)

再生成部分簽名

然后將部分簽名發(fā)送給簽名合成者DC。DC計(jì)算整體簽名S如下：

簽名驗(yàn)證階段

接收方收到簽名(m,S)后，由于

因此由式(8-3)，有

因而接收方可以根據(jù)下式驗(yàn)證簽名的有效性:

DF方案不具備可追查性和健壯性，且系統(tǒng)穩(wěn)定性差。在DF方案中，任何k個(gè)成員對同一消息的群簽名是完全相同的。也就是說，群簽名完全隱藏了簽名者的身份信息，就算事后發(fā)生糾紛，SDC也無法根據(jù)群簽名追查出實(shí)際參與該簽名的成員身份。所以，DF方案是不可追查的。另外，被刪除成員的秘密信息仍然有效，所以DF方案的系統(tǒng)穩(wěn)定性差。在DF方案中，保護(hù)秘密參數(shù)p、q、p′、q′和p′q′的信息是很關(guān)鍵的，Li等指出了對這種方案的兩個(gè)攻擊［41］，k個(gè)或k+1個(gè)參與方進(jìn)行合謀可以高概率地獲取p′q′。而利用王貴林等提出的攻擊方法［36］，k+1個(gè)參與方不僅可以獲取p′q′，還可獲得f(x)，從而可以得到系統(tǒng)中的所有秘密。

2)Shoup方案

Shoup方案同樣是有仲裁者參與的簽名方案，仲裁者生成份額及驗(yàn)證密鑰分發(fā)給各個(gè)參與方，由參與方生成部分簽名后，仲裁者需要將部分簽名進(jìn)一步合成為整體簽名。

初始化階段

仲裁者選擇兩個(gè)長度相同(如均為512bit)的安全素?cái)?shù)p和q，設(shè)p=2p′+1，q=2q′+1,p′、q′為兩個(gè)大素?cái)?shù)。令n=pq為RSA體制中的模數(shù)，m=p′q′。選擇加密指數(shù)e，這里要求e為素?cái)?shù)且e>l，計(jì)算解密密鑰d，使得de≡1modm。系統(tǒng)中的公開參數(shù)為(n,e)。仲裁者隨機(jī)選擇k-1次多項(xiàng)式：

f(x)=a0+a1x+…+ak－1xk－1

其中,a0=d，ai∈{0,1,…,m－1}，i=1,…,k－1。對i=1,2,…,l，仲裁者計(jì)算Si,將之作為第i個(gè)參與者的份額，這里,Si=f(i)modm。設(shè)Qn表示中的平方剩余集合，仲裁者隨機(jī)選擇v∈Qn，對i=1,2,…,l，計(jì)算

作為驗(yàn)證密鑰。

在初始化階段，仲裁者生成了公開密鑰PK=(n,e)，參與方的秘密份額SKi=Si，驗(yàn)證密鑰VK=v以及VKi=vi，i=1,2,…,l。注意到，若用Jn表示中Jacobi符號為1的元素集合，即

則，且Qn為m階循環(huán)群，而Jn為2m階循環(huán)群，－1∈Jn\Qn。由于v是在Qn中隨機(jī)選取的，可將v視為Qn的生成元，從而由vi可以完全確定Simodm。設(shè)H為可以將消息映射到的Hash函數(shù)，若x=H(M)，則對消息M的有效簽名為

，且ye=x。

簽名生成階段

令Δ=l!，對{0,1,…,l}中任意k個(gè)元素組成的集合S，以及任意i∈{0,1,…,l}\S，j∈S，定義整數(shù)

(8-4)由Lagrange插值公式，有

(8-5)

設(shè)x=H(M)，對任意i∈S，有

則參與方i的部分簽名由xi及一個(gè)“正確性證明”(z,c)組成。

(z,c)的生成過程為：設(shè)L(n)為n的二進(jìn)制表示的位數(shù)，H′為輸入是L1bit整數(shù)的Hash函數(shù)，參與方i選擇隨機(jī)整數(shù)

，計(jì)算

從而得到(z,c)。為了驗(yàn)證簽名的正確性，需驗(yàn)證如下等式成立:

假設(shè)有k個(gè)參與者集合S={i1,i2,…,ik}對消息M簽名，令

，并假設(shè)

，為了將部分簽名合成為整體簽名，計(jì)算

如式(8-4)中所定義，根據(jù)式(8-5)，有ωe=xe′，其中e′=4Δ2。由于gcd(e,e′)=1，因而可以用Euclid算法求出滿足e′a+eb=1的整數(shù)a、b，進(jìn)而得到y(tǒng)=ωaxb，且ye=x。

Shoup方案是針對一般的(t,k,l)門限方案而設(shè)計(jì)的，其中t為攻擊者的最大攻擊能力，即系統(tǒng)中最多有t個(gè)參與方會(huì)聯(lián)合起來實(shí)施共謀攻擊。Shoup利用隨機(jī)預(yù)言模型證明了方案的安全性。這里假設(shè)l－t≥k。

定理8-6

當(dāng)k=t+1時(shí)，在關(guān)于H′的隨機(jī)預(yù)言模型下，如果標(biāo)準(zhǔn)RSA簽名體制是安全的，則上述方案是一個(gè)安全的門限簽名體制，即具有健壯性和防冒充性。

證明詳見參考文獻(xiàn)［37］。

Shoup方案有以下優(yōu)點(diǎn)：

(1)在RSA假設(shè)下，Shoup方案在隨機(jī)預(yù)言模型中可以證明具有健壯性，并能防止偽造；

(2)簽名生成和驗(yàn)證過程是非交互式的；

(3)單個(gè)用戶的簽名份額長度是RSA模數(shù)的有限倍，從而可以將份額長度的擴(kuò)張限制在一個(gè)有限的范圍內(nèi)。

2.可生存的信息系統(tǒng)

信息系統(tǒng)可生存性是指在出現(xiàn)攻擊、故障和意外事件的情況下，系統(tǒng)所具有的及時(shí)完成任務(wù)的能力。生存性研究側(cè)重于信息的可用性和關(guān)鍵服務(wù)的可持續(xù)性，重點(diǎn)考慮安全機(jī)制被破壞以后，系統(tǒng)能否及時(shí)地做出響應(yīng)與恢復(fù)，使其中的關(guān)鍵服務(wù)仍然保持必要的屬性。系統(tǒng)的可生存性需求包括安全性、可靠性、可用性和實(shí)時(shí)性等性能［46］。秘密共享方案中，秘密被分為多個(gè)份額，如果有少數(shù)份額丟失、被破壞或過期，則仍可以根據(jù)其它份額來恢復(fù)秘密，通過共享而使系統(tǒng)的可靠性有所提高，這可以用于構(gòu)造可生存的信息系統(tǒng)。

CarnegieMellon大學(xué)的研究人員設(shè)計(jì)了可生存的存儲(chǔ)系統(tǒng)PASIS，數(shù)據(jù)在保存之前首先利用通用的p－m－n門限方案進(jìn)行分離，然后在每個(gè)服務(wù)器中保存一個(gè)份額。在p－m－n門限方案中，數(shù)據(jù)被分為n個(gè)份額，其中任意m個(gè)可以重構(gòu)秘密，而少于p個(gè)份額則得不到關(guān)于秘密的任何信息。通過對三個(gè)參數(shù)的不同選擇可以構(gòu)造具有不同可靠性和效率的系統(tǒng)，比如如果選擇p=m<n，就構(gòu)成了門限方案，如果選擇p=m=n，則成為備份系統(tǒng)。關(guān)于PASIS的細(xì)節(jié)可以參考參考文獻(xiàn)［47］，在這里不作詳述。8.2.1零知識(shí)證明的基本概念

零知識(shí)證明(zero-knowledgeproof)最早由Goldwasser等［49］提出。零知識(shí)證明是一種雙方協(xié)議，其中一方(證明者)向另一方(驗(yàn)證者)證明一個(gè)命題成立，但不讓后者知道證明方法。驗(yàn)證者在確信證明內(nèi)容的有效性之后，并不能獲得證明者為了完成證明所擁有的知識(shí)，另外，協(xié)議結(jié)束后，任何第三方都不可能明白證明者與驗(yàn)證者之間的通信內(nèi)容。8.2零知識(shí)證明

Quisquater和Guillou［50］設(shè)計(jì)了一個(gè)形象的例子來說明零知識(shí)證明的含義，這個(gè)例子又被稱為洞穴問題。假設(shè)有一個(gè)洞穴如圖8-1所示，洞穴底部的門要用秘密的咒語才能打開，證明者P知道咒語，他要向驗(yàn)證者V證實(shí)他確實(shí)知道這個(gè)咒語但又不泄露咒語內(nèi)容。圖8-1洞穴問題

P與V之間通過如下的協(xié)議來實(shí)現(xiàn)證明：

(1)V站在A點(diǎn)；

(2)P一直走到洞穴底部，到達(dá)C點(diǎn)或D點(diǎn)；

(3)當(dāng)P消失在洞穴中后，V走到B點(diǎn)；

(4)V命令P“從左邊出來”或“從右邊出來”；

(5)P照辦，如果需要通過門，則用咒語打開；

(6)重復(fù)上面的步驟。在上面的協(xié)議中，只要有一次P沒有按照V的命令去做，V就會(huì)認(rèn)為證明失敗，P沒有掌握咒語，因此如果P不知道咒語，則經(jīng)過m輪重復(fù)后，P成功實(shí)施欺騙的概率為1/2m，m越大，則證明的可信度就越高。零知識(shí)證明協(xié)議必須滿足完備性、合理性和零知識(shí)性。在零知識(shí)證明中，給定一個(gè)斷言，證明者的目標(biāo)是讓驗(yàn)證者確信其有效性，這被稱為完備性(completeness)；驗(yàn)證者的目標(biāo)是只接受正確的斷言，這稱為合理性(soundness)；在證明過程中，V不會(huì)得到證明者所掌握的知識(shí)，這被稱為零知識(shí)性。證明者在交互過程中要防止驗(yàn)證者提取出知識(shí)，因此通常驗(yàn)證者的工作要相對容易一些。

作為計(jì)算復(fù)雜性理論的重要分支，零知識(shí)證明有著非常重要的理論價(jià)值和應(yīng)用背景，它具有信息論意義上最“強(qiáng)”的可證明安全性，主要應(yīng)用于各種密碼協(xié)議、密鑰分配方案以及某些公鑰密碼體制的設(shè)計(jì)和分析，為密碼協(xié)議的安全性提供了有力的證據(jù)。

Goldreich等指出，如果單向函數(shù)確實(shí)存在，則每個(gè)NP問題都可用于構(gòu)造零知識(shí)證明［51］。

零知識(shí)證明協(xié)議可以分為交互式的和非交互式的。20世紀(jì)80年代末，Blum等人［52］在零知識(shí)證明中利用通信雙方共享一個(gè)共同的短隨機(jī)串來代替交互過程，從而實(shí)現(xiàn)了非交互式的零知識(shí)證明，即證明者和驗(yàn)證者在證明階段無需進(jìn)行交互，就能實(shí)現(xiàn)零知識(shí)性。非交互式不僅提高了效率，而且可以應(yīng)用于一些交互式證明無法實(shí)現(xiàn)的場合，比如可抵抗自適應(yīng)選擇明文攻擊的數(shù)字簽名系統(tǒng)，因而具有更廣的適用范圍。本節(jié)主要討論交互式協(xié)議。交互式零知識(shí)證明有兩種基本模型：GMR模型和FFS模型。GMR模型中，假設(shè)證明者具有無限的計(jì)算能力，驗(yàn)證者具有多項(xiàng)式時(shí)間計(jì)算能力，證明的是語言成員問題，即輸入x是否是語言L的一個(gè)成員。在GMR證明中，證明者向驗(yàn)證者泄露了知識(shí)的1bit，即x∈L。這種證明通常被稱為成員或定理的零知識(shí)證明(zero-knowledgeproofsofmembershiportheorem)。FFS模型中，假設(shè)證明者和驗(yàn)證者均具有多項(xiàng)式時(shí)間的計(jì)算能力，證明者的目的不是向驗(yàn)證者證明x∈L，而是證明他知道x關(guān)于L的狀況。在FFS證明中，驗(yàn)證者沒有得到任何信息，包括是否x∈L還是x

L，但他相信這個(gè)證明的有效性。這種零知識(shí)證明被稱為知識(shí)或身份的零知識(shí)證明(zero-knowledgeproofsofknowledgeoridentity)。8.2.2零知識(shí)證明的形式化定義

一個(gè)交互式圖靈機(jī)(interactiveTuringmachine)是一個(gè)具有一條只讀輸入帶、一條工作帶、一條隨機(jī)帶、一條只讀通信帶和一條只寫通信帶的圖靈機(jī)。隨機(jī)帶上有一個(gè)無限長的隨機(jī)比特序列，它只能從左到右地讀入。

一個(gè)交互協(xié)議(interactiveprotocol)是指一對有序圖靈機(jī)(P,V)，它滿足：

(1)P與V共享同一條輸入帶；

(2)V的只寫通信帶是P的只讀通信帶，反之，V的只讀通信帶是P的只寫通信帶，從而P向V發(fā)送信息m意味著P向自己的只寫通信帶上寫入信息m。

機(jī)器P具有無限的計(jì)算能力,而V具有多項(xiàng)式時(shí)間的計(jì)算能力。

圖8-2給出了交互協(xié)議的工作過程：首先V開始工作，然后兩臺(tái)機(jī)器輪流工作，在P(或V)的工作階段，P(或V)首先使用公共輸入帶和它的工作帶、通信帶、隨機(jī)帶上的內(nèi)容完成某種內(nèi)部計(jì)算；其次，P(或V)在其只寫通信帶上為V(或P)寫一個(gè)串。P(或V)的第i條消息是P(或V)在它的第i個(gè)工作階段寫在它的通信帶上的全部串。一旦機(jī)器P(或V)寫了它的消息，它就不工作，而機(jī)器V(或P)開始工作直至協(xié)議終止。如果任何一個(gè)機(jī)器在其工作階段不發(fā)出消息，則意味著協(xié)議終止?！啊北硎咀x寫頭;“”表示只讀頭；“”表示只寫頭圖8-2交互協(xié)議的工作過程令{0,1}*表示所有有限長的0、1串構(gòu)成的集合，{0,1}*上的語言L是指一個(gè)集合，其中的每個(gè)元素x都可編碼成為一個(gè)有限長的0、1串，該串的長度稱為x的長度，記作|x|。在這個(gè)意義下，可將語言L視為集合{0,1}*的一個(gè)子集，即L

{0,1}*。

從本質(zhì)上講，零知識(shí)證明是一種交互式證明協(xié)議，Goldwasser、Micali和Rackoff定義了交互式證明系統(tǒng)的計(jì)算模型。

交互式證明協(xié)議的基本模型為(P,V)，其中P為證明者，V為驗(yàn)證者。設(shè)L是{0,1}*上的一種語言，對一個(gè)成員歸屬實(shí)例x∈L，P和V必須共享輸入x，因此x稱為公共輸入。

證明實(shí)例可以表示為(P,V)(x)，P與V通過信道聯(lián)系，在證明過程中它們交互的信息稱為證明副本。證明副本由P傳輸?shù)臄?shù)據(jù)(稱為證明者的副本)及V傳輸?shù)臄?shù)據(jù)(稱為驗(yàn)證者的副本)組成。這里，副本的長度以及副本中任一信息的長度都有上界，這個(gè)上界是|x|的多項(xiàng)式。

同時(shí)，證明實(shí)例(P,V)(x)必須在關(guān)于|x|的多項(xiàng)式時(shí)間內(nèi)終止。

協(xié)議終止意味著協(xié)議產(chǎn)生了“接受”或“拒絕”的輸出，表示為

(P,V)(x)∈［Accept,Reject］

交互式證明系統(tǒng)的形式化定義如下：

定義8-7

設(shè)L是{0,1}*上的語言，雙方協(xié)議(P,V)稱為L的一個(gè)交互式證明系統(tǒng)，如果以下兩個(gè)條件成立：

(1)完備性(completeness)，對于足夠長的x∈L，將x作為(P,V)的公共輸入，V終止協(xié)議并至少以概率ε接收x，即

Pr［(P,V)(x)=接受|x∈L］≥ε

(2)合理性(soundness)，對于足夠長的x

L及任意的交互圖靈機(jī)，將x作為的輸入，V終止協(xié)議并至多以概率δ接收x。

其中,ε,δ為常數(shù)，滿足。

概率ε稱為(P,V)的完備性概率，δ稱為的合理性概率，這里概率空間是(P,V)的所有輸入值和P及V的所有隨機(jī)輸入值。

定義8-8

交互證明系統(tǒng)(P,V)被稱為是“零知識(shí)”的，如果對于每個(gè)概率多項(xiàng)式時(shí)間交互機(jī)V*都存在一個(gè)概率多項(xiàng)式時(shí)間算法M*，且滿足對于任意輸入x∈L，則下面兩個(gè)隨機(jī)變量同分布：

(1)〈P,V*〉(x)，即對于公共輸入x，V*與P交互后的輸出；

(2)M*(x)，即對于輸入x，機(jī)器M*的輸出。

機(jī)器M*稱為V*與P交互的仿真器(simulator)。這個(gè)定義說明了，在零知識(shí)證明中，任意概率多項(xiàng)式時(shí)間圖靈機(jī)與預(yù)先確定的證明者之間的交互過程，可以用一個(gè)概率多項(xiàng)式時(shí)間的仿真器來模仿。驗(yàn)證者在與證明者的交互過程中除了斷言的有效性之外，不會(huì)得到任何其它信息，因此如果驗(yàn)證者相信斷言的有效性，則他完全可以在沒有證明者時(shí)獨(dú)立地模仿出交互過程。定義8-8中給出的“零知識(shí)”是一種嚴(yán)格意義上的描述，以下假設(shè)模仿器在交互過程中有一定的失敗概率，從而給出較為弱化的定義。

定義8-9

令(P,V)是某種語言L的交互證明系統(tǒng)，如果對于每個(gè)概率多項(xiàng)式時(shí)間交互機(jī)V*，都存在一個(gè)概率多項(xiàng)式時(shí)間算法M*，使得對于每個(gè)x∈L，如下兩個(gè)條件成立，則稱(P,V)是完全零知識(shí)的(perfectzero-knowledge)：

(1)對于輸入x，M*輸出一個(gè)特殊符號(記作⊥)的可能性至多為，即

(2)用m*(x)來描述M*(x)在輸出不為⊥的條件下的隨機(jī)變量，那么兩個(gè)隨機(jī)變量〈P,V*〉(x)與m*(x)同分布，前者表示對于公共輸入x，在與交互機(jī)P交互之后V*的輸出；后者表示對于輸入x，M*在不輸出⊥的條件下的輸出。

注：在完全的零知識(shí)證明協(xié)議中，V從與P的交互中得到的信息都可以由V單獨(dú)計(jì)算而得到。

換言之，除了x∈L之外，V不會(huì)得到任何信息。8.2.3零知識(shí)證明協(xié)議

本節(jié)介紹幾個(gè)零知識(shí)證明的實(shí)例，包括Feige-Fiat-Shamir(FFS)識(shí)別協(xié)議、圖的非同構(gòu)問題和平方剩余問題。其中，F(xiàn)FS識(shí)別協(xié)議屬于FFS模型，后兩個(gè)屬于GMR模型。

1.FFS識(shí)別協(xié)議

1986年,Fiat和Shamir基于零知識(shí)證明提出了一種新型的識(shí)別協(xié)議，后經(jīng)Feige、Fiat和Shamir的改進(jìn)成為身份的零知識(shí)證明［54］。Feige-Fiat-Shamir識(shí)別協(xié)議是最著名的零知識(shí)證明協(xié)議，它是由一個(gè)仲裁數(shù)字簽名方案改進(jìn)而成的。

準(zhǔn)備階段

可信的權(quán)威機(jī)構(gòu)TA(trustfulauthority)產(chǎn)生全局變量n，n為兩個(gè)大素?cái)?shù)的乘積且除了TA之外沒有任何其它參與方知道n的分解式。

證明者P秘密選擇隨機(jī)數(shù)s，1<s<n且gcd(s,n)=1，P計(jì)算l≡s2modn，將l,n公開。

目的P要使V確信他知道秘密信息s，即要向V證明他知道公鑰l模n的一個(gè)平方根。

雙方通過圖8-3中的協(xié)議完成證明。圖8-3識(shí)別協(xié)議協(xié)議的運(yùn)行過程如下：

協(xié)議1

(1)P隨機(jī)選擇r，計(jì)算x≡r2modn并將x傳給V；

(2)V隨機(jī)選擇ei=0或1，將ei傳給P；

(3)在證明者P一方，如果ei=0，則令y=r，否則令y=rs，P將y傳給V；

(4)當(dāng)ei=0時(shí)，V檢查是否有y2=xmodn，否則檢查是否有y2=xlmodn；

(5)重復(fù)上述步驟。

F-S方案的安全性分析：

(1)給定l,n，計(jì)算s是困難的，其難度相當(dāng)于分解大整數(shù)n；

(2)(完備性)V能確信P知道l模n的平方根而不泄露關(guān)于s的任何信息；

(3)(合理性)P在選擇r并將x傳給V之前并不知道ei的取值，P可以以1/2的概率猜測ei的值，但當(dāng)協(xié)議重復(fù)執(zhí)行t次之后，猜測成功的概率變?yōu)?/2t。

2.圖的非同構(gòu)問題

圖的同構(gòu)問題(graphIsomorphism)描述如下：

假設(shè)兩個(gè)圖的頂點(diǎn)集合分別為V1、V2，且V1=V2={1,2,…,n}，圖G1=(V1,E1)與G2=(V2,E2)是同構(gòu)的當(dāng)且僅當(dāng)存在{1,2,…,n}上的置換π，使得(u,v)∈E1

(π(u),π(v))∈E2

，記作G1

G2。判定兩個(gè)給定的圖是否同構(gòu)是一個(gè)NP問題(顯

然也屬于IP類)，目前尚無多項(xiàng)式時(shí)間算法解決，但它不一定是一個(gè)NP完全問題。圖的非同構(gòu)問題(graphnon-isomorphism)描述為：假設(shè)兩個(gè)圖的頂點(diǎn)集合分別為V1,V2，且V1=V2={1,2,…,n}，如果不存在{1,2,…,n}上的置換π，使得(u,v)∈E1

(