張武軍,劉玉定,高雅倩,孫 曦,王育民

(西安電子科技大學(xué)綜合業(yè)務(wù)網(wǎng)理論及關(guān)鍵技術(shù)國家重點實驗室,陜西西安 710071)

單向函數(shù)假設(shè)下基于身份的陷門水銀承諾

張武軍,劉玉定,高雅倩,孫 曦,王育民

(西安電子科技大學(xué)綜合業(yè)務(wù)網(wǎng)理論及關(guān)鍵技術(shù)國家重點實驗室,陜西西安 710071)

基于身份的陷門水銀承諾結(jié)合了基于身份的陷門承諾和水銀承諾兩個概念,它是構(gòu)造基于身份的零知識集合的基礎(chǔ)模塊.目前,現(xiàn)有的基于身份的陷門水銀承諾方案都是基于強Diffie-Hellman假設(shè)和計算性Diffie-Hellman假設(shè)來構(gòu)造的.單向函數(shù)假設(shè)是密碼學(xué)中最基本的假設(shè),文中基于單向函數(shù)假設(shè)給出了基于身份的陷門水銀承諾的一般性構(gòu)造方法,并且利用Boneh-Boyen簽名給出了一個具體的例證.

陷門水銀承諾;基于身份的密碼體制;單向函數(shù)

承諾是現(xiàn)代密碼學(xué)中最重要的基本概念之一,它在零知識證明、安全多方計算、數(shù)字簽名、安全電子商務(wù)協(xié)議等方面有著重要的應(yīng)用[1-3].直觀上來講,承諾方案可以看作是一個密封的數(shù)字信封,該信封中裝有發(fā)送方給接收方的一個消息.更嚴格地講,一個承諾方案是兩個概率多項式時間的算法(發(fā)送方和接收方)之間所進行的一個交互式的協(xié)議,它包括兩個階段:在承諾階段,發(fā)送方輸入消息m和冗余值r,計算對消息m的承諾值c并將c發(fā)送給接收方.在打開階段,發(fā)送方向接收方泄露消息m和冗余值r,使得接收方相信c確實是對消息m的承諾.一個承諾方案必須滿足隱藏性和綁定性.

陷門承諾是一種特殊的承諾方案,它允許知道陷門信息的人可以用不同的方式打開承諾,即在給定陷門信息的條件下,陷門承諾方案不滿足傳統(tǒng)承諾方案的綁定性.在2005年歐密會上,Chase等[4]介紹了一種新的陷門承諾-水銀承諾.與傳統(tǒng)陷門承諾相比,發(fā)送者在構(gòu)造水銀承諾前必須決定承諾方案是軟承諾還是硬承諾.而且,水銀承諾的打開分為兩個方面:軟承諾不能硬打開但可以軟打開為任何值,而硬承諾只能打開為最初所承諾的值.水銀承諾是構(gòu)造零知識集合的一個重要的基礎(chǔ)模塊.因此,許多學(xué)者對水銀承諾進行了大量的研究[4-9].

2011年,Chen等[9]首次提出了基于身份的陷門水銀承諾的概念.基于身份的陷門水銀承諾結(jié)合了基于身份的陷門承諾和水銀承諾兩種概念,是構(gòu)造基于身份的零知識集合的重要模塊.此外,文獻[9]分別基于強Diffie-Hellman假設(shè)及計算性Diffie-Hellman假設(shè)給出了基于身份的陷門水銀承諾的具體構(gòu)造,然而,由于計算開銷較大,實用價值較差.

在密碼學(xué)理論中,如果一個密碼方案所依賴的數(shù)學(xué)問題的假設(shè)性越弱(即所依賴的數(shù)學(xué)難題的難度越大),則這個密碼方案越具有現(xiàn)實意義.單向函數(shù)存在性假設(shè)是密碼學(xué)中最基本的假設(shè).所謂單向函數(shù),指的是一個計算簡單求逆困難的函數(shù).也就是說,任何一個多項式概率時間的計算單向函數(shù)的算法是幾乎不可能存在的.單向函數(shù)是公鑰密碼學(xué)的理論基礎(chǔ).文中利用單向函數(shù)存在性假設(shè)給出基于身份的陷門水銀承諾的一般性構(gòu)造方法,并利用Boneh-Boyen短簽名給出了一個具體的例證.

1 基于身份的陷門水銀承諾

Chen等[9]首次提出了基于身份的陷門水銀承諾的概念,具體包含以下算法:

Setup:一個概率多項式時間的密鑰生成算法,輸入為1k,輸出一個密鑰對(PK,SK),其中PK為公鑰, SK為主私鑰.

