張 凡,高 勝,2,曾志強(qiáng),劉 喆

1.興唐通信科技有限公司,北京100191

2.數(shù)據(jù)通信科學(xué)技術(shù)研究所,北京100191

3.信息保障技術(shù)重點(diǎn)實(shí)驗(yàn)室,北京100072

4.北京理工大學(xué)信息和電子學(xué)院,北京100081

1 引言

2008年,化名Satoshi Nakamoto(中本聰)的學(xué)者在網(wǎng)絡(luò)上發(fā)表了一篇題為《比特幣:一種點(diǎn)對(duì)點(diǎn)的電子現(xiàn)金系統(tǒng)》的文章,于是比特幣[1]進(jìn)入人們的視野.歷經(jīng)十余年的發(fā)展,各種數(shù)字貨幣紛紛出現(xiàn),例如門羅幣[2,3]、零幣[4]、萊特幣[5]等.比特幣具有去中心化,分布式記賬以及用戶身份匿名等優(yōu)點(diǎn).然而值得詬病的是,交易金額是明文傳輸?shù)?這嚴(yán)重限制了比特幣的廣泛應(yīng)用.隨后諸如門羅幣和零幣等數(shù)字貨幣采用各種密碼技術(shù)(比如環(huán)簽名[6]等特殊數(shù)字簽名、承諾[7]、零知識(shí)證明[8]、同態(tài)加密等)來解決交易金額的隱私保護(hù)問題.例如門羅幣采用Borromean環(huán)簽名結(jié)合 Perdersen承諾[9]來實(shí)現(xiàn)對(duì)交易金額的隱藏,零幣則采用zk-SNARK[10–12]這類零知識(shí)證明對(duì)交易身份以及交易金額進(jìn)行隱藏.

區(qū)塊鏈作為數(shù)字貨幣的支撐技術(shù),本質(zhì)上是采用鏈?zhǔn)綌?shù)據(jù)結(jié)構(gòu)來驗(yàn)證和存儲(chǔ)數(shù)據(jù)并結(jié)合分布式共識(shí)機(jī)制來生成并更新數(shù)據(jù),從而保證全網(wǎng)誠實(shí)節(jié)點(diǎn)的狀態(tài)一致性.去中心化、可驗(yàn)證以及防篡改是區(qū)塊鏈技術(shù)的基本屬性.隨著對(duì)區(qū)塊鏈技術(shù)的深入研究以及其可能的應(yīng)用場景的探討,敏感數(shù)據(jù)的隱私保護(hù)問題顯得尤為重要.在區(qū)塊鏈系統(tǒng)[13]中,隱私保護(hù)主要體現(xiàn)在兩個(gè)方面:匿名性和秘密性.其中匿名性是指交易發(fā)起者和交易接收者的身份隱藏,而秘密性是指交易金額的隱藏.目前比特幣系統(tǒng)只提供弱匿名性,即交易發(fā)起者和交易接收者的真實(shí)身份與其對(duì)應(yīng)的公鑰沒有關(guān)系.門羅幣和零幣雖然能解決隱私保護(hù)問題,但門羅幣中證據(jù)的長度較大,而零幣需要可信任第三方的參與并且證據(jù)生成時(shí)間很長.因而給出一個(gè)高效簡潔的隱私保護(hù)方案是一個(gè)非常有挑戰(zhàn)的問題.

