基于格的高效通用累加器與被累加值的零知識證明

譚子欣,鄧 燚 ,馬 麗

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

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

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

1 引言

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

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

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

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

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

1.1 本文貢獻(xiàn)

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

圖1 當(dāng)q=1024,Ring-SIS哈希函數(shù)與SIS的哈希函數(shù)運行時間對比圖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通用累加器單次更新運行時間對比圖Figure 2 The comparison of single update time between the Ring-SIS accumulator and the SIS accumulator when q=64,N=171

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

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

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

2 預(yù)備知識

2.1 符號定義

全文所需要用到的符號定義如表1所示。

表1 現(xiàn)有工作對比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。給定多項式向量,對于任意概率多項式時間(PPT)算法求取一個非零短向量||e||p≤β是困難的。

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

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

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

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

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

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

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

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

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

易于計算: 對于任意x?,H(x)能在多項式時間內(nèi)計算完成;

壓縮性:m﹤n;

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

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

2.2.3 通用累加器

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

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

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

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

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

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

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

2.2.4 知識的零知識證明

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

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

其中errorc為完整性錯誤。

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

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

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

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

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

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

定理1[18,23]對于任意

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

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

算法A:

算法F:

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

2.2.6 挑戰(zhàn)值空間

挑戰(zhàn)值空間是指驗證者在收到來自證明者的第一輪消息后,選擇挑戰(zhàn)值的值域空間,通常挑戰(zhàn)值空間的尺寸需要足夠大,才能為了保證零知識證明協(xié)議較低的合理性錯誤,所以本文選擇挑戰(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) 多項式xN+1可以分解為d個不可約多項式:

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

2.2.7 承諾方案

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

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

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

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

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

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

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

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

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

是否成立;

是否成立。

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

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

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

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

圖3 Ring-SIS通用累加器設(shè)計圖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,… ,以多項式環(huán)向量作為輸入,哈希函數(shù)Ha定義為

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

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

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

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

3.2 通用累加器

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

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

其中

另外,對于 F irstj與Lastj的定義將在隨后的啟動算法中給出。

啟動算法(Setup):

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

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

累加器生成算法(Acc):

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

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

3) 對于所有子集Si,?i?[p],加入輔助元素,各自計算新的子集通過算法對新子集計算子樹 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中找到元素δ對應(yīng)的葉子節(jié)點,則關(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對應(yīng)的葉子節(jié)點,即元素δ?S的證據(jù)可以表示成如下形式:

其中

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

驗證算法(Ver):

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

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

若

同時滿足,則輸出1。

累加器更新算法(AccUpdate):

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

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

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

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

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

3.3 安全性分析

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

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

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

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

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

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

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

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

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

和路徑:

且由于δ?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的抗碰撞性,也能找到一個PPT算法打破問題的困難性假設(shè)。

4 零知識證明

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

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

則可以從等式組

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

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

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

是否成立。

4.2 范圍證明

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

中,推導(dǎo)出

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

是否成立即可。

4.3 被累加值的零知識證明

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

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

上述等式也得能等價于如下形式:

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

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

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

協(xié)議П:

公共輸入:

輸入證據(jù):

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

生成證明:

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

定義如下參數(shù):

計算

最后證明者將消息

發(fā)送給驗證者。

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

(4) 驗證者令

并檢查下述條件:

是否都成立。

4.4 安全性分析

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

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

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

對于驗證公式:

可以推導(dǎo)出:

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

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

可以推導(dǎo)出

誠實驗證者零知識性:

模擬器Sim:

(1) 隨機選擇

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

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

(4) 隨機選擇

(5) 令

(6) 計算

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

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

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

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

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

4.5 拓展

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

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

5 總結(jié)

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