高效的基于雙線性對和身份的廣義簽密方案

摘 要:為解決目前基于身份的廣義簽密方案效率不高的問題，利用雙線性對，結合廣義的思想，提出了一個高效的基于身份的廣義簽密方案。在隨機預言機模型下給出了該方案的安全性證明，證明結果表明該方案滿足抗適應性選擇密文攻擊下的機密性、不可偽造性和不可否認性。與目前惟一的一個基于身份的廣義簽密方案相比，本方案減少了兩個對運算，是目前效率最高的基于身份和對映射的廣義簽密方案。

關鍵詞:簽密; 廣義簽密; 基于身份; 雙線性對; 隨機預言機

中圖分類號:TP309

文獻標志碼:A

文章編號:1001-3695(2010)02-0678-04

doi:10.3969/j.issn.1001-3695.2010.02.076

Efficient pairing-based and identity-based generalized signcryption scheme

ZHANG Hong-li， ZHAO Jing， LIU Wen-yuan

(Dept. of Computer， School of Information Science Engineering， Yanshan University， Qinhuangdao Hebei 066004， China)

Abstract:To improve the efficience，this paper proposed a new efficient identity-based generalized signcryption scheme using the bilinear pairings and the ideas of generalization. Proved the proposed scheme to be message confidentiality non-repudiation and unforgeability under the random oracle model. As compared withthe only-one identity-based gernalized signcryption scheme to date，the proposed scheme decreases two pairing operations， and is more efficient.

Key words:signcryption; generalized signcryption; identity-based; bilinear pairings;random oracle

0 引言

簽密在一個合理的邏輯步驟內同時完成數字簽名和公鑰加密兩項功能。如今簽密技術已經得到了廣泛的應用，如防火墻、電子現金支付和密鑰分配等。雖然簽密在需要提供加密和認證功能的場合效率比較高，但當系統只需要機密性或認證性時，普通的簽密方案就不再適用了。系統必須切換到其他的加密或簽名算法才能滿足需要，這將增加額外的開銷。為了解決這個問題，2006年，韓益亮等人[1]提出了廣義簽密的概念，即具有更強適應性的簽密體制，它能實現三種功能。當要求同時滿足機密性和認證性時能夠提供加密和簽名雙重功能，當僅要求機密性或認證性時，無須任何修改和附加計算就可以單獨提供加密或簽名功能。他們也提出了一個基于橢圓曲線數字簽名標準ECDSA(elliptic curve digital signature algorithm，橢圓曲線數字簽名算法)的廣義簽密方案SC-ECDSA，但是沒有給出完整的安全性定義。為了簡化密鑰的管理，Shamir[2]于1984年提出基于身份的密碼體制。由于雙線性對是構造基于身份的密碼體制的很好工具，近幾年來，利用雙線性對構造基于身份的方案成為密碼學界的研究熱點。2008年，文獻[3]首次提出了基于對映射和身份的廣義簽密方案，但該方案從簽密到解簽密總共花費了四次對運算，效率比較低。基于身份的廣義簽密將基于身份的簽密推廣到只要求機密性或認證性的場合，有著更廣闊的應用前景。

本文利用雙線性對提出了一個高效的基于身份的廣義簽密方案，并對方案的安全性給出了證明。本文的方案僅需兩個對運算，與文獻[3]中提出的至今惟一一個基于身份的廣義簽密方案相比，本文方案效率更高。

1 預備知識

本節簡要介紹雙線性對的基礎知識及其相關困難問題。

令G1是階為q的循環加法群，G2是q階循環乘法群，P是G1的生成元，映射e:G1×G1→G2。

雙線性對:若映射e滿足下列三個性質則就是雙線性對。

1)雙線性 對任意P，Q∈G1，a，b∈Zq有等式e(aP，bQ)=e(P，Q)ab成立。

2)退化性 對于P∈G1，當且僅當Q∈G1且P=O時，存在e(P，Q)=1成立。

3)可計算性 對于P，Q∈G1， 都存在有效的算法計算e(P，Q)。

本文提出的簽密方案依賴于以下困難問題。

