去中心基于屬性不可否認簽名*

魏 亮，黃振杰，陳群山

(1.福建省粒計算及其應用重點實驗室(閩南師范大學)，福建 漳州 363000; 2.閩南師范大學計算機學院，福建 漳州 363000)

1 引言

基于屬性密碼學，簡稱屬性密碼學，可提供細粒度和靈活的訪問控制，因而受到廣泛關注，成為近年來密碼學研究的熱點之一[1]。基于屬性簽名ABS(Attribute-based Signature)，簡稱屬性簽名，是屬性密碼學的重要組成部分。屬性簽名除了與屬性加密一樣可以進行細粒度訪問控制之外，還具有通常數字簽名所不具備的隱私性(Privacy)[2]。

2005年,Sahai等[3]開始研究屬性加密，之后2008年,Maji等[2]開始研究屬性簽名，他們給出了屬性簽名的概念和安全模型。Maji等[2]提出的屬性簽名方案是針對單調訪問結構的，2014年Okamoto等[4]提出了非單調謂詞的屬性簽名方案，并在標準模型下證明是安全的。2016年，Sakai等[5]提出一般邏輯電路謂詞的屬性簽名方案，可適用于任意訪問結構。2019年，Datta等[6]提出了簽名策略為無界算術分支程序的屬性簽名方案。還有一些增加了額外性質的屬性簽名方案，如基于屬性的外包[7]、可鏈接[8]、層次[9]、可撤銷[10]、代理[11]和動態門限[12]簽名方案等。

在一般的屬性簽名方案中，存在一個唯一的屬性權威中心。一旦權威中心出現腐敗，整個系統就沒有安全性可言了。作為一種解決方案，學者們提出了多權威機構屬性簽名MAABS(Multi-Authority Attribute-Based Signature)[13]的概念。在MAABS中，系統將屬性交由不同的權威機構管理，大大減輕了單個權威中心的負擔，但依然存在一個特殊的權威中心負責給其它權威機構發放密鑰，如果這個權威中心出現腐敗，仍將威脅整個系統的安全性。Okamoto等[14]更進一步提出去中心屬性簽名DABS(Decentralized Attribute-Based Signature)的概念。在DABS中，不再有特殊的權威中心，多個權威機構地位平等，獨立為用戶分發自己管理的屬性密鑰。一個權威機構出現腐敗，只影響相應屬性的安全性，其他屬性的安全性仍不受威脅。2013年，Okamoto等[14]提出了第1個去中心屬性簽名方案，并在標準模型下證明了該方案的安全性。2014年，Kaafarani等[15]提出去中心可追蹤屬性簽名方案，對安全模型進行了重新定義，增強了安全性。在文獻[15]的基礎上，2015年,Ghadafi[16]提出了更高效的去中心可追蹤屬性簽名方法。2017年，Sun等[17]提出安全的去中心外包屬性簽名，大大降低了簽名過程中的計算量。2018年,Sun等[18]將去中心屬性簽名應用于構建醫療區塊鏈。

通常的數字簽名是公開可驗證的，任何人都可以使用公開信息來驗證簽名的真偽，這對某些文件的簽署與發布是非常有利的。但是，在某些場合，簽名人并不希望其簽名被任意傳播，比如對敏感消息的簽名。為解決這個問題，1989年，Chaum等[19]提出了不可否認簽名(Undeniable Signature)的概念。不可否認簽名的特點是如果沒有簽名人的參與，其他人無法單獨驗證簽名，也無法向第三方證實簽名是真的。不可否認簽名的經典應用場景是正版軟件銷售[19]，軟件供應商在銷售軟件時需同時發放正版證書。如果正版證書是用通常簽名算法簽發的，那么惡意的客戶就能私自復制出售附有正版證書的軟件。如果正版證書改用不可否認簽名算法簽發，那么雖然惡意客戶仍能復制軟件和證書，但卻不能向第三方證實證書的有效性(即不能證明軟件是正版的)。2004年，Libert等[20]研究了基于身份不可否認簽名；2008年，Duan[21]研究了無證書不可否認簽名。雖然屬性簽名的研究已有十多年，但據作者所知，至今未見基于屬性不可否認簽名的研究報道。文獻[22,23]雖稱研究“基于屬性的不可否認簽名協議”，實則研究的是如何追蹤屬性簽名的簽名人，使其不能否認簽名行為，令其對簽名負責，這與可追蹤性(Traceability)比較接近[24]，與Chaum等[19]提出的不可否認簽名是完全不同的。

