“工資中位數(shù)問(wèn)題”的方案分析與設(shè)計(jì)*

王鵬宇 張艷碩 李燁龍

北京電子科技學(xué)院，北京市 100070

0 引言

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

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

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

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

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

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

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

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

1.1 平均工資問(wèn)題

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

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

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

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

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

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

2.1 前提條件

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

我們?cè)谖墨I(xiàn)［9］的基礎(chǔ)之上研究這個(gè)問(wèn)題，文獻(xiàn)［9］中有兩個(gè)前提分別如下：

前提1：模型為半誠(chéng)實(shí)模型，每個(gè)人提供自己的工資信息時(shí)不能撒謊。

因?yàn)樵谶@n個(gè)人中，如果有一個(gè)人對(duì)自己的工資數(shù)據(jù)撒謊，那么工資中位數(shù)的計(jì)算就會(huì)在該環(huán)節(jié)出現(xiàn)錯(cuò)誤，那么整個(gè)協(xié)議就會(huì)無(wú)效［9］。

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

也就是說(shuō)，在該協(xié)議中不存在一個(gè)第三方來(lái)協(xié)助計(jì)算，全部的過(guò)程都是只有參與者來(lái)進(jìn)行［9］。

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

2.2 已有解決方案

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

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

（2）Mj（j＝1，2，3，4，5…n）收到M1與M2的數(shù)據(jù)以后進(jìn)行比較，將兩者相減，得出的兩個(gè)結(jié)果（正負(fù)不同）根據(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為負(fù)，則說(shuō)明M1的工資比M2高，反之則M2比M1高。

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

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

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

（7）所有人將自己的工資隨機(jī)分為n－1份，（工資處在中位數(shù)位置的人可以撒謊將工資乘以2 后再隨機(jī)分為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 個(gè)數(shù)據(jù)加和，減去自己的工資后。 將得到的結(jié)果發(fā)給下一個(gè)人，下一個(gè)人收到數(shù)據(jù)后，將數(shù)據(jù)與自己之前收到的n－1 個(gè)數(shù)據(jù)加和，減去自己的工資，將得到的結(jié)果再發(fā)給下一個(gè)人。

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

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

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

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

3.1 存在問(wèn)題

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

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

3.2 問(wèn)題解決思路探討

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

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

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

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

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

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

4 工資中位數(shù)問(wèn)題的改進(jìn)方案

4.1 輔助運(yùn)算方法

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

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

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

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

2）填入后，從Dave 開(kāi)始與堆頂進(jìn)行比較。

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

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

圖1 最小堆排列計(jì)算流程解釋

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

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

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

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

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

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

4.2 具體方案

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

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

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

圖3 方案前期流程圖

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

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

圖4 方案中間流程圖

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

4.3 改進(jìn)方案分析

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

（1）改進(jìn)優(yōu)勢(shì)分析

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

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

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

圖5 方案后期流程圖

（2）方案安全性分析

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

接下來(lái)將進(jìn)行證明改進(jìn)后的方案比方案一更加安全，在這里我們先假設(shè)在只有五個(gè)人的情況下進(jìn)行比較。M1，M2，M3，M4，M5工資分別為1000，1800，1200，1100，1900。 首先用方案一的計(jì)算方法進(jìn)行計(jì)算，M1與M2先進(jìn)行第一輪比較，將自己的工資隨機(jī)分為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ù)這個(gè)數(shù)值和自己的工資數(shù)得到M2的工資，同理M2也可以根據(jù)收到的數(shù)據(jù)得出M1的工資。 這就存在安全風(fēng)險(xiǎn)，進(jìn)行工資比較的雙方工資信息遭到了泄露。

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

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

5 總結(jié)

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

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

但是不可否認(rèn)，本文提出的改進(jìn)方案依舊有著缺陷，因?yàn)樵摲桨附⒃诎胝\(chéng)實(shí)模型基礎(chǔ)上，所以無(wú)法保證在有攻擊者或參與者撒謊的情況下得出正確的工資中位數(shù)結(jié)果，因此在下一步的計(jì)劃中將對(duì)于這個(gè)缺陷進(jìn)行進(jìn)一步的研究，并爭(zhēng)取將其解決。