Symmetric Searchable Encryption，SSE

对称可搜索加密。

定义在字典Δ={W1,W2,…,Wd}上的对称可搜索加密算法可描述为五元组：SSE=(KeyGen,Encrypt,Trapdoor,Search,Decrypt)。
一种通用的可搜索对称加密方案包含四个多项式时间算法：

• K=KeyGen(λ)：λ是安全参数，该算法根据安全参数生成加密密钥K。
• (I,C)=Encrypt(K, D)：也就是BuildIndex(K, D)操作。由数据所有者运行的关键字索引生成算法，它以密钥K和明文文件集合D作为输入，然后输出关键字索引的结果I和密文文件集C。
  • D是明文文件集合， D=(D₁,D₂,…,D_n),Di∈2Δ
  • 该算法生成文件索引I，密文文件集C=(C₁,C₂,…,C_n)，部分方案不需要生成索引
• T_w=Trapdoor(K, w)：由用户运行的关键字Trapdoor（陷门）生成算法。它以密钥K和用户输入需要查询的关键词w作为输入，并输出关键字w的Trapdoor(陷门)T_w。
• D(W)=Search(I, T_w)：由服务器运行的关键字搜索算法，该算法根据用户输入生成的陷门T_w和关键字索引I进行查找，并输出一组与输入关键词匹配的文件集合D(w)。
• D_i=Decrypt(K, C_i)：用生成的密钥K解密返回的密文文件C_i，生成明文文件D_i。

如果对称可搜索加密方案SSE是正确的，那么对于 ∀λ∈N，n∈Z，W∈Δ，D=(D₁,D₂,…,D_n) 以及 KeyGen(λ) 和Encrypt(K,D)输出的K和(I,C)，都有Search(I,Trapdoor(K,W))=D(W)和Decrypt(K, C_i) = D_i 成立。

对称可搜索加密通常对关键词首先进行处理，大多数采用伪随机函数或者散列算法等方法，模糊关键词语义进行随机化的处理。
当用户进行关键词检索时，将查询关键词进行相同处理，与文件的关键词进行相似度匹配，结果满足某种格式，则说明匹配成功，返回相应的文件。

SWP方案

2000年，Song等第一次提出了在密文上进行搜索的方案SWP。

具体构造如下:

• KeyGen()：数据拥有者生成加密密钥k'和k"以及伪随机流S₁,S₂,…,S_n（n为文件中的单词块数目）。
• Encrypt()：将文件分为长度固定的单词块W_i，计算

  $$X_i=E_{k''}(W_i)=(L_i,R_i), k_i=f_{k'}(L_i), T_i=(S_i,F_{k_{i}}(S_i))$$

  和Ci=Xi⊕Ti ，其中，E是分组加密算法，F和f是伪随机函数。
• Trapdoor()：对于用户输入的关键词 W，计算X=E_k''(W)=(L,R) 和 k=f_k'(L)，将（X，k）发送服务器。
• Search()：服务器进行如下计算:

  $$T_p=C_p⊕X=(S_p,S^{'}_p)= \begin{cases} {(S_p,S^{'}_p)} \end{cases}= \begin{cases} (S_p,F_k(S_p)) \\\\ null \end{cases}$$

  如果(S_p~'=F_k(S_p))，返回（p,C_p）。
• Decrypt()：用户收到C_p后，根据自己的密钥解密，具体计算如下：C_p=(C_p,l,C_p,r)， X_p,l=C_p,l⊕S_p，K_p=f_k'(X_p,l)，T_p=(S_p,F_k(S_p))以及X_p=C_p⊕T_p和W_p=D_k''(X_p)。其中，D是分组密码解密算法。

虽然SWP算法可以使服务器不能获得任何明文信息，但是由于需要扫描全文，使算法效率较低，并且该算法容易收到统计攻击的威胁。

1. 单一关键字搜索

顺序扫描的SSE方案

在该方案中，通过顺序扫描整个密文来执行搜索。
该方案的基本思想是通过将明文中的每个关键字与伪随机比特序列进行异或运算来获得密文。因此，允许直接在密文上搜索。

该方案包括3个步骤，分别是：加密、搜索和解密。

在该方案中，明文和查询关键字的隐私得到了保护。
但是，它的搜索效率较低，搜索时间与文档集合的长度成线性关系，因为服务器在确定文档中是否包含某个关键字时，需要扫描文档的整个密文。

具有安全索引的SSE方案

基于文档的索引
为了提高搜索效率而采用伪随机函数和布隆过滤器的安全索引结构，使用布隆过滤器，可以快速确定一个元素是否属于一个集合。
在这个方案中，伪随机函数被应用于文档中的每个关键词两次。然后，输出被映射到布隆过滤器。
有了Bloom filter的知识，确定一个文档是否包含某个关键字就容易多了。

这种方案的优点是服务器只需要搜索索引，而不是扫描整个密文。结果，提高了搜索效率，但服务器还必须搜索每个索引，并且查询的搜索工作与文档数量成线性关系，即使只有一个文档包含查询关键字。

基于关键字的索引
在基于关键字的安全索引中，一个关键字对应许多文档标识符。在该方案中，查询关键词的搜索时间与包含该查询关键词的文档数量成线性关系。因此，与基于文档的索引相比，基于关键字的索引在搜索查询时更有效。
然而，当在集合中添加、删除或修改文档时，更新基于关键字的索引是困难的。

动态SSE方案

这是一种能够处理文档更新的动态SSE方案。 在该方案中，服务器中存储的关键字的搜索时间是对数的。
基本方案扩展到两个方案，这两个方案均支持文档更新。第一个方案是交互式的，而第二个方案是无交互式的。

2. 模糊关键词搜索的方案

在SSE方案中，用户向服务器提交查询关键字的Trapdoor（陷门），服务器返回包含查询关键字的文档。
但是，如果查询关键字与预设的关键字不匹配，如“campus”和“compus”，关键字搜索将失败。
幸运的是，模糊关键字搜索可以处理这个问题，因为它可以容忍轻微的打字错误和格式不一致。

3. 联合关键字搜索

联合关键字搜索允许用户在单个查询期间获得包含几个关键字的文档。

它比单一关键字搜索更高效，更适合实际应用。

一个简单的过程是分别对每个关键字执行单个关键字搜索，然后处理结果。但是，它的效率很低，并且会向服务器泄露一些信息。

现存的一些联合关键字搜索，往往通信成本与文档数量成线性关系，但主要工作可以离线完成；另外的方案只需要不断的交流，不需要离线做任何事情。

其他方案

此外，还有基于非标准shamir秘密共享技术方案实现的方案，也有基于双线性对实现的方案。
也有学者提出支持范围、子串、通配符和短语查询的方案。

4. 排名和可验证的关键字搜索

排名关键字搜索可以通过返回最相关的文档来优化搜索结果，这可以减少网络流量并增强系统可用性。

有学者提出了一种具有“索引匹配”度量的多关键字排序搜索方案。
然而，他们的搜索结果是根据匹配关键词的数量进行排名的，而没有考虑不同关键词的重要性。
也有人提出了一种使用“余弦度量”技术的多关键字排序搜索方案。他们的方案以牺牲搜索精度为代价获得了比线性搜索更好的效率。

最近有学者提出了一个动态的多关键字排序搜索方案，原理是使用一个安全树，也有学者提出基于层次聚类索引的多关键字排序搜索方案，以提高搜索效率。
在他们的方案中，当数据集合的大小呈指数增长时，搜索时间呈线性增长。