保護私有信息的選擇問題研究.pdf

1、安全多方計算是近年來信息安全領(lǐng)域的研究熱點。在分布式數(shù)據(jù)環(huán)境下，各方需要聯(lián)合完成一項計算任務(wù)，如果各方都需要提供自己的輸入數(shù)據(jù)，同時該輸入又不能被其他參與方所知，這樣的輸入我們稱之為隱私輸入。隱私輸入保護要求下的多方協(xié)同計算協(xié)議即為安全多方計算協(xié)議。安全多方協(xié)議區(qū)別于傳統(tǒng)的密碼學協(xié)議之處是其在信息學安全的框架下解決問題并且不考慮外部攻擊，其主要解決計算各方內(nèi)部的“泄密”問題。
　　安全多方統(tǒng)計是安全多方計算的一個重要組成部分。如果

2、待統(tǒng)計的原始數(shù)據(jù)來源于兩個或更多參與方，各個參與方又不愿意把自己擁有的數(shù)據(jù)直接交付給其他參與方或者第三方，那么完成統(tǒng)計就要用到安全多方統(tǒng)計協(xié)議。目前，安全多方統(tǒng)計已經(jīng)有了一些初步結(jié)論。
　　中位數(shù)和第k小元的安全多方計算是安全多方統(tǒng)計的一個特例，可稱為安全選擇問題。如果需要計算兩方或多方擁有數(shù)據(jù)集合的共同的第k小元，同時又要保護各方擁有的私密數(shù)據(jù)不被其他方所知，我們就需要為之設(shè)計一個安全多方計算協(xié)議。
　　本文針對中位數(shù)和第

3、k小元的安全多方計算展開學習和研究。我們在認真學習和研究目前已有的中位數(shù)和第k小元計算方面的文獻之后，對隱私保護需求下的情況進行了探索，在安全多方計算的基礎(chǔ)思路和協(xié)議支持下，取得了一些成果:
　　1.對于多方中位數(shù)的快速計算，總結(jié)出一個很樸素卻有效的結(jié)論:多個數(shù)列，在其共同的中位數(shù)的前面和后面刪除同樣數(shù)目的元素后，得到的新數(shù)列的中位數(shù)依然是原始多個數(shù)列的中位數(shù)。
　　2.對于隱私保護需求下的中位數(shù)的計算，即安全多方中位數(shù)計算

4、。我們基于上述結(jié)論，結(jié)合秘密比較協(xié)議，通過多輪交互，在保護隱私輸入的前提下，提出了一個兩方和三方中位數(shù)的安全計算協(xié)議。
　　3.中位數(shù)是第k小元的一個特例，如果能求出各方的任意k小元，則最大值、最小值、中位數(shù)以及排序都可以直接得到結(jié)果。我們基于前人思想改進了一個利用中位數(shù)來求取兩方k小元的一個安全計算協(xié)議。我們優(yōu)化了邊界條件并對中位數(shù)進行了細分。
　　4.對于多方第k小元的計算，我們使用“計數(shù)”方法，利用安全多方求和協(xié)議，給

5、出了一個保護隱私的安全計算協(xié)議。首先，我們從前人的安全多方求和方法得到啟示，提出一種隨機的環(huán)形的安全多方求和協(xié)議。接下來利用“計數(shù)”方法來求取多方第k小元。具體做法:首先每一方求取自己的中位數(shù)，接下來聯(lián)合安全計算共同的中位數(shù)，以此中位數(shù)作為劃分樞軸，各方將自己的私有數(shù)列劃分成三部分:小于樞軸的、等于樞軸的、大于樞軸的，然后分別計數(shù)。各方利用安全多方求和協(xié)議聯(lián)合計算各自維持的這三個數(shù)的和，則k一定介于這三個和所構(gòu)成的區(qū)段內(nèi)，通過其位置我們