成 雯，李順東，王文麗

1.陜西師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院，西安 710119

2.陜西師范大學(xué) 數(shù)學(xué)與信息科學(xué)學(xué)院，西安 710119

1 引言

安全多方計(jì)算（secure multi-party computation，SMC）這一概念首先由Yao[1]在20 世紀(jì)80 年代以百萬(wàn)富翁問(wèn)題提出，經(jīng)過(guò)Goldreich[2-3]、Franklin[4]和Gennaro[5]等學(xué)者的發(fā)展，安全多方計(jì)算已經(jīng)成為密碼學(xué)領(lǐng)域的研究熱點(diǎn)，是信息安全保護(hù)的關(guān)鍵技術(shù)。安全多方計(jì)算是指兩方或多方在不泄露各自私有數(shù)據(jù)的基礎(chǔ)上保密地進(jìn)行合作計(jì)算，發(fā)揮數(shù)據(jù)在信息時(shí)代的經(jīng)濟(jì)[6-8]、科學(xué)計(jì)算[9-10]、社會(huì)[11-12]等方面的價(jià)值。安全多方計(jì)算協(xié)議也被廣泛地應(yīng)用于秘密共享[13-14]、電子商務(wù)[15]等方面。

區(qū)間的保密計(jì)算具有重要的理論意義，從目前的研究看，大致可以將區(qū)間的保密計(jì)算分為兩類(lèi)：

第一類(lèi)問(wèn)題是目前研究最多的，可以描述為參與計(jì)算的一方擁有區(qū)間，另一方擁有私有數(shù)據(jù)，兩方合作保密判定點(diǎn)與區(qū)間的位置關(guān)系。這類(lèi)問(wèn)題已經(jīng)有過(guò)很多成果。Nishide 等人首先在文獻(xiàn)[16]中將區(qū)間問(wèn)題作為比特分解協(xié)議的應(yīng)用，但并沒(méi)有對(duì)區(qū)間問(wèn)題進(jìn)行深入的分析。文獻(xiàn)[17]利用計(jì)算幾何定理和基本算術(shù)知識(shí)，設(shè)計(jì)了兩個(gè)高效的有理數(shù)區(qū)間保密計(jì)算協(xié)議。文獻(xiàn)[18]利用編碼原理和級(jí)聯(lián)異或，設(shè)計(jì)了整數(shù)點(diǎn)和離散的整數(shù)區(qū)間的保密判定協(xié)議；將實(shí)數(shù)轉(zhuǎn)換為整數(shù)，設(shè)計(jì)了實(shí)數(shù)點(diǎn)和連續(xù)的實(shí)數(shù)區(qū)間的保密判定協(xié)議。文獻(xiàn)[19]利用多項(xiàng)式和整數(shù)向量?jī)?nèi)積符號(hào)的判定，設(shè)計(jì)了高效的有理數(shù)保密計(jì)算協(xié)議和有理區(qū)間保密計(jì)算協(xié)議。

第二類(lèi)問(wèn)題可以描述為兩方或多方合作生成秘密區(qū)間，另一方擁有私密數(shù)據(jù)，任何人對(duì)區(qū)間信息一無(wú)所知，在此基礎(chǔ)上對(duì)秘密區(qū)間與閾值進(jìn)行保密判定。此問(wèn)題在密碼學(xué)領(lǐng)域有重要的理論意義，在保密插入、商品交易等應(yīng)用場(chǎng)景中也具有實(shí)際意義。文獻(xiàn)[20]曾將判定點(diǎn)與線段的關(guān)系轉(zhuǎn)化為判定點(diǎn)與線段兩端點(diǎn)形成的區(qū)間的關(guān)系，但該協(xié)議不能區(qū)分點(diǎn)與區(qū)間的全部位置關(guān)系以及不能抵抗合謀攻擊。而本文設(shè)計(jì)的協(xié)議不僅能區(qū)分閾值與秘密區(qū)間的全部位置關(guān)系，且均能抵抗合謀攻擊，并將秘密區(qū)間問(wèn)題由兩方合作生成擴(kuò)展到多方合作生成。

