基于LBS(位置服務)的隱私保護算法研究

黃小英

（廣西工商職業(yè)技術學院，南寧 530003）

基于LBS(位置服務)的隱私保護算法研究

黃小英

（廣西工商職業(yè)技術學院，南寧 530003）

0 引言

數(shù)據(jù)挖掘和數(shù)據(jù)發(fā)布是當前數(shù)據(jù)庫應用的兩個重要方面。一方面，數(shù)據(jù)挖掘與知識發(fā)現(xiàn)在各個領域都扮演著非常重要的角色。數(shù)據(jù)挖掘的目的在于從大量的數(shù)據(jù)中抽取出潛在的、有價值的知識（模型或規(guī)則）。傳統(tǒng)的數(shù)據(jù)挖掘技術在發(fā)現(xiàn)知識的同時，也給數(shù)據(jù)的隱私帶來了威脅。另一方面，數(shù)據(jù)發(fā)布是將數(shù)據(jù)庫中的數(shù)據(jù)直接地展現(xiàn)給用戶。而在各種數(shù)據(jù)發(fā)布應用中，如果數(shù)據(jù)發(fā)布者不采取適當?shù)臄?shù)據(jù)保護措施，將可能造成敏感數(shù)據(jù)的泄漏，從而給數(shù)據(jù)所有者帶來危害。所以，如何在各種數(shù)據(jù)庫應用中保護數(shù)據(jù)的隱私，成為近年來學術界的研究熱點。

1 隱私保護技術的分類與性能評估

1.1 隱私保護技術的分類

沒有任何一種隱私保護技術適用于所有應用。隱私保護技術分為三類：

1）基于數(shù)據(jù)失真（Distorting）的技術：使敏感數(shù)據(jù)失真但同時保持某些數(shù)據(jù)或數(shù)據(jù)屬性不變的方法。例如，采用添加噪聲（Adding Noise）、交換（Swapping）等技術對原始數(shù)據(jù)進行擾動處理，但要求保證處理后的數(shù)據(jù)仍然可以保持某些統(tǒng)計方面的性質，以便進行數(shù)據(jù)挖掘等操作。

2）基于數(shù)據(jù)加密的技術：采用加密技術在數(shù)據(jù)挖掘過程中隱藏敏感數(shù)據(jù)的方法。多用于分布式應用環(huán)境中，如安全多方計算（Secure Multiparty Computation，以下簡稱SMC）。

3）基于限制發(fā)布的技術：根據(jù)具體情況有條件地發(fā)布數(shù)據(jù)。如：不發(fā)布數(shù)據(jù)的某些域值，數(shù)據(jù)泛化（Generalization）等。

1.2 隱私保護技術的性能評估

隱私保護技術需要在保護隱私的同時，兼顧對應用的價值以及計算開銷。通常從以下三方面對隱私保護技術進行度量：

1）隱私保護度：通常通過發(fā)布數(shù)據(jù)的披露風險來反映，披露風險越小，隱私保護度越高。

2）數(shù)據(jù)缺損：是對發(fā)布數(shù)據(jù)質量的度量，它反映通過隱私保護技術處理后數(shù)據(jù)的信息丟失：數(shù)據(jù)缺損越高，信息丟失越多，數(shù)據(jù)利用率（Utility）越低。具體的度量有：信息缺損（Information Loss）、重構數(shù)據(jù)與原始數(shù)據(jù)的相似度等。

3）算法性能：一般利用時間復雜度對算法性能進行度量。例如，采用抑制（Suppression）實現(xiàn)最小化的k-匿名問題已經證明是NP-hard問題；時間復雜度為O(k)的近似k-匿名算法，顯然優(yōu)于復雜度為O(klogk)的近似算法。均攤代價（Amortized Cost）是一種類似于時間復雜度的度量，它表示算法在一段時間內平均每次操作所花費的時間代價。除此之外，在分布式環(huán)境中，通訊開銷（Communication Cost）也常常關系到算法性能，常作為衡量分布式算法性能的一個重要指標。

2 基于數(shù)據(jù)失真的隱私保護技術

數(shù)據(jù)失真技術通過擾動（Perturbation）原始數(shù)據(jù)來實現(xiàn)隱私保護。它要使擾動后的數(shù)據(jù)同時滿足：

1）攻擊者不能發(fā)現(xiàn)真實的原始數(shù)據(jù)，也就是說，攻擊者通過發(fā)布的失真數(shù)據(jù)不能重構出真實的原始數(shù)據(jù)。

2）失真后的數(shù)據(jù)仍然保持某些性質不變，即利用失真數(shù)據(jù)得出的某些信息等同于從原始數(shù)據(jù)上得出的信息。這就保證了基于失真數(shù)據(jù)的某些應用的可行性。

2.1 隨機化

