秘密區間與閾值的保密判定*

成 雯，李順東，王文麗

1.陜西師范大學 計算機科學學院，西安 710119

2.陜西師范大學 數學與信息科學學院，西安 710119

1 引言

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

區間的保密計算具有重要的理論意義，從目前的研究看，大致可以將區間的保密計算分為兩類：

第一類問題是目前研究最多的，可以描述為參與計算的一方擁有區間，另一方擁有私有數據，兩方合作保密判定點與區間的位置關系。這類問題已經有過很多成果。Nishide 等人首先在文獻[16]中將區間問題作為比特分解協議的應用，但并沒有對區間問題進行深入的分析。文獻[17]利用計算幾何定理和基本算術知識，設計了兩個高效的有理數區間保密計算協議。文獻[18]利用編碼原理和級聯異或，設計了整數點和離散的整數區間的保密判定協議；將實數轉換為整數，設計了實數點和連續的實數區間的保密判定協議。文獻[19]利用多項式和整數向量內積符號的判定，設計了高效的有理數保密計算協議和有理區間保密計算協議。

第二類問題可以描述為兩方或多方合作生成秘密區間，另一方擁有私密數據，任何人對區間信息一無所知，在此基礎上對秘密區間與閾值進行保密判定。此問題在密碼學領域有重要的理論意義，在保密插入、商品交易等應用場景中也具有實際意義。文獻[20]曾將判定點與線段的關系轉化為判定點與線段兩端點形成的區間的關系，但該協議不能區分點與區間的全部位置關系以及不能抵抗合謀攻擊。而本文設計的協議不僅能區分閾值與秘密區間的全部位置關系，且均能抵抗合謀攻擊，并將秘密區間問題由兩方合作生成擴展到多方合作生成。

百萬富翁問題可以描述為：兩個百萬富翁Alice和Bob 想知道他們誰擁有的財富更多，但他們都不想向對方泄露自己的財富。數學描述為：Alice 和Bob各自擁有數據x、y，他們想保密地判斷x、y的大小。Paillier密碼系統的明文空間為ZN。(ZN,+)構成一個加法群，在這個群里是沒有正負數之分的，但如果限制實際處理的明文m都在[0,)之內，即m∈{0,1,…,-1}，如果x+y=0 modN，而0 ＜x＜，那么一定有y＞。在這種情況下y是x的加法逆元，如果認為x≥0，那么y就可以看作負數。進一步假設x,y＜，如果(x-y) modN＜，則x＞y；如果(xy) modN＞，則x＜y。利用這個原理可以設計出半誠實模型下百萬富翁問題的安全多方計算協議。

秘密區間與閾值的保密判定問題直觀上的解決思路就是比較閾值與秘密區間兩個端點的大小關系。針對兩方合作生成秘密區間，只需將秘密區間的兩個端點與閾值進行保密比較，即調用兩次百萬富翁協議；針對多方合作生成秘密區間，通過多次調用百萬富翁協議可以得到秘密區間的兩個端點，再調用兩次百萬富翁協議來比較閾值與秘密區間端點的關系。但是多次調用百萬富翁協議不僅泄露了秘密區間的端點值，而且增加了計算復雜性和通信復雜性。為了保護秘密區間不被泄露以及提高效率，本文利用編碼原理并結合Lifted ElGamal 同態加密算法，提出了優化協議。

本文貢獻如下：

（1）提出了秘密區間與閾值的保密判定這個新的問題，并針對該問題的不同應用場景分別給出了高效安全的解決方法。

（2）針對兩方合作生成秘密區間，基于Paillier 同態加密算法設計了一個協議，利用模擬范例證明了方案的安全性，并進行了效率分析和實驗驗證。

（3）針對多方合作生成秘密區間，利用編碼原理并結合Lifted ElGamal 同態加密算法，提出了優化協議，避免了多次調用百萬富翁協議，保護了秘密區間信息且提高了效率。

（4）本文設計的協議不僅能區分閾值與秘密區間的全部位置關系，且均能抵抗合謀攻擊，并將秘密區間問題由兩方合作生成擴展到多方合作生成。

（5）對區間保密計算問題進行了擴展，針對秘密區間問題進行研究，并給出了秘密區間與閾值保密判定的應用實例。

2 預備知識

2.1 安全性定義

半誠實參與者：一般而言，半誠實參與者是指參與者會嚴格地執行協議，但可能會通過保留的中間結果試圖推出其他參與者的私有數據或其他一些信息。

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

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

