王 寧 顧昊旻 鄭 彤

1(國(guó)網(wǎng)河南省電力公司信息通信公司 河南 鄭州 450052)2(安徽繼遠(yuǎn)軟件有限公司基礎(chǔ)運(yùn)維分部 安徽 合肥 230088)

0 引 言

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

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

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

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

本文中，我們受文獻(xiàn)[15]中數(shù)據(jù)擴(kuò)張的啟示，反過(guò)來(lái)，采用數(shù)據(jù)壓縮的思想，結(jié)合巧妙的編碼以及高效的安全多方求和方法，提出了一個(gè)新的安全多方排序協(xié)議。與已有協(xié)議相比，建議的協(xié)議很好地兼顧了安全性、有效性、公平性，因而更實(shí)用。

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

1.1 線性時(shí)間排序

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

算法1計(jì)數(shù)排序

輸入：數(shù)組A[n]，k

//A[n]存放待排序的n個(gè)數(shù)

輸出：數(shù)組B[n]

//B[n]存放排序后的n個(gè)數(shù)

1. fori←1 tok

2. doC[i]←0

3. forj←1 ton

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

//C[i]現(xiàn)在包含等于

//i的元素個(gè)數(shù)

5. fori←2 tok

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

//C[i]現(xiàn)在包含小于

//或等于i的元素個(gè)數(shù)

7. forj←ndownto 1

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

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

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

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

本文結(jié)合了計(jì)數(shù)排序和桶排的思想，引入高效的安全多方求和技術(shù)以及巧妙的編碼方法，設(shè)計(jì)了一個(gè)安全有效的多方排序算法。

1.2 Paillier同態(tài)加密

在后面的安全多方求和協(xié)議中，我們引入了Paillier同態(tài)加密算法，這里先對(duì)其作簡(jiǎn)要介紹。在1999年歐密會(huì)上，法國(guó)數(shù)學(xué)家P.Paillier提出了一個(gè)概率公鑰加密方案[17](以下簡(jiǎn)稱Paillier加密)。具體方案如下：

wλ(N)≡1modN

(1)

wNλ(N)≡1modN2

(2)

Paillier加密方案的安全基礎(chǔ)是基于“計(jì)算合數(shù)剩余類假設(shè)”[17-19]定義函數(shù)εg：

(3)

另外Paillier加密方案具有加法同態(tài)性質(zhì)，即給定明文m1、m2，有:

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

E(m1+m2)

(4)

2 提出協(xié)議

實(shí)現(xiàn)思想：

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

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

3) 進(jìn)而對(duì)新秘密x′排序：在新秘密序列中統(tǒng)計(jì)小于各自新秘密的秘密個(gè)數(shù)l(x′)(l(x)=l(x′)。

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

協(xié)議1基于安全多方求和的安全多方排序

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

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

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

//即秘密xi在有序序列中對(duì)應(yīng)的位置。

(1) 所有參與者隨機(jī)選擇一個(gè)小整數(shù)m。

//m是一個(gè)小整數(shù)，例如m=2,3,5。

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

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

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

其次，所有參與方公開(kāi)計(jì)算并確定兩個(gè)用于劃分桶的參數(shù)d、k。這里假定d=3、k=4，則四個(gè)桶對(duì)應(yīng)四個(gè)區(qū)間(0,3]、(3,6]、(6,9]、(9,12]。因而5、11、3、8分別轉(zhuǎn)換為向量(0，1，0，0)T、(0，0，0，1)T、(1，0，0，0)T、(0，0，1，0)T。這樣對(duì)5、11、3、8的安全排序就轉(zhuǎn)變?yōu)閷?duì)向量(0，1，0，0)T、(0，0，0，1)T、(1，0，0，0)T、(0，0，1，0)T的安全多方求和。每個(gè)參與方，根據(jù)5進(jìn)制(n+1進(jìn)制)的編碼方式，把各自的隱私向量轉(zhuǎn)變?yōu)橐粋€(gè)小整數(shù)。這里，(0,1,0,0)T對(duì)應(yīng)52=25，(0,0,0,1)T對(duì)應(yīng)50=1，(1,0,0,0)T對(duì)應(yīng)53=125，(0,0,1,0)T對(duì)應(yīng)51=5。最后，指定一個(gè)代理協(xié)助所有參與者執(zhí)行一個(gè)安全多方求和協(xié)議(見(jiàn)協(xié)議2)，安全計(jì)算4個(gè)小整數(shù)的和25+1+125+5=156，再由代理把累加和156逆變換為5進(jìn)制向量(1,1,1,1)T，并向所有參與者公開(kāi)(1,1,1,1)T。

實(shí)際上(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。各參與者根據(jù)公開(kāi)向量和(1,1,1,1)T及各自隱私向量，統(tǒng)計(jì)小于各自秘密的秘密個(gè)數(shù)，從而推算出原始秘密在整個(gè)有序序列中所應(yīng)處的位置。P1得到l(5)=1，因而P1的秘密處于第2的位置；P2得到l(11)=3，因而P2的秘密處于第4的位置；P3得到l(3)=0，因而P3的秘密處于第1的位置；P4得到l(8)=2，因而P4的秘密處于第3的位置。實(shí)際上3<5<8<11，對(duì)應(yīng)著15< 32<354<2 216。

協(xié)議2小整數(shù)的安全多方求和

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

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

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

正確性證明：

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

(5)

3 協(xié)議分析

對(duì)于任意的秘密xi和xj，有以下定理1成立。進(jìn)而，對(duì)于任意的不同秘密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為小整數(shù))，則:

(8)

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

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

表1 各主流協(xié)議的比較

由表1可知，與其他主流協(xié)議相比，我們的協(xié)議整體性能占勢(shì)：計(jì)算開(kāi)銷相對(duì)較低，主要操作為模冪運(yùn)算，其他的加法、整數(shù)與向量轉(zhuǎn)換等操作均為輕量級(jí)可忽略不計(jì)?？偟耐ㄐ艓捪鄬?duì)較低，主要用于小整數(shù)的安全多方求和，特別地保證了協(xié)議的公平性，而且沒(méi)有秘密泄露。

4 結(jié) 語(yǔ)

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