本文將基于屬性、不可否認和去中心3個概念相結合，研究去中心基于屬性不可否認簽名。引進基于屬性和去中心的性質，可以很大程度擴展不可否認簽名的應用范圍。仍以正版軟件銷售為例，使用基于屬性不可否認簽名可以讓軟件生產商對軟件代銷商進行細粒度控制，為每個軟件指定代銷商的資質要求，使得只有滿足資質要求并且得到授權的代銷商才能簽發正版證書。使用去中心系統則可以做到不同的資質由不同的管理機構來頒授，而且這些管理機構可以不是軟件生產商。

本文給出去中心基于屬性不可否認簽名的定義和安全模型，并構造一個去中心基于屬性不可否認簽名方案。該方案主要基于Cramer等[25]的證據隱藏零知識證明協議。本文選擇Schnorr協議[26]作為其基礎Σ協議，使用Shamir(t,n)門限方案[27]作為其秘密分享方案；再使用Fiat-Shamir轉換[28]得到一個基礎(t,n)門限簽名BTS(Basic Threshold Signature)方案;然后再對BTS方案進行不可否認、防共謀和去中心化處理；最后得到一個去中心基于屬性不可否認簽名方案。在去中心屬性密碼中，防共謀的通常做法是引入用戶全局標識，本文沿用這個做法。

2 預備知識

2.1 困難性問題

(1)離散對數問題DL(Discrete Logarithm problem)：假設G為大素數p階循環群，g為G的生成元(下同)。給定群G中的隨機元素A，計算a∈Zp，滿足ga=A。記a為DL(A,g)，稱A為關于g的離散對數。

2.2 拉格朗日插值多項式

已知某個函數φ(x)在t個互不相同點xi(i=1,…,t)的函數值φ(xi)(i=1,…,t)，可構造t-1次拉格朗日插值多項式：

2.3 (t,n)門限簽名方案

(t,n)門限簽名方案是由文獻[25]中Cramer等給出的一個用Σ協議構造證據隱藏零知識證明協議的方法構造而來的。如果選擇Shamir(t,n)門限方案[27]作為其秘密分享方案，使用Schnorr協議[26]作為其基礎Σ協議，再使用Fiat-Shamir轉換[28]即可得到此簽名方案。

基礎門限簽名BTS方案如下所示：

(3) Sign:不妨假設簽名人擁有前t個私鑰,對消息m∈{0,1}*進行簽名：

③計算c=H2(m,R1,…,Rn)；

④用n-t+1個點(0,c),(t+1,ct+1),…,(n,cn)構造n-t次拉格朗日插值多項式Pn-t(x)；

⑤計算ci=Pn-t(i)，di=ti-cisi，i=1,…,t；

⑥輸出簽名：σ=(ci,di,Ri)(i=1,2,…,n)和多項式Pn-t(x)。

注：其中多項式也可不傳，可根據簽名中的參數重構，但會增加驗證者的計算量。

(4) Verify:

①驗證多項式Pn-t(x)是否為n-t次多項式；

②驗證ci=Pn-t(i)，其中i=1,…,n，是否都滿足；

③驗證c=H2(m,R1,…,Rn)是否滿足；

④驗證Ri=gdiYici，其中i=1,…,n，是否都滿足；

⑤如果上述條件都滿足，則驗證人接受此簽名，否則不接受。

因為Schnorr協議和Shamir (t,n)門限方案滿足文獻[25]定理8的條件，所以由文獻[25]定理8和Fiat-Shamir轉換定理(文獻[28]的定理4)，可得到如下引理：

引理1如果離散對數問題是困難的，則上述基礎門限簽名方案是存在不可偽造的。

引理2在上述基礎門限簽名方案中，簽名所使用的私鑰(證據)是隱藏的，也是不可區分的。

2.4 離散對數零知識證明