數(shù)據(jù)隨機化即是對原始數(shù)據(jù)加入隨機噪聲，然后發(fā)布擾動后數(shù)據(jù)的方法。需要注意的是，隨意對數(shù)據(jù)進行隨機化并不能保證數(shù)據(jù)和隱私的安全，因為利用概率模型進行分析常常能披露隨機化過程的眾多性質。隨機化技術包括兩類：隨機擾動（Random Perturbation）和隨機化應答（Randomized Response）。

2.2 隨機擾動

隨機擾動采用隨機化過程來修改敏感數(shù)據(jù)，從而實現(xiàn)對數(shù)據(jù)隱私的保護。一個簡單的隨機擾動模型如表1(a)所示。

對外界而言，只可見擾動后的數(shù)據(jù)，從而實現(xiàn)了對真實數(shù)據(jù)值的隱藏。但擾動后數(shù)據(jù)仍然保留著原始數(shù)據(jù)分布X的信息，通過對擾動后的數(shù)據(jù)進行重構如表1(b)所示，可以恢復原始數(shù)據(jù)分布X的信息。但不能重構原始數(shù)據(jù)的精確值x1,x2,…,xn。

表1 隨機擾動與重構過程

隨機擾動技術可以在不暴露原始數(shù)據(jù)的情況下進行多種數(shù)據(jù)挖掘操作。由于通過擾動數(shù)據(jù)重構后的數(shù)據(jù)分布幾乎等同于原始數(shù)據(jù)的分布，因此利用重構數(shù)據(jù)的分布進行決策樹分類器訓練后，得到的決策樹能很好地對數(shù)據(jù)進行分類。在關聯(lián)規(guī)則挖掘中，通過往原始數(shù)據(jù)注入大量偽項（False Item）來對頻繁項集進行隱藏，再通過在隨機擾動后的數(shù)據(jù)上估計項集支持度，從而發(fā)現(xiàn)關聯(lián)規(guī)則。除此之外，隨機擾動技術還可以應用到OLAP上實現(xiàn)對隱私的保護。

2.3 隨機化應答

隨機化應答的基本思想是：數(shù)據(jù)所有者對原始數(shù)據(jù)擾動后發(fā)布，使攻擊者不能以高于預定閥值的概率得出原始數(shù)據(jù)是否包含某些真實信息或偽信息。雖然發(fā)布的數(shù)據(jù)不再真實，但在數(shù)據(jù)量比較大的情況下，統(tǒng)計信息和匯聚（Aggregate）信息仍然可以較為精確地被估算出。隨機化應答技術與隨機擾動技術的不同之處在于敏感數(shù)據(jù)是通過一種應答特定問題的方式間接提供給外界的。

隨機化應答模型有兩種：相關問題模型（Related-Question Model）和非相關問題模型（Unrelated-Question Model）。相關問題模型是通過設計兩個關于敏感數(shù)據(jù)的對立問題，

3 基于數(shù)據(jù)加密的隱私保護技術

在分布式環(huán)境下實現(xiàn)隱私保護要解決的首要問題是通訊的安全性，而加密技術正好滿足了這一需求，因此基于數(shù)據(jù)加密的隱私保護技術多用于分布式應用中，如分布式數(shù)據(jù)挖掘、分布式安全查詢、幾何計算、科學計算等。在分布式下，具體應用通常會依賴于數(shù)據(jù)的存儲模式和站點（Site）的可信度及其行為。

分布式應用采用兩種模式存儲數(shù)據(jù)：垂直劃分（Vertically Partitioned）的數(shù)據(jù)模式和水平劃分（Horizontally Partitioned）的數(shù)據(jù)模式。垂直劃分數(shù)據(jù)是指分布式環(huán)境中每個站點只存儲部分屬性的數(shù)據(jù)，所有站點存儲的數(shù)據(jù)不重復；水平劃分數(shù)據(jù)是將數(shù)據(jù)記錄存儲到分布式環(huán)境中的多個站點，所有站點存儲的數(shù)據(jù)不重復。

對分布式環(huán)境下的站點（參與者），根據(jù)其行為，可分為：準誠信攻擊者（Semihonest Adversary）和惡意攻擊者（Malicious Adversary）：準誠信攻擊者是遵守相關計算協(xié)議但仍試圖進行攻擊的站點；惡意攻擊者是不遵守協(xié)議且試圖披露隱私的站點。一般地，假設所有站點為準誠信攻擊者。

3.1 安全多方計算

眾多分布環(huán)境下基于隱私保護的數(shù)據(jù)挖掘應用都可以抽象為無信任第三方（Trusted Third Party）參與的SMC問題，即怎樣使兩個或多個站點通過某種協(xié)議完成計算后，每一方都只知道自己的輸入數(shù)據(jù)和所有數(shù)據(jù)計算后的最終結果。

可以證明，由于采用了可交換加密技術的順序無關性，在整個求集合并集的過程中，除了集合交集的大小和最終結果被披露外，沒有其它私有信息泄露，所以該計算集合并的方法是安全的。

