最大最小值的保密計算*

楊顏璟, 李順東, 杜潤萌

陜西師范大學(xué) 計算機(jī)科學(xué)學(xué)院, 西安710119

1 引言

隨著互聯(lián)網(wǎng)、云計算與大數(shù)據(jù)的迅速普及, 隱私泄露極易發(fā)生, 隱私保護(hù)變得十分迫切. 很多隱私保護(hù)問題都可以用安全多方計算方法解決, 因此安全多方計算成為信息社會隱私保護(hù)的關(guān)鍵技術(shù). 如果借助可信的第三方, 安全多方計算問題很容易解決, 但在遍布整個世界的、復(fù)雜的互聯(lián)網(wǎng)環(huán)境中, 找到一個所有參與者都信任的第三者并不容易, 因此需要設(shè)計安全多方計算協(xié)議保證私有信息不被泄露. 安全多方計算在保護(hù)私密數(shù)據(jù)隱私的前提下, 使得參與者能夠最大限度地利用自己的私有數(shù)據(jù)進(jìn)行保密合作計算, 充分發(fā)揮私有數(shù)據(jù)在社會、經(jīng)濟(jì)和科學(xué)技術(shù)領(lǐng)域的積極作用, 是實現(xiàn)合作保密計算的主要工具.

安全多方計算這一概念由圖靈獎獲得者姚期智教授在20 世紀(jì)80 年代以百萬富翁問題引入[1]. 百萬富翁問題是指分別擁有隱私數(shù)據(jù)x,y 的兩個參與者, 保密判斷x 是否大于y, 而不泄露x,y 的其他信息.由百萬富翁問題發(fā)展而來的安全多方計算是指分別擁有隱私數(shù)據(jù)x1,x2,··· ,xn的n 個參與者聯(lián)合計算f(x1,x2,··· ,xn) 的值, 計算完成之后, 每個參與者除了得到f(x1,x2,··· ,xn) 的值之外, 得不到關(guān)于隱私數(shù)據(jù)的其他任何信息. 后來, Goldreich, Micali 等人[2,3]對安全多方計算的理論進(jìn)行深入研究, 證明在一定的條件下, 任意函數(shù)f(x1,x2,··· ,xn) 的安全多方計算都是可以實現(xiàn)的, 并且給出基于不經(jīng)意傳輸?shù)慕鉀Q方案. 這樣的通用解決方案有重要的理論意義, 奠定了安全多方計算的理論基礎(chǔ), 對于某些簡單的安全雙方計算問題, 基于電路的通用解決方案是有效的, 對于復(fù)雜的安全計算問題通用解決方案的效率并不理想, 而且把任意問題轉(zhuǎn)化為電路計算問題也不是一個簡單的問題, 因此針對具體問題提出具體的解決方案是安全多方計算研究的重要方面.

在隱私保護(hù)需要的推動下, 安全多方計算研究取得了豐碩的成果[4,5]. 密碼學(xué)家研究了各個應(yīng)用領(lǐng)域中出現(xiàn)的安全多方計算問題, 其中包括保密科學(xué)計算[6–8]、保密計算幾何[9]、保密數(shù)據(jù)挖掘[10]等問題.計算一組隱私數(shù)據(jù)的最小值(最大值) 在保密的科學(xué)計算中是非常重要的, 可以保密地確定離散數(shù)據(jù)所處的區(qū)間. 理論上這個問題可以歸約到百萬富翁問題, 即通過兩兩比較求出最大值和最小值, 但其計算復(fù)雜性為O(n2), 其中n 為隱私數(shù)據(jù)個數(shù). 1987 年, 文獻(xiàn)[3] 使用算術(shù)電路解決百萬富翁問題, 但計算復(fù)雜性和通信復(fù)雜性都與輸入的規(guī)模呈線性關(guān)系, 只能比較兩個較小的數(shù). 2008 年, 文獻(xiàn)[11] 將百萬富翁問題歸約到集合元素判定問題, 并設(shè)計了基于對稱密碼學(xué)的集合元素保密判定協(xié)議, 進(jìn)而解決百萬富翁問題, 提高了計算效率. 2013 年, 文獻(xiàn)[12] 設(shè)計了一種新的算術(shù)編碼方法, 以此解決比較兩個私有數(shù)據(jù)大小的問題, 很大程度上降低協(xié)議的計算復(fù)雜性.

在安全多方計算中多次調(diào)用百萬富翁協(xié)議求最大值和最小值不僅效率較低, 而且還會泄露兩兩數(shù)據(jù)之間的大小關(guān)系等信息; 若將該問題轉(zhuǎn)化為排序問題, 在一定程度上可以提高效率, 但是這樣做仍會泄露除最大值和最小值以外的其他信息. 最大值和最小值的安全多方計算要求所有參與者只能得到最大值和最小值而不能泄露其他任何信息. 這是解決最大值和最小值保密計算問題的關(guān)鍵所在. 文獻(xiàn)[13–16] 利用編碼方法解決了最大值和最小值的保密計算問題, 但是這些方法不能同時保密計算最大值和最小值.

同時計算一組隱私數(shù)據(jù)的最大最小值是一個新的保密科學(xué)計算問題, 目前還未見到該問題的解決方案. 如果用前述計算最大值和最小值的方法解決, 需要對同一組數(shù)進(jìn)行兩次編碼, 并執(zhí)行兩次協(xié)議才能計算出最大值和最小值, 不僅計算復(fù)雜性與通信復(fù)雜性較高, 且存在泄露信息的可能性.

