支持一般電路的高效安全基于屬性簽名

黃振杰 林志偉,2

1（福建省粒計算及其應用重點實驗室（閩南師范大學）福建漳州 363000）

2（交通運輸部東海航海保障中心廈門通信中心 福建廈門 361026）

基于屬 性簽名（attribute-based signature，ABS）[1]是一種特殊數字簽名體制，可以為用戶提供細粒度的隱私保護，在多個領域有重要應用，因此成為密碼學的研究熱點.

ABS 的隱私保護控制是通過屬性和屬性集上定義的訪問結構實現的.根據訪問結構使用位置的不同，基于屬性簽名分為密鑰策略ABS（key-policy attributebased signature，KP-ABS）和簽名策略ABS（signaturepolicy attribute-based signature，SP-ABS）.在KP-ABS 中，用戶從屬性機構（attribute authority，AA）處獲得其所擁有的訪問結構所對應的簽名密鑰，之后可用其對屬性滿足其訪問結構的消息進行簽名.簽名可以確保消息是由擁有能被指定屬性滿足的訪問結構的用戶簽發的（不可偽造性），但不能辨認出簽名人所擁有的具體訪問結構，更不能辨認出簽名人的身份（隱私性）.SP-ABS 則相反，用戶從屬性機構處獲得其所擁有的屬性所對應的簽名密鑰，然后對具有其屬性所滿足的訪問結構的消息進行簽名.

舉個簡單的說明性例子：ABS 可為教學管理系統提供匿名評價功能.假設每個課程都表示為“課程名稱、開課教師姓名、開課年份、開課學期”，那么每位學生所選的課程組可以表示成(C1∧T1∧Y1∧S1)∨(C2∧T2∧Y2∧S2)∨···∨(Ck∧Tk∧Yk∧Sk)，其 中Ci,Ti,Yi,Si分別表示課程名稱、開課教師姓名、開課年份和開課學期.在學生選定其課程組后，系統根據其所選課程組所對應的訪問結構為其發放簽名密鑰，此后，學生可以使用其簽名密鑰匿名發表課程評價.ABS 的不可偽造性保證只有選修的學生才能對課程進行評價，其隱私性保證任何人都不能辨認出評價出自哪位學生.不可偽造性保證評價來源的合法性，隱私性保障評價者的隱私權.

由于其良好的性質，ABS 在許多領域有重要的應用，如匿名憑證（anonymous credentials）、消息傳遞（message delivery）、匿名認 證（anonymous authentication）、秘密泄露（leaking secrets）、信任協商（trust negotiations）、隱私接入控制（private access control）等等[1-2].

自ABS 被提出以來，眾多學者先后提出許多支持各種不同訪問結構的方案.Shahandashti 等人[2]、Li等人[3]、Herranz 等人[4]和Gagne 等人[5]各自提出支持門限（threshold）訪問結構的ABS 方案；Maji 等人[1]和Gu 等人[6-7]各自提出支持單調（monotone）訪問結構的ABS 方案；Okamoto 等人[8-9]提出支持非單調（nonmonotone）訪問結構的ABS 方案；Tang 等人[10]和Sakai 等人[11]各自提 出電路（circuits）訪問結構的ABS 方案；Kaafarani 等人[12]提出無界電路（unbounded circuits）訪問結構的ABS 方案；Zhang 等人[13]提出支持內積（inner-product）訪問結構的ABS 方案；Datta 等人[14]提出無界算術分支程序（unbounded arithmetic branching programs）訪問結構的ABS 方案.

為了克服ABS 單個屬性機構帶來的瓶頸和信任過度集中的問題，Maji 等人[1]和Okamoto 等人[15]分別提出多屬性機構（multi-authority）ABS 和去中心（decentralized）ABS.為了克服ABS 計算開銷過大，不適用于資源受限場景的缺點，學者們將外包技術引入到ABS 中來，Chen 等人[16]提出外包（outsourced）ABS，Mo 等人[17]和Sun 等人[18]分別提出新的外包ABS 方案.Huang 等人[19]指出已有外包ABS 方案的隱私性缺陷，進而提出具有完善隱私性的外包ABS方案.Ren 等人[20]進一步提出可驗證（verifiable）外包ABS；Cui 等人[21]和Xiong 等人[22]研究了服務器輔助（server-aided）ABS；Wang 等人[23]提出服務器輔助驗證（server-aided verification）ABS.

