佟丹妮，申德榮，韓姝敏，聶鐵錚，寇 月，于 戈

東北大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，沈陽(yáng) 110819

1 引言

當(dāng)今社會(huì)，鏈接來(lái)自多方的大型數(shù)據(jù)庫(kù)記錄的需要日益增加，鏈接的同時(shí)要求保護(hù)存儲(chǔ)在這些數(shù)據(jù)庫(kù)中實(shí)體的隱私。為此，呈現(xiàn)出了對(duì)PPRL（privacypreserving record linkage）的研究，即不同機(jī)構(gòu)數(shù)據(jù)庫(kù)間的記錄鏈接需要滿足下述要求：第一，記錄中的敏感信息不能透露給記錄所有者以外的其他參與方；第二，攻擊方不能獲取這些敏感數(shù)據(jù)。PPRL技術(shù)可以使數(shù)據(jù)需求者只在數(shù)據(jù)庫(kù)中獲取其需要的某些記錄的部分屬性，來(lái)實(shí)現(xiàn)隱私保護(hù)下數(shù)據(jù)整合的目的。當(dāng)前PPRL的研究領(lǐng)域主要包括醫(yī)療保健、政府服務(wù)、犯罪檢測(cè)以及商業(yè)應(yīng)用等。例如，醫(yī)藥研究人員為調(diào)查新藥物的不良反應(yīng)，需要整合來(lái)自不同醫(yī)院、診所和藥房的數(shù)據(jù)，在該項(xiàng)研究中，研究人員只獲取使用該新藥后患者表現(xiàn)出的癥狀，而不知道患者的其他信息。又如，一個(gè)國(guó)家的犯罪調(diào)查單位需要利用執(zhí)法機(jī)構(gòu)、互聯(lián)網(wǎng)服務(wù)提供商和金融機(jī)構(gòu)等單位的國(guó)家數(shù)據(jù)庫(kù)中的機(jī)密數(shù)據(jù)，采用PPRL技術(shù)，只獲取鏈接上的記錄對(duì)應(yīng)的人員身份信息（如某些可疑人員的身份信息），而不必獲取全部數(shù)據(jù)，這將大大減少隱私泄露的風(fēng)險(xiǎn)。

PPRL技術(shù)作為記錄鏈接技術(shù)的一個(gè)分支研究，主要包括分塊和匹配兩個(gè)階段。在分塊階段，將相似記錄劃分在同一分塊內(nèi)，以此減少生成的“候選記錄組”數(shù)量。在匹配階段，應(yīng)用相似度函數(shù)對(duì)每個(gè)候選記錄組進(jìn)行計(jì)算，將候選記錄組歸類為匹配記錄組或不匹配記錄組。但不同于傳統(tǒng)的記錄連接，PPRL的兩個(gè)階段中都需要考慮額外的隱私保護(hù)需求。

然而現(xiàn)有的PPRL分塊方法[1-5]均不能使PPRL同時(shí)達(dá)到高查全率和高查準(zhǔn)率，主要源自于如下兩方面：一方面，分塊后還會(huì)生成過(guò)多真實(shí)情況下并不匹配的候選記錄組，造成額外的計(jì)算代價(jià)；另一方面，分塊后損失真實(shí)匹配的記錄組，未對(duì)其進(jìn)行匹配計(jì)算。而已有PPRL中的匹配方法大多適應(yīng)于兩個(gè)數(shù)據(jù)方間的記錄鏈接，而多個(gè)數(shù)據(jù)方間的匹配方法[6-10]均不能同時(shí)達(dá)到強(qiáng)隱私性和高效性。強(qiáng)隱私保護(hù)記錄鏈接可完全防止攻擊方的攻擊，而現(xiàn)有的多方強(qiáng)隱私保護(hù)下的匹配方法均具有很高的匹配計(jì)算代價(jià)，導(dǎo)致匹配時(shí)間過(guò)長(zhǎng)，使其不適用于大數(shù)據(jù)環(huán)境下的記錄鏈接。

針對(duì)已有工作的不足，本文提出了一種多方強(qiáng)隱私保護(hù)記錄鏈接方法（multi-party strong-privacypreserving record linkage method，MP-SPPRL），其在大數(shù)據(jù)環(huán)境下同時(shí)具有高查全率、高查準(zhǔn)率和高效性。本文的主要貢獻(xiàn)有：

（1）提出了一種LSH（locality sensitive Hashing）結(jié)合后綴的二次分塊方法，根據(jù)LSH分塊后的分塊分散度設(shè)定后綴分塊的后綴長(zhǎng)度，使二次分塊在保證MP-SPPRL高查全率的前提下提高查準(zhǔn)率。

（2）提出了一種基于滑動(dòng)窗口的多方分塊合并方法，提高鏈接的容錯(cuò)率，進(jìn)一步保證MP-SPPRL的高查全率。

（3）設(shè)計(jì)了一種基于SMC的可伸縮多方記錄匹配算法，通過(guò)縮減同態(tài)加密記錄數(shù)量和提前終止不可能匹配的候選記錄組的距離計(jì)算，降低匹配的時(shí)間代價(jià)，使該算法適用于大數(shù)據(jù)環(huán)境下。

（4）通過(guò)實(shí)驗(yàn)證明，本文提出的二次分塊方法可以同時(shí)保證MP-SPPRL的高查全率和高查準(zhǔn)率，提出的匹配算法相較于已有的利用SMC的匹配方法更高效。

2 相關(guān)工作