最大最小值的保密計算問題在信息安全實踐中有重要的實際意義. 在日常生活中, 年齡、工資、成績、產(chǎn)品規(guī)格的參數(shù)等數(shù)據(jù)都在較小的區(qū)間范圍內(nèi), 因此保密地求出數(shù)據(jù)的閾值有很大的實際應(yīng)用價值. 例如某求職者想要了解某公司的工資水平在該行業(yè)處于什么位置, 這就需要執(zhí)行最大值和最小值保密計算協(xié)議來解決該問題. 除此之外, 最大最小值的保密計算問題還具有很重要的數(shù)學(xué)意義. 在求一些數(shù)據(jù)的平均值時, 需要除去該組數(shù)據(jù)的離群值(outlier) 以確保平均值的穩(wěn)定性和準(zhǔn)確性, 保密地計算出最大值和最小值對除去離群值有重大意義. 例如, 某些比賽現(xiàn)場中評委在打分時為了保證比賽的公平性, 需要去掉一個最高分和一個最低分后計算平均分, 在這個過程中打了最高分和打了最低分的評委的身份信息是保密的, 執(zhí)行最大最小值的保密計算協(xié)議則可解決該問題.

范圍查詢問題同樣具有很大的研究價值, 該問題出現(xiàn)在很多應(yīng)用程序中, 包括地理信息系統(tǒng), 數(shù)據(jù)庫信息查詢等. 在許多情況下, 數(shù)據(jù)庫中包含了許多機(jī)密信息, 為了更好地提供范圍查詢服務(wù), 保密地判斷一個數(shù)據(jù)是否在一個區(qū)間內(nèi)是很有必要的. 例如, 一個圖形程序可能需要縮放一組數(shù)據(jù)(x,y) 以適應(yīng)矩形顯示屏或其他圖形設(shè)備, 為此, 程序需要確定x 和y 的值是否在矩形所在位置的坐標(biāo)范圍內(nèi).

為了同時保密計算最大值和最小值, 本文提出一種新的將隱私數(shù)據(jù)編碼為隱私數(shù)組的編碼方法, 在此基礎(chǔ)上利用同態(tài)加密算法可以同時保密計算最大值和最小值, 從而保密地確定離散數(shù)據(jù)的區(qū)間范圍, 在避免信息泄露的同時提高效率. 本文設(shè)計了兩個協(xié)議, 第一個協(xié)議可以抵抗解密密鑰持有者不參與的合謀攻擊; 第二個協(xié)議可以抵抗任意的合謀攻擊. 并且進(jìn)一步以此編碼方案為基礎(chǔ)解決了保密判斷數(shù)據(jù)是否在某個區(qū)間的問題, 即保密的范圍查詢問題. 本文貢獻(xiàn)主要如下:

(1) 提出了一種新的對隱私數(shù)據(jù)進(jìn)行編碼的方法, 進(jìn)一步將這種編碼方法與Paillier 加密算法結(jié)合設(shè)計了可以一次性計算一組保密數(shù)據(jù)的最大值和最小值的高效協(xié)議. 該協(xié)議可以抵抗解密密鑰持有者不參與的合謀攻擊.

(2) 設(shè)計了一種特殊的編碼方法, 保證橢圓曲線密碼系統(tǒng)對于明文具有加法同態(tài)性. 該編碼方法對于充分利用橢圓曲線的同態(tài)性解決其他安全多方計算問題有重要的理論與實際意義. 進(jìn)一步利用門限解密橢圓曲線密碼系統(tǒng)設(shè)計了最大值和最小值的保密計算協(xié)議, 解密密鑰由所有參與者共享,該協(xié)議能抵抗任意參與者的合謀攻擊.

(3) 基于同樣的編碼方法, 設(shè)計了保密判定數(shù)據(jù)是否在區(qū)間內(nèi)的協(xié)議. 用模擬范例證明了本文所設(shè)計方案的安全性, 并實際測試了協(xié)議的效率. 實驗數(shù)據(jù)表明本文設(shè)計的協(xié)議是高效的.

2 預(yù)備知識

2.1 安全性定義

理想模型 假設(shè)存在一個所有參與者都信賴的第三方(Trusted Third Party, TTP). 在這種假設(shè)下安全多方計算的過程如下: 參與者Pi(i=1,··· ,n) 分別將擁有的隱私數(shù)據(jù)xi發(fā)送給TTP, TTP 自己計算函數(shù)f(x1,··· ,xn), 然后將結(jié)果分別發(fā)送給Pi.

因為參與者Pi(i = 1,··· ,n) 無法從可信的第三方中得到除f(x1,··· ,xn) 之外的任何信息, 所以理想模型下安全多方計算協(xié)議所具有的安全性是實際情況下任何一個保密計算函數(shù)f 的協(xié)議都難以達(dá)到的.理想模型下的協(xié)議雖然簡單、安全, 但是在現(xiàn)實中所有參與者完全信任的TTP 不容易找到, 因此密碼學(xué)的主要任務(wù)就是設(shè)計能夠代替理想模型協(xié)議的密碼學(xué)協(xié)議.

半誠實模型 在協(xié)議的執(zhí)行過程中, 半誠實參與者[2]會完全嚴(yán)格地執(zhí)行協(xié)議的每一步, 但是他們可能會保留執(zhí)行協(xié)議過程中獲取的信息, 并試圖從這些信息推導(dǎo)出其他參與者的私有信息.

設(shè)參與者Pi(i = 1,··· ,n) 分別擁有私有數(shù)據(jù)xi, 他們執(zhí)行協(xié)議π 保密地計算函數(shù)f(x1,··· ,xn).在計算過程中, 參與者獲得的信息記為viewπi(X), 其中

Mji(j =1,··· ,t) 表示參與者Pi收到的第j 個信息, ri是參與者Pi選取的隨機(jī)數(shù). 那么對于P1,··· ,Pn中部分參與者構(gòu)成的子集I ={Pi1,··· ,Pis}, 有

