張文芳，張灣灣，王小敏

(西南交通大學(xué) 信息科學(xué)與技術(shù)學(xué)院，四川 成都 611756)

云計算、移動互聯(lián)網(wǎng)、人工智能、物聯(lián)網(wǎng)等現(xiàn)代信息技術(shù)的不斷升級和應(yīng)用普及，為各個實體之間進行數(shù)據(jù)的共享及聯(lián)合計算帶來了極大的便利，使得各個實體不但可以合作共享各自的信息以實現(xiàn)交流互通，還可以方便地利用其他實體的數(shù)據(jù)進行計算以實現(xiàn)數(shù)據(jù)價值最大化。由于不同實體之間進行數(shù)據(jù)聯(lián)合計算的應(yīng)用場景愈發(fā)復(fù)雜化，如果各個實體在未對私有數(shù)據(jù)進行處理的情況下就進行聯(lián)合計算，勢必會存在不同程度的隱私數(shù)據(jù)泄露問題，導(dǎo)致嚴重的后果。因此保護各個實體聯(lián)合計算過程中私有數(shù)據(jù)的機密性和安全性是聯(lián)合計算面臨的一個嚴峻挑戰(zhàn)。

為了解決隱私數(shù)據(jù)的安全共享問題，在保證數(shù)據(jù)機密性的同時實現(xiàn)聯(lián)合計算，國內(nèi)外眾多學(xué)者對安全多方計算（secure multiparty computation，SMC）技術(shù)進行了深入研究。安全多方計算最早由Yao[1]以“百萬富翁問題”提出，即在不泄露雙方參與者具體財富值的情況下對財富大小進行比較，該問題是安全多方計算的一個應(yīng)用實例；并且，該文指出如果陷門置換存在，任何兩方函數(shù)都可以安全地被計算，這標志著安全多方計算的誕生。隨著安全多方計算的發(fā)展，許多新的適用于不同應(yīng)用場景的安全多方計算問題及解決方案被提出，已有的研究主要分為保密的科學(xué)計算[2]、保密的區(qū)間計算[3]、保密的幾何計算[4]、保密的集合運算[5]、保密的數(shù)據(jù)挖掘[6-7]以及其他應(yīng)用問題[8-10]，比如，電子投票相關(guān)問題[11-15]。

在保密的科學(xué)計算方面，對多個數(shù)據(jù)最大（?。┲档谋Ｃ苡嬎氵M行研究是十分重要的，因為它能夠適用于多種應(yīng)用場景，在信息安全實踐中也有很大的實際意義。比如，多個公司進行招標，只有出價最低的公司才能勝出，而其余公司則傾向于不透露自己的招標信息，以避免發(fā)生對公司不利的事件。除此之外，關(guān)于多個數(shù)據(jù)最值的保密計算問題同樣具有十分重要的數(shù)學(xué)意義，可以應(yīng)用于平均值計算場景。比如，在計算平均值的過程中，出于合理性及真實性的考慮，必須忽略這些數(shù)據(jù)的離群值。