在PPRL研究領(lǐng)域，文獻(xiàn)[11]指出許多分塊方法已經(jīng)被采用。Al-Lawati等人[12]首次把標(biāo)準(zhǔn)分塊技術(shù)引入PPRL，具有相同BKV（block key value）的記錄被分到同一塊內(nèi)，而分塊屬性將影響生成的候選記錄組的質(zhì)量和數(shù)量。基于排序的分塊算法[3]根據(jù)分塊參數(shù)排序所有記錄，并沿著已排序記錄列表滑動(dòng)一個(gè)窗口，所有出現(xiàn)在同一個(gè)窗口中的記錄被放置在同一分塊內(nèi)，窗口大小決定分塊大小以及每個(gè)記錄將被放置在多少個(gè)分塊內(nèi)。Vries等人[2]介紹了基于后綴數(shù)組的分塊方法，其基本思想是將記錄的BKV及其后綴插入到基于倒排索引和字母順序的列表中，按其對(duì)記錄進(jìn)行分塊。嵌入式分塊方法[3]使用一組參考集來(lái)定義嵌入空間，數(shù)據(jù)方通過(guò)計(jì)算他們的記錄和參考集內(nèi)記錄之間的距離向量來(lái)嵌入記錄到該空間，如果記錄相似，它們與嵌入空間中參考記錄的距離向量也會(huì)相似。LSH分塊方法[4]是一種高效并廣泛使用的大數(shù)據(jù)分塊方法，它通過(guò)獨(dú)立且隨機(jī)地從哈希函數(shù)集合中選擇函數(shù)來(lái)映射數(shù)據(jù)，這些哈希函數(shù)對(duì)距離度量是局部敏感的，如果用相同函數(shù)來(lái)哈希兩個(gè)實(shí)體，產(chǎn)生相同結(jié)果的概率取決于它們的距離。

由于Bloom Filter可以保持屬于不同數(shù)據(jù)集的原始記錄字符串之間的距離（相似度），它是PPRL中廣泛應(yīng)用的編碼方式。在Bloom Filter上對(duì)記錄進(jìn)行LSH分塊是一種流行的方法。Durham[13]首先提出了基于Bloom Filter的LSH隱私分塊方法，并通過(guò)實(shí)驗(yàn)證明了LSH方法的高查全率。Karapiperis和Verykios[4]提出了利用LSH函數(shù)分塊的PPRL框架，并比較了三種類型的LSH函數(shù)，其中Hamming-based LSH表現(xiàn)最好，可以高效地生成候選記錄對(duì)。在多方分塊方面，Ranbaduge等人[14]提出了基于LSH的多方PPRL分塊方法。雖然LSH分塊方法在PPRL的查全率方面表現(xiàn)優(yōu)異，但其查準(zhǔn)率過(guò)低，會(huì)造成后續(xù)過(guò)多不必要的匹配計(jì)算。

在PPRL匹配方法研究中，目前的研究大多數(shù)是兩個(gè)數(shù)據(jù)方間的記錄匹配，沒(méi)有考慮到多個(gè)數(shù)據(jù)方參與可能。在少數(shù)多方匹配問(wèn)題研究中，第一個(gè)方法由Quantin等人提出[15]，借助第三方來(lái)比較記錄的哈希編碼值，以此對(duì)多個(gè)數(shù)據(jù)方的記錄進(jìn)行匹配。文獻(xiàn)[16]提出了一種結(jié)合動(dòng)態(tài)閾值、檢查機(jī)制和安全合計(jì)的多方近似匹配方法。但這兩種方法均不能完全防止攻擊方的攻擊。SMC（secure multi-party computation）[17]是一種足夠安全且計(jì)算準(zhǔn)確的多方計(jì)算方法，能夠保證多方PPRL的強(qiáng)隱私性，即能夠在某一數(shù)據(jù)方與攻擊方串通的情況下保護(hù)鏈接的隱私性。O’Keefe等人[6]提出了基于SMC的方法，在特定記錄傳輸協(xié)議下完成匹配，此方法在實(shí)現(xiàn)絕對(duì)安全的同時(shí)也會(huì)導(dǎo)致極高的時(shí)間代價(jià)。類似地，Vatsalan等人[10]設(shè)計(jì)的基于SMC的多方匹配算法也存在時(shí)間代價(jià)大的不足。已有的基于SMC的匹配方法均不能實(shí)現(xiàn)可伸縮的PPRL，不適用于大數(shù)據(jù)環(huán)境下。

針對(duì)LSH分塊方法查準(zhǔn)率低的問(wèn)題，本文提出的LSH結(jié)合后綴的二次分塊方法，在損失少量查全率的情況下，大幅度提高了查準(zhǔn)率，再通過(guò)保證鏈接容錯(cuò)率的基于滑動(dòng)窗口的分塊合并方法生成候選記錄組。針對(duì)SMC匹配方法存在計(jì)算代價(jià)大的問(wèn)題，本文設(shè)計(jì)了一種適合MP-SPPRL的基于SMC的可伸縮多方記錄匹配算法，通過(guò)縮減同態(tài)加密記錄數(shù)量和提前終止距離計(jì)算機(jī)制改善了SMC匹配方法時(shí)間代價(jià)大的問(wèn)題，可以在大數(shù)據(jù)情況下進(jìn)行MPSPPRL，保證強(qiáng)隱私性同時(shí)有效控制鏈接時(shí)間。

3 問(wèn)題定義

定義1（MP-SPPRL） 對(duì)于 來(lái)自n個(gè)數(shù)據(jù)方P1,P2,…,Pn的數(shù)據(jù)集D1,D2,…,Dn，識(shí)別出n個(gè)數(shù)據(jù)集中表示同一真實(shí)實(shí)體的記錄組，同時(shí)要求沒(méi)有任何數(shù)據(jù)方的私密信息泄露給鏈接過(guò)程中的其他數(shù)據(jù)方和額外參與方Pn+1。

定義2（Bloom Filter序列）對(duì)記錄屬性值Bloom Filter編碼后得到的由0和1構(gòu)成的序列。每條記錄對(duì)應(yīng)兩個(gè)由所屬數(shù)據(jù)方對(duì)記錄編碼得到的Bloom Filter序列，分別是表示記錄分塊屬性值的bf和表示匹配屬性值的BF，所有Bloom Filter序列的長(zhǎng)度均為L(zhǎng)。

在進(jìn)行分塊前，從n個(gè)數(shù)據(jù)方共同擁有的屬性中選取出分塊屬性和匹配屬性，需要各數(shù)據(jù)方用相同的函數(shù)各自對(duì)記錄進(jìn)行Bloom Filter編碼。

定義3（候選記錄組）由n條分別來(lái)自n個(gè)數(shù)據(jù)方的相似記錄r1,r2,…,rn的編號(hào)組成的n元組，需要計(jì)算此n條記錄相互之間的距離，判斷此n條記錄是否表示同一實(shí)體。

