加密數(shù)據(jù)的k近鄰查詢算法研究.pdf

1、近年來，隨著云服務的興起，許多擁有剩余計算資源、存儲資源的公司利用其多余的資源為廣大用戶提供云服務，例如阿里云、Amazon Relational Database Service(AmzaonRDS)等。一些擁有數(shù)據(jù)的公司或者個人，介于其計算資源的限制或者從公司整體利益考慮，會選擇將其數(shù)據(jù)托付給提供云服務的公司進行處理。為了保證這些擁有數(shù)據(jù)的用戶的利益，在將數(shù)據(jù)上傳到云服務提供商之前，需要將數(shù)據(jù)加密，這樣可以防止云服務提供商損害其利益

2、。但是云服務提供商在加密的數(shù)據(jù)上執(zhí)行查詢等操作將會變得困難，所以能夠提供一種高效且安全的方法來解決這一問題十分必要。本文主要研究的是云服務提供商如何在加密的數(shù)據(jù)上完成用戶的k近鄰查詢請求，并且保證在這個過程中數(shù)據(jù)不被云服務提供商竊取。
　　目前很多研究者針對這一問題做了研究，具體的研究方法可以分為兩類。第一類是通過將數(shù)據(jù)構建成某種特殊的數(shù)據(jù)結構，然后采取適當?shù)牟檎也呗?，完成查找操作。第二類是通過研究加密算法使得密文數(shù)據(jù)之間的距離與

3、明文數(shù)據(jù)間距離存在特定關系，這樣只需要通過密文的計算便可完成查找操作。在這些方法中主要存在兩個問題。第一個問題是安全問題，在計算過程中攻擊者能夠通過一些特殊的攻擊手段獲取到明文內(nèi)容;第二個是效率問題，一些工作主要將研究重點放到了數(shù)據(jù)安全方面，忽略了查詢效率問題。
　　本文針對以上問題主要從兩個方面進行考慮:首先是查詢效率，解決查詢效率問題對于提高用戶體驗、節(jié)省計算資源都十分必要，所以本文采用了一種基于層次聚類的k近鄰查詢算法來實驗