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

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

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

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