苗美霞，武盼汝，王贇玲

(西安郵電大學(xué) 網(wǎng)絡(luò)空間安全學(xué)院，陜西 西安 710121)

密碼累加器能夠高效地證明元素是否存在于集合中。具體來(lái)講，首先將集合X={x1，…，xn}中的所有元素累加到累加器accX中，然后計(jì)算元素xi∈X的證據(jù)wi，最后利用證據(jù)wi和累加值accX來(lái)證明元素xi∈X。密碼累加器與向量承諾[1-2]、零知識(shí)集合(ZK-sets)[3-4]等原語(yǔ)有緊密的聯(lián)系，三者都能解決(非)成員驗(yàn)證的問(wèn)題。但是，三者在驗(yàn)證內(nèi)容、隱私性等方面存在一定的區(qū)別。向量承諾[1-2]針對(duì)有序集合(向量) 提供驗(yàn)證，即不僅能夠證明元素mi存在于有序集合中，而且能證明mi是第i個(gè)位置上的消息，但是其計(jì)算復(fù)雜性較大。零知識(shí)集合[3-4]不僅能夠證明某個(gè)元素是否屬于集合，同時(shí)不泄漏任何關(guān)于集合的信息，如集合的大小。然而，零知識(shí)集合的驗(yàn)證開(kāi)銷(xiāo)與集合中元素的數(shù)量線性相關(guān)，效率較低。

BENALOH等[5]于1993年首次提出密碼累加器的概念，但是該構(gòu)造為靜態(tài)累加器，即累加集合固定不變。CAMENISCH等[6]于2002年提出了動(dòng)態(tài)累加器的概念，可以支持累加集合動(dòng)態(tài)地添加和刪除元素。然而，上述兩類(lèi)累加器僅支持集合中元素的成員證明，即xi∈X，而無(wú)法支持非成員證明，即無(wú)法提供y?X的證據(jù)。為了解決此問(wèn)題，LI等[7]于2007年首次提出了通用累加器的構(gòu)造，能夠同時(shí)實(shí)現(xiàn)成員和非成員證明。

密碼累加器自提出以來(lái)，許多學(xué)者對(duì)其進(jìn)行了大量的研究并給出了具體的構(gòu)造方案?；诓煌拿艽a工具，密碼累加器可分為基于RSA體制的累加器[5-8]、基于雙線性映射的累加器[9-12]和基于Merkle哈希樹(shù)的累加器[13]。密碼累加器有著廣泛的應(yīng)用場(chǎng)景。在訪問(wèn)控制系統(tǒng)中，將授權(quán)用戶的訪問(wèn)權(quán)限聚合到累加器中，授權(quán)用戶通過(guò)將成員證據(jù)作為訪問(wèn)憑證來(lái)訪問(wèn)系統(tǒng)。在匿名憑證系統(tǒng)中[6]，需要進(jìn)一步隱藏用戶的身份，將累加器和零知識(shí)證明[14]結(jié)合是解決這類(lèi)問(wèn)題的有效方法。在數(shù)據(jù)外包存儲(chǔ)中，密碼累加器可用作認(rèn)證數(shù)據(jù)結(jié)構(gòu)(Authenticated Data Structure，ADS)[15-18]，用戶利用計(jì)算結(jié)果和相應(yīng)證據(jù)來(lái)證明計(jì)算結(jié)果的正確性。在加密貨幣中，密碼累加器通過(guò)代替Merkle哈希樹(shù)來(lái)降低通信開(kāi)銷(xiāo)和提高驗(yàn)證效率[19]。此外，累加器還可應(yīng)用于時(shí)間戳[5]、隱私保護(hù)數(shù)據(jù)外包[20]、認(rèn)證字典[21]、編輯[22]、負(fù)責(zé)任的證書(shū)管理[23-24]等場(chǎng)景中。

筆者首先從密碼累加器的構(gòu)造方案和功能應(yīng)用等方面對(duì)現(xiàn)有方案進(jìn)行了分類(lèi)、分析和總結(jié)；其次介紹了密碼累加器的主要應(yīng)用場(chǎng)景；最后指出了現(xiàn)有方案面臨的一些問(wèn)題以及未來(lái)的發(fā)展趨勢(shì)和研究方向。

1 累加器模型與定義

1.1 系統(tǒng)模型

一般來(lái)講，一個(gè)密碼累加器主要包括以下3個(gè)主體。

(1) 累加器管理員：生成密鑰對(duì)，創(chuàng)建并發(fā)布累加器。此外，動(dòng)態(tài)累加器可以添加和刪除元素，并創(chuàng)建這些元素的成員證據(jù)。通用累加器可以對(duì)沒(méi)有被聚合到累加器中的元素創(chuàng)建非成員證據(jù)。

(2) 用戶：接受累加器管理員提供的證據(jù)，證據(jù)是他們?cè)诶奂悠飨到y(tǒng)中的憑證，可以提供給驗(yàn)證方進(jìn)行驗(yàn)證。之后有新的元素添加到累加器時(shí)，用戶可以在本地更新證據(jù)。

(3) 驗(yàn)證方：通過(guò)用戶提供的證據(jù)和累加器公開(kāi)的累加值，來(lái)檢查元素x是否在此累加器中。

下面分別對(duì)靜態(tài)累加器、動(dòng)態(tài)累加器以及通用累加器進(jìn)行了定義。用X表示累加器的累加值域，用X={x1，…，xn}表示累加器中元素的集合，用t表示累加元素的上限，t可以是無(wú)窮的，表示累加域無(wú)界。此外，陷門(mén)信息(即私鑰skacc)是可選擇的輸入，因?yàn)橛行├奂悠餍枰蓍T(mén)信息才能更新累加器或證據(jù)，而有些不需要。

