1、定义

一般的加密方案关注的都是数据存储安全。即，我要给其他人发个加密的东西，或者要在计算机或者其他服务器上存一个东西，我要对数据进行加密后在发送或者存储。没有密钥的用户，不可能从加密结果中得到有关原始数据的任何信息。只有拥有密钥的用户才能够正确解密，得到原始的内容。我们注意到，这个过程中用户是不能对加密结果做任何操作的，只能进行存储、传输。对加密结果做任何操作，都将会导致错误的解密，甚至解密失败。
同态加密方案最有趣的地方在于，其关注的是数据处理安全。同态加密提供了一种对加密数据进行处理的功能。也就是说，其他人可以对加密数据进行处理，但是处理过程不会泄露任何原始内容。同时，拥有密钥的用户对处理过的数据进行解密后，得到的正好是处理后的结果。


定义同态加密（homomorphic encryption）是一种特殊的加密方法，允许对密文进行处理得到仍然是加密的结果。即对密文直接进行处理，跟对明文进行处理后再对处理结果加密，得到的结果相同。从抽象代数的角度讲，保持了同态性。

如果我们有一个加密函数 f , 把明文A变成密文A’, 把明文B变成密文B’，也就是说 f(A) = A’ ， f(B) = B’ 。另外我们还有一个解密函数 能够将 f 加密后的密文解密成加密前的明文。


对于一般的加密函数，如果我们将A’和B’相加，得到C’。我们用 对C’进行解密得到的结果一般是毫无意义的乱码。


但是，如果 f 是个可以进行同态加密的加密函数， 我们对C’(A’和B’相加)使用 进行解密得到结果C， 这时候的C = A + B。这样，数据处理权与数据所有权可以分离，这样企业可以防止自身数据泄露的同时，利用云服务的算力。

2、同态分类

同态性来自代数领域，一般包括四种类型：加法同态、乘法同态、减法同态和除法同态。同时满足加法同态和乘法同态，则意味着是代数同态，称为全同态（full homomorphic）。同时满足四种同态性，则称为算数同态。
对于计算机操作来讲，实现了全同态意味着对于所有处理都可以实现同态性。只能实现部分特定操作的同态性，称为特定同态（somewhat homomorphic）。
a) 如果满足 f(A)+f(B)=f(A+B) ， 我们将这种加密函数叫做加法同态
b) 如果满足 f(A)×f(B)=f(A×B) ，我们将这种加密函数叫做乘法同态。


如果一个加密函数f只满足加法同态，就只能进行加减法运算；
如果一个加密函数f只满足乘法同态，就只能进行乘除法运算;


如果一个加密函数同时满足加法同态和乘法同态，称为全同态加密。那么这个使用这个加密函数完成各种加密后的运算(加减乘除、多项式求值、指数、对数、三角函数)。

第一个满足加法和乘法同态的同态加密方法直到2009年才由Craig Gentry提出。


同态加密算法
RSA 算法对于乘法操作是同态的。
Paillier 算法则是对加法同态的。
Gentry算法则是全同态的。

3、应用

这几年不是提了个云计算的概念嘛。同态加密几乎就是为云计算而量身打造的！我们考虑下面的情景：一个用户想要处理一个数据，但是他的计算机计算能力较弱。这个用户可以使用云计算的概念，让云来帮助他进行处理而得到结果。但是如果直接将数据交给云，无法保证安全性啊！于是，他可以使用同态加密，然后让云来对加密数据进行直接处理，并将处理结果返回给他。这样一来：

• 用户向云服务商付款，得到了处理的结果；
• 云服务商挣到了费用，并在不知道用户数据的前提下正确处理了数据；

我们在云计算应用场景下面进行介绍：
Alice通过Cloud，以Homomorphic Encryption（以下简称HE）处理数据的整个处理过程大致是这样的：

1. Alice对数据进行加密。并把加密后的数据发送给Cloud；
2. Alice向Cloud提交数据的处理方法，这里用函数f来表示；
3. Cloud在函数f下对数据进行处理，并且将处理后的结果发送给Alice；
4. Alice对数据进行解密，得到结果。

