基于隱私保護的企業間安全多方計算研究

〔摘 要〕基于現行數據隱私問題日益嚴重，如何防止數據挖掘過程中隱私信息的泄漏，將是一個重要的研究議題。本文主要針對關聯規則挖掘技術，從安全多方計算方面探討隱私信息的保護，提出適用于挖掘水平分割數據的保護機制。方法設計采用集中式挖掘，過程中加入信息安全技術以確保參與單位的數據隱私，以求在隱私保護和知識獲取間取得一個平衡。

〔關鍵詞〕隱私保護;安全多方計算;密碼學

〔中圖分類號〕TP311 〔文獻標識碼〕A 〔文章編號〕1008-0821(2009)09-0199-03

Study of Privacy Preserving in Secure Multi-party

Computation Between EnterprisesLiu Song

(Information Science School，Guangdong University of Business Studies，Guangzhou 510320，China)

〔Abstract〕Privacy-preserving data mining， which finds out knowledge but preserves privacy，consequently is becoming an important but difficult issue.In this paper，privacy-preserving mechanisms for association rule mining were investigated.A mechanism that partitions data horizontally and transforms individual data for the co-operative mining was proposed.A centralized mining model was used，data privacy of each participating party could be protected through encryption but valuable co-operative results can be discovered.The proposed mechanisms thus struck a balance between privacy protection and knowledge discovery.

〔Key words〕privacy-preserving;secure multi-party computation;cryptography

針對目前競爭激烈的市場環境，企業間通過多方合作挖掘，共同創造價值的模式日益盛行。但各種數據挖掘工具在從海量數據中獲取有用信息的同時，也對數據的安全產生了威脅[1-2]，如果在挖掘過程中不采取任何數據保護措施，將可能造成各參與挖掘單位隱私信息的泄露。因此，如何在保護數據隱私的情況下挖掘出有用信息是企業間進行合作挖掘時必須解決的問題。盡管目前已有基于隱私保護的分布式多方挖掘方法[3-4]，但由于挖掘過程中各參與單位需要聯機操作且要花費較多的計算和通訊成本，使得方法的執行效率不佳。本文針對關聯規則挖掘技術，提出適用于數據水平分割的安全多方挖掘方法，挖掘過程中利用信息安全技術對各方數據進行處理，再將整體數據匯集到一個計算中心單位進行集中式挖掘，通過此方法，不僅能確保各參與挖掘單位的數據隱私，還可以有效準確地獲得整體數據的挖掘結果，達到安全多方挖掘的目的。

1 安全多方計算技術

安全多方計算技術適用于多單位合作的情況，其主要目的是確保各單位原始數據內容在挖掘過程中不被泄露，并在挖掘完成后共同得到整體數據的挖掘結果。現行方法設計均采用分布式挖掘，常用技術有安全聯集、安全和和安全純量乘積[5]等。

安全聯集技術通過加密機制在未知各單位所擁有項目內容的情況下，安全地求得各單位的項目內容聯集結果。執行過程為各單位先通過非對稱加密機制產生一對金鑰，然后通過其加密金鑰對所屬項目內容進行加密，并傳送到尚未對此項目內容加密的單位，最后，各單位共同對已加密的項目進行解密，即可求得各單位的項目內容聯集結果。安全和技術中各單位擁有一個特定數值，通過在計算中加入隨機數安全地求得各單位的數值和。執行過程為各單位先協商一個啟始單位，啟始單位負責產生一個隨機數并將其加入自身所擁有的數值，然后傳送到第二個單位，第二個單位將所接收的數值加上其擁有的數值后，傳送到第三個單位，依此類推。通過此方式各單位順序加入所屬數值后，最終單位將求和計算結果再傳送到啟始單位，扣除隨機數值后，即可安全地求得各單位的數值和。安全純量乘積技術適用于兩單位間的合作，雙方利用隨機數干擾其持有的純量內容，經多個步驟的計算后，安全地求出純量相乘結果。

上述多方計算技術可以很好地保護參與挖掘單位的數據隱私，精確地求得全部單位數據中符合閾值要求的關聯規則;過程中沒有隱藏不完全、遺失規則及多余規則等問題產生。但由于方法使用的安全技術本身的原因，導致參與合作單位的數量受到限制。另外，多單位合作挖掘采用在線分布式模式，在過程中需要花費較多的通訊和計算成本，執行效率欠佳。針對上述不足，本文提出的方法不僅沒有合作挖掘單位數量的限制，而且所有參與合作挖掘的單位并不需要同時聯機操作。采用這種集中式挖掘能降低各參與挖掘單位的通訊與計算量，提高方法整體挖掘效能，達到隱私保護與執行效能兼顧的目的。

