程小剛, 郭 韌, 周長利

1. 華僑大學 計算機科學與技術(shù)學院, 廈門361021

2. 華僑大學 工商管理學院, 泉州362021

1 引言

群簽名[1,2]是指一群人中的任一個人都可以生成合法的簽名, 外界只能驗證此簽名合法但不知道具體是這群人中的哪一個做的簽名, 只有擁有密鑰的群管理員(Group Manager, GM) 才能打開簽名找出真正的簽名者. 由于群簽名同時具有隱私保護和可追蹤的良好特性, 所以是一種具有中心地位的密碼系統(tǒng), 可應用于眾多領域, 如電子投票[3–5]、電子貨幣[6–9]、電子拍賣[10–13]、可信計算[14,15]和車載自組網(wǎng)[16–18] 等等.

群簽名方案中一個重要的問題是成員撤銷問題[19], 即如果一個成員離開群(比如從公司離職) 或成為惡意成員(如做了很多不負責任的簽名) 等, 那么他的簽名能力就要被撤銷.

最簡單的撤銷方法是GM 更新群簽名驗證公鑰, 并給每個合法的群成員重新發(fā)送一個私鑰(排除撤銷的成員), 顯然開銷為O(N), N 是群的大小.

VLR (Verifier Local RevocRevoc) 驗證方本地撤銷[20], 指的是GM 把撤銷成員的信息放入一個列表中, 群簽名時每個合法群成員都要證明自己不在撤銷列表中, 顯然此種方式下每個群簽名的簽名與驗證開銷為O(R), R 是撤銷成員的數(shù)量.

DA (Dynamic Accumulator) 動態(tài)聚集器撤銷[21], 動態(tài)聚集器就是可以把許多數(shù)據(jù)合并成一個數(shù)據(jù),并有高效NIZK 協(xié)議來證明簽名者持有被聚合數(shù)據(jù)中的一個, 此種方式下GM 只要廣播一條短消息給所有簽名者和驗證者即可.

群簽名還有其他多種不同的撤銷方式來適應不同應用場景的需要, 如雙重撤銷[22], 即同時支持兩種撤銷方式: 正常撤銷(不可鏈接撤銷) 和惡意用戶的撤銷(可鏈接撤銷), 正常撤銷后, 群成員不能再生成合法的群簽名, 但其以前做的簽名任然保持匿名, 而惡意成員被撤銷后, 不僅其不能生成新的群簽名, 其以前做的群簽名也喪失匿名性被曝光了; K +L 次條件撤銷[23], 簽名次數(shù)K 次以內(nèi)不可追蹤(完全匿名), 而超過K 次小于K +L 次則GM 可追蹤, 超過K +L 次則任何人都可追蹤了即被曝光; 三重撤銷[24],可以三種不同的方式撤銷群簽名: 根據(jù)已泄露的群成員私鑰撤銷、根據(jù)某個惡意成員的群簽名撤銷和GM強制撤銷.

本文提出一種新的撤銷方式的概念: 層次撤銷, 其支持普通的單個成員撤銷, 然后若某個小組(由多個成員構(gòu)成) 不可信, 則可以撤銷此小組, 當然簡單的方法是對每個成員進行普通撤銷, 但效率非常低; 而層次撤銷中支持高效撤銷一個小組, 其開銷同撤銷單個成員是差不多的; 類似還撤銷大組(由多個小組構(gòu)成)、更大的組等等, 即層次撤銷.

這種層次撤銷群簽名方案可應用于如下的場合: 一個單位里要撤銷某個部門, 若用普通VLR 撤銷群簽名方案, 那么部門中的每個人都要單獨撤銷, 效率很低; 而用本文提出的層次撤銷群簽名方案, 可簡單撤銷此部門, 效率同撤銷單個成員近似. 還有就是如果某個小團體中多人出現(xiàn)問題, 成為惡意成員, 那么可認為此小團體整體不可信, 作為處罰, 就可用本文的方案高效撤銷整個小團體.

同本文相關的工作還有文獻[25,26] 等, 也是采用層次結(jié)構(gòu)組織成員, 成員撤銷采用VLR 撤銷, 主要的區(qū)別在于撤銷時要把每個成員的信息放入RL 中去, 而本文支持高效撤銷一整個小組、大組等等, 即能高效進行整體撤銷.