本文設(shè)計(jì)的MP-SPPRL流程如圖1所示。首先，各數(shù)據(jù)方對(duì)其數(shù)據(jù)集Bloom Filter編碼；其次，數(shù)據(jù)方各自對(duì)其數(shù)據(jù)集進(jìn)行二次分塊；接著，一個(gè)額外的參與方Pn+1合并各數(shù)據(jù)方的相似分塊，在合并后形成的最終分塊內(nèi)生成候選記錄組；最后，n個(gè)數(shù)據(jù)方和Pn+1共同對(duì)候選記錄組進(jìn)行匹配，得到匹配記錄組集合M。

4 LSH結(jié)合后綴的二次分塊方法

4.1 二次分塊模型

二次分塊是指在LSH分塊的基礎(chǔ)上進(jìn)行后綴分塊。分塊過(guò)程中各數(shù)據(jù)方的記錄不會(huì)傳遞給其他數(shù)據(jù)方，可確保分塊階段隱私性。傳統(tǒng)LSH方法不能有效地控制分塊內(nèi)記錄的數(shù)量，會(huì)生成較多實(shí)際并不匹配的候選記錄組，導(dǎo)致查準(zhǔn)率較低。本文在LSH方法生成的分塊上進(jìn)行后綴分塊，生成新的分塊，相較于LSH分塊方法提高查準(zhǔn)率，同時(shí)具有LSH方法查全率高和可以對(duì)大型數(shù)據(jù)集快速劃分的特點(diǎn)。

LSH分塊：多個(gè)數(shù)據(jù)方確定J組一致的Hash函數(shù)Hj,j=1,2,…,J,每組Hj由K個(gè)哈希函數(shù)構(gòu)成，k=1,2,…,K。對(duì)于每組Hj,n個(gè)數(shù)據(jù)方各自用其進(jìn)行LSH分塊，將每條記錄劃分到一個(gè)分塊內(nèi)。方法是用Hj對(duì)記錄的bf進(jìn)行哈希映射，得到長(zhǎng)度為K的向量即hash key，向量值相同的記錄被分到同一LSH分塊內(nèi)。選擇J組函數(shù)是為了避免因表示同一實(shí)體的記錄形式不一致而造成候選記錄組損失的情況。

Fig.1 MP-SPPRL process圖1 MP-SPPRL流程圖

后綴分塊：對(duì)于每組通過(guò)Hj生成的LSH分塊，分別利用x種不同長(zhǎng)度(lmin,lmin+1,…,lmin+x-1)的后綴對(duì)每個(gè)LSH分塊進(jìn)行x次后綴分塊，每個(gè)LSH分塊內(nèi)bf后綴值相同的記錄被分到同一個(gè)分塊內(nèi)，則二次分塊后，一條記錄會(huì)出現(xiàn)在J×x個(gè)分塊內(nèi)。

Fig.2 Double blocking process圖2 二次分塊流程圖

二次分塊后，一個(gè)分塊用一個(gè)簽名＜id，LSH-key，suffix＞表示，其中id是分塊編號(hào)，LSH-key是LSH分塊過(guò)程中對(duì)應(yīng)的向量值，suffix是后綴分塊過(guò)程中對(duì)應(yīng)的后綴值。各數(shù)據(jù)方將代表其分塊信息的簽名及各分塊內(nèi)記錄編號(hào)傳遞給額外的參與方Pn+1。

本文利用Hamming LSH方法及其對(duì)應(yīng)的Hash函數(shù)hjk(bf)=bf[l]，函數(shù)映射得到的哈希值為bf的第l個(gè)位置的值，l是從區(qū)間[0,L)中隨機(jī)選取的。如圖2所示，LSH分塊表示的是一組由4個(gè)hjk組成的Hash函數(shù)Hj對(duì)n=3個(gè)數(shù)據(jù)方記錄的分塊過(guò)程，選擇的4個(gè)哈希函數(shù)的l分別是1、3、5、7，如P1中的第一條bf通過(guò)Hj得到的向量即為＜1,0,1,1＞。在后綴分塊過(guò)程中，后綴長(zhǎng)度為2，P1的第一個(gè)LSH分塊包含兩條記錄，它們長(zhǎng)度為2的后綴值分別是01和11，于是后綴分塊后它們屬于不同的分塊。圖2僅為利用一組哈希函數(shù)和一種長(zhǎng)度后綴的二次分塊過(guò)程。

Fig.4 Relationship of precision and lmin圖4 查準(zhǔn)率與最小后綴長(zhǎng)度關(guān)系圖

4.2 基于LSH分塊分散度的后綴長(zhǎng)度確定

4.2.1 后綴長(zhǎng)度對(duì)MP-SPPRL查全率和查準(zhǔn)率的影響

圖3和圖4說(shuō)明了二次分塊中最小后綴長(zhǎng)度lmin(x=2)與MP-SPPRL查全率和查準(zhǔn)率之間的關(guān)系。LSH1+suffix和LSH2+suffix是對(duì)同一數(shù)據(jù)集采用不同的函數(shù)進(jìn)行LSH分塊的兩種二次分塊，lmin為0時(shí)等同于只進(jìn)行LSH分塊，lmin大于0時(shí)為進(jìn)行LSH分塊和后綴分塊的二次分塊。在圖3和圖4中，隨著lmin增加，查全率下降緩慢，查準(zhǔn)率上升迅速。當(dāng)lmin達(dá)到15后，LSH1+suffix的查全率和查準(zhǔn)率都趨于平穩(wěn)，則對(duì)于此二次分塊應(yīng)選擇的lmin為15。而LSH2+suffix對(duì)應(yīng)的二次分塊適合的lmin為10?？梢?，不同的LSH分塊集群適合不同的后綴長(zhǎng)度。

4.2.2 基于信息熵的分塊分散度度量模型

本文引入分塊分散度度量來(lái)確定后綴分塊的后綴長(zhǎng)度。在LSH分塊后，n個(gè)數(shù)據(jù)方記錄構(gòu)成LSH分塊集群，可依據(jù)表示集群分塊內(nèi)記錄差異程度的分塊分散度確定后綴長(zhǎng)度。分散度足夠低說(shuō)明LSH分塊方法已經(jīng)能夠有效地對(duì)記錄進(jìn)行劃分，若繼續(xù)劃分會(huì)造成真實(shí)匹配記錄組的損失。反之，還可繼續(xù)劃分。二次分塊時(shí)LSH分塊集群的分散度越高，應(yīng)選取越大的后綴長(zhǎng)度。