定義1 對于任意a，b，c∈Zq，由(P，aP，bP，cP)計算e(P，P)abc就是BDH問題(這里并不知道具體的a、b、c的值)。注意:橢圓曲線中的BDH問題是數學領域公認的難題。目前大部分基于身份和對映射的密碼學方案都是基于BDH難題假設。

2 基于身份的廣義簽密定義

本章描述基于身份的廣義簽密方案的算法組成及其安全性概念。

2.1 基于身份的廣義簽密的算法組成

在基于身份的廣義簽密中存在三種模式，即簽密、簽名和加密。

定義2 一個基于身份的廣義簽密由以下四個算法組成:

a)系統密鑰的生成(setup)。由PKG完成，輸入安全參數，密鑰生成中心(PKG)輸出主密鑰s和系統參數params。保密s，公開params。

b)用戶私鑰的生成(extract)。輸入一個用戶身份IDU和主密鑰s，PKG計算相應IDU的私鑰SU，并通過安全方式發送給這個用戶。

c)廣義簽密(GSC)。該簽密有三種可能模式，但每次廣義簽密只有一種模式發生。

(a)簽密。若Alice(IDA)需要既機密又認證地發送一個消息m給Bob(IDB)。Alice的輸入需為(SA，IDB，m)，廣義簽密算法生成密文σ=GSC(m，SA，IDB)。

(b)簽名。若Alice只需簽名一個消息m，則不需要特定的接收方Bob的信息。Alice的輸入為(SA，ID，m)，其中ID為身份空的情況。廣義簽密算法生成密文σ=GSC(m，S-A，ID)。此時的廣義簽密就相當于簽名。

(c)加密。若某個用戶只需要機密地向Bob發送消息m，則無須知道Alice的信息。輸入為(S，IDB，m)。其中S表示用戶的身份為ID時對應的用戶私鑰。廣義簽密算法生成密文σ=GSC(S，IDB，m)，此時的廣義簽密就相當于加密。

c)解廣義簽密(DGSC)。無論是解簽密、簽名驗證還是解密都會執行如下操作:

若密文σ是有效的密文，則Bob解簽后返回消息m、Alice對m的簽名，否則返回⊥表示解簽密失敗。

注意:只有滿足基于身份的廣義簽密方案的正確性驗證，即當且僅當m=DGSC(σ，IDA，SB)成立時才會有σ=GSC(m，SA，IDB)是合法的密文。

2.2 安全性概念

根據攻擊者是否包括執行協議的兩方，又可分為內部安全和外部安全。當攻擊者包括執行協議的兩方時的安全性稱為內部安全性，否則稱為外部安全性，內部安全性更強[4]。本節所定義的安全性都是指內部安全性。

1)機密性 因為只有在加密模式和簽密模式下才會涉及到機密性的概念，而簽名模式則無須考慮機密性問題。所以廣義簽密機密性的攻擊游戲和定義如下:

游戲(簽密或加密)

初始化階段

C運行setup(1k)返回params給A，保密s。

游戲第一階段如下:

a)簽密(或加密)詢問A提交一個簽名者的身份、一個接收者的身份和消息(或只提交接收者的身份和消息)給C，C返回對消息的簽密(或密文)。

b)解簽密(或解密)詢問A提交密文和接收者的身份給C， C用接收者的私鑰解密;然后驗證解密的結果與簽名是不是合法的消息/簽名對。若是則C返回明文消息、該消息的簽名和簽名者的身份，否則返回⊥表示拒絕(或A提交密文和接收者的身份給C， C用接收者的私鑰解密并返回明文消息)。

c)Extract詢問。A提供一個身份IDU， C返回相應的私鑰SU給A。

d)A輸出兩個身份{IDA，IDB}和兩個消息{m1，m0}，A不允許對IDB進行extract詢問。這里IDB≠ID，否則考慮機密性就沒有意義了。C隨機選取b∈{0，1}。當IDA≠ID時， C計算σ=GSC(mb，SA，IDB)或當IDA=ID時，C計算σ=GSC(mb，S，IDB)，返回σ給A。