多個數(shù)據(jù)的最大（?。┲当Ｃ苡嬎惴桨高€可廣泛應(yīng)用于保密集合運算、保密數(shù)據(jù)挖掘及查詢、保密電子拍賣等實際場景，同時這些算法和協(xié)議還可以作為基礎(chǔ)模塊用于設(shè)計各種更加安全高效的保密招投標、保密選拔推薦、保密優(yōu)化、多方參與的點和區(qū)間關(guān)系的保密判定等安全多方計算協(xié)議。一般要計算最大值和最小值需要對多個數(shù)據(jù)進行兩兩比較或者將該問題轉(zhuǎn)化為排序問題，但這種做法會大大增加計算復(fù)雜度甚至?xí)孤冻畲笾岛妥钚≈抵獾钠渌[私信息。因此，進行最大（?。┲档谋Ｃ苡嬎惴桨秆芯渴呛苡斜匾?。

Shi等[16]利用分片混合和二分查找技術(shù)構(gòu)造了一個可保密計算最大值的保密查詢協(xié)議，但是，該協(xié)議需要一個不可信的數(shù)據(jù)聚合服務(wù)器為每個參與者分配一個基于身份信息的密鑰，并負責(zé)收集數(shù)據(jù)，不能抵抗數(shù)據(jù)聚合服務(wù)器和參與者參與的合謀攻擊。Li等[17]基于加法同態(tài)加密算法和HMAC密鑰管理技術(shù)提出一個時間序列數(shù)據(jù)保密求和協(xié)議，能夠保密計算時間序列數(shù)據(jù)的最大值，但是需要一個可信的權(quán)威服務(wù)器和一個不可信的數(shù)據(jù)聚合者。竇家維等[18]利用ElGamal同態(tài)加密給出了一個最小值保密計算方案，但是由于數(shù)據(jù)編碼方式的原因，該方案并不適用于多數(shù)據(jù)最大值的保密計算，需要將編碼原理進行變換后重新編碼，存在不能同時計算各參與者私有數(shù)據(jù)的最大值和最小值這一缺陷。Zhang等[19]針對不同用戶手機感知到的數(shù)據(jù)進行數(shù)據(jù)收集，在保證數(shù)據(jù)機密性的條件下計算該組數(shù)據(jù)的最小值，但是，該方案需要可信第三方生成用戶加密密鑰，不能抵抗用戶和第三方參與的合謀攻擊。楊曉藝等[20]提出一種新思想，將最小值保密計算問題轉(zhuǎn)換為保密替換問題，在半誠實模型下設(shè)計了一個能夠保密計算最小值的協(xié)議，但是，該方案與文獻[18]方案一樣需要通過兩種編碼方法來分別計算最大值和最小值，存在復(fù)雜度高、安全性低等缺陷。李占利等[21]利用0-1編碼原理及NTRU加密算法構(gòu)造了一個適用于云環(huán)境下的最小值保密計算協(xié)議，通過編碼方式及全集排列順序的改變可以保密地進行最大值的計算，但是同樣不能一次性計算出最大值和最小值。

上述方案都是利用編碼方法解決最大值和最小值問題，但此類方案并不能同時保密計算最大值和最小值。目前可同時求解最大（?。┲档姆桨篙^少。楊顏璟等[22]基于Рaillier同態(tài)加密算法設(shè)計了一個可一次性計算一組保密數(shù)據(jù)最大值和最小值的協(xié)議，但由于解密過程不是聯(lián)合解密，存在不能抵抗解密密鑰持有者參與合謀攻擊的問題。李順東等[23]給出一個惡意模型下可同時求解最大值和最小值的方案，該方案是在惡意模型下設(shè)計的，雖然安全性較高，但由于采用了零知識證明，協(xié)議的整體效率較低。

綜上，現(xiàn)有的大部分安全多方計算協(xié)議存在以下問題：效率低下、需要可信或者不可信的第三方、不能一次性保密計算出最大值和最小值、保密計算結(jié)果由唯一的指定解密密鑰持有者獲取等。為解決上述問題，本文首先提出一種新的隱私數(shù)據(jù)編碼方法，可以對保密數(shù)據(jù)一次編碼后同時計算最大值和最小值，其基本思想是給定一個勢為l的有序數(shù)全集，各參與者據(jù)其所持數(shù)據(jù)在全集中的位置編碼得到長度為l的數(shù)組，各數(shù)組按位相乘后的最左和最右非1數(shù)值所在位置即為最大值和最小值在全集中的位置。

在此基礎(chǔ)上，結(jié)合ElGamal同態(tài)加密算法及門限解密構(gòu)造了一個由各參與者參與且無需可信第三方的可同時求解最大值和最小值的安全高效保密計算協(xié)議。該協(xié)議可以保證所有參與者數(shù)據(jù)的安全性，并且解決了保密計算結(jié)果由唯一的指定解密密鑰持有者獲取的安全瓶頸問題，實現(xiàn)去中心化的目的。最后，基于理想-現(xiàn)實模擬范例證明了所提方案在半誠實模型下能夠抵抗解密密鑰持有者不參與的合謀攻擊。該保密計算協(xié)議還可作為基礎(chǔ)模塊用于設(shè)計更加安全高效的保密數(shù)據(jù)挖掘、保密優(yōu)化、多方參與的點與區(qū)間關(guān)系保密判定等安全多方計算協(xié)議。

1 預(yù)備知識

給出用于構(gòu)造可同時求解最大（?。┲捣桨傅陌踩喾接嬎銋f(xié)議安全性的定義，主要包括安全多方計算的理想模型、半誠實模型以及證明安全多方計算協(xié)議安全性需要用到的理想-現(xiàn)實模擬范例。

1.1 安全多方計算的理想模型

假定存在一個不可攻破的可信第三方TTР，TTР會忠實地執(zhí)行協(xié)議并且不會透露任何隱私信息。各個參與者Pi分別通過安全信道將自己的隱私數(shù)據(jù)xi告訴TTР，由TTР在本地幫助參與方執(zhí)行計算函數(shù)，得出計算結(jié)果fi(x1,x2,···,xn)，再通過安全信道將結(jié)果分發(fā)給對應(yīng)的參與者。協(xié)議執(zhí)行過程中，TTР不會透露除結(jié)果外的任何信息，參與者Pi也無法獲取額外信息。具體模型如圖1所示。

圖1 理想模型Fig.1 Ideal model

1.2 安全多方計算的半誠實模型

半誠實模型又稱被動攻擊模型，是一種重要的安全多方計算模型，該模型下，參與者P1,P2,···,Pn誠實地按照協(xié)議規(guī)則和步驟執(zhí)行，但Pi有可能會記錄計算過程中Pj(i≠j)傳送的中間結(jié)果和協(xié)議的最終輸出結(jié)果，并在協(xié)議執(zhí)行后試圖根據(jù)記錄的這些秘密信息推導(dǎo)出Pj的秘密輸入，也可能將自己的秘密數(shù)據(jù)泄露給攻擊者，這種攻擊稱為被動攻擊，它只發(fā)生在協(xié)議執(zhí)行之后。

1.3 理想-現(xiàn)實模擬范例

安全多方計算的安全性證明主要是通過計算復(fù)雜性進行一種抽象的仿真，即構(gòu)造式證明。理想安全多方計算協(xié)議被認為是安全性最高的，然而現(xiàn)實生活中很難找到一個可以被所有參與者信任的TTР，因此實際中設(shè)計的安全多方計算協(xié)議是無可信第三方的?，F(xiàn)實的安全多方計算協(xié)議通過參與方之間的交互協(xié)同計算功能函數(shù)f(x1,x2,···,xn)。在證明現(xiàn)實模型下安全多方計算協(xié)議安全性過程中，假設(shè)協(xié)議A和協(xié)議B完成同樣的功能，如果攻擊者攻擊協(xié)議A不能比攻擊協(xié)議B獲得更多的信息，那么協(xié)議A至少和協(xié)議B一樣安全[24]。同理，如果攻擊者攻擊現(xiàn)實模型下的一個協(xié)議 π，不比攻擊理想模型下的一個協(xié)議 F獲得更多的信息，那么 π 至少和 F一樣安全。該說法可以形式化地表述為：如果任何現(xiàn)實模型攻擊者都存在一個理想模型攻擊者S（模擬器），對于任何輸入，在現(xiàn)實模型下運行包含攻擊者的協(xié)議 π的全局輸出，它和在理想模型下運行包含攻擊者的協(xié)議 F的全局輸出是計算不可區(qū)分的，那么 π 至少和 F一樣安全。

理想-現(xiàn)實模擬范例是利用仿真建立現(xiàn)實模型和理想模型之間的聯(lián)系，將現(xiàn)實模型的安全規(guī)約到理想模型的安全上。其一般框架是，在模擬器S中分別構(gòu)造理想模型和現(xiàn)實模型?，F(xiàn)實模型中，模擬器內(nèi)部調(diào)用敵手，以誠實參與方的身份與敵手共同執(zhí)行一個真實的兩方協(xié)議；理想模型中，模擬器以敵手的身份與可信第三方TTР一起計算功能函數(shù)f(x1,x2,···,xn)。現(xiàn)實模型中，敵手在協(xié)議執(zhí)行過程中所實施的攻擊，在理想模型中都存在一個敵手實施相同效果的攻擊。模擬器成功完成模擬后，將現(xiàn)實模型中的聯(lián)合輸出與理想模型中的聯(lián)合輸出進行對比，如果二者是計算不可區(qū)分的，則說明在理想模型中可以模擬敵手的可能的實際執(zhí)行，敵手無法區(qū)分現(xiàn)實協(xié)議與理想?yún)f(xié)議，現(xiàn)實協(xié)議是安全的。

