近年来云计算的广泛应用，大量数据已经被存放在云中。虽然云服务提供了很多优点，敏感数据的隐私和安全问题仍然仍然让人担忧。为了消除这种担忧，以加密的形式外包敏感数据是值得期待的管理方式。加密存储防止对数据进行非法访问，但使得一些基本操作复杂化，如对数据的搜索。在很多文献中已经提出基于不危害隐私而实现对加密数据的搜索的可搜索加密方案。然而，大部分都是处理精确查询匹配，现实中应用最多的是相似性查询。一些复杂的基于加密技巧的安全多方计算对相似性实验是可利用的，但计算量大且不能对大数据源规模化，因此如何找到一种高效的方法非常重要。本文主要是分享一种对加密数据的高效的相似性搜索方案：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