定義1一個(gè)靜態(tài)累加器方案可以描述成一個(gè)四元組Π=(Gen，Eval，WitCreate，Ver)。

(1) Gen(1λ，t)：累加器管理員輸入安全參數(shù)λ、累加元素上限t，輸出密鑰對(duì)(skacc，pkacc)，如果累加器不存在陷門(mén)信息，則陷門(mén)信息skacc=φ。

(2) Eval((skacc，pkacc)，X)：累加器管理員計(jì)算累加值和輔助信息。輸入集合、密鑰對(duì)(skacc，pkacc)，輸出累加值accX，并將其公布給用戶和驗(yàn)證方；輸出輔助信息aux，并發(fā)送給用戶，使得用戶可以在本地更新證據(jù)。

(3) WitCreate((skacc，pkacc)，xi，accX，aux)：累加器管理員創(chuàng)建用戶xi的證據(jù)。輸入密鑰對(duì)(skacc，pkacc)、累加值accX、元素xi∈X及輔助信息aux，生成xi的證據(jù)wi。

(4) Ver(pkacc，xi，wi，accX)：驗(yàn)證方驗(yàn)證元素是否在累加器中。輸入公鑰pkacc、累加值accX、元素xi及其證據(jù)wi。如果wi是xi∈X的證據(jù)，則返回1；否則，返回0。

在此基礎(chǔ)上，如果累加器可以動(dòng)態(tài)地更新集合X，并可以有效地更新集合中元素的證據(jù)，那么該累加器為動(dòng)態(tài)累加器。通過(guò)對(duì)靜態(tài)累加器定義擴(kuò)展，可以得到一個(gè)動(dòng)態(tài)累加器。

定義2動(dòng)態(tài)累加器在靜態(tài)累加器的基礎(chǔ)上添加了一個(gè)三元組Π=(Add，Del，MemWitUp)。

(1) Add((skacc，pkacc)，accX，aux，x)：累加器管理員添加元素x?X到累加器中，并更新累加值accX。輸入密鑰對(duì)(skacc，pkacc)、累加值accX、輔助信息aux和要添加的元素x?X，輸出更新后的累加值accX′=accX∪{x}，并更新輔助信息aux。

(2) Del((skacc，pkacc)，accX，x，aux)：累加器管理員刪除元素x∈X時(shí)，更新累加值accX。輸入密鑰對(duì)(skacc，pkacc)、累加值accX、輔助信息aux和被刪除的元素x∈X，輸出更新后的累加值accX′=accX{x}，并更新輔助信息aux。

(3) MemWitUp((skacc，pkacc)，x，wi，aux)：添加或刪除元素x后，用戶更新元素xi的證據(jù)wi。輸入密鑰對(duì)(skacc，pkacc)、x、輔助信息aux和xi的證據(jù)wi，輸出xi更新后的證據(jù)w′i。

上述累加器可以對(duì)元素x∈X構(gòu)造成員證據(jù)，但無(wú)法對(duì)元素x?X構(gòu)造非成員證據(jù)。而通用累加器既可以對(duì)元素x∈X構(gòu)造成員證據(jù)，又可以對(duì)元素x?X構(gòu)造非成員證據(jù)。

定義3通用累加器在上述WitCreate算法中，可以添加一個(gè)布爾參數(shù)type，創(chuàng)建成員證據(jù)時(shí)type=0，創(chuàng)建非成員證據(jù)時(shí)type=1。如果通用累加器不具備動(dòng)態(tài)累加器添加或刪除元素的功能，則為通用靜態(tài)累加器，否則為通用動(dòng)態(tài)累加器。對(duì)于通用動(dòng)態(tài)累加器，則需要在定義1和定義2的基礎(chǔ)上添加NonMemWitUp算法，可以在累加集合更新時(shí)，對(duì)非成員證據(jù)進(jìn)行更新。

(1) NonMemWitUp((skacc，pkacc)，x，w，aux)：在添加或刪除某個(gè)元素x時(shí)，用戶更新非成員元素y?X的證據(jù)u為u′。輸入密鑰對(duì)(skacc，pkacc)、x、輔助信息aux和y的證據(jù)u，輸出y更新后的證據(jù)u′。

1.2 累加器的性質(zhì)

累加器有3個(gè)安全性質(zhì)：正確性、健壯性(包括無(wú)碰撞性和不可否認(rèn)性)、不可區(qū)分性。3個(gè)安全性質(zhì)定義如下：

(1) 正確性：對(duì)于所有誠(chéng)實(shí)生成的密鑰、所有誠(chéng)實(shí)計(jì)算的累加值和證據(jù)，驗(yàn)證算法Ver將始終返回1。

(2) 健壯性：傳統(tǒng)上，健壯性指無(wú)碰撞性，對(duì)于元素y?X，很難找到其成員證據(jù)[8]，對(duì)于元素xi∈X，也很難找到其非成員證據(jù)[7]；健壯性的另一種擴(kuò)展形式是不可否認(rèn)性[23]，不可否認(rèn)性是通用累加器特有的性質(zhì)，它表示為元素x∈X或x?X計(jì)算兩個(gè)相互矛盾的證據(jù)在計(jì)算上是不可能的。

(3) 不可區(qū)分性：不可區(qū)分性[25-26]與安全隱私相關(guān)，指累加器和持有證據(jù)的用戶都不會(huì)泄露有關(guān)累加集合X的信息。

分別對(duì)靜態(tài)累加器、動(dòng)態(tài)累加器和通用累加器進(jìn)行形式化定義。具體如下：

(1) 安全性(靜態(tài))：一個(gè)靜態(tài)累加器是安全的，如果對(duì)于所有概率多項(xiàng)式時(shí)間(Probabilistic Polynomial Time，PPT)對(duì)手Aλ，有

