同态加密的分类
根据对密文数据进行操作的种类和次数，同态加密方案可以分为三大类。
●半同态加密（Partially Homomorphic Encryption，PHE），仅支持一种同态运算，但是支持执行无限次该同态运算。
●部分同态加密（Somewhat Homomorphic Encryption，SWHE），可以支持多种同态运算，但是同态运算的次数有限。
●全同态加密（Fully Homomorphic Encryption，FHE），支持无限次、所有种类同态和运算。
PHE方案在一些应用中可以使用，如在线投票、隐私信息检索（Private Information Retrieval，PIR），这些应用的特点是仅需要使用一种同态运算就够了，如仅使用同态加法或者同态乘法。
SWHE方案必须同时支持同态加法和同态乘法，但是SWHE方案密文的尺寸随着同态运算次数增长得很快，因此总的运算次数受限。这些缺点使得在实际应用中，PHE和SWHE都受到一定限制。
Gentry提出了第一个FHE方案，该方案基于理想格构造，但是这个方案的效率比较低，除了重大的理论意义以外，其工程实现的效率并不好。之后有许多人基于Gentry的方案进行了改进，并给出了不同的FHE方案。
半同态加密
半同态加密仅支持密文之间的加法或者乘法，有多个传统的加密算法都具有半同态性，如RSA、ElGamal、Goldwasser-Micali等。现有的PHE方案都是非对称的公钥加密方案，其中大部分都是加法同态方案，但是RSA、ElGamal属于乘法同态方案，在计算性能方面，RSA、ElGamal的表现优越。
许多PHE方案已经有实际落地的应用了，并且大多数方案的单次密文加法或乘法运算在几秒内即可完成，例如，在电子投票系统和生物信息保护领域，Pai方案加解密1024比特的数据块大约需要2313ms。
2011年，MIT计算机科学和人工智能实验室（CSAIL）研发了一个加密数据库系统CryptDB，该数据库系统允许用户查询加密的SQL数据库，而且能在无须解密存储信息的情况下返回结果。其原理是在可信的MySQL-Prxoy代理服务器端对明文SQL语句进行拦截，之后对隐私字段进行加密，将改写后的SQL语句提交到不可信的MySQL服务器端执行存储以实现对隐私数据的保护。CryptDB系统可直接对密文数据进行SQL操作。
但是，为了支持多种不同的查询操作，CryptDB不得不同时使用多种加密算法对数据库内的数据进行加密。例如，使用Pai同态加密算法支持计数查询，使用Song同态加密算法或EGM同态加密算法支持关键词检索。但是这会使存储数据量急剧增大，同时通信开销也会增加。
操作种类受限显然制约了PHE方案在大数据外包计算中的大规模应用。已经有一些工作考虑改进PHE方案以满足更多的应用，例如，MREA方案和CEG方案。
部分同态加密
SWHE方案能够同时支持加法同态运算和乘法同态运算，因此在应用场景范围方面，比PHE更有优势。但是SWHE支持的同态运算次数有限，次数上限是由能否正确解密密文决定的。
通常情况下，同态加密输出的密文中包含“噪声”，每次同态运算都会增大密文中的噪声值，解密运算能够消除噪声，一旦对密文进行同态运算的次数超过上限，则会导致密文中的“噪声”过大无法解密。
21世纪初提出的大多数同态加密方案都被归类为SWHE方案，因为这些方案都尽可能地保持低的噪声参数，因而可以执行的操作数量有限。换句话说，SWHE方案只能支持部分现实场景。
在首个FHE方案出现以前，已经出现了许多SWHE方案。2009年，Craig提出第一个FHE方案之后，先构建SWHE再转化为FHE的范式促使更多的SWHE方案被提出，用于构建更高效的FHE。
在文献里面出现得最早的重要SWHE方案是Polly Cracker方案，该方案的密文大小随着同态运算次数增大呈指数增长，尤其是乘法运算导致的密文增长更为迅速。随后研究者们提出了多个对Polly Cracker改进的方案，可惜的是这些改进方案均被发现存在安全性漏洞。
另一个角度实现密文运算的尝试是使用不同的代数集合作为加密方案的基础。1999年出现的SYY方案，其底层代数集合为 NC 1 中的一个半群。 NC 1 是一个复杂类，该类中包含具有深度为多项式对数且大小为多项式的电路。SYY方案支持多项式次密文同态相加，但仅支持单次密文同态求逆或求和运算。
SWHE方案里面最重要的一个是2005年提出的BGN方案，该方案能够在密文上同态执行2-析取范式（二元合取范式的析取）运算，并能够支持无限次加法同态运算以及一次乘法同态运算，且具有同态运算后密文大小保持不变的优点。BGN方案的安全性基于子群判定问题的困难性，该问题判定群 G 中的特定元素是否为子群 G p 中的元素，其中 G 的阶为 n = pq ， p 和 q 为不同的素数。
全同态加密
允许对密文进行无限次任意同态运算操作，且结果输出在密文空间内的同态加密方案称为全同态加密（FHE）方案。在“隐私同态”概念自1978年引入后，人们经过大约30年才找到实现FHE的实际方案。2009年Gentry在其博士论文中不仅给出了一个FHE方案，而且提出一个通用的FHE框架。
尽管Gentry提出的基于理想格的FHE方案实现了理论性的突破，但 该方案在实际应用中也存在许多瓶颈，最典型的就是计算量过大，方案中使用的数学概念使该方案复杂、难以理解和实现。 因此，后续有许多新的方案对Gentry的FHE进行了改进，以突破这些方式实现中的瓶颈。
从算法设计原理的角度来看，现有的FHE方案可以分成 三大类 ：基于格、基于纠错码、基于数论。
1.基于格的FHE
格是欧几里得空间中按规律整齐排列的点所组成的集合。基于格的密码学具有诸多优点：抗量子攻击安全性、最坏情况到平均情况的规约。在格方法中，公钥对应格的“坏”基，或者说是基向量较长、基向量之间夹角较小的一组基；而私钥对应格的“好”基，或者说是基向量较短、基向量之间倾向于互相垂直的一组基。使用基于格的方法来构建FHE还有一个优点在于，解密电路的复杂度往往低于之前的同态加密方案（如RSA、EGM）。
2.基于纠错码的FHE
2011年，Bogdanov和Lee提出了一个基于纠错码的FHE方案。基于纠错码的方案和基于格的方案一样，密文的加密过程都是通过仿射变换及增加噪声实现的，基于格的方案中，密文的安全性是通过隐藏在噪声中实现的，而在基于纠错码的方案中，明文则隐藏在仿射变换中，噪声用于保证仿射变换不可逆。
3.基于数论的FHE
数论方法在公钥密码设计中占有很重要的地位，在过去二十年中，FHE的设计人员也开始考虑使用数论作为底层数学基础设计无噪声的FHE方案，以解决基于格FHE的性能问题。现有基于数论FHE方案可以进一步分为四类。
●DGHV方案及其改进。2010年，Dijk、Gentry、Halevi、Vaikuntanathan四人提出一个基于整数的FHE方案，称为DGHV方案。该方案的安全性基于近似最大公约数（A-GCD）问题，为了实现全同态，DGHV方案依然使用Gentry提出的自举技术，导致其效率受限。DGHV方案及其后续改进均被认为不是无噪声的FHE方案。
●基于交换环和非交换环的方案。2012年，有人提出了基于整数分解问题的FHE，该方案建立在交换环上，是一个对称加密方案。针对该方案的改进，有人提出在非交换环上设计方案。
●基于整数向量的方案。2014年出现了将基于LWE方案进行模数切换（Modulus Switching）的方案，该方案支持整数向量的三种基本操作：加法、线性变换、带权内积。
●基于八元代数（Octonion Algebra）的方案。有一些FHE方案为了解决其普遍存在的性能偏低问题，研究有限环 Z q 上的八元代数结构FHE方案，此类方案的安全性基于多变量二次方程系统困难性假设。
