一種實用高效的安全多方排序協議

王 寧 顧昊旻 鄭 彤

1(國網河南省電力公司信息通信公司 河南 鄭州 450052)2(安徽繼遠軟件有限公司基礎運維分部 安徽 合肥 230088)

0 引 言

安全多方計算研究一組互不信任的參與方之間保護隱私的合作計算問題，最早由圖靈獎得主姚期智先生于1982年提出[1]。文獻[1]構造了這樣一個問題(簡稱百萬富翁問題)：兩個百萬富翁Alice和Bob在街頭相遇，其中Alice擁有財富a，Bob擁有財富b。他們希望在不泄露自身財富信息的前提下比較出他們誰更富有，即兩方秘密比較a和b的大小。此后，出現了很多解決百萬富翁問題的安全方案[2-3]。

安全多方排序問題是百萬富翁問題(兩方秘密比較)的自然推廣：假定有n個參與者P1,P2,…,Pn分別擁有隱私秘密x1,x2,…,xn(令X={x1,x2,…,xn})，他們希望在不泄露各自隱私秘密的前提下得到各自秘密在有序序列X′中的位置p(xi)，其中X′是X中n個秘密按從小到大排序的序列。排序問題是計算機科學領域最為重要并得到廣泛研究的核心問題之一，它是求解許多復雜問題的基本構成單元。同樣地，安全多方排序在保護用戶隱私的多方協作計算領域有著很重要的應用價值，是很多復雜協議的基礎協議。例如，保護用戶隱私的電子投標和拍賣[4]、保護用戶隱私的在線電子交易[5]、保密數據庫查詢[6]等。

目前，國外對安全多方排序問題的研究成果并不多。在為數不多的研究成果中，多數作者采用了基于比較的排序思想，因而至少需要Ω(nlogn)次兩方秘密比較。例如，2011年，文獻[7]基于排序網絡提出了一個安全多方排序協議。該協議需要執行O(log2n)輪，總的計算和通信開銷均為O(nlog2n)。文獻[8]提出了一個隨機化的安全希爾排序協議，以較高概率成功排序，需要執行O(log2n)輪，通信和計算開銷均為O(nlogn)。同年，文獻[9]提出了兩個基于比較的常數階輪次的安全排序協議，其通信和計算復雜性均為O(Nn)或O(n2)，其中N表示隱私秘密的范圍大小。文獻[10]基于快速排序提出了另一個有效的安全多方排序協議，需要執行O(logn)輪，其中通信和計算開銷也均為O(nlogn)。

國內也有一些很好的研究成果。2007年，劉文等[11]利用EIGamal密碼體制提出了一個安全多方多數據的排序協議，保證協議在常數輪的情形下，其通信復雜性為O(n2Nlgp)，計算復雜性為O(nN+k1+k2+…+kn)lgp)。2009年，邱梅等[12]利用RSA密碼體制提出了另一個安全多方多數據排序協議，其原理與性能與文獻[11]相當。2008年，李順東等[13]基于離散對數困難性假設提出了一個高效的安全多方排序協議，其通信和計算復雜性均為O(n)。同年，肖倩等[14]基于同態加密提出了兩種安全多方排序協議，繼而基于模糊貼近度提出了另一種高效的多方排序協議，其計算和通信復雜性均降為線性O(n)。但是文獻[13]和文獻[14]中的協議均需要O(n)輪，特別是這兩個協議均不是公平的協議，其中有一個特殊的參與者P1，他與某個(或幾個)參與者聯合可以很容易得到其他參與者的隱私秘密。

本文中，我們受文獻[15]中數據擴張的啟示，反過來，采用數據壓縮的思想，結合巧妙的編碼以及高效的安全多方求和方法，提出了一個新的安全多方排序協議。與已有協議相比，建議的協議很好地兼顧了安全性、有效性、公平性，因而更實用。

1 預備知識

1.1 線性時間排序

對于排序問題，有很多經典的求解算法，例如:插入排序、快速排序、合并排序、堆排序等。以上這些均是基于比較的排序算法。基于比較的排序算法最壞情況下的時間復雜性的下界為Ω(nlogn)。當然，也存在其他更有效的排序算法，例如計數排序和桶排序[16]。計數排序的基本思想是對每一個輸入元素x，確定出小于x的元素個數。有了這個信息就可把x直接放到它在最終輸出數組中的位置上。在下面的算法中假定n個輸入元素中的每一個都是介于1到k之間的整數。

算法1計數排序

輸入：數組A[n]，k

//A[n]存放待排序的n個數

輸出：數組B[n]

//B[n]存放排序后的n個數

1. fori←1 tok

2. doC[i]←0

3. forj←1 ton

4. doC[A[j]]←C[A[j]]+1

