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

黃振杰 林志偉,2

1（福建省粒計算及其應(yīng)用重點實驗室（閩南師范大學(xué)）福建漳州 363000）

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1 預(yù)備知識

1.1 符號說明

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

1.2 多線性映射與困難性假設(shè)

多線性映射.G(1λ,k)為群生成算法，輸入安全參數(shù) λ和多線性映射級數(shù)k，輸出素數(shù)p階群序列G1,G2,···,Gk和相應(yīng)的生成元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)…))，其中右側(cè)的e為其輸入所對應(yīng)的雙線性映射ei,j.

Table 1 Symbols Interpretation表1 符號釋義

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

1.3 電 路

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

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

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

1）輸入節(jié)點.

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

② 輸入為0 的節(jié)點，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))，則

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

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

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

2 電路訪問結(jié)構(gòu)密鑰策略ABS

本節(jié)給出訪問結(jié)構(gòu)為電路的密鑰策略ABS 的定義和安全模型.

2.1 算法組成

電路訪問結(jié)構(gòu)密鑰策略ABS 方案由1）～4）算法組成：

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

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

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

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

2.2 安全性模型

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

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

Ga me1（EUF-sA-CMA）.

1）Initialization.敵手 F選擇挑戰(zhàn)屬性 ??并發(fā)送給挑戰(zhàn)者 C.

2）Setup.挑戰(zhàn)者 C生成系統(tǒng)公開參數(shù)pp并發(fā)送給敵手 F.

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

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

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

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

①σ*是關(guān)于消息M*和屬性 ?*的有效簽名；

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

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

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

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

Initialization.敵手 F選擇并發(fā)送挑戰(zhàn)消息M?和挑戰(zhàn)屬性 ??給挑戰(zhàn)者 C.

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

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

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

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

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

3.1 主要設(shè)計思想

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

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

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

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

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

3.2 簽名方案

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

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

1）運行G(1λ,k=n+?+3)得到階為素數(shù)p的群序列G1,G2,…,Gk和對應(yīng)的生成元序列g(shù)1(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 函數(shù)H:{0,1}?→G1.

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

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

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

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

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

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

否則，調(diào)用其右孩子節(jié)點的ER(w).

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

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

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

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

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

4）輸入節(jié)點.w∈I.計算

5）計算并輸出簽名

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

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

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

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

4.1 安全性證明

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

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

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

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

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

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

證明.假設(shè) F是具有優(yōu)勢 ε的EUF-sA-CMA 敵手，C 是k-MCDH 問題的挑戰(zhàn)者，我們構(gòu)建如下的算法 B，利用 F來解k-MCDH 問題.

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

k-MCDH Gen.

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

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

1）輸入節(jié)點.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中，則返回相應(yīng)的hi；否則，B 響應(yīng)如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詢問關(guān)于消息Mj和屬性?j的簽名時，B先請求關(guān)于消息Mj的H-Oracle 服務(wù)，從LH中得到相應(yīng)的rj和 ρj.如果ρj=0，則中止；否則，計算并返回

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

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

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

證畢.

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

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

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

證畢.

4.2 性能與效率分析

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

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

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

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

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

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

比較結(jié)果表明：本文方案在數(shù)據(jù)長度和計算開銷2 方面性能都具有優(yōu)勢.

5 結(jié)論

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

進一步研究的方向?qū)⑹翘岢鲎赃m應(yīng)選擇消息且自適應(yīng)選擇屬性攻擊下存在不可偽造的方案，且在標準模型下證明其安全性.

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