近年來雲計算的廣泛應用，大量資料已經被存放在雲中。雖然雲服務提供了很多優點，敏感資料的隐私和安全問題仍然仍然讓人擔憂。為了消除這種擔憂，以加密的形式外包敏感資料是值得期待的管理方式。加密存儲防止對資料進行非法通路，但使得一些基本操作複雜化，如對資料的搜尋。在很多文獻中已經提出基于不危害隐私而實作對加密資料的搜尋的可搜尋加密方案。然而，大部分都是處理精确查詢比對，現實中應用最多的是相似性查詢。一些複雜的基于加密技巧的安全多方計算對相似性實驗是可利用的，但計算量大且不能對大資料源規模化，是以如何找到一種高效的方法非常重要。本文主要是分享一種對加密資料的高效的相似性搜尋方案：1.利用高維空間的快速近鄰搜尋算法局部敏感哈希（LSH）；2.提供了一種嚴格的安全定義來確定敏感資料的隐私性并證明方案在定義下的安全性。最後簡單介紹一下有關應用和實驗效果。
相似性搜尋的目标是在根據可選度量的給定門檻值，檢索某些對查詢項的相似性滿足給定門檻值的資料項。本文亮點如下：
1.安全LSH索引：基于LSH索引的可搜尋對稱加密方案：私鑰加密方式，保證Curtmola的适應語義安全定義下的安全。
2.對加密資料的容錯性搜尋：允許對有印刷錯誤的查詢集或資料集實作搜尋。
3.洩露資訊的分離：現有方案會洩露對應查詢陷門的加密資料的标号而導緻統計學的攻擊，是以可設定兩個伺服器來分離洩露資訊。查詢陷門好比是查詢進入資料集的入口，這裡可看做是查詢項的安全LSH索引值。
一、安全LSH索引
資料擁ＬＳＨ索引Ｉ并發送給雲端伺服器，本文采用AND-OR級聯的MinHash函數族來建立索引。過程如下：
第一步需要從敏感資料集中提取特征集合，如提取出abcdefg，john或johhn.
第二步需要使用轉換函數将文檔轉換成資料集合，
1.可對特征統計使用的比較簡單的算法
k-gram
算法，
k
是一個變量，表示提取文本中的k個字元，算法從頭依次掃描文本，然後依次把
k
個字元儲存起來，比如有個文本，内容是
abcdefg
,
k
設為2，那得到的子特征就是
ab,bc,cd,de,ef,fg
。
然後采用布隆過濾器(Bloom filter)編碼方法，即一種空間效率很高的随機資料結構，利用位數組很簡潔地表示一個集合，并能判斷一個元素是否屬于這個集合。但在判斷一個元素是否屬于某個集合時，有可能會把不屬于這個集合的元素誤認為屬于這個集合。是以可應用在能容忍低錯誤率的場合。
一個Bloom filter是有k個哈希函數的m位數組，分别将集合中每個元素映射到{1,...,m}的範圍中，初始時每位都置為0，如圖所示，這裡取k=2,即兩個哈希函數，轉換函數表達如：ρ(S) = {i | i ∈ L ∧ encode(S)[i] = 1}，文檔字元串為S，encode是一個編碼函數，L是m位的位數組，p是轉換函數。具體示例如下：
Jaccard距離：1減去Jaccad相似度，Jaccad相似度即
然後計算其Jaccard距離J（A，B）=1-6/7=0.14，
2.Minhash
兩個集合的随機的一個行排列的minhash值相等的機率和兩個集合的Jaccard相似度相等
證明如下：
兩個集合，A、B，對一行來說，他們的狀态有三種
X：A、B都為1，即表示A、B集合中都有這個單詞
Y：A、B其中一個為1，其中一個不為1，即一個有這個單詞，一個沒有
Z：A、B都為0，即表示A、B中都沒有這個單詞。
假設有x行為X，y行為Y，z行為z，這是jaccard系數為x/(x+y)。再看minhash，因為排列是随機的，在遇到Y之前遇到X的機率是x/(x+y)，正好等于jaccard系數的值。
定義如：Δ是位數組L的最大範圍，P是對Δ的一個随機排列，p[i]是P的第i個元素，如果該元素在集合R中，則将最先出現在R中的元素的i記為最小哈希值，hp(R)為最小哈希函數，hP (R) = min({i | 1 ≤ i ≤ |Δ| ∧ P[i] ∈ R})如：Δ = {i | 1 ≤ i ≤ 10}.P1 = {8, 3, 6, 1, 9, 5, 2, 4, 7, 10}，hP1 (ρ(john)) = 4 and hP1 (ρ(johhn)) = 3.
3. AND-OR級聯方式： 在局部敏感哈希家族H中選出k個哈希函數，構成哈希家族g。對于g家族中的g= [h1,…,hk]，g(x)=g(y)當且僅當對所有的i， 所有 hi(x)=hi(y)都滿足。在局部敏感哈希家族g中選出l個哈希哈數，構成哈希家族G。對于G家族中的g = [g1,…,gl]，G(x)=G(y)當且僅當存在i，滿足gi(x)=gi(y).
第三步是建構桶索引，假設使用上步中的哈希函數族H，通過g1,...,gl映射每個特征fj到l個桶中，gi(fj)記為索引桶的标号，桶内容是L位的位向量，設資料标号為1，...,L.id(Di)是資料Di的标号，Bk是桶标号，VBk是對應的位向量，那麼當gi(fj)=Bk時，Bk[id(Di)]=1否則為0。
第四步是桶索引加密，對Bk和VBk加密，前者在查詢過程中隻有使用者知道，否則敵手會利用LSH方法找到某個特征的桶，後者應該被加密來隐藏一些資訊洩露，如資料個數防止被敵手利用造成統計攻擊。
1.Kid, Kpayload ∈ {0, 1}ψ是參數為ψ的密鑰，分别為僞随機序列和PCPA（對可選明文攻擊的僞随機性）安全加密。I是安全索引，令[EncKid (Bk), EncKpayload (VBk )] ∈ I。一旦加密被做，還可以添加一些假記錄到索引中來隐藏資料庫中特征的數量。設總特征數目為Max，c是I中的記錄數，則可加入Max-c*l個假記錄到I中，然後将I發送給伺服器。
二、搜尋過程
兩輪互動搜尋：
1.資料擁有者A産生密鑰Kid, Kpayload and Kcoll.
2.A使用上步密鑰Kid, Kpayload對資料集D建構安全LSH索引。如一中所示。
3.A使用密鑰Kcoll（也是一個PCPA安全加密）對資料集加密得到ED，并将其和安全LSH索引發送給伺服器B，也就是外包資料給伺服器。為使得使用者C能夠從遠端伺服器實作對加密資料的檢索，A共享C：Kid，Kcoll，Kpayload，p(轉換函數)和g.
4.陷門建構：C有查詢f,使用轉換函數得到對應向量集合，運用g生成索引并用Kid加密（Kid(gi(fj))），得到對應的l個陷門Tfj，将其發送給伺服器B。
5.搜尋：B根據Tfj執行搜尋，并将對應的EncKpayload (VBk )發送給C，
6.排序：C使用Kpayload對EncKpayload (VBk )解密，對于所有Bk中VBk[i]為1的的i累加得到score(i),并傳回t個最大score的id清單給B。
7.B找到加密資料集中對應id的資料并發送給C，C解密即可得到需要的資料。
需要兩輪互動查詢，像大部分可搜尋加密方案一樣會使的對應陷門的資料标号洩露，但是這種洩露的安全陷阱還沒有深度分析過，是以可以在不損失查詢性能前提下隐藏陷門和資料标号之間的結合，使用兩台伺服器來實作搜尋。
一輪搜尋：
1.A建構安全LSH索引時，對VBk使用同态加密Kpub,
2.C将陷門Tfj和參數t發送給B1
3.B1根據陷門使用Kpub對VBk[i]為1的項實作同态加，得到加密的wscore(i),将其發送給B2，
4.B2使用Kpriv對wscore(i)解密，将t個加密資料的标号發送給C，C解密即可得到需要的資料。
當資料項很小，特征數很多時可采用一輪搜尋，因為伺服器的計算和帶寬開銷與資料數目成線性關系。
三應用執行個體
對加密資料的錯誤感覺關鍵字搜尋
四實驗評估
在公開的郵件資料Enron資料集上實驗，随機選擇5000封郵件，由于使用LSH檢索效果非常好，特征數目的增加不影響搜尋時間和通信開銷（陷門，加密的位向量和資料标号）。
參考文獻：Efficient Similarity Search over Encrypted Data