2.4.1 離散對數相等零知識證明[29]

EDLZKP(Equal Discrete Logarithm Zero Knowledge Proof)協議：

(3)P收到c后，計算d=r+cumodp，將d發送給T。

(4)T收到d后，檢查gd=z1Uc和Vd=z2Wc是否成立。如果成立，則T接受P知道秘密值u，且DL(U,g)=DL(W,V)。

引理3上述協議具有如下性質：

(1)如果DL(U,g)=DL(W,V)，則驗證人接受此證明有效。

(2)如果DL(U,g)≠DL(W,V)，則驗證人接受此證明有效的概率是可忽略的。

(3)協議是零知識的，即通過此仿真算法任何人都可產生一個仿真副本，此副本與真實副本(按協議執行產生的)不可區分。

2.4.2 離散對數不相等零知識證明[29]

假設證明人P知道秘密值u=DL(U,g)，可使用下面的交互協議向驗證人T證明DL(U,g)≠DL(W,V)。

NEDLZKP(No Equal Discrete Logarithm Zero Knowledge Proof)協議:

(3)P收到c后，計算d1=α+c(ur)modp，d2=β+crmodp，然后將(d1,d2)發送給驗證人T。

(4)T收到(d1,d2)后，檢查Vd1/Wd2=z1Ac，gd1/Ud2=z2是否成立。如果成立，則驗證人T接受此證明。

引理4上述協議具有如下性質：

(1)如果DL(U,g)≠DL(W,V)，則驗證人接受此證明有效。

(2)如果DL(U,g)=DL(W,V)，則驗證人接受此證明有效的概率是可忽略的。

(3)協議是零知識的，即任何人都可通過仿真算法產生一個與真實副本不可區分的仿真副本。

3 去中心基于屬性不可否認簽名

3.1 去中心基于屬性不可否認簽名定義

1個去中心基于屬性不可否認簽名方案包含5個算法和2個交互式協議:

(1) Setup:輸入系統安全參數1k，初始化系統公開參數gparam(下面各算法和協議都需要輸入公開參數gparam，為簡潔起見將其省略)。

(2) AAGen:每個屬性權威機構Ai生成各自的公私鑰對(pki,ski),ski為保密私鑰，pki為公開公鑰。

(3) UGen:用戶產生自己的全局標識IDu。

(4) UAGen:屬性權威機構Ai為用戶生成關于屬性Ai的私鑰。輸入用戶全局標識ID、屬性權威機構的私鑰ski和屬性Ai，輸出用戶私鑰skID,Ai。

(5) Sign:輸入簽名人的私鑰集{skID,Ai}、消息m和訪問結構T，輸出簽名σ。

(6) Confirm:是驗證人和簽名人之間的交互協議。驗證人輸入四元組(ID,m,σ,T),簽名人輸入其私鑰或某秘密值。如果簽名是有效的，那么協議結束時，驗證人接受該簽名有效。

(7) Denial:與驗證協議相似，驗證人同樣輸入四元組(ID,m,σ,T),簽名人輸入其私鑰或某秘密值。如果簽名是無效的，那么協議結束時，驗證人接受該簽名為無效。

3.2 安全模型

去中心基于屬性不可否認簽名應具有正確性(Correctness)、不可偽造性(Unforgeability)、隱藏性(Invisibility)、屬性隱私性(Attributes Privacy)和不可傳遞性(Non-transferability)等性質。

正確性是指，如果按方案給定的算法和協議執行，那么都將得到正確的結果。其定義比較平凡，限于篇幅，此處省略詳細描述。下面給出其他性質的形式化定義。

3.2.1 不可偽造性

不可偽造性是指，如果沒有獲得滿足訪問結構所需的私鑰，任何人都不能偽造有效的簽名。其形式化定義通過如下的GAME 1給出。

GAME 1：

(1)挑戰者C初始化系統，并公開公共參數gparam。

(2)C為各權威機構Ai生成公私鑰對(aski,apki)，保留其私鑰aski，并將公鑰apki發送給敵手F。

(3)在多項式時間內，允許F適應性地進行以下詢問：

①用戶全局標識詢問：F提交請求，C返回一個全局標識ID。