百萬(wàn)富翁問(wèn)題可以描述為：兩個(gè)百萬(wàn)富翁Alice和Bob 想知道他們誰(shuí)擁有的財(cái)富更多，但他們都不想向?qū)Ψ叫孤蹲约旱呢?cái)富。數(shù)學(xué)描述為：Alice 和Bob各自擁有數(shù)據(jù)x、y，他們想保密地判斷x、y的大小。Paillier密碼系統(tǒng)的明文空間為ZN。(ZN,+)構(gòu)成一個(gè)加法群，在這個(gè)群里是沒(méi)有正負(fù)數(shù)之分的，但如果限制實(shí)際處理的明文m都在[0,)之內(nèi)，即m∈{0,1,…,-1}，如果x+y=0 modN，而0 ＜x＜，那么一定有y＞。在這種情況下y是x的加法逆元，如果認(rèn)為x≥0，那么y就可以看作負(fù)數(shù)。進(jìn)一步假設(shè)x,y＜，如果(x-y) modN＜，則x＞y；如果(xy) modN＞，則x＜y。利用這個(gè)原理可以設(shè)計(jì)出半誠(chéng)實(shí)模型下百萬(wàn)富翁問(wèn)題的安全多方計(jì)算協(xié)議。

秘密區(qū)間與閾值的保密判定問(wèn)題直觀上的解決思路就是比較閾值與秘密區(qū)間兩個(gè)端點(diǎn)的大小關(guān)系。針對(duì)兩方合作生成秘密區(qū)間，只需將秘密區(qū)間的兩個(gè)端點(diǎn)與閾值進(jìn)行保密比較，即調(diào)用兩次百萬(wàn)富翁協(xié)議；針對(duì)多方合作生成秘密區(qū)間，通過(guò)多次調(diào)用百萬(wàn)富翁協(xié)議可以得到秘密區(qū)間的兩個(gè)端點(diǎn)，再調(diào)用兩次百萬(wàn)富翁協(xié)議來(lái)比較閾值與秘密區(qū)間端點(diǎn)的關(guān)系。但是多次調(diào)用百萬(wàn)富翁協(xié)議不僅泄露了秘密區(qū)間的端點(diǎn)值，而且增加了計(jì)算復(fù)雜性和通信復(fù)雜性。為了保護(hù)秘密區(qū)間不被泄露以及提高效率，本文利用編碼原理并結(jié)合Lifted ElGamal 同態(tài)加密算法，提出了優(yōu)化協(xié)議。

本文貢獻(xiàn)如下：

（1）提出了秘密區(qū)間與閾值的保密判定這個(gè)新的問(wèn)題，并針對(duì)該問(wèn)題的不同應(yīng)用場(chǎng)景分別給出了高效安全的解決方法。

（2）針對(duì)兩方合作生成秘密區(qū)間，基于Paillier 同態(tài)加密算法設(shè)計(jì)了一個(gè)協(xié)議，利用模擬范例證明了方案的安全性，并進(jìn)行了效率分析和實(shí)驗(yàn)驗(yàn)證。

（3）針對(duì)多方合作生成秘密區(qū)間，利用編碼原理并結(jié)合Lifted ElGamal 同態(tài)加密算法，提出了優(yōu)化協(xié)議，避免了多次調(diào)用百萬(wàn)富翁協(xié)議，保護(hù)了秘密區(qū)間信息且提高了效率。

（4）本文設(shè)計(jì)的協(xié)議不僅能區(qū)分閾值與秘密區(qū)間的全部位置關(guān)系，且均能抵抗合謀攻擊，并將秘密區(qū)間問(wèn)題由兩方合作生成擴(kuò)展到多方合作生成。

（5）對(duì)區(qū)間保密計(jì)算問(wèn)題進(jìn)行了擴(kuò)展，針對(duì)秘密區(qū)間問(wèn)題進(jìn)行研究，并給出了秘密區(qū)間與閾值保密判定的應(yīng)用實(shí)例。

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

2.1 安全性定義

