可搜索加密算法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，优势在于计算开销小、算法简单、速度快。通常使用在单用户模型中，检索方和数据拥有者是同一个。

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

场景模拟

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

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

Searchable Encryption的构造

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

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

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

• SWP方案