2 基于ElGamal同態(tài)加密和門限解密的最大（?。┲当Ｃ苡嬎銋f(xié)議

首先，給出最大（小）值保密計算協(xié)議的計算原理，主要包含各個參與者隱私數(shù)據(jù)的編碼原理和實現(xiàn)隱私數(shù)據(jù)最大值和最小值保密計算的依據(jù)。然后，基于該計算原理結(jié)合ElGamal同態(tài)加密算法及門限解密設(shè)計一個可一次性保密計算最大（?。┲档陌踩喾接嬎銋f(xié)議。

2.1 基本編碼原理

給出一種新的編碼方法，該方法無需兩次編碼便能同時求解n個參與者的最大值和最小值。在該方法基礎(chǔ)上結(jié)合同態(tài)加密即可實現(xiàn)最大（?。┲档谋Ｃ苡嬎恪Ｏ旅嬖敿毥o出該編碼方法的具體步驟。

假設(shè)有n個保密數(shù)據(jù)都在全集中，即xi∈{z1,z2,···,zl}=U，它們分別由n個參與者Pi(i=1,2,···,n)持有，其中z1＜z2＜···＜zl且全集U的勢 |U|=l。

1）每個參與者Pi首先將數(shù)據(jù)xi按照以下方法表示為對應(yīng)的數(shù)組Xi={xi1,xi2,···,xil}，其中：