半誠(chéng)實(shí)參與者：一般而言，半誠(chéng)實(shí)參與者是指參與者會(huì)嚴(yán)格地執(zhí)行協(xié)議，但可能會(huì)通過(guò)保留的中間結(jié)果試圖推出其他參與者的私有數(shù)據(jù)或其他一些信息。

假設(shè)有n個(gè)參與者分別擁有私密數(shù)據(jù)xi(i∈{1,2,…,n})，他們共同執(zhí)行協(xié)議π的計(jì)算函數(shù)f(x)：

并得到最終結(jié)果。令X=(x1,x2,…,xn)，在協(xié)議執(zhí)行過(guò)程中，將參與者得到的消息序列記為：

定義1（半誠(chéng)實(shí)協(xié)議的安全性[21]）設(shè)f=f({0,1}?)n→({0,1}?)n是概率多項(xiàng)式函數(shù)。fi(x1,x2,…,xn)是f(x1,x2,…,xn)中的第i個(gè)元素，令Pi表示第i個(gè)參與者，設(shè)I={Pi1,Pi2,…,Pis}?{P1,P2,…,Pn}是任意參與者的子集，fI(x1,x2,…,xn)代表序列fi1(x1,x2,…,xn),fi2(x1,x2,…,xn),…,fis(x1,x2,…,xn)，outputπ(x) 表 示 所 有 參 與者執(zhí)行完協(xié)議π后的結(jié)果。假設(shè)參與者都是半誠(chéng)實(shí)的，如果說(shuō)協(xié)議π保密地計(jì)算n元函數(shù)f，那么存在概率多項(xiàng)式時(shí)間算法S，使得對(duì)于任意I都有下列式子成立：

2.2 概率加密算法

一個(gè)公鑰加密方案[22]一般由KeyGen、Encrypt、Decrypt 三個(gè)算法組成。

（1）KeyGen

選取安全參數(shù)λ，輸出私鑰sk、公鑰pk、明文空間M和密文空間C，即：

（2）Encrypt

給定公鑰pk和明文m∈M，輸出相應(yīng)的密文c∈C：

（3）Decrypt

給定私鑰sk和密文c，輸出相應(yīng)的明文m：

概率加密算法在加密過(guò)程中需要選擇隨機(jī)數(shù)r∈M參與運(yùn)算，因此如果選用不同的隨機(jī)數(shù)r，對(duì)于相同的明文m也會(huì)產(chǎn)生不同的密文c。

Paillier、ElGamal 等是常用的概率加密算法，這些算法具有的同態(tài)加密性[23]可以幫助解決很多保密計(jì)算問(wèn)題。例如Paillier 加密算法具有加法同態(tài)性，具體如下：

Lifted ElGamal 加密算法是在ElGamal 加密算法上加以修改的，它具有加法同態(tài)性，具體如下：

E(m1)E(m2)=E(m1+m2)

2.3 門(mén)限密碼體制

在安全多方計(jì)算中可以用門(mén)限解密[24]來(lái)抵抗合謀攻擊。因?yàn)楸疚男枰挚筺-1 個(gè)參與者的合謀攻擊，所以需要的是(n,n)門(mén)限。公鑰由n個(gè)參與者聯(lián)合生成，而私鑰是由這些參與者分享的。用公鑰加密的消息必須由n個(gè)參與者合作才能完成解密。Paillier、ElGamal 等密碼系統(tǒng)都可以用來(lái)構(gòu)造門(mén)限密碼系統(tǒng)，下面以Lifted ElGamal 為例給出門(mén)限密碼系統(tǒng)的具體構(gòu)造：

（1）KeyGen

選取安全參數(shù)λ并產(chǎn)生素?cái)?shù)p，選擇的一個(gè)生成元g。每個(gè)參與者Pi隨機(jī)選取ki∈作為私鑰，并計(jì)算hi=modp。n個(gè)參與者計(jì)算公鑰：

（2）Encrypt

為加密明文M，選擇隨機(jī)數(shù)r，按照下式計(jì)算密文c：

（3）Decrypt

對(duì)于密文c=(c1,c2)，每個(gè)參與者Pi按照下式解密：