為了保障交易的秘密性,Maxwell等人提出秘密交易 (CT)[14]概念,即交易發(fā)起者對(duì)交易金額做承諾,然后給出相應(yīng)的證據(jù)證明該金額在某個(gè)公開的范圍內(nèi).Maxwell等人利用Borromean環(huán)簽名給出一個(gè)具體的范圍證明方案,該方案無需可信第三方的參與,然而證據(jù)長度比較龐大并且證據(jù)生成和證據(jù)驗(yàn)證的時(shí)間復(fù)雜度也不小(均與金額的比特?cái)?shù)線性相關(guān)),因此該方案在實(shí)際應(yīng)用中很受限.Jan Camenisch等人于 2008年提出基于 Boneh-Boyen簽名[15]的交互式范圍證明方案[16],該方案后來被 Shunli Ma等人[17]借鑒用來保護(hù)交易金額的隱私性,由于該方案利用雙線性對(duì)并且需要可信第三方的參與,雖然證據(jù)長度很短,但驗(yàn)證時(shí)間比較長.2017年,Benedikt Bunz等人[18]提出新的范圍證明方案,該方案借鑒Jonathan Bootle[19]等人提出的基于多項(xiàng)式承諾的零知識(shí)證明方案,并利用向量內(nèi)積承諾方案將證據(jù)長度減為對(duì)數(shù)級(jí)別.該方案不僅不需要可信第三方的參與,而且將證據(jù)長度大大降低并且減少證據(jù)驗(yàn)證的時(shí)間復(fù)雜度,這使得該方案能很好地應(yīng)用在區(qū)塊鏈系統(tǒng)中.本文在 Benedikt Bunz等人工作的基礎(chǔ)上提出了一個(gè)新的范圍證明方案,該方案將金額按兩比特劃分并構(gòu)造新的可滿足性電路,然后借鑒 Jonathan Bootle等人的零知識(shí)證明方案和向量內(nèi)積承諾,將證據(jù)的生成時(shí)間和證據(jù)的驗(yàn)證時(shí)間大幅減少.結(jié)合Jonathan Bootle等人的零知識(shí)證明方案以及向量內(nèi)積承諾的安全性證明,很容易給出本文提出的范圍證明方案的安全性證明.當(dāng)公開區(qū)間為[0,264)時(shí),本文方案不僅將證據(jù)生成時(shí)間減少近一半,而且將證據(jù)驗(yàn)證時(shí)間減少約 33%.為了對(duì)這些范圍證明方案有一個(gè)直觀的認(rèn)識(shí),表1給出這四個(gè)方案的性能比較,其中ct表示橢圓曲線中標(biāo)量點(diǎn)乘的時(shí)間復(fù)雜度,cs表示橢圓曲線中點(diǎn)的長度.容易看出本文的范圍證明方案更適合應(yīng)用在區(qū)塊鏈系統(tǒng)中來保護(hù)交易金額的隱私.

本文的結(jié)構(gòu)如下:首先第2節(jié)介紹符號(hào)定義、Pedersen承諾以及多項(xiàng)式承諾的基本概念.接下來第3節(jié)介紹Jonathan Bootle等人提出的對(duì)任意函數(shù)的零知識(shí)證明方案.第4節(jié)給出本文的范圍證明方案.最后第5節(jié)對(duì)本文做出一個(gè)總結(jié).

表1 n=64,m=8具體方案性能比較Table 1 Performance comparison among specific schemes with n=64,m=8

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

本節(jié)首先介紹一些符號(hào)定義,然后介紹Pedersen承諾、多項(xiàng)式承諾以及向量內(nèi)積承諾等基礎(chǔ)知識(shí).

2.1 符號(hào)定義

下面介紹本文將要使用的符號(hào)定義.

G 滿足離散對(duì)數(shù)困難問題的乘法交換群

g群G的生成元

q群G的階,為大素?cái)?shù)

Zq模q的整數(shù)環(huán)

H抵抗碰撞的哈希函數(shù)

?向量的Hadmard積

·向量的內(nèi)積

⊕異或運(yùn)算

ct G上隨機(jī)元素指數(shù)運(yùn)算的計(jì)算復(fù)雜度

ce G上雙線性對(duì)運(yùn)算的計(jì)算復(fù)雜度

cs G上元素的長度

本文規(guī)定加粗的字符表示向量,未加粗的字符表示集合中的元素.并且規(guī)定這里g=(g1,g2,···,gn)∈Gn,a=(a1,a2,···,an)∈. 規(guī)定兩個(gè)向量多項(xiàng)式a(X),b(X)∈[X]的乘積運(yùn)算c(X)=a(X)·b(X)為多項(xiàng)式乘法并且系數(shù)之間的乘法定義為內(nèi)積,此時(shí)c(X)∈Zq[X].

2.2 Pedersen承諾

Pedersen承諾[9]是由雙方參與的協(xié)議.定義公開參數(shù)ck={G,q,g,h},這里g是G的生成元,h∈G且其離散對(duì)數(shù)未知.

定義 1(Pedersen承諾)Comck(a;r):=grha為對(duì)a的Pedersen承諾,這里r是隨機(jī)數(shù)且不公開.

而多元 Pedersen承諾類似于 Pedersen承諾,即給定公開的參數(shù) ck=(G,q,g,h1,···,hn),這里g是 G 的生成元,(h1,···,hn)∈Gn,這些點(diǎn)的離散對(duì)數(shù)均未知.給定消息 (m1,···,mn)∈,則對(duì)應(yīng)的Pedersen承諾為

Pedersen承諾滿足隱藏性(Hiding)和綁定性(Binding):

隱藏性:承諾值和隨機(jī)數(shù)在計(jì)算上不可區(qū)分.由于r是隨機(jī)數(shù),C0=grha0和C1=grha1在計(jì)算上是不可區(qū)分的,進(jìn)而隱藏承諾內(nèi)容.

