多方強隱私保護記錄鏈接方法*

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

東北大學(xué) 計算機科學(xué)與工程學(xué)院，沈陽 110819

1 引言

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

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

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

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

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

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

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

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

2 相關(guān)工作

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

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

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

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

3 問題定義

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

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

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

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

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

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

4.1 二次分塊模型

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

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

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

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

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

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

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

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

4.2 基于LSH分塊分散度的后綴長度確定

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

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

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

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

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

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

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

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

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

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

4.3 基于滑動窗口的分塊合并

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

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

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

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

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

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

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

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

5 強隱私保護下基于SMC的可伸縮多方記錄匹配算法

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

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

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

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

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

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

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

6 實驗與結(jié)果

6.1 實驗設(shè)置

（1）實驗數(shù)據(jù)集

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

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

（2）評價準(zhǔn)則

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

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

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

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

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

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

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

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

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

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

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

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

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

6.2 實驗結(jié)果及分析

（1）基于滑動窗口的分塊合并方法的作用

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

Fig.8 Comparison of common block merging and window-based block merging圖8 簡單分塊合并與基于滑動窗口的分塊合并對比

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

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

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

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

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

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

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

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

（3）多方可伸縮匹配算法精確性評估

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

（4）MP-SPPRL方法時間性能評估

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

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

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

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

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

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

7 結(jié)束語

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