(2) 安全性(動(dòng)態(tài))：令M為接收輸入(f，aux，g)的交互式圖靈機(jī)，其中，aux是有關(guān)f的輔助信息，g∈ZA。M維護(hù)一個(gè)元素集合X，該集合最初為空，初始累加器acc設(shè)置為g。M響應(yīng)兩種消息：對(duì)于消息D(add，x)，它確保x∈X，將x添加到集合X中，通過(guò)運(yùn)行D修改acc，然后將更新后的acc發(fā)回；對(duì)于消息D(delete，x)，它將檢查x∈X，將其從集合X中刪除，通過(guò)運(yùn)行D更新acc，然后將更新后的acc發(fā)回。最后，M輸出X和acc的當(dāng)前值。如果對(duì)于所有PPT的對(duì)手Aλ，動(dòng)態(tài)通用累加器方案是安全的，則有

(3) 安全性(通用)：一個(gè)通用累加器是安全的，如果對(duì)于所有PPT對(duì)手Aλ，有

2 基于RSA體制的累加器

2.1 靜態(tài)累加器

(1) Gen(1λ)：累加器管理員輸入安全參數(shù)λ，生成累加器初始值g∈Zn，輸出密鑰對(duì)(skacc，pkacc)=((p，q)，N)，其中N由兩個(gè)大的強(qiáng)素?cái)?shù)p、q組成，且N=pq。

(2) Eval(pkacc，X)：累加器管理員計(jì)算累加值。累加值accX=gx1，…，xnmodN，其中X={x1，…，xn}，且xi是素?cái)?shù)。

(3) WitCreate(pkacc，xi，accX)：累加器管理員創(chuàng)建用戶的證據(jù)。輸入公鑰pkacc、累加值accX和元素xi，生成xi的證據(jù)wi=gx1，…，xi-1，xi+1，…，xnmodN。

值得注意的是，RSA累加器在計(jì)算過(guò)程中需要進(jìn)行模冪運(yùn)算，集合X中的元素在指數(shù)中是乘法關(guān)系，所以上述構(gòu)造的元素必須限制為素?cái)?shù)，如果聚合的是非素?cái)?shù)，則可能存在某個(gè)值是另2個(gè)值的乘積，進(jìn)而敵手可以很容易偽造證據(jù)進(jìn)行驗(yàn)證。

2.2 動(dòng)態(tài)累加器

在一些需要添加或撤銷(xiāo)成員的應(yīng)用場(chǎng)景中，如在群簽名、匿名憑證撤銷(xiāo)系統(tǒng)中，群管理員需要?jiǎng)討B(tài)添加或撤銷(xiāo)成員資格。然而，上述靜態(tài)累加器的集合元素固定，不具備添加或刪除的功能。因此，CAMENISCH等[6]為了解決匿名憑證系統(tǒng)的撤銷(xiāo)等問(wèn)題，將累加器擴(kuò)展為動(dòng)態(tài)。動(dòng)態(tài)累加器允許累加器管理員動(dòng)態(tài)地添加或刪除元素，并且可以動(dòng)態(tài)地更新累加器和成員證據(jù)。在添加元素時(shí)，更新累加器、成員證據(jù)只需要進(jìn)行簡(jiǎn)單的模指運(yùn)算，可以很容易實(shí)現(xiàn)；而在刪除元素時(shí)，CAMENISCH等[6]采用了RSA算法的基本思想來(lái)更新累加器，通過(guò)使用陷門(mén)信息skacc進(jìn)行求逆運(yùn)算，可以將元素從累加器中刪除。刪除元素時(shí)需要用陷門(mén)信息更新累加值，但更新成員證據(jù)時(shí)無(wú)需陷門(mén)信息。方案具體如下：

(1) Gen(1λ)：累加器管理員生成公私鑰對(duì)，初始空累加值acc0=g∈ZN。輸入安全參數(shù)1λ，輸出累加器管理員公私鑰對(duì)(skacc，pkacc)=((p，q)，N)，其中N=pq，且p、q為大的強(qiáng)素?cái)?shù)。

(2) Add(accX，x，X，pkacc)：累加器管理員添加元素x后更新累加值accX。添加元素x?X到累加器中，X更新為X∪{x}，更新后的累加值為

(3) Del(accX，x，X，(skacc，pkacc))：累加器管理員刪除元素x后更新累加值accX。刪除元素x時(shí)，需要陷門(mén)信息skacc，通過(guò)計(jì)算的累加值為

值得注意的是，執(zhí)行刪除操作時(shí)，累加器管理員需要用到陷門(mén)信息skacc來(lái)更新累加值，此時(shí)不誠(chéng)實(shí)的累加器管理員可以通過(guò)陷門(mén)信息隨意更改累加值、對(duì)成員創(chuàng)建假的證據(jù)等，所以必須要求累加器管理員是可信的。

2.3 通用累加器

該方案給出了兩種創(chuàng)建非成員證據(jù)的方法，一種需要陷門(mén)信息skacc，另一種不需要。不需要陷門(mén)信息的方法在計(jì)算非成員證據(jù)時(shí)需要找到a、b，使得ax*+byi=1，而x*與累加器成員個(gè)數(shù)線性相關(guān)，計(jì)算開(kāi)銷(xiāo)很大。需要陷門(mén)信息的方法在計(jì)算證據(jù)時(shí)，可通過(guò)x*′=x*mod(p-1)(q-1)，其中p、q為陷門(mén)信息，使得x*′在進(jìn)行模運(yùn)算后很小，從而在ax*′+byi=1中，證據(jù)的計(jì)算開(kāi)銷(xiāo)僅為O(1)。因此在某些可以使用陷門(mén)信息的場(chǎng)景下，選擇需要陷門(mén)信息計(jì)算非成員證據(jù)的計(jì)算量小；而對(duì)于某些無(wú)法使用陷門(mén)信息的場(chǎng)景下，不需要陷門(mén)信息計(jì)算非成員證據(jù)是一個(gè)很好的選擇。下面給出了兩種計(jì)算非成員證據(jù)的具體構(gòu)造。