綁定性:在承諾做出之后,承諾內(nèi)容不可抵賴.假設(shè)存在r′和a′?=a使得grha=C=gr′ha′,則有h=g(r?r′)(a′?a)?1,這說明h的離散對(duì)數(shù)已經(jīng)被求出,而這與離散對(duì)數(shù)的困難性假設(shè)矛盾,因此綁定性滿足.

2.3 多項(xiàng)式承諾

假設(shè)證明者擁有多項(xiàng)式t(X)=t0+t1X+t2X2+···+td?1Xd?1,則該多項(xiàng)式承諾是一個(gè)三段式協(xié)議,具體流程如下:

(1)證明者計(jì)算pc←PolyCommit(t(X)),即對(duì)t(X)的每個(gè)系數(shù)做承諾,

這里ck={G,q,g,h},然后將pc發(fā)送給驗(yàn)證者.

(2)驗(yàn)證者隨機(jī)選擇x∈,并將其發(fā)送給證明者.

(3)證明者計(jì)算 pe←PolyEval(x,t(X)),這里 pe=(v,ρ),其中v=t(x),ρ=;并將 pe發(fā)送給驗(yàn)證者.

(4)驗(yàn)證者計(jì)算v←PolyVerify(pc,pe,x),這里

利用Fiat-Shamir方法,該承諾方案變?yōu)榉墙换ナ匠兄Z方案,此時(shí)x=H(pe,ck).于是證明者公開承諾值(pe,v,ρ),驗(yàn)證者則計(jì)算x并調(diào)用PolyVerify(pc,pe,x)驗(yàn)證該承諾是否合法.

注意到承諾的長度會(huì)隨多項(xiàng)式的次數(shù)d增加而線性增加.為了降低承諾的長度,文獻(xiàn) [19]將多項(xiàng)式的系數(shù)分段并構(gòu)造矩陣,然后對(duì)矩陣的每一行做多元 Pedersen承諾并構(gòu)造新的多項(xiàng)式承諾方案,此時(shí)承諾長度為

2.4 向量內(nèi)積承諾

向量內(nèi)積承諾是指證明者擁有兩個(gè)秘密向量a,b∈,公開c=a·b以及A=ga和B=hb,證明者向驗(yàn)證者證明A和B所蘊(yùn)含的向量a和b之內(nèi)積確實(shí)為c.

下面介紹文獻(xiàn)[19]提出的向量內(nèi)積承諾方案,不妨將該方案記做(G,g,h,A,B,c,n;a,b),這里g和h中每個(gè)元素的離散對(duì)數(shù)互不知曉且n為二的冪次方.

首先將n維向量切成2個(gè)塊,每個(gè)塊是n/2維的向量,記

這里g1,g2,h1,h2∈Gn/2,a1,a2,b1,b2∈,則

如果令A(yù)′=(g′)a′,B′=(h′)b′,則原向量內(nèi)積承諾轉(zhuǎn)化為對(duì)新向量a′和b′的內(nèi)積承諾.注意到驗(yàn)證者需要計(jì)算g′,h′,A′,B′以及c′,證明者需要傳輸Ak,Bk和ck,這里k∈{?1,1}.

下面描述該向量內(nèi)積承諾方案(G,g,h,A,B,c,n;a,b)的具體過程,這里只有a和b是秘密.在下面的過程描述中,P是指證明者,而V是指驗(yàn)證者.

公開輸入:g,h∈Gn,A,B∈G,c∈,并且假設(shè)n為二的冪次方.

秘密輸入:證明者擁有(a,b)且滿足A=ga,B=hb以及c=a·b.

協(xié)議過程:(1)當(dāng)(n>1)時(shí),執(zhí)行遞歸約減步驟:

?P→V:發(fā)送A?1,B?1,c?1,A1,B1,c1共 6個(gè)元素 (注意到A0=A,B0=B和c0=c,這三元組不用發(fā)送);

?P←V:發(fā)送隨機(jī)數(shù)x∈;

?P→V:P和V分別將原始知識(shí)證明問題轉(zhuǎn)化為如下知識(shí)證明問題

這里

此外,P還需更新自己的秘密輸入,即a′=a1x+a2x2和b′=b1x?1+b2x?2.

然后P和V循環(huán)執(zhí)行該遞歸約減步驟.

(2)當(dāng)(n=1)時(shí),執(zhí)行終止步驟:

?P→V:P直接發(fā)送(a,b);

?P←V:如果A=ga,B=hb以及c=ab成立,則返回接受,否則拒絕.

上述方案中證明者需要向驗(yàn)證者發(fā)送Ai,Bi以及ci,所需的通信帶寬較大.為了降低通信復(fù)雜度,文獻(xiàn)[18]考慮P=gahb,這里c=a·b,gt的離散對(duì)數(shù)未知.此時(shí)在遞歸約減的步驟中Ai,Bi和ci可以合并發(fā)送.不妨將該承諾方案記做(G,gt,g,h,P,n;a,b),下面是其具體過程.

