一、前世：云计算时代下的数据安全
云计算强大的开放性和共享性在为人们带来便利的同时，云计算的安全性却面临着非常大的挑战，用户希望能够将数据交由云服务器存储和管理的同时又不向云服务器泄露任何与数据相关的信息，而对数据进行加密再上传是最常见的解决办法。
虽然数据加密再上传解决了隐私安全问题，但是当用户需要使用某个文件时，用户必须将上传至云服务器的密文数据分组全部下载下来，在本地解密后才能搜索出自己需要的内容。这无疑浪费了传输带宽资源，且搜索效率极低。为解决这个问题，可搜索加密应运而生。
Song 等人提出可搜索加密（Searchable Encryption, SE）：将已加密数据文件存储在一个不可信服务器上，在对文件进行检索时，希望只获得包含某个特定关键字 w 的一部分文档。服务器可以在加密文件上进行查找并只返回可能包含关键字 w 的文档，而无法获得除此之外的其他信息。
可搜索加密作为一种新型的密码学原语，使得用户拥有在密文域上进行关键词搜索的能力。当数据以密文的形式存储在云服务器上时，利用云服务器的强大计算能力进行关键词的检索，而不会向云服务器泄露任何用户的隐私。这不仅仅使用户的隐私得到了有效保护，而且检索效率也在云服务器的帮助下得到了大幅度提升。
SE 可分为两种：对称可搜索加密（Symmetric Searchable Encryption, SSE）和非对称可搜索加密（Asymmetric Searchable Encryption, ASE）
SSE相比于ASE，优势在于计算开销小、算法简单、速度快。通常使用于单用户模型中，检索方和数据拥有者是同一人。
在静态的可搜索加密的基础上，为了便于用户对云服务器上的数据进行更新，学界提出了动态可搜索加密技术。动态可搜索加密不仅支持用户对外包的密文数据库进行关键词检索，而且允许用户对密文数据库进行插入和删除的动态更新操作。
二、今生：动态可搜索加密
动态可搜索加密（Dynamic Symmetric Searchable Encryption, DSSE）指用户可以动态地对存储在服务器上的密文文档进行更新（update）。
更新操作包括两种：添加（add）、删除（delete）。大多方案在实现删除时，并非真正从服务器移除，只是把删除的文档添加到删除实例中。
前向安全（Forward Privacy）
前向安全是指更新操作不会泄露之前的查询的信息，也就是说，服务器不知道更新的关键字是否在之前被查询过。
更新时泄露的信息只能严格包含操作类型、文件标识符和文件大小，而没有任何其他的信息。
大部分方案都会专注于前向安全，目前为止不满足后向安全的方案的安全隐患并不明显，但不满足前向安全的隐患则很大。
论文中形式化定义：
后向安全（Backward Privacy）
如果一个文件（w, ind）已经被删除，那么之后在关键字 w 上进行的搜索都不能包含这个 ind。
第 Ⅰ 类：允许泄漏与当前查询关键词 w 相匹配的文件，插入到数据库的时间戳，以及 w 的总更新次数。
第 Ⅱ 类：除了第 Ⅰ 类中泄露的信息外，还会泄露关于关键词 w 上更新的时间戳和操作类型。
第 Ⅲ 类：与第 Ⅱ 类相比，还进一步泄露了删除操作中取消的添加操作内容。
形式化定义：
面临的攻击
文件注入攻击（File-Injection Attack）
核心思想在于，关联用户过去提交的搜索令牌和新提交的文件，以此恢复出用户提交的关键字，推测文档内容。抵抗文件注入攻击的关键在于保证DSSE的前向安全。
统计推理攻击（Statistical Inference Attack）
通过统计用户提交的搜索和访问操作，以及其他信息与公开或已知的数据库进行比对，从中恢复出一些关键信息，对方案的安全性要求更高。因此隐藏返回结果成为关键，这有两种常用的方法：填充和分区。填充是指对搜索结果进行填充，让结果看起来一样长；分区则是把文档按照关键字分区，每次返回对应分区的结果。
穿刺加密 puncturable encryption, PE
前向安全公钥加密 (forward secure public key encryption) 的一种变体，可以支持对单个消息的细粒度撤销。
核心思想在于使用标记(tag)。消息用一组tag加密，穿刺算法使用某个tag更新密钥，使得新的密钥能够解密所有不包含该tag的密文。
形式化的定义如下：
一个在消息空间M和标记空间T上的穿刺公钥加密方案是一个算法四元组(KeyGen, Encrypt, Puncture, Decrypt)，每个算法定义如下：
KeyGen(1^λ): 输入安全参数λ，输出公钥PK和最初的密钥。
Encrypt(PK, m, t): 输入公钥PK、消息m∈M和标记t∈T，输出对应的密文CT。
Puncture(, t): 输入密钥和标记t，输出一个新的密钥，它能够解密所有密钥能够解密的，除了那些使用标记t加密的密文。
Decrypt(, CT, t): 输入密钥，密文CT和标记t，解密成功输出明文m，否则输出⊥。
正确性：如果使用没有被标记t穿刺的密钥SK去解密被t加密的消息m，则一定能够输出明文m。
三、其他相关概念
同态加密 Homomorphic Encryption,HE
同态加密是允许服务器在密文上进行计算的技术。用户把加密的输入提交到服务器，服务器直接在密文上进行计算后把结果返回给用户，用户解密后可以得到正确答案。
相关的详细知识、实现与方案探究在此：
不经意传输 Oblivious Transfer, OT
发送者每次发送两个或多个信息，接收者从中选择一个进行接收。保证发送者无法知道接收者获得了什么消息。
匿踪查询 Private Information Retrieval, PIR
查询方在不泄露查询对象关键词的情况下提交查询，服务器提供与关键词匹配的查询结果，但无法知道结果具体对应哪个查询对象。使用不对称加密、不经意传输等技术。
待学习补充…