2.3.1 需要陷門(mén)信息

使用skacc計(jì)算非成員證據(jù)。假設(shè)存在受信任的累加器管理員知道skacc=(p，q)、集合X={x1，…，xn}、累加器accX=gx1，…，xnmodN，其中g(shù)∈QRN。累加器管理員計(jì)算元素yi?X的非成員證據(jù)如下：

2.3.2 不需要陷門(mén)信息

該方案同時(shí)支持元素的動(dòng)態(tài)添加和刪除，并實(shí)現(xiàn)相應(yīng)證據(jù)的高效更新，具體的非成員證據(jù)更新算法NonMemWitUp如下：

NonMemWitUp(x，(a，B)，accX，accX′)：

添加：添加元素x∈XX，且x≠yi，給定更新前后的累加器accX和accX′，則yi∈XX的證據(jù)ui=(a，B)更新如下：

(1) 找到兩個(gè)整數(shù)a0′和r0，使得a0′x+r0yi=1，由于x、yi都為素?cái)?shù)，所以a0′、r0可以很容易找到；

(2) 兩邊同乘更新前的證據(jù)a，使得a0′ax+r0ayi=a；

(1) 選擇一個(gè)整數(shù)r，使得ax-ryi∈Z2l；

2.4 支持批處理更新的累加器

LI等[7]簡(jiǎn)要地概述了累加器可以批量添加和刪除元素，并未給出具體的算法，而B(niǎo)ONEH等[19]給出了具體的批量添加(BatchAdd)和批量刪除(BatchDel)的算法。在BatchDel中，存在一個(gè)ShamirTrick算法，可以將兩個(gè)元素的證據(jù)聚合在一起。具體的算法如下：

(1) BatchAdd(accX，{x1，…，xm})

② accX′←accx*

(2) BatchDel(accX，(x1，w1)…(xm，wm))

① accX′←w1

②x*←x1

③ fori←2，i≤m

④ accX′←ShamirTrick(accX′，wi，x*，xi)

⑤x*←x*·xi

⑥ return accX′

(3) ShamirTrick(w1，w2，x1，x2)

②a，b←Bezout(x1，x2)

PoE協(xié)議輸入：u、w∈G，x∈Z；證明：ux=w。

① 驗(yàn)證方發(fā)送隨機(jī)的λ比特的素?cái)?shù)l給證明方；

② 證明方計(jì)算(q，r)，使得x=ql+r，并將Q=uq發(fā)送給驗(yàn)證方；

③ 驗(yàn)證方計(jì)算r=xmodl，當(dāng)Qlur=w成立時(shí)接受。

此外，為了減小通信開(kāi)銷(xiāo)，BONEH等[19]也使用了Fiat-Shamir啟發(fā)式方法[32]及多輪協(xié)議的概括[33]，將PoE協(xié)議改成了非交互式協(xié)議NI-PoE。并將NI-PoE協(xié)議運(yùn)用到累加器中來(lái)提高批處理成員驗(yàn)證的效率，具體構(gòu)造如下：

MemWitCreate*(accX，{x1，…，xn})

②wx*←WitCreate(accX，x*)

③ returnwx*，π=NI-PoE(x*，wx*，accX)

VerMem*(accX，{x1，…，xn}，w={wx*，π})

除了成員驗(yàn)證效率得到了提高，非成員驗(yàn)證的效率也提高了。當(dāng)進(jìn)行批處理非成員驗(yàn)證時(shí)，一種方法是通過(guò)NonMemWitCreate*算法將多個(gè)非成員元素直接相乘來(lái)創(chuàng)建證據(jù)，驗(yàn)證時(shí)只需要驗(yàn)證VerNonMem*算法中的協(xié)議運(yùn)行是否成功。另一種方法是通過(guò)AggNonMemWit算法聚合這些非成員證據(jù)來(lái)創(chuàng)建證據(jù)。

PoKE2協(xié)議輸入：u、w∈G；證據(jù)：x∈Z；證明：ux=w。

① 驗(yàn)證方發(fā)送g給證明方；

② 證明方發(fā)送z=gx給驗(yàn)證方；

③ 驗(yàn)證方發(fā)送隨機(jī)的λ比特的素?cái)?shù)l和一個(gè)挑戰(zhàn)值α給證明方；

④ 證明方計(jì)算(q，r)，使得x=ql+r，并將Q=uqgαq和r發(fā)送給驗(yàn)證方；

⑤ 驗(yàn)證方檢查Qlurgαr=wzα是否成立。

NonMemWitCreate*(accX，x*，y*)：//accX=gx*，x*=∏x∈Xx，y∈∏yi

①a，b←Bezout(x*，y*)//ax*+by*=1

④πg(shù)←NI-PoE(y*，B，gV-1)//By*=gV-1

①a，b←Bezout(y1，y2)

③a′←ba1y2+aa2y1

④a12←a′mody1y2

⑧πg(shù)←NI-PoE(y12，B12，gV-1)//By1212=gV-1，y12=y1y2，

3 基于雙線性映射的累加器

