王鵬宇 張艷碩 李燁龍

北京電子科技學院，北京市 100070

0 引言

姚氏百萬富翁問題［5］由華裔計算機科學家、圖靈獎獲得者姚期智［1］先生于1982 年首次提出：存在2 個爭強好勝的富翁Alice 和Bob，他們?nèi)绾卧诓槐┞陡髯载敻坏那疤嵯卤容^誰更富有？ 后來該問題演變成安全多方計算［2］。 隨著網(wǎng)絡技術與計算能力的不斷進步，人們越來越注重個人隱私的保護，如今對用戶隱私的保護成為了計算的基本要求，安全多方計算正是在這樣的環(huán)境下引起人們越來越多的關注。 由百萬富翁問題發(fā)展而來的安全多方計算是指兩個或多個互不信任的用戶在無可信第三方的情況下，如何安全的計算一個約定函數(shù)，同時還要保持各自數(shù)據(jù)的安全性。

安全多方計算的基本概念［2］是“一組參與者希望共同計算某個約定的函數(shù)；函數(shù)的輸入?yún)?shù)有多個；每個參與者提供函數(shù)的一個輸入；每個人都知道這個函數(shù)的值；除了函數(shù)的輸出外，沒有人知道其他參與者輸入的信息”。 一個安全多方計算協(xié)議，如果對于擁有無限計算能力攻擊者而言是安全的，則稱作是信息論安全的或無條件安全的；如果對于擁有多項式計算能力的攻擊者是安全的，稱為是密碼學安全的或條件安全的。 已有的結(jié)果證明了在無條件安全模型下，當且僅當惡意參與者的人數(shù)少于總?cè)藬?shù)的1／3 時，安全的方案才存在。 而在條件安全模型下，當且僅當惡意參與者的人數(shù)少于總?cè)藬?shù)的一半時，安全的方案才存在。

安全多方計算不同于傳統(tǒng)意義上的密碼學，傳統(tǒng)意義上的密碼學主要研究的是在不安全的媒體上提供安全通信的問題，是指在信息傳送過程中防止信息泄露或者被篡改，其加密機制屬于傳統(tǒng)密碼學的范疇。 而安全多方計算主要研究的是系統(tǒng)內(nèi)部各參與方協(xié)作計算時各自數(shù)據(jù)的隱私保護問題，更加偏向于網(wǎng)絡計算。 安全多方計算分為兩種模型，半誠實模型和惡意模型。 半誠實模型是指，所有參與者都是誠實，或者半誠實的，相互之間沒有勾結(jié)，不存在主動攻擊，完全按照協(xié)議的規(guī)程執(zhí)行，不會中途退出或者篡改運行結(jié)果，但是參與者可以保留運算過程中所有的中間結(jié)果，以期望在運行結(jié)束后推斷出其他用戶的輸入信息。 惡意模型則是指有惡意參與者的模型，其中的攻擊者是主動的，可能會不按照協(xié)議的流程執(zhí)行、隨意終止協(xié)議的運行，也可能會修改協(xié)議的中間結(jié)果或者與其他參與方進行勾結(jié)。 本文所討論的針對“工資中位數(shù)”問題的解法主要是在半誠實模型的基礎上進行計算的。

安全多方計算理論［12］主要研究參與者間的協(xié)同計算及隱私信息的保護問題，其特點包括輸入隱私性、計算正確性及去中心化等特性。 在隱私保護被不斷提及的當下，安全多方計算研究取得了極大的進步。 密碼學家研究了各個應用領域中出現(xiàn)的安全多方計算問題，其中包括保密科學計算、保密計算幾何、保密數(shù)據(jù)挖掘等問題。安全多方計算在電子選舉、門限簽名以及電子拍賣等諸多場合發(fā)揮了巨大的作用，成為了這些設計得以實施的密碼學基礎，為實現(xiàn)數(shù)據(jù)的可控共享做出了極大的貢獻。

