基於隱私保持的分布式Top-k查詢方法
2023-09-13 06:53:35 1
專利名稱：基於隱私保持的分布式Top-k查詢方法
技術領域：
本發明涉及一種基於隱私保持的分布式Top-k查詢方法，確切地說，涉及一種在匯聚計算過程中對處理的數據對是經過本發明處理過的非真實值，但是最終獲得的查詢結果是真實、正確的，從而保護數據提供方的數據隱私；屬於計算機網絡中的網絡管理、安全監控、數據挖掘隱私保護、分布式計算等多項技術，特別是分布式計算和數據挖掘、數據隱私保護的技術領域。
背景技術：
本發明處理的數據對象為分布在不同地理位置的數據列表，該參見圖1，分布式Top-k(前k項)查詢是由中心計算節點通過匯聚分布在不同地理位置的數據列表，計算出全局匯聚值最大的前k個對象及匯聚值；其中數據列表的每一項都是一個數據對 ，數據對中的對象和對象值都包含有數據提供方的敏感信息。分布式Top-k查詢計算在網絡和系統監控、信息採集、傳感器網絡、P2P系統以及數據流控制系統等技術領域都有廣泛的應用。傳統的分布式Top-k查詢算法需要中心計算節點收集分布在不同地理位置的眾多數據提供方提供的數據列表，通過匯聚排序後，再返回查詢的結果，計算過程中數據提供方的數據隱私全部暴露給中心節點，中心計算節點信息的洩露就會導致數據提供方數據隱私的洩露。三階段統一閥值算法(TPUT)是將分布式Top-k查詢分為三個階段第一階段，中心計算節點匯聚計算各數據列表的前k項，計算出一個統一的閥值。第二階段，各數據提供方將各自數據列表中對象值大於該閥值的數據對上傳到中心計算節點，中心計算節點通過界限剪枝去除掉冗餘的數據對，得到Top-k候選集。第三階段，各數據提供方從各自的數據列表中找出候選集出現的對象，將對應的數據對上傳到中心計算節點，中心計算節點通過匯聚計算，並降序排列得到最終的Top-k查詢結果。該方法減少了數據提供方上傳的數據量，可以通過有限次數的應答(即三次)獲得精確的Top-k查詢結果。然而，該算法沒有考慮到數據提供方的數據分布性特點，只是假設所有數據提供方提供的數據具有相同的分布性。如果各個數據提供方擁有的數據分布差異較大時，數據上傳量將大大增加，從而也會造成數據隱私的洩露。三階段自適應閥值算法(TPAT)對TPUT算法的第一階段進行了改進中心計算節點根據數據提供方各自數據列表數據對象的直方圖進行統計，通過最優化算法計算出各個數據提供方對應的上傳數據的閥值；這樣有效減少了第一階段數據上傳的冗餘，但是，當各數據提供方數據排序變化比較大時，仍會有大量數據隱私會被洩露。目前，安全多方計算研究已經取得了一定成果。概括地說，安全多方計算是為了研究一組互不信任的參與者如何在保護各自私有信息的基礎上完成合作計算。基於二分查找的分布式Top-k查詢方法通過使用安全多方計算中的比較等原子操作，再使用二分查找計算最終的全局匯聚值最大的前K個對象及匯聚值，該計算過程中無需中心計算節點的參與，數據提供方在不暴露數據列表中對象值的情況下，就可以獲得最終正確的計算結果。但是，該方法計算過程中沒有對數據列表中的對象的隱私進行處理，算法中大量的安全多方計算比較操作導致算法運行時間難以部署在實際應用環境中。基於Hash表的二分查找分布式Top-k查詢方法是首先通過使用Hash表對各個數據提供方數據列表中的對象進行歸一化，然後使用Siamir(人名)門限秘密共享方案，對歸一化的數據進行安全匯聚，最後通過安全的二分查找獲得最終的查詢結果。由於Hash表對數據進行歸一化會造成數據項的衝突，最終的查詢結果只是一個近似結果，此外，計算過程中大量安全多方求和操作和比較操作也會使算法的運行時間隨著Hash表的大小呈指數增長。分布式Top-k查詢計算需要中心計算節點與各個數據提供方協同計算共同完成， 由於大多數的數據提供方分別屬於不同的組織或管理機構，分布在不同的地理位置，同時數據提供方提供的數據列表中中還包含了大量的隱私敏感信息，然而，目前已有的分布式 Top-k查詢算法在隱私保護、運行效率方面還不能滿足實時、全面保護的要求，因此，如何在平衡算法的運行效率和安全保護就成為當前亟需解決的問題。
發明內容
有鑑於此，本發明的目的是提供一種基於隱私保持的分布式Top-k查詢方法，該方法特點是在三階段閥值算法基礎上，使用安全多方計算操作分別對數據列表中的對象和對象值進行隱私保護處理，從而在最大化保護數據提供方隱私的同時，可以快速、精確地獲得Top-k查詢結果，使得數據提供方在不暴露自有數據隱私的前提下，就完成安全的數據匯聚查詢操作。為了達到上述發明目的，本發明提供了一種基於隱私保持的分布式TOP-K查詢方法，所述分布式Top-k查詢是中心計算節點通過匯聚分布在不同地理位置的數據列表，計算出全局匯聚值中最大的前k個對象及匯聚值；其特徵在於中心計算節點先對各數據提供方數據列表中的對象進行隱私保護處理，然後在三階段閥值算法的基礎上，利用安全多方計算操作對數據列表中的對象值進行隱私保護處理，以便在最大化保護數據提供方數據隱私的同時，能夠快速、精確地獲得Top-k查詢結果；所述方法包括下列操作步驟(1)中心計算節點與數據提供方之間運行安全計算協議，對數據列表中的對象和對象值進行隱私保護處理；(2)中心計算節點與數據提供方之間根據閥值算法計算Top-k候選集；(3)數據提供方之間對候選集中的對象進行安全多方求和操作，中心計算節點通過降序排列得到經過隱私處理後的Top-k對象集及其對應的匯聚值。(4)中心計算節點還原Top-k對象集中的對象真實值，返回查詢結果。本發明方法與現有技術相比較，主要有兩方面的改進首先，本發明對數據隱私保護具有全面性；其次，本發明的運行效率和準確性都比較高。傳統的基於閥值的分布式Top-k查詢算法，雖然能經過有限次的交互查詢就可以得到精確或近似的查詢結果，但是，數據中涉及對象屬性和對象的數值分布完全暴露給中心計算節點，中心計算節點的信息洩露會導致參與查詢計算的數據提供方信息的洩露。基於安全多方計算的二分查找分布式Top-k查詢算法只對對象值進行了隱私處理，當各個數據提供方對象分布不均勻時，會造成數據對象信息的洩露。如在網絡監控應用中，不同管理域之間進行目的IP位址匯聚查詢計算，使用該算法可能會造成各個管理域的大部分活躍IP位址洩露，從而可能引發不必要的網絡攻擊行為。目前，最好的可以隱私保持的分布式Top-k查詢算法是基於Hash表和安全多方計算的的二分查找算法，該算法通過Hash表對數據對象實現了歸一化和隱私保護，然後，再使用Siamir門限秘密共享方案對歸一化的對象值進行安全匯聚，最後通過安全的二分查找獲得最終近似的查詢結果，從而實現了對數據對象和對象值的全面保護。但是，由於該算法利用hash表進行數據對象的歸一化，在歸一化的過程中會造成數據對象遺漏，從而造成查詢結果的不準確。雖然通過增加hash表的長度可有效減少誤差，然而，表長的增加，增加了安全多方計算比較和的求和操作，進而影響算法的運行效率，難以滿足實時連續查詢需求。因此，本發明在三階段閥值算法基礎上，使用安全多方計算操作分別對數據列表中的對象和對象值進行隱私保護處理，從而既最大化地保護數據提供方隱私，同時，能夠快速、精確地獲得Top-k查詢結果，使得數據提供方在不暴露自有數據隱私的前提下，就能夠快速、 安全地完成數據匯聚查詢操作。所以，本發明在分布式網絡協同安全監控、網絡管理、數據挖掘隱私保護等許多領域具有很好的推廣應用前景。
圖1是本發明基於隱私保持的分布式Top-k查詢方法的一種應用場景系統結構示意圖。圖2是本發明基於隱私保持的分布式Top-k查詢方法操作步驟流程圖。
具體實施例方式為使本發明的目的、技術方案和優點更加清楚，下面結合附圖和實施例對本發明作進一步的詳細描述。本發明基於隱私保持的分布式Top-k查詢方法是中心計算節點先對各數據提供方數據列表中的對象進行隱私保護處理，然後在三階段閥值算法的基礎上，利用安全多方計算操作對數據列表中的對象值進行隱私保護處理，以便在最大化保護數據提供方數據隱私的同時，能夠快速、精確地獲得Top-k查詢結果。本發明中，每個數據提供方提供的數據列表中的對象是m位字符串χ = (X1. . . . . Xm)，式中，下標m的取值區間為(192，256)，若字符串的長度超過256，則數據提供方使用統一的映射函數(例如哈希函數)將該字符串映射為m位字符串，然後中心計算節點對各數據提供方的數據列表中的對象和對象值執行隱私處理。參見圖2，介紹本發明方法的下述具體操作步驟步驟1，中心計算節點與數據提供方之間運行安全計算協議，對數據列表中的對象和對象值進行隱私保護處理。該步驟包括下列操作內容(11)中心計算節點隨機產生一個大素數ρ和ρ階乘法群GP，以及(}P的生成元g，並
在整數模P乘法群《中隨機產生ail個隨機值Ia1,......，和Ir1,......，rm}，再組成
m個數據對( , ^i)，式中，自然數i的最大值為m，並計算固定值/ = g1/r^ ，並將這m 個數據對和固定值t發送給各個數據提供方；(12)數據提供方按照下述方式逐一計算數據列表中每個對象χ = (X1. . . . . I)對應的加密值M
若\ = 0，則記為 ，否則，記為^Xri ；再計算J = (ΠΓ=1 Α) Χ (Π =1 η),則該對象
的加密值M = tA，然後將該加密值與原對象建立一一映射關係；經過上述隱私處理後，中心計算節點就無法獲知各數據列表中對象的真實值，且每個數據提供方數據列表中同一個對象的加密值是相同的，每個數據提供方能夠還原加密對象的真實值；(13)數據提供方選擇一個隨機值，再將各自數據列表中所有對象的對象值減去該隨機值，數據提供方之間共同運行Siamir門限秘密共享求和操作，計算這些隨機值的總和，以使每個數據提供方也不能獲知其他數據提供方相減後的隨機值；然後，將該總和發送給中心計算節點；如此操作後，數據提供方與中心計算節點之間交互對象的對象值都是隱私處理後的非真實值。步驟2，中心計算節點與數據提供方之間根據閥值算法計算Top-k候選集。該步驟包括下列操作內容(21)數據提供方只將各數據列表中加密後中降序排列的前k個對象上傳到中心計算節點，中心計算節點刪除重複出現的對象後，將剩餘的對象發送給各數據提供方，以使數據提供方再將這些對象對應的對象值上傳給中心計算節點；(22)假設參與查詢計算的數據提供方共有η個，各數據提供方將每個需要上傳對象的對象值分成η份，該η份的和等於該對象值；再將(η-1)份發給其他數據提供方；如果該對象不在數據列表中，則認為該對象的對象值為以前減去的隨機值，也分為η份發給其他數據提供方；其它數據提供方接收到該對象的(η-1)份數據後，重新匯聚求和，作為該對象的對象值；然後將這些對象及匯聚後的對象值上傳到中心計算節點；(23)中心計算節點將上傳的對象匯聚求和後，按降序排列，選取第k個對象的匯聚值為閥值，並將該閥值均分後發送給各數據提供方；數據提供方接收到均分的閥值後，將大於該閥值的對象及對象值上傳到中心計算節點；(24)中心計算節點去除重複出現的對象，將剩餘的對象組成Top-k候選集，再將該Top-k候選集發送到各個數據提供方。步驟3，數據提供方之間對候選集中的對象進行安全多方求和操作，中心計算節點通過降序排列得到經過隱私處理後的Top-k對象集及其對應的匯聚值。該步驟包括下列操作內容(31)各數據提供方從各自的數據列表中找出候選集出現的對象，將每個對象的對象值分成η份，該η份的和等於該對象值；再將(η-1)份發送給其他數據提供方；如果候選集中的該對象不在數據列表中，則認為該對象的對象值為以前減去的隨機值，也分為η份發送給其他數據提供方；其它數據提供方接收到該對象的(η-1)份數據後，重新匯聚求和， 作為該對象的對象值；然後將該對象值上傳到中心計算節點；(32)中心計算節點再次將上傳的對象匯聚求和，並將該結果加上由步驟(13)減去隨機值的總和，進行降序排列後，得到Top-k對象集合及匯聚值。步驟4，中心計算節點還原Top-k對象集中的對象真實值，返回查詢結果，查詢結束。該步驟包括下列操作內容(41)中心計算節點向各數據提供方查詢Top-k對象集合中對象的真實值；(42)中心計算節點向各數據提供方返回真實的Top-k對象集合及對應的匯聚值，查詢結束。 以上所述僅為本發明的較佳實施例而已，並不用以限制本發明，凡在本發明的精神和原則之內，所做的任何修改、等同替換、改進等，均應包含在本發明保護的範圍之內。
權利要求
1.一種基於隱私保持的分布式Top-k查詢方法，所述分布式Top-k查詢是中心計算節點通過匯聚分布在不同地理位置的數據列表，計算出全局匯聚值中最大的前k個對象及匯聚值；其特徵在於中心計算節點先對各數據提供方數據列表中的對象進行隱私保護處理，然後在三階段閥值算法的基礎上，利用安全多方計算操作對數據列表中的對象值進行隱私保護處理，以便在最大化保護數據提供方數據隱私的同時，能夠快速、精確地獲得 Top-k查詢結果；所述方法包括下列操作步驟(1)中心計算節點與數據提供方之間運行安全計算協議，對數據列表中的對象和對象值進行隱私保護處理；(2)中心計算節點與數據提供方之間根據閥值算法計算Top-k候選集；(3)數據提供方之間對候選集中的對象進行安全多方求和操作，中心計算節點通過降序排列得到經過隱私處理後的Top-k對象集及其對應的匯聚值；(4)中心計算節點還原Top-k對象集中的對象真實值，返回查詢結果。
2.根據權利要求1所述的方法，其特徵在於每個數據提供方所提供的數據列表中的對象是m位字符串χ = (X1……I)，式中，下標m的取值區間為(192，256)，若字符串的長度超過256，則數據提供方使用統一的映射函數將該字符串映射為m位字符串，然後中心計算節點對各數據提供方的數據列表中的對象和對象值執行隱私處理。
3.根據權利要求2所述的方法，其特徵在於所述映射函數是哈希函數。
4.根據權利要求1所述的方法，其特徵在於所述步驟(1)包括下列操作內容(11)中心計算節點隨機產生一個大素數ρ和ρ階乘法群(}P，以及(^p的生成元g，並在整數模P乘法群《中隨機產生ail個隨機值Ia1,......，和Ir1,......，rm}，再組成m個數據對(屮，屮·巧)，式中，自然數i的最大值為m，並計算固定值/ =α·,並將這m個數據對和固定值t發送給各個數據提供方；(12)數據提供方按照下述方式逐一計算數據列表中每個對象χ= (X1.....xffl)對應的加密值M 若Xi = 0，則記為否則，記為屮Xri ；再計算J = (Π Ci1) χ (Π: η),則該對象的加密值M = tA，然後將該加密值與原對象建立一一映射關係；經過上述隱私處理後，中心計算節點就無法獲知各數據列表中對象的真實值，且每個數據提供方數據列表中同一個對象的加密值是相同的，每個數據提供方能夠還原加密對象的真實值；(13)數據提供方選擇一個隨機值，再將各自數據列表中所有對象的對象值減去該隨機值，數據提供方之間共同運行Siamir門限秘密共享求和操作，計算這些隨機值的總和，以使每個數據提供方也不能獲知其他數據提供方相減後的隨機值；然後，將該總和發送給中心計算節點；如此操作後，數據提供方與中心計算節點之間交互對象的對象值都是隱私處理後的非真實值。
5.根據權利要求1所述的方法，其特徵在於所述步驟(2)包括下列操作內容(21)數據提供方只將各數據列表中加密後中降序排列的前k個對象上傳到中心計算節點，中心計算節點刪除重複出現的對象後，將剩餘的對象發送給各數據提供方，以使數據提供方再將這些對象對應的對象值上傳給中心計算節點；(22)假設參與查詢計算的數據提供方共有η個，各數據提供方將每個需要上傳對象的對象值分成η份，該η份的和等於該對象值；再將(η-1)份發給其他數據提供方；如果該對象不在數據列表中，則認為該對象的對象值為以前減去的隨機值，也分為η份發給其他數據提供方；其它數據提供方接收到該對象的(η-1)份數據後，重新匯聚求和，作為該對象的對象值；然後將這些對象及匯聚後的對象值上傳到中心計算節點；(23)中心計算節點將上傳的對象匯聚求和後，按降序排列，選取第k個對象的匯聚值為閥值，並將該閥值均分後發送給各數據提供方；數據提供方接收到均分的閥值後，將大於該閥值的對象及對象值上傳到中心計算節點；(24)中心計算節點去除重複出現的對象，將剩餘的對象組成Top-k候選集，再將該 Top-k候選集發送到各個數據提供方。
6.根據權利要求1所述的方法，其特徵在於所述步驟(3)包括下列操作內容(31)各數據提供方從各自的數據列表中找出候選集出現的對象，將每個對象的對象值分成η份，該η份的和等於該對象值；再將(η-1)份發送給其他數據提供方；如果候選集中的該對象不在數據列表中，則認為該對象的對象值為以前減去的隨機值，也分為η份發送給其他數據提供方；其它數據提供方接收到該對象的(η-1)份數據後，重新匯聚求和，作為該對象的對象值；然後將該對象值上傳到中心計算節點；(32)中心計算節點再次將上傳的對象匯聚求和，並將該結果加上由步驟(13)減去隨機值的總和，進行降序排列後，得到Top-k對象集合及匯聚值。
7.根據權利要求1所述的方法，其特徵在於所述步驟(4)包括下列操作內容(41)中心計算節點向各數據提供方查詢Top-k對象集合中對象的真實值；(42)中心計算節點向各數據提供方返回真實的Top-k對象集合及對應的匯聚值，查詢結束。
8.根據權利要求1所述的方法，其特徵在於所述方法用於分布式網絡的協同安全監控、網絡管理和數據挖掘隱私保護。
全文摘要
一種基於隱私保持的分布式Top-k查詢方法，是由中心計算節點先對各數據提供方數據列表中的對象進行隱私保護處理，然後在三階段閥值算法的基礎上，利用安全多方計算操作分別對各個數據列表中的對象值進行隱私保護處理，以便在最大化保護數據提供方數據隱私的同時，能夠快速、精確地獲得Top-k查詢結果，從而使得數據提供方在不暴露自有數據隱私的前提下，就完成安全的數據匯聚查詢操作。所以，本發明在分布式網絡協同安全監控、網絡管理、數據挖掘隱私保護等許多領域具有很好的推廣應用前景。
文檔編號H04L12/24GK102394784SQ20111037106
公開日2012年3月28日 申請日期2011年11月21日 優先權日2011年11月21日
發明者吳軍, 寧春雨, 張沛, 林昭文, 王振華, 蘇玉潔, 趙欽, 鄭希帆, 馬嚴, 黃小紅 申請人:北京郵電大學