RSA累加器方案中，累加器聚合的元素被限制為素?cái)?shù)，需要把元素轉(zhuǎn)變?yōu)樗財(cái)?shù)[34]后才能進(jìn)行累加。為了解決這個(gè)問(wèn)題，NGUYEN等[9]首次提出了基于強(qiáng)Diffie-Hellman(SDH)假設(shè)的雙線性映射動(dòng)態(tài)累加器，此累加器不要求累加值域?yàn)樗財(cái)?shù)。DAMGARD等[10]和AU等[11]補(bǔ)充了LI等[7]提出的通用累加器構(gòu)造，使得雙線性映射累加器同RSA累加器一樣，都具備了動(dòng)態(tài)和通用的功能。然而，上述累加器中累加集合的大小需提前設(shè)定，如累加的元素?cái)?shù)量上限為q。因此，TOLGA等[35]通過(guò)一組累加器突破了上述累加集合大小受限的問(wèn)題。此外，CAMENISCH等[12]也給出了一種基于q-DHE假設(shè)的方案，此方案對(duì)證據(jù)和累加器的更新無(wú)需陷門(mén)參與，即支持公開(kāi)更新。

3.1 動(dòng)態(tài)累加器

RSA累加器的累加域元素要求為素?cái)?shù)，為了解決這一問(wèn)題，NGUYEN等[9]提出了基于q-SDH假設(shè)的雙線性映射累加器，其中累加的元素的數(shù)量上限為q。相比于RSA累加器采用模冪運(yùn)算聚合累加元素，此構(gòu)造以雙線性對(duì)運(yùn)算為基礎(chǔ)。具體構(gòu)造如下：

(2) Eval(X，pkacc)：累加器管理員計(jì)算累加值accX。輸入集合X={x1，…，xn}?Zp{-s}，其中n≤q，使用pkacc而無(wú)需私鑰s的情況下計(jì)算累加器accX=gu∏x∈X(x+s)。

(3) WitCreate(pkacc，xi，accX，X)：累加器管理員創(chuàng)建用戶xi的證據(jù)。輸入公鑰pkacc、累加值accX、集合X和元素xi，生成xi∈X的證據(jù)為wi=gu∏x∈X{xi}(x+s)。

(4) VerMem(accX，xi，wi)：驗(yàn)證方驗(yàn)證xi是否在累加器中。通過(guò)驗(yàn)證e(wi，gxigs)=e(accX，g)是否成立。如果成立，則輸出1，否則輸出0。

要注意的是，在上述構(gòu)造中，公鑰大小與累加元素的上限q線性相關(guān)，如果q很大，則元素公鑰將會(huì)非常大，而在RSA累加器中，公鑰是常數(shù)N。此外，RSA動(dòng)態(tài)累加器只有在刪除操作更新累加值時(shí)會(huì)用到陷門(mén)信息skacc，而在此構(gòu)造中，更新累加值時(shí)，包括添加和刪除都需要用到陷門(mén)信息。

雙線性映射動(dòng)態(tài)累加器除了該基于q-SDH假設(shè)的方案之外，CAMENISCH等[12]也給出了一種基于q-DHE假設(shè)的構(gòu)造。此方案采用了兩個(gè)公開(kāi)的集合V和Vw，分別是被累加到累加器中的元素集合和證據(jù)wi被創(chuàng)建時(shí)，累加器添加或刪除了哪些元素的集合。當(dāng)證據(jù)需要更新時(shí)，可以通過(guò)Vw對(duì)所有元素的證據(jù)公開(kāi)更新。具體構(gòu)造如下：

(1) Gen(1λ，t)：輸入?yún)?shù)1λ和累加元素上限t，累加器管理員隨機(jī)選擇值γ∈Zq，生成初始累加器accφ=1、初始狀態(tài)stateφ=(φ，gγ1，…，gγq，gγq+2，…，gγ2q)和公私鑰對(duì)：

(pkacc，skacc)=((g1，…，gq，gq+2，…，g2q，e(g，g)γq+1，pksig)，(γ，sksig))=
((gγ1，…，gγq，gγq+2，…，gγ2q，e(g，g)γq+1，pksig)，(γ，sksig)) 。

stateU∪{i}={U∪{i}，g1，…，gn，gn+2，…，g2n} 。

(3) Update(pkacc，V，stateU)：用戶輸出accV=∏v∈Vgn+1-v(V?U)。

(4) WitUp(pkacc，wi，Vw，V，accV，stateU)：任何不可信實(shí)體都可以進(jìn)行證據(jù)的更新。如果i∈V且V∪Vw?U，計(jì)算

輸出wi′=(w′，σi，gi)。

(5) VerMem(pkacc，i，wi，accV)：驗(yàn)證方驗(yàn)證i是否在累加器中。不可信實(shí)體更新證據(jù)wi后，用戶i獲得新的證據(jù)wi′后，通過(guò)等式e(gi，accV)=ze(g，w)來(lái)驗(yàn)證i是否在累加器中。

在刪除成員時(shí)，RSA累加器[6-7]和基于SDH假設(shè)的雙線性映射累加器[9-10]更新累加值都會(huì)用到陷門(mén)信息，并且更新操作都進(jìn)行了冪運(yùn)算。而該方案在刪除成員時(shí)更新累加器不需要陷門(mén)信息，并且更新操作無(wú)需進(jìn)行冪運(yùn)算，只用進(jìn)行簡(jiǎn)單的乘法運(yùn)算，因此計(jì)算效率大大提升。

3.2 通用累加器

上述累加器無(wú)法支持非成員驗(yàn)證，因此，DAMGARD等[10]首次基于SDH假設(shè)將雙線性映射累加器擴(kuò)展為通用累加器，具體非成員證據(jù)的構(gòu)造和驗(yàn)證方法如下：

(2) VerNonMem(accX，y，(ay，By))：驗(yàn)證方驗(yàn)證元素y的非成員身份。已知公共參數(shù)gs，驗(yàn)證通過(guò)檢查e(ay，gygs)=e(accXgBy，g)是否成立。如果成立，則輸出1，否則輸出0。

在該方案的基礎(chǔ)上，AU等[11]也提出了基于SDH假設(shè)的通用累加器方案，使得無(wú)需使用陷門(mén)信息便可進(jìn)行累加器的更新。