式中，rij為不等于1的隨機數(shù)，rij∈ZN，且 2 ≤rij＜p1/n，其中p為算法的模數(shù)。

所有參與者按照式（1）得到與自己持有的秘密數(shù)據(jù)xi一一對應(yīng)的數(shù)組Xi，

2）所有參與者對得到的n個數(shù)組X1,X2,···,Xn求積，即將這些數(shù)組對應(yīng)元素相乘，得到一個新數(shù)組：

3）對于新數(shù)組Y={y1,y2,···,yl}，按照從左到右的方向，當(dāng)首次出現(xiàn)yi=rij時，它所在的位置就是最小值在全集U中所在的位置，且該位置的元素值與最小值相等，即 min{x1,x2,···,xn}=zi；按照從右到左的方向，當(dāng)首次出現(xiàn)yj=rij時，所在的位置就是最大值在全集U中所在的位置，且該位置的元素值與最大值相等，即 max{x1,x2,···,xn}=zj。

假設(shè)有4個參與者，其各自擁有的數(shù)據(jù)分別為x1=16,x2=13,x3=18,x4=12， 令U={11,12,···,19,20}，則：

顯然可得：m in{x1,x2,···,xn}=z2=12， max{x1,x2,···,xn}=z8=18。

以上是實現(xiàn)秘密數(shù)據(jù)的最大值最小值保密計算的依據(jù)，正確性說明詳見第3.1節(jié)。直接在明文狀態(tài)下進行運算不能保證數(shù)據(jù)的安全性，為了實現(xiàn)最大值和最小值的保密計算，本文在上述編碼方法的基礎(chǔ)上引入ElGamal同態(tài)加密，詳見第2.2節(jié)。

2.2 最大（小）值保密計算協(xié)議設(shè)計

在第2.1節(jié)的編碼方法的基礎(chǔ)上結(jié)合ElGamal同態(tài)加密和最大門限解密，設(shè)計出可同時求解最大（小）值的保密計算協(xié)議，具體步驟如下：

4）所有參與者由公布的密文可獲取矩陣C：

5）對密文矩陣C的每一列元素進行相乘，得到密文：

6）聯(lián)合解密密文H，解密某個密文Hk=(Hk1,Hk2)時每個參與者需要提供部分解密結(jié)果Vi=(modp)=

具體協(xié)議執(zhí)行過程如圖2所示。

圖2 最大（?。┲当Ｃ苡嬎銋f(xié)議執(zhí)行過程示意圖Fig.2 Schematic diagram of the implementation process of the confidential maximum (minimum) value calculation protocol

3 安全性分析