Extract:一個確定性多項式時間密鑰生成算法,輸入為ID,SK,輸出是身份ID的陷門信息SID.

HCom:一個概率多項式時間硬承諾算法,輸入為PK,自定義的身份L=IDP‖IDV‖IDT,消息m∈M和一個隨機字符串r∈{0,1}k,輸出c=HComPK,L(m;r).

HOpen:一個確定性的多項式時間打開算法,輸入為硬承諾c=HComPK,L(m;r),輸出為c的打開值d= HOpenPK,L(c).注意到,這個算法應(yīng)該用與HCom算法相同的r值運行.

HVer:一個確定性多項式時間驗證算法,輸入為PK,L,c和d,輸出b∈{0,1},要求對所有的m∈M,以不可忽略的概率成立.

SCom:一個概率多項式時間的軟承諾算法,輸入為PK,L,c和一個隨機字符串r∈{0,1}k,輸出c= SComPK,L(;r).

SOpen:一個確定性多項式時間打開算法,輸入為PK,L,承諾c,消息m和標志F∈{H,S},輸出為一個打開值τ,其中,τ=SOpenPK,L(m;c;H),是硬承諾c=HComPK,L(m;r)相對應(yīng)的打開值;τ=SOpenPK,L(m;c;S),是軟承諾c=SComPK,L(;r)相對應(yīng)的打開值.

SVer:一個確定性多項式時間驗證算法,輸入為PK,L,c和τ,輸出b∈{0,1}.要求對于所有的m∈M,要么,要么以不可忽略的概率成立.

MFake:一個概率多項式時間算法,輸入為PK,SL,和一個隨機字符串r∈{0,1}k,輸出一個假承諾c=(;r),它并不對任何消息m做承諾.MFake與SCom有些相似,兩者的主要區(qū)別在于,SL是MFake的一個輸入.

HEquiv:一個確定性多項式時間算法,輸入為PK,L,SL,c=和一個給定的消息m∈M,輸出為一個貌似有效的硬打開值要求對于所有的m∈M以不可忽略的概率成立.

SEquiv:一個確定的多項式時間算法,輸入為PK,L,SL,c=MFakeSL(;r)和一個給定的消息m∈M,輸出為一個貌似有效的軟打開值要求對于所有的m∈M=1以不可忽略的概率成立.

2 單向函數(shù)假設(shè)下通用構(gòu)造方法

Canetti等人在文獻[10]指出,在單向函數(shù)存在的假設(shè)前提下可以構(gòu)造Σ協(xié)議的簽名方案.同時,Canetti等人在標準模型下利用基于Σ協(xié)議的簽名方案,給出了一個基于身份的陷門承諾方案的一般性構(gòu)造.這樣一來,在單向函數(shù)的前提下可以生成一個基于身份的陷門承諾方案.此外,給定一個基于身份的陷門承諾方案可以定義兩個基于身份的Σ協(xié)議的比特承諾方案,其中這兩個比特承諾方案可以從文獻[10]中的ECom和Com兩個算法中獲得.而且,Catalano等人在文獻[5]基于Σ協(xié)議的比特承諾給出了基于身份的陷門水銀承諾方案的一般性構(gòu)造方案.因此,在單向函數(shù)的假設(shè)下可以得到基于身份的陷門水銀承諾方案.總的來說,它分為以下4個步驟:

(1)單項函數(shù)存在的假設(shè)→構(gòu)造出具有擴展的Σ協(xié)議的簽名方案;

(2)具有擴展的Σ協(xié)議的簽名方案→構(gòu)造出基于身份的陷門承諾方案;

(3)基于身份的陷門承諾方案→兩個基于身份的Σ協(xié)議的比特承諾;

(4)基于身份的Σ協(xié)議的比特承諾→基于身份的陷門水銀承諾.

下面,將詳細給出在單向函數(shù)假設(shè)存在下,基于身份的陷門水銀承諾的一般構(gòu)造方法:

首先,通過文獻[10]中定理5.1可知,當單向函數(shù)存在的假設(shè)下,可以構(gòu)造具有擴展的Σ協(xié)議的簽名方案.然后,可以在具有擴展的Σ協(xié)議的簽名方案的基礎(chǔ)上,可以得到基于身份的陷門承諾方案:

設(shè)Υ=(Gen,Sig,Ver)定義為任何現(xiàn)有的不可偽造的抗選擇消息攻擊的簽名方案.定義一個關(guān)系式RΥ(x,w),使得(x,w)∈RΥ.如果對于關(guān)系式RΥ存在著擴展的Σ協(xié)議,可以說Υ存在擴展的Σ協(xié)議.如果x=〈VK,m〉w=σ,則Ver(VK,m,σ)=accept;否則,w=rg,則為(VK,SK)=Gen(rg,1λ),且SK是與VK一致的簽名私鑰(即w包含Gen算法在生成VK和SK時的所有隨機可能性),L為自定義的身份,記為L= IDP‖IDV‖IDT.

