楊曉莉，黃振杰

1.閩南師范大學(xué) 福建省粒計(jì)算及其應(yīng)用重點(diǎn)實(shí)驗(yàn)室，福建 漳州363000

2.閩南師范大學(xué) 計(jì)算機(jī)學(xué)院，福建 漳州363000

基于屬性密碼是密碼學(xué)的研究熱點(diǎn)之一，能通過屬性和關(guān)于屬性的訪問結(jié)構(gòu)實(shí)現(xiàn)細(xì)粒度的訪問控制，而且具有很好的隱私性，因此有極廣泛的應(yīng)用場景，其主要內(nèi)容包括基于屬性加密[1]（attribute-based encryption）、基于屬性簽名[2]（attribute-based signatures）和基于屬性身份識別[3]（attribute-based identification）等?；趯傩悦艽a的研究成果豐富且持續(xù)不斷，2020 年仍有不少研究成果報(bào)道，比如Dong 等[4]基于格提出一個(gè)服務(wù)器輔助可撤銷基于屬性加密方案，Ishizaka等[5]給出一個(gè)從可搜索加密到基于屬性加密的一般性構(gòu)造，Cui 等[6]給出一個(gè)密鑰可再生的基于屬性加密方案，Ali等[7]給出一個(gè)基于屬性層次加密方案，Deng 等[8]給出一個(gè)基于屬性代理重加密方案，Le等[9]的基于屬性加密的密文壓縮，Takashima[10]提出一個(gè)表達(dá)力強(qiáng)且密文長度固定的基于屬性加密方案，Zhao等[11]研究了基于屬性加密的黑盒和公開可追蹤性，Okamoto等[12]的去中心基于屬性加密和簽名。

在最初的基于屬性密碼系統(tǒng)中，用戶密鑰是由單個(gè)屬性權(quán)威中心頒發(fā)的，如果這個(gè)權(quán)威中心腐敗了，那么整個(gè)系統(tǒng)就沒安全性可言了，這是一個(gè)嚴(yán)重的缺點(diǎn)。另外，單個(gè)屬性權(quán)威中心也容易出現(xiàn)瓶頸問題。為滿足大規(guī)模分布式應(yīng)用的需求，學(xué)者們提出了多權(quán)威（multi-authority）基于屬性加密[13]、多權(quán)威基于屬性簽名[14]和去中心（decentralized）基于屬性加密[15]、去中心基于屬性簽名[16]。多權(quán)威基于屬性密碼系統(tǒng)雖然是由多個(gè)屬性機(jī)構(gòu)來分發(fā)密鑰，但仍然有一個(gè)特殊中心權(quán)威機(jī)構(gòu)，由它給各屬性權(quán)威機(jī)構(gòu)分發(fā)密鑰。這個(gè)特殊中心權(quán)威機(jī)構(gòu)仍然身系整個(gè)系統(tǒng)的安全性，因此，多權(quán)威基于屬性密碼雖然解決了瓶頸問題，但仍未解決安全性問題。去中心基于屬性密碼系統(tǒng)中不存在任何特殊的中心機(jī)構(gòu)，系統(tǒng)中的各個(gè)屬性機(jī)構(gòu)相互獨(dú)立。一個(gè)機(jī)構(gòu)的腐敗只影響其管理的屬性，不構(gòu)成整個(gè)系統(tǒng)的安全性災(zāi)難。去中心基于屬性密碼最大程度解決傳統(tǒng)基于屬性密碼的兩大缺點(diǎn)。

零知識證明（zero-knowledge proof）是Goldwasser等[17]于1985 年提出的重要密碼原語，同時(shí)具備兩個(gè)看起來相互矛盾的性質(zhì)：一方面，要使驗(yàn)證者接受某個(gè)聲明；另一方面，要讓驗(yàn)證者不能從證明過程中得到任何知識。Σ 協(xié)議是一種三輪公開拋硬幣誠實(shí)驗(yàn)證者零知識交互證明協(xié)議，是由Cramer等[18-19]首先定義的。Σ 協(xié)議的一個(gè)重要應(yīng)用是通過Fiat-Shamir轉(zhuǎn)換得到數(shù)字簽名方案，重要的Σ 協(xié)議和對應(yīng)的簽名方案有：Schnorr[20]和Beth[21]的基于離散對數(shù)的協(xié)議和簽名方案；Ong等[22]的基于大整數(shù)分解的協(xié)議和簽名方案；Guillou 等[23]、Shamir[24]、Okamoto[25]和Girault[26]的基于RSA困難性的協(xié)議和簽名方案；Hess[27]和Cha等[28]的基于Computational Diffie-Hellman 困難性的協(xié)議和簽名方案。

雖然基于屬性密碼和Σ 協(xié)議都受到密碼學(xué)學(xué)者的廣泛注意，但到目前還沒有基于屬性Σ 協(xié)議的研究報(bào)道。目前已有一些相近的概念，但都與基于屬性Σ 協(xié)議有重要的區(qū)別。

相近的概念有：

（1）Cramer 等[18]的部分知識證明（proofs of partial knowledge）和Anada 等[29]的謂詞知識證明（proofs of predicates knowledge）本質(zhì)上是相同的，都是一種證據(jù)不可區(qū)分證明協(xié)議，可以用來證明擁有滿足訪問結(jié)構(gòu)的某個(gè)證據(jù)集，而且在證明過程中到底是使用哪個(gè)證據(jù)集是不可區(qū)分的。這兩個(gè)性質(zhì)與基于屬性Σ 協(xié)議是相同的，但它們都不考慮共謀攻擊問題，即不要求用來證明的證據(jù)集是屬于同一個(gè)人的，也就是說，證據(jù)集是可以“湊”的；而在基于屬性Σ 協(xié)議中，證據(jù)必須是同一個(gè)用戶的，這就是基于屬性Σ 協(xié)議的抗共謀性。