對于一個函數(shù)f, 如果存在概率多項式時間算法S, 使得

其中c≡表示其兩邊的對象計算不可區(qū)分, 則稱協(xié)議π 安全地計算n 元函數(shù)f.

2.2 部分同態(tài)加密方案

部分同態(tài)加密算法是一種特殊的加密算法[17], 可以使我們在密文狀態(tài)下對明文進(jìn)行某種運算, 即直接對密文進(jìn)行某種計算的結(jié)果, 等于對明文進(jìn)行某種計算后再加密. 部分同態(tài)加密體制包括加法、乘法和異或同態(tài)加密, 其特殊性質(zhì)在安全多方計算中有著重要應(yīng)用, 本文設(shè)計的協(xié)議用到了加法同態(tài)性

基于此, 本文設(shè)計了基于Paillier 加密算法和橢圓曲線門限密碼體制的安全多方計算協(xié)議.

2.2.1 Paillier 加密算法

Paillier 加密算法[18]的具體過程如下:

解密

假設(shè)密文

那么

因此該算法滿足加法同態(tài)性質(zhì)

Paillier 加密算法具有語義安全性, 即同一個明文可以加密成多個不同的密文, 這些密文都是計算不可區(qū)分的(即無法知道這些密文是不是同一個明文對應(yīng)的密文).

2.2.2 橢圓曲線密碼系統(tǒng)

橢圓曲線密碼系統(tǒng)(Elliptic Curve Cryptography,ECC)是1985 年由Victor Miller 和Neal Koblitz共同提出的[19]. 在密碼學(xué)中普遍采用的是有限域上的橢圓曲線, 其中最常用的是由下面方程定義的曲線

式(2) 中所有系數(shù)都是某一有限域GF(p) 中的元素(其中p 為一大素數(shù)).