公開輸入:g,h∈Gn,gt,P∈G,這里n是二的冪次方.

秘密輸入:證明者擁有a=(a1,a2),b=(b1,b2)并滿足,這里

g=(g1,g2),h=(h1,h2),c=a1·b1+a2·b2

協(xié)議過程:如果n=1,則

?P→V:直接發(fā)送(a,b)

?P←V:如果P=gahb,這里c=ab,則返回接受;否則拒絕.

遞歸約減:如果n>1,則證明者令n′=n/2,然后計(jì)算

?P→V:發(fā)送 (L,R),這里cR=a2·b1∈Zq.

?P←V:發(fā)送隨機(jī)數(shù)x∈

?證明者和驗(yàn)證者將原問題轉(zhuǎn)化為如下新問題

(G,gt,g′,h′,P′,n′;a′,b′)

這里

而且證明者還需計(jì)算

綜上,第一個(gè)向量內(nèi)積承諾方案的通信復(fù)雜度為6logn+2,而第二個(gè)向量內(nèi)積承諾方案的通信復(fù)雜度為2logn+2,而且第二個(gè)方案的計(jì)算復(fù)雜度比第一個(gè)方案小.引理1給出這兩個(gè)內(nèi)積承諾方案的安全性.

引理 1上述向量內(nèi)積承諾方案具有完美完全性 (perfect completeness)和統(tǒng)計(jì)的見證擴(kuò)展仿真性(statistical witness-extended-emulation),即提取出非平凡的離散對(duì)數(shù)或者提出有效的見證(witness).

證明請(qǐng)參考文獻(xiàn)[18].

3 算術(shù)電路的無中心零知識(shí)證明方案

零知識(shí)證明由 Goldwasser等人[21]于上世紀(jì) 80年代提出.它是一種密碼學(xué)技術(shù),通過交互,證明者向驗(yàn)證者證明某個(gè)提議是正確的并且無需泄露除了它是正確之外的任何信息.后來,Goldreich等人[22]證明任何 NP問題都有零知識(shí)證明系統(tǒng).至此人們提出許多零知識(shí)證明方案,其中最為著名的是 Fiat-Shamir零知識(shí)身份認(rèn)證協(xié)議[23–25],其安全性建立在大整數(shù)分解問題的困難性,然而其通信和計(jì)算復(fù)雜度太大,因而實(shí)用性不強(qiáng).2013年,Parno等人提出匹諾曹協(xié)議[10],該協(xié)議是一個(gè)簡潔非交互式零知識(shí)證明協(xié)議(zk-SNARK),并且用于對(duì)任意布爾 (或算術(shù))電路的可信計(jì)算.該協(xié)議最大的優(yōu)勢是無論可滿足性電路有多復(fù)雜,其證據(jù)的長度固定為 288字節(jié).2016年,Bootle等人[19]提出另外一種零知識(shí)證明協(xié)議,該協(xié)議同樣用于對(duì)任意布爾電路的可信計(jì)算.與匹諾曹協(xié)議不同的是,該協(xié)議不僅無需可信第三方以及復(fù)雜的預(yù)計(jì)算過程,而且其安全性只依賴于離散對(duì)數(shù)的困難性.2017年,Bootle等人[26]提出可以批處理的零知識(shí)證明,該方法將多個(gè)秘密滿足的簡單電路轉(zhuǎn)化為低次數(shù)的多項(xiàng)式,進(jìn)而利用多項(xiàng)式承諾給出高效的證明.2018年,Wahby等人[27]提出新的zk-SNARK協(xié)議Hyrax,該協(xié)議結(jié)合Pedersen承諾、求和驗(yàn)證協(xié)議等密碼學(xué)工具對(duì)任意電路實(shí)現(xiàn)可信計(jì)算,并且無需可信第三方以及安全性假設(shè)只依賴于離散對(duì)數(shù)問題.除此之外,Huige WANG等人[28,29]借鑒這類對(duì)可滿足性電路的零知識(shí)證明方法并應(yīng)用在功能加密和訪問控制加密中.

本節(jié)介紹Bootle等人的零知識(shí)證明方案,其中3.1節(jié)介紹算術(shù)電路轉(zhuǎn)化為代數(shù)表達(dá)式的過程,第3.2介紹代數(shù)表達(dá)式轉(zhuǎn)化為向量多項(xiàng)式的過程,接下來3.3節(jié)介紹基于多項(xiàng)式承諾的零知識(shí)證明方案,最后3.4節(jié)給出該零知識(shí)證明方案的具體過程.

