基于LBS位置服務(wù)的隱私保護(hù)算法研究.doc

《基于LBS位置服務(wù)的隱私保護(hù)算法研究.doc》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫。

1、TheprivacypreservationstudybasedonLBS黃小英HUANGXiao-ying(廣西工商職業(yè)技術(shù)學(xué)院，南寧530003)摘要：隨著數(shù)據(jù)挖掘和數(shù)據(jù)發(fā)布等數(shù)據(jù)庫應(yīng)用的出現(xiàn)與發(fā)展?如何保護(hù)隱私數(shù)據(jù)和防止敏感信息泄廳成為當(dāng)前面臨的重大挑戰(zhàn)。隱私保護(hù)技術(shù)需要在保護(hù)數(shù)據(jù)隱私的同時不影響數(shù)據(jù)應(yīng)用。根振采用技術(shù)的不同?出現(xiàn)了數(shù)據(jù)失真、數(shù)據(jù)加密'限制發(fā)布等隱私保護(hù)技術(shù)。尖鍵詞：隱私保護(hù)；隨機(jī)化；安全計算中圖分類號：TP312文獻(xiàn)標(biāo)識碼：ADoi:10.3969/j.issn,1009-0134.2011.5(上).330引言數(shù)據(jù)挖掘和數(shù)據(jù)發(fā)布是當(dāng)前數(shù)據(jù)庫應(yīng)用的兩

2、個重要方而。一方而，數(shù)據(jù)挖掘與知識發(fā)現(xiàn)在各個領(lǐng)域都扮演著非常重要的角色。數(shù)據(jù)挖掘的目的在于從大量的數(shù)拯中抽取出潛在的、有價值的知識(模型或規(guī)則)C傳統(tǒng)的數(shù)據(jù)挖掘技術(shù)在發(fā)現(xiàn)知識的同時，也給數(shù)據(jù)的隱私帶來了威脅。另八方血，數(shù)據(jù)發(fā)布是將數(shù)據(jù)庫中的數(shù)據(jù)直接地展現(xiàn)給用戶。而在各種數(shù)據(jù)發(fā)布應(yīng)用中，如果數(shù)據(jù)發(fā)布者不釆取適當(dāng)?shù)臄?shù)據(jù)保護(hù)措施，將可能造成敏感數(shù)據(jù)的泄漏，從而給數(shù)摒所有者帶來危害。所以，如何在各種數(shù)據(jù)庫應(yīng)用中保護(hù)數(shù)據(jù)的隱私，成為近年來學(xué)術(shù)界的研究熱點。1隱私保護(hù)技術(shù)的分類與性能評估1.1隱私保護(hù)技術(shù)的分類沒有任何一種隱私保護(hù)技術(shù)適用于所有應(yīng)用。隱私保護(hù)技術(shù)分為三類：1)基于數(shù)據(jù)失

3、真(Distorting)的技術(shù)：使敏感數(shù)據(jù)失真但同時保持某些數(shù)據(jù)或數(shù)據(jù)屬性不變的方法。例如，采用添加噪聲(AddingNoise)、交換(Swapping)等技術(shù)對原始數(shù)據(jù)進(jìn)行擾動處理，但要求保證處理后的數(shù)據(jù)仍然可以保持某些統(tǒng)計方血的性質(zhì)，以便進(jìn)行數(shù)據(jù)挖掘等操作。2)基于數(shù)據(jù)加密的技術(shù)：采用加密技術(shù)在數(shù)據(jù)挖掘過程屮隱藏敏感數(shù)據(jù)的方法。多用于分布式應(yīng)用環(huán)境中，如安全多方計算(SecuiyMultipartyComputation,以下簡稱SMC)。文章編號:1009-0134(2011)5(1)-0096-033)基于限制發(fā)布的技術(shù)：根據(jù)具體情況有條件地發(fā)布數(shù)據(jù)。如：不發(fā)布

