譚子欣,鄧 燚 ,馬 麗

1中國科學(xué)院信息工程研究所 信息安全國家重點(diǎn)實(shí)驗(yàn)室 北京 中國 100093

2密碼科學(xué)技術(shù)國家重點(diǎn)實(shí)驗(yàn)室 北京 中國 100878

3中國科學(xué)院大學(xué) 網(wǎng)絡(luò)空間安全學(xué)院 北京 中國101408

1 引言

在過去,當(dāng)用戶需要訪問數(shù)據(jù),通常需要向數(shù)據(jù)管理者發(fā)送訪問請(qǐng)求,然后管理者通過查表檢查該用戶是否具有訪問權(quán)限。在這樣的權(quán)限管理過程中,查表操作帶來的開銷往往會(huì)隨著列表的大小呈線性增長(zhǎng),這樣低效的管理方法顯然將無法適應(yīng)未來高速的大數(shù)據(jù)時(shí)代,為了解決這樣的問題,1994年Benaloh和de Mare[1]提出了累加器的概念。累加器是指將某個(gè)集合中的所有元素壓縮成一個(gè)較短輸出,并能夠?yàn)樗斜焕奂又瞪善鋵?duì)應(yīng)的成員關(guān)系證據(jù),通過成員關(guān)系證據(jù)可以向他人證明被累加值的成員身份,故而用戶可直接將其身份和成員關(guān)系證據(jù)發(fā)送給數(shù)據(jù)管理者,數(shù)據(jù)管理者再通過一個(gè)確定的檢驗(yàn)算法來判定該用戶的合法性,這樣的過程大大縮減了權(quán)限管理中的驗(yàn)證時(shí)間。除此之外,累加器在數(shù)字簽名、匿名憑證、范圍證明、集合成員關(guān)系證明等領(lǐng)域也有相當(dāng)多的應(yīng)用場(chǎng)景。

近二十年來,累加器的發(fā)展日新月異,功能性及安全性也在不斷的更新和完善。1997年Bari?和Pfitzmann[2]提出了無碰撞累加器的概念,并且首次給出了累加器的安全性定義。2002年Camenisch和 Lysyanskaya[3]提出了動(dòng)態(tài)累加器的概念,即累加器增刪元素的更新操作的時(shí)間復(fù)雜度獨(dú)立于集合大小。2005年 Nguyen[4]提出了基于強(qiáng)Diffie-Hellman假設(shè)的動(dòng)態(tài)累加器,2008年Damg?rd[5]和Triandopoulos又在此基礎(chǔ)上設(shè)計(jì)出了能夠支持非成員關(guān)系證明的雙線性映射累加器。2007年 Jiangtao Li等人[6]提出了通用累加器的概念,同時(shí)基于強(qiáng)RSA假設(shè)實(shí)現(xiàn)了動(dòng)態(tài)通用累加器。通用累加器既能為被累加成員生成成員關(guān)系證據(jù),又能為非被累加成員生成非成員關(guān)系證據(jù),而動(dòng)態(tài)通用累加器則在通用累加器的基礎(chǔ)上增加了動(dòng)態(tài)更新的功能。到了 2012年 Camacho等人[7]和Lipmaa[8]分別獨(dú)立研究出了能夠去除可信第三方前提假設(shè)限制的通用累加器,前者是基于哈希樹結(jié)構(gòu)的通用累加器,后者是建立在歐氏環(huán)上的通用累加器。

隨著量子計(jì)算的發(fā)展,人們開始憂心以往那些安全性基于強(qiáng) RSA假設(shè),離散對(duì)數(shù)假設(shè)等數(shù)論假設(shè)的累加器方案,未來在超高速量子計(jì)算機(jī)面前將會(huì)不堪一擊,因而開始向格領(lǐng)域探索。2016年Libert等人[9]在利用基于SIS問題困難性假設(shè)[10]的抗碰撞哈希函數(shù),構(gòu)造出了第一個(gè)抗量子攻擊的 SIS累加器,隨后 Ling等人[11]在此基礎(chǔ)上又提出了抗量子攻擊的動(dòng)態(tài)SIS累加器。2018年Libert等人[12]又設(shè)計(jì)出了基于 SIS問題困難性假設(shè)的通用累加器,同年Zuoxia Yu等人[13]設(shè)計(jì)出了首個(gè)基于SIS問題困難性假設(shè)的非成員關(guān)系累加器。

