無雙線性配對的無證書簽名方案

王圣寶，劉文浩，謝琪

（1. 杭州師范大學 信息科學與工程學院，浙江 杭州 310012；2. 北京郵電大學 網絡與交換技術國家重點實驗室，北京 100876；3. 合肥新星應用技術研究所，安徽 合肥 230031）

1 引言

公鑰密碼學自 1976年誕生以來，用戶的公鑰如何才能得到高效認證始終是一個熱點研究問題。在基于傳統公鑰證書的密碼方案中，證書的管理過程十分復雜。而在身份基公鑰密碼體制中不存在公鑰證書，但卻不可避免地存在密鑰托管問題。鑒于此，Al-Riyami和 Paterson[1]于 2003年首次提出了無證書公鑰密碼學的全新概念。在文獻[1]中提出了第一個無證書簽名方案，但沒有證明其安全性。

近年來，無證書簽名方案的研究受到廣泛重視，出現了許多新的方案。但是，這些方案或者存在安全漏洞，或者存在計算效率不高的問題。其中，導致計算效率不高的問題主要是因為它們都以雙線性配對作為設計工具。2004年，Yum等[2]首次提出不使用雙線性配對來設計無證書簽名方案。然而，Hu等[3]指出文獻[2]中的方案不能抵抗密鑰替換攻擊，并提出了一個改進的無需雙線性配對的無證書簽名方案。2005年，Huang等[4]提出了針對文獻[1]中簽名方案的密鑰替換攻擊，提出了避免此類攻擊的改進方案，并詳細證明了他們新方案的安全性。同年，Corantla等[5]提出了一個在ROM模型下安全的無證書簽名方案，其安全性基于CDH假設。該方案中，簽名時不需要計算無雙線性配對，但在簽名的驗證過程中則需要 3次雙線性配對運算。2006年，Cao等[6]指出Corantla等[5]的簽名方案仍然不能抵抗密鑰替換攻擊，并給出一個驗證簽名需要 4次雙線性配對運算的改進方案。同年，Zhang等[7]提出了一個無證書簽名方案，其簽名過程無需雙線性配對，但驗證過程則需要4次雙線性配對運算。Choi等[8]于2007年所提出的2個方案在簽名過程中沒有用到雙線性配對，但在簽名驗證過程中至少需要進行1次配對運算。2008年，Duan等[9]提出了無證書不可否認簽名方案，其簽名過程需要2次雙線性配對運算。Liu等[10]提出了標準模型下安全的無證書簽名方案，其驗證過程需要進行多達6次配對運算。Xiong等[11]針對Liu[10]的方案提出了惡意 KGC攻擊，并提出了改進方案，改進方案在驗證階段仍然需要 3次配對運算。同時，Shim[12]指出了 Xiong等[11]的方案不能抗密鑰替換攻擊。2009年，Yuan等[13]提出了標準模型下的無證書簽名方案，其簽名過程無雙線性配對運算，驗證過程需要2次雙線性配對運算。Du等[14]所提出的無證書短簽名方案在簽名的過程沒有用到配對，而且驗證過程只需1次配對運算。

在各種無證書簽名方案的變體類型中，則往往需要更多次數的配對運算。2010年，Jin等[15]提出了無證書多重代理簽名方案，其簽名過程需要4n+4次配對運算。Guo等[16]提出了無證書代理重簽名方案，其簽名過程無需配對運算，但驗證過程需要 6次配對運算。Yang等[17]給出了無證書可轉換加密簽名的模型，并提出了具體方案，其簽名階段沒有用到配對，而驗證階段需進行4次配對運算。2011年，Zhang等[18]首次定義了無證書盲簽名方案，其簽名過程需要進行2次配對運算，驗證過程需要3次配對運算。同年，Yang等[19]設計了可追蹤的無證書門限代理簽名方案，其簽名過程需進行 7n次配對運算，而驗證階段要進行10次配對運算。