對第2節(jié)所提基于ElGamal同態(tài)加密和門限解密的最大（小）值保密計算協(xié)議進行正確性及安全性分析，并與現(xiàn)有同類方案進行性能對比。

3.1 正確性證明

定理1 對于n個參與者擁有的數(shù)據(jù)x1,x2,···,xn，均按照式（1）構(gòu)造數(shù)組Xi，將數(shù)組對應(yīng)位置的元素相乘，得到一個新數(shù)組Y={y1,y2,···,yl}。按照從左到右的方向，當(dāng)首次出現(xiàn)yi=rij時，全集U中對應(yīng)位置的元素即為最小值，即 min{x1,x2,···,xn}=zi；按照從右到左的方向，當(dāng)首次出現(xiàn)yj=rij時，全集U中對應(yīng)位置的元素即為最大值，即 max{x1,x2,···,xn}=zj。

證明：因為對于每個參與者按照式（1）編碼后獲得的數(shù)組Xi(i=1,2,···,n) 來說，xi在全集U中所在的位置對應(yīng)的元素為隨機數(shù)rij，其余位置對應(yīng)元素為1；將每個參與者編碼后得到的數(shù)組Xi(i=1,2,···,n)對應(yīng)位置的元素進行相乘得到數(shù)組Y，相當(dāng)于在全集U中對這n個參與者私有數(shù)據(jù)的最大值和最小值位置進行標記，數(shù)組Y從左到右的方向第一個等于隨機數(shù)的元素yi和從右到左的方向第1個等于隨機數(shù)的元素yj的位置則分別為所有參與者私有數(shù)據(jù)最小值和最大值在全集U中所處的位置。證畢。

定理2 在半誠實模型下，基于ElGamal同態(tài)加密和門限解密的最大（?。┲当Ｃ苡嬎銋f(xié)議是正確的。

根據(jù)定理1，按照從左到右的方向解密，當(dāng)首次出現(xiàn)yi=rij時，全集U中對應(yīng)位置的元素為最小值，即min{x1,x2,···,xn}=zi；按照從右到左的方向解密，當(dāng)首次出現(xiàn)yj=rij時，全集U中對應(yīng)位置的元素為最大值，即 max{x1,x2,···,xn}=zj。證畢。

3.2 安全性證明

在安全多方計算中，半誠實協(xié)議的安全性定義如下[25]：

設(shè)f=f({0,1}*)n→({0,1}*)n是概率多項式函數(shù)，如果存在概率多項式時間算法S滿足：

則稱 π為保密計算f的協(xié)議。

定理3 基于ElGamal同態(tài)加密和門限解密的最大（小）值保密計算協(xié)議在半誠實模型下是安全的，且能抵抗合謀攻擊。

證明：在半誠實模型下，考慮任意n-1個參與者合謀的情況，證明協(xié)議的安全性，該結(jié)構(gòu)為最大攻擊者結(jié)構(gòu)，如果可以證明基于ElGamal同態(tài)加密和門限解密的最大（?。┲当Ｃ苡嬎銋f(xié)議對于該最大攻擊者結(jié)構(gòu)是安全的，那么該協(xié)議對于其他任意非最大攻擊者結(jié)構(gòu)都是安全的。

各參與者都是在密文的形式下進行計算，所以，攻擊者只能獲取其他參與者保密信息的密文形式。由于協(xié)議采用的是基于難解的離散對數(shù)困難性問題的ElGamal同態(tài)加密算法，因此攻擊者不能解密獲取其他參與者的保密信息。

由協(xié)議的執(zhí)行過程可知，每個參與者都是通過自己持有的私鑰進行公鑰計算，最后聯(lián)合生成ElGamal同態(tài)加密系統(tǒng)的公鑰，解密過程需要所有參與者共同協(xié)作才能得到正確的輸出結(jié)果。如果有某個參與者不進行聯(lián)合解密，那么就不能正確地將密文解密，所以能抵抗合謀攻擊。

不妨假設(shè)后n個參與者合謀，由于在該協(xié)議中各個半誠實參與者Pi的地位是均等的，所以只需證明P1的保密數(shù)據(jù)是安全的即可。不失一般性，假設(shè)P1是誠實的，最大攻擊者集合為I={P2,P3,···,Pn}，X={x1,x2,···,xn}，P1的私有數(shù)據(jù)x1有兩種情況：