基于格上困難性假設(shè)的零知識(shí)證明系統(tǒng)通常有基于 Stern-like框架[9,11-15]和基于 Schnorr-like框架[16-20]兩種模式?；赟tern-like框架的協(xié)議結(jié)合統(tǒng)計(jì)隱藏,計(jì)算綁定的承諾方案可以實(shí)現(xiàn)具有完美完整性以及統(tǒng)計(jì)零知識(shí)性的零知識(shí)協(xié)議,但缺點(diǎn)在于其單輪協(xié)議執(zhí)行具有2/3的合理性錯(cuò)誤,為了降低合理性錯(cuò)誤,需要多次執(zhí)行協(xié)議,所以整體執(zhí)行效率低,在效率上不適用于現(xiàn)實(shí)場(chǎng)景; 而基于 Schnorr-like協(xié)議框架相對(duì)前者執(zhí)行效率較高,且合理性錯(cuò)誤較低,甚至可以實(shí)現(xiàn)單輪次執(zhí)行合理性錯(cuò)誤可忽略的零知識(shí)協(xié)議[1819],但需要拒絕樣保證協(xié)議零知識(shí)性,因此存在一定的協(xié)議終止概率,不過可以通過參數(shù)設(shè)置將該終止概率降至任意小,所以相對(duì)前者更具有現(xiàn)實(shí)應(yīng)用價(jià)值。

被累加值的零知識(shí)證明是指證明者以零知識(shí)的方式向他人證明自己知道一個(gè)累加器中的被累加值,即其所知秘密滿足通用累加器成員關(guān)系驗(yàn)證算法,屬于累加器在零知識(shí)證明領(lǐng)域上的一種應(yīng)用。在過去,基于格上困難性假設(shè)的被累加值的零知識(shí)證明[9]和非被累加值的零知識(shí)證明[16]都主要采用 Stern-like協(xié)議框架來實(shí)現(xiàn),卻無法基于Schnorr-like協(xié)議框架來實(shí)現(xiàn),主要原因在于該框架存在著知識(shí)的提取性錯(cuò)誤,即無法保證提取出的證據(jù)滿足范數(shù)限制要求或范圍限制要求。今年Bootle等人[19]解決了這一問題,并基于 Schnorr- like協(xié)議框架實(shí)現(xiàn)了短秘密滿足=m odq 的零知識(shí)證明,同時(shí)其1/n的合理性錯(cuò)誤遠(yuǎn)小于基于 Stern-like協(xié)議框架實(shí)現(xiàn)的版本。同年,Rupeng Yang等人[20]基于Schnorr-like的協(xié)議框架實(shí)現(xiàn)了合理性錯(cuò)誤1/poly的通用零知識(shí)協(xié)議框架,并且針對(duì)SIS累加器[9],提出了相應(yīng)的被累加值的零知識(shí)證明方案[20],合理性錯(cuò)誤可降低至1/poly。

1.1 本文貢獻(xiàn)

本文在 SIS通用累加器[14]的基礎(chǔ)上通過替換底層假設(shè)以及改進(jìn)通用累加器的存儲(chǔ)結(jié)構(gòu)等手段,設(shè)計(jì)并實(shí)現(xiàn)了第一個(gè)基于 Ring-SIS問題困難性假設(shè)的通用累加器,可為被累加成員生成較短成員關(guān)系證據(jù),也可為非被累加成員生成較短非成員關(guān)系證據(jù); 該通用累加器打破了原有格上通用累加器[14]和非成員關(guān)系累加器[15]只能全局更新的限制,可實(shí)現(xiàn)局部更新; 圖1展示的是本文設(shè)計(jì)的Ring-SIS哈希函數(shù)同 SIS哈希函數(shù)[15]在計(jì)算效率上的比較,當(dāng)安全參數(shù)N越大,Ring-SIS哈希函數(shù)的計(jì)算效率越高。圖2選用參數(shù)a1=64,N=171,此時(shí) Ring-SIS哈希函數(shù)在計(jì)算效率上會(huì)低于 SIS哈希函數(shù),但隨著集合大小M的增加,Ring-SIS通用累加器存儲(chǔ)結(jié)構(gòu)帶來的效率優(yōu)勢(shì)也越發(fā)明顯,所以綜合圖1和圖2可以得出結(jié)論: 隨著安全參數(shù)N的增大或者被累加集合大小M的增大,Ring-SIS通用累加器內(nèi)部計(jì)算效率以及更新效率要遠(yuǎn)優(yōu)于以往的 SIS通用累加器[15]。實(shí)驗(yàn)結(jié)果表明本文所設(shè)計(jì)的通用累加器將更加適用于更新操作頻繁且數(shù)據(jù)量更大的應(yīng)用場(chǎng)景。

圖1 當(dāng)q=1024,Ring-SIS哈希函數(shù)與SIS的哈希函數(shù)運(yùn)行時(shí)間對(duì)比圖Figure 1 The comparison of execution time between the Ring-SIS hash function and the SIS hash function when q=1024