4 基于Merkle哈希樹(shù)的累加器

Merkle哈希樹(shù)累加器是一類(lèi)設(shè)計(jì)簡(jiǎn)潔且高效的累加器。Merkle哈希樹(shù)中，葉子節(jié)點(diǎn)為集合元素的哈希值，內(nèi)部節(jié)點(diǎn)為左右孩子的哈希值，根節(jié)點(diǎn)為最終累加值。元素xi的成員證據(jù)由xi到根節(jié)點(diǎn)路徑上的所有兄弟節(jié)點(diǎn)組成，通過(guò)重構(gòu)根節(jié)點(diǎn)來(lái)判斷元素xi是否存在于集合中。然而，RSA累加器和雙線性映射累加器只需O(1)大小的證據(jù)，而Merkle哈希樹(shù)累加器需要O(logN)大小的證據(jù)，其中N表示累加元素的總數(shù)。

CAMACHO等[13]給出了一個(gè)通用累加器方案的簡(jiǎn)單構(gòu)造，該方案和LI等[7]的通用累加器方案在功能上是相似的，適用于動(dòng)態(tài)集合并允許非成員身份證明，并且該方案在存在抗碰撞哈希函數(shù)的假設(shè)下可證明是安全的。該方案實(shí)現(xiàn)非成員證明的主要思想為：集合中元素按順序存儲(chǔ)，若某元素的左右相鄰元素為連續(xù)元素，則該元素不在集合中。例如，x的左右相鄰元素為xα、xβ，且xα、xβ連續(xù)，則x為非成員元素。方案具體構(gòu)造如下：

(1) Gen(1λ)：累加器管理員輸入安全參數(shù)λ，生成初始累加器acc0和M0。初始集合X為空，是M={0，1}λ的子集；然后選擇一個(gè)哈希函數(shù)H，計(jì)算一個(gè)隨機(jī)索引i∈K，并設(shè)置H=Hi；最后將m的初始值設(shè)置為H(-∞‖+∞)的根節(jié)點(diǎn)Nm，并且累加器管理員公布acc0=ProofNm。

(2) WitCreate(m，x)：累加器管理員創(chuàng)建證據(jù)。輸入x∈M和內(nèi)存m，計(jì)算證據(jù)w=(w1，w2)如下：

① 如果x∈X，則證據(jù)w1=(xα，xβ)，其中x=xα或x=xβ；否則x?X，證據(jù)w1=(xα，xβ)，其中xα

② 設(shè)置w2是由H(xα‖xβ)生成的m的最小子樹(shù)。

(3) Update(m，x)：累加器管理員更新累加器、內(nèi)存m和證據(jù)w。輸入x∈X，acc和m。

① 添加：x?X時(shí)，添加x操作如下：將m中適當(dāng)節(jié)點(diǎn)處的值H(xα‖xβ)替換為H(xα‖x)，其中xα

② 刪除：刪除x時(shí)，查找包含x的兩個(gè)節(jié)點(diǎn)，用Vα，Vβ表示。刪除x后，用H(xα‖xβ)代替之前的H(xα‖x)和H(x‖xβ)，并保持樹(shù)平衡。更新后的樹(shù)為m′、累加器acc′=Proofm′、證據(jù)w′=(del，w1，w2，w3)。

(4) CheckUpdate(acc，acc′，w′)：在添加或刪除元素后，用戶檢查累加器管理員提供的更新后的元素，更新正確，則輸出OK。輸入x∈M、更新前的累加器acc、更新后的累加器acc′和更新后的證據(jù)w′。如果w′=(add，w1，w2)且符合下列前提，則算法輸出1；否則輸出0。刪除操作也類(lèi)似，這里省略。

①w1是通過(guò)在w2上添加葉子獲得的樹(shù)。

② 除了值是H(xα‖xβ)的節(jié)點(diǎn)以外，w1、w2樹(shù)中其余所有節(jié)點(diǎn)都相同。

③ Proofw1=acc，Proofw2=acc′。

④H(xα‖x)，H(x‖xβ)∈Vw2。

(5) VerMem(x，w，acc)：驗(yàn)證方驗(yàn)證某個(gè)元素是否在集合中。輸入x∈M、證據(jù)w=((w1，w2)，u)和累加器acc。檢查(a)Proofu=acc；(b)H(x′‖x″)∈Vu和(c)(x=x′)，(c)(x=x″)或(c′)(x′

首先，在RSA累加器和雙線性映射累加器中，需要累加器管理員生成陷門(mén)信息來(lái)更新累加器或證據(jù)，而Merkle哈希樹(shù)累加器[13]不需要陷門(mén)信息來(lái)更新累加器或證據(jù)，因而無(wú)需管理員參與。其次，Merkle哈希樹(shù)累加器主要基于哈希算法，而RSA累加器和雙線性映射累加器分別需要模指數(shù)運(yùn)算和雙線性對(duì)運(yùn)算，所以Merkle哈希樹(shù)累加器計(jì)算效率高。然而，Merkle哈希樹(shù)累加器的證據(jù)大小與集合大小呈對(duì)數(shù)關(guān)系，所以通信代價(jià)較高。

5 三類(lèi)密碼累加器的分析與比較

對(duì)上述3類(lèi)密碼累加器的構(gòu)造方案進(jìn)行了比較和總結(jié)。RSA累加器基于強(qiáng)RSA假設(shè)，具有較短的公共參數(shù)，且可以很容易擴(kuò)展到通用累加器[7]或動(dòng)態(tài)累加器[6]，但此類(lèi)型下的累加器通常需要昂貴的操作才能將元素以素?cái)?shù)形式編碼。雙線性映射累加器有基于q-SDH假設(shè)和q-DHE假設(shè)的兩種類(lèi)型，它們不需要素?cái)?shù)編碼，但需要最大元素?cái)?shù)量的公共參數(shù)。大多數(shù)RSA累加器和雙線性映射累加器都需要可信累加器管理員生成陷門(mén)信息。如在RSA累加器中，任何知道模N=pq分解的對(duì)手都可以輕易地作弊。而Merkle哈希樹(shù)累加器不需要陷門(mén)信息，把這類(lèi)不需要陷門(mén)信息的累加器也稱為強(qiáng)累加器。Merkle哈希樹(shù)累加器基于抗碰撞的哈希函數(shù)假設(shè)，是一類(lèi)高效簡(jiǎn)潔的累加器，但是該類(lèi)構(gòu)造不需要可信的累加器管理員，所以需要O(logN)大小的證據(jù)(N表示累加集合的元素?cái)?shù)量)，而前兩類(lèi)需要可信設(shè)置的累加器只需O(1)大小的證據(jù)。此外，RSA累加器和雙線性映射累加器也有一些構(gòu)造[23，28]。這些構(gòu)造下，累加器管理員完全不受信任，但這些構(gòu)造要么證據(jù)數(shù)量隨集合X的大小呈對(duì)數(shù)增長(zhǎng)，要么依賴尚未在密碼學(xué)進(jìn)行深入研究的代數(shù)群。