1）m ax(X)=x1或 者 min(X)=x1并 且x1?{x2,x3,···,xn} ，此時如果后n個參與者合謀，x1將完全泄露，這和理想模型下的協(xié)議完全一樣，實際協(xié)議沒有比理想?yún)f(xié)議泄露更多信息，所以協(xié)議是安全的。

2） min(X)＜x1＜max(X) ，此時如果后n個參與者合謀，x1不會泄露，和理想模型下的協(xié)議也完全一樣，實際協(xié)議沒有比理想?yún)f(xié)議泄露更多信息，所以協(xié)議是安全的，證明如下：

利用模擬-范例的方式，通過構(gòu)造滿足式（4）的模擬器S，模擬后n個合謀者在現(xiàn)實模型下的視圖信息，分為以下兩種情況：

①基于以上假設(shè)，最大攻擊者集合為I={P2,P3,···,Pn} ，這n-1 個攻擊者合謀想獲取有關(guān)P1私有數(shù)據(jù)x1的信息。S的模擬過程如下：

S模擬過程中所得的視圖信息如下：

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

②基于以上假設(shè)，I?{P2,P3,···,Pn}想獲取有關(guān)P1私有數(shù)據(jù)的信息。

由情況①可知：當(dāng)I?{P2,P3,···,Pn}時，在執(zhí)行協(xié)議時，I作為一個攻擊者集合，收到的消息只有第2.2節(jié)第3）步P1發(fā)出的C1=E(X1)={C11,C12,···,C1l}和第2.2節(jié)第6）步解密某個密文Hm=(Hm1,Hm2)時收到的部分信息，后n個參與者參與合謀無法獲取關(guān)于保密數(shù)據(jù)x1的有關(guān)信息，因為解密過程需要所有參與者共同協(xié)作才能得到正確的輸出結(jié)果。同理，當(dāng)攻擊者結(jié)構(gòu)為其他任意非最大攻擊者結(jié)構(gòu)時，這些參與者參與合謀同樣無法獲取關(guān)于保密數(shù)據(jù)x1的有關(guān)信息，即當(dāng)I?{P2,P3,···,Pn} 時，合謀者無法獲取有關(guān)P1私有數(shù)據(jù)的信息。

綜上所述，基于ElGamal同態(tài)加密和門限解密的最大（?。┲当Ｃ苡嬎銋f(xié)議在半誠實模型下是安全的，且能抵抗合謀攻擊。證畢。

3.3 安全性對比

選取同類最大（小）值保密計算方案與本文所提方案進行性能對比，分別從同態(tài)特性、是否需要可信第三方、比較最值是多次比較還是一次性比較、是否是聯(lián)合解密等方面進行對比，其對比結(jié)果如表1所示。

表1 方案性能對比分析Tab.1 Comparative analysis of programme performance

由表1可以看出：文獻[17]方案基于加法同態(tài)加密算法保密計算時間序列數(shù)據(jù)的最大值，需要一個可信的權(quán)威服務(wù)器和一個不可信的數(shù)據(jù)聚合者，不能一次性計算一組保密數(shù)據(jù)最大值及最小值，并且解密過程不是聯(lián)合解密。文獻[18]方案用的是乘法同態(tài)，整個協(xié)議執(zhí)行過程中都無需可信第三方，但是存在不能同時計算各參與者私有數(shù)據(jù)的最大值和最小值這一缺陷，同時由于解密過程不是聯(lián)合解密，所以不能抵抗任意合謀攻擊。文獻[22]方案采用的是加法同態(tài)，即無需可信第三方還能一次性計算一組保密數(shù)據(jù)最大值及最小值，但由于解密過程不是聯(lián)合解密，所以存在不能抵抗解密密鑰持有者參與的合謀攻擊這一問題。本文所提方案既無需可信第三方還可一次性保密計算最大值和最小值，同時利用聯(lián)合解密解決了保密計算結(jié)果由唯一指定解密密鑰持有者獲取導(dǎo)致的安全問題。

4 效率分析

對上述基于ElGamal同態(tài)加密和門限解密的最大（?。┲当Ｃ苡嬎銋f(xié)議的效率進行分析，分別從計算復(fù)雜度、通信復(fù)雜度、方案性能對比等方面進行研究。