（2）Anada等[3,29]的基于屬性身份識別（ABI）通過證明擁有滿足訪問結(jié)構(gòu)的某個(gè)屬性集私鑰來證明身份，而且也考慮了抗共謀性。它與基于屬性Σ 協(xié)議的區(qū)別在于安全性要求不同：基于屬性身份識別主要是要求抗假扮（against impersonation），不考慮零知識性；而基于屬性Σ 協(xié)議要求具有特殊魯棒性（special soundness）和誠實(shí)驗(yàn)證者零知識性（honestverifier zero-knowledge）。一般來說，基于屬性Σ 協(xié)議可以用作基于屬性身份識別方案，反之則不一定可以。比如文獻(xiàn)[3]的基于屬性身份識別方案就不是零知識證明協(xié)議，更不可能是Σ 協(xié)議。

（3）Anada等[30]研究的匿名身份驗(yàn)證（anonymous authentication）與基于屬性身份識別有點(diǎn)相近，具有匿名性，能抗錯(cuò)誤驗(yàn)證（against misauthentication），但這里的匿名性是指不知道用戶到底是使用哪個(gè)密鑰，對應(yīng)的屬性集卻是明確的，這與基于屬性密碼的隱私性是有明顯不同的?；趯傩悦艽a的隱私性要求對應(yīng)的屬性集是隱藏的、不可知的。另一方面，為了減少計(jì)算量，匿名身份驗(yàn)證也不要求抗共謀。因此，匿名身份驗(yàn)證在隱私性和抗共謀性方面都弱于基于屬性Σ 協(xié)議。

本文將基于屬性密碼引入到知識證明領(lǐng)域，研究基于屬性Σ 協(xié)議。作為直接的應(yīng)用場景，基于屬性Σ 協(xié)議可以為各種信息系統(tǒng)提供匿名認(rèn)證服務(wù)。與現(xiàn)有匿名認(rèn)證機(jī)制相比，基于屬性Σ 協(xié)議具有訪問控制表達(dá)能力強(qiáng)、粒度細(xì)的優(yōu)點(diǎn)。本文所提出的方案是去中心的，解決了單個(gè)機(jī)構(gòu)的瓶頸問題和系統(tǒng)的安全性問題，因此應(yīng)用場景更加廣闊?；趯傩驭矃f(xié)議作為一種新的密碼學(xué)原語是十分值得研究的，不僅能進(jìn)一步豐富基于屬性密碼和知識證明這兩個(gè)密碼學(xué)重要領(lǐng)域的內(nèi)容，還能通過其重要應(yīng)用而間接豐富數(shù)字簽名、匿名認(rèn)證、匿名訪問控制等其他領(lǐng)域。

本文的主要貢獻(xiàn)有：

（1）提出基于屬性Σ 協(xié)議的概念，給出（去中心）基于屬性Σ 協(xié)議的定義和安全模型。

（2）基于標(biāo)準(zhǔn)Σ 協(xié)議、陷門可取樣關(guān)系和平滑秘密共享方案，提出一個(gè)去中心基于屬性Σ 協(xié)議的一般性構(gòu)造方法，并證明方案的安全性。因?yàn)橐延胸S富的標(biāo)準(zhǔn)Σ 協(xié)議[20-28]，所以由本文方法可以得到一系列去中心基于屬性Σ 協(xié)議。

（3）作為去中心基于屬性Σ 協(xié)議的應(yīng)用，利用Fiat-Shamir轉(zhuǎn)換，得到一個(gè)去中心基于屬性簽名和一個(gè)去中心基于屬性雙層簽名的一般性構(gòu)造方法。同樣地，由此可以得到一系列去中心基于屬性簽名和去中心基于屬性雙層簽名方案。

（4）效率分析表明，本文的去中心基于屬性簽名和去中心基于屬性雙層簽名方案相比已有的方案在數(shù)據(jù)長度和計(jì)算開銷兩方面都具有顯著的優(yōu)勢。而且本文的方案是去中心的，克服了瓶頸問題和系統(tǒng)安全性依賴單個(gè)中心的問題。

1 預(yù)備知識

1.1 平滑秘密共享方案

秘密共享方案可以將一個(gè)秘密值s的份額分發(fā)給n個(gè)參與者，每個(gè)參與者得到一個(gè)份額，使得一些參與者可以使用他們所擁有的份額重構(gòu)出秘密值s。能夠重構(gòu)出秘密值的參與者子集稱為許可集。秘密共享方案稱為完善的，如果任何非許可集都不能獲得關(guān)于秘密值s的任何信息。

如下Shamir(t,n)門限方案是一個(gè)常用的完善秘密共享方案，可以將域F中的秘密值s分拆成n個(gè)份額，使得任意t個(gè)互不相同的份額可以重構(gòu)出秘密值s。

Shamir(t,n)門限方案：

（1）分拆方法：隨機(jī)選取常數(shù)項(xiàng)為s的t-1 次多項(xiàng)式f(x)∈F(x)，隨機(jī)選取xi∈F，i∈{1,2,…,n}，計(jì)算n個(gè)份額f(xi)。

（2）重構(gòu)方法：已知t個(gè)互不相同的份額j∈{1,2,…,t}，構(gòu)造Lagrange插值公式：

計(jì)算秘密值s=f(0)。

所有許可集構(gòu)成的集合稱為秘密共享方案的訪問結(jié)構(gòu)Γ。一個(gè)訪問結(jié)構(gòu)Γ稱為單調(diào)的，如果A是一個(gè)許可集，那么任何包含A的集合也是許可集。

設(shè)Γ是總體N上定義的訪問結(jié)構(gòu)。對任意A?N，記為A在N中的補(bǔ)集。定義Γ的對偶訪問結(jié)構(gòu)Γ?如下：

例如，上述(t,n)門限的對偶是(n-t+1,n)門限。

定義1一個(gè)完善的秘密共享方案稱為半平滑的（semi-smooth），如果滿足下面（1）～（4）；如果還滿足（5），則稱為平滑的（smooth）。

