層次匿名群簽名的概念與構建

程小剛， 郭韌， 周長利， 陳永紅， 盧正添

(1. 華僑大學 計算機科學與技術學院， 福建 廈門 361021；2. 華僑大學 工商管理學院， 福建 泉州 362021)

群簽名是一種具有中心地位的密碼系統[1-2]，具有匿名和可追蹤的良好特性，在電子投票[3-4]、電子貨幣[5-6]、電子拍賣[7-8]、可信計算[9-10]、車載互聯網[11-13]和隱私保護[14]等領域應用廣泛[15-16].群簽名的概念是1991年由Chaum和Heyst提出的[1].1997年，Camenisch等[17]提出的CS97群簽名方案，在群簽名構建上具有十分重要的意義，其實現群公鑰及簽名的長度、簽名和驗證的計算復雜度都獨立于群的大小，但其安全性基于隨機預言模型(ROM).在標準模型下構建的群簽名一般是利用兩種簽名方案，給群成員的證書為群管理員(GM)的簽名，群成員利用此證書再生成群簽名.GS08中提出的在標準模型下安全的、基于雙線性群的高效非交互零知識證明方案，是第1種可對一大類關系進行零知識證明的方案.因此，GS08被廣泛用于各種標準模型下安全群簽名方案的構建[15].

把單位組織成層次結構的密碼系統有一些相關工作，如基于身份的層次加密(HIBE)[18-20].由于基于身份的加密(IBE)系統中所有用戶的私鑰都由某個中心生成，負擔較重，HIBE系統可由上層單位把下層單位的密匙生成工作委托給下層組織，如身份公鑰Alice.hqu.edu.cn對應的私鑰原來由中心生成，而在HIBE系統中此工作可由中心委托華僑大學來生成(即hqu.edu.cn負責生成所有*.hqu.edu.cn的私鑰)，而華僑大學的私鑰又可由教育部門來生成(即edu.cn負責生成所有*.edu.cn的私鑰)，從而極大地降低了中心的負擔.文獻[21]中提出層次撤銷群簽名的概念，即在撤銷時利用組織的層次結構進行靈活的撤銷.層次群簽名[22-23]可應用于匿名信用卡，在打開簽名時，有多個被組織成層次結構的GM，簽名者是樹的葉子節(jié)點，GM可以打開簽名，但每個GM只能打開本層.

傳統群簽名的匿名性只在本群內是匿名的，其匿名范圍是不可變的.實現自主匿名群簽名的簡單做法是組織樹中的每個單位生成自己的群簽名方案，群成員向每個單位申請加入并獲得相應的私鑰，這樣的缺點是沒有實現單位的層次關系的限制.因此，本文提出一種匿名性可變的層次匿名群簽名的概念，將成員所在的單位組織成層次架構，這樣在生成群簽名時可根據具體的應用自主選擇匿名層次，這與層次撤銷群簽名在某種程度上是一種對偶關系；構建的方案能強制實現單位間的層次關系，即不屬于本單位的成員不能加入與生成群簽名.

1 初步知識

定義1層次匿名群簽名由下列5個概率多項式算法構成.

1) 設置(Setup).GM將部門內所在單位組織成層次結構，葉子節(jié)點是人，即群成員，并生成層次結構中各單位的群公鑰(GPK)和負責成員加入的群私鑰(GSK).

2) 加入(Join).成員申請加入群，GM在核實其身份信息之后，可利用GSK生成其成員私鑰(MSK)，用于生成群簽名.

3) 簽名(Sign).生成群簽名時，成員可選擇其匿名層次，即在從根到其葉子節(jié)點路徑上任選一個單位，對應其群公鑰，利用其MSK生成相應的群簽名.

4) 驗證(Verify).驗證時，驗證方能驗證群簽名的合法性(根據簽名中包含的單位信息)，但不清楚是此群中哪個成員生成的簽名.

5) 打開(Open).當出現爭議時，GM可打開簽名找出真正的簽名者.