并基于RSA 假設、多項式、NIZK (非交互零知識證明) 等構(gòu)建了一個具體的方案, 其基本思想是多項式的解作為私鑰, 群簽名就是NIZK 證明簽名者擁有私鑰滿足公鑰多項式; 同一小組的成員其公鑰的值被安排在同一條直線上, 這樣撤銷時公布此條直線方程即可; 而大組所有成員的公鑰被安排在一個平面上,撤銷時公布此平面方程; 以此類推來進行層次撤銷.

本文安排如下: 第2 節(jié)介紹了層次撤銷群簽名的定義和一些預備知識; 第3 節(jié)給出層次撤銷群簽名的具體構(gòu)建; 方案的安全性和效率在第4 節(jié)進行了分析和對比; 最后第5 節(jié)是結(jié)束語和一些值得進一步研究的方向.

2 預備知識

定義1 (可撤銷群簽名) 一般由下面的6 個隨機多項式算法組成:

(1) 設置: 給定一安全參數(shù)K, 群管理員(GM) 生成一個群公鑰(GPK) 可用于群簽名的驗證, 和一群私鑰(GSK) 可用于生成成員私鑰;

(2) 加入: 用戶向GM 申請加入群成為群成員, GM 驗證用戶身份并同意其加入后, 生成成員私鑰并秘密傳給此新成員; 同時保存相關信息以便將來打開此用戶所做的群簽名;

(3) 簽名: 群成員可利用自己的成員私鑰生成對任一消息的群簽名;

(4) 驗證: 任何人獲得GPK 和一個消息/簽名對, 可驗證此群簽名是否合法, 但對合法的群簽名他不能找出實際的簽名者;

(5) 打開: 對于合法的群簽名, GM 能打開并找出實際的簽名者;

(6) 撤銷: GM 可撤消某成員的簽名權(quán)利, 之后此用戶就再也不能生成合法的群簽名.

定義2 (層次撤銷群簽名) 我們的層次撤銷群簽名對上述的加入和撤銷操作進行了擴展:成員加入時, 將相關成員放在同一小組中, 相關小組放在同一大組中, 以此類推.

撤銷時分成下面幾種情況:

(6.1) 撤銷某個成員, 同原來的撤銷功能;

(6.2) 撤銷某個小組, 即撤銷后, 此小組的任一成員都不能生成合法群簽名;

(6.3) 撤銷某個大組, 即撤銷后, 此大組中的任一小組都被撤銷了;

(6.4) 以此類推可撤銷更大的組.

參見圖1, 其中Ln層為群成員, 而L1層為最大的組.

圖1 層次撤銷成員組織圖Figure 1 Membership structure of hierarchy revocation

定義3 (可追蹤性安全定義模型) 博弈游戲定義如下, 敵手為A, 挑戰(zhàn)者C:

(1) C 作為群管理員GM, 生成群公私鑰GPK 和GSK, 并把GPK 發(fā)給敵手A;

(2) 利用GPK, A 可以向GM 申請加入群Join, 成為群成員并得到成員公私鑰MPK 和MSK; A 也可以申請得到對某個消息m 的群簽名Sm; A 可以要求得到某個群成員的私鑰MSK; A 也可以要求GM 撤銷某個群成員;

(3) A 輸出一個消息m 和簽名對(m,Sm), 如果簽名合法(未被撤銷), 且A 未要求查詢得到過m 的群簽名, 且簽名Sm不能被GM 追蹤為A 已經(jīng)查詢過或攻破過的群成員, 則稱A 贏得勝利.可追蹤性安全則指沒有多項式時間的敵手A 能以高概率贏得上述博弈游戲.

定義4 (零知識證明系統(tǒng)(ZK)) 有兩方, 證明者P (Prover) 和驗證者V (Verifier), 通過一個交互協(xié)議, P 要向V 證明他具有某個知識(如離散對數(shù)、整數(shù)的因子分解等), 協(xié)議要滿足下述兩個安全性條件:

(1) 零知識特性: 即V 只能確信P 擁有某個知識, 但不能夠獲取到這個知識的任何信息;

(2) 公正性: P 不能欺騙V, 即如果P 沒有某個知識, 他就不能使V 相信他有.

定義5 (非交互式ZK (NIZK)) 取消上述ZK 協(xié)議中的交互過程, 只要P 要V 發(fā)送一條消息來實現(xiàn)ZK 證明. 如著名的Schnorr 簽名就是一個NIZK, 來證明簽名者擁有作為私鑰的離散對數(shù).

3 層次撤銷群簽名構(gòu)建

3.1 初始普通撤銷群簽名方案構(gòu)建