2 數據水平分割的安全多方關聯規則挖掘方法

2.1 方法設計

本文方法主要針對數據水平分割的數據庫設計，方法中除了參與挖掘的各方外，還增加了一個計算中心負責匯集各單位交易記錄進行關聯規則挖掘。各單位將交易記錄傳送到計算中心前，先通過諸如非對稱加密、隨機化處理、異或運算等信息安全技術進行數據處理，以確保數據的隱私性。

方法執行包括3個階段，分別為初始階段、數據匯集階段和挖掘階段。方法中所使用的符號如下所示:

Pc 計算中心的公開金鑰

Xc 計算中心的私密金鑰

Ri 計算中心產生單位i的隨機數

R′ij 參與挖掘單位i產生其交易記錄區塊j的隨機數

EP() 利用公開金鑰P進行加密

DX() 利用私密金鑰X進行解密

 異或運算

2.1.1 初始階段

計算中心先對各參與挖掘單位i產生一串與其項目欄位總數相同的布爾型隨機數Ri(i為單位名稱)，并通過安全渠道傳送給各單位，計算中心與各單位間共享一把公開金鑰Pc。

2.1.2 數據匯集階段

(1)單位i將其交易記錄分割成多個區塊，對每個區塊交易記錄產生一串與項目欄位總數相同的布爾型隨機數R′ij(j為各區塊交易記錄編號)。例如單位A總交易記錄量有100筆，若平均分割成5部分，則每區塊有20筆交易記錄，再對應產生隨機數R′A1、R′A2、R′A3、R′A4與R′A5。各單位分割交易記錄的設計主要是為了避免數據匯集過程中各單位總交易記錄量的泄露，從而提高數據內容的安全性。

(2)為了達到交易數據來源隱藏的目的，單位i可先將從計算中心接收的Ri與自身產生的R′ij進行異或運算，然后再利用異或(RiR′ij)運算結果對其所有交易記錄進行異或運算。

(3)單位i分別對Ri和每個R′ij用計算中心提供的公開金鑰Pc進行加密，并將其附加于各交易記錄區塊前，再將已處理的各個交易記錄區塊，分別傳送到其它參與挖掘的單位。

(4)當單位i接收到已保護的交易記錄區塊時，利用其異或(RiR′ij)運算結果對區塊內每筆交易記錄進行異或運算，并在交易記錄區塊前附上其已加密的隨機數EPc(Ri)和EPc(R′ij)，再將此交易記錄區塊傳送到尚未進行處理的單位。

(5)重復步驟(4)，直到所有單位都對交易記錄區塊處理完畢，然后由最后處理該交易記錄區塊的單位將數據傳送到計算中心，進行交易記錄數據的匯集。

2.1.3 挖掘階段

計算中心將所有參與挖掘單位匯集的交易記錄經還原處理后，利用關聯規則挖掘技術，依據定義的支持度和置信度閾值，從整體交易記錄中挖掘出所有符合條件的關聯規則，然后將挖掘結果報告傳給各參與挖掘單位。計算中心還原已保護的交易記錄的原理是基于每筆交易記錄都已在參與挖掘單位進行了Ri與R′ij的異或運算，根據異或運算相同內容兩次異或運算可抵消的特性，計算中心在獲取任一交易記錄區塊前附上的加密內容并利用其私密金鑰Xc進行解密后，再將其對各筆已保護的交易記錄進行異或運算，即可還原整體交易記錄內容。另外，計算中心為確保接收的交易記錄內容來自于參與挖掘的單位，可根據附加于交易記錄區塊前的加密內容，經解密后判斷是否存在事先傳送給各挖掘單位的隨機數Ri，以避免接收到非參與挖掘單位的數據。

2.2 方法安全性及效率分析

2.2.1 安全性分析