圖2 當(dāng)q=64,N=171,Ring-SIS通用累加器與SIS通用累加器單次更新運(yùn)行時(shí)間對(duì)比圖Figure 2 The comparison of single update time between the Ring-SIS accumulator and the SIS accumulator when q=64,N=171

另外針對(duì)本文所設(shè)計(jì)的 Ring-SIS通用累加器,本文基于 Schnorr-like協(xié)議框架,并選用尺寸大于2256的挑戰(zhàn)值空間,設(shè)計(jì)出了第一個(gè)合理性錯(cuò)誤可忽略的被累加值的零知識(shí)證明協(xié)議。表1所展示的是本文所設(shè)計(jì)零知識(shí)協(xié)議同以往協(xié)議[9,20]的工作比較。

1.2 本文結(jié)構(gòu)

本文將在第 2章節(jié)給出全文所需要的準(zhǔn)備工作,其中包括符號(hào)定義,密碼學(xué)工具定義以及相關(guān)安全性定義; 第3章介紹了基于Ring-SIS問題困難性假設(shè)的通用累加器的具體設(shè)計(jì)以及通用累加器的安全性證明; 第4章詳細(xì)介紹了Ring-SIS通用累加器所相應(yīng)的被累加值的零知識(shí)證明協(xié)議,包括設(shè)計(jì)思路、具體構(gòu)造以及協(xié)議的安全性證明; 第5章對(duì)本文工作進(jìn)行了簡(jiǎn)要總結(jié)。

2 預(yù)備知識(shí)

2.1 符號(hào)定義

全文所需要用到的符號(hào)定義如表1所示。

表1 現(xiàn)有工作對(duì)比Table 1 The comparison of current schemes

2.2 工具介紹

2.2.1 格上問題與困難性假設(shè)

定義1(困難性假設(shè))[21]已知環(huán)R,整數(shù)模數(shù)q≥2,整數(shù)l≥1,β﹥0和p≥1。給定多項(xiàng)式向量,對(duì)于任意概率多項(xiàng)式時(shí)間(PPT)算法求取一個(gè)非零短向量||e||p≤β是困難的。

定義2(問題)[18]已知環(huán)R,整數(shù)模數(shù)q≥ 2 ,整數(shù)k﹥n≥ 1,β﹥0和p≥1。給定一個(gè)隨機(jī)矩陣,找到一個(gè)非零短向量y滿足

根據(jù)[18]中的定義,如果存在算法A和函數(shù)ε,對(duì)無窮多個(gè)n,使得

則稱算法A能以優(yōu)勢(shì)ε(n)解決問題。

定義3(問題)[18]已知環(huán)R,整數(shù)模數(shù)q≥ 2 ,整數(shù)k﹥n≥ 1 ,β﹥0和p≥1。區(qū)分?y的分布與上均勻隨機(jī)分布,其中,且為非零短向量。且

表2 標(biāo)記符注釋列表Table 2 Tag comment list

根據(jù)文獻(xiàn)[18]在定義,如果存在算法A和函數(shù)ε,對(duì)于無窮多個(gè)n,使得

則稱算法A能以優(yōu)勢(shì)1/poly(n)解決問題。

2.2.2 抗碰撞哈希函數(shù)

定義 4已知環(huán)R,整數(shù)模數(shù)q≥2,整數(shù)n,m≥ 0 。如果函數(shù)H:→滿足下面三條性質(zhì):

易于計(jì)算: 對(duì)于任意x?,H(x)能在多項(xiàng)式時(shí)間內(nèi)計(jì)算完成;

壓縮性:m﹤n;

抗碰撞性: 對(duì)于任意 PPT算法A,都存在一個(gè)可忽略函數(shù)ε,對(duì)所有安全參數(shù)n?N,

則稱函數(shù)H為抗碰撞哈希函數(shù)。

2.2.3 通用累加器

通用累加器主要由以下4個(gè)算法組成:

啟動(dòng)算法(Setup):輸入安全參數(shù)N,輸出一個(gè)公共參數(shù)pp;

累加器生成算法(Acc):輸入公共參數(shù)pp和集合S,輸出累加值u;

證據(jù)生成算法(Wit):輸入公共參數(shù)pp、累加值u、元素δ以及類型type。當(dāng)type=0,輸出δ?S的證據(jù)w,否則輸出δ?S的證據(jù)w;

驗(yàn)證算法(Ver):輸入公共參數(shù)pp、累加值u、元素δ、證據(jù)w以及類型type。當(dāng)type=0,驗(yàn)證w是否為δ?S的證據(jù),否則驗(yàn)證w是否為δ?S的證據(jù)。