（1）方案生成的所有份額都是多項(xiàng)式長的。

（2）秘密的分發(fā)和重構(gòu)都可在多項(xiàng)式時(shí)間內(nèi)完成。

（3）給定秘密及其全部份額，可以在多項(xiàng)式時(shí)間內(nèi)檢驗(yàn)它們是正確的。

（4）給定任何秘密值，由任何非許可集的份額都可以在多項(xiàng)式時(shí)間內(nèi)擴(kuò)充成完整份額。

（5）對于任意非許可集，其成員的份額都是互相獨(dú)立的。

上述Shamir(t,n)門限方案就是平滑的。

1.2 標(biāo)準(zhǔn)Σ 協(xié)議

知識證明是這樣的一種協(xié)議，通過它證明者P可以向驗(yàn)證者V 證明其知道指定聲明x所對應(yīng)的證據(jù)w。所有的聲明x和相應(yīng)證據(jù)w構(gòu)成一個(gè)二元關(guān)系R={(x,w)}。

定義2標(biāo)準(zhǔn)Σ 協(xié)議是一種3 輪公開拋硬幣誠實(shí)驗(yàn)證者零知識交互證明協(xié)議，由Σgen、Σcom、Σcha、Σres、Σvrf、Σext、Σsim7個(gè)算法組成。

（1）Σgen:輸入系統(tǒng)安全參數(shù)1k，輸出公開參數(shù)pp和一個(gè)二元關(guān)系R={(x,w)}。

（2）Σcom:由證明者P 執(zhí)行，輸入一對聲明和證據(jù)(x,w)，輸出承諾COM和狀態(tài)St，并發(fā)送承諾COM給驗(yàn)證者V。

（3）Σcha:由驗(yàn)證者V 執(zhí)行，輸入承諾COM和聲明x，公開拋硬幣隨機(jī)選擇一個(gè)挑戰(zhàn)CHA發(fā)送給P。

（4）Σres:由證明者P 執(zhí)行，輸入聲明x，證據(jù)w，承諾COM，狀態(tài)St和挑戰(zhàn)CHA，輸出一個(gè)響應(yīng)RES，并發(fā)送給驗(yàn)證者V。

（5）Σvrf:由驗(yàn)證者V 執(zhí)行，輸入聲明x，承諾COM，挑戰(zhàn)CHA和響應(yīng)RES，輸出一個(gè)決定值d。d=1表示接受本次證明；d=0 表示不接受。

（6）Σext:是證據(jù)提取器，輸入相同聲明x的兩個(gè)會(huì)話副本，提取證據(jù)w′。

（7）Σsim:是仿真器，輸入聲明x，輸出一個(gè)仿真副本(COM?,CHA?,RES?)。

在執(zhí)行一次證明協(xié)議過程中，雙方交互的所有消息所構(gòu)成的集合稱為一個(gè)會(huì)話副本。能讓驗(yàn)證算法輸出1的副本稱為可接受副本。

Σ 協(xié)議應(yīng)具有正確性、特殊魯棒性和誠實(shí)驗(yàn)證者零知識性：

正確性（completeness）：對于任何的(x,w)∈R，如果(COM,CHA,RES)是正確執(zhí)行協(xié)議所產(chǎn)生的副本，那么它是可接受副本。即

特殊魯棒性（special soundness）：如果存在一個(gè)知識提取器Σext，從對應(yīng)于相同聲明x的兩個(gè)可接受副本(COM,CHA,RES)和(COM,CHA′,RES′)（其中承諾COM相同，挑戰(zhàn)CHA、CHA′不同），能以壓倒性概率μ提取出x的一個(gè)證據(jù)w′，則稱Σ 協(xié)議具有特殊魯棒性。即

誠實(shí)驗(yàn)證者零知識性（honest-verifier zeroknowledge）：如果存在一個(gè)仿真器Σsim能產(chǎn)生與真實(shí)副本不可區(qū)分的仿真副本(COM?,CHA?,RES?)，則稱Σ 協(xié)議具有誠實(shí)驗(yàn)證者零知識性。即，對于任意的多項(xiàng)式時(shí)間區(qū)別器D，都有：

分別為真實(shí)副本和仿真副本分布，ε為可忽略量。這里假定驗(yàn)證者V是誠實(shí)的，它總是誠實(shí)運(yùn)行Σcha來產(chǎn)生挑戰(zhàn)值。

由Σ 協(xié)議的上述3個(gè)性質(zhì)可知，它也具有如下證據(jù)不可區(qū)分性。文獻(xiàn)[18]中的Σ 協(xié)議也是證據(jù)不可區(qū)分的。

證據(jù)不可區(qū)分（witness indistinguishable）：對于任意的驗(yàn)證者V、任意的聲明x及其任意的兩個(gè)證據(jù)w1和w2，分別使用證據(jù)w1和w2進(jìn)行證明所得的兩個(gè)副本是不可區(qū)分的。即，對于任意的多項(xiàng)式時(shí)間區(qū)別器D，都有：

如下Beth方案[21]是一個(gè)常用的Σ 協(xié)議。

Beth-Σ 協(xié)議：

①選擇大素?cái)?shù)q階乘法群G及其生成元g，記=(G,q,g)；

②隨機(jī)選取r∈Zq，計(jì)算R=gr；

③隨機(jī)選取x∈Zq，計(jì)算X=gx；

④隨機(jī)選取h∈Zq，計(jì)算s=r-1(h-Rx) modq；

1.3 陷門可取樣關(guān)系

對于關(guān)系R，定義值域Rng(R)={y:?x,(x,y)∈R}，x的像集R(x)={y:(x,y)∈R}，y的原像集R-1(y)={x:(x,y)∈R}。

定義3一個(gè)陷門可取樣關(guān)系（trapdoor samplable relations，TSR）由滿足正則性和求逆困難性的三個(gè)算法(TDG,Smp,Inv)組成，記為∏TSR(TDG,Smp,Inv)。