基于安全多方計算的工資中位數(shù)問題在信息安全實踐中具有重要的實際意義。 在日常生活中，工資無論對于個人或者公司來說都是極為隱秘和重要的數(shù)據(jù)。 如果員工想要知道自己的工資在公司中處于什么樣的水平，就需要計算公司員工的工資中位數(shù)。 由于員工和公司之間通常都簽有保密協(xié)議，因此需要進行工資中位數(shù)問題的保密計算。 除此之外，工資中位數(shù)問題還具有很重要的數(shù)學意義。 如何利用純數(shù)學的知識來進行工資中位數(shù)的保密計算，這需要借助安全多方排序，同時還需要設計一個可靠的中位數(shù)計算函數(shù)來進行計算，達到安全的同時保證其簡易可行。

工資中位數(shù)問題屬于安全多方計算平均工資問題的衍生問題，作為統(tǒng)計學與經(jīng)濟學的結(jié)合，相較于平均工資，更能貼近普通民眾的實際生活水平，本文在研究其解法的同時深入討論該問題背后隱藏的安全性問題，即存在的信息泄露的隱患，并針對該問題設計安全方案。 本文針對工資中位數(shù)問題進行深入分析闡述，借鑒了李燁龍等［9］關于平均工資問題的研究，并結(jié)合了利用最小堆求無序數(shù)組［11］中位數(shù)的算法，引用了石磊等［3］關于信息秘密比較的研究，采用了秘密比較協(xié)議［4］的計算方法，達成了在確保安全性以及用戶工資不被泄露的同時計算工資中位數(shù)的目的。

1 工資中位數(shù)問題

工資中位數(shù)問題在安全多方計算領域?qū)儆谄骄べY問題的一種延伸。 工資中位數(shù)問題來源于平均工資問題，首先我們將對平均工資問題進行簡單介紹。

1.1 平均工資問題

現(xiàn)假設有四名員工Alice、Bob、Carol 和Dave四個人在一家公司工作，他們均簽署了公司的保密協(xié)議，即他們不能向其他人透露自己的工資，但是他們每個人又想了解彼此的工資情況，現(xiàn)場無仲裁者。 在這種情況下，最能夠簡單直白地作為衡量自己工資標準的就是四個人的平均工資，在這種情況下計算四人的平均工資就是安全多方計算平均工資問題。

1.2 工資中位數(shù)問題

本小節(jié)將具體闡述工資中位數(shù)問題，工資對于個人和公司來說是極其隱私的數(shù)據(jù)。 很多公司的工資信息十分的隱蔽。 為了不讓工資信息外泄，員工必須簽署工資保密協(xié)議，每個人不得透漏自己的工資，但是有些員工想了解自己在公司的工資處于什么層次。 安全多方計算中的安全多方排序［6－8］就能解決這個問題，通過一個公認的函數(shù)秘密的計算工資中位數(shù)，每個人就都可以根據(jù)工資中位數(shù)來判斷自己在公司中的層次?，F(xiàn)假設有n名員工在一家公司工作，他們均簽署了公司的保密協(xié)議，即他們不能向其他人透露自己的工資，但是他們每個人又想知道自己的工資在公司處于什么樣的水平，現(xiàn)場無仲裁者。 在這種情況下，只需要一個能夠安全計算出工資中位數(shù)的函數(shù)，就可以計算出工資中位數(shù)，從而每個人都可以根據(jù)工資中位數(shù)來分析自己在公司的工資處于什么水平。

在經(jīng)濟學中，工資中位數(shù)用來描述收入分配差異程度，因為某地區(qū)的人均收入因貧富的差距可遠遠大于收入中位數(shù)，而收入中位數(shù)則可以將這種差距反映出來。 而在統(tǒng)計學中，中位數(shù)［10］是按順序排列的一組數(shù)據(jù)中居于中間位置的數(shù)，代表一個樣本、種群或概率分布中的一個數(shù)值，相較于平均數(shù)，中位數(shù)不易受數(shù)據(jù)中極端數(shù)值的影響，但是當中位數(shù)與安全多方計算結(jié)合到一起，就出現(xiàn)了如何在不暴露參與者信息的情況下計算出中位數(shù)的難題。 下文將根據(jù)上述問題來設計安全多方計算中的“工資中位數(shù)問題”解決算法，分析其中的安全性問題并設計安全方案。

