一、同态加密&全同态加密简介
全同态加密是密码学中的一个分支，了解全同态加密前，我们需要先看看什么是同态加密。
维基百科：同态加密（英语：Homomorphic encryption）是一种加密形式，它允许用户在加密情况下对数据执行计算，而无需先进行解密。计算产生的结果以加密形式保留，当解密后，产生的计算结果与对未加密数据计算产生的输出结果相同。
同态加密方案关注的是数据处理的安全，提供一种对加密数据进行处理的功能。其特点是允许数据在加密情况下实现数学或逻辑运算。同态是指代数中的同态性，加密和解密函数可以被认为是明文和密文空间之间的同态。
Ø同态性在代数上包括：加法同态、乘法同态、减法同态和除法同态；
Ø同时满足加法同态和乘法同态，则意味着是代数同态，即全同态；
Ø同时满足四种同态性，则被称为算数同态。
全同态加密(Fully Homomorphic Encryption)，支持对密文进行任意计算的密码系统称为全同态加密(FHE)。这种方案能够为任何所需功能构建程序，这些功能可以在加密输入上运行以产生结果加密。由于这样的程序永远不需要解密其输入，因此它可以由不受信任的一方运行，而不会泄露其输入和内部状态。
下面我们以PYSEAL论文中对全同态加密场景的一个举例：
上图是PYSEAL论文中对全同态加密场景的一个举例。5和10可以分别加密为X和YZ。X+YZ的计算结果为PDQ，而PDQ解密后的结果为15，与加密前的计算结果5+10=15完全相同。其中，X+YZ=PDQ被称为密文计算，并且图中也表明，在密文计算的过程中，随时可以被解密。
二、全同态加密&全同态加密简介
1978年（在RSA方案发布后的一年内）由Rivest、Adleman和Dertouzos三位研究人员提出同态加密概念，推出了最早的公钥密码体系RSA，此方案满足乘法同态性。其中Rivest和Adleman是我们熟知的RSA算法中的R和A。
2009年由Gentry提出了第一个全同态加密方案，该方案是基于理想格构造的，方案支持对密文进行加法和乘法运算，方案的安全性基于两个假设：理想格上的某些最坏情况问题，以及稀疏（或低权重）子集和问题。
2010年Dijk、Gentry、Halevi和Vaikuntanathan提出了一个基于整数的全同态加密方案，设计基于近似的最大公因数问题。方案使用了许多Gentry构造的工具，但不需要理想格。他们表明，Gentry基于理想格的方案的某种同态组件可以用一个使用整数的非常简单的某种同态方案来代替。因此，该方案在概念上比Gentry的理想格方案更简单，但在同态运算和效率方面具有相似的属性，运算效率并没有提高，且原始方案只支持低阶多项式的运算。
2013年Gentry、Sahai和Waters(GSW)提出了一种构建FHE方案的新技术，该技术避免了同态乘法中昂贵的“重新线性化”步骤。Brakerski和Vaikuntanathan观察到，对于某些类型的电路，GSW密码系统的噪声增长速度更慢，因此效率更高，安全性更强。
这些技术得到进一步改进，以开发GSW密码系统的有效环变体：FHEW(2014)和TFHE(2016)。FHEW方案首次表明，通过在每次操作后刷新密文，可以将引导时间减少到几分之一秒。FHEW引入了一种新方法来计算加密数据的布尔门，这极大地简化了自举，并实现了自举过程的变体。TFHE方案进一步提高了FHEW的效率，该方案使用类似于FHEW中的方法实现了自举过程的环形变体。
三、全同态加密算法的应用
全同态加密技术是一种趋势性技术，它可被应用于外包计算、隐私保护机器学习、安全多方计算、联合学习、数据交换和共享等领域。大量的专家和学者对其进行了研究。目前，同态加密技术的研究主要集中在提高计算速度、缩短密文长度、扩展数据类型、扩大支持操作等方面。
基于全同态加密的特性，它可被用于保护隐私的外包存储和计算以及在加密的数据中进行诸如检索、比较等操作，得出正确的结果，而在整个处理过程中无需对数据进行解密。它的意义在于，能够解决将数据及其计算委托给第三方时的数据安全问题。对于医疗保健信息等敏感数据，全同态加密可用于通过消除抑制数据共享产生的隐私安全问题或提高现有服务的安全性来启用扩展新的服务。例如，由于医疗数据隐私问题，医疗保健中的预测分析可能难以通过第三方服务提供商处理，如果预测分析服务提供商可以对加密数据进行操作，就会减少因为使用第三方服务而产生的隐私安全问题。即使服务提供商的系统受到安全威胁，数据也将保持安全。
全同态加密在当今时代的意义十分重大。但是遗憾的是，目前已知的全同态加密算法需要消耗大量计算资源的计算时间，还达不到实用的标准。且由于全同态加密算法只支持加法和乘法同态，很多数理统计方法，会有开根号等计算，还需要使用到信息论和数学中的逼近理论，通过近似算法来达到相同或相近的计算目的，这类计算通常也会伴随着精度丢失、误差偏大等问题。
随着数据安全的普及用户个人隐私安全的保障以及隐私数据边缘计算服务的发展，全同态加密算法还拥有着十分广泛的发展空间和应用场景。
四、全同态加密算法的实现
目前被广泛采用的全同态加密方案，按照与其底层方法相对应被分为以下几代:
1.Pre-FHE:
ØRSA密码系统（无限数量的模块乘法）
ØElGamal密码系统（无限数量的模块乘法）
ØGoldwasser-Micali密码系统（无限数量的异或操作）
ØBenaloh密码系统（无限数量的模加法）
ØPaillier密码系统(无限数量的模加法)
ØSander-Young-Yung系统（20多年后解决了对数深度电路的问题）
ØBoneh-Goh-Nissim密码系统（加法运算次数不限，但最多只有一次乘法）
ØIshai-Paskin密码系统(多项式大小的分支程序)
2.第一代FHE：
ØMarten van Dijk,Craig Gentry,Shai Halevi and Vinod Vaikuntanathan(idea lattice)
3.第二代FHE：
ØBrakerski-Gentry-Vaikuntanathan（BGV，2011）方案
ØLopez-Alt,Tromer,and Vaikuntanathan（LTV,2012）的基于NTRU的方案
ØBrakerski/Fan-Vercauteren（BFV，2012）的方案，基于Brakerski的scale-invarian密码系统
ØBos,Lauter,Loftus,and Naehrig(BLLN,2013)的基于NTRU的方案，建立在LTV和Brakerski的scale-invarian密码系统上
4.第三代FHE：
ØCraig Gentry,Amit Sahai,and Brent Waters(GSW),关于建立FHE方案，避免了同态乘法中昂贵的"重线性化"步骤
ØFHEW（2014），GSW密码系统的环变体
ØTFHE（2016），GSW密码系统的环变体
ØCKKS方案，专注于机器学习，在加密状态下进行高效的rounding操作
下面列举了实现第二代和/或第三代FHE方案的开源FHE库列表。
第二代和第三代全同态加密方案有几种开源实现。第二代FHE方案实现通常在水平FHE模式下运行，并支持高效的类似SIMD的数据打包；通常用于计算加密整数或实数/复数。第三代FHE方案的实现通常在每次布尔门操作后自举，但对打包和高效算术计算的支持有限；通常用于计算加密位上的布尔电路。使用第二代还是第三代方案的选择取决于输入数据类型和所需的计算。
