可搜索加密算法SSE

可搜索加密算法SE

目前，云计算飞速发展，许多用户更喜欢将数据上传到云上，以减轻本地存储的负担。

然而，在远程服务器上存储敏感数据会带来隐私方面的挑战，这是一个令人担忧的问题。

2000年，Song等首次提出了可搜索加密的概念。作为一种新型的密码原语，可搜索加密技术使用户具有在密文域上进行关键词搜索的能力。 数据以密文方式存储在云服务器上时，利用云服务器的强大计算能力进行关键词的检索，而不会向服务器泄露任何用户的隐私。这不仅仅使用户的隐私得到了有效保护，而且检索效率也在服务器的帮助下得到了大幅度提升。

Searchable Encryption（可搜索加密）是一种保护用户敏感数据的积极方法，同时保留了服务器端的搜索能力。

可搜索加密解决两类基本问题： ① 不可信赖服务器的存储问题 ② 不可信赖服务器的路由问题

Searchable Encryption的主要分支是 SSE(对称可搜索加密，Symmetric Searchable Encryption) 和ASE(非对称可搜索加密, Asymmetric Searchable Encryption)。 ASE 也称公钥可搜索加密(PEKS,带有关键字搜索的公钥加密，Public key Encryption with Keyword Search)。

SSE和ASE 的区别：

• SSE 使用对称加密算法，加密和解密的密钥一样；ASE 使用非对称加密算法。
• SSE只允许私钥持有者生成密文并为搜索创建陷门; PEKS允许多个拥有公钥的用户生成密文，但只允许私钥持有者创建陷门。

SSE相比于ASE，优势在于计算开销小、算法简单、速度快。通常使用在单用户模型中，检索方和数据拥有者是同一个。

对于可搜索加密技术的来源，要追溯到不可信赖的服务器存储问题。

tip 场景模拟

假设Alice有一些文档，存储在一个不可信服务器Bob上。 因为Bob是不可信的，Alice希望只在Bob上存储加密过的文档。 每个文档都可以被分成单词，每个单词可以是等长或者不等长的。 因为Alice和服务器Bob之间通信带宽可能比较低，她在对文档进行检索时，希望只获得包含某个特定关键字w的一部分文档。 为了达到这个目标，设计了这样一个方案，Bob可以在密文上进行某种计算，并且只返回可能包含关键字w的文档，而无法获得除此之外的其他信息。

关键在于，未获得数据拥有者Alice授权的其他用户不能够知道任何关于文件明文的知识。

Searchable Encryption的构造

基于索引： 对于每一个关键字 W，建立一个索引，索引中包含所有含有该关键字的文件的指针。 由于这种方案在更新数据的时候会对索引进行大量的修改，因此适合大量只读模式。

• Z-IDX方案
• SSE-1方案

基于存储结构： 这种情况下没有索引，每次查询都是对文件进行一次扫描来寻找符合查询条件的文件。 无疑，这种模式的查询效率会低很多，但是却更适合经常更新的存储系统。

• SWP方案

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=(D1,D2,…,Dn),Di∈2Δ
  • 该算法生成文件索引I，密文文件集C=(C1,C2,…,Cn)，部分方案不需要生成索引
• Tw =Trapdoor(K, w)：由用户运行的关键字Trapdoor（陷门）生成算法。它以密钥K和用户输入需要查询的关键词w作为输入，并输出关键字w的Trapdoor(陷门)Tw。
• D(W)=Search(I, Tw)：由服务器运行的关键字搜索算法，该算法根据用户输入生成的陷门Tw和关键字索引I进行查找，并输出一组与输入关键词匹配的文件集合D(w)。
• Di=Decrypt(K, Ci)：用生成的密钥K解密返回的密文文件Ci，生成明文文件Di。

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

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

SWP方案

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

具体构造如下:

• KeyGen()：数据拥有者生成加密密钥k'和k"以及伪随机流S1,S2,…,Sn（n为文件中的单词块数目）。

• Encrypt()：将文件分为长度固定的单词块Wi，计算

  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=Ek''(W)=(L,R) 和 k=fk'(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()：用户收到Cp后，根据自己的密钥解密，具体计算如下：Cp=(Cp,l,Cp,r)， Xp,l=Cp,l⊕Sp，Kp=fk'(Xp,l)，Tp=(Sp,Fk(Sp))以及Xp=Cp⊕Tp和Wp=Dk''(Xp)。其中，D是分组密码解密算法。

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

1. 单一关键字搜索

顺序扫描的SSE方案

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

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

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

具有安全索引的SSE方案

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

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

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

动态SSE方案

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

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

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

3. 联合关键字搜索

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

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

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

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

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

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

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

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

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