2 工資中位數(shù)問題解決思路

本節(jié)將介紹解決安全多方計算工資中位數(shù)問題的一般設計思路，并在對現(xiàn)有的解決方案與解決思路進行解釋。

2.1 前提條件

為了深入探索該安全多方計算工資中位數(shù)問題的解法，必須先探討一些前提條件，為了尋求方案的一般性，在這里直接討論針對n個人的情況。

我們在文獻［9］的基礎之上研究這個問題，文獻［9］中有兩個前提分別如下：

前提1：模型為半誠實模型，每個人提供自己的工資信息時不能撒謊。

因為在這n個人中，如果有一個人對自己的工資數(shù)據(jù)撒謊，那么工資中位數(shù)的計算就會在該環(huán)節(jié)出現(xiàn)錯誤，那么整個協(xié)議就會無效［9］。

前提2：協(xié)議中沒有可信第三方。

也就是說，在該協(xié)議中不存在一個第三方來協(xié)助計算，全部的過程都是只有參與者來進行［9］。

在上述前提之下，如果存在除參與者之外的敵手對該協(xié)議進行攻擊，那么同樣會出現(xiàn)安全風險。

2.2 已有解決方案

本小節(jié)先給出現(xiàn)有的解題方案（簡稱為方案一），方案的具體步驟如下：

（1）M1與M2先進行第一輪比較。M1與M2將自己的工資隨機分成n－2 份，并分別用Mj（j＝3，4…n）的公鑰加密，用自己的私鑰簽名，并分發(fā)給相應的人。

（2）Mj（j＝1，2，3，4，5…n）收到M1與M2的數(shù)據(jù)以后進行比較，將兩者相減，得出的兩個結(jié)果（正負不同）根據(jù)兩者的大小，將數(shù)據(jù)再用M1，M2的公鑰加密，用自己的私鑰簽名后，發(fā)給M1，M2。 （例如M1的數(shù)據(jù)為123，M2的數(shù)據(jù)為456，則將－333 發(fā)給M1，將333 發(fā)給M2。 ）

（3）M1，M2收到數(shù)據(jù)后，將收到的所有數(shù)據(jù)相加，得出的結(jié)果如果M1為正，M2為負，則說明M1的工資比M2高，反之則M2比M1高。

（4）接下來令M1，M2中大的使用序號1（例如，M2比M1大，則M1與M2交換序號，M1序號為2，M2序號為1）并且交換公鑰與私鑰（即身份交換，M1變?yōu)镸2，M2變?yōu)镸1）。 例如，M1大于M2，則不需要進行身份交換過程，如果M1小于M2，則需要身份交換。 然后繼續(xù)讓M1與M3，M4，M5…Mn重復進行比較過程，以及身份交換過程。

（5）M1完成一輪比較后（此時工資表第一位已經(jīng)排出來，但是理想情況下只有自己知道自己是工資表第一位，非理想情況即，例如Mn的工資為最大的，M1與Mn完成比較后進行了身份交換，此時的M1與Mn都知道了原Mn的工資是最大的）。M2進行下一輪比較，重復比較過程與排序過程。

（6）最后直到Mn－1完成排序后，整個過程結(jié)束。 理想情況下只有每個人自己知道自己的工資表排名，所以只有工資排名處在中位數(shù)位置的，才知道自己的工資為中位數(shù)。