4、數(shù)據(jù)的某些域值，數(shù)據(jù)泛化(Generalization)等。1.2隱私保護(hù)技術(shù)的性能評估隱私保護(hù)技術(shù)需要在保護(hù)隱私的同時，兼顧對應(yīng)用的價值以及計算開銷。通常從以下三方面對隱私保護(hù)技術(shù)進(jìn)行度量：1)隱私保護(hù)度：通常通過發(fā)布數(shù)據(jù)的披露風(fēng)險來反映，披露風(fēng)險越小，隱私保護(hù)度越髙°2)數(shù)據(jù)缺損：是對發(fā)布數(shù)據(jù)質(zhì)量的度量，它反映通過隱私保護(hù)技術(shù)處理后數(shù)據(jù)的信息丟失：數(shù)據(jù)缺損越高，信息丟失越多，數(shù)據(jù)利用率(Utility)越低。具體的度量有：信息缺損(InformationLoss)、重構(gòu)數(shù)據(jù)與原始數(shù)扼的相似度等。3)算法性能：一般利用時間復(fù)雜度對算法性能進(jìn)行度量。例如，采用抑制(Supp

5、ression)實現(xiàn)最小化的k-匿名問題已經(jīng)證明是NP-hard問題；時間復(fù)雜度為0(k)的近似k-匿名算法，顯然優(yōu)于復(fù)朵度為O(klogk)的近似算法。均攤代價(AmortizedCost)是一種類似于時間復(fù)雜度的度量，它表示算法在一段時間內(nèi)平均每次操作所花費的時間代價。除此之外，在分布式環(huán)境小，通訊開銷(CommunicationCost)也常常關(guān)系到算法性能，常作為衡量分布式算法性能的一個重要指標(biāo)。2基于數(shù)據(jù)失真的隱私保護(hù)技術(shù)數(shù)據(jù)失真技術(shù)通過擾動(Perturbation)原始收稿日期:2011-01-05作者簡介：黃小英(1976-),女，廣西寧明人，講師,工稈碩士

6、,硏究方向為計算機(jī)應(yīng)用。數(shù)據(jù)來實現(xiàn)隱私保護(hù)。它要使擾動后的數(shù)據(jù)同時滿足：1)攻擊者不能發(fā)現(xiàn)真實的原始數(shù)據(jù)，也就是說，攻擊者通過發(fā)布的失真數(shù)據(jù)不能重構(gòu)出真實的原始數(shù)據(jù)乙2)失真后的數(shù)據(jù)仍然保持某些性質(zhì)不變，即利用失真數(shù)據(jù)得出的某些信息等同于從原始數(shù)據(jù)上得出的信息。這就保證了基于失真數(shù)據(jù)的某些應(yīng)用的可行性。2.1隨機(jī)化數(shù)據(jù)?隨機(jī)化即是對原始數(shù)據(jù)加入隨機(jī)噪聲，然后發(fā)布擾動后數(shù)據(jù)的方法。需耍注意的是，隨意對數(shù)據(jù)進(jìn)行隨機(jī)化并不能保證數(shù)據(jù)和隱私的安全，因為利用概率模型進(jìn)行分析常常能披露隨機(jī)化過程的眾多性質(zhì)。隨機(jī)化技術(shù)包括兩類：隨機(jī)擾動(RandomPerturbation)和隨機(jī)化應(yīng)答

7、(RandomizedResponse)。2.2隨機(jī)擾動隨機(jī)擾動采用隨機(jī)化過程來修改敏感數(shù)據(jù)，從而實現(xiàn)對數(shù)據(jù)隱私的保護(hù)。一個簡單的隨機(jī)擾動模型如表1(a)所示。對外界而言，只可見擾動后的數(shù)據(jù)，從而實現(xiàn)了對真實數(shù)據(jù)值的隱藏。但擾動后數(shù)據(jù)仍然保留著原始數(shù)據(jù)分布X的信息，通過對擾動后?的數(shù)扼進(jìn)行重構(gòu)如表1(b)所示，可以恢復(fù)原始數(shù)據(jù)分布X的信息。但不能重構(gòu)原始數(shù)據(jù)的精確值x“x2,…,x11C表1隨機(jī)擾動與巫構(gòu)過程(a)隨機(jī)擾動過程輸入1?原始數(shù)據(jù)為x1,x2,—,xri,服從于未知分布X；2.擾動數(shù)據(jù)為y1，丫2,??