游戲第二階段如下:

(a)A像第一階段那樣執行多項式有界次詢問。 但是不允許對IDB進行extract詢問， 也不允許用IDB對σ進行解簽密詢問。

最后階段如下:

A返回b′，若b′=b則A獲勝。

定義3 令A表示進行上面游戲的攻擊者，若A在攻擊中的優勢adv[A]=2Pr[b=b′]-1是可忽略的，則稱一個基于身份的廣義簽密方案是抗適應性選擇密文攻擊(IND-IBGSC-CCA2)安全的。

2)不可偽造性 因為只有在簽名模式和簽密模式下才會涉及到偽造性，機密模式時無須考慮偽造性。在內部安全性[4]的意義下，簽密的偽造者為密文的接收者(Bob)和第三方攻擊者，接收者知道自己的私鑰，他具有最強的偽造能力。給定一個簽密密文給接收者(Bob)，它能夠用自己的私鑰解簽密，對簽密的偽造就是對簽名的偽造。因此，廣義簽密的不可偽造性與簽名的不可偽造性相同，即在簽名模式中適應性攻擊者(包括接收者)冒充發送方偽造一則簽密文在計算上是不可行的，則稱一個基于身份的廣義簽密方案滿足不可偽造性。

攻擊游戲

初始化 C運行setup(1k)返回給A。

詢問A 像定義3 那樣執行多項式有界次詢問。

最后， A輸出一個新的三元組(σ，IDA，IDB)或(σ，IDA，ID)，且這個元組不是由簽密預言機產生，也沒有對IDA執行extract詢問。如果解廣義簽密(σ，IDA，IDB)或(σ，IDA，ID)成功，則A贏得游戲。

定義4 如果沒有任何多項式有界的敵手以一個不可忽略的優勢(A獲勝利的概率就是他的優勢)贏得以上游戲，則稱一個基于身份的廣義簽密方案在適應性選擇消息攻擊下不可偽造。

3)不可否認性 與2)類似，如果在簽名和簽密模式下，發送方想要否認他曾發出的簽密文時，第三方進行仲裁在計算上是可行的，則稱一個基于身份的廣義簽密方案滿足不可否認性。

3 基于身份的廣義簽密方案

根據定義2知基于身份的廣義簽密最關建的就是區分簽密、簽名、加密這三個模式。在基于身份的密碼學中， 簽名消息需要特定的發送者的信息，加密消息需要特定的接收者的信息， 簽密消息則既要知道特定的發送者又要知道特定的接收者的信息。因此，協議雙方的身份就可以用來區分這三種模式。當輸入者的身份不存在時，令其公鑰為0表示的二進制串來區分三個模式;采用異或加密方式來控制是否屏蔽加密功能。

方案的具體描述如下:

a)Setup。令G1是階為q的循環加法群，G2是q階循環乘法群，P是G1的生成元。e:G1×G1→G2為雙線性映射。定義四個函數H1:{0，1}→G1，H2:{0，1}→Zq，H3:G1→Zq，H4:G2→{0，1}n為安全的hash函數，而且令H4(1)輸出的為n bit的0串。PKG隨機選擇一個主密鑰s∈Zq，計算密PKG的公鑰Ppub=sP。{G1，G2，n，e，P，Ppub，H1，H2，H3，H4}是PKG公開的系統參數，保密主密鑰s。

b)Extract。給定一個用戶U的IDU，PKG計算U的私鑰SU=sQU。其中QU=H1(IDU)為U的公鑰。在這里設Alice的身份為IDA，公鑰為QA，私鑰為SA。Bob的身份為IDB，公鑰為QB，私鑰為SB。對于簽名或加密模型，由于接收者或者發送者不存在，令ID是與IDU同樣長度的0串，并令IDU=ID，則有SU=S=O，QU=Q=O。其中Q是用戶身份為ID時對應的公鑰。

c)廣義簽密。

(a)簽密 輸入(SA，IDB，m)，為了發送一個消息給Bob，Alice執行

①隨機選取k∈Zq。