（7）所有人將自己的工資隨機分為n－1份，（工資處在中位數(shù)位置的人可以撒謊將工資乘以2 后再隨機分為n－1 份）（若n為奇數(shù)，則工資中位數(shù)位置是（1／2）*（n ＋1）， 如果n是偶數(shù)， 則工資中位數(shù)位置為 （1／2）*n與（1／2）*n ＋1）。 分別用Mj（j＝1，2，3…n）（除自己以外）的公鑰加密，用自己現(xiàn)在的私鑰（即身份交換后的私鑰）簽名，發(fā)給Mj。

（8）所有人完成分發(fā)后，M1將自己收到的n－1 個數(shù)據(jù)加和，減去自己的工資后。 將得到的結(jié)果發(fā)給下一個人，下一個人收到數(shù)據(jù)后，將數(shù)據(jù)與自己之前收到的n－1 個數(shù)據(jù)加和，減去自己的工資，將得到的結(jié)果再發(fā)給下一個人。

（9）重復此過程，直到所有人都將自己的工資減去。 此時最后一個人得出工資中位數(shù)。（如果n為奇數(shù)，則得出的是工資中位數(shù)，如果為偶數(shù)，則該數(shù)除以2 得到中位數(shù)）

但是此方案存在一種致命的問題，就是信息泄露問題。 在比較大小過程中，比較完成后，比較結(jié)果發(fā)回給M1，M2， 此時M1，M2都知道了對方的工資數(shù)據(jù)，如果兩人中有一個人試圖泄露對方的工資數(shù)據(jù)，那么整個協(xié)議就是失敗的。 而且這個方案與保護工資隱私的原則相悖。

3 工資中位數(shù)問題方案分析

方案一的設計思路表面上可以解決工資中位數(shù)問題，但是該方案在實際操作中還是存在著不可忽視的安全問題，本小節(jié)將揭示其存在的問題，在對其進行分析同時給出問題解決思路。

3.1 存在問題

方案一中，兩名用戶首先將工資數(shù)據(jù)進行拆分加密后發(fā)放給其余人，在此處對工資數(shù)據(jù)進行的加密會保證即便他人將信息截取，也不能解密得出拆分前的結(jié)果。 隨后其他人對收到的兩份數(shù)據(jù)進行比較，將結(jié)果再加密后發(fā)還兩名用戶。但是方案一實際上并沒有滿足安全多方計算中的安全要求，在工資進行兩兩比較時，比較完成后，兩名用戶對收到的所有返回數(shù)據(jù)進行加和得出的是兩名用戶的工資差值。 兩名用戶就會得知對方的工資數(shù)據(jù)信息。 這就存在信息泄露隱患，參與比較的兩個人都會知道對方的工資。

雖然方案一的去中心化和數(shù)據(jù)發(fā)送加密滿足問題需求，同時沒有第三方的參與。 但是存在工資泄露的隱患，如果兩個人中存在一人將對方的工資信息泄露，整個協(xié)議就會暴露出安全隱患。 且方案一的解決步驟過于臃腫繁瑣，不利于理解和計算。

3.2 問題解決思路探討

在對方案一進行安全性分析后，本小節(jié)將針對以上原始方案一中存在的安全問題進行探討并給出改進的方案思路。 我們在對中位數(shù)問題進行研究的時候發(fā)現(xiàn)了另一種更加安全的工資比較方法，該方法有著很高的安全性同時還具有一定的密碼學數(shù)學基礎。 本小節(jié)將根據(jù)此方法衍生的改進思路進行簡單的介紹。

由于方案一安全性無法保障，在工資信息比較環(huán)節(jié)存在工資隱私數(shù)據(jù)泄露問題，但是方案一中對工資信息進行非對稱加密的設計思路以及中位數(shù)計算的思路可以借鑒，因此新方案將沿襲方案一中的“中位數(shù)計算”與“非對稱加密”的方法，使計算過程更加安全可靠，將方案流程上的存在的安全風險進一步降低，增強其安全性。