本方案群公鑰就是一個模N (N 為一安全的RSA 模) 的多項式, 成員私鑰就是此多項式的一個解,群簽名就是NIZK 來證明成員擁有一個解, 如可用文獻[27–30] 等中提出的NIZK 方案.假設群有3 個成員, 則選擇一個有三個變量的隨機多項式如:

N 是一安全的RSA 模數(shù), 給定其中的(i,j,k), 而系數(shù)(a,b,c,d) 待定, 3 個成員隨機選取三組數(shù)

則可代入上式解出 (a,b,c,d), 三個方程四個未知數(shù)是因為上述方程兩邊可同乘以 1/a 得到(1,b/a,c/a,d/a).

如假設我們選定的多項式為(如上所述我們令a=1):

隨機選擇:

可得下面三個方程:

在有理數(shù)上可解得: x=?2702/143, y =?583/26, z =1272082/143, 模N =323 后得到:

即公鑰多項式為:

可驗證(xi,yi,zi),i ∈{1,2,3} 都是此多項式方程的解. 如果GM 想撤銷第一個用戶, 那么他可以令(x1,y1,z1) 為其他值, 再重新生成新的公鑰多項式. 如令(x1,y1,z1)=(7,8,9), 那么方程組為:

可解得: x=?7291/520, y =4559/1040, z =521017/260, 即:

即新的公鑰多項式為:

代入顯然可得f(3,4,5) = 215= 0, 而f(4,5,6) = f(5,6,7) = f(7,8,9) = 0, 即第一個用戶(密鑰為(x1=3,y1=4,z1=5)) 已被撤銷.

也有可能出現(xiàn)的情況是對于隨機選擇的新密鑰, 有可能會出現(xiàn)同余方程組無解的情況; 因為線性方程組一般會有唯一的有理數(shù)解, 但若此有理數(shù)的分母同RSA 模不互素, 則線性同余方程組無解. 比如若上例中我們隨機選擇的新用戶的密鑰為(6,7,8), 則無解, 因此時的線性方程為:

解為: x = ?1436/85,y = ?1941/170,z = 515634/85, 此時(85,323) = 17,(170,323) = 17, 所以同余方程組無解.

但顯然對于安全的RSA 模數(shù)來說, 此種情況出現(xiàn)的概率很低, 并且假若出現(xiàn)也只要重新生成一個新的隨機密鑰即可.

本方案撤銷比較方便方便, 只要GM 更新群公鑰即可, 正常用戶不需要更新私鑰, 但缺點是公鑰過長為O(n), 簽名和驗證效率也較低為O(n), n 是群的大小. 下面我們對此方案進行提高來構(gòu)建我們的層次撤銷群簽名方案.

3.2 層次撤銷群簽名構(gòu)建

下面我們來基于多項式構(gòu)建層次撤銷群簽名方案:

(1) 群公鑰是一個多項式如:

其中N 是一個安全的RSA 模, 變量的個數(shù)決定了可撤銷的層數(shù).

(2) 群成員的私鑰為(x1,y1,z1,w1),(x2,y2,z2,w2),(x3,y3,z3,w3),··· 等等, 都是上述公鑰多項式的解, 即:

注意對任意的(x,y,z), 通常都有相應的w 滿足公鑰多項式方程(如上述分析, 只有極個別情況可能無解).即解空間近似為一個三維空間(x,y,z). 那么在生成私鑰時, GM 先生成X,Y,Z,W, 再利用N 的因子分解來求出成員私鑰x,y,z,w. GM 可把同一小組的成員放在一條直線上, 同一大組成員放在同一平面上.即使同一小組成員的: X =xi,Y =Yj,Z =zk滿足一直線方程. 而同一大組成員X,Y,Z 滿足一平面方程等等. 顯然, 公鑰多項式中的變量個數(shù)同可撤銷的層次式相關的, 即若有n 個變量, 則支持撤銷的層次數(shù)為n ?1. 如本例中有四個變量, 則支持三層撤銷: 單個成員(點)、小組(直線) 和大組(平面).

(3) 群簽名時, 群成員公布自己的Xt,Yt,Zt,Wt, 然后再NIZK 證明:

對SPK{x : xi= X}(m) 的基于ROM 模型構(gòu)建如下[27], 即對消息m 的知識簽名為(t,T), 其中t = xcr mod N, T = rimod N, r 為隨機數(shù), c = Hash(m) (Hash 函數(shù)看作是Random Oracle), 驗證時看ti=XcT mod N 是否成立即可.