本文提出基于信息熵的分塊分散度度量模型：?jiǎn)螇K分散度和整體分散度兩類。單塊分散度由分塊所屬數(shù)據(jù)方計(jì)算，整體分散度由任一數(shù)據(jù)方或額外參與方計(jì)算。分析含有記錄數(shù)量過(guò)少的分塊會(huì)造成分析得不準(zhǔn)確，分析時(shí)應(yīng)排除此類情況的分塊。

每個(gè)數(shù)據(jù)方在其大小大于X的分塊中隨機(jī)選取N個(gè)（遠(yuǎn)小于存在的分塊數(shù)量），分別從這N個(gè)分塊內(nèi)隨機(jī)選取q條記錄（遠(yuǎn)小于分塊內(nèi)記錄總數(shù)）。在bf上隨機(jī)選擇m個(gè)LSH分塊函數(shù)不曾作用的位置，連接每條記錄bf這m個(gè)位置的值形成一個(gè)序列，統(tǒng)計(jì)一個(gè)分塊內(nèi)序列的差異程度。n個(gè)數(shù)據(jù)方應(yīng)確定一致的x、N、q取值和m個(gè)位置。單塊分散度如式（1）所示：

其中，j表示n×N個(gè)分塊中的第j個(gè)，。為此分塊內(nèi)I種不同序列出現(xiàn)的概率，i=1,2,…,I。

根據(jù)單塊分散度計(jì)算整體分散度，據(jù)此來(lái)評(píng)估n個(gè)數(shù)據(jù)方綜合的分塊分散情況，則整體分塊分散度如式（2）所示：

通過(guò)閾值θ判斷是否需要進(jìn)行后綴分塊，θ的取值和數(shù)據(jù)擾亂程度相關(guān)。通過(guò)增加LSH中每組Hash函數(shù)的個(gè)數(shù)，確定僅通過(guò)LSH分塊就達(dá)到可接受的查準(zhǔn)率時(shí)的Hs值為θ。但僅通過(guò)LSH分塊達(dá)到此查準(zhǔn)率時(shí)對(duì)應(yīng)的查全率遠(yuǎn)低于通過(guò)二次分塊達(dá)到此查準(zhǔn)率時(shí)對(duì)應(yīng)的查全率，尤其是數(shù)據(jù)擾亂比例大的情況下。當(dāng)LSH分塊集群的Hs小于等于θ時(shí)，表明LSH方法已經(jīng)將相似度低的記錄劃分到不同的分塊內(nèi)，無(wú)需進(jìn)行后綴分塊，后續(xù)分塊合并步驟只需將各方LSH-key相同的分塊合并即可。若初步分塊的Hs大于θ，則選取的最小后綴長(zhǎng)度lmin如式（3）所示：

其中，Ht是對(duì)和需要鏈接的數(shù)據(jù)集質(zhì)量相同的數(shù)據(jù)進(jìn)行LSH分塊后測(cè)試得到的整體分散度，lt是Ht對(duì)應(yīng)的最佳最小后綴長(zhǎng)度。

4.3 基于滑動(dòng)窗口的分塊合并

由于不同數(shù)據(jù)方對(duì)同一實(shí)體的描述方式不一定相同，這可能會(huì)導(dǎo)致真實(shí)匹配的候選記錄組的損失。通過(guò)圖5來(lái)說(shuō)明分塊過(guò)程中這一問(wèn)題。Peter和Pete是P1和P2的兩條表示同一實(shí)體的記錄的分塊屬性值，它們所屬分塊的LSH-key相同但suffix不同，合并分塊時(shí)需要將Peter和Pete所屬的兩個(gè)分塊融合在一個(gè)最終分塊內(nèi)。為此，本文提出基于滑動(dòng)窗口的分塊合并方法以提高M(jìn)P-SPPRL的容錯(cuò)率。分塊合并步驟是Pn+1利用滑動(dòng)窗口對(duì)n個(gè)數(shù)據(jù)方各自的分塊進(jìn)行融合生成最終分塊的過(guò)程。然后在含有n方記錄的最終分塊內(nèi)生成候選記錄組。要求分塊合并方法使n方的相似記錄存在于同一最終分塊內(nèi)，并避免過(guò)多不匹配的候選記錄組生成。多方分塊合并方法具體如下：

Fig.5 Example of different records for the same entity圖5 表示相同實(shí)體的不同記錄舉例

首先，Pn+1統(tǒng)計(jì)接收的n方分塊簽名，對(duì)LSH-key相同且suffix長(zhǎng)度相同的分塊簽名按suffix值二進(jìn)制大小順序排序形成簽名列表。

如圖6所示，n=3時(shí)，在使用一組Hj的LSH分塊和x=2的兩次后綴分塊后，對(duì)LSH-key為1011，suffix長(zhǎng)度分別為2和3的兩組分塊簽名排序，并形成兩個(gè)簽名列表（圖6中的前5行為第一個(gè)簽名列表，后7行為第二個(gè)簽名列表）。

Fig.6 Blocks combining based on sliding window(n=3)圖6 基于滑動(dòng)窗口的分塊合并（n=3）

之后，采用大小為w的滑動(dòng)窗口對(duì)每個(gè)簽名列表進(jìn)行滑動(dòng)，在同一窗口內(nèi)若存在來(lái)自n個(gè)數(shù)據(jù)方的分塊，此窗口內(nèi)的所有分塊才會(huì)被合并生成一個(gè)最終分塊。最終分塊內(nèi)每n條來(lái)自不同數(shù)據(jù)方的記錄組成候選記錄組。其中，滑動(dòng)窗口大小w通過(guò)實(shí)驗(yàn)測(cè)試確定，要求w大于等于n，查全率隨w增大而升高，查準(zhǔn)率隨w增大而降低。