由上述定義可見，與普通的群簽名相比，層次匿名群簽名在簽名時，位于葉子節(jié)點的成員可選擇匿名級別，即可選擇從根到其自身路徑上的任一個單位作為匿名范圍，上層單位代表匿名性較高(即把自己隱藏在更大的組中)，而下層單位匿名性較低(即其所在單位成員較少).這樣一個層次匿名群簽名密碼系統就可適應多種不同的需求.

知識簽名是對消息m的簽名，對擁有某個知識(如離散對數、大整數因子分解等)的非交互式零知識證明，通常表示為

SPK{x:x是某個難題的解}(m).

上式中：m是簽名的消息；x是簽名方擁有的秘密知識(即簽名私鑰).

而數學難題是簽名方案對應的公鑰，如著名的基于離散對數和ROM模型的Schnorr簽名方案，公鑰為{g，h，p}，私鑰為x，滿足關系h=gxmodp，其簽名就是

SPK{x:h=gxmodp}(m).

構造為

上式中:r為隨機數；H為ROM的哈希函數；R=grmodp.

驗證方程為

定義2可追蹤性安全定義模型.博弈游戲定義敵手為A，挑戰(zhàn)者為C，即

1) C作為群管理員GM，生成層次群簽名各單位的GPK和GSK，并把GPK發(fā)給敵手A；

2) 利用GPK，A可以向GM申請加入群成為群成員，并得到成員私鑰MSK；A也可以申請得到對某個消息m的群簽名Sm；A還可以要求得到某個群成員的私鑰MSK；

3) A輸出一個消息和簽名對(m，Sm)，如果簽名合法，且A未要求查詢得到過m的群簽名，且簽名不能被GM追蹤為A已經查詢過或攻破過的群成員，則稱A贏得勝利.

可追蹤性安全指沒有多項式時間的敵手A能以高概率贏得上述博弈游戲.

2 層次匿名群簽名的構建

2.1 構建方法

1) 設置(Setup).最上層群公鑰為1個隨機多項式(變量個數對應層次結構高度)，即

axi+byj+czk+dwl+evs+fut+g=0 modN.

而下面每層的單位又有1個公鑰多項式，變量個數逐漸減少，每個最小的組公鑰是1個有2個變量的隨機多項式，即

an-1xin-1+bn-1yjn-1+cn-1=0 modN.

假定樹的高度為n，類似地，倒數第2層組織的公鑰是1個有3個變量的隨機多項式，即

an-2xin-2+bn-2yjn-2+cn-2zkn-2+dn-2=0 modN.

另外，要求生成這些隨機多項式時，從根到葉子節(jié)點上的路徑上所有公鑰多項式中同一個變量的指數是互素的(主要是為了增強匿名性，使上、下層單位之間的群簽名不可鏈接).

2) 加入(Join).當某個成員要加入時，從最底層開始，隨機選擇1個xr，那么，GM利用持有的私鑰(即N的因子分解p和q)，可解出對應的yr滿足

把(xr，yr)代入上一層方程，GM又可以解出zr，滿足

mod依次往上，直到最高層得到用戶的全部私鑰(xr，yr，zr，wr，vr，ur)，滿足

3) 簽名(Sign).最高層公鑰多項式對應的線性化方程為

aX+bY+cZ+dW+eV+fU+g=0 modN.

上式中：X=xi；Y=yj；Z=zk；W=wl；V=vs；U=utmodN.

簽名時，簽名者公布其Xm，Ym，Zm，Wm，Vm，Um，這些公開信息要滿足上述的線性化方程，即

aXm+bYm+cZm+dWm+eVm+fUm+e=0 modN.

然后，零知識證明其擁有相應的私鑰，即知識簽名表示為

SPK{x，y，z，w，v，u:Xm=xi，Ym=yj，Zm=zk，Wm=wl，Vm=vs，Um=utmodN}(m).