（1）生成算法TDG：輸入安全參數(shù)1k；輸出公開參數(shù)pp，關(guān)系R的描述和陷門t。

（2）取樣算法Smp：輸入關(guān)系R 的描述；輸出在關(guān)系R上均勻分布的(x,y)。

（3）求逆算法Inv：輸入關(guān)系R的描述，對應(yīng)的陷門t和元素y∈Rng(R)；輸出y的一個(gè)隨機(jī)原像x。

（4）正則性:對于由TDG產(chǎn)生的任意一個(gè)關(guān)系R，存在一個(gè)正整數(shù)d，使得對所有的y∈Rng(R)，都有|R-1(y)|=d。

陷門可取樣關(guān)系實(shí)例：

（1）TDG(1k)：

①選擇大素?cái)?shù)q階乘法群G及其生成元g，記=(G,q,g)；

②隨機(jī)選取陷門x∈Zq，計(jì)算X=gx；

上述陷門可取樣關(guān)系是q-正則的，其求逆困難性相當(dāng)于求離散對數(shù)困難性。

2 去中心基于屬性Σ 協(xié)議

2.1 去中心基于屬性Σ 協(xié)議的定義

在定義基于屬性Σ 協(xié)議之前，先定義一種特殊的關(guān)系，稱之為基于屬性關(guān)系。

假設(shè)系統(tǒng)屬性總體為N，Γ為N上的訪問結(jié)構(gòu)，基于屬性關(guān)系定義為：

其中，WA為“擁有屬性集A∈?！钡耐脩敉巫C據(jù)。

一般來說，系統(tǒng)會(huì)在不同時(shí)候?yàn)椴煌脩魧ο嗤虿煌瑢傩约疉生成不同的證據(jù)。在關(guān)系RΓ中，要求證據(jù)WA是為同一個(gè)用戶生成的關(guān)于屬性集A的同一次證據(jù)，目的是防止共謀攻擊，即防止用A1的證據(jù)和A2的證據(jù)湊成作為A1?A2的證據(jù)。假設(shè)用戶1擁有屬性子集A1，用戶2擁有屬性子集A2，A1和A2都不滿足訪問結(jié)構(gòu)Γ，但A1?A2可能滿足訪問結(jié)構(gòu)Γ；或者，用戶原來擁有屬性子集A1，后來由于身份變化而變更為擁有屬性子集A2，有可能A1和A2都不滿足訪問結(jié)構(gòu)Γ，但A1?A2滿足訪問結(jié)構(gòu)Γ。如果不要求是同用戶同次證據(jù)，惡意用戶就可能欺騙驗(yàn)證者。

稱關(guān)于上述基于屬性關(guān)系RΓ的具有屬性隱私性的Σ 協(xié)議為基于屬性Σ 協(xié)議。下面給出去中心基于屬性Σ 協(xié)議的準(zhǔn)確定義。

為方便敘述，假設(shè)系統(tǒng)有n個(gè)屬性機(jī)構(gòu)，每個(gè)屬性機(jī)構(gòu)管理1 個(gè)屬性，即總屬性集N={1,2,…,n}，屬性機(jī)構(gòu)i管理屬性i。

在去中心系統(tǒng)中，每個(gè)屬性機(jī)構(gòu)是獨(dú)立為用戶生成對應(yīng)證據(jù)的，為了防止上述的共謀攻擊，讓各自獨(dú)立的屬性機(jī)構(gòu)能協(xié)同生成一致性的同用戶同次證據(jù)，在下面的定義及一般性方案中都引入證據(jù)標(biāo)識τ。具有相同證據(jù)標(biāo)識τ的證據(jù)才能一起使用，用來防止敵手從不同屬性機(jī)構(gòu)處“湊”證據(jù)來欺騙驗(yàn)證者。

定義4一個(gè)去中心基于屬性Σ 協(xié)議由如下算法組 成，記 為

2.2 安全性定義

基于屬性Σ 協(xié)議除必須具有一般Σ 協(xié)議的正確性、特殊魯棒性和誠實(shí)驗(yàn)證者零知識性外，還須具有屬性隱私性。

正確性：對于任何的(Γ,Wτ,A)∈RΓ，如果(COM,CHA,RES)是正確執(zhí)行協(xié)議所產(chǎn)生的副本，那么它是可接受副本。即

注：上述定義要求有相同證據(jù)標(biāo)識τ是防止共謀攻擊的關(guān)鍵，如果對于不同證據(jù)標(biāo)識的副本也能提取證據(jù)，那么就會(huì)存在共謀攻擊。

分別為真實(shí)副本和仿真副本分布，ε為可忽略量。這里假定驗(yàn)證者V是誠實(shí)的，它總是誠實(shí)運(yùn)行來產(chǎn)生挑戰(zhàn)值。

屬性隱私性（attribute-privacy）：對于任意的訪問結(jié)構(gòu)Γ和任意兩個(gè)屬性集A,A′∈Γ，用證據(jù)Wτ,A和Wτ,A′進(jìn)行證明，所產(chǎn)生的副本(COM,CHA,RES) 和(COM′,CHA′,RES′)是不可區(qū)分的。即對于任意的多項(xiàng)式時(shí)間區(qū)別器D，都有：

3 去中心基于屬性Σ 協(xié)議的一般性構(gòu)造

本章利用標(biāo)準(zhǔn)Σ 協(xié)議、陷門可取樣關(guān)系和平滑秘密共享方案來構(gòu)造去中心基于屬性Σ 協(xié)議，并證明其安全性。

3.1 一般性構(gòu)造方案

條件1如下兩個(gè)分布相同：

條件2仿真器是從挑戰(zhàn)空間隨機(jī)選取挑戰(zhàn)CHA?的。

條件3的挑戰(zhàn)空間與Ψ的份額空間相同。