此外，學者們還研究了具有附加性質的ABS，如基于屬性環簽名（attribute-based ring signature）[24]、基于屬性代理簽名（attribute-based proxy signature）[25]、基于屬性簽密（attribute-based signcryption）[26]、基于屬性凈化簽名（attribute-based sanitizable signature）[27]等.

ABS 研究的主要目標是更高的安全性、更高的效率和更強的訪問結構表達力.電路是最富表達力的訪問結構之一.目前已知有3 個ABS 方案支持電路訪問結構：Tang 等人[10]的方案、Sakai 等人[11]的方案和Kaafarani 等人[12]的方案.文獻[11?12]方案的效率都很低，簽名的長度都與電路的輸入成線性關系.Tang等人[10]的方案的簽名僅為1 個群元素，效率最高，但在安全性和訪問結構表達力方面卻比較弱：

1）Tang 等人[10]方案的不可偽造性是很弱的，只是在選定消息和選定屬性攻擊下存在不可偽造，只能防止敵手偽造特定消息的簽名.

2）Tang 等人[10]的方案僅支持特殊電路，要求兄弟節點的深度必須相同，且都是其父節點的深度加1；要求所有輸入節點的深度相同.

本文改進了Tang 等人[10]的方案，提高了安全性、豐富了訪問結構表達力、縮短了數據長度并降低了計算開銷.本文的主要貢獻包括3 個方面:

1）增強方案的安全性.從“選定消息和選定屬性攻擊下存在不可偽造（existentially unforgeable under selective message attack and selective attribute,EUF-sAsMA）”提升到“自適應選擇消息但選定屬性攻擊下存在不 可偽造（existentially unforgeable under adaptive chosen message but selective attribute attack,EUF-sACMA）”.EUF-sA-CMA 比EUF-sA-sMA 強很多，能防止敵手偽造任何自適應選擇消息的簽名.

2）豐富了訪問結構表達力，將訪問結構從特殊電路拓展到一般電路.去掉原有的所有限制，允許兄弟節點的深度不同；允許孩子節點的深度比其父節點的深度大于1，即可以跳層；允許輸入節點的深度不同.另外，任意電路都可以通過德·摩根（De Morgan）定律轉換成非葉子節點為“或門”或“與門”，“非門”只出現在葉子節點的電路.如果將帶“非門”的葉子節點定義為1 個新屬性（比如“不是教授”）作為1 個新的輸入，就可以支持非單調電路.一般電路的極強表達能力使得方案可支持任意訪問結構，達到任意的訪問控制粒度.

3）縮短了數據長度并降低了計算開銷.在保持簽名大小僅為1 個群元素的前提下，將主公鑰、主私鑰和簽名鑰的大小都顯著縮短；將簽名密鑰生成、簽名生成和簽名驗證的計算開銷都顯著降低.

1 預備知識

1.1 符號說明

本文使用的符號和參數的含義如表1 所示.

1.2 多線性映射與困難性假設

多線性映射.G(1λ,k)為群生成算法，輸入安全參數 λ和多線性映射級數k，輸出素數p階群序列G1,G2,···,Gk和相應的生成元g1,g2,···,gk，以及雙線性映射序列ei,j：Gi×Gj→Gi+j，1 ≤i≤k?1,1 ≤j≤k?1,i+j≤k，滿足

多線性映射定義為e(a1,a2,…,an)=e(a1,e(a2,…,e(an?1,an)…))，其中右側的e為其輸入所對應的雙線性映射ei,j.

Table 1 Symbols Interpretation表1 符號釋義

k-MCDH 假設.任意概率多項式時間算法 A 成功解k-MCDH 問題的概率都是可忽略的.

1.3 電 路

假設電路有n個輸入節點，q個門節點，記輸入節點集合為I={1,2,···,n}，門節點 集合為G={wn+1,wn+2,…,wn+q}，所有節 點集合 為N=I∪G，其 中wtop=wn+q為頭部節點.門節點w的左、右孩子節點分別記為L(w)和R(w).GT(w)表示門節點w的類型，即“AND”或“OR”.電路記為f=(n,q,L,R,GT).

D(w)表示節點w的深度.頭部節點的深度為0，其他節點的深度為其到頭部節點的最長路的長度.f(?)表示輸入為? ∈{0,1}n時，電路f的輸出.當f(?)=1時，稱 ?滿足f；否則，稱 ?不滿足f.類似地，fw(?)表示輸入為 ?時，電路f中門節點w的輸出.