圖6中的w為4，suffix長(zhǎng)度為2的分塊簽名列表中有5條分塊簽名，窗口從頂部向下滑動(dòng)，每次滑動(dòng)一行，直至底部，則對(duì)于此簽名列表，生成兩個(gè)最終分塊，分別由編號(hào)為B11、B21、B31、B12和編號(hào)為B21、B31、B12、B22的分塊合并得到，編號(hào)Bij表示數(shù)據(jù)方Pi的第j個(gè)分塊。

根據(jù)上述方法，發(fā)現(xiàn)當(dāng)用長(zhǎng)度為3的后綴進(jìn)行分塊時(shí)，圖5中兩條記錄所在的LSH-key相同的分塊對(duì)應(yīng)的后綴值分別是100和000，因?yàn)楹缶Y值第一個(gè)比特位值不同，兩個(gè)分塊排序后會(huì)相隔較遠(yuǎn)，同時(shí)存在于滑動(dòng)窗口內(nèi)的可能性低，但當(dāng)用長(zhǎng)度為2的后綴進(jìn)行分塊時(shí)，兩記錄所在分塊的后綴值均為00，排序后一定會(huì)出現(xiàn)這兩個(gè)分塊同時(shí)存在于滑動(dòng)窗口內(nèi)的情況，并且這兩個(gè)分塊會(huì)被合并。以此避免拼寫錯(cuò)誤等情況造成的真實(shí)匹配候選記錄組的損失，提高M(jìn)PSPPRL的容錯(cuò)率。可根據(jù)一條記錄內(nèi)拼寫錯(cuò)誤的平均字符數(shù)量確定x和w。

5 強(qiáng)隱私保護(hù)下基于SMC的可伸縮多方記錄匹配算法

PPRL普遍考慮的攻擊模式是HBC（honest-butcurious behavior）[17]，即PPRL的參與方均遵守規(guī)定的鏈接規(guī)則，但他們?cè)噲D獲取其他數(shù)據(jù)方的輸入信息。在這種攻擊模式下，數(shù)據(jù)方可以和額外的參與方Pn+1串通，從而獲取其他數(shù)據(jù)方的敏感信息。

采用同態(tài)加密的SMC匹配方法可以在HBC模式下防止數(shù)據(jù)方和Pn+1串通引起的攻擊，其強(qiáng)隱私性在PPRL中具有很高的應(yīng)用價(jià)值，但同態(tài)加密計(jì)算方法時(shí)間復(fù)雜度大，因此之前沒(méi)有應(yīng)用在大數(shù)據(jù)多方PPRL中。

為此，本文提出了一種基于SMC的可伸縮多方記錄匹配算法，通過(guò)縮減加密時(shí)間和提前終止機(jī)制，在保證匹配強(qiáng)隱私性的同時(shí)大幅度降低時(shí)間代價(jià)，面對(duì)大數(shù)據(jù)集和數(shù)據(jù)方個(gè)數(shù)增加時(shí)，具有可伸縮性的匹配算法依然能保證時(shí)間代價(jià)在可控范圍內(nèi)。

數(shù)據(jù)集大小均為z，傳統(tǒng)SMC方法的加密記錄個(gè)數(shù)為n×z，而本文根據(jù)改進(jìn)的同態(tài)加密距離計(jì)算[4]兩條記錄只需加密一條的特點(diǎn)，設(shè)計(jì)的算法只需選擇接近z條記錄進(jìn)行同態(tài)加密，各數(shù)據(jù)方的加密時(shí)間約縮減為原來(lái)的1/n。加密方指派原則為同一LSH-key值對(duì)應(yīng)的候選記錄組中只對(duì)一個(gè)數(shù)據(jù)方記錄的匹配屬性值BF進(jìn)行同態(tài)加密。Pn+1確定各LSH-key值對(duì)應(yīng)的加密方，使得加密時(shí)間最長(zhǎng)的一方加密時(shí)間最小化。提前終止匹配機(jī)制是在Pn+1確認(rèn)候選記錄組已不匹配的情況下，Pn+1通知數(shù)據(jù)方終止不必要的距離計(jì)算，縮減候選記錄組匹配時(shí)間。

本文基于加密方指派原則和提前終止匹配機(jī)制，采用同態(tài)Hamming距離計(jì)算，提出了可伸縮多方記錄匹配算法，在一個(gè)候選記錄組中，若加密記錄與其余n-1條記錄均相似，則認(rèn)為這n-1條記錄也相互相似，判斷此候選記錄組為匹配的。記錄對(duì)相似度sim=1-d/L,因此本文用Hamming距離來(lái)判定候選記錄對(duì)相似性。由于數(shù)據(jù)質(zhì)量問(wèn)題，規(guī)定當(dāng)兩記錄距離d＞T時(shí)視此記錄對(duì)不相似，反之，為相似記錄對(duì)。閾值T的選取與表示同一實(shí)體的記錄對(duì)匹配屬性值可能出現(xiàn)的不同字符數(shù)量有關(guān)。

算法1可伸縮多方記錄匹配算法

1～4行是Pn+1指派各LSH-key值對(duì)應(yīng)的加密方，并將指派結(jié)果EncryptingPartyInfo和候選記錄組集合G發(fā)送給n個(gè)數(shù)據(jù)方。5～6行是數(shù)據(jù)方根據(jù)指派加密BF并傳遞給其余n-1方。7～14行是根據(jù)計(jì)算得到的記錄間Hamming距離將不匹配的記錄組從候選記錄組集合G中移除。對(duì)于每個(gè)Pi不是加密方的候選記錄組{r1,r2,…,rn},Pi利用BFi和BFj*計(jì)算ri和加密方Pj的記錄rj形成的記錄對(duì)的Hamming距離d?，多組候選記錄組包含相同的記錄對(duì)，計(jì)算一次即可，Pi將d?傳遞給Pn+1，Pn+1對(duì)d?解密，如果距離大于閾值T，則判斷包含此記錄對(duì)的候選記錄組均不匹配，并通知數(shù)據(jù)方將它們從候選組集合G中移除，節(jié)省數(shù)據(jù)方不必要的記錄組距離計(jì)算。15～20行是Pn+1對(duì)未被移除候選記錄組的核查，如果候選記錄組g的加密方記錄rk與其余n-1條記錄rl，l=1,2,…,k-1,k+1,…,n均進(jìn)行過(guò)距離計(jì)算則判定g為匹配的，否則需要完成遺漏的距離計(jì)算再判斷g是否匹配。最后，仍存在于G的記錄組被認(rèn)定為匹配的記錄組，返回匹配記錄組集合M=G。