滿足這樣條件的標(biāo)準(zhǔn)Σ 協(xié)議是普通存在的，比如引言中提到的文獻(xiàn)[20-28]所提出的方案都滿足條件。

②選取Hash函數(shù)H:{0,1}?→Rng(R)；

③輸出全局參數(shù)gparam=pp。

①計(jì)算xi=H(i||τ),wi←Invi(xi,ti)；

②輸出Wτ,i=wi。

①計(jì)算xi=H(i||τ),i∈N；

②(COMi,Sti)←

③(COMi,CHAi,RESi)←

④輸出承諾COM={COMi}i∈N；

⑤狀態(tài)St={{Sti}i∈A,{CHAi,RESi}i∈Aˉ}。

①將份額{CHAi|i∈Aˉ}擴(kuò)充成CHA關(guān)于Γ?的完整份額，記擴(kuò)充得到的份額為{CHAi|i∈A}；

②RESi←

③輸出響應(yīng)RES={(CHAi,RESi)}i∈N。

①計(jì)算xi=H(i||τ),i∈N；

②如果有某個(gè)i∈N則輸出0；

③如果{CHAi|i∈N}不是CHA關(guān)于Γ?的完整份額，則輸出0；

④輸出1。

①記A={i|CHAi≠CHA′i,i∈N}；

②wi←i∈A；

③輸出{wi}i∈A。

①隨機(jī)選取A∈Γ；

②從挑戰(zhàn)空間隨機(jī)選取挑戰(zhàn)CHA?和

注：基于屬性Σ 協(xié)議的作用是讓證明者可以向驗(yàn)證者證明其擁有滿足訪問結(jié)構(gòu)的屬性，因此雙方都必須知道證明所指向的訪問結(jié)構(gòu)，把訪問結(jié)構(gòu)作為的輸入。但其運(yùn)行時(shí)只需要知道挑戰(zhàn)空間，不需要輸入訪問結(jié)構(gòu)Γ、承諾COM和標(biāo)識τ，這是因?yàn)棣?協(xié)議的挑戰(zhàn)是隨機(jī)選取的。把它們作為輸入只是為了方便驗(yàn)證階段找準(zhǔn)對應(yīng)的數(shù)據(jù)。

3.2 一個(gè)實(shí)例

使用1.2 節(jié)的Beth-∑協(xié)議，1.3 節(jié)的陷門可取樣關(guān)系實(shí)例和1.1節(jié)的Shamir(t,n)門限方案，由上述的一般性方法，可以得到如下去中心基于屬性Σ 協(xié)議。證明者可向驗(yàn)證者證明其擁有系統(tǒng)n個(gè)屬性中的t個(gè)。為方便敘述，不妨假設(shè)證明者擁有前t個(gè)證據(jù)。記為

①選擇大素?cái)?shù)q階乘法群G及其生成元g，記

②選取Hash函數(shù)H:{0,1}?→Zq；

③輸出全局參數(shù)gparam=

①隨機(jī)選取xi∈Zq，計(jì)算；

②輸出該機(jī)構(gòu)的公私鑰avki=Xi，aski=xi。

①隨機(jī)選取ri∈Zq，計(jì)算，hi=H(i||Ri||τ)，

②輸出證據(jù)Wτ,i={Ri,si}和標(biāo)識τ。

①對每個(gè)i∈{1,2,…,t}，隨機(jī)選取yi∈Zq，計(jì)算承諾

②對每個(gè)i∈{t+1,t+2,…,n}，隨機(jī)選取ci,zi∈Zq，Ri∈G，計(jì)算

③計(jì)算hi=H(i||Ri||τ),i∈{1,2,…,n}；

①用(0,c),(t+1,ct+1),…,(i,ci),…,(n,cn),i∈{t+1,t+2,…,n}這n-t+1 個(gè)點(diǎn)構(gòu)造n-t次拉格朗日插值多項(xiàng)式Pn-t(x)；

②計(jì)算ci=Pn-t(i),i∈{1,2,…,t}；

③計(jì)算zi=yi+cisimodq,i∈{1,2,…,t}；

①用(0,c),(t+1,ct+1),…,(i,ci),…,(n,cn),i∈{t+1,t+2,…,n}重構(gòu)n-t次拉格朗日插值多項(xiàng)式Pn-t(x)；

②驗(yàn)證是否有ci=Pn-t(i),i∈{1,2,…,t}；

③計(jì)算hi=H(i||Ri||τ),i∈{1,2,…,n}；

⑤如果以上都成立，則輸出1；否則輸出0。

①記A={i|ci≠c′i,i∈{1,2,…,n}}；

②si=(ci-c′i)-1(zi-z′i) modq,i∈A；

③輸出{si}i∈A。

②隨機(jī)選取n-t次多項(xiàng)式Pn-t(x)，記其常數(shù)項(xiàng)為c?；

3.3 安全性證明

本節(jié)證明上述構(gòu)造的協(xié)議是去中心基于屬性Σ協(xié)議，即具有正確性、特殊魯棒性、誠實(shí)驗(yàn)證者零知識性和屬性隱私性。

定理1如果所使用的標(biāo)準(zhǔn)Σ 協(xié)議、陷門可取樣關(guān)系和平滑秘密共享方案是正確的，且滿足3個(gè)條件，那么上述構(gòu)造的去中心基于屬性Σ 協(xié)議是正確的。

證明因?yàn)椤荰SR(TDG,Smp,Inv)是陷門可取樣關(guān)系，且Smp的輸出與的輸出同分布（條件1），所以算法產(chǎn)生的(xi,wi)可以作為的聲明與證據(jù)。條件3保證算法中的擴(kuò)展份額可以進(jìn)行。