表1給出了3類(lèi)密碼累加器構(gòu)造方案的詳細(xì)比較[26，36]。其中，S代表靜態(tài)累加器，D代表動(dòng)態(tài)累加器，U代表通用累加器，w代表成員證據(jù)的更新，u代表非成員證據(jù)的更新，a和d分別代表添加和刪除操作時(shí)累加值的更新，acc代表累加值的更新，B代表累加器累加元素是否具有上限，|pkacc|、|w|、|u|分別代表公共參數(shù)，成員證據(jù)和非成員證據(jù)的大小。

表1 不同類(lèi)型累加器的比較

6 應(yīng) 用

累加器自提出以來(lái)，有著廣泛的應(yīng)用場(chǎng)景。包括時(shí)間戳[5]、群簽名[6，37]、環(huán)簽名[38]、訪問(wèn)控制系統(tǒng)[39]、匿名憑證系統(tǒng)[6]、加密貨幣[19]、認(rèn)證數(shù)據(jù)結(jié)構(gòu)(ADS)[15-18]等。此外，還被用在隱私保護(hù)數(shù)據(jù)外包[20]、認(rèn)證字典[21]、編輯[22]、負(fù)責(zé)任的證書(shū)管理[23-24]等應(yīng)用中。介紹幾種典型應(yīng)用：累加器在時(shí)間戳、成員資格撤銷(xiāo)中的應(yīng)用。此外，還會(huì)介紹最近比較流行的應(yīng)用：累加器在區(qū)塊鏈[40-42]中的應(yīng)用。

6.1 時(shí)間戳

BENALOH等[5]首次提出了密碼學(xué)累加器，并應(yīng)用于時(shí)間戳中。時(shí)間戳可以在任何文檔上附加一個(gè)“發(fā)布”日期，以證明原始文件在簽名時(shí)間之前已經(jīng)存在。在傳統(tǒng)的時(shí)間戳系統(tǒng)中，機(jī)構(gòu)需要對(duì)文件逐個(gè)添加時(shí)間戳，驗(yàn)證方也需要逐個(gè)驗(yàn)證，使得時(shí)間戳的生成和驗(yàn)證代價(jià)高。為了提高時(shí)間戳系統(tǒng)的效率，BENALOH等[5]設(shè)計(jì)了基于密碼累加器的時(shí)間戳系統(tǒng)，該系統(tǒng)可以批量的生成和驗(yàn)證時(shí)間戳。具體方法為：將某個(gè)時(shí)刻產(chǎn)生的所有文檔聚合到累加器中，然后對(duì)該累加器附加時(shí)間戳。驗(yàn)證t時(shí)刻的文檔時(shí)，僅需驗(yàn)證該文檔存在于t時(shí)刻的累加器中，并且可以實(shí)現(xiàn)多個(gè)文檔時(shí)間戳的批量驗(yàn)證，大大提高了時(shí)間戳系統(tǒng)的生成和驗(yàn)證效率。

6.2 成員資格撤銷(xiāo)

靜態(tài)累加器[5]可以用來(lái)解決時(shí)間戳、成員資格測(cè)試等集合成員無(wú)需變動(dòng)的問(wèn)題。然而，存在一些應(yīng)用場(chǎng)景需要對(duì)成員進(jìn)行添加或刪除操作，如匿名憑證撤銷(xiāo)系統(tǒng)、群簽名方案、身份托管方案等[43-45]會(huì)進(jìn)行撤銷(xiāo)成員的操作。傳統(tǒng)的撤銷(xiāo)方案[43]如下：一種是當(dāng)用戶嘗試訪問(wèn)資源時(shí)，驗(yàn)證方通過(guò)在數(shù)據(jù)庫(kù)中查找用戶的證書(shū)，使得證書(shū)被撤銷(xiāo)的用戶無(wú)法訪問(wèn)資源，但此查詢操作與用戶數(shù)線性相關(guān)；另一種方法是每天為所有合格用戶重新頒發(fā)新的證書(shū)，使得證書(shū)被撤銷(xiāo)的用戶無(wú)法使用舊證書(shū)訪問(wèn)資源，此方法中，合法用戶進(jìn)行證書(shū)驗(yàn)證和管理員重新頒發(fā)證書(shū)的通信成本高，與成員數(shù)線性相關(guān)。上述撤銷(xiāo)方案的困難度與合法成員數(shù)線性相關(guān)。為了解決此類(lèi)撤銷(xiāo)問(wèn)題，CAMENISCH等[6]提出了基于動(dòng)態(tài)累加器的成員撤銷(xiāo)系統(tǒng)。在該方案中，群管理員充當(dāng)累加器管理員的角色，將合法證書(shū)聚合成累加值。當(dāng)撤銷(xiāo)成員時(shí)，群管理員用累加器陷門(mén)信息更新累加值。由于動(dòng)態(tài)累加器在撤銷(xiāo)證書(shū)時(shí)，更新累加值和證據(jù)的計(jì)算量與合格成員數(shù)和撤銷(xiāo)用戶數(shù)量無(wú)關(guān)，所以大大提高了成員資格撤銷(xiāo)的效率。