4.1 計算復(fù)雜度

在基于ElGamal同態(tài)加密和門限解密的最大（?。┲当Ｃ苡嬎銋f(xié)議中，首先，n個參與者都需要生成各自的公鑰最后合作計算獲得聯(lián)合公鑰，所有參與者需要進行 2n次模指數(shù)運算。接著，每個參與者Pi(i=1,2,···,n) 按照式（1）將各自擁有的保密數(shù)據(jù)xi編碼為對應(yīng)的l維數(shù)組。而后，對編碼后的數(shù)組中的每一個元素進行加密，所有參與者需要進行 2nl次模指數(shù)運算。然后，所有參與者聯(lián)合解密密文H，先按照從左到右的方向進行聯(lián)合解密，當(dāng)?shù)玫降?個等于 0的元素yi時終止解密，并令a=min{x1,x2,···,xn}=zi，需要進行ni次模指數(shù)運算；再按照從右到左的方向解密，得到第1個等于 0 的元素yj時終止解密，并令b=max{x1,x2,···,xn}=zj，需要進行n(l-j)次模指數(shù)運算。因此，協(xié)議總共需要 2n(l+1)+n(i+l-j)次模指數(shù)運算。

4.2 通信復(fù)雜度

通信復(fù)雜度指的是一個問題能以多快的速度解決。比如EQ的任何確定型通信協(xié)議無法比發(fā)送所有輸入做得更好，那么這就意味著EQ的復(fù)雜度為O(n)。一般情況下，通常采用一個協(xié)議的通信輪數(shù)、傳送比特數(shù)等來衡量該協(xié)議的通信復(fù)雜度，而針對安全多方計算協(xié)議則往往傾向于選擇通信輪數(shù)這一指標來進行衡量。

在基于ElGamal同態(tài)加密和門限解密的最大（?。┲当Ｃ苡嬎銋f(xié)議中，每個參與者Pi(i=1,2,···,n)共同計算獲得聯(lián)合公鑰K需要進行1輪通信。接著，對數(shù)組Xi={xi1,xi2,···,xil} 進行加密，而后公布密文Ci，需要進行1輪通信。最后，所有參與者聯(lián)合解密密文H，先按從左到右的方向進行聯(lián)合解密，當(dāng)?shù)玫降?個等于隨機數(shù)的元素yi時終止解密，需要進行i輪通信；再按從右到左的方向解密，得到第1個等于隨機數(shù)的元素yj時終止解密，需要進行j輪通信。因此，協(xié)議總共需要i+j+2輪通信。

4.3 性能對比

文獻[18]方案利用ElGamal同態(tài)加密給出一個最小值的保密計算方案，運行整個協(xié)議求出一組數(shù)據(jù)的最小值需要進行 2(nl+y)次模指數(shù)運算，如果需要一次性計算出最大值和最小值則需要進行兩次協(xié)議的執(zhí)行，即需要進行 4(nl+y)次模指數(shù)運算。另外，該協(xié)議執(zhí)行完需要的通信輪數(shù)為n+y-1輪。文獻[20]方案利用GM同態(tài)加密算法給出一個最小值的保密計算方案，但是該方案需要通過兩種編碼方法來分別計算出最大值和最小值，存在復(fù)雜度高、安全性低等缺陷。此外，該協(xié)議總共需要 2nl+lbp次模指數(shù)運算、n輪通信。文獻[21]方案利用0-1編碼原理及NTRU加密算法構(gòu)造一個適用于云環(huán)境下的最小值保密計算協(xié)議，通過編碼方式及全集排列順序的改變可以保密地進行最大值的計算，其基本原理是最大值和最小值問題具有對稱性，整個協(xié)議總共需要進行n(l+1) 次模指數(shù)運算、3n-1輪通信。

本文所提方案既無需可信第三方還可一次性保密計算最大值和最小值，同時利用聯(lián)合解密解決保密計算結(jié)果由唯一指定解密密鑰持有者獲取導(dǎo)致的安全問題。整個協(xié)議總共需要 2n(l+1)+n(i+l-j)次模指數(shù)運算、i+j+2輪通信。