對于任意屬性集A，當(dāng)i∈A時(shí)，COMi是由產(chǎn)生的，CHAi是產(chǎn)生的CHA在Γ?下的份額，RESi是由(COMi,Sti,CHAi,wi)產(chǎn)生的，因此只要是正確的，那么一定能有(COMi,CHAi,RESi)=1。當(dāng)i∈Aˉ時(shí)，(COMi,CHAi,RESi)是由(H(i||τ))產(chǎn)生的，只要是正確的，自然也有RESi)=1。

注意到，在方案中{CHAi|i∈N}本來就是CHA關(guān)于Γ?的完整份額，因此只要是正確的，就是正確的。

定理2如果所使用的標(biāo)準(zhǔn)Σ 協(xié)議具有特殊魯棒性且秘密共享方案是半平滑的，那么上述構(gòu)造的去中心基于屬性Σ 協(xié)議具有特殊魯棒性。

證明假設(shè)(COM,CHA,RES)和(COM,CHA′,RES′)是對應(yīng)于聲明Γ的相同證據(jù)標(biāo)識τ的兩個(gè)可接受副本，且CHA≠CHA′，只需要證明提取器能提取出滿足訪問結(jié)構(gòu)Γ的證據(jù){wi}i∈A。

令A(yù)={i|CHAi≠CHA′i,i∈N}，因?yàn)槭菍τ诿總€(gè)i∈A調(diào)用來提取wi的，所以由的特殊魯棒性可知能提取出{wi}i∈A，而且所有證據(jù){wi}i∈A都對應(yīng)于同一個(gè)標(biāo)識τ。

接下來證明A∈Γ。否則，如果A?Γ，那么就有。注意到={i|CHAi=CHA′i,i∈N}，而且CHAi和CHA′i分別是CHA和CHA′關(guān)于Γ?的完整份額，則有CHA=CHA′，與假設(shè)矛盾。

總之，{wi}i∈A是聲明Γ的一個(gè)合格證據(jù)，上述構(gòu)造的去中心基于屬性Σ 協(xié)議方案具有特殊魯棒性。

定理3如果所使用的標(biāo)準(zhǔn)Σ 協(xié)議具有誠實(shí)驗(yàn)證者零知識性，且滿足條件2，那么上述構(gòu)造的去中心基于屬性Σ 協(xié)議具有誠實(shí)驗(yàn)證者零知識性。

證明條件2 保證方案的仿真器能正確運(yùn)行。仿真器就是對每個(gè)i∈N使用，只要輸出的副本是不可區(qū)分的，那么輸出的副本就也是不可區(qū)分的。因此，只要具有誠實(shí)驗(yàn)證者零知識性，那么就具有誠實(shí)驗(yàn)證者零知識性。

定理4如果所使用的基礎(chǔ)Σ 協(xié)議是證據(jù)不可區(qū)分的，秘密共享方案是平滑的，那么上述構(gòu)造的去中心基于屬性Σ 協(xié)議具有屬性隱私性。

證明首先，因?yàn)榛A(chǔ)Σ 協(xié)議是證據(jù)不可區(qū)分的（文獻(xiàn)[18]），所以{COMi|i∈N}，只與yi=H(i||τ)有關(guān)，與所使用的屬性集無關(guān)。

最后，因?yàn)閧RESi|i∈N}由{COMi,CHAi|i∈N}完全決定，所以也與所使用的屬性集無關(guān)。

總之，整個(gè)副本{(COMi,CHAi,RESi)}i∈N與所使用的屬性集無關(guān)，屬性隱私性成立。

4 去中心基于屬性Σ 協(xié)議的應(yīng)用

4.1 去中心基于屬性簽名

使用著名的Fiat-Shamir 轉(zhuǎn)換可以將上述去中心基于屬性Σ 協(xié)議轉(zhuǎn)換成去中心基于屬性簽名，得到如下方案，記為∏ABS(Gsetup,Asetup,Gen,Sign,Vrf)。

（1）Gsetup(1k)：同3.1 節(jié)的，但增加一個(gè)從{0,1}*到挑戰(zhàn)空間的Hash函數(shù)H1。

（2）Asetup：同3.1節(jié)的

（3）Gen(aski,i,τ)：同3.1 節(jié)的，只是這里把輸出的wi稱為關(guān)于屬性i私鑰skτ,i，屬性集A的私鑰skA={skτ,i}i∈A。

（4）Sign(skA,m,Γ)：輸入私鑰skA={skτ,i}i∈A，消息m和訪問結(jié)構(gòu)Γ。

①令Wτ,A={wi}i∈A={skτ,i}i∈A=skA；

②{COM,St}←

③計(jì)算CHA=H1(COM||Γ||τ||m)；

④RES←

⑤輸出簽名σ=(τ,COM,CHA,RES)。

（5）Vrf(m,Γ,σ)：輸入消息m，訪問結(jié)構(gòu)Γ和簽名σ。

①計(jì)算CHA=H1(COM||Γ||τ||m)；

②b←

③如果b=1，則簽名σ有效，否則無效。

將上述一般性方法用于3.2 節(jié)的方案，可以得到一個(gè)新的去中心基于屬性簽名方案，其簽名算法如下，算法（1）～（3）和（5）基本上和3.2節(jié)方案的對應(yīng)算法一樣。

去中心基于屬性簽名方案：

（1）Gsetup(1k)：同3.2節(jié)的

（2）Asetup：同3.2節(jié)的

（3）Gen(aski,i,τ)：同3.2 節(jié)的，只是這里把輸出的wi稱為關(guān)于屬性i私鑰skτ,i，屬性集A的私鑰skA={skτ,i}i∈A。

（4）Sign(skA,m,Γ)：輸入私鑰，標(biāo)識τ和消息m。

①對每個(gè)i∈{1,2,…,t}，隨機(jī)選取yi∈Zq，計(jì)算

②對每個(gè)i∈{t+1,t+2,…,n}，隨機(jī)選取ci,zi∈Zq，Ri∈G，計(jì)算

③計(jì)算hi=H(i||Ri||τ),i∈{1,2,…,n}；