設(shè)Ep(a,b) 表示方程(2) 所定義的橢圓曲線上的點{(x,y)|0 ≤x

首先取一大素數(shù)p 和兩個參數(shù)a,b, 得到方程(2) 表達(dá)的橢圓曲線及其上面的點構(gòu)成的Abel 群Ep(a,b). 取Ep(a,b) 的一個基點G(x1,y1), 要求G 的階是一個非常大的素數(shù)(G 的階是滿足nG = O的最小正整數(shù)n). Ep(a,b) 和G 作為公開參數(shù).

密鑰生成 選擇一小于p 的整數(shù)k 作為私鑰, 并由K =kG 產(chǎn)生Ep(a,b) 上的一點作為公鑰.

加密 將消息m 編碼到Ep(a,b) 上一點M, 并隨機(jī)選擇正整數(shù)r, 計算密文

解密 使用私鑰k 對密文(c1,c2) 進(jìn)行解密運算, 計算過程如下

然后對明文編碼點M 解碼, 最終得到m.

同態(tài)性 設(shè)E(M1)=(M1+r1K,r1G),E(M2)=(M2+r2K,r2G), 那么

式(3) 表明橢圓曲線密碼系統(tǒng)對于橢圓曲線上的點來說具有加法同態(tài)性. 如果能夠設(shè)計一種線性編碼方法, 使得橢圓曲線密碼系統(tǒng)對于編碼前的原始數(shù)據(jù)仍保持加法同態(tài)性, 這對于我們設(shè)計構(gòu)造最大最小值的保密計算協(xié)議具有重要意義, 為此我們提出一種新的編碼方法.

2.3 線性編碼

編碼 假設(shè)選定了橢圓曲線的一個基點G, 任意給定一個正整數(shù)m, 可以將m 編碼為mG.

解碼給定一個消息的編碼M =mG, 要解碼得到消息m 需要計算橢圓曲線上的離散對數(shù). 這個問題是困難的, 但是如果將消息限制在一個較小的范圍內(nèi)如m ∈{0,··· ,210}, 解碼過程就可以避免計算離散對數(shù). 我們可以制作一個乘法表T ={G,2G,3G,··· ,210G}, 要解碼M 只需要反向查表即可.

這樣的編碼方法可使密碼系統(tǒng)對于橢圓曲線上的點mG 的同態(tài)性轉(zhuǎn)化為對于明文消息m 的同態(tài)性.這是因為明文m1,m2的編碼為M1= m1G,M2= m2G, 根據(jù)式(3), 可得到E(m1G)+E(m2G) =E((m1+m2)G). 即不需要解密, 就可由m1G 和m2G 的密文直接計算得到(m1+m2)G 的密文(c1,c2).當(dāng)然通過解密(c1,c2), 僅可得到(m1+m2)G, 進(jìn)一步解碼才能獲得m1+m2. 由于橢圓曲線上離散對數(shù)問題的困難性, 無法直接由(m1+m2)G 解碼獲得m1+m2, 但當(dāng)m1,m2的范圍不太大時, 可以用上述查表法進(jìn)行解碼.

2.4 門限解密

在可對抗合謀攻擊的門限解密密碼體系中[21,22], 公鑰由n 個參與者聯(lián)合生成, 解密密鑰由這n 個參與者聯(lián)合持有. 公鑰可以直接用來加密消息, 但解密一個密文需要n 個參與者中一定數(shù)量人員合作才能完成. 在安全多方計算中, 總希望抵抗盡可能多參與者的合謀攻擊, 因而需要樸素的門限密碼體制, 即(n,n)門限密碼體制, 具體過程如下.

密鑰生成 選定一條橢圓曲線Ep(a,b) 及其上的一個基點G, 假設(shè)G 的階是一個非常大的素數(shù)q.Ep(a,b) 和G 作為公開參數(shù). 每個參與者Pi任意選擇一個私鑰ki

加密 首先將消息在橢圓曲線Ep(a,b) 上進(jìn)行編碼得到點M, 并隨機(jī)選擇正整數(shù)r(1 ≤r ≤q ?1),通過加密運算得到(c1,c2)=(M +rK,rG).

解密 每個參與者Pi根據(jù)私鑰ki計算kic2, 將計算結(jié)果發(fā)送給其他參與者, 然后所有參與者聯(lián)合解密(c1,c2) 得到編碼點M

3 基于Paillier 算法的最大最小值保密計算協(xié)議

本節(jié), 我們利用Paillier 加密算法設(shè)計一個同時計算最大值與最小值的協(xié)議.

3.1 基本原理

編碼方法 假設(shè)所有參與者Pi(i = 1,··· ,n) 的私有數(shù)據(jù)xi∈{z1,z2,··· ,zl} = U(對于很多應(yīng)用場景如涉及人的年齡、學(xué)生的成績、人們的工資等, 集合U 是客觀存在的), 其中z1< z2< ··· < zl且|U|=l. 參與者Pi(i=1,··· ,n) 首先按照下面的方法構(gòu)造一個數(shù)組

其中

rij∈ZN為不等于0 的隨機(jī)數(shù). 依此方式, Pi擁有的秘密數(shù)據(jù)xi與數(shù)組Xi構(gòu)成一一對應(yīng)關(guān)系. 對得到的n 個數(shù)組X1,··· ,Xn求和, 即將這些數(shù)組的對應(yīng)元素相加, 得到一個新的數(shù)組

例1 假設(shè)x1=4,x2=7,x3=2,x4=5, 令U ={1,2,3,4,5,6,7,8,9} 并構(gòu)造表1.

顯然, 按照數(shù)組Y 的順序方向, 第一個不為0 的元素17 所在的位置在全集U 中對應(yīng)的元素2 為最小值; 按照數(shù)組Y 的逆序方向, 第一個不為0 的元素39 所在的位置在全集U 中對應(yīng)的元素7 為最大值.

事實1 對于n 個參與者擁有的數(shù)據(jù)x1,··· ,xn, 均按照方式(4) 構(gòu)造數(shù)組Xi, 將數(shù)組Xi對應(yīng)位置的元素相加, 得到一個新的數(shù)組: Y = (y1,··· ,yl). 按照數(shù)組Y 順序方向, 當(dāng)首次出現(xiàn)yi?= 0 時,min{x1,··· ,xn}=zi; 按照數(shù)組Y 逆序方向, 當(dāng)首次出現(xiàn)yj?=0 時, max{x1,··· ,xn}=zj.

證明: 因為對于每個編碼后得到的數(shù)組Xi(i = 1,··· ,n) 來說, xi在全集U 中所在的位置對應(yīng)的元素為隨機(jī)數(shù)rij, 其余位置對應(yīng)的元素為0, 將數(shù)組Xi(i=1,··· ,n) 對應(yīng)位置的元素進(jìn)行相加得到數(shù)組Y, 相當(dāng)于在全集中對最大值和最小值的位置進(jìn)行標(biāo)記, 第一個不等于0 的元素yi和最后一個(按照數(shù)組Y 逆序方向為第一個) 不等于0 的元素yj在數(shù)組Y 中所在的位置則為最大值和最小值在全集中所在的位置.上述事實是我們保密計算最大值和最小值的依據(jù), 直接這樣做沒有保密性可言. 要實現(xiàn)最大最小值的保密計算需要在密文狀態(tài)下對明文進(jìn)行運算, 并分別從左向右解密得到最小值后再從右向左解密計算最大值. 而Paillier 加密算法和橢圓曲線密碼系統(tǒng)均是加法同態(tài)算法, 可實現(xiàn)保密求和運算.

U 1 2 3 4 5 6 7 8 9 X1 0 0 0 21 0 0 0 0 0 X2 0 0 0 0 0 0 39 0 0 X3 0 17 0 0 0 0 0 0 0 X4 0 0 0 0 16 0 0 0 0 Y 0 17 0 21 16 0 39 0 0

3.2 具體協(xié)議

協(xié)議1 基本最大最小值保密計算方案(參與者之間有安全信道)輸入: P1,··· ,Pn各自的秘密數(shù)據(jù)x1,··· ,xn.

輸出: y =min{x1,··· ,xn};z =max{x1,··· ,xn}.

(1) P1使用Paillier 加密算法產(chǎn)生私鑰和公鑰, 并公布公鑰.

(2) 所有參與者Pi(i = 1,··· ,n) 根據(jù)3.1 節(jié)式(4) 中構(gòu)造數(shù)組的方法, 將私有數(shù)據(jù)xi轉(zhuǎn)化為數(shù)組Xi, 其中

并使用公鑰加密數(shù)組Xi得到密文序列

(3) 令C =(c1,··· ,cl)=(1,··· ,1). Pi(i=1,··· ,n ?1) 依次計算

并把結(jié)果發(fā)送給Pi+1. Pn按照上述方法做同樣的計算得到C =(c1,··· ,cl).

(4) Pn將密文數(shù)組C 的元素從左向右依次逐個發(fā)送給P1, P1進(jìn)行解密. 當(dāng)解密得到第一個不等于0 的元素yi時, P1終止密文發(fā)送, 并令min{x1,··· ,xn} = zi; 然后Pn從右向左依次將C 的元素逐個發(fā)送給P1, P1解密得到第一個不等于0 的元素yj時終止密文發(fā)送, 并令max{x1,··· ,xn}=zj.

(5) P1公布min{x1,··· ,xn},max{x1,··· ,xn}.

3.3 方案分析

正確性分析 協(xié)議1 的正確性可由3.1 節(jié)中所述的事實1 得到保證.

安全性分析 在協(xié)議1 中, P1對數(shù)組C 中元素進(jìn)行解密運算. 由于P1持有私鑰能夠解密, 協(xié)議1 能夠抵抗沒有P1參與的合謀攻擊. 為了保證協(xié)議1 的安全性, 密文傳輸?shù)倪^程需要建立在安全信道之上.

