關聯的無證書環簽名方案*

劉純璐 ，游 林

（1.杭州電子科技大學 通信工程學院，浙江 杭州 310018；2.杭州電子科技大學 網絡空間安全學院，浙江 杭州 310018）

0 引 言

2001年，環簽名由Rivest等人[1]首次提出，允許簽名者在保持匿名的情況下代表所有環成員對消息進行簽名。簽名者任意選取n個成員公鑰，結合自己的私鑰就可以生成一個首尾閉合的環狀簽名，起到保護簽名者隱私的作用。它在需要長期保存信息的一些特殊應用中非常實用，但卻為違法犯罪分子的不良行為提供了庇護。為此，針對具有關聯性、可追蹤性等特殊性質的環簽名研究為更多的實際應用場景提供了可能。2003年，Al-Riyami等人[2]首次提出無證書公鑰密碼體制。用戶從自己的基本信息中提取公鑰，隨機選擇秘密值與密鑰生成中心（Key Generation Center，KGC）為用戶生成的部分密鑰結合生成相應的私鑰。從而有效地簡化了傳統公鑰密碼體制的證書管理問題，也避免了基于身份的公鑰密碼體制[3]的密鑰托管問題。

2014年，Liu等人[4]提出了一個具有無條件匿名性的關聯的環簽名方案，該方案在環簽名的基礎上添加關聯參數，由此可以判斷任意兩個簽名是否由同一個簽名者簽發。2017年，Zhang等人[5]將環簽名與無證書公鑰密碼學相結合，提出了具有三個雙線性對運算的無證書環簽名方案。2018年，Gu等人[6]在標準模型中提出了一個可追蹤的無證書環簽名方案。本文提出了一個新的關聯的無證書環簽名方案，在保證高效率的同時實現了安全模型下的可證明安全。

1 關聯的無證書環簽名方案

關聯的無證書環簽名方案的合法參與者包括KGC、n個簽名者、簽名驗證者和關聯驗證者，由系統初始化、部分密鑰生成、秘密值生成、私鑰生成、公鑰生成、簽名生成、簽名驗證和關聯驗證8個函數組成。其中，圖1描述了方案的密鑰生成過程以及圖2描述了方案的模型流程圖。

圖1 密鑰生成過程

圖2 關聯的無證書環簽名方案模型

（1）系統初始化：輸入安全參數λ，KGC選取素數階為p的循環加法群G，P是G的生成元。隨機選擇主密鑰計算系統主公鑰并且將和作為三個系統哈希函數。最后，將系統公共參數集合公開，并且秘密保存系統主密鑰θ。

（2）部分密鑰生成：輸入用戶身份IDi、θ和param，KGC隨機選擇ri∈Zp*，計算Ri=riP，Qi=H(IDi,Ri,Ppub)和Si=ri+θQimodp。然后，KGC將用戶的部分私鑰ppki=(Si,Ri)通過安全渠道發送給用戶。通過檢驗Ri+QiPpub=SiP等式是否成立，用戶可以驗證部分密鑰的正確性。

（3）秘密值生成：輸入param和IDi，用戶隨機選取為秘密值。

（4）私鑰生成：用戶生成私鑰ski=(xi,Si)。

（6）簽名生成：該函數由身份為IDπ的簽名者運行，輸入參數集合(event,n,PK,skπ,m)。其中，參數分別表示事件event、環的大小n、公鑰集合PK=(pk1,pk2,…,pkn)、簽名者私鑰skπ以及消息m。簽名者私鑰為skπ=(xπ,Sπ)，計算如下：

1）計算e=H′(event)，t=xπe；

2）取rx,ry,c1,…,cπ-1,cπ+1,…,cn∈R Zp*，并計算：

3）為了得到cπ的值，計算c1+…+cnmodp=H′(PK||event||t||m||K||K′)；

（7）簽名驗證：輸入參數集合(event,n,PK,δ)，計算驗證等式是否成立。若成立，則輸出“TURE”，否則，則輸出“FALSE”。

（8）關聯驗證：輸入 (event1,n1,PK1,m1,δ1)和(event2,n2,PK2,m2,δ2)，分別對其檢驗簽名的有效性。若δ1=(t1,·)和δ2=(t2,·)都為有效簽名，且t1=t2，則兩個簽名“關聯”，否則，“不關聯”。

2 安全性證明

我們將基于橢圓曲線離散對數困難問題，在隨機預言模型中證明關聯的無證書環簽名方案針對第Ⅰ類型敵手AⅠ和第Ⅱ類型敵手AⅡ都具有不可偽造性的安全特性。

定理2.1：基于離散對數問題是困難的假設前提下，在隨機預言機模型中關聯的無證書環簽名針對第Ⅰ類型敵手AⅠ具有不可偽造性。

證明：假設AⅠ具有不可忽略的優勢ε1來攻破我們提出的方案。我們要證明多項式時間函數挑戰者B能夠利用AⅠ來解決離散對數問題，即根據已知隨機實例(P,xP)來確定x的值。