②計算，R=kP，S=k-1(H2(m)#8226;Ppub+H3(R)#8226;SA)。

③計算w=e(Ppub，QB)k和c=H4(w)m。

④發送密文σ=(c，R，S)給Bob。

(b)簽名 輸入(SA，ID，m)

①和②與簽密相同。

③計算w=e(Ppub，QB)k=e(Ppub，O)k=1，然后計算c=H4(w)m=H4(1)m=m。

④發送密文σ=(c，R，S)=(m，R，S)給Bob。

(c)加密

①與簽密相同。

②計算R=kP，S=k-1(H2(m)#8226;Ppub)。

③和④與簽密相同。

d)解廣義簽密。當收到密文σ時，Bob執行

①計算w=e(R，SB)，恢復消息m=cH4(w)。

②若等式e(R，S)=e(P，Ppub)H2(m)#8226;e(Ppub，QA)H3(R)成立，Bob接收這個消息，否則認為σ不合法。

廣義簽密方案的正確性驗證:

e(R，S)=e(kP，k-1(H2(m)#8226;Ppub+H3(R)#8226;SA))=

e(P，H2(m)#8226;Ppub+H3(R)#8226;SA)=

e(P，H2(m)#8226;Ppub+H3(R)#8226;sQA)=

e(P，Ppub)H2(m)#8226;e(P，sQA)H3(R)=

e(P，Ppub)H2(m)#8226;e(Ppub，QA)H3R

4 安全性分析

1)機密性

定理1 在隨機預言模型中，若存在一個IND-IBSC-CCA2攻擊者A能夠在t時間內，以ε的優勢贏得定義1的游戲(A最多能進行qi次Hi詢問(i=1，2，3，4)，qs次簽密詢問(或qe次加密詢問)，qu次解簽密詢問(或qd次解密詢問))，則存在一個區分者C，能夠在t′ε#8226;(1/q1q4)的優勢解決BDH問題。其中te表示計算一次雙線性對運算所需要的時間。

證明 區分者接收隨機的BDH問題實例(P，aP，bP，cP)，它的目標是計算出e(P，P)abc。區分者則扮演C的角色，把A作為子程序并扮演IND-IBSC-CCA2游戲中向C提出挑戰的攻擊者。游戲一開始，C發送系統參數給A。 其中Ppub=cP (C并不知道c，c扮演PKG的主密鑰)。 C維護L1、L2、L3、L4、Ls或Le、Lu或Ld六張列表， 這些列表開始均為空，L1，L2，L3，L4分別用于跟蹤A對預言機H1、H2、H3、H4的詢問，Ls用于模擬簽密預言機(或Le于來模擬加密預言機)，Lu用于模擬解簽密預言機(或Ld用來模擬解密預言機)。 這些列表的建立詳細解釋如下:

a)H1詢問。C首先從{1，2，…，q1}中選取一個隨機數ib。假設A不會作重復詢問。對于A的第i次H1詢問，若IDU=ID，C計算QU=0，P=O，SU=0，Ppub=O，并添加(ID，O，O，0)到L1中，回答H1(ID)=O。若i=ib，回答H1(IDU)=bP并設置IDb=IDU;否則從Zq中隨機選取x，計算QU=xP，SU=xPpub，并添加(IDU，QU，SU，x)到L1中，回答H1(IDU)=QU。

b)H2詢問。若(m，h2)在L2中，返回h2;否則從Zq中隨機選取h2，添加(m，h2)到L2中，返回h2。

c)H3詢問。若(R，h3)在L3中，返回h3;否則從Zq中隨機選取h3，添加(R，h3)到L3中，返回h3。

d)H4詢問。若(w，h4)在L4中，返回h4;若w=1，令h4為0構成的二進制串，并添加(w，h4)到L4中;否則，從{0，1}n中隨機選取h4，添加(w，h4)到L4中，返回h4。

e)Extract詢問。假設A在對執行extract詢問前已經執行過H1詢問了。若IDU=IDb，終止模擬;否則在表L1中查找IDU對應的條目(IDU，QU，SU，x)，返回SU。