6 實(shí)驗(yàn)與結(jié)果

6.1 實(shí)驗(yàn)設(shè)置

（1）實(shí)驗(yàn)數(shù)據(jù)集

本文采用的數(shù)據(jù)集為北卡羅來(lái)納州選民登記數(shù)據(jù)集（NCVR），選取記錄的姓和名作為分塊屬性，選取通信地址作為匹配屬性，bf和BF長(zhǎng)度均為100。

實(shí)驗(yàn)環(huán)境如下：主機(jī)采用Intel?CoreTMi7 CPU，3.4 GHz雙核處理器，內(nèi)存容量為8 GB，操作系統(tǒng)為64位Windows 7。本文用Python（3.6.3）實(shí)現(xiàn)文中提出的方法。

（2）評(píng)價(jià)準(zhǔn)則

實(shí)驗(yàn)通過(guò)查全率（Recall）、查準(zhǔn)率（Precision）[3]和運(yùn)行時(shí)間（Runtime）評(píng)價(jià)二次分塊方法，通過(guò)錯(cuò)誤率（Error rate）和運(yùn)行時(shí)間（Runtime）評(píng)價(jià)可伸縮多方記錄匹配方法，并與已有的分塊及匹配方法進(jìn)行對(duì)比評(píng)估。

查全率是候選記錄組中真正匹配的記錄組數(shù)量與數(shù)據(jù)集中真正匹配的記錄組數(shù)量的比率（見式（4））。

查準(zhǔn)率是候選記錄組中真正匹配的記錄組數(shù)量與候選記錄組數(shù)量的比率（見式（5））。

其中，TP是實(shí)際匹配的候選記錄組數(shù)量，F(xiàn)P是實(shí)際不匹配的候選記錄組數(shù)量，F(xiàn)N是由于分塊步驟損失的實(shí)際匹配的記錄組數(shù)量。

錯(cuò)誤率是判定為匹配的記錄組集合M中實(shí)際不匹配的記錄組所占比例，錯(cuò)誤率與匹配方法的精確性成反比。

PPRL的運(yùn)行時(shí)間可劃分為兩階段。第一階段為PPRL開始至生成候選記錄組所用時(shí)間，此段時(shí)間可用以評(píng)估分塊方法的時(shí)間性能，所用時(shí)間受分塊操作簡(jiǎn)單性和生成的候選記錄組數(shù)量影響。第二階段為對(duì)候選記錄組進(jìn)行匹配計(jì)算至得到匹配記錄組集合M所用時(shí)間，此段時(shí)間可用以評(píng)估匹配方法的時(shí)間性能，所用時(shí)間和匹配方法的計(jì)算復(fù)雜度有關(guān)。

（3）對(duì)比方法及參數(shù)確定

本文對(duì)提出的二次分塊方法與已有的LSH分塊方法[4]和后綴分塊方法[2]進(jìn)行對(duì)比實(shí)驗(yàn)，提出的可伸縮匹配算法與已有的利用SMC的匹配算法[10]進(jìn)行對(duì)比實(shí)驗(yàn)。實(shí)驗(yàn)數(shù)據(jù)有擾亂比例30%和75%兩種，每個(gè)數(shù)據(jù)方的數(shù)據(jù)集大小為5×103條記錄至1×105條記錄，數(shù)據(jù)方個(gè)數(shù)為3、5、7或9。

表1為僅通過(guò)LSH分塊方法得到的查全率及查準(zhǔn)率，當(dāng)Hs的值在0.27和0.55之間時(shí)，查全率和查準(zhǔn)率均趨于平穩(wěn)，且查準(zhǔn)率可以接受，則合適的θ取值應(yīng)在此范圍內(nèi)。圖4和圖5已經(jīng)測(cè)試出擾亂比例為30%時(shí)兩組整體分散度及對(duì)應(yīng)的最佳的最小后綴長(zhǎng)度，一組作為計(jì)算參數(shù)Ht=1.4，lt=15，另一組（1.11,10）用于測(cè)試θ取值，在0.27～0.55范圍內(nèi)測(cè)試不同的θ值，當(dāng)θ被設(shè)置為0.5時(shí)，根據(jù)式（3）計(jì)算出的Hs=1.11對(duì)應(yīng)的lmin=10.16符合lmin的真實(shí)值10，因此本文實(shí)驗(yàn)中擾亂比例30%數(shù)據(jù)的θ=0.5。類似地，設(shè)置擾亂比例75%數(shù)據(jù)的θ=0.3。

實(shí)驗(yàn)中的LSH方法和二次分塊方法中均選擇3組哈希函數(shù)，每組20個(gè)，選擇兩種長(zhǎng)度的后綴(x=2)，通過(guò)θ=0.5和θ=0.3確定兩種擾亂比例數(shù)據(jù)對(duì)應(yīng)的后綴長(zhǎng)度均為15、16位。后綴分塊方法的窗口大小為6，后綴長(zhǎng)度為15、16。實(shí)驗(yàn)數(shù)據(jù)集匹配屬性值由擾亂最多可造成兩個(gè)字符的不同，且考慮不同字符映射到Bloom Filter同一比特位的沖突情況，根據(jù)測(cè)試確定T的最佳值為3。

Table 1 Hs,Recall and Precision of LSH blocking表1 LSH分塊的Hs與查全率、查準(zhǔn)率