//C[i]現在包含等于

//i的元素個數

5. fori←2 tok

6. doC[i]←C[i]+C[i-1]

//C[i]現在包含小于

//或等于i的元素個數

7. forj←ndownto 1

8. doB[C[A[j]]]←A[j]

9.C[A[j]]←C[A[j]]-1

若k=O(n)，則計數排序的時間復雜性為O(n)。在上面計數排序算法中，最關鍵的兩個步驟分別是：計算等于i的元素個數，存儲于C[i]中；計算小于或等于i的元素個數，存儲于新的C[i]中(更新C[i])。對于算法1，若在第4步中調用安全多方求和算法計算C[i]，并公開計算結果C[1]～C[n]，后面各參與者可以根據自身的隱私輸入A[j]，計算小于等于C[A[j]]的值，從而判定自己的秘密在整個秘密序列中的有序位置。經過這樣修改的算法1實質上就是一種安全多方排序算法，在計算時保證了各參與者的隱私輸入。即，借鑒計數排序的思想，對安全多方排序問題的求解自然就轉變為對安全多方求和問題的求解。但遺憾的是，計數排序并不是普適的，而是有一定的適用條件(適用于秘密較小的情形)。

此外，桶排序也是一種高效的排序算法，平均情形下其時間復雜性也為O(n)。它的思想就是把待排序區間劃分成多個相同大小的子區間或稱桶，然后將n個輸入數分布到各個桶中去。為了得到有序序列，先對各個桶中的數進行排序，然后按次序把各桶中的元素列出來即可。

本文結合了計數排序和桶排的思想，引入高效的安全多方求和技術以及巧妙的編碼方法，設計了一個安全有效的多方排序算法。

1.2 Paillier同態加密

在后面的安全多方求和協議中，我們引入了Paillier同態加密算法，這里先對其作簡要介紹。在1999年歐密會上，法國數學家P.Paillier提出了一個概率公鑰加密方案[17](以下簡稱Paillier加密)。具體方案如下：

wλ(N)≡1modN

(1)

wNλ(N)≡1modN2

(2)

Paillier加密方案的安全基礎是基于“計算合數剩余類假設”[17-19]定義函數εg：

(3)

另外Paillier加密方案具有加法同態性質，即給定明文m1、m2，有:

gm1+m2(r1·r2)NmodN2(令r=r1·r2)=

E(m1+m2)

(4)

2 提出協議

實現思想：

1) 避免基于比較的排序方法，借鑒計數排序和桶排序的思想，所有參與者執行一次安全多方求和協議，計算小于各自秘密的秘密個數，從而確定各自秘密x在整個有序序列中應處的位置p(x)。

2) 為了提高效率，參與者先對各自的秘密x壓縮得到x′，要求p(x)=p(x′)。

3) 進而對新秘密x′排序：在新秘密序列中統計小于各自新秘密的秘密個數l(x′)(l(x)=l(x′)。

4) 最終各參與者輸出p(x)=l(x)+1，即各自秘密在有序序列中對應的位置。

協議1基于安全多方求和的安全多方排序

輸入：各參與者Pi隱私輸入秘密xi；

//假定各個參與者的秘密各不相同，且xi∈ZN。

輸出：各參與者Pi輸出p(xi)；

//即秘密xi在有序序列中對應的位置。

(1) 所有參與者隨機選擇一個小整數m。

//m是一個小整數，例如m=2,3,5。

(1) 參與者計算d=└logmN┘ /k，其中k為劃分的桶的個數，而d為每個桶的區間大小。

(2) 把整個待排序空間劃分為k個區間(即k個桶)，分別為(0,d]，(d,2d]，…，((k-1)d,└logmN┘]。

下面舉例說明，假定有4個參與者：P1、P2、P3、P4，且假定他們各自的隱私秘密為32、2 216、15、354。即P1擁有32，P2擁有2 216，P3擁有15，P4擁有354。他們希望在保證各自隱私的前提下，實施安全的排序。

其次，所有參與方公開計算并確定兩個用于劃分桶的參數d、k。這里假定d=3、k=4，則四個桶對應四個區間(0,3]、(3,6]、(6,9]、(9,12]。因而5、11、3、8分別轉換為向量(0，1，0，0)T、(0，0，0，1)T、(1，0，0，0)T、(0，0，1，0)T。這樣對5、11、3、8的安全排序就轉變為對向量(0，1，0，0)T、(0，0，0，1)T、(1，0，0，0)T、(0，0，1，0)T的安全多方求和。每個參與方，根據5進制(n+1進制)的編碼方式，把各自的隱私向量轉變為一個小整數。這里，(0,1,0,0)T對應52=25，(0,0,0,1)T對應50=1，(1,0,0,0)T對應53=125，(0,0,1,0)T對應51=5。最后，指定一個代理協助所有參與者執行一個安全多方求和協議(見協議2)，安全計算4個小整數的和25+1+125+5=156，再由代理把累加和156逆變換為5進制向量(1,1,1,1)T，并向所有參與者公開(1,1,1,1)T。