3.1 算術(shù)電路的代數(shù)表達(dá)式刻畫

本節(jié)介紹將任意給定算術(shù)電路轉(zhuǎn)化為代數(shù)表達(dá)式的過程.

如圖1所示,首先對(duì)每個(gè)乘法門分配相應(yīng)的(ai,bi,ci),其對(duì)應(yīng)的代數(shù)表達(dá)式為aibi=ci;其次對(duì)于常數(shù)乘法門以及異或門,利用相關(guān)輸入輸出的仿射表達(dá)式刻畫,例如圖1中右側(cè)的線性表達(dá)式給出了常數(shù)乘法門和異或門的代數(shù)刻畫.

圖1 算術(shù)電路的代數(shù)表達(dá)式刻畫Figure 1 Algebraic expression of arithmetic circuity

假設(shè)該電路圖的乘法門個(gè)數(shù)N=m?n,(ai,bi,ci)則用三個(gè)m?n的矩陣 (A,B,C)表示,定義A?B=C,這里A,B和C的每一行表示為

且滿足ai?bi=ci,其中i∈{1,···,m}.每個(gè)仿射表達(dá)式的刻畫表示如下

這里wq,a,i,wq,b,i,wq,c,i和Kq是只與電路有關(guān)的常數(shù),Q是仿射表達(dá)式的個(gè)數(shù).

3.2 算術(shù)電路的多項(xiàng)式轉(zhuǎn)化

本節(jié)介紹將代數(shù)表達(dá)式轉(zhuǎn)化為單變元多項(xiàng)式的過程.設(shè)Y是自變量,定義Y′=(Ym,Y2m,···,Ynm)和Y=(Y,Y2,···,Ym),則Y(A?B)Y′T=YCY′T,展開得

即Yi+jm對(duì)應(yīng)的系數(shù)滿足ai,jbi,j=ci,j.令M=N+m,對(duì)于Q個(gè)仿射表達(dá)式,則有

將上面的兩個(gè)表達(dá)式聯(lián)立,有

定義

于是電路是可滿足的當(dāng)且僅當(dāng)

設(shè)驗(yàn)證者發(fā)送隨機(jī)數(shù)y∈,此時(shí)證明者需要證明

這里y′=(ym,y2m,···,ynm).

3.3 基于多項(xiàng)式承諾的零知識(shí)證明

根據(jù)算術(shù)電路的代數(shù)表達(dá)式刻畫,證明者構(gòu)造如下洛朗多項(xiàng)式:

這里d為盲化向量.容易驗(yàn)證t(X)的常數(shù)項(xiàng)為零.

一種非常直接的思路是,證明者首先將ai,bi,ci和d的承諾發(fā)送給驗(yàn)證者,隨后驗(yàn)證者隨機(jī)選取y∈并將其發(fā)送給證明者,接下來證明者利用PolyCommit將t(X)的承諾pc發(fā)送給驗(yàn)證者,驗(yàn)證者隨后隨機(jī)選取x∈并將其發(fā)送給證明者,然后證明者將r(x)以及由PolyEval產(chǎn)生的pe一并發(fā)送給驗(yàn)證者,此時(shí)驗(yàn)證者首先根據(jù)ai,bi,ci和d的承諾驗(yàn)證r(x)的正確性,然后計(jì)算s(x)和K(y)以及r′(x),接著驗(yàn)證者根據(jù)(pc,pe)驗(yàn)證承諾的正確性并計(jì)算t(X)在x處的取值,最后驗(yàn)證者判斷t(x)r(x)·r′(x)?2K(y)是否成立即確定該證據(jù)是否為對(duì)應(yīng)電路的合法零知識(shí)證明.

文獻(xiàn)[18]的作者利用向量內(nèi)積承諾給出更高效的證明方案.注意到

這里Ai,Bi,Ci和D分別是ai,bi,ci和d的承諾,即

Ai=Comck(ai,αi),Bi=Comck(bi,βi),Ci=Comck(ci,γi),D=Comck(d,δ)

其中 ck={G,q,g,g=(g1,g2,···,gn)}. 如果令,則gr=hr?y′并且hr′=grh2s.設(shè)v=t(x),則r·r′=v+2K(y).此時(shí)該零知識(shí)證明方案轉(zhuǎn)化為如下向量內(nèi)積承諾方案

(G,g,h,R,R′,v+2K(y),n;r,r′)

這里R=gr,R′=R?h2s=hr′,此時(shí)證明者的秘密輸入是r和r′,而驗(yàn)證者通過多項(xiàng)式承諾方案得到v的取值.

3.4 零知識(shí)證明方案的具體描述

本小節(jié)介紹零知識(shí)證明方案的詳細(xì)過程,其中P是指證明者,V是指驗(yàn)證者.