借助取余數(shù)的方式對工資進行比較。 假設有兩個人A、B，他們的工資分別是a、b（假設工資區(qū)間為1000～2000，且兩人都可以使用計算機輔助計算），協(xié)議開始前，B 生成一對RSA 密鑰。首先，A 選取一個大隨機數(shù)x， A 用B 的公鑰對隨機數(shù)x加密，得到密文m。 A 把m減a的值發(fā)給B，那么B 實際接收到的數(shù)就是m-a。 接下來，B 嘗試用私鑰來恢復x。 由于B 不知道a是多少，于是B 只能枚舉所有1000 到2000 之間的整數(shù)，用私鑰對1000 ～2000 這1001 個數(shù)分別解密，得到的結(jié)果分別為（x1，x2，x3…x1001），解出來的1001 個數(shù)里面，只有一個恰好等于x。

接下來B 選取一個素數(shù)p，這個素數(shù)p應該比1001 略大，B 把解密得到的1001 個數(shù)全部模p，得到（s1，s2，s3…s1001）。 因為B 的工資是b，那么B 把后面（第b ＋1 項到第1001 項）全部加上一個隨機數(shù)α，并亂序處理，然后與素數(shù)p打包后用A 的公鑰加密傳給A。

A 只需要驗證x模p是否等于收到的數(shù)字序列中的某個數(shù)。 如果a ＞b，那么B 發(fā)送的序列中不存在模p與x同余的數(shù)，如果a ＜＝b，那么B 發(fā)送的序列中存在模p與x同余的數(shù)。 A 不可能知道b是多少，因為A 收到的序列是模p后的序列，A 不能把序列還原成模p前的序列，自然也就不能用B 的公鑰返回去計算B 的工資。

這種方案相對比之下更加安全，但是對用戶的計算需求較高。

4 工資中位數(shù)問題的改進方案

4.1 輔助運算方法

本節(jié)討論的工資中位數(shù)問題的改進方案用到了兩種輔助運算方法，一種是秘密比較的運算方法，另一種是利用最小堆求無序數(shù)組中位數(shù)的運算方法。

（1）最小堆排列計算求中位數(shù)

將前（n ＋1）／2 個元素調(diào)整為一個最小堆，對后續(xù)的每一個元素，和堆頂比較，如果小于等于堆頂，就將其丟棄，如果大于堆頂，就用該元素替換堆頂，并繼續(xù)將堆調(diào)整為最小堆。 重復此過程，遍歷全部元素，最終的堆頂就是中位數(shù)［11］。

1）假設Alice 的工資為1000，Bob 的工資為1800，Carol 的工資為1200，Dave 的工資為1100，張三的工資為1900，先建立完全二叉樹，將前三個人的工資依次填入。

2）填入后，從Dave 開始與堆頂進行比較。

3）開始調(diào)整。 根據(jù)性質(zhì)，小的數(shù)字往上移動。

4）最小堆建立完成后，讓后2 位數(shù)字分別與堆頂數(shù)字進行比較如果小于等于，就跳過，接著看下一個數(shù)字。 如果大于，則用該數(shù)字取代堆頂數(shù)字，再將堆調(diào)整至最小堆，接著看下一個數(shù)字。 重復這個步驟，直到將后2 位數(shù)字全部遍歷一遍。 遍歷完成后的堆頂數(shù)字即為中位數(shù)。 最小堆排列計算流程如圖1 所示。

圖1 最小堆排列計算流程解釋

（2）秘密比較協(xié)議

當存在雙方都想在不泄露自身工資信息的情況下比較兩人的工資大小，那么此時就必須有一個秘密比較協(xié)議可以滿足要求。 即在保證工資信息不會泄露的情況下比較工資大小［4］。

1）假設有兩個人A、B，他們的工資分別是a、b（假設工資區(qū)間為1000 ～2000，且兩人都可以使用計算機輔助計算）， 協(xié)議開始前，B 生成一對RSA 密鑰。 首先，A 選取一個大隨機數(shù)x，A 用B 的公開鑰匙給隨機數(shù)x加密，得到密文m。 A 把m減a的值發(fā)給B，那么B 實際接收到的數(shù)就是m-a。 接下來，B 嘗試用私人密鑰來恢復x。 由于B 不知道a是多少，于是B 枚舉所有1000 到2000 之間的整數(shù)，用私鑰對1000 ～2000這1001 個數(shù)分別解密，得到的結(jié)果分別為（x1，x2，x3…x1001），解出來的1001 個數(shù)里面，只有一個恰好等于x。