為了有效降低計算開銷，本文為電路引入節點權重的概念，用Ww(?)表示在輸入為 ?時節點w的權重，其計算方法如1）～3）：

1）輸入節點.

①輸入為1 的節點，Ww(?)=n?1；

② 輸入為0 的節點，Ww(?)=∞.

2）或門.

①如果fw(?)=0，則Ww(?)=∞；

② 否則Ww(?)=min{WL(w)(?),WR(w)(?)}+2.

3）與門.

①如果fw(?)=0，則Ww(?)=∞；

② 否則：

如果D(L(w))=D(R(w))，則

如果D(L(w))≠D(R(w))，則

這樣定義的節點權重其實就是使用本文方案生成簽名時，使用該節點所需要計算的對運算的數量.對運算越少，效率就越高.

圖1 給出一個一般電路的說明性例子：

Fig.1 Example of general circuit圖1 一般電路示例

2 電路訪問結構密鑰策略ABS

本節給出訪問結構為電路的密鑰策略ABS 的定義和安全模型.

2.1 算法組成

電路訪問結構密鑰策略ABS 方案由1）～4）算法組成：

1）Setup(1λ,n,?).輸入安全參數 λ、電路輸入數n和最大深度?，輸出系統公開參數pp和系統主私鑰msk.

2）KeyGen(pp,msk,f).輸入系統公開參數pp、系統主私鑰msk和電路f，輸出電路f所對應的簽名密鑰S Kf.

3）Sign(pp,S Kf,M,?).輸入公開參數pp、簽名密鑰S Kf、消息M及其屬性 ?，輸出關于(M,?)的簽名 σ.

4）Verify(pp,M,?,σ).輸入公開參數pp、消息M、屬性 ?和簽名 σ.如果 σ是關于(M,?)的有效簽名，輸出1；否則，輸出0.

2.2 安全性模型

定義1.正確性.一個電路訪問結構的密鑰策略ABS 方案是正確的，如果對于任意的消息M和滿足f(?)=1的任意屬性 ?與電路f都有概率，則

不可偽造性.大多數ABS 的文獻使用如下不可偽造性定義，其形式化模型如Game1：

Ga me1（EUF-sA-CMA）.

1）Initialization.敵手 F選擇挑戰屬性 ??并發送給挑戰者 C.

2）Setup.挑戰者 C生成系統公開參數pp并發送給敵手 F.

3）KeyGen Oracle.敵 手 F提交電 路f給挑戰 者C .C返回電路f的密鑰S Kf給 F.

4）Sign Oracle.敵手 F提交消息M和屬性 ?給挑戰者 C .C返回(M,?)的簽名 σ 給 F.

5）Forgery.敵手 F輸出(σ*,M*,??).

如果下面①～③都滿足，稱敵手贏得Game1.

①σ*是關于消息M*和屬性 ?*的有效簽名；

② (M*,?*)沒有被詢問過Sign Oracle；

③任何詢問過KeyGen Oracle 的電路f都 使f(??)=0.F

定義2.一個電路訪問結構密鑰策略ABS 方案稱為自適應選擇消息但選定屬性攻擊下存在不可偽造的；如果對于任何多項式時間敵手 F，其贏得Game 1的優勢是可忽略的.

Tang 等人[10]方案的不可偽造性是很弱的“選定消息和選定屬性攻擊下存在不可偽造”，其Game 和Game1 基本相同，只是Initialization 應改為：

Initialization.敵手 F選擇并發送挑戰消息M?和挑戰屬性 ??給挑戰者 C.

完善隱私性.本文方案和Tang 等人[10]方案都實現了完善隱私性，任何敵手即使擁有無限的計算能力也無法識別用于生成簽名的電路.

定義3.如果對于任何M，?和滿足f0(?)=f1(?)=1的f0,f1，使用f0和f1所產生的簽名分布

是信息論意義不可區分的，則稱該電路訪問結構密鑰策略ABS 方案具有完善隱私性.

3 一般電路密鑰策略ABS 方案

本節提出一個支持一般電路的密鑰策略ABS 方案.

3.1 主要設計思想

本文方案是基于Tang 等人[10]方案改進而來的，改進的主要思想如1）～4）所描述：

1）以唯一的頭部節點為參照原點，其他節點都參照它進行定位，以便支持一般電路.而Tang 等人[10]方案采用葉子（輸入）節點為參照原點，所以需要假設所有輸入節點均有相同的深度.