公開輸入:(ck,C,N,m,n),這里ck=(G,q,g,g),g=(g1,g2,···,gn)∈Gn和函數(shù)f的布爾電路C.

證明階段:

如果n=1,將 (pe,r,ρ)發(fā)送給 V;

否則計(jì)算r′=r?y′+2s(x),并將 (pe,ρ)發(fā)送給 V.

驗(yàn)證階段:首先V計(jì)算v←PolyVerify(pc,pe,x),如果v=⊥則拒絕并驗(yàn)證失敗.

?如果n=1,V根據(jù)收到的r計(jì)算r′=r?y′+2s(x)并且驗(yàn)證

?如果n>1,P和V運(yùn)行如下向量內(nèi)積承諾

(G,g,h,R,R′,v+2K,n/2;r,r′)

這里

引理2給出上述對(duì)任意可滿足性電路的基于多項(xiàng)式承諾的零知識(shí)證明方案的安全性.

引理 2上述對(duì)可滿足性電路的零知識(shí)證明方案滿足完美完全性 (perfect completeness)、完美誠實(shí)驗(yàn)證者零知識(shí)性 (perfect special honest verifier zero-knowledge)以及統(tǒng)計(jì)的見證擴(kuò)展模擬性 (statistical witness-extended emulation),即提取一個(gè)違背承諾方案綁定性的實(shí)例或者可滿足性電路中的見證(witness).

證明請(qǐng)參考文獻(xiàn)[19].

4 高效的范圍證明方案

范圍證明是零知識(shí)證明在區(qū)塊鏈系統(tǒng)中的一個(gè)重要應(yīng)用.范圍證明是指對(duì)于某個(gè)值v∈[0,2n),證明者構(gòu)造Pedersen承諾V=gwhv以及相應(yīng)的證據(jù),以證明該值v確實(shí)在范圍[0,2n)中.

文獻(xiàn)[18]將v按單比特處理,即令,則vi(vi?1)=0,根據(jù)這兩個(gè)方程構(gòu)造多項(xiàng)式,并利用多項(xiàng)式承諾構(gòu)造范圍證明.最后他們提出的改進(jìn)的向量內(nèi)積承諾將證據(jù)的長度減為O(logn).本文將v按兩比特處理并構(gòu)造新的多項(xiàng)式,然后構(gòu)造相應(yīng)的多項(xiàng)式承諾,最后結(jié)合向量內(nèi)積承諾給出高效的范圍證明方案.

4.1 新方案描述

令v=,這里k=n/2.此時(shí)vi(vi?1)(vi?2)(vi?3)=0.令

a=(v0,v1,···,vk?1),

b=a?3,c=a?b,d=c+2,

v=a·t4

這里定義

按照前面介紹的方法,我們構(gòu)造兩個(gè)洛朗多項(xiàng)式r(X)和r′(X),使得這兩個(gè)向量多項(xiàng)式的乘積多項(xiàng)式的常數(shù)項(xiàng)為零,即令

r(X)=ay?1X+bX?1+cX2+dX?2+cy?1X3+eX4

s(X)=y·y2k·(yX?1?X+ykX?2?ykX2)+t4yX?1?2y′X?3

r′(X)=r(X)?y′+s(X)

t(X)=r(X)·r′(X)?K(y)

這里y=(y,y2,···,yk)∈Zkq,y′=(y2,y4,···,y2k)∈以及K(y)=y2k·y·(3+2yk).于是t(X)的常數(shù)項(xiàng)

t0=2(a?b?c)·y′·y?1+2(c?d)·y′+y·y2k((a?b)+(c?d)·yk)+(a·t4)?K(y)

=y2k·y·(3+2yk)+v?K(y)=v

在介紹協(xié)議的執(zhí)行過程之前,令該協(xié)議的公開參數(shù) (G,q,g,h,gs,hs,gu,g,h),這里g=(g1,g2,···,gk),h=(h1,h2,···,hk),且g,h,g,h,gs,hs,gu的離散對(duì)數(shù)互不知曉.下文的過程描述中P是指證明者,V是指驗(yàn)證者.

證明過程:

?P→V: 隨機(jī)選擇α,β,γ,δ,θ∈以及盲化向量 e∈,計(jì)算

A=Comck(a;α),B=Comck(b;β),C=Comck(c;γ),

D=Comck(d;δ),E=Comck(e;θ)

這里ck={G,q,g,g},然后將A,B,C,D和E發(fā)送給驗(yàn)證者.

?P←V:發(fā)送隨機(jī)值y∈,然后 P計(jì)算s(X)和K(y)

?P→V:P計(jì)算洛朗多項(xiàng)式