4、意义

仅满足加法同态的算法包括Paillier和Benaloh算法；仅满足乘法同态的算法包括RSA和ElGamal算法。
同态加密在云计算和大数据的时代意义十分重大。目前，虽然云计算带来了包括低成本、高性能和便捷性等优势，但从安全角度讲，用户还不敢将敏感信息直接放到第三方云上进行处理。如果有了比较实用的同态加密技术，则大家就可以放心地使用各种云服务了，同时各种数据分析过程也不会泄露用户隐私。加密后的数据在第三方服务处理后得到加密后的结果，这个结果只有用户自身可以进行解密，整个过程第三方平台无法获知任何有效的数据信息。
另一方面，对于区块链技术，同态加密也是很好的互补。使用同态加密技术，运行在区块链上的智能合约可以处理密文，而无法获知真实数据，极大地提高了隐私安全性。

可搜索加密(Searchable Encryption，SE)

以博主看过的文献或查阅的资料为基础，本博文将介绍可搜索加密(Searchable Encryption，SE)的相关知识点，以及归纳与总结。这也是博主个人的学习过程，长期更新，建议收藏，也欢迎指正！

可搜索加密：旨在将数据文件进行加密后存储到云端，然后对密文进行检索的一种技术。

例如：用户为节约自身的资源开销，将文件外包给云服务器，但又不想云服务知道存储的文件内容，因此需要对文件采用某种加密方式加密后存储。此外，用户若想从云服务器中查询文件中的特定数据，只有合法的用户基于关键词检索对应的密文数据。

一、可搜索加密的诞生