定理1 同時保密計算最大值與最小值的協(xié)議1 在半誠實模型下是安全的.

證明: 通過構(gòu)造滿足式(1)的模擬器S 來證明定理1, 分為以下三種情況:

(1) P1不參與合謀, I = {P2,··· ,Pi?1,Pi+1,··· ,Pn} 要獲得Pi保密數(shù)據(jù)的相關(guān)信息. S 的模擬過程如下:

(a) 給定輸入(I,XI,fI(X)), 即(I,XI,fI(X)) = (I,(x2,··· ,xi?1,xi+1,··· ,xn),fI(X)), 隨機(jī)選擇兩個數(shù)據(jù)x′1∈{z1,z2,··· ,zl} = U 和x′i∈{z1,z2,··· ,zl} = U, 使得fI(X) = fI(X′), 在這里X′={x′1,x2,··· ,xi?1,x′i,xi+1,··· ,xn}.

(b) 模擬器S 將X′中的每個數(shù)據(jù)x′i編碼為數(shù)組X?1,··· ,Xi?1,X?i,Xi+1,··· ,Xn. 然后模擬器S利用公鑰加密X?1,··· ,Xi?1,X?i,Xi+1,··· ,Xn, 得到

(c) 模擬器S 按照協(xié)議1 將密文數(shù)組中對應(yīng)元素相乘, 得到數(shù)組C?. 然后解密得到fI(X′).

在協(xié)議1 中

令

由于Paillier 加密算法是語義安全的, 對I 中參與者來說, 密文數(shù)組C 與C?是計算不可區(qū)分的, 即Cc≡C?. 又由于fI(X)=fI(X′), 故有

由此可知, 在情況(1) 下, 協(xié)議1 是安全的.

(2) P1不參與合謀, I ?{P2,··· ,Pi?1,Pi+1,··· ,Pn} 要獲得Pi保密數(shù)據(jù)的相關(guān)信息.

由情況(1) 可知, 當(dāng)I = {P2,··· ,Pi?1,Pi+1,··· ,Pn} 時, 只有P1擁有私鑰可以解密, 因此參與合謀方得不到私有數(shù)據(jù)x1和xi的相關(guān)信息. 那么當(dāng)I ?{P2,··· ,Pi?1,Pi+1,··· ,Pn} 時, 同樣因為只有P1擁有私鑰可以解密, 所以參與合謀方得不到與x1、xi有關(guān)的信息. 即在最大合謀(攻擊者) 結(jié)構(gòu)參與合謀的情況下是安全的, 合謀者為其子集時也是安全的.

(3) P1參與合謀, I ={P1,··· ,Pi?1,Pi+1,··· ,Pn} 要獲得Pi保密數(shù)據(jù)的相關(guān)信息.

在此情況下, 由于P1擁有私鑰可以解密, 且有n ?1 個參與者參與合謀, 他們可以獲知Pi的私有數(shù)據(jù)xi的相關(guān)信息. 如果參與合謀方利用可信的第三者同時保密計算最大值和最小值, 當(dāng)xi是最大值或者最小值時會泄露數(shù)據(jù)xi的大小; 當(dāng)xi不是最大值或者最小值時, 參與合謀方只能確定xi處于某個區(qū)間內(nèi). 因此這和使用可信第三者的安全性只有微小的差別.

由此可知, 協(xié)議1 可以抵抗解密密鑰持有者不參與的所有合謀攻擊.

4 基于門限解密的最大最小值保密計算協(xié)議

上節(jié)提出了計算最大值和最小值的高效方案, 但是該方案只能抵抗沒有P1參與的合謀攻擊. 如果P1與Pn合謀, 就可以知道所有參與者的隱私數(shù)據(jù)集合(但不知道Pi和xi的對應(yīng)關(guān)系), 這對于其他參與者是不公平的, 也是協(xié)議的安全弱點. 為了阻止P1參與的合謀攻擊, 本部分我們應(yīng)用橢圓曲線密碼系統(tǒng), 構(gòu)造一個所有參與者聯(lián)合解密的最大值和最小值保密計算方案, 其安全性更強.

4.1 具體協(xié)議

協(xié)議2 各參與者地位平等的抗合謀的最大最小值保密計算方案

輸入: P1,··· ,Pn各自的秘密數(shù)據(jù)x1,··· ,xn.

輸出: y =min{x1,··· ,xn};z =max{x1,··· ,xn}.

(1) P1,··· ,Pn商定一條橢圓曲線Ep(a,b) 及其上的一個生成元G(要求G 的階L 足夠大), 然后每個參與者Pi選擇私鑰ki,2 ≤ki≤L ?1, 聯(lián)合生成公鑰(K,G)

(2) 所有參與者Pi(i=1,··· ,n) 以方式(4) 將自己的數(shù)據(jù)轉(zhuǎn)化為數(shù)組Xi, 其中

然后, Pi將數(shù)組Xi的每個元素編碼成為橢圓曲線Ep(a,b) 上的點Mij=xijG, j ∈[1,l], 得到

并加密Mi的每個元素, 得到下面編碼密文數(shù)組E(Mi), 并公布

(3) 所有參與者利用密文數(shù)組構(gòu)成一個密文矩陣M

將矩陣M 每一列的元素相加, 得到一個新的密文數(shù)組