Setup(1λ):計算(VK,SK)←Gen(rg,1λ),其中rg定義為使用Gen算法時的隨機硬幣.返回參數(shù)對(PK=VK,MSK=rg).

Extract(PK,ID,MSK):運行Gen(MSK,1λ)得到SK.計算σID=Sig(SK,ID),返回SKID=σID.

Com(PK,L,d,m):計算(a,z)←ZKSim(x=〈PK,L〉,c=m,rs=d),其中ZKSim是關(guān)系式RΥ的Σ協(xié)議模擬器.返回承諾κ=a.

ECom(PK,L,SKID):選擇隨機硬幣ra并計算a=A(x=〈PK,ID〉,w=SKL,ra).返回參數(shù)對(κ=a, α=ra).

Eqv(PK,L,SKL,κ,α,m):計算rs=RSC(x=〈PK,L〉,w=SKL,ra=α,c=m).返回d=rs.

再次,在基于身份的陷門承諾基礎(chǔ)上,可以由以上方案中的Com和ECom兩個算法得到基于身份的比特承諾.即把0和1兩個比特分別代入就可以得到基于身份的比特承諾.而且,很容易證明這兩個基于身份的比特承諾具有Σ協(xié)議.

最后可以由以下的過程來獲得基于身份的陷門水銀承諾,過程如下:

設(shè)C=(Com-Gem,Com,Open,Ver)是常規(guī)的比特承諾方案,它對于關(guān)系Rpk={(c,d)|Verpk(0,c, d)=1},具有一個Σ協(xié)議Π=(Start,Finish,Extract,Simul).這意味著驗證者只能得到一個承諾c,且證明者也可以得到一個證據(jù),即對于0的承諾c的有效打開值d.同時,假設(shè)M是Π的挑戰(zhàn)空間.接著對消息空間M定義了一個水銀承諾C′=(MCom-Gen,HCom,HOpen,HVer,SCom,Sopen,SVer),如下所示:

HCompk,L(m;(rs,r1)):設(shè)c1=HCompk,L(1;r1)是對1的承諾,且(a1,z1)=Simulpk,L(c1,m;rs),是Π偽造的第一或最后的消息,它(這里是不正確的)宣稱c1是在挑戰(zhàn)m上對0的承諾.輸出值為(c1,a1).

HOpenpk,L(m;(rs,r1)):設(shè)c1=Compk,L(1;r1)和(a1,z1)=Simulpk,L(c1,m;rs)如上文所示.使d1= Openpk,L(1;r1)并輸出(d1,z1).

HVerpk,L(m;(rs,r1),(d1,z1)):當且僅當Verpk,L(1,c1,d1)=1時接受(d1是1承諾的正確的打開值)且Checkpk,L(c1,a1,m,z1)=1(在挑戰(zhàn)m上的假的副本即c1看起來像是對0的承諾).

SCompk,L(;(rp,ro)):設(shè)c0=Compk,L(0;r0)是對0的承諾,d0=Openpk,L(0;r0)是相應(yīng)的打開值,且a0= Startpk,L(c0,d0;rp)是Π的第一個真實的消息,它宣稱c0是對0的承諾.輸出為(c0,a0).

SOpenpk,L(m,H;(rs,r1)):設(shè)c1=Compk,L(1;r1)和(a1,z1)=Simulpk,L(c1,m;rs)是挑戰(zhàn)m上的假的副本,即c1是對0的承諾.輸出為z1.

SOpenpk,L(m,S;(rp,r0)):設(shè)c0=Compk,L(0;r0),d0=Openpk,L(0;r0)和a0=Startpk,L(c0,d0;rp)為挑戰(zhàn)m的正確的最后流程.輸出為z0.

SVer(m,(c,a),z):當且僅當Checkpk,L(cb,a,m,z)=1時接受,副本(a,m,z)表示c是對0的承諾是正確的.

MFakesk,L(;(rp,r)):設(shè)c=Fakesk,L(;r)為假的承諾,d0=Equivsk,L(0;r)是相對于0的假打開,且a0= Srartpk,L(c,d0,rp)是Σ協(xié)議正確的第一個流程.輸出為(c,a0).