如果在读此篇博文之前，读者有了解过SE的背景，想必都知道SE的开篇之作。即使不了解的读者也没关系，这里将隆重介绍一下SE的诞生。SE的开篇之作名为"Practical techniques for searches on encrypted data "。这是作者首次研究出支持对数据加密后进行搜索的密码技术，由此开辟了密码学中的全新研究方向——可搜索加密(Searchable Encryption）。

• 作者：Dawn Xiaoding Song, D. Wagner, and A. Perrig.
• 单位：University of California, Berkeley
• 发表刊物：Proceedings of the 2000 IEEE Symposium on Security and Privacy（国际顶级会议，中国计算机学会（CCF）推荐的 A 类网络与信息安全国际学术会议）
• 时间：2000年5月
• 被引次数：3894（截至2021年4月29日，来源Google Scholar）

后来的研究者写可搜索加密时基本会引用Song2000

二、可搜索加密的分类

2.1 按照应用模型分类

• 1）单用户 — 单服务器模型：用户加密个人文件并将其存储到不可信的服务器。只有该用户具备基于关键词检索的能力，服务器无法获取明文文件和待检索关键词的信息。
  

• 2）多用户 — 单接收者(单服务器)模型：多个发送者加密文件后，将其上传至不可信的服务器，以达到与单个接收者传送数据的目的。只有接收者具备基于关键词检索的能力，服务器无法获取明文文件信息，不同于单用户模型，多用户 — 单服务器模型要求发送者和接收者不能是同一用户。
  

• 3）单用户 — 多接收者(单服务器)模型：与上一类型类似，但为单个发送者将加密文件上传至不可信服务器，然后多个接收者共享数据。
  

• 4）多用户 — 多接受者(单服务器)模型：在多对单模型的基础上，任意用户都可成为接受者，通过访问控制和认证策略后，具备关键词的密文检索方式提取共享文件的能力。只有合法的用户具备基于关键词检索的能力，服务器无法获取明文文件信息，具备广阔的应用前景。
  

2.2 按照解决策略分类

• 1）对称可搜索加密(Symmetric searchable encryption, SSE)：旨在加解密过程中采用相同的密钥之外，陷门生成也需要密钥的参与，通常适用于单用户模型，具有计算开销小、算法简单、速度快的特点。
• 2）非对称可搜索加密(Asymmetric searchable encryption, ASE)：旨在加解密过程中采用公钥对明文信息加密和目标密文的检索，私钥用于解密密文信息和生成关键词陷门。非对称可搜索加密算法通常较为复杂，加解密速度较慢，其公私钥相互分离的特点，非常适用于私钥生成待检索关键词陷门，通常适用于多对一模型。
• 3）对称+非对称可搜索加密：由于非对称SE本身支持最基本形式的隐私数据共享，可通过共享密钥拓展到多对多的应用场景。对称SE虽然使用单用户模型，但计算开销小、速度快，更适用于大型文件数据的加密和共享。通过混合加密与基于属性加密技术相结合，或与代理重加密结合，也可构造共享方案。
• 4）属性基加密(Attribute-based encryption, ABE)：它是指通过对用户私钥设置属性集(或访问结构）为数据密文设置访问结构（或属性集），由属性集和访问结构之间的匹配关系确定其解密能力。特别是密文策略的属性基加密（CP-ABE），其密文上的访问策略本身就是一种搜索策略，访问策略的表达能力从一定程度上反映了可搜索能力。

2.3 按照检索关键词数分类

• 1）单关键词搜索：旨在用户在检索的过程中使用单关键词进行检索。
• 2）多关键词搜索：顾名思义，用户在检索的过程中使用多个关键词进行检索。

2.4 按照准确度分类

• 1）精确搜索：旨在搜索的过程中，只有当输入的关键词完全等于文件的索引值时才能检索出结果。
• 2）模糊搜索：与精确搜索不同，旨在搜索的过程中，用户输入的关键词与数据或索引中存在的关键词之间存在某种模糊的关系，并以这种模糊关系进行关键词匹配。（例如，我们输入打乱的关键词“ture”，能够搜索到索引中包含关键词“true”的数据文件，这可以帮助用户输入错误的检索问题。）

三、可搜索加密相关技术的名词解释

可搜索加密是一项结合各种密码学原语与信息检索的技术，旨在能够以某种方式对数据和数据的关键词索引进行加密，使得用户能够通过提交关键词进行方便灵活且高效的搜索，同时又保证负责存储的云服务器对密文数据本身以及关键词相关信息一无所知。

目前研究热点，分为三个维度：表达能力、安全性和检索效率。

• 1）相似度度量：以欧式距离、余弦距离、陆地移动距离或词移距离来度量被输入的多个关键词与索引对应的数据文件之间的匹配符合程度。
• 2）语义文本相似度：旨在衡量两段文本在语义上的相似程度。通常，文本的语义相似度数值越小，则说明两个文本之间的语义差异性越大；反之，该数值越大，则说明这两个文本所表达出的语义越相似。

• 3）语义搜索：在各种搜索引擎中应用最广泛，也是最迎合用户体验的搜索功能，它能够充分地理解用户的搜索意图，返回尽可能符合用户本意和需求的搜索结果。
• 4）编辑距离：通常被用于句子的快速模糊匹配领域，以表示两个文本之间，由一个转换成另一个所需的最少编辑操作次数，其中编辑操作包括增、删、改三种。
• 5）向量空间模型(VSM)：主要思想是假设一个文本的语义只与该文本中的单词有关，而忽略其语序和单词之间的相互关系，然后通过基于词频统计的方法，将文本映射成向量，最后通过向量间的距离计算以表征文本间的相似度。
• 6）TF-IDF函数：用于表征词在文本中的权重，TF代表某个词在单份文件中出现的频率，IDF代表包含某个词的文件与全部文件数量比例的倒数，TF-IDF为两者的乘积。
• 7）Top-K排名搜索：旨在获取相似度后，将其作为打分结果，根据匹配到的文件的分数，按照顺序返回给用户分数排名最高的K份数据，是搜索引擎中最常见的模式。
• 8）安全最近邻((k-Nearest Neighbors, kNN)算法：旨在向量空间模型(VSM)中，将真实的数据文件表示成空间向量，将用户提交的多个关键词描述为虚拟文件向量，在空间中计算和寻找最符合用户描述的k份真实数据问题，这与Top-K排名搜索高度适应。
• 9）N-gram分割：旨在把关键词按照一定规则进行字符分割，便于将语义相关的关键词表示为词向量时，仍保持语义关系。
• 10）词嵌入：旨在用机器学习的方法，通过对大量文本数据集进行训练，将单词表示为固定维度100/200/300的词向量，当两个单词之前存在语义关系时，则对应的向量较为相似。
• 11）词向量计算：旨在用词嵌入获取词向量后，在某个模型中对词向量进行计算，完成包括搜索在内的特定计算任务。
• 12）基于自然语言处理模(NLP)型：旨在用词嵌入获取词向量后，对数据文本用机器学习的方法进行计算，完成某种文本处理任务，包含对数据文本的关键词搜索。
• 13）贪心算法：通过将全局问题分为多个子问题，分布求出各个子问题的局部最优解，对权重大的节点为贪心的选择，则全局最优解为各个局部最优解之和。（转载：漫画式理解）
• -14）深度优先搜索算法：是指通过产生目标树的相应拓扑排列表，利用该表可以方便的解决很多查找路径问题。可简单理解为对每个可能的分支路径深入到不能再深入为止。
• 15）近似最近邻(Approximate Nearest Neighbor，ANN)：主要分为基于树的方法(KD-tree、Ball-tree、Annoy和B树等）、哈希方法（局部敏感哈希）和矢量量化方法（Product Quantization）三类。

四、存在问题及未来方向

• 1）在可搜索加密的理论研究方面：主要集中在研究密文搜索语句的表达能力、可搜索加密方案的安全性、可搜索加密方案的高效性等方面。

  • 表达能力：不仅需要让用户精确地定位所需要的加密文件，而且要让用户能够更加灵活地表述搜索需求。因此，主要集中密文搜索能力的复杂性的探索、研究支持模糊搜索、有序搜索、区间搜索，以及子集搜索等复杂性密文搜索能力。
  • 安全性：针对不同需求，不同表达能力，定义不同SE的安全级别，在不同安全级别的基础上，寻求简单高效的难题假设证明SE的安全性。
  • 高效性：研究SE的搜索凭证、搜索关键字与密钥、密文间的关系，探索用越短的密钥、密文来实现表达能力越丰富的SE方案，进一步地，结合不同的需求和安全级别，探索高效安全的SE。

• 2）利用属性基加密(ABE)实现安全搜索方面，效率是一个主要因素，研究属性基加密以及签名的安全搜索与隐私保护的一般理论，主要集中在属性基加密以及签名的高效性上，包括表达能力、通信效率、计算效率和属性特征等方面。

  • 表达能力丰富的ABE
  • 更短密文、短密钥、短公开参数的ABE
  • 高效的解决方案及加密数据外包计算方案
  • 简单的难题假设
  • 基于属性的隐私保护

• 3）在安全搜索与隐私保护的基础理论研究的基础上，探索安全搜索与隐私保护的一般规律与方法，并在此基础上进行方案的轻量化的研究，并探索在安全搜索与隐私保护的过程中一次使用有关的公钥加密方案，以适用于存储、计算资源受限网络环境。

  • 探索SE轻量化方法
  • 探索ABE实现安全搜索的轻量化和高效实现方法

文献引用：

[1] 李经纬,贾春福,刘哲理,李进,李敏.可搜索加密技术研究综述[J].软件学报, 2015,26(1):109-128.
[2] 董晓蕾,周俊,曹珍富.可搜索加密研究进展[J].计算机研究与发展,2017,54(10):2107-2120.

1.加密流量分类概述

1.1识别方法

• 负载检测： 模式匹配（签名、指纹）
• 负载随机性：统计方法（信息熵、卡方距离）
• 数据包分布：统计方法（简单统计、交叉熵）
• 机器学习：机器学习算法（集成学习、强化学习）
• 主机行为：图论（BLINC、Motifs、社交网络）
• 混合方法

1.2 识别粒度

粗粒度>------------------------------------------------->细粒度
是否加密>协议>应用>服务>网页>异常流量>内容参数
第二节将重点介绍

1.3 识别对象等级

• 流级：关注流的特征和到达过程，还可分为单向流和双向流
• 包级：关注包的特征和到达过程，包的大小分布、到达时间、到达顺序等
• 主机级：关注主机间的连接模式，如主机（或端口）通信的所有流量
• 会话级：关注绘画的特征和到达过程，特征包括字节数和会话持续时间等

2.加密流量识别粒度相关研究

2.1加密与未加密流量分类

这是加密流量识别的首要任务。
Dorfinger等人提出一种加密流量实时识别放大RT-ETD
Lotfollahi提出一种基于神父学习的方法Deep Packet，将特征提取和分类阶段集成到一个系统中，不但能判断是否是加密流量，还能区分VPN和非VPN流量，网络模型为SAE（堆叠自编码器）和CNN。

2.2 加密协议识别

加密协议识别由于各种协议封装格式不同，需要了解协议的交互过程，找出交互过程中的可用于区分不同应用的特征及规律才能总结出网络流量中各应用协议的最佳特征属性，最终为提高总体流识别的粒度和精度奠定基础。
加密协议交互过程大体可分为两个阶段

• 建立安全连接：握手、认证、密钥交换。在该过程中通信双方协商支持的加密算法，互相认证并生成密钥
• 第二阶段采用第一阶段产生的密钥加密传输数据

目前主流的加密协议有以下三种

2.2.1 IPSec

一组确保IP层通信安全的协议栈，保护TCP/IP通信免遭窃听和篡改，其中包含了

1. 认证头AH，为IP数据报提供无连接数据完整性、消息认证以及防重放攻击保护；
2. 封装安全载荷ESP，提供机密性、数据源认证、无连接完整性、防重放和有限的传输流（traffic-flow）机密性；
3. 安全关联SA，提供算法和数据包，提供AH、ESP操作所需的参数。
4. 密钥协议IKE，提供对称密码的钥匙的生存和交换。

详细链接（百度百科）

2.2.2 SSL/TLS

安全套接层协议SSL提供应用层和传输层之间的数据安全性机制，在客户端和服务器之间建立安全通道，对数据进行加密和隐藏，确保数据在传输过程中不被改变。SSL协议在应用层协议通信之前就已经完成加密算法和密钥的协商，在此之后所传送的数据都会被加密，从而保证通信的私密性。
详细链接（百度百科）

2.2.3 SSH

安全外壳协议是一种在不安全网络上提供安全远程登录及其他安全网络服务的协议。主要包括传输层协议、用户认证协议和连接协议。
详细链接（百度百科）

2.3 服务识别

服务识别就是识别加密流量所属的应用类型，如

• 流媒体：YouTube、优酷、土豆
• SNS：Facebook、推特、微博
• P2P：Skype、BitTorrent
  随着P2P应用的不断发展，出现了多种混淆技术，如动态端口号、端口跳变、HTTP伪装、分块文件传输和加密有效载荷等，因此需要有效的方法来识别P2P流量。

Maiolini利用K-means进行分类，准确率达到99.8%

2.4 异常流量识别

基于信息熵的异常检测算法比传统的流量分析提供更细粒度的识别。

Adami提出Skype-hunter，基于签名和流统计特征相结合的策略，能识别信令任务和数据业务

2.5 内容参数识别

指对加密应用流量从内容属性上进一步识别，如视频清晰度及图片格式等。

Khakpour提出内容参数识别方法Iustitia

3.加密流量精细化分类方法相关研究（六种）

3.1 基于有效载荷

通过分析数据包的有效载荷来识别流量，准确率高，但识别复杂度也高。由于解析数据包负载触犯隐私逐渐被取代。

3.2 数据报负载随机性检测

网络应用的数据流并不是完全随机加密，由于每个分组会携带一些相同的特征字段，所以分组的这些字节可能并不是随机的，因此可以根据数据流的特定字节的随机性来识别

3.3 机器学习

基于机器学习的识别方法只需处理传输层以下的内容，加密技术一般只对载荷信息进行加密而不对流量特征进行处理，该方法受加密影响小。

3.4 基于行为的识别方法

这种方法首先是从主机的角度来分析不同应用的行为特征，识别结果通常是粗粒度的，如P2P和Web，其次对传输层加密无能为力，最后使用网络地址转换和非对称路由等技术会因为不完整的连接信息而影响其识别精度。

3.5 基于数据报大小分布

实际网络环境中，为了提高用户体验，不同的应用对数据流中的数据包大小要求不同，例如流媒体的数据包不宜过大，否则网络拥塞时影响播放流畅度，文件下载的数据包可以以最大报文长度传输。

3.6 混合方法

很多特定方法只对特定协议有效，因此可以将多种加密流量识别方法集成实现高效的加密流量识别。

3.7 加密流量识别方法综合对比

• ⭐越多表示性能越好

4.分类结果影响因素

4.1 隧道技术

隧道技术常用在不安全的网络上建立安全通道，将不同协议的数据包封装在负载部分后通过隧道发送。识别隧道协议相对容易，关键在于如何识别隧道协议下承载的应用。因此加密流i昂识别需要考虑隧道技术的影响

4.2 代理技术

加密流量识别就还要客服代理技术带来的影响。数据压缩代理技术可以有效减少带宽使用，但对流量识别技术产生较大的影响。

4.3 流量伪装技术

流量伪装技术（如协议混淆、流量变种）将一种流量的特征伪装成零一种流量的特征，组织基于流统计特征的识别方法的准确识别，木马蠕虫等恶意程序越来越多地采用流量伪装技术进行恶意攻击和隐蔽通信。

4.4 HTTP/2.0及QUIC协议

为了降低延迟和提高安全性，Google提出了新的协议，不久的将来，这两种协议将被广泛应用，如何识别协议下承载的应用面临新的挑战。

5.加密流量特征变化相关研究

特征提取方向的研究非常广泛，但很少有人关注类别不均衡和概念漂移的问题。

• Li考虑到时间空间域不同的影响， 使用FCBF和对称不确定度量选择特征子集，但单个FCBF特征分类性能低，不能很好地解决概念漂移问题。
• 张宏莉等提出bagging集成学习来解决，尽管准确度提升了，类不均衡的问题依然存在。
• Zhong在CVFDT的基础上提出了解决P2P流量概念漂移问题的算法iCVFDT，在出现概念漂移时生成一棵新子树，但未考虑多种应用情况下的概念漂移。
• Gama提出根据分类错误率检测概念飘逸算法DDM，如果错误率高于阈值就报告发生概念漂移，对突变式数据表现优异，渐变式则欠佳。
• Nishida提出基于统计的检测方法STEPD，该方法与DDM具有相似的架构，但该方法采用统计检验来检测概念漂移，需要预先给定一个滑动窗口。如果窗口大小不合适，容易产生误报或漏报。

6.SSL/TLS加密应用分类相关研究

分类HTTPS加密流量给网络带来了新的挑战。

• Kim提出从SSL/TLS有效载荷中自动生成服务签名的方法。
• Bernaille提出了一种基于SSL连接的前几个数据包大小的方法，早期识别精度85%。
• Sun提出一种使用签名和流统计分析相结合的方案来识别SSL/TLS加密应用。

7.SSL/TLS加密视频QoE参数识别相关研究

近年来，视频QoE评估被广泛研究。卡顿和初始缓冲时延时QoE评估的关键性能指标。

• Nam对移动网络下Youtube和Netflix视频流量进行了研究，发现网络带宽和CPU能力也是影响QoE的重要因素。
• Seufert研究了自适应码流技术在HTTP视频服务中的应用。