將文獻[18,20,21]方案與本文方案進行效率對比，分別從是否能夠抵抗合謀攻擊、計算復(fù)雜度、通信復(fù)雜度等方面進行研究，結(jié)果如表2所示。

表2 最大（?。┲当Ｃ苡嬎惴桨感蕦Ρ萒ab.2 Comparison of the efficiency of the maximum aximum (minimum) value confidential calculation scheme

表2中，n為參與者人數(shù)，l為全集中的元素個數(shù)，y為最小值，i、j分別為最小值、最大值在全集中所處的位置，p為算法模數(shù)。表2中數(shù)據(jù)表明：雖然文獻[21]方案效率較高，但并不能抵抗合謀攻擊。因此，主要與文獻[18,20]方案進行對比。文獻[18,20]方案的計算復(fù)雜度與n、l、y、p有關(guān)，而本文方案與n、l、i、j有關(guān)。一般情況下，i和j都較小，而n、l、y、p較大，所以總體來看，本文方案具有更低的計算復(fù)雜度。

為了更直觀地看出文獻[18,20]方案與本文方案的差異，分別假設(shè)協(xié)議中n=100，l=50，y=10，i=5，j=7，通過計算不同同態(tài)加密算法在同一個模指數(shù)下的運行時間進行實驗仿真，其中，硬件環(huán)境為Intel Core i5 @CPU at 8300 Hz with 8.00 GB of RAM，軟件環(huán)境為Win 10 64-bit，Python 2.7。文獻[18,20]方案和本文所提協(xié)議計算耗時對比如圖3所示，通信輪數(shù)對比如圖4所示。

圖3 其他方案與本文方案計算開銷對比Fig.3 Comparison of the computational overhead of other solutions and the proposed solution in this paper

圖4 相關(guān)協(xié)議在不同參與人數(shù)情況下的通信輪數(shù)對比Fig.4 Comparison of the number of communication rounds for the relevant protocols with different numbers of participants

由圖3結(jié)果可以看出：文獻[18,20]方案和本文方案在算法模數(shù)為128～256 bit之間時，三者計算開銷相差不大；但當(dāng)模數(shù)大于256 bit時，顯然本文方案的協(xié)議耗時最少。文獻[18]方案的協(xié)議耗時雖然與本文方案耗時相差不大，但是它不能抵抗解密密鑰持有者參與的合謀攻擊，而本文方案可以抵抗任意參與者參與的合謀攻擊。

由圖4結(jié)果可以看出：文獻[18,20]方案中協(xié)議的通信輪數(shù)隨著參與者人數(shù)的增加而線性增加，而本文方案的通信輪數(shù)不變。原因是因為本文方案的通信輪數(shù)只與最大值和最小值在全集中所處位置有關(guān)，而其他方案的通信輪數(shù)與參與人數(shù)相關(guān)。當(dāng)參與者人數(shù)小于或者等于10時，文獻[20]方案中協(xié)議的通信輪數(shù)是所有方案中最少的，但當(dāng)參與者人數(shù)超過14時，本文方案比其他方案具備更高的效率。

5 結(jié) 論

本文研究一組數(shù)據(jù)的最大值和最小值同時求解問題，該問題的解決方案可以作為基礎(chǔ)模塊用于設(shè)計其他安全多方計算協(xié)議，在信息安全實踐中也有著廣泛的應(yīng)用前景。本文以ElGamal同態(tài)加密算法為基石，提出一種安全高效的可同時求解最大（小）值的方案。方案中設(shè)計了一種隱私數(shù)據(jù)編碼方法，能有效克服傳統(tǒng)方案中的無法一次性保密計算最大（小）值問題；另外，采用門限解密技術(shù)可有效保證所有參與者的計算公平性，實現(xiàn)去中心化的目的。同時，對所提方案在半誠實模型下能夠抵抗任意合謀攻擊進行證明。最后，與同類方案進行性能和效率分析對比，表明本文所提方案在一次性保密計算最大值和最小值的同時還能保證各參與方之間的公平性，并且通過仿真測試可以看出所提方案在運算效率方面具有一定優(yōu)越性。如何將最大最小值保密計算協(xié)議應(yīng)用于保密集合運算、保密數(shù)據(jù)挖掘、保密電子拍賣等實際場景有待于進一步研究。