如果通用累加器對(duì)于所有的 PPT敵手A,都存在一個(gè)可忽略函數(shù)ε,滿足:

則稱該通用累加器是安全的。

2.2.4 知識(shí)的零知識(shí)證明

定義5(知識(shí)的零知識(shí)證明系統(tǒng))對(duì)于NP關(guān)系P= { (x,w)} ? { 0,1}*× { 0,1}*,假設(shè)P為證明者,V為驗(yàn)證者,如果 P ( x,w) ,V ( x)是知識(shí)的零知識(shí)證明系統(tǒng),則滿足下面性質(zhì):

完整性:如果(x,w)?P,則

其中errorc為完整性錯(cuò)誤。

m-特殊合理性:如果存在 PPT提取器,以P*,V ( x)產(chǎn)生的 m條合法副本 ( a,e1,z1),…,(a,em,zm)作為輸入,可以輸出證據(jù)w'滿足(x,w ')?P,其中對(duì)于任意 i,j ?[m],ei≠ej。

誠實(shí)驗(yàn)證者零知識(shí)性:存在一個(gè) PPT模擬器S,使得 S(x,r)輸出副本 t r′ = ( a ′,e′ ,z′)的分布與驗(yàn)證者V誠實(shí)執(zhí)行協(xié)議 P ( x,w) ,V ( x)所輸出副本的分布是計(jì)算不可區(qū)分,其中r為誠實(shí)驗(yàn)證者使用的隨機(jī)數(shù)。

2.2.5 正態(tài)分布與拒絕抽樣

在域 RN上的,期望值為 v ?RN同時(shí)標(biāo)準(zhǔn)差為σ﹥ 0 的正態(tài)分布,其概率密度函數(shù)通常被定義為

本文所使用的是在域 Rk上,期望值為 v ?Rk,標(biāo)準(zhǔn)差為 σ ﹥ 0 的離散正態(tài)分布,其分布函數(shù)被定義為

下面是關(guān)于正態(tài)分布隨機(jī)抽樣的范數(shù)界限定理和拒絕抽樣定理。

定理1[18,23]對(duì)于任意

當(dāng)k?N足夠大時(shí),該范數(shù)界限成立的概率接近于1。

定理 2[23]集合V為 Rm中所有||?||2﹤T 的元素構(gòu)成的子集,同 時(shí)h:V→R為一種概率分布。存在常數(shù) M =O(1 ),使得算法A與算法F輸出分布的統(tǒng)計(jì)距離將小于

算法A:

算法F:

由文獻(xiàn)[23]可知,如果對(duì)于任意正整數(shù)α,令σ=α ?T ,則 M = e xp(12/α + 1 /(2α2))。算法A將會(huì)以至少的概率正常輸出,且其輸出分布與算法F輸出分布之間的統(tǒng)計(jì)距離將小于

2.2.6 挑戰(zhàn)值空間

挑戰(zhàn)值空間是指驗(yàn)證者在收到來自證明者的第一輪消息后,選擇挑戰(zhàn)值的值域空間,通常挑戰(zhàn)值空間的尺寸需要足夠大,才能為了保證零知識(shí)證明協(xié)議較低的合理性錯(cuò)誤,所以本文選擇挑戰(zhàn)集 合當(dāng)N=512,其大小滿足 | C |=﹥2256。

定理 3[18,24]當(dāng)N,d為 2的冪次,且滿足N≥d﹥ 1,模質(zhì)數(shù)滿足 q ≡ 2 d + 1 mod4d,則

(1) 多項(xiàng)式xN+1可以分解為d個(gè)不可約多項(xiàng)式:

(2) 對(duì)于所有 y ?Rq{0}且滿足或,在域Rq中可逆。

2.2.7 承諾方案

承諾方案由承諾階段Com和打開階段Open組成。在承諾階段,承諾者S和接收者R需要先執(zhí)行一個(gè)交互協(xié)議或者非交互協(xié)議,為一個(gè)具體的承諾方案生成所需參數(shù),如消息x。然后S從自身的隨機(jī)帶中是隨機(jī)挑選一個(gè)隨機(jī)數(shù)r,計(jì)算承諾值c = C om(x;r),并將c發(fā)送給接收者; 在打開階段,S將被承諾的消息x和隨機(jī)數(shù)r發(fā)送給R,R隨即通過驗(yàn)證 c = C om(x;r)來判斷x,r是否為c的被承諾值。

另外,當(dāng)算法 R*被限制為多項(xiàng)式時(shí)間算法,則上述承諾方案是計(jì)算隱藏的,當(dāng)不限制算法 R*的計(jì)算能力,則稱承諾方案是統(tǒng)計(jì)隱藏的。