②用戶秘密值詢問：F提交IDu，C返回對應的秘密值su或⊥。

③密鑰詢問：F提交(Ai,ID)，C返回關于(Ai,ID)的密鑰。

④簽名詢問：F提交(ID,m,T)，C返回關于(ID,m,T)的簽名σ。

⑤驗證詢問：F提交(ID,m,T,σ)，C與之執行驗證協議。

⑥否認詢問：F提交(ID,m,T,σ)，C與之執行否認協議。

(4)最后，F輸出(ID*,m*,T*,σ*)。

F贏得游戲，如果：

①(ID*,m*,T*,σ*)不能被否認。

②F沒有對(ID*,m*,T*)進行過簽名詢問。

③F就ID*進行過密鑰詢問的屬性集A*不滿足T*。

定義1如果任意敵手F在多項式時間內贏得上述游戲的概率都是可忽略的，則一個去中心基于屬性不可否認簽名方案稱為選擇消息存在不可偽造的。

3.2.2 隱藏性

隱藏性是指，除了簽名人外，任何其他人均不能判定簽名的有效性。其形式化定義通過如下的GAME 2給出。

GAME 2

(1)系統初始化、權威機構公私鑰生成同GAME 1。

(2)敵手F可以請求如同GAME 1的所有詢問，挑戰者C的響應也同GAME 1。

(3)F選擇一條消息m*、訪問結構T*和一個全局標識ID*，并提交給C。

(4)C接收(ID*,m*,T*)后，隨機選擇b∈{0,1}。當b=1時，計算(ID*,m*,T*)的有效簽名σ*；當b=0時，從簽名空間中隨機選擇σ*。將σ*發送給F。

(5)F得到挑戰簽名σ*后，還可進行預言機詢問，但不能對(ID*,m*,T*,σ*)進行驗證詢問和否認詢問，且就ID*進行過密鑰詢問的屬性集A*不滿足T*。

(6)最后，F輸出其猜測b′。

如果b′=b，則稱敵手贏得此游戲。

定義2如果任意敵手F在多項式時間內贏得上述游戲的概率是可忽略的，則稱一個去中心基于屬性不可否認簽名方案具有隱藏性。

3.2.3 屬性隱私性

本文沿用文獻[14]的屬性隱私性：由簽名不能知道簽名人擁有哪些屬性。其形式化定義通過如下的GAME 3給出。

GAME 3：

(1)系統初始化、權威機構公私鑰生成同GAME 1。

(2)預言機服務同GAME 1。

(3)敵手F選擇目標明文m*、身份標識ID*、訪問結構T*和2個滿足T*的屬性集(B0,B1)，將五元組(ID*,m*,T*,B0,B1)作為挑戰目標提交給挑戰者C。

(4)挑戰者C收到(ID*,m*,T*,B0,B1)后,隨機選擇b∈{0,1}，然后用Bb的屬性密鑰產生簽名σ*，并發送給F。

(5)F得到簽名σ*后，還可以進行一系列詢問。

(6)最后，F輸出其猜測b′∈{0,1}。

如果b′=b，則稱F贏得此游戲。

定義3如果任意敵手F在多項式時間內贏得上述游戲的概率是可忽略的,則稱一個去中心基于屬性不可否認簽名方案具有屬性隱私性。

3.2.4 不可傳遞性

不可傳遞性是指，在簽名人向驗證人證實或否認簽名之后，驗證人仍然不能向任何第三方證實或否認簽名，但驗證和否認協議的證據是不可傳遞的，即他不能從中得到任何知識以向第三方證實或否認簽名。其形式化定義通過如下的GAME 4給出。

GAME 4：

(1)系統初始化、權威機構公私鑰生成與GAME 1相同。

(2)預言機服務同GAME 1。

(3)敵手F向挑戰者C提交挑戰(ID*,m*,σ*,T*)。挑戰者C隨機選取b∈{0,1}。當b=0時，根據簽名的有效性，C用仿真器(Simulator)產生一個驗證或否認協議的副本；當b=1時，根據簽名的有效性，C執行驗證或否認協議得到一個副本。C將得到的副本返回給敵手F。

(4)敵手F可重復進行步驟(2)的詢問。