r(X)=ay?1X+bX?1+cX2+dX?2+cy?1X3+eX4

s(X)=y·y2k·(yX?1?X+ykX?2?ykX2)+t4yX?1?2y′X?3

r′(X)=r(X)?y′+s(X)

t(X)=r(X)·r′(X)?K(y)

然后對(duì)t(X)的非零系數(shù)做承諾,即,這里t(X)=

i∈{?5,?4,?3,?2,?1,1,2,3,4,5,6}.P 將這 11個(gè)承諾值發(fā)送給 V.

?P←V:發(fā)送隨機(jī)值x∈,V計(jì)算

s=s(x)=y·y2k(yx?1?x+ykx?2?ykx2)+t4yx?1?2y′x?3

?P→V:P計(jì)算

r=r(x)=ay?1x+bx?1+cx2+dx?2+cy?1x3+ex4

ρ=αy?1x+βx?1+γx2+δx?2+γy?1x3+θx4

s=s(x)=y·y2k·(yx?1?x+ykx?2?ykx2)+t4yx?1?2y′x?3

以及t=t(x)=r·(r?y′+s)和τx=,這里τ0=ω,即承諾值V的隨機(jī)指數(shù).如果k=1,P將τx,ρ,r發(fā)送給 V;否則 P將τx,ρ,t發(fā)給V.

驗(yàn)證過程:首先驗(yàn)證者根據(jù)收到的τx和t驗(yàn)證是否成立,如果不成立,則驗(yàn)證失敗.其次,

?如果k=1,V根據(jù)r計(jì)算t=r·(r?y′+s)?K(y)并驗(yàn)證

Comck(r;ρ)=Ay?1xBx?1Cx2Dx?2Cy?1x3Ex4

是否成立,如果不成立,則驗(yàn)證失敗.

?如果k>1,P 和 V 均計(jì)算R=Ay?1xBx?1Cx2Dx?2Cy?1x3Ex4g?ρ=gr并計(jì)算

(G,q,gu,gv,hv,R′,k;r,r′)

本節(jié)給出的范圍證明方案是交互式方案,為了將其應(yīng)用在區(qū)塊鏈系統(tǒng)中,利用Fiat-Shamir變換很容易將其變?yōu)榉墙换ナ椒秶C明方案.

定理1本文提出的范圍證明方案具有完美完整性(perfect completeness)、完美誠實(shí)驗(yàn)證者零知識(shí)性(perfect honest verifier zero-knowledge)以及計(jì)算特殊合理性(computational special soundness).

證明:證明者和驗(yàn)證者在運(yùn)行向量內(nèi)積承諾之前,他們的交互過程與文獻(xiàn)[19]中的對(duì)可滿足性電路的零知識(shí)證明方案的過程一致.如果證明者和驗(yàn)證者不運(yùn)行向量內(nèi)積承諾,而是證明者在最后一步將t(X)的承諾以及r直接發(fā)送給驗(yàn)證者,根據(jù)引理1和多項(xiàng)式承諾的完美完整性和統(tǒng)計(jì)特殊合理性 (statistical special soundness),該修改的范圍證明方案具有完美完整性、完美誠實(shí)驗(yàn)證者零知識(shí)性以及計(jì)算特殊合理性.而本文提出的范圍證明方案是將向量內(nèi)積承諾替換這個(gè)修改范圍證明方案的最后一步,由于gu,g,h的離散對(duì)數(shù)互不知曉,根據(jù)引理2以及類似文獻(xiàn)[18]對(duì)計(jì)算特殊合理性的證明,本文提出的范圍證明方案具有完美完整性、完美誠實(shí)驗(yàn)證者零知識(shí)性以及計(jì)算特殊合理性.

4.2 新方案性能分析

本文我們只考慮將G上的指數(shù)運(yùn)算作為對(duì)范圍證明方案的計(jì)算復(fù)雜度的估計(jì),這是因?yàn)閆q上的算術(shù)運(yùn)算與G上的指數(shù)運(yùn)算相比可以忽略不計(jì).記ct為G上隨機(jī)元素的指數(shù)運(yùn)算所需的時(shí)間復(fù)雜度,指數(shù)運(yùn)算由平方和乘法運(yùn)算組成.本文假設(shè)指數(shù)運(yùn)算所需的總平方運(yùn)算和總乘法運(yùn)算耗時(shí)相當(dāng),并且假設(shè)固定元素的指數(shù)運(yùn)算所需要的時(shí)間復(fù)雜度只占隨機(jī)元素指數(shù)運(yùn)算時(shí)間復(fù)雜度的一半 (這里暫不考慮建表等優(yōu)化細(xì)節(jié)).設(shè)cs為G上元素的長度并且假設(shè)G中元素和Zq中元素的比特長度相同(如果考慮G為橢圓曲線群,利用點(diǎn)壓縮技術(shù)后,G中元素只比Zq中元素多1比特).