另外,當(dāng)算法 S*被限制為多項(xiàng)式時(shí)間算法,則上述承諾方案是計(jì)算綁定的,當(dāng)不限制算法 S*的計(jì)算能力,則稱承諾方案是統(tǒng)計(jì)綁定的。

本文所構(gòu)造的知識(shí)的零知識(shí)證明方案,需要使用具有加法同態(tài)性質(zhì)的承諾方案,形如:

承諾方案主要用于保證協(xié)議的零知識(shí)性,故而選用文獻(xiàn)[17]中的多項(xiàng)式向量承諾方案,具體算法如下所示:

密鑰生成算法(CkeyGen):輸入安全參數(shù)(1n,1k),輸出公共參數(shù),其中

承諾算法(Com):輸入消息,選擇隨機(jī)數(shù)計(jì)算承諾值:

然后承諾者將c發(fā)送給接收者。

驗(yàn)證算法(Verify):承諾者向接收者發(fā)送接收者驗(yàn)證:

是否成立;

是否成立。

定理4[17]如果存在算法A能以優(yōu)勢(shì)ε打破承諾方案ComE的隱藏性,則存在算法 A ′在相同時(shí)間量級(jí)內(nèi)以優(yōu)勢(shì)ε解決問題。

定理5[17]如果存在算法A能以概率ε打破承諾方案ComE的綁定性,則存在算法 A ′在相同時(shí)間量級(jí)內(nèi)以優(yōu)勢(shì)ε解決問題。

3 通用累加器設(shè)計(jì)

目前已有的 SIS通用累加器[13,15,16],都是基于Merkle哈希樹的結(jié)構(gòu)實(shí)現(xiàn)的,而哈希函數(shù)作為哈希樹的主要部件,決定著累加器的安全性和計(jì)算的整體效率。另外,對(duì)于以往SIS通用累加器,都要求葉子節(jié)點(diǎn)呈升序排列,故而每當(dāng)有成員的加入或是撤銷,都需要重新排序,再計(jì)算整棵Merkle哈希樹。所以本文設(shè)計(jì)通用累加器的大致思想是通過替換哈希函數(shù)的底層假設(shè),從根本上提升內(nèi)部計(jì)算效率。同時(shí),將單棵哈希樹結(jié)構(gòu)拆分成多棵子樹結(jié)構(gòu),如圖3所示,當(dāng)通用累加器需要更新時(shí),只需對(duì)被操作元素對(duì)應(yīng)的子樹進(jìn)行重新計(jì)算,通過局部更新來實(shí)現(xiàn)通用累加器更新效率的大幅度提升。本節(jié)將主要介紹基于Ring-SIS的哈希函數(shù)以及基于Ring-SIS的通用累加器的具體構(gòu)造。

圖3 Ring-SIS通用累加器設(shè)計(jì)圖Figure 3 The design of the Ring-SIS universal accumulator

3.1 抗碰撞哈希函數(shù)

在給出高效通用累加器算法之前,本節(jié)首先將介紹保證高效通用累加器安全性的基礎(chǔ)部件:基于Ring-SIS問題困難性假設(shè)的抗碰撞哈希函數(shù)。本文所使用的哈希函數(shù)為了能與樹型累加器所需要的數(shù)據(jù)形式相結(jié)合,在一般背包函數(shù)形式的哈希函數(shù)[25-26]的基礎(chǔ)上稍作修改,具體構(gòu)造如下所定義:

定義 6(哈希函數(shù))給定模數(shù)q,整數(shù),向 量 a =(a1,… ,以多項(xiàng)式環(huán)向量作為輸入,哈希函數(shù)Ha定義為

操作 Г : = Rq→被定義為 Г (t) = ( cl,… ,c1),其中另外對(duì)于所有i?[N]與

由上面哈希函數(shù)的結(jié)構(gòu)可以推出:

定理6如果問題對(duì)于所有PPT算法是困難的,則上述給出的哈希函數(shù)Ha是抗碰撞哈希函數(shù)。證明.假設(shè)函數(shù)Ha不是抗碰撞的,則存在PPT算法A和一個(gè)多項(xiàng)式poly(?),對(duì)于無窮多個(gè)n,

即至少能以1/poly(n)的概率找到一對(duì)碰撞(e,h0)和(r,h1)滿足下面關(guān)系:

3.2 通用累加器

本文設(shè)計(jì)的高效通用累加器是以3.1小節(jié)中基于Ring-SIS問題困難性假設(shè)的哈希函數(shù)Ha為基礎(chǔ)部件,一共涉及四個(gè)基礎(chǔ)算法以及一個(gè)通用累加器更新算法。

令p=l?N- 2 ,另外要求安全參數(shù)N使得p滿足 p = 2g0,其中g(shù)0為正整數(shù)。這里定義被累加值的選擇空間為:

其中

另外,對(duì)于 F irstj與Lastj的定義將在隨后的啟動(dòng)算法中給出。

啟動(dòng)算法(Setup):

(1) 輸入安全參數(shù)N。

(3) 輸出公共參數(shù)為 p p = {a,{F irstj,L astj}j?[p]}。

累加器生成算法(Acc):

1) 輸入公共參數(shù)pp以及升序集合S?K。