此種基于ROM 模型的NIZK 優(yōu)點是簡單, 缺點是安全性較基于標準模型的方案弱. 文獻[28–30] 中的方案是交互式的ZK 協(xié)議不適合構(gòu)建簽名方案, 而且這些方案都是對多項式函數(shù)的根的零知識證明, 此處用的方案比較簡單只是證明擁有一個RSA 簽名.

(4) 驗證當然就是驗證上述SPK 是否合法, 以及下式是否成立:

成立當然說明簽名者擁有公鑰多項式的一個解.

(5) 打開簽名: 利用群簽名中的Xt,Yt,Zt,Wt, 以及成員加入時提供的信息, GM 可簡單的判斷是誰做出的簽名.

(6) 撤銷:

(a) VLR 單個成員撤銷: 把此成員的(X,Y,Z,W) 信息放入撤銷列表RL (Revocation List) 中去, 這樣驗證方很容易判斷一個簽名是否由其簽署;

(b) 小組撤銷: 公布一條直線方程:

到RL 中去, 這樣驗證方可由簽名中的Xt,Yt,Zt,Wt來判斷簽名者是否屬于被撤銷的小組;(c) 大組撤銷: 公布一個平面方程到RL 中去:

下面給出一個具體的例子

例如, 作為公鑰的多項式為:

可取一條直線如下:

任取此直線的兩個點如(為簡化描述, 以下運算都是模323 的運算):

可代入原線性化的公鑰多項式7X +8Y +9Z+10W +2=0 解出對應的

所得的W 值相同, 因為此兩點在同一直線上, 然后GM 利用私鑰可求出相應的成員私鑰:

群成員在簽名時, 先公布(X,Y,Z,W), 然后再零知識證明[31]:

撤銷時, 若撤銷某個成員, 可把他的(X,Y,Z,W) 放入RL 中去即可, 而若要撤銷小組, 可把上述的直線方程:

放入RL 中, 這樣此條直線上的所有成員都被撤銷了.

顯然我們的層次群簽名構(gòu)建是可鏈接的, 即同一成員做的簽名雖然匿名但是可分辨的; 所以一個重要的公開問題就是如何構(gòu)建不可不可鏈接的層次撤銷群簽名方案.

4 安全性分析與效率對比

下面我們來證明上述層次群簽名方案滿足可追蹤性:

定理1 基于RSA 假設, 上述的層次群簽名方案是可追蹤的.

證明: 基于RSA 假設, 下面來證明能贏得上述可追蹤游戲的敵手A 是不存在的:

挑戰(zhàn)者C 作為群管理員生成群公鑰GPK 為N 和一個隨機多項式

私鑰 GSK=(p,q), 滿足N =pq, C 并把GPK 發(fā)給A: 如果A 發(fā)出Join 的請求, 那么C 就利用GSK生成一個MSK=(xi;yi;zi;wi) 發(fā)送給A; 如果A 發(fā)出Sign 的請求, 那么C 就利用任意群成員的MSK來生成群簽名

并發(fā)送給A; 如果A 發(fā)出Corruption 的請求, 要求得到對應某個群成員公鑰MPK=(X;Y;Z;W) 的成員私鑰, 那么C 就利用GSK 來計算對應的MSK=(x;y;z;w), 滿足:并把此MSK 發(fā)給敵手A; 如果A 發(fā)出Revoke 的請求, 那么就把此成員的MPK = (X;Y;Z;W) 放到撤銷列表RL 中去.

最后輸出階段, 來看A 的輸出, A 能贏得可追蹤的游戲, 即敵手A 能偽造簽名, 即A 能造出(?x,?y,?z, ?w), 滿足公鑰多項式且不同于任一組成員的私鑰, 即:

且

那么下面來證明這樣的敵手A 是不可能存在的, 否則就違反了RSA 假設:

首先, 易見生成(X,Y,Z,W) 滿足方程

是容易的, 只需要隨機選擇(X,Y,Z), 然后再解一個線性方程就可求出對應的W; 對于A 來說困難在于如何生成成員秘鑰(x,y,z,w) 滿足

因A 沒有對應的GM 私鑰p,q :N =pq, 即RSA 模的因子分解.

由于(?X, ?Y, ?Z, ?W) /∈{(Xi,Yi,Zi,Wi)}, 必定有:

因為W 可由(X,Y,Z) 唯一確定(他們滿足一個線性方程), 不失一般性假設?Z /∈{(Zi)}:

(1) 如果ADV 先選定?z, 再計算?Z = ?zkmod N, 那么根據(jù)RSA 是隨機置換的假設?Z 就是隨機的,類似的可以生成隨機的 ?X 和?Y, 那么由之而確定出來的 ?W 也是必然是隨機的, 根據(jù)RSA 假設,給定一個隨機數(shù) ?W, 來計算相應的?w, 即其l 次方根是困難的.

(2) 如果如上所述, 先生成(?X, ?Y, ?W), 再計算?Z, 那么類似上述?Z 是隨機的, 那么根據(jù)RSA 假設計算?z = ?Z1/kmod N 就是困難的.

所以, 根據(jù)RSA 假設, 能贏得可追蹤游戲的敵手A 是不存在的.

關于匿名性, 我們的方案只滿足有限匿名的特性, 即驗證方不能知道簽名者的身份信息, 因為簽名中公布的(X,Y,Z,W) 都是隨機值, 在加上NIZK, 都不會暴露簽名者身份; 但同一成員所做的簽名是可以被分辨出來的, 因簽名中用的是相同的(X,Y,Z,W), 而GM 利用其數(shù)據(jù)庫中保存的成員加入時提供的信息可知道其身份.

效率比較參見表1, 表中N 是群的大小, 即群成員的人數(shù); R 表示被撤銷成員的個數(shù); L 表示可撤銷的層數(shù); 更新私鑰是指在GM 撤銷成員時, 合法的群成員需不需要更新自己的私鑰; VLR 方案的驗證開銷為O(R), 是因為驗證方要對RL 中的每一項來進行檢驗; DA 方案的撤銷開銷為O(N), 因為每個未被撤銷的群成員都要更新自己的私鑰, 所以撤銷一個成員對整個群來說總體開銷為O(N); NFHNF 方案比較高效, 主要缺點為公鑰較大為O(N); 綜合來看目前最高效的可撤銷群簽名方案是LPY 方案, 公鑰為O(log N), 簽名驗證效率都為常量級O(1), 而且撤銷成員是合法群成員也不需要更新私鑰, 只是撤銷開銷為O(R). 表中也對各個方案所基于的數(shù)學假設, 和是否基于ROM 模型進行了比較; LPY 方案是基于標準模型, 安全性較高, 但其所基于的數(shù)學假設較復雜.

作為引例的我們的第一個方案效率較低, 公鑰大小為O(N), 簽名驗證的效率都為O(N), 撤銷成員的開銷也是O(N), 優(yōu)點就是撤銷時合法成員不用更新私鑰; 我們的第二個方案效率有所提高, 公鑰大小、簽名效率是O(L), 即依賴于所需要撤銷的層次數(shù), 驗證效率是O(R)/O(1), 即假如撤銷的單個成員, 那么驗證效率是O(R), 而假如撤銷的是一組成員, 那么效率比較高近似為O(1), 撤銷操作也比較高效為O(1),即GM 只要把相關信息放入RL 中即可.

總體上看, 我們的方案的效率同其他可撤銷群簽名方案相比, 效率上并沒有優(yōu)勢, 但我們的方案時支持層次撤銷的, 具有其他方案所沒有的可撤銷小組、大組、更大組的功能.

表1 效率與安全性比較Table 1 Comparison of efficiency and security

5 結(jié)束語

本文提出一種新的群簽名撤銷的概念: 層次撤銷, 即把所有成員組織成小組、大組、更大的組等這種層次結(jié)構(gòu), 這樣撤銷時可選擇撤銷個人、小組、大組等.

基于RSA 假設、多項式、NIZK 等技術(shù)給出了一個具體的方案, 撤銷時對未撤銷的用戶沒有任何影響, 只要GM 把成員、或小組或大組的相關信息加入RL 中即可, 簽名驗證者下載RL 后即可驗證簽名是否合法(即VLR 撤銷), 但比傳統(tǒng)VLR 撤銷更高效, 因傳統(tǒng)VLR 的RL 中每一項只能撤銷一個成員, 而我們的方案的RL 中一項既可以撤銷一個成員, 也可以撤銷一組成員.

但我們構(gòu)建方案的缺點是簽名是可鏈接的, 即同一群成員的簽名雖然是匿名的, 但是可被發(fā)現(xiàn)是同一成員簽署的; 所以一個重要的公開問題就是如何構(gòu)建不可鏈接的層次撤銷群簽名方案.