(4) 所有參與者聯(lián)合對密文數(shù)組T 從左到右解密, 并對解密結(jié)果進(jìn)行解碼, 當(dāng)?shù)玫降谝粋€不等于0 的元素yi時停止計算, 則min{x1,··· ,xn} = zi; 然后他們轉(zhuǎn)而從右向左解密, 并對解密結(jié)果進(jìn)行解碼, 當(dāng)?shù)玫降谝粋€不等于0 的yj時停止計算, 則max{x1,··· ,xn}=zj.

4.2 方案分析

正確性分析 首先, 在協(xié)議第2 步中, 每個Pi將私有數(shù)據(jù)xi按照方式(4) 構(gòu)造對應(yīng)的長度為l 的數(shù)組Xi, 再將Xi中元素應(yīng)用編碼方式Mij= xijG 編碼到橢圓曲線上并進(jìn)行加密, 最終得到密文數(shù)組E(Mi). 所用編碼方式保證了在應(yīng)用橢圓曲線加密方案進(jìn)行計算時對Xi中的元素也具有加法同態(tài)性.

協(xié)議的第3 步中, 參與者構(gòu)造與編碼矩陣相對應(yīng)的密文矩陣M, 對M 中每一列所有元素求和, 根據(jù)加密算法的加法同態(tài)性, 可得出

協(xié)議的第4 步中, 所有參與者聯(lián)合解密T, 以下是進(jìn)行解密運算的過程

定理2 同時保密計算最大值與最小值的協(xié)議2 在半誠實模型下是安全的.

證明: 對于任意n ?1 個參與者構(gòu)成的合謀者集合是一個最大攻擊(合謀) 者結(jié)構(gòu), 只要對此合謀者結(jié)構(gòu)是安全的, 則對于其他任意合謀者集合都是安全的. 若要證明對于這個合謀者結(jié)構(gòu)是安全的, 則需構(gòu)造相應(yīng)的模擬器S, 使得(1) 式成立. 由于各參與者地位的平等性, 不妨設(shè)P2,··· ,Pn試圖通過合謀來獲取P1的私密數(shù)據(jù)x1的有關(guān)信息, 分為以下兩種情況:

(1) I ={P2,··· ,Pn} 合謀要得到參與者P1的保密數(shù)據(jù)的相關(guān)信息, S 的模擬過程如下:

(a) 給定輸入(I,XI,fI(X)), 即(I,XI,fI(X)) = (I,(x2,··· ,xn),fI(X)), 隨機(jī)選擇一個數(shù)據(jù)x′1∈{z1,z2,··· ,zl}=U, 使得fI(X)=fI(X′), 在這里X′={x′1,x2,··· ,xn}.

(b) 模擬器 S 將 X′中的每個數(shù)據(jù) x′i按照方式 (4) 構(gòu)造為數(shù)組 X?1,X2,··· ,Xn, 再將所有數(shù)組元素編碼到橢圓曲線上得到 n 個編碼數(shù)組 M?1,M2,··· ,Mn, 然后加密得到 n 個密文數(shù)組E(M?1),E(M2),··· ,E(Mn).

(c) 模擬器S 按照步驟3 將密文矩陣中對應(yīng)元素相加, 得到新的密文數(shù)組T?. 然后解密得到橢圓曲線上的點, 進(jìn)一步解碼得到fI(X′).

在協(xié)議2 中

令

因為概率公鑰加密系統(tǒng)是語義安全的, 并且所有參與者合作才能正確解密(即使I 中的所有參與者合謀也無法解密任何密文),所以密文數(shù)組T 與T?是計算不可區(qū)分的,即Tc≡T?. 又由于fI(X)=fI(X′),故有

(2) I ?{P2,··· ,Pn} 合謀要得到P1保密數(shù)據(jù)的相關(guān)信息.

由情況(1) 可知, 當(dāng)I = {P2,··· ,Pn} 時, 因為參與合謀方無法正確解密密文, 所以不能得到任何有關(guān)x1的信息. 那么當(dāng)I ?{P2,··· ,Pn}, 參與合謀方同樣也不能獲得x1的相關(guān)信息(因為I 的任何子集能夠得到的信息都不超過I 能夠得到的信息). 因此在情況(2) 下, 協(xié)議2 也是安全的.

由此可知, 在半誠實模型下協(xié)議2 是安全的.

5 效率分析

本節(jié)對上述兩個最大最小值保密計算方案的效率進(jìn)行分析比較. Paillier 加密算法加密一次需要進(jìn)行2 次模指數(shù)運算, 解密一次需要進(jìn)行1 次模指數(shù)運算. 橢圓曲線上的ElGamal 加密方案加密需要2 次橢圓曲線乘法運算, 解密需要1 次橢圓曲線乘法運算(橢圓曲線上的乘法運算對應(yīng)于ElGamal 加密算法的模指數(shù)運算). 文中協(xié)議1,2 的性能分析見表2.

5.1 計算復(fù)雜性分析

在協(xié)議1 中, 所有參與者都需要將數(shù)組中的每一個元素加密, n 個參與者需要進(jìn)行2nl 次模指數(shù)運算,然后P1對密文數(shù)組C 進(jìn)行解密, 如果最小值在數(shù)組Y 中按順序方向處于第i 位, 最大值在數(shù)組Y 中按逆序方向處于第j 位, 則要進(jìn)行i+j 次模指數(shù)運算. 因此協(xié)議1 總共做了2nl+i+j 次模指數(shù)運算.

協(xié)議2 中所有參與者對數(shù)組中的每一個元素進(jìn)行加密, 需要進(jìn)行2nl 次運算, 然后所有參與者對密文數(shù)組T 進(jìn)行聯(lián)合解密得到數(shù)組Y, 如果最小值在數(shù)組Y 中按順序方向處于第i 位, 最大值在數(shù)組Y 中按逆序方向處于第j 位, 那么需要進(jìn)行i+j 次解密運算. 因此協(xié)議2 的計算復(fù)雜性是O(nl).