2）接下來B 選取一個素數(shù)p，這個素數(shù)p應該比1001 大，B 把解密得到的1001 個數(shù)全部模p，得到（s1，s2，s3…s1001）因為B 的工資是b，那么B 把后面（第b ＋1 項到第1001 項）全部加上隨機數(shù)α，然后與素數(shù)p打包后用A 的公鑰加密傳給A。

3）A 只需要計算x模p是否等于序列中的某個數(shù)。 如果a ＞b，那么B 發(fā)送的序列中不存在模p與x同余的數(shù)，如果a ＜＝b，那么B 發(fā)送的序列中存在模p與x同余的數(shù)。 A 不可能知道b是多少，因為A 收到的序列是模p后的序列，A不能把序列還原成模p前的序列，自然也就不能用B 的公鑰返回去計算B 的工資。 秘密比較協(xié)議流程如圖2 所示。

圖2 秘密比較協(xié)議流程解釋

4.2 具體方案

根據(jù)上文的計算方法，在進行深入思考與討論之后，得出了一種結(jié)合了方案一計算中位數(shù)的優(yōu)點，在完全去中心化的同時避免了信息泄露。下面本文將給出改進后的安全多方計算中工資中位數(shù)問題新設計，具體方案步驟如下：

（1） 假設有n個人， 分別是（N1，N2，N3…Nn），工資分別為（A1，A2，A3…An）。 這n個人序號分別為（1，2，3…n）。 那么情況一：n為偶數(shù)，讓序號為1 ～n／2 的人按照順序建立完全二叉樹。 情況二：n為奇數(shù)，讓序號為1 ～（n＋1）／2 的人按照順序建立完全二叉樹。 其余與情況一相同。

（2）序號1 生成RSA 密鑰，公鑰為root1，序號2 生成RSA 密鑰公鑰為left1， 序號3 生成RSA 密鑰公鑰為right1， 序號2 生成RSA 密鑰公鑰為root2， 序號3 生成RSA 密鑰公鑰為root3，序號4 生成RSA 密鑰公鑰為left2，序號5生成RSA 密鑰公鑰為right2， 序號6 生成RSA密鑰公鑰為left3……以此類推直到建立完全二叉樹。

圖3 方案前期流程圖

（3）隨后開始最小堆的建立，從序號1 開始進行秘密比較協(xié)議，序號1 與序號2 進行工資秘密比較，然后再與序號3 進行工資秘密比較，比較完成后，按照最小堆的規(guī)則進行序號交換。 由于秘密協(xié)議只在這3 個人中進行，所以工資信息不會外泄，同樣序號交換的結(jié)果也不會外泄。 然后再從序號2 開始進行秘密比較協(xié)議，序號2，序號4，序號5 之間進行兩兩工資秘密比較，根據(jù)最小堆的規(guī)則進行序號交換。 以此類推直到完成最小堆的建立。

（4）隨后遍歷序號n／2＋1 ～n（奇數(shù)則為（n ＋1）／2＋1 ～n）分別與堆頂序號進行工資秘密比較，如果小于等于堆頂序號，則跳過，如果大于，則該序號與堆頂序號進行交換。 隨后重復2過程，直到序號n／2 ～n都被遍歷，此時堆頂序號的工資就是工資中位數(shù)。 且只有堆頂序號知道自己的工資是中位數(shù)。 每個人重新生成一個臨時的私鑰與公鑰。 所有人將自己的工資隨機分為n－1 份，（工資處在中位數(shù)位置的人可以撒謊將工資乘以2 后再隨機分為n－1 份）分別用Nj（j＝1， 2， 3…n）（除自己以外）的公鑰加密，用自己的私鑰即簽名，發(fā)給Nj（j ＝1， 2，3…n）。