定義1（半誠實協議的安全性[21]）設f=f({0,1}?)n→({0,1}?)n是概率多項式函數。fi(x1,x2,…,xn)是f(x1,x2,…,xn)中的第i個元素，令Pi表示第i個參與者，設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) 表 示 所 有 參 與者執行完協議π后的結果。假設參與者都是半誠實的，如果說協議π保密地計算n元函數f，那么存在概率多項式時間算法S，使得對于任意I都有下列式子成立：

2.2 概率加密算法

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

（1）KeyGen

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

（2）Encrypt

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

（3）Decrypt

給定私鑰sk和密文c，輸出相應的明文m：

概率加密算法在加密過程中需要選擇隨機數r∈M參與運算，因此如果選用不同的隨機數r，對于相同的明文m也會產生不同的密文c。

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

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

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

2.3 門限密碼體制

在安全多方計算中可以用門限解密[24]來抵抗合謀攻擊。因為本文需要抵抗n-1 個參與者的合謀攻擊，所以需要的是(n,n)門限。公鑰由n個參與者聯合生成，而私鑰是由這些參與者分享的。用公鑰加密的消息必須由n個參與者合作才能完成解密。Paillier、ElGamal 等密碼系統都可以用來構造門限密碼系統，下面以Lifted ElGamal 為例給出門限密碼系統的具體構造：

（1）KeyGen

選取安全參數λ并產生素數p，選擇的一個生成元g。每個參與者Pi隨機選取ki∈作為私鑰，并計算hi=modp。n個參與者計算公鑰：

（2）Encrypt

為加密明文M，選擇隨機數r，按照下式計算密文c：

（3）Decrypt

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

Lifted ElGamal門限密碼系統在解密過程中得到的是gM，涉及到離散對數計算，為了計算方便，一般取g=2，gM＜p。當M的值不太大時（本文協議2 中M的取值只有0，1），很容易從2M中獲得M。可以預先計算所有的結果，在解密時通過查表快速解密。

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

兩方合作生成秘密區間與閾值的保密判定問題具有廣泛的應用背景。考慮如下場景：Alice 擁有數x，Bob 擁有數y，Alice 和Bob 合作構成區間[x,y]或[y,x]，Carol 擁有數z，現要保密得到z的插入位置，即z在區間左側、在區間內還是在區間右側。

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

解決思路如下：直觀上考慮，要保密地判斷z與秘密區間I的關系，就是要保密比較閾值與區間端點的關系。因此基于以下事實設計了協議1。

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

證明由Paillier 加密算法定義以及加法同態性，可知：

當用私鑰解密時，解密結果為：

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

協議1兩方合作生成秘密區間與閾值的保密判定

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

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

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

并將U發送給P2。

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

并將V、A發送給P1。

（4）P1選取隨機數r21，計算：

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

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

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

正確性分析：兩方合作生成秘密區間與閾值的判定問題可以描述為閾值與區間端點比較問題，基于事實可以正確得到秘密區間與閾值的關系。

安全性分析：

（1）考慮合謀

①P1、P2合謀想獲取P3的信息z。因為只有P3可以解密，P1、P2只能得到P3的密文E(N-z)，而加密算法是語義安全的，E(N-z)和某個隨機數是不能被區分開來的，因此協議1 可以抵抗P1、P2合謀。

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

在這兩個等式中，y、r12、r22、z是P2、P3的保密數和隨機數，x、r11、r21是3 個未知變量。P2、P3不能通過這兩個方程來確定P1的值x。因此協議1 可以抵抗P2、P3合謀。

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

（2）不考慮合謀

假設參與者都不合謀，對于P3來說，存在6 個未知變量，他不能通過兩個方程來確定P1、P2的值；對于P1、P2來說，僅知道自己的數據、T值和一些密文，得不到任何信息。

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

定理1協議1 在半誠實模型下是安全的。

證明下面通過構造滿足式（1）的模擬器S來證明定理1。

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

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

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

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

（2）P3不參與合謀，P1、P2只知道P3發布的密文E(N-z)，而加密算法是語義安全的，密文和某個隨機數是不可區分的，可以用類似的模擬證明協議1的安全性。

因此，該協議對于半誠實參與者是安全的。□

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

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

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

解決思路如下：n個參與者數據中的最小值和最大值分別為秘密區間I的兩個端點，得到I后再保密地判定閾值與秘密區間的關系。可以借鑒文獻[25]中保密替換的思想，但并不需要求出最小值和最大值，而直接得到保密的區間范圍，然后根據z值取對應列元素進行相加即可判斷z與秘密區間I的關系。

多個數據求最小值的方法如下：

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

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

多個數據求最大值的方法如下：

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

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

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