Lifted ElGamal門(mén)限密碼系統(tǒng)在解密過(guò)程中得到的是gM，涉及到離散對(duì)數(shù)計(jì)算，為了計(jì)算方便，一般取g=2，gM＜p。當(dāng)M的值不太大時(shí)（本文協(xié)議2 中M的取值只有0，1），很容易從2M中獲得M?？梢灶A(yù)先計(jì)算所有的結(jié)果，在解密時(shí)通過(guò)查表快速解密。

3 兩方合作生成秘密區(qū)間與閾值的保密判定

兩方合作生成秘密區(qū)間與閾值的保密判定問(wèn)題具有廣泛的應(yīng)用背景?？紤]如下場(chǎng)景：Alice 擁有數(shù)x，Bob 擁有數(shù)y，Alice 和Bob 合作構(gòu)成區(qū)間[x,y]或[y,x]，Carol 擁有數(shù)z，現(xiàn)要保密得到z的插入位置，即z在區(qū)間左側(cè)、在區(qū)間內(nèi)還是在區(qū)間右側(cè)。

問(wèn)題描述：Alice 擁有x，Bob 擁有y，Carol 擁有z(x,y,z＞0)，保密地判斷z與秘密區(qū)間I=[min{x,y},max{x,y}]的關(guān)系。

解決思路如下：直觀上考慮，要保密地判斷z與秘密區(qū)間I的關(guān)系，就是要保密比較閾值與區(qū)間端點(diǎn)的關(guān)系。因此基于以下事實(shí)設(shè)計(jì)了協(xié)議1。

事實(shí)假設(shè)Alice 擁有數(shù)據(jù)x，Bob 擁有數(shù)據(jù)y(0 ≤x,y＜)，要保密判斷x、y的大小。將x和Ny分別用Paillier 加密算法的公鑰加密得到E(x) 和E(N-y)，令C=E(x)E(N-y)，用私鑰解密C，記解密結(jié)果為w=D(C)，則有下面結(jié)論：

證明由Paillier 加密算法定義以及加法同態(tài)性，可知：

當(dāng)用私鑰解密時(shí)，解密結(jié)果為：

分析如下：為了描述方便，定義T(z,I)（以下簡(jiǎn)稱T）如下：

協(xié)議1兩方合作生成秘密區(qū)間與閾值的保密判定

準(zhǔn)備階段：選定安全參數(shù)k，參與者P3運(yùn)行Paillier 加密算法，生成公鑰pk和私鑰sk，P3向P1、P2公布生成的公鑰（以下所涉及到的隨機(jī)數(shù)均屬于

（1）P3用公鑰加密N-z得到E(N-z)并發(fā)送給P1、P2。

（2）P1選取隨機(jī)數(shù)r11，用公鑰加密x得到E(x)，計(jì)算：

并將U發(fā)送給P2。

（3）P2選取隨機(jī)數(shù)r12、r22，用公鑰加密y得到E(y)，計(jì)算：

并將V、A發(fā)送給P1。

（4）P1選取隨機(jī)數(shù)r21，計(jì)算：

并將A重隨機(jī)化后記為C，選取隨機(jī)置換φ作用于B、C，得到J、K并發(fā)送給P3。

（5）P3解密P1發(fā)來(lái)的數(shù)據(jù)得到u=D(J)，v=D(K)，按照下述情況輸出T：

注：由上述事實(shí)可知，在利用Paillier 加密算法的性質(zhì)保密比較x、y的大小時(shí)，需要限制x、y的范圍為0 ≤x,y＜。在協(xié)議1 中，為了保護(hù)數(shù)據(jù)隱私以及得到計(jì)算結(jié)果，需要計(jì)算(x+N-z)r11r12和(y+Nz)r21r22?，F(xiàn)令x′=xr11r12，z′=zr11r12和y′=yr21r22，z″=zr21r22，與事實(shí)中x、y相對(duì)應(yīng)，就需要限制0 ≤x′,z′＜和0 ≤y′,z″＜，因此協(xié)議1 中選取的數(shù)據(jù)和隨機(jī)數(shù)都屬于[0,]。