④計(jì)算c=H(R1||R2||…||Rn||Y1||Y2||…||Yn||m)；

⑤用(0,c),(t+1,ct+1),…,(i,ci),…,(n,cn),i∈{t+1,t+2,…,n}這n-t+1 個(gè)點(diǎn)構(gòu)造n-t次拉格朗日插值多項(xiàng)式Pn-t(x)；

⑥計(jì)算ci=Pn-t(i),i∈{1,2,…,t}；

⑦計(jì)算zi=yi+cisimodq,i∈{1,2,…,t}；

⑧輸出簽名σ=

（5）Vrf(m,Γ,σ)：同3.2 節(jié)的，只是這里c=H(R1||R2||…||Rn||Y1||Y2||…||Yn||m)。

Fiat-Shamir轉(zhuǎn)換保證簽名方案的不可偽造性，只要Σ 協(xié)議具有特殊魯棒性。去中心基于屬性簽名方案的屬性隱私性直接從去中心基于屬性Σ 協(xié)議繼承。

4.2 基于屬性的雙層簽名

雙層簽名（tow-tier signature）[31]是Bellare和Shoup在PKC2007提出的，簽名方案中用戶有兩個(gè)密鑰，第一個(gè)稱為一層密鑰，用來計(jì)算第二層密鑰；二層密鑰是一次性簽名密鑰，用來對消息進(jìn)行簽名，但每個(gè)二層簽名密鑰都只簽一個(gè)消息，每個(gè)消息都換新的密鑰來簽。這樣做的好處是可以提高安全性，達(dá)到標(biāo)準(zhǔn)模型下的可證明安全性。2016 年Anada 等[32]研究了基于屬性雙層簽名（attribute-based two-tier signatures），給出正式定義和一個(gè)方案。

用Fiat-Shamir 轉(zhuǎn)換也可以將3.1 節(jié)的一般性方案轉(zhuǎn)換成基于屬性雙層簽名方案。上節(jié)本文轉(zhuǎn)換出基于屬性簽名的一般方案，本節(jié)直接轉(zhuǎn)換出基于屬性雙層簽名的具體方案，得到首個(gè)去中心基于屬性雙層簽名方案。下面方案的訪問結(jié)構(gòu)是(t,n)門限，為敘述方便，假設(shè)用戶擁有前t個(gè)屬性。記為∏ABTTS(Gsetup,Asetup,PKGen,Sign,Vrf)。

（1）Gsetup(1k)：生成全局公共參數(shù)。

①選擇大素?cái)?shù)q階乘法群G及其生成元g，記

②選取Hash函數(shù)H:{0,1}?→Zq；

（2）Asetup(N)：由屬性機(jī)構(gòu)i運(yùn)行，生成屬性機(jī)構(gòu)i的公私鑰。

①隨機(jī)選取xi∈Zq，計(jì)算

②輸出該機(jī)構(gòu)的公私鑰avki=Xi，aski=xi。

（3）PKGen({avki,aski},i,τ)：輸入機(jī)構(gòu)i的公私鑰(Xi,xi)和證據(jù)標(biāo)識τ，生成第一層私鑰。

①隨機(jī)選取ri∈Zq，計(jì)算，hi=H(i||Ri||τ)，

②輸出用戶第一層私鑰{Ri,si}。

注：擁有屬性集A的用戶從相關(guān)的屬性機(jī)構(gòu)處獲得用同標(biāo)識τ生產(chǎn)的第一層私鑰{Ri,si}，構(gòu)成其第一層私鑰

（4）SKGen({avki,aski}i∈A,SKτ,A)：輸入屬性機(jī)構(gòu)的公鑰，用戶的第一層私鑰，生成第二層公私鑰。

①對每個(gè)i∈{1,2,…,t}，隨機(jī)選取yi∈Zq，計(jì)算

②對每個(gè)i∈{t+1,t+2,…,n}，隨機(jī)選取ci,zi∈Zq，Ri∈G，計(jì)算

③計(jì)算hi=H(i||Ri||τ),i∈{1,2,…,n}；

（5）Sign({avki}i∈A,SPKτ,A,SSKτ,A,m,Γ) ：輸入第二層公私鑰對(SPKτ,A,SSKτ,A)和消息m。

①計(jì)算c=H(SPKτ,A||τ||m)；

②用(0,c),(t+1,ct+1),…,(i,ci),…,(n,cn),i∈{t+1,t+2,…,n}這n-t+1 個(gè)點(diǎn)構(gòu)造n-t次拉格朗日插值多項(xiàng)式Pn-t(x)；

③計(jì)算ci=Pn-t(i),i∈{1,2,…,t}；

④計(jì)算zi=yi+cisimodq,i∈{1,2,…,t}；

（6）Vrf({avki}i∈A,SPKτ,A,σ,m,Γ)：輸入機(jī)構(gòu)的公鑰，二層公鑰SPKτ,A，消息m和簽名σ。

①計(jì)算c=H(SPKτ,A||τ||m)；

②用(0,c),(t+1,ct+1),…,(i,ci),…,(n,cn),i∈{t+1,t+2,…,n}重構(gòu)n-t次拉格朗日插值多項(xiàng)式Pn-t(x)；

③驗(yàn)證是否有ci=Pn-t(i),i∈{1,2,…,t}；

④計(jì)算hi=H(i||Ri||τ),i∈{1,2,…,n}；

⑥如果以上都成立，則輸出1；否則輸出0。

同樣地，由Fiat-Shamir 轉(zhuǎn)換可以保證上述簽名方案的所有安全性。3.2節(jié)、4.1節(jié)的例子與上面例子的安全性都基于離散對數(shù)困難性假設(shè)。

4.3 效率比較