本文提出了無雙線性配對運算的高效無證書簽名新方案，并基于離散對數（DL, discrete logarithm）困難假設，在隨機預言模型（ROM）下證明了所提新方案的安全性。與同類方案相比，本文的新方案具有更好的計算效率。

2 預備知識

2.1 困難問題及假設

離散對數問題（DLP, discrete logarithm problem）：設循環群G的階為q，P是它的一個生成元。給定隨機元素Q∈G，計算a∈Zq*，使其滿足Q=aP。

在概率多項式時間內算法A在解決 DLP的優勢定義如下：

離散對數假設：對任意概率多項式時間算法A，AdvDLP(A) 是可以忽略的。

2.2 無證書簽名方案

在無證書簽名方案中，存在3個合法參與者，它們分別是密鑰生成中心（KGC）、簽名者IDi和驗證者IDj。一個無證書簽名方案由如下7個算法構成。

1) 系統建立

輸入安全參數k，輸出系統公開參數params和系統主密鑰。然后，公開params，由密鑰生成中心（KGC）秘密地保管主密鑰。

2) 部分密鑰生成

此算法輸入給定用戶的身份標識IDi、系統參數params和主密鑰，KGC輸出身份該用戶的部分私鑰Di，并通過秘密信道將Di返回給用戶IDi。

3) 秘密值生成

此算法輸入用戶身份標識IDi，系統參數params，輸出該用戶的秘密值xi∈Zq*。

4) 用戶私鑰生成

輸入用戶身份標識IDi、系統參數params、用戶部分私鑰Di及其長期秘密值xi，算法輸出該用戶的私鑰SKi= (xi,Di)。

5) 用戶公鑰生成

輸入用戶身份標識IDi、參數params、部分私鑰Di和長期私鑰xi，輸出用戶公鑰PKi。

6) 簽名

輸入系統參數params、待簽名消息m、簽名者用戶身份標識IDi、其公鑰PKi以及簽名私鑰SKi，最終輸出該用戶針對消息m的簽名σ。

7) 驗證

輸入系統參數params、簽名σ、消息m、簽名者身份標識IDi及其公鑰PKi，若驗證通過，輸出1；否則，輸出0。

2.3 安全模型

本節給出由文獻[13]所定義的關于無證書簽名方案的形式化安全模型，在該模型中，攻擊者被分為AI和AII兩類。

AI：此類攻擊者不掌握系統主密鑰，但它可以替換合法用戶的公鑰。

AII：此類攻擊者可得到系統主密鑰，但是它被禁止替換合法用戶的公鑰。

定義1 在AI類攻擊者攻擊下的不可偽造性：在多項式時間內，若AI攻擊者不能以不可忽略的優勢在如下游戲中獲勝，則稱該無證書簽名方案在適應性選擇消息攻擊下具有不可偽造性(EUF-CLSC-CMA)。

1) 挑戰者C輸入安全參數k，運行系統建立算法，獲得系統主密鑰x和系統參數params，保密主密鑰并將系統參數params交給攻擊者AI。

2) 查詢階段，攻擊者AI執行如下操作。

Hash查詢：AI可以針對任意輸入查詢Hash值。

部分私鑰生成查詢：AI選擇一個身份標識ID，根據參數params和系統主密鑰x，C計算用戶部分私鑰DID，并將其發送給攻擊者AI。

私鑰生成查詢：攻擊者AI選擇一個身份標識ID，挑戰者C根據用戶密鑰生成算法生成用戶ID的私鑰SKID，并將其發送給AI。

公鑰生成查詢：攻擊者AI選擇一個用戶身份標識ID，挑戰者C根據用戶公鑰生成算法生成該用戶的公鑰PKID，并將其發送給AI。

用戶公鑰替換：針對任意身份標識ID，攻擊者AI可以選擇一個新的公鑰來替換原公鑰PKID。

簽名生成查詢：攻擊者AI選擇身份標識IDi和明文m，挑戰者C對IDi進行私鑰生成查詢，然后，計算簽名σ=Sign(IDi,m,SKi)，并將σ發送給AI。