f)簽密(或加密)詢問。假設A在ID1對ID2和執行此詢問前已經執行過H1詢問了。

①ID1≠IDb

表L1中查找到條目(ID1，Q1，S1，x)，然后從Zq中隨機選取k并計算R=kP。

計算h2=H2(m) (H2(m)可以從上述的H2詢問獲得)。

計算h3=H3(R)H3(R)(可以從上述的H3詢問獲得)。

計算S=k-1(h2Ppub+h3S1)。

計算Q2=H1(ID2)。

計算w=e(Ppub，Q2)k。

計算c=H4(w)m(H4(w)可從上述H4詢問獲得)。

返回(c，R，S)。

②ID1=IDb

從Zq中隨機選取k并計算R=kPpub。

計算h2=H2(m) (H2(m)可以從上述的H2詢問獲得)。

計算h3=H3(R) (H3(R)可以從上述的H3詢問獲得)。

計算S=k-1(h2P+h3bP)，在表L1中查找到條目(ID2，Q2，S2，x)，然后計算w=e(R，S2)。

計算c=H4(w)m(H4(w)可從上述H4詢問獲得)。

返回(c，R，S)。

g)解簽密(或解密)詢問。輸入(c，R，S)，假設A在對ID2執行此詢問前已經執行過H1詢問了。

①ID2≠IDb

在表L1中查找到條目(ID2，Q2，S2，x)。

計算w=e(R，S2)。若wL4返回符號“⊥”;

當為dec詢問還需考慮:若ID1=ID2或ID1L1，返回符號“⊥”;否則在表L1中查找到條目(ID，O，O，0)返回Q1=O。否則繼續執行后面步驟。

計算m=cH4(w)。

若ID1=ID2或ID1L1，返回符號“⊥”;否則計算Q1=H1(ID1)。

若mL2，返回符號“⊥”;否則計算h2=H2(m)。

若RL3，返回符號“⊥”;否則計算h3=H3(R)。

若e(R，S)≠e(P，Ppubh2#8226;e(Ppub，Q1)h3)，則返回符號“⊥”; 否則返回m。

②ID2=IDb

按以下的步驟遍歷表L4中的條目(w，h4)。

當為解簽密詢問時還需考慮:若ID1=IDb，移到表L4中的下一個條目并且重新開始。若ID1∈L1，找到L1中的Q1和;否則移到表L4中的下一個條目且重新開始。否則繼續執行后面步驟。

計算m=cH4(w)。

若m∈L2，計算h2=H2(m);否則移到表L4中的下一個條目且重新開始。

若R∈L3，計算h3=H3(R);否則移到表L4中的下一個條目且重新開始。

若e(R，S)=e(P，Ppub)h2#8226;e(Ppub，Q1)h3成立，返回消息m;否則移到表L4中的下一個條目且重新開始。

若遍歷完L4中所有的條目還是沒有消息返回，則返回符號“⊥”。

在經過多項式有界次上述詢問后，A輸出兩個希望挑戰的身份{IDA，IDB}和兩個消息{m0，m1}。若IDB≠IDb(或IDB≠IDb或者IDA≠ID)，C終止這個模擬;否則隨機選取S∈G1，b∈{0，1}，令R=aP，w(w從H4中隨機選取作為BDH問題的候選答案)，計算c=mbH4(w)，然后返回挑戰密文σ=(c，R，S)給A。A經過第二輪的詢問，這些詢問同第一輪相同。在第二階段模擬結束時，A輸出一個b′作為對b的猜測。若b′=b，C就能輸出w=e(P，P)abc作為BDH問題的答案，即C解決了BDH問題;否則C沒有解決BDH問題。

現在考慮第一階段失敗的情況:從A的角度來看，A和C之間的詢問與A和真正的預言機的詢問如果出現不同，就說發生錯誤了。很顯然，對H1、H2、H3的模擬和真正的語言機是不可區分的。此時，對H4的詢問只是在A或B需要時才發生，所以對H4的模擬也是和真正的隨機預言機不可區分的。對簽密詢問的模擬是不可能失敗的。最后是extract模擬。看一下H1的模擬就會發現，A選擇一個H1詢問，并用一個待解決的BDH實例的群元素bP作為響應。在挑戰中，模擬器身份是A選擇作為接收者的身份的最小概率是1/q1。若不是這種情況，則就說錯誤發生在extract階段。因為若A對身份進行extract時，模擬會終止。

第二階段失敗的情況:所有上述錯誤都可能發生，另外，若A對w=e(P，P)abc執行H4詢問那么C會失敗。但是，若A有ε的優勢攻擊成功，則A就不能失敗。那么A就必須對w=e(P，P)abc執行H4詢問。一旦A進行詢問，L4中必會有足夠的信息讓C解決BDH問題。C解決BDH問題的概率是1/q4。所以C成功解決BDH問題的概率最少為ε#8226;(1/q4q1)。證畢。

2)不可偽造性 本文的方案在適應性選擇消息攻擊下能抗存在性偽造。 若一個敵手能偽造一個本文的簽名，則他也能夠偽造下面的一個簽名方案，這個簽名方案是Paterson方案[6]的一個變體。