基于屬性簽名方案已有很多，其中大部分是需要雙線性對運(yùn)算的，本文在4.1節(jié)給出的一般性方法可產(chǎn)生許多去中心基于屬性簽名方案，可以是有雙線性對運(yùn)算的方案，也可以是無雙線性對運(yùn)算的方案。一般來說，無對的方案效率會(huì)比較高，將本文的方案與現(xiàn)有的無對運(yùn)算的基于屬性簽名方案進(jìn)行比較。因?yàn)槲墨I(xiàn)[33-34]的方案都是門限的，所以本文的方案和文獻(xiàn)[35]的方案也選擇門限結(jié)構(gòu)來比較，結(jié)果見表1。在表1和表2中，n是屬性總數(shù)，t是簽名者的屬性個(gè)數(shù)，l是用戶數(shù)的上限，k為離散對數(shù)問題的安全參數(shù)，λ為RSA問題的安全參數(shù)。RSA模N的長度為2λ，因此當(dāng)k=160 時(shí)就可以達(dá)到λ=512 的安全強(qiáng)度。用E和E'分別表示數(shù)據(jù)規(guī)模為160 bit和1 024 bit的一次冪指數(shù)運(yùn)算，tE 就表示計(jì)算t次冪指數(shù)運(yùn)算。用DL 表示離散對數(shù)困難假設(shè)，RSA 表示RSA 假設(shè)，SRSA表示強(qiáng)RSA假設(shè)（strong RSA assumption）。

從表1 可以看出，本文的方案和文獻(xiàn)[35]的方案在各項(xiàng)指標(biāo)上是相當(dāng)?shù)?，只在簽名私鑰上本文的方案少1k。這兩個(gè)方案在除密鑰生成開銷外的所有指標(biāo)上都是最優(yōu)的，而且優(yōu)勢非常顯著。在密鑰生成開銷方面，最優(yōu)的是文獻(xiàn)[33]方案，但這個(gè)方案在其他指標(biāo)方面都是最差的。

Table 1 Comparison of ABS scheme performance efficiency表1 ABS方案性能效率對比

目前已有的基于屬性雙層簽名方案只有文獻(xiàn)[32]的方案，因此將本文4.2節(jié)的方案與文獻(xiàn)[32]的方案進(jìn)行效率比較，結(jié)果見表2。仍然以訪問結(jié)構(gòu)為(t,n)門限作為例子來進(jìn)行比較。

Table 2 Comparison of ABTTS scheme performance efficiency表2 ABTTS方案性能效率對比

為了更直觀地比較，用n=10,t=n/2,k=60,λ=1 024 計(jì)算了本文方案各項(xiàng)長度和計(jì)算開銷與文獻(xiàn)[32]方案相應(yīng)值的比率。雖然E和E'都是一次冪指數(shù)運(yùn)算，但由于數(shù)據(jù)規(guī)模差別很大，計(jì)算開銷也差別很大。在本文方案中，E 是160 bit 規(guī)模的冪指數(shù)運(yùn)算，而在文獻(xiàn)[32]方案中則是1 024 bit，數(shù)據(jù)長度相差6.4倍，計(jì)算開銷至少相差40 倍（長度倍數(shù)的平方）。在表2中，按40倍進(jìn)行估算。

從表2可以看出，對于除簽名計(jì)算之外的所有指標(biāo)，本文方案都大大優(yōu)于文獻(xiàn)[32]的方案。兩個(gè)方案的簽名計(jì)算都主要是數(shù)的相乘、相加和求逆，由于數(shù)據(jù)規(guī)模的原因，本文方案也是有很大優(yōu)勢的。

表2 中，主公鑰和主私鑰是與文獻(xiàn)[32]方案一樣按有中心的來計(jì)算的，如果按去中心的來計(jì)算，每個(gè)屬性機(jī)構(gòu)都需要各1k長的屬性機(jī)構(gòu)公鑰和私鑰度，因此系統(tǒng)機(jī)構(gòu)公鑰總長度為(n′+2)k，機(jī)構(gòu)私鑰總長度為n′k，其中n′為屬性機(jī)構(gòu)的個(gè)數(shù)，其最大值是n。按取最大值n′=n來計(jì)算，主公鑰長度的比率為5.86%，主私鑰長度的比率為312.50%。除了主公鑰和主私鑰的長度之外，其他指標(biāo)不受是否去中心的影響。也就是說，做到了去中心，本文方案仍然在除主私鑰和簽名計(jì)算之外的指標(biāo)上具有絕對的優(yōu)勢。因?yàn)樵谌ブ行南到y(tǒng)中，每個(gè)屬性機(jī)構(gòu)一定要有自己的私鑰，所以私鑰總數(shù)是肯定要增加的，但如果就每個(gè)屬性機(jī)構(gòu)來說，其私鑰長度仍然只有1k，仍然只是文獻(xiàn)[32]方案的31.25%。

綜上所述，本文方案在數(shù)據(jù)長度、計(jì)算開銷和去中心化等方面都具有顯著優(yōu)勢。

5 結(jié)束語

基于屬性密碼和Σ 協(xié)議都是密碼學(xué)的重要研究對象，本文將基于屬性引入到知識證明領(lǐng)域，研究基于屬性Σ 協(xié)議，給出其定義，刻畫其安全模型。去中心化可以提高基于屬性密碼系統(tǒng)的抗攻擊能力，解決有中心系統(tǒng)的瓶頸問題，本文基于標(biāo)準(zhǔn)Σ 協(xié)議、陷門可取樣關(guān)系和平滑秘密共享方案，給出一個(gè)去中心基于屬性Σ 協(xié)議的一般性構(gòu)造，并證明其安全性；作為去中心基于屬性Σ 協(xié)議的應(yīng)用，利用Fiat-Shamir轉(zhuǎn)換，得到去中心基于屬性簽名和去中心基于屬性雙層簽名的一般性構(gòu)造和相應(yīng)的例子。本文方案要求訪問結(jié)構(gòu)是平滑秘密共享方案，提出更一般訪問結(jié)構(gòu)的基于屬性Σ 協(xié)議是未來進(jìn)一步研究的目標(biāo)。