HEquivsk,L(m;(rp,r)):設(shè)c=Fakesk,L(;r),d0=Equivsk,L(0;r)和a0=Srartpk,L(c,d0,rp)如上文所示.計算1的承諾c的假打開值d1=Equivsk,L(1;r)和正確的最后消息z0=Finishpk,L(c,d0,m;rp).輸出(d1,z0).

SEquivsk,L(m;(rp,r)):設(shè)c=Fakesk,L(;r),d0=Equivsk,L(0;r)和a0=Srartpk,L(c,d0,rp)如上文所示.計算正確的最后消息z0=Finishpk,L(c,d0,m;rp)且輸出z0.

3 基于短簽名的具體構(gòu)造

基于Boneh-Boyen短簽名[11]來構(gòu)造一個具體的基于身份的陷門水銀承諾方案.

設(shè)k為安全參數(shù),G1為由P生成的GDH(Gap Diffie-Hellman)群,它的階為素數(shù)q,G2是具有相同階數(shù)的乘法循環(huán)群.一個雙線性對是一個映射e:G1×G1→G2.設(shè)H:{0,1}*→一個全域抗碰撞哈希函數(shù).選擇兩個隨機整數(shù)y1,y2∈.主私鑰為(y1,y2),相應(yīng)的公鑰為(Ppub1=y1P,Ppub2=y2P).給定一個字符串x∈,x的簽名是一個二元組(w,σ=P(x+y1+wy2)).可以利用如下的Σ協(xié)議來給出(w,σ)的知識證明.

證明者選擇一個隨機參數(shù)Q∈G1,計算承諾a=e(x P+Ppub1,Q)并發(fā)送(a,w)給驗證者.驗證者發(fā)送一個隨機挑戰(zhàn)c∈給證明者.最后,證明者計算并響應(yīng)R=Q-cσ.當且僅當e(x P+Ppub1+wPpub2,R)= ae(P,P)-c,驗證者輸出1.另一方面,模擬器即使不知道陷門知識(w,σ)也能提供計算上不可區(qū)分的模擬的證明(a=e(P,P)ce(x P+Ppub1+w Ppub2,R),w,c,R),其中w和c是中的兩個隨機元素,R是G1中的隨機元素.

可以很容易地驗證Boneh-Boyen簽名方案具有一個擴展的Σ協(xié)議.因此,可以構(gòu)造一個基于身份的陷門承諾C=e(P,P)me(H(ID)P+Ppub1+w Ppub2,R):令Com(1)=e(P,P)v,Com(0)=e(H(L)P+Ppub1+ wPpub2,R),為兩個基于身份的比特承諾方案(注意,使用了自定義的身份標識L代替了字符串ID,而且Com(0)是陷門承諾C在m=0的值).此外,需要一個Σ協(xié)議來證明v=loge(P,P)Com(1)的知識.令(a=e(P, P)u,c,z=(u-m)/v),是Σ協(xié)議的輸出,當且僅當a=e(P,P)uCom(1)z驗證者接受該證明.

下面給出基于身份的陷門水銀承諾方案:硬承諾HCom的輸出為(a0,Com(0)),其中(a0,m,z0)是對Com(0)是在挑戰(zhàn)m上1的承諾的模擬證明.一般地,a0=e(P,P)me(H(L)P+Ppub1+wPpub2,R)u和z0=u,其中u是的隨機元素.給定打開值d=(m,n,w,R),可以證明a0=e(P,P)mCom(0)u和Com(0)= e(H(L)P+Ppub1+wPpub2,R).軟承諾SCom的輸出值為(a1,Com(1)),其中(a1,m,z1)是在挑戰(zhàn)m上1的承諾Com(1)的真實證明.一般地,a1=e(P,P)u和z1=(u-m)/v,其中u是的隨機元素.給定一個軟承諾的打開值zi,如果ai=e(P,P)mCom(i)zi則輸出1,其中如果F=H,則i=0,如果F=S,則i=1.同樣地,假承諾MFake的輸出為(e(P,P)u,e(P,P)v)(硬承諾HCom和軟承諾SCom的值域都是).HEquiv的輸出是(m, z1,d0),其中z1=(u-m)/v,是Σ協(xié)議中為了證明在挑戰(zhàn)m上1的承諾e(P,P)v的響應(yīng),且d0=(w,vP(H(L)+y1+wy2)),是0的承諾e(P,P)v的打開值.同樣地,SEquiv的輸出值z1=(u-m)/v.因此,基于Boneh-Boyen簽名方案的構(gòu)造可以被看作基于單向函數(shù)假設(shè)的一般構(gòu)造方法的實例.

4 結(jié)束語