正確性分析：兩方合作生成秘密區(qū)間與閾值的判定問(wèn)題可以描述為閾值與區(qū)間端點(diǎn)比較問(wèn)題，基于事實(shí)可以正確得到秘密區(qū)間與閾值的關(guān)系。

安全性分析：

（1）考慮合謀

①P1、P2合謀想獲取P3的信息z。因?yàn)橹挥蠵3可以解密，P1、P2只能得到P3的密文E(N-z)，而加密算法是語(yǔ)義安全的，E(N-z)和某個(gè)隨機(jī)數(shù)是不能被區(qū)分開(kāi)來(lái)的，因此協(xié)議1 可以抵抗P1、P2合謀。

②P3參與合謀，此時(shí)P1、P2的地位是平等的，能力是相同的，因此只對(duì)其中一種情況證明協(xié)議1 是安全的。假設(shè)P2、P3合謀想獲取P1的值x，P2、P3能夠在協(xié)議過(guò)程中獲得密文J、K，假設(shè)：

在這兩個(gè)等式中，y、r12、r22、z是P2、P3的保密數(shù)和隨機(jī)數(shù)，x、r11、r21是3 個(gè)未知變量。P2、P3不能通過(guò)這兩個(gè)方程來(lái)確定P1的值x。因此協(xié)議1 可以抵抗P2、P3合謀。

同理可證協(xié)議1 可以抵抗P1、P3合謀。

（2）不考慮合謀

假設(shè)參與者都不合謀，對(duì)于P3來(lái)說(shuō)，存在6 個(gè)未知變量，他不能通過(guò)兩個(gè)方程來(lái)確定P1、P2的值；對(duì)于P1、P2來(lái)說(shuō)，僅知道自己的數(shù)據(jù)、T值和一些密文，得不到任何信息。

因此協(xié)議1 是安全的，并且可以抵抗合謀攻擊。

定理1協(xié)議1 在半誠(chéng)實(shí)模型下是安全的。

證明下面通過(guò)構(gòu)造滿足式（1）的模擬器S來(lái)證明定理1。

（1）假設(shè)P3參與合謀，以P2、P3合謀為例，則最大合謀者集合為I={P2,P3}。此時(shí)：

給定輸入(I,(y,z),fI(X))，S隨機(jī)選擇x′使得：

模擬器S用x′、y、z按照協(xié)議1 做如下模擬：

并將A′重隨機(jī)化后記為C′，選取隨機(jī)置換φ作用于B′、C′，得到J′、K′。

（2）P3不參與合謀，P1、P2只知道P3發(fā)布的密文E(N-z)，而加密算法是語(yǔ)義安全的，密文和某個(gè)隨機(jī)數(shù)是不可區(qū)分的，可以用類(lèi)似的模擬證明協(xié)議1的安全性。

因此，該協(xié)議對(duì)于半誠(chéng)實(shí)參與者是安全的。□

4 多方合作生成秘密區(qū)間與閾值的保密判定

考慮以下場(chǎng)景：顧客想將古董賣(mài)給古董行，有多家古董行都想購(gòu)入該古董，現(xiàn)要保密地判斷顧客估價(jià)是否符合該古董的市場(chǎng)估價(jià)范圍。每家古董行都有一個(gè)估價(jià)，市場(chǎng)估價(jià)范圍[x,y]由多家古董行的最低價(jià)x和最高價(jià)y構(gòu)成。如果估價(jià)在[x,y]內(nèi)，則顧客和古董行進(jìn)一步商量，達(dá)成交易；否則顧客可以繼續(xù)調(diào)整估價(jià)或放棄交易。因此設(shè)計(jì)這樣的協(xié)議不僅能保護(hù)用戶的私有數(shù)據(jù)，同時(shí)能節(jié)省不少時(shí)間和成本，在生活中是具有實(shí)際意義的。

問(wèn)題描述：假設(shè)參與者Pi(i∈{1,2,…,n})擁有私密數(shù)據(jù)xi，Alice 擁有數(shù)據(jù)z，保密地判斷z是否在n個(gè)參與者合作構(gòu)成的秘密區(qū)間I=[min{x1,x2,…,xn}，max{x1,x2,…,xn}]內(nèi)。