a)簽名。簽名者隨機選取k∈Zq，計算R=kP和S=k-1(H2(m)#8226;Ppub+H3(R)#8226;SA)。消息m的簽名為σ=(R，S)。

b)驗證。當收到m的簽名σ時，驗證者檢驗e(R，S)=e(P，Ppub)H2(m)#8226;e(Ppub，QA)H3(R)是否成立， 當且僅當該等式成立時接受此簽名。由于Paterson方案在適應性選擇消息攻擊下能抗存在性偽造，本文的方案也同樣能抗存在性偽造。

3)不可否認性 既然本文的方案是不可偽造的，若Alice確實簽密過一個消息，他就不能夠否認。

5 效率分析

由于對運算比乘法群中的指數運算、加法群中的標量成運算耗時的多，對基于雙線性對的密碼學方案來說，影響整個方案效率的主要因素就是對運算的使用個數，即不可與計算的對運算使用個數越少，效率越高。

表1給出了本文方案與目前存在的基于身份和雙線性對的廣義簽密方案效率比較。用e、 m、p分別表示G2中的指數運算個數、G1中的標量乘運算個數、對運算個數。

表1 簽密功能的性能比較

文獻[3]本文方案

簽名3m+p4m

驗證m+3p2p

加密2m+p3m

解密m+3p2p

簽密3m+pe+4m

解簽密m+3p2e+2p

通過比較可見本文提出的方案無論是用做簽名方案、加密方案還是簽密方案，效率都比較高。

6 結束語

本文基于BDH難題假設提出了目前效率最高的基于身份和對運算的廣義簽密方案，它滿足內部安全性意義抗適應性選擇攻擊下的機密性、不可偽造性和不可否認性，減少了計算比較耗時的對運算的使用個數。但本文方案假設在PKG完全可信的情況下，對于如何防止不可信的PKG情況， 還仍然是值得研究的問題。

參考文獻:

[1]韓益亮， 楊曉元. ECDSA可公開驗證廣義簽密[J]. 計算機學報， 2006，29(11):2003-2012.

[2]SHAMIR A. Identity-based cryptosystems and signature schemes[C]//Advances in Cryptology-CRYPTO’84. Berlin:Springer-Verlag， 1984:47-53.

[3]LAL S， KUSHWAH P. ID based generalized signcryption[R/OL]. (2008-08-04).http://eprint.iacr. org/.

[4]AN J H， DODIS Y， RABIN T. On the security of joint signature and encryption[C]//Advances in Cryptology EUROCRYPT’2002. Berlin:Springer-Verlag，2002:83-107.

[5]PATERSON K G. ID-based signatures from pairings on elliptic curves[J].Electronics Letters，2002，38(18):1025-1026.

[6]ZHENG Y. Digital signcryption or how to achieve cost(signa-tureencryption cost(signature)+cost (encryption)[C]//Advances in Cryptology-CRYPTO’97. Berlin: Springer-Verlag，1997:165-179.