下面分析本文方案的計(jì)算復(fù)雜度和證據(jù)長度.在運(yùn)行內(nèi)積向量承諾(G,q,gu,gv,hv,R′,k;r,r′)之前,證明者的計(jì)算開銷主要是 (A,B,C,D,E)的計(jì)算、11個(gè)Ti的計(jì)算以及 (gv,hv,R′)的計(jì)算,其總的時(shí)間復(fù)雜度約為 (0.75n+19)ct,而驗(yàn)證者的計(jì)算開銷主要是 (τx,t)的驗(yàn)證以及 (gv,hv,R′)的計(jì)算,其總的時(shí)間復(fù)雜度約為 (0.5n+12)ct.證明者和驗(yàn)證者運(yùn)行內(nèi)積向量承諾 (G,gu,gv,hv,R′,k;r,r′)所需的時(shí)間復(fù)雜度分別為 (0.5n+6.5logn?15)ct和 (4.5logn?7)ct.綜上,證明者產(chǎn)生證據(jù)的時(shí)間復(fù)雜度為 (1.25n+6.5logn+4)ct,而驗(yàn)證者產(chǎn)生證據(jù)的時(shí)間復(fù)雜度為 (0.5n+4.5logn+5)ct,證據(jù)的長度為(19+2logn)cs.

接下來分析文獻(xiàn)[18]中方案的計(jì)算復(fù)雜度和證據(jù)長度.在運(yùn)行內(nèi)積向量承諾之前,證明者花費(fèi)的時(shí)間復(fù)雜度約為(2n+3.5)ct,而驗(yàn)證者花費(fèi)的時(shí)間復(fù)雜度約為(n+6)ct.證明者和驗(yàn)證者運(yùn)行內(nèi)積向量承諾所需的時(shí)間復(fù)雜度分別為(n+6.5logn?8.5)ct和(4.5logn?2.5)ct.因此證明者總的時(shí)間復(fù)雜度約為(3n+6.5logn?5)ct,而驗(yàn)證者總的時(shí)間復(fù)雜度約為(n+4.5logn+3.5)ct,證據(jù)的長度為(9+2logn)cs.

最后分析文獻(xiàn) [16]和文獻(xiàn) [14]方案的計(jì)算復(fù)雜度和證據(jù)長度,并在表2中給出這四個(gè)方案的證據(jù)生成時(shí)間、證據(jù)驗(yàn)證時(shí)間以及證據(jù)長度.值得一提的是,文獻(xiàn)[16]方案需要可信第三方的預(yù)計(jì)算,且預(yù)計(jì)算的時(shí)間復(fù)雜度為 (2n/m+0.5)ct,表中ce表示G上的雙線性對(duì)的時(shí)間復(fù)雜度,一般來說ce>8.5ct.本文與文獻(xiàn)[18]相比,證據(jù)生成的時(shí)間和證據(jù)驗(yàn)證的時(shí)間均大大減少.

從表中可以看出,在無中心的前提下,本文的方案是非常有優(yōu)勢的.值得一提的是,工程實(shí)現(xiàn)一般選擇G為滿足離散對(duì)數(shù)困難的素?cái)?shù)階橢圓曲線群,則文獻(xiàn)[14,18]以及本文所提出的方案具有很大的優(yōu)化空間,而文獻(xiàn) [16]方案中證據(jù)的真實(shí)生成時(shí)間不會(huì)比本文方案的證據(jù)生成時(shí)間要少.考慮到本文的方案在驗(yàn)證的時(shí)間復(fù)雜度上更有優(yōu)勢以及證據(jù)長度很小,本文的方案更適合應(yīng)用在區(qū)塊鏈系統(tǒng)中.

表2 范圍證明方案的性能比較Table 2 Performance comparison among range proof schemes

5 結(jié)論

本文研究文獻(xiàn)[18]的范圍證明方案并結(jié)合該文獻(xiàn)的零知識(shí)證明方案提出一種新的高效的范圍證明方案,新方案對(duì)金額進(jìn)行兩比特分割,然后結(jié)合向量內(nèi)積承諾構(gòu)造相應(yīng)的多項(xiàng)式承諾.與文獻(xiàn)[18]中的方案相比,當(dāng)范圍區(qū)間為[0,264)時(shí),本文的方案將證明者的計(jì)算時(shí)間減少了近一半,而將驗(yàn)證者的計(jì)算時(shí)間減少約33%.通過與文獻(xiàn)[14,16,18]的方案相比,本文的方案非常實(shí)用.