2）引入節點權重的概念并采用“從上到下”遞歸的方式計算簽名，只計算必須計算的且權重較小的節點的Ew.而Tang 等人[10]方案“自下而上”計算所有輸出為1 的節點的Ew，許多不必要的Ew也計算了，浪費了計算資源.

3）充分利用左右孩子節點的對稱性，將孩子節點同深度的門節點的密鑰都減少了1 個分量，“或門”的密鑰減少了25%，“與門”的密鑰減少了33.33%.孩子節點有不同深度的門節點的密鑰沒有減少，只是為了在安全性證明中方便仿真密鑰.實際使用時同深度和不同深度的門節點可不加區別，都減少1 個分量.

4）通過使用安全Hash 函數，將不可偽造性提升到“自適應選擇消息但選定屬性攻擊下存在不可偽造”，同時將主公鑰和主私鑰長度各減少2m個元素（m為消息的長度）.

3.2 簽名方案

本文所提出的一般電路密鑰策略ABS 方案的算法為：

Setup.輸入安全參數 λ、電路最大深度 ?和電路輸入數n.

1）運行G(1λ,k=n+?+3)得到階為素數p的群序列G1,G2,…,Gk和對應的生成元序列g1(g=g1),g2,···gk，以及其上的多線性映射e.

2）隨機選取ai,β∈RZp，i∈[1,n],β∈{0,1}，計算Ai,β=.記a={a1,0,a1,1,a2,0,a2,1,…,an,0,an,1}，A={A1,0,A1,1,A2,0,A2,1,…,An,0,An,1}.

3）隨機選取α∈RZP，計算Y=

4）選取防碰撞Hash 函數H:{0,1}?→G1.

輸出系統公開參數pp={Y,A,n,?,p,G1,G2,…,Gk,g1,g2,…,gk,e,H}和主私鑰msk={α,a}.

KeyGen.輸入系統公開參數pp、系統主私鑰msk和電路f=(n,q,L,R,GT).

2）采用“自下而上”的方式計算密鑰組成部分Kw.

①輸入節點.w∈I=[1,n] ，D(w)=iw，計算

② 或門.w∈G，GT(w)=OR ，D(w)=iw.

（i）如果D(L(w))=D(R(w)),即iL(w)=iR(w),計算

③與門.w∈G，GT(w)=AND ，D(w)=iw.

（i）如果D(L(w))=D(R(w)),即iL(w)=iR(w),計算

3）輸出簽名密鑰S Kf={Kw}w∈N.

Sign.輸入公開參數pp、簽名密鑰S Kf、消息M和屬性?=(?1,?2,…,?n)∈{0,1}n，計算f(?)和各節點的權重.如果f(?)=0，無法簽名，停止；如果f(?)=1，按“從上到下”遞歸方法計算必要節點的Ew.

2）或門.w∈G，GT(w)=OR.

如果WL(w)(?)≤WR(w)(?)，調用其左孩子節點的EL(w)，計算

否則，調用其右孩子節點的ER(w).

如果D(L(w))=D(R(w))，計算

如果D(L(w))≠D(R(w))，計算

3）與門.w∈G，GT(w)=AND，調用其孩子節點的EL(w)和ER(w).

如果D(L(w))=D(R(w))，計算

如果D(L(w))≠D(R(w))，計算

4）輸入節點.w∈I.計算

5）計算并輸出簽名

Verify.輸入待驗證的簽名 σ及相應的消息M和屬性 ?.如果等式

成立，輸出1；否則，輸出0.

4 安全性證明與性能效率分析

本節證明所提出方案的安全性，并分析其性能和效率.

4.1 安全性證明

定理1.本文所提出的一般電路密鑰策略基于屬性簽名方案是正確的.

證明.容易知道，在簽名遞歸過程所有被計算的節點都有fw(?)=1.下面，用數學歸納法證明簽名生成過程中所有的Ew都有Ew=其中?(?)=

1）當w為輸入節點時，即w∈I，D(w)=iw，有

①或門.w∈G，GT(w)=OR.

② 與門.w∈G，GT(w)=AND.

定理2.如果k-MCDH 假設成立，則所提出的一般電路密鑰策略ABS 方案是自適應選擇消息但選定屬性攻擊下存在不可偽造的.

證明.假設 F是具有優勢 ε的EUF-sA-CMA 敵手，C 是k-MCDH 問題的挑戰者，我們構建如下的算法 B，利用 F來解k-MCDH 問題.