(5)最后，F輸出其猜測b′∈{0,1}。

如果b′=b，則稱F贏得此游戲。

定義4如果任意敵手F贏得GAME 4的優勢是可忽略的,則稱一個去中心基于屬性不可否認簽名方案具有不可傳遞性。

4 去中心基于屬性不可否認簽名方案

本節提出一個去中心基于屬性不可否認簽名方案，其訪問結構為(t,n)門限，具體如下所示：

(5) Sign:不妨假設簽名人S擁有的屬性集為{A1,A2,…,At}。

ei=H1(Ai,ri,IDs,yi)

Ri=gdiYici

③計算:

c=H2(m,T1,T2,…,Tn,IDs)

④用n-t+1個點(0,c),(t+1,ct+1),…,(n,cn)構造n-t次拉格朗日插值多項式Pn-t(x)。

⑤計算ci=Pn-t(i)，di=ti-cisi，i=1,…,t。

⑥輸出簽名：σ=(ci,di,Ti,ri,IDs)(i=1,2,…,n)和多項式Pn-t(x)。

(6) Confirm:

①驗證人T驗證Pn-t(x)是否為n-t次多項式。

②驗證是否有Pn-t(i)=ci，i=1,…,n。

③驗證是否有Pn-t(0)=H2(m,T1,T2,…,Tn,IDs)。

④驗證人T與簽名人S進行交互驗證。使用秘密值ss，簽名人通過2.4節的EDLZKP協議向驗證人驗證DL(Ti,Ri)=DL(IDs,g)，其中Ri=gdiYici，Yi=riyiei，ei=H1(Ai,ri,IDs,yi)，i=1,…,n。

⑤以上全通過，則簽名為有效簽名。

(7) Denial:

①驗證人T驗證Pn-t(x)是否為n-t次多項式；

②驗證是否有Pn-t(i)=ci，i=1,…,n；

③驗證是否有Pn-t(0)=H2(m,T1,T2,…,Tn,IDs)；

④以上有一個不通過，則簽名為無效簽名。

驗證人T與簽名人S進行交互驗證。使用秘密值ss，簽名人通過2.4節的NEDLZKP協議向驗證人證明存在某個i,使得DL(Ti,Ri)≠DL(IDs,g)，其中Ri=gdiYici，Yi=riyiei，ei=H1(Ai,ri,IDs,yi)。

注：上述方案是去中心的，方案中的每個權威機構都各自獨立隨機選取自己的私鑰，然后計算自己的公鑰，因此各權威機構的私鑰是統計獨立的。各權威機構都只知道自己的私鑰，不知道其他權威機構的私鑰，不存在掌握系統全部私鑰的特別權威中心。如果某個權威機構被攻破或腐敗，只影響相對應的一個屬性的安全性，不會致使整個系統崩潰。

5 安全性與效率分析

5.1 安全性分析

定理1本文方案是正確的。

證明本定理可通過如下簡單驗算得到:

gtig-ci(ki+eiri)(gkigxiei)ci=

gti=Ri

□

定理2如果離散對數問題是困難的，那么本文方案是存在不可偽造的。

證明本文方案的不可偽造性可歸約到預備知識2.3給出的基礎門限簽名方案(BTS)。詳細證明過程如下所示：

如果存在一個敵手F能以εF的優勢偽造本文方案的簽名，那么存在敵手F′能以εF′=εF/q的優勢偽造基礎門限簽名方案的簽名，其中q為F請求用戶全局標識的最多個數。記C為基礎門限簽名方案的挑戰者。

(2)F′為所有權威機構Ai生成公私鑰對(xi,yi=gxi)，將公鑰yi和(G,p,g)發送給F，i=1,…,n。

(3)假設F最多請求q個全局標識，F′隨機選取j,1≤j≤q。

(4)F′為F提供如下預言機服務：

②當F對IDu進行秘密值詢問時，如果IDu在IDlist中，F′返回su；否則，返回⊥。

⑦當F對(ci,di,Ti,ri,IDs)(i=1,…,n)和多項式Pn-t(x)進行簽名人驗證或否認詢問時，F′用ss與F進行驗證或否認協議。