圖7為數(shù)據(jù)方個(gè)數(shù)不同時(shí)，MP-SPPRL的查全率隨分塊合并方法中滑動(dòng)窗口大小w增加的變化情況。利用滑動(dòng)窗口的目的是使各方的相似記錄存在于同一分塊內(nèi)，w越大相似記錄越可能被聚合在同一最終分塊內(nèi)，查全率越高。因?yàn)榻^大多數(shù)相似記錄所在分塊在簽名列表中位置會(huì)相近，w足夠大后，絕大數(shù)相似記錄會(huì)被聚合，w繼續(xù)增大作用很小，對(duì)查全率改變并不明顯。可以看出對(duì)于3、5、7、9個(gè)數(shù)據(jù)方，當(dāng)w分別達(dá)到5、7、9、12后，查全率趨于平穩(wěn)。同時(shí)，查準(zhǔn)率一定會(huì)隨w增加持續(xù)降低。因此下面實(shí)驗(yàn)中4種數(shù)據(jù)方個(gè)數(shù)的MP-SPPRL方法對(duì)應(yīng)的w分別設(shè)置為5、7、9、12。

Fig.7 Relationship of recall and window size圖7 查全率與窗口大小關(guān)系圖

6.2 實(shí)驗(yàn)結(jié)果及分析

（1）基于滑動(dòng)窗口的分塊合并方法的作用

圖8實(shí)驗(yàn)在數(shù)據(jù)方各自二次分塊后，對(duì)比了簡(jiǎn)單合并和基于滑動(dòng)窗口合并兩種方法，簡(jiǎn)單合并為僅將不同數(shù)據(jù)方簽名中LSH-key和suffix相同的分塊合并。P1表示數(shù)據(jù)的擾亂比例為記錄的30%，P2表示數(shù)據(jù)的擾亂比例為記錄的75%，每個(gè)數(shù)據(jù)集的大小|Di|=20 000。圖8（a）中，基于滑動(dòng)窗口的分塊合并方法查全率高于簡(jiǎn)單合并方法，尤其是數(shù)據(jù)擾亂比例大時(shí)，基于滑動(dòng)窗口的分塊合并方法具有容錯(cuò)性，因此顯著優(yōu)于簡(jiǎn)單合并方法。圖8（b）中，基于滑動(dòng)窗口合并方法查準(zhǔn)率低于簡(jiǎn)單合并方法，因?yàn)槠錇楸ＷC容錯(cuò)率合并了更多分塊。雖然基于滑動(dòng)窗口的合并方法會(huì)導(dǎo)致需要匹配更多的候選記錄組，但為避免數(shù)據(jù)擾亂造成的真實(shí)匹配記錄組的過(guò)度損失，相較于簡(jiǎn)單合并方法，此方法更優(yōu)，并且本文提出的高效的可伸縮匹配算法也可彌補(bǔ)此不足。

Fig.8 Comparison of common block merging and window-based block merging圖8 簡(jiǎn)單分塊合并與基于滑動(dòng)窗口的分塊合并對(duì)比

Fig.9 Comparison of double blocking,LSH and suffix blocking in different database sizes圖9 不同大小數(shù)據(jù)集下二次分塊、LSH和后綴分塊對(duì)比

（2）分塊方法查全率及查準(zhǔn)率評(píng)估

圖9和圖10實(shí)驗(yàn)對(duì)不同大小和不同擾亂比例的數(shù)據(jù)集分別進(jìn)行二次分塊（結(jié)合基于滑動(dòng)窗口的分塊合并）、LSH分塊和后綴分塊，以數(shù)據(jù)方個(gè)數(shù)為自變量，查全率與查準(zhǔn)率作為因變量，比較三種分塊方法。

以往對(duì)分塊方法查準(zhǔn)率的評(píng)估均是在兩方情景下進(jìn)行的。文獻(xiàn)[4]中兩方Hamming-based LSH分塊方法對(duì)每方大小為2.5×105的數(shù)據(jù)生成的候選記錄對(duì)數(shù)量為5×107，推斷其查準(zhǔn)率必然低于0.005，擴(kuò)展到多方時(shí)會(huì)生成更多的候選記錄組，顯著降低查準(zhǔn)率。文獻(xiàn)[2]中大小僅為5×103的數(shù)據(jù)集對(duì)應(yīng)的查準(zhǔn)率在0.2到0.6之間，當(dāng)數(shù)據(jù)集規(guī)模增大時(shí)，查準(zhǔn)率會(huì)持續(xù)降低。LSH方法簡(jiǎn)明的分塊方式適合多方間的PPRL，但其查準(zhǔn)率相較于其他分塊方法較低。二次分塊方法極大改善了LSH分塊方法的查準(zhǔn)率。

Fig.10 Comparison of double blocking,LSH and suffix blocking in different disturbances圖10 不同擾亂比例下二次分塊、LSH和后綴分塊對(duì)比

圖9中，S1表示每個(gè)數(shù)據(jù)方的數(shù)據(jù)集大小|Di|=10 000,S2表示|Di|=20 000，數(shù)據(jù)的擾亂比例均為30%。如圖9（a）所示，三種方法均為S2比S1查全率高，因?yàn)閿?shù)據(jù)集較大時(shí)分塊內(nèi)的記錄較多，真實(shí)匹配的候選記錄組損失的可能性就比較低，查全率由高至低分別是LSH分塊方法、二次分塊方法和后綴分塊方法。隨著數(shù)據(jù)方個(gè)數(shù)的增加，三種方法的查全率均有所下降，其中LSH方法下降最為緩慢，二次分塊方法下降最為迅速。如圖9（b）所示，三種方法均為數(shù)據(jù)集較大時(shí)查準(zhǔn)率低，隨著數(shù)據(jù)方個(gè)數(shù)的增加，LSH方法的查準(zhǔn)率跨數(shù)量級(jí)迅速下降，二次分塊方法和后綴分塊方法的查準(zhǔn)率緩慢下降，因?yàn)橥ㄟ^(guò)LSH方法形成的最終分塊內(nèi)記錄數(shù)量明顯多于其余兩種方法。

圖10中，P1表示數(shù)據(jù)的擾亂比例為記錄的30%，P2表示數(shù)據(jù)的擾亂比例為記錄的75%，每個(gè)數(shù)據(jù)集的大小|Di|=20 000，對(duì)兩種擾亂比例下通過(guò)三種分塊方法得到的查全率與查準(zhǔn)率進(jìn)行評(píng)估。如圖10（a）所示，在數(shù)據(jù)方個(gè)數(shù)相同的情況下，數(shù)據(jù)的擾亂比例由30%增加到75%，二次分塊方法和后綴分塊方法的查全率比LSH方法降低明顯，因?yàn)檫@兩種方法的最終分塊內(nèi)記錄數(shù)量少，數(shù)據(jù)擾亂比例高的時(shí)候更有可能損失真實(shí)匹配的記錄組。圖10（a）的其他情況與圖9（a）一致。如圖10（b）所示，擾亂比例的增加會(huì)造成分塊方法查準(zhǔn)率一定程度的下降，這是由于識(shí)別出的真實(shí)匹配候選記錄組數(shù)量的減少造成的，其他情況與圖9（b）基本一致。