解決思路如下：n個(gè)參與者數(shù)據(jù)中的最小值和最大值分別為秘密區(qū)間I的兩個(gè)端點(diǎn)，得到I后再保密地判定閾值與秘密區(qū)間的關(guān)系?？梢越梃b文獻(xiàn)[25]中保密替換的思想，但并不需要求出最小值和最大值，而直接得到保密的區(qū)間范圍，然后根據(jù)z值取對(duì)應(yīng)列元素進(jìn)行相加即可判斷z與秘密區(qū)間I的關(guān)系。

多個(gè)數(shù)據(jù)求最小值的方法如下：

編碼方法1n個(gè)參與者各自擁有私密數(shù)據(jù)xi(1 ≤xi≤m)，將數(shù)據(jù)xi按照以下方法表示為對(duì)應(yīng)的數(shù)組Xi=(xi1,xi2,…,xim)，其中：

參與者P1按照該方法得到數(shù)組X1=(x11,x12,…,x1m)，即數(shù)組前面有x1-1 個(gè)0，后面有m-x1+1 個(gè)1。參與者Pj(j∈{2,3,…,n})用m-xj+1 個(gè)1 替換前一個(gè)參與者發(fā)來(lái)的數(shù)組的后m-xj+1 個(gè)元素，得到新的數(shù)組Xj，而其他元素保持不變。最后求得的數(shù)組Xn=(xn1,xn2,…,xnm)中0 元素的個(gè)數(shù)恰好等于最小值減1 的值。

多個(gè)數(shù)據(jù)求最大值的方法如下：

編碼方法2n個(gè)參與者各自擁有私密數(shù)據(jù)xi(1 ≤xi≤m)，將數(shù)據(jù)xi按照以下方法表示為對(duì)應(yīng)的數(shù)組Yi=(yi1,yi2,…,yim)，其中：

參與者P1按照該方法得到數(shù)組Y1=(y11,y12,…,y1m)，即數(shù)組前面有x1個(gè)0，后面接著有m-x1個(gè)1。參與者Pj(j∈{2,3,…,n})用xj個(gè)0 替換前一個(gè)參與者發(fā)來(lái)的數(shù)組的前xj個(gè)元素，得到新的數(shù)組Yj，而其他元素保持不變。最后求得的數(shù)組Yn=(yn1,yn2,…,ynm) 中0元素的個(gè)數(shù)恰好等于最大值。

例如，參與者Pi(i∈{1,2,3})分別擁有數(shù)據(jù)x1=5，x2=3，x3=9，令m=10。

P1分別利用編碼方法1、2 構(gòu)造數(shù)組如下：

由P2替換后為：

由P3替換后為：

則參與者合作構(gòu)成的秘密區(qū)間為：

Alice 擁有數(shù)據(jù)z(1 ≤z≤m)，只要將數(shù)組對(duì)應(yīng)第z列元素進(jìn)行相加記為T(mén)，即可根據(jù)下述情況判斷z與秘密區(qū)間I的關(guān)系。

（1）當(dāng)T=0 時(shí)，z在秘密區(qū)間左側(cè)；

（2）當(dāng)T=1 時(shí)，z在秘密區(qū)間內(nèi)；

（3）當(dāng)T=2 時(shí)，z在秘密區(qū)間右側(cè)。

協(xié)議2多方合作生成秘密區(qū)間與閾值的保密判定

輸入：參與者Pi(i∈{1,2,…,n})各自輸入數(shù)據(jù)xi，Alice輸入z。

輸出：T(z,I)（以下簡(jiǎn)稱T）。

準(zhǔn)備階段，運(yùn)行Lifted ElGamal 加密系統(tǒng)構(gòu)造的(n+1,n+1) 門(mén)限密碼系統(tǒng)，參與者Pi(i∈{1,2,…,n})，Alice 分別選擇私鑰ki(i∈{1,2,…,n+1})，并選擇公共參數(shù)g、p聯(lián)合生成公鑰：