2) 將集合S按照如下方法劃分為p個(gè)互不相交的升序子集,即 S = { Si}i?[p]。對(duì)于任意s=(sl,… ,s1)?Si,要 求deep(ptbl(s) ) - 2 =i,其 中deep(ptbl(s) ) ?[l ?N ]表示比特串ptbl(s) ? { 0,1}l?N中的從右至左的非零最高位。

3) 對(duì)于所有子集Si,?i?[p],加入輔助元素,各自計(jì)算新的子集通過算法對(duì)新子集計(jì)算子樹 Ti,并返回 Ti的根rooti。

證據(jù)生成算法(Wit):

2) 當(dāng)type=0且δ?S,輸出關(guān)于δ?S的證據(jù)w:

(1) 令 nd= d eep(δ),i =nd- 2 ,故 δ ? Si? S 。

(2) 在子樹 Ti中找到元素δ對(duì)應(yīng)的葉子節(jié)點(diǎn),則關(guān)于δ?S的證據(jù)可以表示成如下形式:

其中

(3) 輸出證據(jù)w。

3) 當(dāng)type=1且δ?S,輸出關(guān)于δ?S的證據(jù)w:

(1) 令 nd= d eep(δ),i =nd- 2 ,故 d ?Si。

(3) 在子樹 Ti中找到 δ0,δ1對(duì)應(yīng)的葉子節(jié)點(diǎn),即元素δ?S的證據(jù)可以表示成如下形式:

其中

(4) 輸出證據(jù)w。

驗(yàn)證算法(Ver):

1) 輸入公共參數(shù)pp,元素δ?K,證據(jù)w,累加值?u以及類型標(biāo)識(shí)type。

2) 當(dāng)type=0,檢查是否δ?S:

若

同時(shí)滿足,則輸出1。

累加器更新算法(AccUpdate):

1) 輸入公共參數(shù)pp,被操作元素δ?K以及操作標(biāo)識(shí)opt。

2) 當(dāng)opt = 0 ? δ ? S ,表示向通用累加器中添加新元素δ:

3) 當(dāng)opt= 1 ? δ ? S ,表示從通用累加器中刪除元素δ:

(1) 令 i = d eep(δ) - 2 ,將δ從升序子集Si?S中刪除,得到新的升序集 Si=Si/δ,此時(shí) ki=|Si|。

(2) 隨后按照步驟2中的(2)至(4)執(zhí)行,最終輸出最終樹T更新后的根節(jié)點(diǎn)Root。

3.3 安全性分析

定理 7如果問題對(duì)于所有 PPT算法是困難的,根據(jù) 2.2.3小節(jié)中通用累加器的安全性定義可知,3.2小節(jié)給出通用累加器ACC是安全的。

證明.假設(shè)ACC不是安全的,則存在一個(gè)PPT敵手算法B以及一個(gè)多項(xiàng)式poly(?),對(duì)于無窮多個(gè)N,使得

然后可以利用敵手算法B構(gòu)造出另一個(gè) PPT敵手算法A來打破哈希函數(shù)Ha的抗碰撞性,進(jìn)而打破格上問題的困難性假設(shè),以此證明假設(shè)的矛盾性 。

令事件A為δ?S,同時(shí)PPT算法B能偽造δ? S 的有效非成員關(guān)系證據(jù); 令事件B為δ?S,同時(shí)PPT算法B能偽造δ?S的有效成員關(guān)系證據(jù),根據(jù)假設(shè)可以得出:

令事件C為存在一個(gè)PPT算法找到哈希函數(shù)Ha的一對(duì)碰撞,那么事件C發(fā)生的概率

下面將討論: 在事件A發(fā)生的前提下,事件C發(fā)生的概率。

若δ? S ? t ype= 1 ,令 i = d eep(δ) - 2 ,則算法B偽造的證據(jù)為

子樹 Ti中葉子節(jié)點(diǎn)至最終樹T中根節(jié)點(diǎn)Root的路徑:

另外通過驗(yàn)證算法 V erpp(,δ,w,1 )可以計(jì)算出路徑:

和路徑:

且由于δ?S,所以有如下不等式關(guān)系:

下面將討論: 在事件B發(fā)生的前提下,事件C發(fā)生的概率。

若δ? S ? t ype= 0 ,令 i = d eep(δ) - 2 ,則算法B偽 造 的 證 據(jù) 為 w = ( (b1,… ,bgi+g0),(wgi+g0,… ,w1) ),然后通過累加器生成算法可以獲得樹T中的一條路徑:

綜上可以得出事件C發(fā)生的概率:

該結(jié)果與哈希函數(shù)Ha的抗碰撞性定義相矛盾。根據(jù)定理6可以得知當(dāng)存在PPT算法打破哈希函數(shù)Ha的抗碰撞性,也能找到一個(gè)PPT算法打破問題的困難性假設(shè)。

4 零知識(shí)證明

本節(jié)主要介紹Ring-SIS通用累加器相關(guān)的,被累加值的零知識(shí)證明協(xié)議П。在此之前,首先簡(jiǎn)要介紹協(xié)議中主要用到的一些技巧以及協(xié)議所證斷言的變形過程。

4.1 秘密值之間特殊關(guān)系證明

則可以從等式組

中獲得如下關(guān)于d的線性關(guān)系式:

為了證明秘密值p,t,v,f之間形如:

然后計(jì)算 c1= C om(h1)與 c2= C om(h2),并將其先發(fā)送給驗(yàn)證者。證明者在收到挑戰(zhàn)值后,再計(jì)算并回復(fù)消息 zb,zf,zt給驗(yàn)證者,最后由驗(yàn)證者驗(yàn)證:

是否成立。

4.2 范圍證明

為了證明秘密滿足一些特殊的范圍限制,通常會(huì)采用范圍限制轉(zhuǎn)換技術(shù)來實(shí)現(xiàn),范圍限制轉(zhuǎn)換技術(shù)即將秘密值滿足范圍限制這一條件轉(zhuǎn)換成秘密值滿足特定關(guān)系等式的條件。比如,為了證明秘密值,則只要證明等式是否成立即可,另外,集合{0,1}k可以看做是kR的真子集。

中,推導(dǎo)出

最終得到了一個(gè)關(guān)于d的線性關(guān)系式。

是否成立即可。

4.3 被累加值的零知識(shí)證明

本小節(jié)將詳細(xì)介紹如何使用秘密值的特殊關(guān)系證明以及范圍證明等技巧來共同實(shí)現(xiàn) Ring-SIS通用累加器所對(duì)應(yīng)的,被累加值的零知識(shí)證明系統(tǒng)。該零知識(shí)系統(tǒng)具體可以表述成如下語言:

根據(jù) 3.2小節(jié)中的成員關(guān)系驗(yàn)證算法的要求,當(dāng)hg+r= δ ,對(duì)?j?[L],有下列等式成立:

上述等式也得能等價(jià)于如下形式:

為了更加簡(jiǎn)潔地描述上述驗(yàn)證等式,我們可以定義如下參數(shù)符號(hào):

可以得到簡(jiǎn)潔版的成員關(guān)系驗(yàn)證等式:

下面將構(gòu)造被累加值的零知識(shí)證明協(xié)議П來零知識(shí)地證明秘密值滿足上述成員關(guān)系驗(yàn)證等式。

協(xié)議П:

公共輸入:

輸入證據(jù):

證明目標(biāo):存在向量滿足下述關(guān)系:

生成證明:

(1) 證明者選擇以下隨機(jī)數(shù):

定義如下參數(shù):

計(jì)算

最后證明者將消息

發(fā)送給驗(yàn)證者。

(3) 證明者檢查挑戰(zhàn)d是否有效,若有效則計(jì)算如下消息:

(4) 驗(yàn)證者令

并檢查下述條件:

是否都成立。

4.4 安全性分析

完整性:當(dāng)協(xié)議不中止,誠實(shí)證明者可以正確回復(fù)所有來自驗(yàn)證者的挑戰(zhàn)d,由定理2可知,當(dāng)σ=α?T ,可以獲得 M =exp(12/α + 1 /(2α2) ),協(xié)議中斷的概率。另外根據(jù)定理1可知因此誠實(shí)證明者使得誠實(shí)驗(yàn)證者相信的概率趨近于

3-特殊合理性:當(dāng)惡意證明者能以的概率猜中挑戰(zhàn)值,或者能以不超過τ的概率偽造承諾并通過驗(yàn)證,則合理性錯(cuò)誤 e rrors最多為。將概率τ降至,則協(xié)議的合理性錯(cuò)誤為