實際上(1,1,1,1)T=(0,1,0,0)T+(0,0,0,1)T+(1,0,0,0)T+(0,0,1,0)T。各參與者根據公開向量和(1,1,1,1)T及各自隱私向量，統計小于各自秘密的秘密個數，從而推算出原始秘密在整個有序序列中所應處的位置。P1得到l(5)=1，因而P1的秘密處于第2的位置；P2得到l(11)=3，因而P2的秘密處于第4的位置；P3得到l(3)=0，因而P3的秘密處于第1的位置；P4得到l(8)=2，因而P4的秘密處于第3的位置。實際上3<5<8<11，對應著15< 32<354<2 216。

協議2小整數的安全多方求和

輸入：各參與者Pi隱私輸入秘密xi；

1) 每個參與者Pi(1≤i≤n)隨機生成k個整數ai,1,ai,2，…，ai,k，其中k≤(n-1)/2，k的具體值可由Pi確定，而ai,j∈[0,p0](1≤j≤k)。接著參與者Pi隨機選取k個其他參與者，假定為{Pi1，Pi2，…，Pik}。Pi分別計算gp0-ai,jmodN2，并把gp0-ai,jmodN2秘密發送給參與者Pij(1≤j≤k)。

3) 收到其他所有參與者的秘密消息gp0-ai,jmodN2或gp0+ai,jmodN2后，每個參與者Pj(1≤j≤n)計算收到的所有秘密消息的乘積Gj。例如Pj分別收到P1、P3、P5的秘密消息gp0-a1,jmodN2、gp0+a3,jmodN2、gp0-a5,jmodN2，則Pj計算Gj=gp0-a1,jgp0+a3,jgp0-a5,jmodN2。

正確性證明：

(gp0+aj,1gp0+aj,2…gp0+aj,k)]}modN2=

(5)

3 協議分析

對于任意的秘密xi和xj，有以下定理1成立。進而，對于任意的不同秘密xi和xj，有以下定理2成立。

定理1假定參與者Pi、Pj的隱私輸入分別為xi、xj，則有：

其中xi=xj的概率為1/(m└logmxi┘+1-m└logmxi┘)，反之xi≠xj的概率為1-1/(m└logmxi┘+1-m└logmxi┘)。

[(N-m└logmN┘)(N-m└logmN┘-1)]=

(6)

(7)

若N=ms(其中m為小整數)，則:

(8)

協議1中，若選擇一個隨機的m并執行秘密排序1次，各參與者的輸出結果可能不是正確解，而是近似解，其最大誤差為所屬桶內的秘密個數。顯然，當xi所在桶內只有一個秘密時，計算得到的l(xi)是正確的，從而p(xi)是正確的。實際上根據累加向量和，參與者可以判斷自己獲得的解p(xi)是否正確。為了提高精度，可以通過協議1的多次執行(即重新選擇m重新計算p(xi))，各參與者總能得到正確的輸出。此外，協議1也適宜于每個參與者擁有多個秘密的情形。與單個秘密情形有所不同的僅僅是“在協議1的第2步中的第3小步驟中，根據公開劃分的桶，每方將得到一個多個分量為1(對應多個秘密)的0/1向量”，其他計算步驟不變。

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

表1 各主流協議的比較

由表1可知，與其他主流協議相比，我們的協議整體性能占勢：計算開銷相對較低，主要操作為模冪運算，其他的加法、整數與向量轉換等操作均為輕量級可忽略不計。總的通信帶寬相對較低，主要用于小整數的安全多方求和，特別地保證了協議的公平性，而且沒有秘密泄露。

4 結 語

避免傳統的基于比較的排序方法，借助計數排序和桶排序的思想，把安全多方排序歸約為安全多方求和。結合一種巧妙的編碼方法，設計了一個安全、高效的多方排序協議。盡管安全和效率是一對矛盾體，但建議的協議使用靈活，可以根據安全等級，動態調整相應的安全策略。安全性高的，通信代價也相應高，上限為O(n2)；反之，通信代價低，理論上可達O(n)。與主流協議相比，綜合性能優，保證了協議的公平性，能夠在常數輪內有效實現。此外，能夠滿足參與者擁有多個隱私秘密的排序情形。因而建議的協議有著很好的應用前景，特別地，可作為基礎協議應用于分布式網絡環境下保護用戶隱私的多方協作計算中。