類似地，簽名的葉子節(jié)點用戶可選擇從根到其路徑上的任一節(jié)點單位的公鑰多項式，來生成相應的簽名，即層次匿名群簽名.

證明SPK{x:Xm=xi}(m)可高效實現如下：對消息m的知識簽名為(t，T)，其中，t=xH(m)rmodN，r為隨機數，T=rimodN；驗證簽名就是驗證方程ti=XH(m)TmodN是否成立.

4) 驗證(Verify).由上述可知，簽名就是針對某個公鑰多項式的知識簽名SPK，所以，驗證就是驗證SPK是否成立.由于SPK的零知識特性，驗證方只能知道公開的信息{Xm，Ym，Zm，Wm，Vm，Um}，但不知道具體是哪個成員簽署的.

5) 打開(Open).若后期有爭議發(fā)生，GM利用成員加入時保存的相關信息，根據{Xm，Ym，Zm，Wm，Vm，Um}可以很容易追蹤出是哪個成員所做的群簽名.因此，GM可利用GSK=(p，q)計算出Xm對應的成員私鑰xm，從而在自己的數據庫中查找此私鑰是分配給哪個用戶的.

2.2 一個簡單的例子

以簡單的二層組織架構為例(更多的層次只需增加變量的個數即可)，最上層有3個變量的隨機公鑰多項式為

f1(x，y，z)=x5+245y11+137z7+92=0 mod 323(17×19).

設第2層有2個單位，那么，各自可選1個2個變量的隨機多項式作為公鑰，如

f21(x，y)=x7+135y7+31=0 mod 323，

f22(x，y)=x11+231y5+27=0 mod 323.

對于組織1，GM可根據以下步驟生成成員私鑰：隨機取x=3，由f21解出y=202，再把(x=3，y=202)代入f1，解出z=39，容易驗證

f1(3，202，39)=35+245×20211+137×397+92=0 mod 323，

f21(3，202)=37+135×2027+31=0 mod 323，

即此成員的私鑰為MSK=(3，202，39).GM可將此MSK發(fā)給成員，并在自己的數據庫中保存此MSK和對應成員的身份信息，用于以后打開簽名.利用此MSK，成員可以生成群簽名.簽名時，若此成員想實現最大匿名性，那么，可以利用MSK=(3，202，39)和最高層的公鑰多項式

f1(x，y，z)=x5+245y11+137z7+92=0 mod 323，

按以下方式進行簽名.先計算

Xm=35mod 323=243，Ym=20211mod 323=179，Zm=397mod 323=248，

并把(Xm，Ym，Zm)作為簽名的一部分；然后，針對要簽名的消息m，再生成知識簽名，即

SPK{(x，y，z):Xm=x5，Ym=y11，Zm=z7}(m).

最終的群簽名為

(Xm，Ym，Zm，SPK).

驗證簽名時，驗證方要先驗證(Xm，Ym，Zm)是否滿足線性化的公鑰多項式方程，即Xm+245Ym+137Zm+92=0 mod 323是否成立，這里顯然

243+245×179+137×248+92=78 166=242×323=0 mod 323

成立.如果不成立，則拒絕簽名；如果成立，再繼續(xù)驗證上述知識簽名是否合法.

若此成員想生成一個以其所在的組織1為匿名范圍的群簽名，那么，可以利用MSK中的(3，202)，先計算

Xm=37=249 mod 323，Ym=2027=297 mod 323.

然后，生成知識簽名

SPK{(x，y):Xm=x7，Ym=y7}(m).

驗證時，驗證方要先驗證(Xm，Ym)是否滿足線性化的f21，即Xm+135Ym+31=0 mod 323是否成立，這里顯然

249+135×297+31=40 375=125×323=0 mod 323

成立.若成立，再驗證知識簽名是否合法.

3 安全性分析與證明

定理1基于RSA假設，上述層次匿名群簽名時是可追蹤的.