B 維護一個初始化為空的列表 LH.令qs為查詢Sign Oracle的最大次數.

k-MCDH Gen.

3）B 發送公 開參數pp={Y,A,n,?,p,G1,G2,…,Gk,g1,g2,…,gk,e}給敵手 F .

KeyGen Oracle.當敵手 F 詢 問關于電路f=(n,q,L,R,GT)的密鑰時，如果f(??)=1，拒絕；否則，采用“自下而上”的方式計算密鑰組成部分Kw.

1）輸入節點.w∈I，D(w)=iw.

2）或門.w∈G，GT(w)=OR ，D(w)=iw.

①如果fw(??)=1，選取zw,vw∈RZp.

3）與門.w∈G，GT(w)=AND ，D(w)=iw.

4）最后，返回S Kf={Kw}w∈N給敵手 F.

H-Oracle.當敵手 F詢問消息Mi的Hash 值時，如果Mi在 LH中，則返回相應的hi；否則，B 響應如1)～4):

1）選取ρi∈{0,1}，使ρi=0的概率為(qs+1)?1.

2）如果ρi=1，選取ri∈RZp，令hi=gri.

3）如果ρi=0，令hi=

4）返回hi給敵手 F，添加(Mi,hi,ri,ρi) 到 LH.

Sign Oracle.當敵手 F詢問關于消息Mj和屬性?j的簽名時，B先請求關于消息Mj的H-Oracle 服務，從LH中得到相應的rj和 ρj.如果ρj=0，則中止；否則，計算并返回

由于上述Setup，KeyGen，H-Oracle,Sign Oralce 的仿真都是完善的，如果 B 沒有中止，F輸出1 個有效簽名的概率至少為ε.

因為ρi=0的概率是(qs+1)?1，B在Sign Oralce 中不中止的概率至少為因此，B解k-MCDH 問題的概率至少為

當n→∞時，概率等于因此，在k-MCDH 假設下，所提出的一般電路密鑰策略基于屬性簽名方案是自適應選取消息但選定屬性攻擊下存在不可偽造的.

證畢.

定理3.所提出的一般電路密鑰策略基于屬性簽名方案具有完善隱私性.

證明.對于任何M,?和滿足f0(?)=f1(?)=1的f0,f1，對應于f0,f1的簽名分布σ0←和σ1←分別為

分布{σ0}和{σ1}是完全一樣的,因此是信息論意義不可區分的，所以所提出的方案具有完善隱私性.

證畢.

4.2 性能與效率分析

與已有方案相比，本文方案有2 個顯著優點：一是訪問結構的表達能力達到最強，可以支持任意訪問結構；二是簽名只有1 個群元素，長度達到最短.

正前文所指出的，目前只有3 個支持電路訪問結構的基于屬性簽名方案：Tang 等人[10]方案、Sakai 等人[11]方案和Kaafarani 等人[12]方案.文獻[11-12]方案的簽名的長度都與電路的大小成線性增長關系，效率都很低，Tang 等人[10]方案的簽名大小也僅為1 個群元素.

將本文方案與Tang 等人[10]方案進行比較，結果如表2 所示.本文方案在安全性和訪問結構的表達力方面都有明顯優勢.

因為不同的電路會有不同的數據規模和計算開銷，本文以圖1 的電路和1 個輸入為n=64的電路為例進行效率比較，結果如表3 所示.當n=64，屬性的數量是264（>7.38×1019），電路f的數量更是不受限制，因此能完全滿足應用需要.

Table 2 Performance Comparison of Schemes表2 方案性能比較

Table 3 Efficiency Comparison of Schemes with m Equals 160表3 方案效率對比（m=160）

比較結果表明：本文方案在數據長度和計算開銷2 方面性能都具有優勢.

5 結論

ABS 能提供靈活的隱私保護，在許多場景有重要應用.本文使用多線性映射構造了一個密鑰策略的ABS 方案，可支持一般電路作為訪問結構.與同類方案相比，本文方案在安全性、訪問結構表達力、數據長度和計算開銷等方面都有明顯優勢.

進一步研究的方向將是提出自適應選擇消息且自適應選擇屬性攻擊下存在不可偽造的方案，且在標準模型下證明其安全性.

作者貢獻聲明：黃振杰負責方案設計、安全性證明和定稿；林志偉負責方案設計、性能分析和初稿撰寫.