在挖掘中各參與挖掘單位數據隱私是否泄露是衡量本方法安全性的關鍵所在。方法執行過程中由計算中心匯集各參與挖掘單位的交易數據，由于所有參與挖掘單位都已對各個交易記錄區塊做過隨機化加密處理，加上各區塊傳遞處理的順序不同，使得各單位數據在傳送到其它單位時不會造成數據隱私的泄露。同時，計算中心也無法從中辨識出各交易記錄區塊原先所屬單位，計算中心僅知道全體數據的挖掘結果，從而無法回推出各參與挖掘單位的隱私數據，包括交易記錄內容、數據集大小、頻繁項目集等，從而達到隱藏數據來源的目的。另外，方法在兩單位合作挖掘時，數據來源等隱私信息存在被計算中心泄漏的可能，因為在雙方數據匯集的過程中，當一單位傳送已處理的交易記錄區塊到計算中心時，計算中心即可判斷此數據為另一單位所擁有。因此，方法為能克服使用單位的限制，針對兩單位合作挖掘提出一個改進方式，在原方法中新增一個存儲中心，當兩個單位都處理完交易記錄區塊后，先傳送至存儲中心進行數據匯集，再通過存儲中心將全部交易數據轉送到計算中心進行挖掘。由于存儲中心所接收的交易數據都已由兩單位先行進行加密處理，可確保兩單位數據隱私的安全，同時，計算中心是接收存儲中心所匯集的整體交易數據，無法獲知數據的來源單位。

2.2.2 效率分析

方法執行過程中由計算中心匯集所有參與合作挖掘單位的交易數據，采用集中式挖掘方式挖掘出整體交易數據中的有用信息，此模式將挖掘所需要耗費的繁重計算量轉移到計算中心，與分布式合作挖掘過程中各單位需負荷過多的通訊和計算量相比較，可有效地減輕各單位的通訊和計算成本，提高整體挖掘的效率。以下就方法中各參與挖掘單位的通訊和計算量進行分析。

(1)通訊量:方法在數據匯集階段，各參與挖掘單位需將其分割的交易記錄區塊與其它單位互換以進行處理，處理完成后再傳送匯集到計算中心。因此，各參與挖掘單位的通訊量僅取決于全部單位分割交易記錄區塊的總數。

(2)計算量:盡管繁重的挖掘計算量由計算中心執行，但方法在數據匯集階段為能達到隱藏交易數據來源的目的，各參與挖掘單位需要對全體交易記錄區塊進行處理。方法中各單位i利用其隨機數Ri和R'ij對全體交易記錄內容進行簡單的異或運算，并在交易記錄區塊前附上隨機數Ri和R′ij的加密內容，雖然方法設計采用非對稱加密系統，在運行時會有較復雜的指數運算量，但對各參與挖掘單位不會造成過重的負擔，因為各單位附加于交易記錄區塊前的加密內容是相同的，各單位只需要對其隨機數進行一次加密即可。因此，各參與挖掘單位的主要計算量仍集中在全體交易數據內容的異或運算上，由于異或運算的簡單快速，故能有效地減輕各單位的運算量負荷。

3 結束語

本文提出了一個適用于水平分割數據的安全多方關聯規則挖掘方法，方法在多方合作的基礎上采用集中式挖掘，新增一個計算中心分攤各參與合作挖掘單位的計算量，以提高整體挖掘的執行效率，在匯集各單位交易數據的過程中，引入信息安全技術，并針對兩單位合作挖掘時的隱私保護提供了引進存儲中心的改進方法。本文方法在確保各單位交易數據隱私的前提下，能準確地挖掘出符合條件的關聯規則，達到提高執行效率和保護隱私的目的。

參考文獻

[1]Verykios VS，Bertino E，Fovino IN，Provenza LP，Saygin Y，Theodoridis Y.State-of-the-Art in privacy preserving data mining[J].SIGMOD Record，2004，33(1):50-57.

[2]Han J，Kamber M.Data Mining:Concepts and Techniques.Beijing:China Machine Press，2001(in Chinese).

[3]Kantarcioglou，M.and Clifton，C..Privacy-Preserving Distributed Mining of Association Rules on Horizontally Partitioned Data.Proceedings of the ACM SIGMOD Workshop on Research Issues in Data Engineering(RIDE)，2002:24-31.

[4]Vaidya，J.and Clifton，C..Privacy Preserving Association in Vertically Partitioned Data.Proceedings of the 8th ACM SIGKDD 118 International Conference on Knowledge Discovery and Data Mining，2002:639-644.

[5]Clifton，C.，Kantarcioglou，M.，Lin，X.，and Zhu，M.Y..Tools for Privacy Preserving Distributed Data Mining[J].Proceedings of the ACM SIGKDD Explorations Newsletter，2002，4(2):28-34.