楊顏璟, 李順東, 杜潤(rùn)萌

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

1 引言

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

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

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

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

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

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

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

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

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

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

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

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

2.1 安全性定義

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

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

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

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

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

對(duì)于一個(gè)函數(shù)f, 如果存在概率多項(xiàng)式時(shí)間算法S, 使得

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

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

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

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

2.2.1 Paillier 加密算法

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

解密

假設(shè)密文

那么

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

Paillier 加密算法具有語(yǔ)義安全性, 即同一個(gè)明文可以加密成多個(gè)不同的密文, 這些密文都是計(jì)算不可區(qū)分的(即無(wú)法知道這些密文是不是同一個(gè)明文對(duì)應(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 為一大素?cái)?shù)).

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

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

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

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

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

然后對(duì)明文編碼點(diǎn)M 解碼, 最終得到m.

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

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

2.3 線性編碼

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

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

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

2.4 門限解密

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

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

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

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

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

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

3.1 基本原理

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

其中

rij∈ZN為不等于0 的隨機(jī)數(shù). 依此方式, Pi擁有的秘密數(shù)據(jù)xi與數(shù)組Xi構(gòu)成一一對(duì)應(yīng)關(guān)系. 對(duì)得到的n 個(gè)數(shù)組X1,··· ,Xn求和, 即將這些數(shù)組的對(duì)應(yīng)元素相加, 得到一個(gè)新的數(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 的順序方向, 第一個(gè)不為0 的元素17 所在的位置在全集U 中對(duì)應(yīng)的元素2 為最小值; 按照數(shù)組Y 的逆序方向, 第一個(gè)不為0 的元素39 所在的位置在全集U 中對(duì)應(yīng)的元素7 為最大值.

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

證明: 因?yàn)閷?duì)于每個(gè)編碼后得到的數(shù)組Xi(i = 1,··· ,n) 來(lái)說(shuō), xi在全集U 中所在的位置對(duì)應(yīng)的元素為隨機(jī)數(shù)rij, 其余位置對(duì)應(yīng)的元素為0, 將數(shù)組Xi(i=1,··· ,n) 對(duì)應(yīng)位置的元素進(jìn)行相加得到數(shù)組Y, 相當(dāng)于在全集中對(duì)最大值和最小值的位置進(jìn)行標(biāo)記, 第一個(gè)不等于0 的元素yi和最后一個(gè)(按照數(shù)組Y 逆序方向?yàn)榈谝粋€(gè)) 不等于0 的元素yj在數(shù)組Y 中所在的位置則為最大值和最小值在全集中所在的位置.上述事實(shí)是我們保密計(jì)算最大值和最小值的依據(jù), 直接這樣做沒(méi)有保密性可言. 要實(shí)現(xiàn)最大最小值的保密計(jì)算需要在密文狀態(tài)下對(duì)明文進(jìn)行運(yùn)算, 并分別從左向右解密得到最小值后再?gòu)挠蚁蜃蠼饷苡?jì)算最大值. 而Paillier 加密算法和橢圓曲線密碼系統(tǒng)均是加法同態(tài)算法, 可實(shí)現(xiàn)保密求和運(yù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 基本最大最小值保密計(jì)算方案(參與者之間有安全信道)輸入: 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) 依次計(jì)算

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

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

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

3.3 方案分析

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

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

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

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

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

(a) 給定輸入(I,XI,fI(X)), 即(I,XI,fI(X)) = (I,(x2,··· ,xi?1,xi+1,··· ,xn),fI(X)), 隨機(jī)選擇兩個(gè)數(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′中的每個(gè)數(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ù)組中對(duì)應(yīng)元素相乘, 得到數(shù)組C?. 然后解密得到fI(X′).

在協(xié)議1 中

令

由于Paillier 加密算法是語(yǔ)義安全的, 對(duì)I 中參與者來(lái)說(shuō), 密文數(shù)組C 與C?是計(jì)算不可區(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} 時(shí), 只有P1擁有私鑰可以解密, 因此參與合謀方得不到私有數(shù)據(jù)x1和xi的相關(guān)信息. 那么當(dāng)I ?{P2,··· ,Pi?1,Pi+1,··· ,Pn} 時(shí), 同樣因?yàn)橹挥蠵1擁有私鑰可以解密, 所以參與合謀方得不到與x1、xi有關(guān)的信息. 即在最大合謀(攻擊者) 結(jié)構(gòu)參與合謀的情況下是安全的, 合謀者為其子集時(shí)也是安全的.

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

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

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

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

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

4.1 具體協(xié)議

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

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

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

(1) P1,··· ,Pn商定一條橢圓曲線Ep(a,b) 及其上的一個(gè)生成元G(要求G 的階L 足夠大), 然后每個(gè)參與者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的每個(gè)元素編碼成為橢圓曲線Ep(a,b) 上的點(diǎn)Mij=xijG, j ∈[1,l], 得到

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

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

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

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

4.2 方案分析

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

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

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

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

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

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

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

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

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

在協(xié)議2 中

令

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

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

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

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

5 效率分析

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

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

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

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

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

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

在協(xié)議1 中, Pi(i = 1,··· ,n ?1) 將收到的密文數(shù)組E(Xi?1) 與自己擁有的E(Xi) 進(jìn)行運(yùn)算之后發(fā)送給Pi+1, 在這個(gè)過(guò)程中需要n ?1 輪通信. 最終, Pn完成運(yùn)算后將結(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 輪通信. 加密過(guò)程公布E(Mi) 需要1 輪通信. 如果最小值在數(shù)組Y 中按順序方向處于第i 位, 最大值在數(shù)組Y 中按逆序方向處于第j 位, 解密過(guò)程需要i+j 輪通信, 共需要i+j+2 輪通信.

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

5.3 實(shí)驗(yàn)數(shù)據(jù)分析

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

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

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

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

5.4 方案比較

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

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

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

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

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

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

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

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

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

基本原理 Alice 首先將私有數(shù)據(jù)x 按照3.1 節(jié)中的方式(4) 編碼成一個(gè)數(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 中的排列位置, 做如下計(jì)算

上述事實(shí)是我們判斷數(shù)據(jù)是否在區(qū)間內(nèi)的依據(jù), 我們選用具有加法同態(tài)性的Paillier 加密算法來(lái)加密數(shù)組, 使得加密后的0 和隨機(jī)數(shù)r 在計(jì)算上不可區(qū)分, 從而實(shí)現(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)性做如下計(jì)算

然后將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é)中所述的事實(shí)2 得到保證.

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

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

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

7 結(jié)論

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