證明：挑戰(zhàn)者C作為GM生成GPK(即一隨機多項式和RSA模數N，變量個數等于組織層次架構高度)，GSK滿足N=pq，并將GPK發(fā)給敵手A進行如下游戲.

1) A可以申請加入群，此時，C只要利用自己的群私鑰GSK生成成員私鑰(即對應于公鑰多項式的解)發(fā)送給A即可.

2) A要求獲得對某個消息相對某個群組的群簽名，此時，C可以利用自己的群私鑰GSK生成相應群組中某個成員私鑰；然后，利用此私鑰生成相應的層次群簽名(即上述知識簽名)即可.

3) A要求獲得某個群成員的私鑰，此時，C利用保存在數據庫中該成員的相關信息查找或生成其私鑰；然后，發(fā)送給A即可.

4) 最后，如果A能夠生成1個合法的群簽名，而GM不能追蹤到該簽名的簽名方(即A沒有查詢過此消息此單位的群簽名，且A沒有從C獲得過本次簽名中所用的成員私鑰)，則稱A贏得此次游戲.如果A能以不可忽略的概率贏得游戲，那么，證明利用A可以攻破RSA假設，即A能夠造出成員私鑰(x′，y′)，滿足群公鑰多項式

ax′i+by′j+c=0 modN.

首先，找到(X′，Y′)，滿足

aX′+bY′+c=0 modN

是簡單的，隨機選擇1個X′，可解此線性方程得到相應的Y′.下面證明要同時獲取x′，y′滿足

x′i=X′，y′j=Y′ modN

是困難的，即

1) 敵手A可先選擇隨機的x′，再計算X′=x′i，那么，根據RSA是隨機置換的假設，X′是隨機的，相應的Y′也是隨機的，所以，要對隨機的Y′取其j次根，即Y′1/j根據RSA假設是困難的；

2) 敵手A也可以選擇已有的X(即從上述游戲中獲取的X)，那么，Y也就確定了，此時，GM就可追蹤到了.

匿名性：由上述構建可見，群簽名就是{Xm，Ym，Zm，…}和SPK，這些顯然都不包含任何成員信息，即驗證方只能驗證簽名是否合法，但不知道是哪個成員做的簽名，即簽名是匿名的.在上述的簽名方案中，由于在簽名時要公布Xm，Ym，Zm等信息，所以，不是完全匿名的，即同一成員相對同一單位所做的群簽名是可鏈接的，不是完全匿名的.但由于要求在根到葉子節(jié)點的路徑上，所有公鑰多項式中的同一個變量的指數是互素的，則根據RSA是隨機置換的假設，公開信息也是隨機的，從而在不同匿名級別的簽名中，同一個成員是不可鏈接的.

因此，一個重要的公開問題就是如何構建完全匿名(即同一成員針對同一單位所做的群簽名也是不可鏈接的)的層次匿名群簽名方案.

4 討論

提出一種新的層次匿名群簽名的概念，將組織的不同部門單位作為層次機構，葉子節(jié)點作為群成員個人，群成員在生成群簽名時，可以選擇自己的匿名層次，即在簽名時可以選擇把自己隱藏在小組或大組之中，方便成員在不同的應用中使用不同的簽名方式.基于多變量多項式、RSA假設和知識簽名技術，構建一個具體的方案，但方案的缺陷在于沒有實現完全匿名，只是有限匿名，即同一個成員對同一個單位所做的群簽名雖然是匿名的，但是是可鏈接的.

因此，下一步重要的研究課題就是如何構建實用、高效的完全匿名的層次匿名群簽名方案.另一工作方向是降低中心管理員負擔，即考慮結合HIBE和文中的層次匿名方案，構建既能實現層次匿名，又能實現層次管理的方案，即上層管理員可以把成員加入等工作委托給下層單位管理員，從而緩解中心管理員的負擔，并考慮如何做到在中心管理員和下層管理員之間合理的工作分配問題，綜合考慮管理員的成員密鑰生成工作、成員撤銷工作及簽名打開等工作的合理分配與協調.