3) 簽名偽造階段：攻擊者AI輸出一個四元組(m*,σ*,ID*,PK*)。定義AI在這個游戲中獲勝，當且僅當：

②攻擊者AI沒有查詢過身份標識為ID*的用戶的部分私鑰；

③攻擊者AI沒有查詢過身份標識為ID*，公鑰為PK*的用戶對消息m*的簽名。

定義2 在AII攻擊者攻擊下的不可偽造性：若在多項式時間內攻擊者AII不能以不可忽略的優勢在如下游戲中獲勝，則稱無證書簽名方案在適應性選擇消息攻擊下具有不可偽造性。

1) 建立階段：挑戰者C輸入安全參數k，運行“系統參數建立”算法，獲得系統主密鑰x和params，并發送x和params給攻擊者AII。

2) 查詢階段：攻擊者AII執行的操作同定義1中的階段2)。

3) 簽名偽造階段：攻擊者AII輸出一個四元組(m*,σ*,ID*,PK*)。定義攻擊者AII在這個游戲中獲勝，當且僅當：

①σ*的身份標識為ID*，公鑰為PK*的用戶對m*的一個有效簽名；

如何解決傳統安全監督檢查工作中的突出問題，構建更加高效、更有質量的安全監督工作模式，不只是單純管理變革的問題，也不是單純應用某項新科技或新技術的問題，應該從管理體系構建、企業應用場景分析、信息技術應用三個方面出發進行系統分析，形成三位一體構建新的工作模式。

②攻擊者AII沒有查詢過身份標識為ID*用戶的長期秘密值xi，并且它也沒有替換過該用戶的公鑰；

③攻擊者AII沒有詢問過身份標識為ID*，公鑰為PK*的用戶對m*的簽名。

定義3 一個無證書簽名方案在適應性選擇消息攻擊下滿足不可偽造的安全屬性，當且僅當任何多項式時間攻擊者贏得上述2個游戲的概率都是可忽略的。

3 新的無證書簽名方案

本節給出新提出的無證書簽名方案。在本方案中，無論是簽名者還是驗證者都不需要進行相對費時的雙線性配對運算。

1) 系統建立階段

輸入安全參數k，輸出2個大素數p、q，滿足q|p-1。設P為循環群G1中任意一個階為q的生成元。選擇安全Hash函數：H1:{0,1}*×G1→Zq*，

H2:{0,1}*→Zq*，KGC隨機選擇主密鑰z∈Zq*，然后計算y=zP，并公開系統參數 (p,q,P,y,H1,H2)，保密系統主密鑰z。

2) 用戶密鑰生成

給定用戶身份標識IDi，KGC隨機選取ri∈Zq*，然后計算Ri=riP，Di=ri+zH1(IDi,Ri)，通過安全信道將Di發給用戶。用戶將其作為部分私鑰，將Ri=riP作為他的部分公鑰。

該用戶隨機選取xi∈Zq*作為其長期私鑰，并生成相應私鑰(xi,Di) ，接著計算Xi=xiP，生成公鑰(Xi,Ri) 。用戶可以通過等式Ri+H1(IDi,Ri)y=DiP是否成立來判斷 KGC發送的部分私鑰是否有效。

3) 簽名

假定用戶A為簽名者，隨機選擇整數a∈Zq*，然后計算TA=aP，h=H2(TA||XA||IDA||m)，s1=a/(xA+DA+h)，s2=xA/(xA+DA+h)，從而得到簽名σ= (h,s1,s2)，并將其與部分公鑰RA一道傳遞給用戶B。

4) 簽名驗證

假定B為簽名驗證者，當收到簽名σ和RA后，B計算h1=H1(IDA,RA)，

4 安全證明

在隨機預言模型下，利用2.3節所描述的安全模型，證明前面所提新方案的安全性。

定理 1 （相對AI的不可偽造性）在隨機預言模型下，若存在一個(EUF-CLSC-CMA)攻擊者AI能在多項式時間內以ε的優勢在定義1中的游戲中獲勝（假設它最多進行qi次Hi查詢，其中，i= 1 ,2），則存在一個算法Q能在多項式時間內以的優勢成功解決離散對數問題。