由于多數(shù)SMC基于“準誠信模型”假設之上，因此應用范圍有限。SCAMD（Secure Centralized Analysis of Multi-party Data）協(xié)議在去除該假設基礎上，引入準誠信第三方實現(xiàn)當站點都是惡意時進行安全多方計算；文獻[6]提出拋棄傳統(tǒng)分布式環(huán)境下對站點行為約束的假設，轉而根據(jù)站點的動機，將站點分為弱惡意攻擊者和強惡意攻擊者，用可交換加密技術解決在分布環(huán)境下的信息共享問題。

當前，關于SMC的主要研究工作集中于降低計算開銷、優(yōu)化分布式計算協(xié)議以及以SMC為工具解決問題等。

3.2 分布式匿名化

匿名化即是隱藏數(shù)據(jù)或數(shù)據(jù)來源。因為對大多數(shù)應用而言，首先需要對原始數(shù)據(jù)進行處理以保證敏感信息的安全；然后再在此基礎上，進行數(shù)據(jù)挖掘、發(fā)布等操作。分布式下的數(shù)據(jù)匿名化都面臨在通訊時，如何既保證站點數(shù)據(jù)隱私又能收集到足夠的信息來實現(xiàn)利用率盡量大的數(shù)據(jù)匿名。

以在垂直劃分的數(shù)據(jù)環(huán)境下實現(xiàn)兩方的分布式k-匿名為例。兩個站點S1和S2，它們擁有的數(shù)據(jù)分別為{ID,A11,A12,...,A1n1}，{ID,A21,A22,...,A2n1}。其中Aij為Si擁有數(shù)據(jù)的第j個屬性。利用可交換加密在通訊過程中隱藏原始信息，再構建完整的匿名表判斷是否滿足k-匿名條件來實現(xiàn)。

4 結論

隱私保護技術在諸多領域都有廣泛的應用，是近年來學術界新興的研究課題。本文側重數(shù)據(jù)庫應用，對隱私保護技術的研究現(xiàn)狀進行綜述。首先給出了隱私及其度量的定義，然后在對已有的隱私保護技術進行分類的基礎上，介紹了基于失真、加密和匿名化的三大類隱私保護技術，特別是，對當前隱私保護領域的研究熱點“基于數(shù)據(jù)匿名化的隱私技術”進行了比較詳盡的闡述與分析。

容易看出，每類隱私保護技術都有不同的特點，在不同應用需求下，它們的適用范圍、性能表現(xiàn)等不盡相同。當針對特定數(shù)據(jù)實現(xiàn)隱私保護且對計算開銷要求比較高時，基于數(shù)據(jù)失真的隱私保護技術更加適合；當更關注于對隱私的保護甚至要求實現(xiàn)完美保護時，則應該考慮基于數(shù)據(jù)加密的隱私保護技術，但代價是較高的計算開銷（在分布式環(huán)境下，還會增加通訊開銷）。而數(shù)據(jù)匿名化技術在各方面都比較平衡：能以較低的計算開銷和信息缺損實現(xiàn)對隱私保護。

[1]J.Han and M.Kamber.Data Mining:Concepts and Techniques.2nd edition,San Francisco:Morgan Kaufmann Publishers,2006.

[2]D.Agrawal and C.C.Aggarwal.On the Design and Quantification of Privacy Preserving Data Mining Algorithms. In Sym.on Principles of Database Systems (PODS),Santa Barbara, California,USA,2001:247-255.

[3]張鵬,童云海,唐世渭,楊冬青,馬秀莉.一種有效的隱私保護關聯(lián)規(guī)則挖掘方法[J].軟件學報,2006,17(8):1764-1774.

[4]羅永龍,黃劉生,荊巍巍,姚亦飛,陳國良.一個保護私有信息的布爾關聯(lián)規(guī)則挖掘算法[J].電子學報,2005,33(5):900-903.

The privacy preservation study based on LBS

HUANG Xiao-ying

隨著數(shù)據(jù)挖掘和數(shù)據(jù)發(fā)布等數(shù)據(jù)庫應用的出現(xiàn)與發(fā)展，如何保護隱私數(shù)據(jù)和防止敏感信息泄露成為當前面臨的重大挑戰(zhàn)。隱私保護技術需要在保護數(shù)據(jù)隱私的同時不影響數(shù)據(jù)應用。根據(jù)采用技術的不同，出現(xiàn)了數(shù)據(jù)失真、數(shù)據(jù)加密、限制發(fā)布等隱私保護技術。

隱私保護；隨機化；安全計算

黃小英（1976 -），女，廣西寧明人，講師，工程碩士，研究方向為計算機應用。

TP312

A

1009-0134(2011)5(上)-0096-03

10.3969/j.issn.1009-0134.2011.5(上).33

2011-01-05