（1）參與者P1分別按照編碼方法1、2 將x1表示為數(shù)組X1、Y1，并將E(X1)=(E(x11),E(x12),…,E(x1m))，E(Y1)=(E(y11),E(y12),…,E(y1m))發(fā)送給P2。

（2）令c=(c1,c2,…,cm)=(E(x11),E(x12),…,E(x1m))，d=(d1,d2,…,dm)=(E(y11),E(y12),…,E(y1m))。

（3）參與者Pj(j∈{2,3,…,n})計(jì)算如下：

①參與者Pj根據(jù)數(shù)據(jù)xj按照上述方法分別對(duì)數(shù)組c、d中的元素進(jìn)行替換。

②對(duì)數(shù)組c、d進(jìn)行重隨機(jī)化。

③更新數(shù)組c=(E(xj1),E(xj2),…,E(xjm))，d=(E(yj1),E(yj2),…,E(yjm))。

（4）參與者Pn將數(shù)組c=(E(xn1),E(xn2),…,E(xnm)),d=(E(yn1),E(yn2),…,E(ynm))發(fā)送給Alice。

（5）Alice 根據(jù)自己的數(shù)據(jù)z分別選擇數(shù)組c、d中對(duì)應(yīng)的第z列元素，計(jì)算如下：

并將U公布。

（6）n個(gè)參與者和Alice 聯(lián)合解密T=D(U)，即可以得到z與秘密區(qū)間I的關(guān)系。

正確性分析：協(xié)議2 的正確性可由門(mén)限解密的基本原理和第4 章協(xié)議的基本原理得到保證。

安全性分析：協(xié)議2 的安全性是基于門(mén)限密碼體制的安全性，因此協(xié)議過(guò)程中公布的密文，如果有任何少于n個(gè)參與者進(jìn)行解密的話都無(wú)法得到正確結(jié)果，也就是說(shuō)協(xié)議2 是可以抵抗合謀攻擊的。

定理2協(xié)議2 在半誠(chéng)實(shí)模型下是安全的。

定理2 的證明與定理1 類(lèi)似，此處省略具體證明過(guò)程。

5 效率分析

秘密區(qū)間與閾值的保密判定問(wèn)題研究成果較少，文獻(xiàn)[20]涉及3 個(gè)參與者，且秘密區(qū)間由兩方合作生成，與本文協(xié)議1 情況類(lèi)似，對(duì)協(xié)議1 與文獻(xiàn)[20]進(jìn)行效率比較。而目前沒(méi)有多方合作生成秘密區(qū)間與閾值保密判定的協(xié)議，因此協(xié)議2 沒(méi)有與其他文獻(xiàn)進(jìn)行效率比較。

5.1 計(jì)算復(fù)雜性

首先分析協(xié)議的計(jì)算復(fù)雜性。為了方便計(jì)算，在分析協(xié)議的計(jì)算復(fù)雜性時(shí)只考慮最耗時(shí)的模指數(shù)運(yùn)算。文獻(xiàn)[20]、協(xié)議1 選用的是Paillier 加密算法，加密、解密一次均需要兩次模指數(shù)運(yùn)算，計(jì)算一次密文模指數(shù)需要一次模指數(shù)運(yùn)算。協(xié)議2 選用的是Lifted ElGamal 門(mén)限密碼系統(tǒng)，加密一次需要三次模指數(shù)運(yùn)算，解密運(yùn)算的模指數(shù)運(yùn)算次數(shù)與參與解密的人數(shù)有關(guān)。

文獻(xiàn)[20]共需要18 次模指數(shù)運(yùn)算。協(xié)議1 加密、解密、密文模指數(shù)、重隨機(jī)化分別需要6 次、4 次、4次、2 次模指數(shù)運(yùn)算，共需要16 次模指數(shù)運(yùn)算。協(xié)議2 中假設(shè)所有數(shù)據(jù)不超過(guò)m，加密過(guò)程最多需要6mn次模指數(shù)運(yùn)算，解密、重隨機(jī)化過(guò)程分別需要(n+2)次、4m(n-1) 次模指數(shù)運(yùn)算，因此協(xié)議2 最多需要10mn-4m+n+2 次模指數(shù)運(yùn)算。