5.2 通信復(fù)雜性分析

衡量通信復(fù)雜度的指標(biāo)一般為協(xié)議的通信輪數(shù)或者傳送比特總數(shù). 在安全多方計算中, 通常采用通信輪數(shù)衡量.

在協(xié)議1 中, Pi(i = 1,··· ,n ?1) 將收到的密文數(shù)組E(Xi?1) 與自己擁有的E(Xi) 進(jìn)行運算之后發(fā)送給Pi+1, 在這個過程中需要n ?1 輪通信. 最終, Pn完成運算后將結(jié)果發(fā)送給P1解密, 如果最小值在數(shù)組Y 中按順序方向處于第i 位, 最大值在數(shù)組Y 中按逆序方向處于第j 位, 則Pn需要向P1發(fā)送i+j 輪消息, 所以協(xié)議1 共需要n+i+j ?1 輪通信.

在協(xié)議2 中, 所有參與者構(gòu)造公鑰需要1 輪通信. 加密過程公布E(Mi) 需要1 輪通信. 如果最小值在數(shù)組Y 中按順序方向處于第i 位, 最大值在數(shù)組Y 中按逆序方向處于第j 位, 解密過程需要i+j 輪通信, 共需要i+j+2 輪通信.

性能 協(xié)議1 協(xié)議2計算復(fù)雜性 2nl+i+j O(nl)通信復(fù)雜性 n+i+j ?1 i+j +2安全性 抵抗除P1 外的合謀攻擊 抵抗合謀攻擊

5.3 實驗數(shù)據(jù)分析

為了更清晰地展現(xiàn)方案的可行性和計算效率, 本文使用Java 語言編程測試了執(zhí)行協(xié)議1, 協(xié)議2 所需要的時間.

實驗測試環(huán)境: Windows XP 專業(yè)版32 位操作系統(tǒng), CPU 為Intel(R) Core(TM) i3-2100 CPU @3.10 GHz, 內(nèi)存是2.99 GB. 本文所做模擬實驗均使用Java 語言在MyEclipse 上運行實現(xiàn).

實驗方法: 實驗選取范圍為0–100 的數(shù)據(jù), 參與者人數(shù)分別設(shè)定為2, 4, 6, 8, 10. 為了保證數(shù)據(jù)的準(zhǔn)確性, 本文進(jìn)行10 次模擬實驗測試, 然后對測試結(jié)果求平均值(僅考慮加密與解密過程所耗費的時間, 忽略密文傳輸所需的通信時間). 協(xié)議1 采用Paillier 加密算法, 設(shè)定素數(shù)大小為512 比特. 協(xié)議2 采用橢圓曲線密碼系統(tǒng), 其中參數(shù)p,a 和b 均取256 比特, 私鑰長度最大限值取273 比特. 實驗結(jié)果如圖1 所示.

由圖1 可知保密地同時求解最小值與最大值的執(zhí)行時間隨參與者人數(shù)增長而線性增加. 基于門限解密算法的最大最小值保密計算方案效率高于基于Paillier 加密算法的最大最小值保密計算方案.

5.4 方案比較

一次計算一組隱私數(shù)據(jù)的最大最小值是一個新的保密科學(xué)計算問題, 目前該問題還未被研究. 現(xiàn)有的方法需要對同一組隱私數(shù)據(jù)進(jìn)行編碼的變換并重復(fù)調(diào)用協(xié)議才能分別求出最大值和最小值, 這樣會使協(xié)議的計算效率較低.

文獻(xiàn)[13] 利用編碼和ElGamal 算法實現(xiàn)了最小值的保密計算. 如果要計算最大值, 需要變換編碼方法后再次對數(shù)據(jù)進(jìn)行編碼, 然后調(diào)用協(xié)議. 如果全集的勢為l, 最小值為y, 協(xié)議共需進(jìn)行加密運算nl 次與解密運算y 次, 即進(jìn)行模指數(shù)運算2(nl+y) 次. 若要同時保密計算最大值與最小值, 則需執(zhí)行兩次協(xié)議,顯然, 本文所設(shè)計的協(xié)議計算效率更高.

文獻(xiàn)[14] 所研究問題與文獻(xiàn)[13] 類似. 文獻(xiàn)[14] 使用保密替換的方法解決了最小值的保密計算問題.加密過程所有參與者最多共需要2nl 次模指數(shù)運算, 解密過程進(jìn)行l(wèi)og p 次模指數(shù)運算(p 為GM 加密系統(tǒng)中的大素數(shù)私鑰), 總共需要2nl+log p 次模指數(shù)運算. 若要實現(xiàn)最大值和最小值的保密計算, 同樣需要變換編碼方法并執(zhí)行兩次協(xié)議. 因此本文協(xié)議在計算效率上具有顯著優(yōu)勢.

文獻(xiàn)[15] 使用0-1 編碼方案和NTRU 加密算法在云環(huán)境下保密計算最小值, 每位參與者需要l+1次模指數(shù)運算, 因此共需要n(l+1) 次模指數(shù)運算. 基于最大值問題和最小值問題的對稱性, 改變?nèi)呐判蝽樞蚝拖鄳?yīng)的編碼方式后再次調(diào)用協(xié)議可實現(xiàn)最大值的保密計算. 本文通過一次編碼保密計算最大值和最小值, 在提高計算效率的同時避免了不必要的信息泄露.