證明 假設Q是一個關于 DLP問題的有效算法，其輸入為(vP,P)，目標是計算出v。Q設置y=vP，然后利用AI作為子程序試圖解決 DLP問題，并且充當(EUF-CLSC-CMA)游戲中的挑戰者。游戲開始后，挑戰者Q發送 (p,q,P,y,H1,H2)給攻擊者AI，并維持列表L1,L2,LD,LSK,LPK,LS,LV分別用于跟蹤AI對預言機H1,H2、部分私鑰提取、私鑰提取、公鑰提取、簽名和驗證簽名的查詢。注意，每個列表最初被設置為空。

H1查詢：列表L1的格式為 (ID,R,h1)，當Q收到攻擊者AI針對H1(IDi,Ri) 的查詢時，若 (ID,R,h1)已經存在于列表L1中，則返回列表中相應的值給AI。否則，挑戰者Q隨機選取h1∈Zq*，并將(ID,R,h1)加入到列表L1中。

H2查詢：此列表的格式為 (m,ID,X,T,h2,c)，假使挑戰者Q收到AI針對H2(m||ID||T||X)的查詢，Q查找 (m,ID,X,T,h2)是否存在于列表L2之中，若存在則返回相應值給AI。否則，隨機選取c∈{0,1}，設Pr[c=1]=δ。若c=0，隨機選取h2∈Zq*

，并將h2返回給A1，然后將(m,ID,X,T,h2,c)加入列表L2中；若c=1，則令h1=⊥，返回⊥給AI表示終止游戲。

部分私鑰查詢：若(ID,D,R)存在于列表LD中，則返回其中相應的值給AI。否則，挑戰者Q隨機選擇D,h1∈Zq*，并計算R=DP-yh1，然后將(ID,D,R)加入列表LD中，將 (ID,R,h1)加入列表L1中，最后將(R,D)返回給攻擊者AI。

私鑰查詢：若(ID,D,x)在列表LSK中存在，則將列表中相應的值返回給AI。否則，Q查找列表LD得到D，并隨機選擇x∈Zq*，最后將(ID,D,x)插入列表LSK。

公鑰查詢：若(ID,R,X)存在列表LPK中，則將列表中相應的值返回給AI。否則，Q先查找列表LD和LSK，計算X=xP，將(ID,R,X)加入列表LPK中，并將(R,X) 返回給AI；若在列表LD和LSK中不存在，則查找列表L2。若c= 1 ，則Q隨機選取r,x∈Zq*

，并計算R=rP,X=xP，然后將(ID,R,X,c)插入列表LPK，并返回(R,X)；若c= 0 ，則運行部分私鑰查詢獲得(R,D)，然后Q隨機選擇x∈Zq*，并將(ID,D,x)插入列表LSK，接著將(ID,R,X,c)插入列表LPK，并返回(R,X) 。

公鑰替換查詢：假設簽名者的身份標識為ID，攻擊者AI可以任意選取一個新的x′替換掉原先的x，并以新的公鑰R′替換原公鑰R。

簽名生成查詢：挑戰者Q在列表LPK查找若c=1，則放棄；否則，查找列表并隨機選a∈Zq*，計算T=aP，，最后返回簽名σ= (h,s1,s2)給AI。

驗證簽名查詢：Q在列表LPK查詢IDA：①若存在且c= 0 ，則在列表L1中查詢，接著計 算和XA+h1y+hP)；若H2(T'||X'||IDA||m) =h成立，則輸出 1，表示“通過驗證”，否則終止模擬游戲；②若存在且c= 1 ，則在列表L1中查找若存在則輸出 1，表示“通過驗證”，否則終止模擬游戲；③若列表LPK中不存在，則表示公鑰已被替換，則在列表L1中查找，若發現(m,IDA,T',X',h)∈L2，則輸出1，表示“通過驗證”，否則終止模擬游戲。