圖4 方案中間流程圖

（5）所有人完成分發(fā)后，N1將自己收到的n－1 個數(shù)據(jù)加和，減去自己的工資后。 將得到的結(jié)果發(fā)給下一個人，下一個人收到數(shù)據(jù)后，將數(shù)據(jù)與自己之前收到的n－1 個數(shù)據(jù)加和，減去自己的工資，將得到的結(jié)果發(fā)給下一個人。 重復直到所有人都將自己的工資減去，最后一個人得出工資中位數(shù)。

4.3 改進方案分析

本小節(jié)將對工資中位數(shù)問題的改進方案進行分析，改進方案與原始方案相比有許多優(yōu)勢，并且方案的安全性和可行性都得到了增強，因此本小節(jié)將主要從改進方案的優(yōu)勢以及方案的安全性這兩個方面進行分析。

（1）改進優(yōu)勢分析

改進思路的目的是在具有隱私性、計算正確性及去中心化的特性的同時具有簡單的原理和較強的可行性。 方案一實際上并沒有滿足安全多方計算中的安全要求，并且存在信息泄露隱患，參與信息秘密比較的兩個人都會知道對方的工資。 在信息秘密比較環(huán)節(jié)存在工資隱私數(shù)據(jù)泄露問題，但是方案一中的對工資信息進行公私鑰加密的設計思路以及中位數(shù)計算的思路可以借鑒。

與方案一進行對比，改進方案采取的加密措施是在加密時使用非對稱密碼算法，甲選取一個隨機數(shù)用乙的公鑰進行加密，隨后將加密的結(jié)果減去自己的工資然后再發(fā)給乙，乙會用自己的私鑰進行解密，但是解密的結(jié)果并不是甲選的隨機數(shù)，于是乙就會枚舉工資區(qū)間，并對所有數(shù)進行解密。 隨后乙會再選一個隨機數(shù)m， 然后讓所有數(shù)都模m， 隨后將結(jié)果發(fā)給甲，甲會進行對比，從而得出兩人工資比較的結(jié)果。

這里相當于信息在公開信道中進行加密傳輸以及信息在密態(tài)下的秘密比較，在雙方隱私?jīng)]有被泄露的同時，將信息傳遞給對方，然后對雙方的工資信息進行比較，再通過最小堆排列計算求中位數(shù)的方式，進行對工資中位數(shù)的計算。

圖5 方案后期流程圖

（2）方案安全性分析

由于方案一存在的問題是安全性得不到保障，兩名用戶在進行工資數(shù)據(jù)信息比較時，會先將工資數(shù)據(jù)進行拆分，然后再進行加密后發(fā)給其他人。 在此處對工資數(shù)據(jù)進行的加密雖然會保證信息在被截取的情況下，截獲者也不能解密得出拆分后的結(jié)果。 但是在其他人對收到的兩份數(shù)據(jù)進行大小比較后，將結(jié)果再加密然后發(fā)回兩名用戶后，兩名用戶會對收到的信息進行比較，信息比較完成時，兩名用戶會對收到的所有返回數(shù)據(jù)進行加和得出雙方的工資差值，于是兩名用戶就會得知對方的工資數(shù)據(jù)信息。

接下來將進行證明改進后的方案比方案一更加安全，在這里我們先假設在只有五個人的情況下進行比較。M1，M2，M3，M4，M5工資分別為1000，1800，1200，1100，1900。 首先用方案一的計算方法進行計算，M1與M2先進行第一輪比較，將自己的工資隨機分為n－2 份，即3 份，并分別分發(fā)給M3，M4，M5。 下面M3，M4，M5將比較后得到的數(shù)據(jù)發(fā)給M1，M2那么M1得到的數(shù)據(jù)為－800，M2得到的數(shù)據(jù)為800，這表示M1的工資比M2小800，那么M1就可以根據(jù)這個數(shù)值和自己的工資數(shù)得到M2的工資，同理M2也可以根據(jù)收到的數(shù)據(jù)得出M1的工資。 這就存在安全風險，進行工資比較的雙方工資信息遭到了泄露。

