保護(hù)私有信息的選擇問題研究.pdf

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

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

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

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

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