上述實(shí)驗(yàn)表明，本文提出的二次分塊方法查全率略低于LSH方法，查準(zhǔn)率顯著高于LSH方法，隨著數(shù)據(jù)方個(gè)數(shù)的增加，LSH方法的查準(zhǔn)率急劇下降，而二次分塊方法的查準(zhǔn)率下降趨勢(shì)較為平緩，并且二次分塊方法的查全率和查準(zhǔn)率均優(yōu)于后綴分塊方法。實(shí)驗(yàn)結(jié)果說(shuō)明，相較于LSH方法和后綴分塊方法，本文提出的二次分塊方法更適用于多方大數(shù)據(jù)集間的記錄鏈接。

（3）多方可伸縮匹配算法精確性評(píng)估

圖11實(shí)驗(yàn)采用P1=30%和P2=75%兩種擾亂比例，表示同一實(shí)體的記錄組數(shù)量為500的數(shù)據(jù)集。通過(guò)實(shí)驗(yàn)可以看出，錯(cuò)誤率隨數(shù)據(jù)擾亂比例值增加而升高。數(shù)據(jù)方個(gè)數(shù)增加時(shí)，錯(cuò)誤率降低，匹配算法對(duì)候選記錄組的判定更為精確。

（4）MP-SPPRL方法時(shí)間性能評(píng)估

圖12中，實(shí)驗(yàn)測(cè)試了三種分塊方法隨數(shù)據(jù)方個(gè)數(shù)增加對(duì)應(yīng)的第一階段時(shí)間，每個(gè)數(shù)據(jù)集的大小|Di|=20 000，數(shù)據(jù)的擾亂比例為30%?？梢钥闯鱿嗤瑪?shù)據(jù)方個(gè)數(shù)時(shí)應(yīng)用LSH方法的時(shí)間明顯高于應(yīng)用二次分塊和后綴分塊兩種方法的時(shí)間，且隨數(shù)據(jù)方個(gè)數(shù)增加，應(yīng)用LSH方法時(shí)間的增長(zhǎng)速度快于應(yīng)用其余兩種方法。造成此情況的原因是，雖然LSH分塊方法的操作更為快速，但其形成的分塊內(nèi)記錄數(shù)量多，會(huì)導(dǎo)致生成大量候選記錄組的時(shí)間花費(fèi)大，生成候選記錄組花費(fèi)的時(shí)間同樣是評(píng)價(jià)分塊方法時(shí)間性能需考慮的因素。

Fig.11 Error rate of scalable multi-party matching algorithm圖11 可伸縮多方記錄匹配算法錯(cuò)誤率

Fig.12 Relationship of blocking runtime and party number圖12 分塊方法運(yùn)行時(shí)間與數(shù)據(jù)方個(gè)數(shù)關(guān)系圖

Fig.13 Relationship of matching runtime and data size圖13 匹配算法運(yùn)行時(shí)間與數(shù)據(jù)集大小關(guān)系圖

Fig.14 Relationship of matching runtime and party number圖14 匹配算法運(yùn)行時(shí)間與數(shù)據(jù)方個(gè)數(shù)關(guān)系圖

在圖13和圖14實(shí)驗(yàn)中，數(shù)據(jù)的擾亂比例為30%，提前對(duì)數(shù)據(jù)集進(jìn)行了二次分塊及分塊合并。圖13實(shí)驗(yàn)表明了數(shù)據(jù)方個(gè)數(shù)n=3時(shí)，兩種匹配算法的運(yùn)行時(shí)間均隨數(shù)據(jù)集大小的增加而升高，本文提出的可伸縮多方記錄匹配算法所用時(shí)間約為SMC匹配算法時(shí)間的一半，可伸縮匹配算法在大小為1×105的大數(shù)據(jù)集下合理的運(yùn)行時(shí)間說(shuō)明了其具有良好的擴(kuò)展性。圖14實(shí)驗(yàn)表明了在|Di|=20 000數(shù)據(jù)集下，隨著數(shù)據(jù)方個(gè)數(shù)的增加，兩種匹配算法的運(yùn)行時(shí)間都增加，但可伸縮多方記錄匹配算法的時(shí)間增速明顯小于SMC匹配算法，說(shuō)明基于改進(jìn)同態(tài)加密計(jì)算和提前終止匹配機(jī)制的可伸縮匹配算法在多個(gè)數(shù)據(jù)方的情況下表現(xiàn)突出。由圖13和圖14可以得出本文提出的可伸縮多方記錄匹配算法在多方大數(shù)據(jù)集情景下具有高效性的結(jié)論。

7 結(jié)束語(yǔ)

本文提出了結(jié)合LSH分塊和后綴分塊的二次分塊方法，在損失少量查全率的條件下大幅度提高查準(zhǔn)率，同時(shí)具有高精確性與高效性。同時(shí)，將分塊分散度度量引入二次分塊，支持二次分塊中兩種分塊方法的自調(diào)節(jié)，有效地控制查全率的損失。此外，基于滑動(dòng)窗口的分塊合并方法可以和二次分塊方法結(jié)合，提高M(jìn)P-SPPRL的容錯(cuò)率，避免真實(shí)匹配的候選記錄組的損失。本文設(shè)計(jì)的基于SMC的可伸縮多方記錄匹配算法能在保證強(qiáng)隱私性的前提下，明顯縮減匹配時(shí)間，提高匹配效率，使其適用于大數(shù)據(jù)環(huán)境下。但是，隨著數(shù)據(jù)方個(gè)數(shù)的增加，已有的PPRL方法和本文提出的MP-SPPRL方法的查全率均會(huì)下降，下一步，將試圖在本文的基礎(chǔ)上解決這一問(wèn)題。