□

注：本定理的證明雖然是自適應選擇屬性和全局標識的，但也有個限制，即敵手攻擊的全局標識是請求過全局標識詢問的。因此，準確地講，本方案是限制性自適應選擇全局標識、自適應選擇屬性和自適應選擇消息不可偽造的。“限制性自適應選擇全局標識”還是要強于某些文獻的“選定身份”或“選定屬性”的。

定理3如果SDDH問題是困難的，那么本文方案具有隱藏性。

□

定理4本文方案具有屬性隱私性。

證明在知識證明系統中，證據隱藏性是指在證明過程中，如果證明人等概率地使用證據w1或證據w2來進行證明，那么驗證者猜中其所使用證據的優勢是可忽略的。在屬性簽名方案中，屬性隱私性是指，如果簽名人等概率地使用屬性集B0或屬性集B1的私鑰進行簽名，那么驗證者猜中其所使用私鑰的優勢是可忽略的。簽名方案是一種特殊的非交互證明系統，屬性隱私性與證據隱藏性兩者的安全模型在本質上是一致的。本文方案是由Cramer等[25]的證據隱藏零知識證明協議經Fiat-Shamir轉換[28]得到的，因此方案保持了證據隱藏的性質，用戶所擁有的屬性私鑰就是其所使用的證據，從而具有屬性隱私性。

□

定理5本文方案具有不可傳遞性。

證明根據定義4，如果存在能仿真出不可區分副本的仿真器則本定理成立。下面是分別給出證實協議和否認協議的仿真器。

(1)證實協議仿真器。

(2)證實協議仿真不可區分性：

從上述的仿真算法可知仿真副本的分布為：

從證實協議可知真實副本的分布為：

上述2個分布是相同的、不可區分的。

(3)否認協議仿真器。

(4)與否認協議真實副本不可區分：

否認協議仿真副本的分布如下所示：

否認協議真實副本分布如下所示：

上述2個分布是相同的、不可區分的。

□

5.2 效率分析

本文所提出的方案是基于屬性不可否認簽名方案，因目前未見同類方案的公開報道，因此只能與基于屬性簽名(不具有不可否認性)方案進行效率上的比較。目前，已有的基于屬性簽名方案大多是基于雙線性對或多線性對的，只有文獻[30，31，32]中的方案不是基于線性對的，其中文獻[30]提出的是一種一般性構造方法，沒有具體方案，無法進行效率比較；文獻[31]所提出的方案不具有屬性隱私性這一重要性質，從嚴格意義上說不能算是屬性簽名方案，因此也不具有可比性。文獻[32]的方案與本文方案具有相同屬性隱私性，也都不是基于線性對的，因此將本文方案與文獻[32]方案作簡單的效率比較，結果見表1，其中n為總體屬性個數，t為簽名人所擁有屬性的個數，計算開銷是指冪指數運算的次數，私鑰、公鑰、簽名長度是指組成的元素個數。

可見，本文方案在簽名計算、驗證計算、簽名長度、私鑰長度方面都優于文獻[32]方案。注意到文獻[32]方案是基于RSA問題的，作者建議安全參數為1 024，而本文方案是基于離散對數問題，可以在橢圓曲線上實現，同等安全的安全參數為160，因此在數據長度方面的優勢就更加明顯了。在公鑰長度方面，由于文獻[32]方案是中心化的，所以只有1個權威中心的公鑰，8個元素，約8×1024比特，而本文方案是去中心化的，n個屬性就有n個屬性機構，有n個屬性機構就需要n個不同的公鑰，約160n比特，在屬性總體個數n小于50時，本文方案仍然具有優勢。

Table 1 Comparision of efficiency and properties表1 效率性質對比

6 結束語

對基于屬性簽名的研究已有十多年，但仍未有真正基于屬性不可否認簽名的研究報道。本文將基于屬性、不可否認和去中心3個概念相結合，研究去中心基于屬性不可否認簽名，給出了其定義和安全模型，并構造了一個去中心基于屬性不可否認簽名方案。這只是基于屬性不可否認簽名研究的初步探索，未來還需在功能更全、安全性更強、效率更高和簽名長度更短等方面進一步努力。