在系統初始化階段，B輸入一個安全的參數λ，輸出主密鑰θ和系統公共參數集合param。B將param=(G,p,H,H′,H′,P,Ppub)發送給AⅠ，另外秘密保存θ。

（1）H′哈希值查詢：對于H′哈希值的查詢，挑戰者B隨機選擇計算并返回αP的值。

（2）H、H′哈希值查詢：對于未分配的哈希值查詢，B隨機選擇并返回。

（3）部分密鑰查詢：當AⅠ查詢身份為IDi用戶的部分密鑰，其中被查詢用戶的身份IDi不是目標身份IDⅠ。B首先隨機選取正整數計算得Ri=siP-hiPpub。然后，B返回部分密鑰ppki=(Ri,si)給AⅠ。

（4）秘密值查詢：當AⅠ查詢用戶的秘密值，B將隨機選取并返回給AⅠ。

（5）公鑰查詢：當AⅠ查詢身份為IDi用戶的公鑰，其中被查詢用戶的身份IDi不是目標身份IDⅠ。B首先進行秘密值查詢和部分密鑰查詢，然后計算得pki=(xi+Si)P。

（6）公鑰替代查詢：當AⅠ對用戶的公鑰pki進行公鑰替代查詢，B可以實現將pki′替代原公鑰pki。

（7）環簽名查詢：當AⅠ對輸入的參數集合(event,n,PK,skπ,m)進行環簽名查詢，B將進行以下過程：

1）如果H′(event)未賦值，首先對事件event運行哈希查詢H′，計算得到e=H′(event)=αP，并計算得t=xπe。

3）B輸出簽名

如果AⅠ為身份為IDⅠ的目標用戶以不可忽略的概率優勢ε1成功輸出環簽名這說明B至少能以1/qH×(1-1/qH)qn×ε1的優勢解決橢圓曲線離散對數問題，其中qH代表對哈希查詢H進行的最大查詢次數，qn代表對部分密鑰查詢的最大查詢次數。然而，這與橢圓曲線離散對數問題困難假設相矛盾，即AⅠ無法為目標用戶以不可忽略的概率優勢ε1成功輸出

定理2.2：基于離散對數問題是困難的假設前提下，在隨機預言機模型中關聯的無證書環簽名對第Ⅱ類型敵手AⅡ具有不可偽造性。

證明：假設AⅡ具有不可忽略的優勢ε2來攻破關聯的無證書環簽名方案。我們要證明多項式時間函數B能夠利用AⅡ來解決離散對數問題，即根據已知隨機實例(P,xP)來確定x的值。

在系統初始化階段，輸入一個安全的參數λ，輸出系統主密鑰θ和系統公共參數集合param。然后，B將param=(G,p,H,H′,H′,P,Ppub)和θ通過安全信道都發送給AⅡ。

在這整個過程中，哈希查詢、公鑰查詢、環簽名查詢的細節與上述定理2.1的證明過程相同。但是，AⅡ具有主私鑰θ，可以自主計算出部分私鑰ppki。如果AⅠ為身份為IDⅠ的目標用戶以不可忽略的概率優勢ε2成功輸出環簽名δ*={t*,x~*,y~*,c1*,…,cn*}。這說明B至少能以 1/qH×(1-1/qH)qm×ε2的優勢解決橢圓曲線離散對數問題，其中qH代表對哈希查詢H進行的最大查詢次數，qm代表對秘密值的最大查詢次數。然而，這與橢圓曲線離散對數問題困難假設相矛盾。

3 性能分析

我們從運算代價和性能將本方案與同類型簽名方案進行對比，比較結果如表1所示。為方便起見，我們將E表示指數運算，M表示多次冪指數運算，其運算代價約E的1.3倍，P表示雙線性對運算，TE表示橢圓曲線上的標量乘法運算，以及TPO表示基于配對的標量乘法運算。

表1 簽名方案性能比較

由上表可知，同類型簽名方案的運算代價主要集中在證書管理以及簽名和驗證運算過程中。在Liu等人[4]提出關聯的環簽名方案中，證書管理的開銷會隨著環成員的增加而呈線性增長。Gu等人[6]提出可追蹤的無證書環簽名方案需要大量的雙線性計算，而雙線性對計算會造成很大的運算代價。相較于其他兩個方案，我們的方案在整個簽名運算過程中克服了證書管理問題，減少對可信第三方的依賴程度，并且降低了雙線性對計算100%的運算量。

4 結 語

本文在無證書環簽名算法的基礎上添加關聯參數，在隨機預言機模型中提出了一個具有高安全性和低運算量的關聯的無證書環簽名方案。在橢圓曲線離散對數問題是困難的假設前提下，我們針對該方案在選擇消息攻擊下的兩種典型攻擊進行了驗證，結果表明該方案具有不可偽造性。在整個運算過程中，主要的運算量集中于證書管理和雙線性對計算。與同類型的簽名方案相比，我們提出方案克服了證書管理問題，并且降低了雙線性對計算100%的運算量，運算效率有顯著的提升，在電子選舉、數字貨幣等網絡環境中得到著更好地應用。