經過多項式次數的上述查詢之后，AI隨機選取計算然后輸出對m的偽造簽名σ*= (h*,s*)。注意，挑戰者Q掌握被攻擊者替換掉的公鑰。若偽造的簽名有效，則Q輸出v= (a-s*作為DLP問題的答案；否則，Q無法解決 DLP問題。若AI對IDA進行過部分私鑰或私鑰查詢，則Q失敗退出，而AI不進行這2種查詢的概率至少是 1 /q12；如果AI對T'進行過H2查詢，則Q失敗退出，而AI不進行這種查詢的概率大于1/q2。因此，挑戰者Q解決 DLP問題的優勢至少為

定理 2 （相對AII攻擊下的不可偽造性）。在隨機預言模型下，若存在一個(EUF-CLSC-CMA)攻擊者AII能在多項式時間內以優勢ε在定義2中的游戲中獲勝（假設攻擊者最多進行qi次Hi查詢，i= 1 ,2），則存在一個算法Q能在多項式時間內以優勢解決DLP問題。

證明 給定一個隨機 DLP問題實例(p,q,P,aP)，算法Q的目標是計算獲得a。同定理 1的證明，Q試圖以AII為子程序解決 DLP問題，并充當(EUF-CLSC-CMA)游戲中的挑戰者。游戲開始后，Q將系統參數 (p,q,P,y,H1,H2)發送給AII。根據定義，攻擊者AII掌握系統主私鑰z，但不能進行公鑰替換攻擊，其他條件及目標同定理1。

在此攻擊游戲中，AII可以進行定理1證明過程中的除驗證簽名之外的所有查詢。

驗證簽名查詢：Q在列表LPK查找IDA：①若存在且c= 0 ，則在列表L1中查找并計算；若H2(T'||IDA||m)=h成立，則返回“通過”，否則終止游戲模擬；②若存在且c=1，則在L1中查找，若存在則返回“通過”，否則終止游戲模擬；③若列表LPK中不存在該公鑰，則在列表L1中查找，若存在則返回“通過”，否則終止游戲模擬。

在游戲的某個階段，攻擊者AII隨機選取，并計算最后輸出對消息m的偽造簽名σ*= (h*,s*)。若偽造簽名能通過驗證，則挑戰者Q輸出rA= (a-s*(vh1+xA+h*) )/s*作為 DLP問題實例的解；否則，Q不能解決DLP問題。若AII對IDA進行過部分私鑰或私鑰查詢，則Q失敗退出。AII不進行這 2種查詢的概率至少為 1 /q12；若AII對T'進行過H2查詢，則Q失敗退出，AII不進行這種查詢的概率大于 1 /q2。所以，挑戰者Q解決 DLP問題的優勢至少為

5 效率分析

數字簽名方案的效率包括簽名階段和驗證階段的計算量以及簽名長度等。表 1將新方案與已有的具有代表性方案的效率進行了比較。其中，P表示一個雙線性配對運算，S表示群G1中的標量乘法運算，E表示群G2中的指數運算，H表示一個散列運算。另外，P1表示G1中一個元素的長度，P2表示G2元素的長度，而Z1表示Zq*中的整數的長度。

表1 計算量和簽名長度的比較

根據文獻[20]所給出的分析結果，雙線性配對、指數運算與散列運算的計算量分別是標量乘運算的約21倍、3倍及1倍。從表1可以看到，在簽名及其驗證簽名階段，只有文獻[2,3]中的方案與所提出的新方案一樣都沒有用到雙線性配對。但是，它們已被證明是不安全的。而其他所有方案至少需要進行1次雙線性配對運算。在本文所提出的新方案中，簽名為σ= (h,s1,s2)。在計算h時，簽名者需要先計算TA=aP，即1次點乘計算。另外計算h時還需進行一次散列操作，即計算因此計算量總計為1S+1H。類似地，可以計算出簽名驗證階段所需的計算量，即2S+1H。新方案的簽名長度與表1中其他方案相比也具有較大優勢。

6 結束語

本文提出了一個新的無雙線性配對運算的無證書簽名方案。基于離散對數問題假設，在隨機預言模型下證明了其安全性。通過分析表明，新方案的計算效率和簽名長度都優于已有方案。因此，它更適合應用于計算能力和帶寬都受限的場景，例如無線傳感器網絡和ad hoc網絡。

[1] AL-RIYAMI S S, PATERSON, K G. Certificateless public key cryptography[A]. Proc of Asiacrypt 2003[C]. Springer-Verlag, Berlin,2003. 452-473.

[2] YUM D H, LEE P J. Generic construction of certificateless signature[A]. In Information Security and Privacy: 9th Australasian Conference, ACISP 2004[C]. Springer-Verlag, 2004. 200-211.

[3] HU B, WONG D, ZHANG Z,et al. Key replacement attack against a generic construction of certificateless signature[A]. Proc of 11th Australasian Conference on Information Security and Privacy[C]. Melbourne, Australia, 2006. 235-246.

[4] HUANG X, SUSILO, W, MU Y, ZHANG F. On the security of certificateless signature schemes[A]. Asiacrypt 2003[C]. 2005.13-25.

[5] GORANTLA M C, SAXENA A. An efficient certificateless signature scheme[A]. Proc of CIS’05[C]. Springer-Verlag, 2005. 110-116.

[6] CAO X, PATERSON K G, KOU W. An Attack on a Certificateless Signature Scheme[R]. Cryptology ePrint Archive, 2006.

[7] ZHANG Z, WONG D, XU J,et al. Certificateless public-key signature[A]. Security Model and Efficient Construction, ACNS 2006[C].Springer-Verlag, 2006. 293-308.

[8] CHOI K Y, PARK J H, HWANG J,et al. Efficient certificateless signature schemes[A]. Proc of ACNS’07[C]. Springer-Verlag, 2007.443-458.

[9] DUAN S. Certificateless undeniable signature scheme[J]. Information Sciences, 2008, 178 (3): 742-755.

[10] LIU J, AU M, SUSILO W. Self-generated-certificate public key cryptography and certificateless signature/encryption scheme in the standard model[A]. Proc of ACM 2007 ACM Symposium on Information,Computer and Communications Security[C]. Singapore, 2007. 273-283.

[11] XIONG H, QIN Z, LI F. An improved certificateless signature scheme secure in the standard model[J]. Funda Info, 2008, 88: 193-206.

[12] SHIM K A. Breaking the short certificateless signature scheme[J].Information Sciences, 2009, 179 (3): 303-306.

[13] YUAN Y, LI D, TIAN L, ZHU H. Certificateless signature scheme without random oracles[A]. ISA 2009[C]. 2009. 31-40.

[14] DU H, WEN Q. Efficient and provably-secure certificateless short signature scheme from bilinear pairings[J]. Computer Standards and Interfaces, 2009, 31(2): 390-394.

[15] JIN Z, WEN Q. Certificateless multi-proxy signature[J]. Comput Commun, 2011, 34(3): 344-352.

[16] GUO D, WEI P, YU D,et al. A certificateiess proxy re-signature scheme[A]. Proc of Computer Science and Information Technology(ICCSIT)[C]. 2010. 157-161.

[17] YANG B, XIAO Z, LI S. Certificateiess verifiably encrypted signature scheme[A]. Proc of IC-NIDC[C]. 2010. 783-788.

[18] ZHANG L, ZHANG F, QIN B,et al. Provably-secure electronic cash based on certificateless partially-blind signatures[J]. Electron Comm Res, 2011, 10(5): 545-552.

[19] YANG T, XIONG H, HU J. A traceable certificateless threshold proxy signature scheme from bilinear pairings[A]. Proc of APWeb’11[C].2011. 376-381.

[20] CHEN L, CHENG Z, SMART N P. Identity-based key agreement protocols from pairings[J]. Int J Inf Secur, 2007, 6(4):213-241.