接下來證明提取出的秘密具有合法有效性。令

對(duì)于驗(yàn)證公式:

可以推導(dǎo)出:

由于 d '- d≠ 0 ,且根據(jù)定理 4可知,d'-d在Rq中是可逆的,所以可以得出結(jié)論:

另外根據(jù)驗(yàn)證等式:

可以推導(dǎo)出

誠實(shí)驗(yàn)證者零知識(shí)性:

模擬器Sim:

(1) 隨機(jī)選擇

(3) 以概率 Pabort= 1 - 1 /M輸出副本:

并中止程序,否則繼續(xù)步驟4;

(4) 隨機(jī)選擇

(5) 令

(6) 計(jì)算

(7) 以概率 Pabort= 1 - 1 /M 輸出副本:

下面將論證模擬器Sim輸出副本的分布與協(xié)議П輸出副本的分布不可區(qū)分。

在模擬器Sim被中止的情況下,由于承諾方案的隱藏性,所以(c1,c2)的分布與的分布不可區(qū)分; P1與都來自于相同分布; P的分布由來自于均勻隨機(jī)分布的 rt,ry,rv共同決定,所以P與P′也是不可區(qū)分的。故而在被中止情況下,副本′的分布與協(xié)議П輸出副本的分布是不可區(qū)分的。

在模擬器Sim不被中止的情況下,承諾值(c1,c2)的分布與的分布不可區(qū)分依賴于承諾方案Com的隱藏性; 由于協(xié)議П在不中止的情況下,有效副本需要滿足的條件,又因?yàn)橐虼?當(dāng)問題對(duì)于任意算法是困難的,P的分布與上均勻隨機(jī)1分布不可區(qū)分,所以的分布與′的分布也是不可區(qū)分的,具體可參考文獻(xiàn)[18]定理 6中的證明; 對(duì)于P的分布與P′的分布,由于′都是均勻隨機(jī)抽取的,所以P與P′的分布也是均勻隨機(jī)的; 對(duì)于(zp,zv,zf,zt,zy)的分布,又由于rp,rv,rf,rt,ry都分別取自均勻隨機(jī)分布,所以(zp,zv,zf,zt,zy)的分布與的 分布也是不可區(qū)分的; 最后根據(jù)定理2可知,由拒絕抽樣所得的的分布與是統(tǒng)計(jì)不可區(qū)分的。

故綜上,模擬器Sim輸出副本的分布與協(xié)議П輸出副本的分布是不可區(qū)分的。

4.5 拓展

關(guān)于基于 Ring-SIS的通用累加器所對(duì)應(yīng)的非被累加值的零知識(shí)證明系統(tǒng),具體可以表述成如下語言:

根據(jù)3.2小節(jié)中的非成員關(guān)系驗(yàn)證算法,非被累加值的零知識(shí)證明需要證明者證明非被累加值所在子樹中存在兩個(gè)相鄰葉子節(jié)點(diǎn),且非被累加值的大小在這兩個(gè)葉子節(jié)點(diǎn)取值之間,為了實(shí)現(xiàn)以上過程,不僅需要被累加值的零知識(shí)證明,還需要大整數(shù)范圍證明以及大整數(shù)加法關(guān)系證明共同實(shí)現(xiàn)。由于基于Schnorr-like框架的大整數(shù)間加法關(guān)系的零知識(shí)證明還未取得相關(guān)進(jìn)展,故暫時(shí)未能實(shí)現(xiàn)對(duì)于合理性錯(cuò)誤可忽略的非被累加值的零知識(shí)證明,我們未來也將繼續(xù)探究該問題。

5 總結(jié)

近年來,各類抗量子的密碼學(xué)工具逐漸走入人們的視野,其最大的亮點(diǎn)主要在于更強(qiáng)的安全性,但影響著其實(shí)用性的關(guān)鍵主要還是在于其效率的考量。本課題主要是從抗量子攻擊通用累加器的效率角度,以及相應(yīng)知識(shí)的零知識(shí)協(xié)議的效率角度進(jìn)行進(jìn)行研究,提出了計(jì)算效率和更新效率遠(yuǎn)優(yōu)于以往方案的 Ring-SIS通用累加器,同時(shí)還提出了單輪次執(zhí)行合理性錯(cuò)誤可忽略的,被累加值的零知識(shí)協(xié)議方案,其直接解決了以往方案需要重復(fù)執(zhí)行多次來降低合理性錯(cuò)誤的弊端,為基于格上困難性假設(shè)的通用累加器實(shí)用性相關(guān)的研究,進(jìn)行了近一步的探索。