6.3 無(wú)狀態(tài)區(qū)塊鏈

近年來(lái)，區(qū)塊鏈的擴(kuò)容技術(shù)[19，40，46-47]有很多，其中無(wú)狀態(tài)區(qū)塊鏈[19]是一項(xiàng)很重要的擴(kuò)容技術(shù)。如在比特幣中，當(dāng)節(jié)點(diǎn)A向B發(fā)起一筆轉(zhuǎn)賬時(shí)，除了需要通過(guò)簽名來(lái)驗(yàn)證這筆交易是否是A發(fā)起的，還要驗(yàn)證A是否有這筆錢(qián)。在傳統(tǒng)驗(yàn)證方法中，驗(yàn)證節(jié)點(diǎn)維護(hù)網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)的未花費(fèi)交易集合UTXO[19]，驗(yàn)證節(jié)點(diǎn)通過(guò)查看節(jié)點(diǎn)A發(fā)起的交易是否在UTXO集合中來(lái)判斷A是否發(fā)起了合法的轉(zhuǎn)賬。然而，隨著參與比特幣交易的用戶越來(lái)越多，UTXO集合越來(lái)越大，驗(yàn)證節(jié)點(diǎn)的存儲(chǔ)壓力也越來(lái)越大。除了比特幣等基于UTXO模型的區(qū)塊鏈面臨這樣的問(wèn)題，基于賬戶的模型，如以太坊也面臨著同樣的問(wèn)題。為了解決此類(lèi)問(wèn)題，BONEH等[19]提出了基于支持批處理累加器的無(wú)狀態(tài)區(qū)塊鏈。在該無(wú)狀態(tài)區(qū)塊鏈的構(gòu)造中，驗(yàn)證節(jié)點(diǎn)無(wú)需存儲(chǔ)整個(gè)UTXO集合，只需存儲(chǔ)該UTXO集合中元素的累加值，用戶節(jié)點(diǎn)存儲(chǔ)與自己相關(guān)的UTXO及證據(jù)。當(dāng)進(jìn)行一筆交易時(shí)，交易發(fā)起者會(huì)提供附帶證據(jù)的交易給驗(yàn)證節(jié)點(diǎn)，驗(yàn)證節(jié)點(diǎn)通過(guò)判斷交易和證據(jù)是否通過(guò)驗(yàn)證來(lái)確定這筆交易是否合法。此外，批處理累加器可以對(duì)交易進(jìn)行高效批量驗(yàn)證，不僅減輕了全節(jié)點(diǎn)的存儲(chǔ)壓力，而且進(jìn)一步提高了驗(yàn)證效率。在此之后，也產(chǎn)生了很多區(qū)塊鏈擴(kuò)容技術(shù)[19，40，46，47]。

7 總結(jié)和展望

筆者主要圍繞密碼累加器的相關(guān)研究?jī)?nèi)容展開(kāi)綜述，并按實(shí)現(xiàn)方式、功能對(duì)累加器進(jìn)行了分類(lèi)，詳細(xì)描述了基于RSA的累加器、基于雙線性映射的累加器和基于Merkle哈希樹(shù)的累加器的經(jīng)典構(gòu)造。經(jīng)過(guò)分析，現(xiàn)有的累加器方案仍然存在一些不足，未來(lái)的研究方向可以關(guān)注以下幾點(diǎn)：

(1)基于雙線性對(duì)的累加器解決了累加元素必須為素?cái)?shù)的不足，然而，該類(lèi)累加器的公開(kāi)參數(shù)的大小與集合的大小相同，增加了通信代價(jià)。此外，累加器的大小需提前設(shè)置，即累加器包含的元素個(gè)數(shù)固定。在動(dòng)態(tài)應(yīng)用場(chǎng)景中，元素的個(gè)數(shù)不斷增加，若參數(shù)設(shè)置過(guò)大，則增加公開(kāi)參數(shù)的傳輸開(kāi)銷(xiāo)；若參數(shù)設(shè)置過(guò)小，則應(yīng)用場(chǎng)景受限。因此，如何突破雙線性映射累加器的大小限制成為未來(lái)研究的方向之一。

(2)在可驗(yàn)證外包數(shù)據(jù)存儲(chǔ)中，使用數(shù)字簽名、布隆過(guò)濾器、Merkle哈希樹(shù)等驗(yàn)證數(shù)據(jù)結(jié)構(gòu)驗(yàn)證外包數(shù)據(jù)的完整性，具有證據(jù)生成和驗(yàn)證效率高等優(yōu)點(diǎn)。然而，該類(lèi)數(shù)據(jù)驗(yàn)證結(jié)構(gòu)為私有驗(yàn)證，即只有擁有私鑰的用戶才能驗(yàn)證結(jié)構(gòu)，使得使用場(chǎng)景受限。向量承諾、密碼累加器可以實(shí)現(xiàn)公開(kāi)驗(yàn)證，然而，構(gòu)造和驗(yàn)證效率低下。因此，如何構(gòu)造高效的密碼累加器，應(yīng)用于動(dòng)態(tài)密文檢索、無(wú)狀態(tài)區(qū)塊鏈、分布式存儲(chǔ)系統(tǒng)是未來(lái)研究的方向之一。