P1分別利用編碼方法1、2 構造數組如下：

由P2替換后為：

由P3替換后為：

則參與者合作構成的秘密區間為：

Alice 擁有數據z(1 ≤z≤m)，只要將數組對應第z列元素進行相加記為T，即可根據下述情況判斷z與秘密區間I的關系。

（1）當T=0 時，z在秘密區間左側；

（2）當T=1 時，z在秘密區間內；

（3）當T=2 時，z在秘密區間右側。

協議2多方合作生成秘密區間與閾值的保密判定

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

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

準備階段，運行Lifted ElGamal 加密系統構造的(n+1,n+1) 門限密碼系統，參與者Pi(i∈{1,2,…,n})，Alice 分別選擇私鑰ki(i∈{1,2,…,n+1})，并選擇公共參數g、p聯合生成公鑰：

（1）參與者P1分別按照編碼方法1、2 將x1表示為數組X1、Y1，并將E(X1)=(E(x11),E(x12),…,E(x1m))，E(Y1)=(E(y11),E(y12),…,E(y1m))發送給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})計算如下：

①參與者Pj根據數據xj按照上述方法分別對數組c、d中的元素進行替換。

②對數組c、d進行重隨機化。

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

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

（5）Alice 根據自己的數據z分別選擇數組c、d中對應的第z列元素，計算如下：

并將U公布。

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

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

安全性分析：協議2 的安全性是基于門限密碼體制的安全性，因此協議過程中公布的密文，如果有任何少于n個參與者進行解密的話都無法得到正確結果，也就是說協議2 是可以抵抗合謀攻擊的。

定理2協議2 在半誠實模型下是安全的。

定理2 的證明與定理1 類似，此處省略具體證明過程。

5 效率分析

秘密區間與閾值的保密判定問題研究成果較少，文獻[20]涉及3 個參與者，且秘密區間由兩方合作生成，與本文協議1 情況類似，對協議1 與文獻[20]進行效率比較。而目前沒有多方合作生成秘密區間與閾值保密判定的協議，因此協議2 沒有與其他文獻進行效率比較。

5.1 計算復雜性

首先分析協議的計算復雜性。為了方便計算，在分析協議的計算復雜性時只考慮最耗時的模指數運算。文獻[20]、協議1 選用的是Paillier 加密算法，加密、解密一次均需要兩次模指數運算，計算一次密文模指數需要一次模指數運算。協議2 選用的是Lifted ElGamal 門限密碼系統，加密一次需要三次模指數運算，解密運算的模指數運算次數與參與解密的人數有關。

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

5.2 通信復雜性

使用通信次數來分析通信復雜性。

文獻[20]需要10 次通信，協議1 需要7 次通信，協議2 需要2n次通信。

文獻[20]、協議1、協議2 的計算復雜性和通信復雜性分析結果如表1 所示。

Table 1 Analysis results of computational complexity and communication complexity表1 計算復雜性和通信復雜性分析結果

由表1 可知，協議1 的計算復雜性和通信復雜性均低于文獻[20]。本文設計的協議均能抵抗合謀攻擊，且能區分閾值與區間全部的位置關系。

5.3 實驗分析

為了進一步驗證協議的效率，通過模擬實驗來測試文獻[20]協議和本文協議執行所用的時間。實驗的測試環境：Windows 10 64 位操作系統，處理器參數為Intel?CoreTMi5-4590S CPU@3.00 GHz，4 GB 內存，用Java語言編程實現，都忽略了預處理時間。

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

Table 2 Comparison of experimental results between Ref.[20]and protocol 1表2 文獻[20]與協議1 實驗結果比較 ms

協議2 使用的是Lifted ElGamal 門限密碼系統，忽略生成共享密鑰的時間。實驗設定p的位數為512 bit，參與者人數一共為10 人，數據范圍從[0,100]到[0,1 000]，并隨機選取100 組數據求平均值作為實驗結果。實驗結果如圖1 所示。

由圖1 可知，數據范圍不斷增大，協議2 的執行時間也不斷增加，執行時間隨數據范圍增長基本呈線性增加。

Fig.1 Relationship between execution time and data range in protocol 2圖1 協議2 執行時間與數據范圍的關系

6 結束語

本文提出了秘密區間與閾值保密判定問題，針對不同的應用場景，設計了兩個秘密區間與閾值保密判定的協議，并證明了協議均能抵抗合謀攻擊。文中還給出了一些秘密區間與閾值保密判定的實際應用場景，今后將在現有研究的基礎上進一步研究高效的秘密區間與閾值判定協議，并將其擴大到更大的適用范圍。