文獻(xiàn)[16] 研究的問題是有一個數(shù)據(jù)收集者要利用分散用戶的智能手機(jī)感知有關(guān)數(shù)據(jù), 并以保密的形式獲取這些數(shù)據(jù)的最小值. 平均每位用戶需要進(jìn)行2 log2M 次逐位異或運算, 3 log2M 次比較運算. 數(shù)據(jù)收集者需要進(jìn)行(n ?1)log2M 次逐位異或運算和log2M 次比較運算(其中用戶私有數(shù)據(jù)的范圍為[0,M ?1]). 該解決方案假設(shè)有一個權(quán)威可以為所有參與者生成關(guān)鍵信息(等同于加密密鑰), 并且未考慮權(quán)威和用戶之間的合謀, 這將導(dǎo)致嚴(yán)重的安全問題. 本文考慮的是標(biāo)準(zhǔn)的安全多方計算場景, 沒有可信的第三方, 僅憑借參與者之間的交互完成保密計算, 參與者之間可能合謀.

本文協(xié)議1、協(xié)議2 與文獻(xiàn)[13–16] 的計算效率比較結(jié)果如表3 所示.

協(xié)議 計算復(fù)雜性 通信復(fù)雜性 執(zhí)行協(xié)議次數(shù)協(xié)議1 2nl+i+j n+i+j ?1 1協(xié)議2 O(nl) i+j +2 1文獻(xiàn)[13] 2(nl+y) n+y ?1 2文獻(xiàn)[14] 2nl+log p n 2文獻(xiàn)[15] n(l+1) 3n ?1 2文獻(xiàn)[16] O(n log2 M) log2 M 2

6 保密判斷數(shù)據(jù)是否在區(qū)間內(nèi)

協(xié)議1 與協(xié)議2 解決了最大最小值的保密計算問題, 從而確定了離散數(shù)據(jù)所在的區(qū)間. 在本節(jié)中, 我們以協(xié)議1 使用的編碼方案為基礎(chǔ), 進(jìn)一步設(shè)計了保密判斷隱私數(shù)據(jù)是否在隱私區(qū)間內(nèi)的協(xié)議.

6.1 判斷數(shù)據(jù)是否在區(qū)間內(nèi)的保密計算方案

問題描述 假設(shè)Alice 擁有一個私密數(shù)據(jù)x, Bob 擁有一個私密區(qū)間[y1,y2], 他們希望判斷Alice 的私有數(shù)據(jù)是否在Bob 的私有區(qū)間內(nèi), 而不泄露自己的信息.

基本原理 Alice 首先將私有數(shù)據(jù)x 按照3.1 節(jié)中的方式(4) 編碼成一個數(shù)組X = {x1,x2,··· ,xl},假設(shè)區(qū)間左端的數(shù)據(jù)y1在全集U 中處于第k 位, 區(qū)間右端的數(shù)據(jù)y2在全集U 中處于第m 位, Bob 根據(jù)區(qū)間兩端的數(shù)據(jù)y1和y2在全集U 中的排列位置, 做如下計算

上述事實是我們判斷數(shù)據(jù)是否在區(qū)間內(nèi)的依據(jù), 我們選用具有加法同態(tài)性的Paillier 加密算法來加密數(shù)組, 使得加密后的0 和隨機(jī)數(shù)r 在計算上不可區(qū)分, 從而實現(xiàn)保密地判斷數(shù)據(jù)是否在區(qū)間內(nèi).

協(xié)議3 數(shù)據(jù)是否在區(qū)間內(nèi)的保密判定方案

輸入: Alice 的私有數(shù)據(jù)x, Bob 的私有區(qū)間[y1,y2].

輸出: 是否x ∈[y1,y2].

(1) Alice 使用Paillier 加密算法產(chǎn)生私鑰和公鑰, 并公布公鑰.

(2) Alice 以方式(4) 將自己的數(shù)據(jù)轉(zhuǎn)化為數(shù)組X, 并用公鑰將數(shù)組X 加密為E(X) 發(fā)送給Bob.

(3) Bob 根據(jù)區(qū)間兩端的數(shù)據(jù)y1和y2在全集U 中的位置, 利用加法同態(tài)性做如下計算

然后將E(V) 發(fā)送給Alice.

(4) Alice 用私鑰解密E(V) 得到V. 若V =r, 則數(shù)據(jù)x 在區(qū)間[y1,y2] 內(nèi); 若V =0, 則數(shù)據(jù)x 不在區(qū)間[y1,y2] 內(nèi).

6.2 方案分析

正確性分析 協(xié)議3 的正確性可由6.1 節(jié)中所述的事實2 得到保證.

安全性分析 協(xié)議3 的安全性由Paillier 加密算法的語義安全性得以保證, 本文可通過構(gòu)造滿足式(1)的模擬器證明其安全性, 具體證明過程如下.

定理3 保密判定數(shù)據(jù)是否在區(qū)間內(nèi)的協(xié)議3 在半誠實模型下是安全的.

由此可知, 協(xié)議3 在半誠實模型下是安全的.

7 結(jié)論

在安全多方計算領(lǐng)域, 同時保密計算最大值和最小值問題是一個全新的問題, 在密碼學(xué)理論與隱私保護(hù)實踐中有重要的應(yīng)用, 可以保密地確定離散數(shù)據(jù)所在的區(qū)間. 本文設(shè)計了一種新的編碼方法, 并使用Paillier 加密算法, 橢圓曲線門限密碼系統(tǒng)構(gòu)造了兩個保密計算最大值和最小值的安全而高效的協(xié)議, 進(jìn)一步以此為基礎(chǔ)構(gòu)造了一個解決區(qū)間判定問題的協(xié)議. 本文提出的協(xié)議對于半誠實參與者都是安全的, 且在私有數(shù)據(jù)范圍已知的情況下適用. 今后將進(jìn)一步研究如何在私有數(shù)據(jù)范圍未知的情形下, 進(jìn)行最大值和最小值的保密計算, 以及提出適用于惡意模型的解決方案.