下面我們再使用改進后的方案進行計算，首先讓M1，M2，M3的工資數(shù)據(jù)生成最小堆，具體方法在上文中已經(jīng)描述，這里就不多贅述。 其中在進行工資比較時使用的方法是上文中的秘密比較協(xié)議［4］主要運用的計算方法有數(shù)字取余和RSA 算法加密。 而且在進行工資比較時，是對加密后的數(shù)據(jù)進行比較，在私鑰沒有泄露的情況下，工資信息是不會泄露的。 所以安全性相較于方案一可以得到有效的保障。

改進方案的流程設計沿襲方案一的“中位數(shù)計算”與“公私鑰加密”的方法，達到更加安全可靠的效果，將方案流程上的風險進一步降低，增加其安全性。 與方案一進行對比，改進方案保證了完全的去中心化，并且利用數(shù)字取余，增強了安全性，保證了數(shù)據(jù)的安全可靠，同時因為頻繁對工資數(shù)據(jù)進行公私鑰加密，減小了數(shù)據(jù)在傳輸過程中發(fā)生信息泄露的可能性。 同時改進方案設計原理較為簡單，只是操作流程稍微復雜，而且極大地增強了可行性與安全性，但是由于方案中存在枚舉過程與取余過程，所以計算量較大。

5 總結(jié)

隨著現(xiàn)代密碼學的不斷發(fā)展，安全多方計算理論在信息安全領域以及密碼保密領域起到了越來越大的作用。 隨著人們對個人隱私和信息安全的關注度逐漸提高，對于安全多方計算的安全性、隱私性和去中心化程度的要求會越來越高。 本文所探討的工資中位數(shù)問題就是在這種大環(huán)境下的產(chǎn)物。 工資中位數(shù)又稱收入中位數(shù)，是指用統(tǒng)計學上中位數(shù)的概念來衡量某地區(qū)普通民眾的收入水平，相比較于人均收入，收入中位數(shù)更貼近普通民眾的實際生活水平，因為某地區(qū)的人均收入因貧富的差距可遠遠大于收入中位數(shù)，而收入中位數(shù)則可以將這種差距反映出來。 中位數(shù)算出來可避免極端數(shù)據(jù)，代表著數(shù)據(jù)總體的中等情況。 例如，一個公司內(nèi)部可能基層與高層之間收入差距較大，這時如果要衡量公司內(nèi)部的收入水平，就不能單純的采取計算工資平均數(shù)的方式。

本文對已有的安全多方計算中工資中位數(shù)問題的問題解決思路進行了分析，發(fā)現(xiàn)其隱藏的安全隱患，取長補短設計出原始方案雖然解決了工資中位數(shù)問題，但是其安全性并沒有得到保障。 于是在已有問題解決思路以及原始思路的基礎上，對現(xiàn)有的安全多方計算中工資中位數(shù)問題的原始解決方案進行了深入解讀分析，發(fā)現(xiàn)其隱藏的安全隱患，取長補短設計新方案，解決了原有的工資隱私信息數(shù)據(jù)泄露問題，其創(chuàng)新點主要有，利用數(shù)字取余進行密態(tài)數(shù)字比較，利用最小堆的特性進行中位數(shù)的計算。 同時新方案設計原理簡單，可行性高，適用于工資中位數(shù)或者其他中位數(shù)計算。

但是不可否認，本文提出的改進方案依舊有著缺陷，因為該方案建立在半誠實模型基礎上，所以無法保證在有攻擊者或參與者撒謊的情況下得出正確的工資中位數(shù)結(jié)果，因此在下一步的計劃中將對于這個缺陷進行進一步的研究，并爭取將其解決。