K-匿名隱私保護(hù)模型中不確定性數(shù)據(jù)的查詢問題.pdf

1、在網(wǎng)絡(luò)信息技術(shù)快速發(fā)展的今天，人們?cè)谙硎苤l(fā)布和獲取信息、數(shù)據(jù)的便捷和高效同時(shí)，也在承受著隨之而來的隱私泄露的風(fēng)險(xiǎn)。隱私保護(hù)的常用手段是對(duì)有可能被探密者利用的數(shù)據(jù)進(jìn)行不確定性變換，以減少隱私泄露的風(fēng)險(xiǎn)。k-匿名隱私保護(hù)模型是數(shù)據(jù)發(fā)布者常用的隱私保護(hù)模型，滿足k-匿名要求的不確定性數(shù)據(jù)在互聯(lián)網(wǎng)上越來越多。
　　 在k-匿名隱私保護(hù)模型中，每條元組不僅包括精確數(shù)據(jù)，還包括泛化數(shù)據(jù)，因此k-匿名數(shù)據(jù)是一種不確定數(shù)據(jù)。但k-匿名數(shù)據(jù)又是

2、一種特殊的不確定性數(shù)據(jù)，它是人為泛化后的不確定性數(shù)據(jù)，泛化后的每個(gè)實(shí)例還原成泛化前元組的概率是相等的。
　　 經(jīng)典的數(shù)據(jù)庫模型和管理系統(tǒng)都沒有考慮數(shù)據(jù)的不確定性，如何管理和查詢?cè)从趉-匿名隱私保護(hù)模型的不確定性數(shù)據(jù)是一個(gè)亟待解決的問題。
　　 首先，基于可能世界模型，根據(jù)k-匿名數(shù)據(jù)的特點(diǎn)，提出了一種新的描述k-匿名數(shù)據(jù)的不確定性數(shù)據(jù)模型kpro-table，該模型具有良好的可讀性與描述能力，并證明了其完備的;其次，分析

3、了k-匿名數(shù)據(jù)的查詢語義，形式化的給出了k-匿名數(shù)據(jù)的成員(Membership)問題、可能性(Possibility)問題、確定性(Certainty)問題、包含(Containment)問題等查詢問題的定義;再次，從計(jì)算理論的角度，通過多項(xiàng)式時(shí)間歸約的方法，分別證明了Membership問題是PTIME，q-Membership問題是NP-完全的，q'-Containment問題是NP-完全的，q-Containment問題coNP