2.加密信息检索技术

　　对加密信息检索的研究始于2000年，Song等人提出加密数据搜索的实用算法，Boneh等人提出基于关键词的公钥加密算法，Park等人提出安全索引搜索算法。

　　（1）线性搜索算法

　　在线性搜索算法中，首先用对称加密算法对明文信息加密。对于每个关键词对应的密文信息，生成一串长度小于密文信息长度的伪随机序列，并生成一由伪随机序列及密文信息确定的校验序列。伪随机序列的长度与检验序列长度之和等于密文信息的长度。伪随机序列及检验序列对密文信息再次加密。在搜索过程中，用户提交明文信息对应的密文信息序列。在服务器端，密文信息序列被线性地同每一段序列模2加。如果得到的结果满足校验关系，那么说明密文信息序列出现，否则，说明密文信息不存在。

　　线性搜索方法是一种一次一密的加密信息检索算法，因此有极强的抵抗统计分析的能力。但其有一个致命的缺点，即逐次匹配密文信息，这使得这种检索方法在大数据集的情况下难以应用。

　　（2）基于关键词的公钥搜索

　　基于关键词的公钥加密搜索算法由Boneh等人提出，其目的是可以在用户端存储、计算资源不足的情况下，通过访问远端数据库获取数据信息。存储、计算资源分布具有不对称性，即用户的计算存储能力不能实时满足其需求。另一方面用户在移动情况下存储、索引数据的需求也有增加，比如Email服务等。在这种特定情况下，需要保护用户的数据隐私。加密数据有多个不同来源，针对这一问题的解决方法是加密算法使用公钥加密。

　　算法的过程如下，首先生成公钥、私钥，然后对待存储的明文关键词用公钥进行加密，生成可搜索的密文信息。

　　（3）安全索引

　　安全索引由Park等人提出，解决了简单索引方式易受统计攻击的问题。其机制是每次加密所用的密钥是事先生成的一组逆Hash序列，加密后的索引被放入布隆过滤器中。当检索的时候，首先用逆Hash序列密钥生成多个陷门，然后进行布隆检测。对返回的密文文档解密即可得到所需检索的文档。

　　针对有新用户加入、旧用户退出的多用户加密信息检索，这是一种解决方法。但其存在的缺陷是需要生成大量的密钥序列，随着检索次数的增加，每多进行一次检索，其计算复杂度均线性增加。这在实际应用中很难被接受。

　　在以上提到的多种加密信息检索算法中，所用的检索模型都是布尔模型，因而无法根据查询与待检索文档的相关度进行排序操作。在实际情况中，尤其是在数据规模较大的云存储应用中，包含某一查询关键词的文档可能有很多个，如何在多个可能相关的文档中找出最相关的一个或若干个文档是需要解决的问题。对加密的文档，是否可以应用成熟的向量空间模型，进而进行相关排序，是一个开放的问题。

　　（4）引入相关排序的加密搜索算法

　　Swaminathan等人提出了保护隐私的排序搜索算法。在这一算法中，每一文档中关键词的词频都被保序加密算法加密。加密文档被提交查询给服务器端后，首先计算检索出含有关键词密文的加密文档;然后对用保序算法加密的词频对应的密文信息进行排序处理;最后把评价值高的加密文档返回给用户，由用户对其进行解密。

　　这一种方法可以在给定多个可能相关文档的情况下对加密文档进行排序，进而把最可能相关的文档返回给用户。但这一种算法首先不适用于一个查询包含多个查询词的情况，其次算法只利用了文档中的词频信息，无法利用词的逆文档频率，进而向量空间模型无法直接应用。解决前一种问题的一种方法是用加法同态加密算法对词频信息进行加密处理。