基于身份的陷門水銀承諾結(jié)合了基于身份的陷門承諾和水銀承諾兩個承諾的概念,它是構(gòu)造基于身份的零知識集合的基礎(chǔ)模塊,解決了證據(jù)的廣泛傳播和防止剽竊之間的矛盾,同時,對它做稍微的改變之后還可以用來設(shè)計ZKS協(xié)議的非傳遞性證明.單向函數(shù)存在性假設(shè)是密碼學(xué)中最基本的假設(shè),在此基礎(chǔ)上構(gòu)造的密碼方案則更具有實踐意義.在單向函數(shù)假設(shè)下,提出了基于身份的陷門水銀承諾的一般構(gòu)造的方法,并給出了一個具體的例證.

[1]王明偉,胡予濮.一種前向-后向安全的數(shù)字簽名方案[J].西安電子科技大學(xué)學(xué)報,2014,41(2):71-78. Wang Mingwei,Hu Yupu.Forward and Backward Secure Signature Scheme[J].Journal of Xidian University,2014,41 (2):71-78.

[2]江明明,胡予濮,王保倉,等.格上的代理重簽名方案[J].西安電子科技大學(xué)學(xué)報,2014,41(2):20-24. Jiang Mingming,Hu Yupu,Wang Baocang,et al.Proxy Re-signature Scheme over the Lattic[J].Journal of Xidian University,2014,41(2):20-24.

[3]孫瑾,胡予濮.完全安全的基于屬性的廣播加密方案[J].西安電子科技大學(xué)學(xué)報,2012,39(4):23-28. Sun Jin,Hu Yupu.Fully Secure Attribute-based Broadcast Encryption[J].Journal of Xidian University,2012,39(4): 23-28.

[4]Chase M,Healy A,Lysyanskaya A,et al.Mercurial Commitments with Applications to Zero-knowledge Sets[C]// Lecture Notes in Computer Science:3494.Berlin:Springer,2005:422-439.

[5]Catalano D,Dodis Y,and Visconti I.Mercurial Commitments:Minimal Assumptions and Efficient Constructions[C]// Theory of Cryptography.Berlin:Springer,2006:120-144.

[6]Catalano D,Fiore D,Messina M.Zero-knowledge Sets with Short Proofs[C]//Lecture Notes in Computer Science: 4965.Berlin:Springer,2008:433-450.

[7]Libert B,Yung M.Concise Mercurial Vector Commitments and Independent Zero-knowledge Sets with Short Proofs [C]//Theory of Cryptography.Berlin:Springer,2010:488-517.

[8]Chase M,Healy A,Lysyanskaya A,et al.Mercurial Commitments with Applications to Zero-knowledge Sets[J]. Journal of Cryptology,2013,26(2):251-278.

[9]Chen X,Susilo W,Zhang F,et al.Identity-based Trapdoor Mercurial Commitments and Applications[J].Theoretical Computer Science,2011,412(38):5488-5512.

[10]Canetti R,Dodis Y,Pass R,and Walfish S.Universally Composable Security with Global Setup[C]//Lecture Notes in Computer Science:4392.Berlin:Springer,2007:61-85.

[11]Boneh D,Boyen X.Short Signatures without Random Oracles[C]//Lecture Notes in Computer Science:3027.Berlin: Springer,2004:56-73.

(編輯:王 瑞)

ID-based trapdoor mercurial commitment under one-way functions assumptions

ZH ANG Wujun,LIU Yuding,GAO Yaqian,SUN Xi,WANG Yumin
(State Key Lab.of Integrated Service Networks,Xidian Univ.,Xi’an 710071,China)

The notion of identity-based trapdoor mercurial commitment incorporates the advantages of both identity-based trapdoor commitment and trapdoor mercurial commitment.So far,the existing identitybased trapdoor mercurial commitment schemes are based on the strong Diffie-Hellman assumption or computational Diffie-Hellman assumption.One-way function existence is one of the fundamental assumptions in the cryptography.In this paper,we first propose a general construction for identity-based trapdoor mercurial commitment based on the one-way function.Meanwhile,we give a concrete instantiation based on the Boneh-Boyen signature scheme.

trapdoor mercurial commitment;identity-based cryptosystems;one-way functions

TP309

A

1001-2400(2015)05-0038-05

2014-05-16< class="emphasis_bold">網(wǎng)絡(luò)出版時間:

時間:2014-12-23

國家自然科學(xué)基金資助項目(61272455)

張武軍(1978-),男,西安電子科技大學(xué)博士研究生,E-mail:wjzhang@xidian.edu.cn.

http://www.cnki.net/kcms/detail/61.1076.TN.20141223.0946.007.html

10.3969/j.issn.1001-2400.2015.05.007