5.2 通信復(fù)雜性

使用通信次數(shù)來(lái)分析通信復(fù)雜性。

文獻(xiàn)[20]需要10 次通信，協(xié)議1 需要7 次通信，協(xié)議2 需要2n次通信。

文獻(xiàn)[20]、協(xié)議1、協(xié)議2 的計(jì)算復(fù)雜性和通信復(fù)雜性分析結(jié)果如表1 所示。

Table 1 Analysis results of computational complexity and communication complexity表1 計(jì)算復(fù)雜性和通信復(fù)雜性分析結(jié)果

由表1 可知，協(xié)議1 的計(jì)算復(fù)雜性和通信復(fù)雜性均低于文獻(xiàn)[20]。本文設(shè)計(jì)的協(xié)議均能抵抗合謀攻擊，且能區(qū)分閾值與區(qū)間全部的位置關(guān)系。

5.3 實(shí)驗(yàn)分析

為了進(jìn)一步驗(yàn)證協(xié)議的效率，通過(guò)模擬實(shí)驗(yàn)來(lái)測(cè)試文獻(xiàn)[20]協(xié)議和本文協(xié)議執(zhí)行所用的時(shí)間。實(shí)驗(yàn)的測(cè)試環(huán)境：Windows 10 64 位操作系統(tǒng)，處理器參數(shù)為Intel?CoreTMi5-4590S CPU@3.00 GHz，4 GB 內(nèi)存，用Java語(yǔ)言編程實(shí)現(xiàn)，都忽略了預(yù)處理時(shí)間。

文獻(xiàn)[20]、協(xié)議1 使用的是Paillier 加密算法，實(shí)驗(yàn)設(shè)定p、q的位數(shù)為512 bit，數(shù)據(jù)范圍為[0,4 000]，并隨機(jī)選取500 組數(shù)據(jù)求平均值作為實(shí)驗(yàn)結(jié)果。實(shí)驗(yàn)結(jié)果如表2 所示。由實(shí)驗(yàn)結(jié)果可知，協(xié)議1 的總運(yùn)算耗時(shí)要低于文獻(xiàn)[20]，證明協(xié)議1 是高效的。

Table 2 Comparison of experimental results between Ref.[20]and protocol 1表2 文獻(xiàn)[20]與協(xié)議1 實(shí)驗(yàn)結(jié)果比較 ms

協(xié)議2 使用的是Lifted ElGamal 門(mén)限密碼系統(tǒng)，忽略生成共享密鑰的時(shí)間。實(shí)驗(yàn)設(shè)定p的位數(shù)為512 bit，參與者人數(shù)一共為10 人，數(shù)據(jù)范圍從[0,100]到[0,1 000]，并隨機(jī)選取100 組數(shù)據(jù)求平均值作為實(shí)驗(yàn)結(jié)果。實(shí)驗(yàn)結(jié)果如圖1 所示。

由圖1 可知，數(shù)據(jù)范圍不斷增大，協(xié)議2 的執(zhí)行時(shí)間也不斷增加，執(zhí)行時(shí)間隨數(shù)據(jù)范圍增長(zhǎng)基本呈線性增加。

Fig.1 Relationship between execution time and data range in protocol 2圖1 協(xié)議2 執(zhí)行時(shí)間與數(shù)據(jù)范圍的關(guān)系

6 結(jié)束語(yǔ)

本文提出了秘密區(qū)間與閾值保密判定問(wèn)題，針對(duì)不同的應(yīng)用場(chǎng)景，設(shè)計(jì)了兩個(gè)秘密區(qū)間與閾值保密判定的協(xié)議，并證明了協(xié)議均能抵抗合謀攻擊。文中還給出了一些秘密區(qū)間與閾值保密判定的實(shí)際應(yīng)用場(chǎng)景，今后將在現(xiàn)有研究的基礎(chǔ)上進(jìn)一步研究高效的秘密區(qū)間與閾值判定協(xié)議，并將其擴(kuò)大到更大的適用范圍。