同态加密

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

本文，我们先回顾传统的加密方式，再介绍几种典型的同态加密

传统的加密方式

构建一个加密系统，往往需要一个密钥（key），通过这个密钥，我们可以把明文的信息加密成密文，然后通过密钥再把密文变回原来的样子。所有的加密系统，无疑是做了三件事：

1. $KeyGen(1^ \lambda)$ 来随机生成一对加密和解密的密钥（$Enc_{Key},Dec_{Key}$）

2. 加密方通过加密密钥$Enc_{Key}$和加密算法$Encryption$来加密明文$plaintext$，得到密文$ciphertest$

3. 解密方通过解密密钥$Dec_{Key}$和解密算法$Decryption$来解密密文，得到明文$plaintext$

在密码学研究中，每当我们看到一个新的系统的定义之后，接下来往往都要陈述这个系统所应具有的属性。

正确性 如果我拥有一个正确的密钥，那么我就可以通过解密算法$Decryption$来把密文还原成原文。我们如下表示解密的成功率

$\forall pt \in PT,(k_{enc},k_{dec})\larr KenGen(1^\lambda)\\ Pr[Decryption(k_{dec},Encryption(k_{enc},pt))=pt]=1$

等式代表了，如果我们拥有正确的密钥，那么解密算法可以还原加密算法生成的密文的几率是100%。

语义安全（Semantic Security）

如果我们拥有任意两个不同的原文所对应的密文，那么我们是无法区分到底哪个密文是对应了哪个原文的：

$\forall m_0.m_1:Enc(k_{enc},m_0)≈Enc(k_{dec},m_1)$

语义安全的主要意义在于旁观者无法区分两条加密的消息。

同态加密的分类

系统来看，同态加密大致上可以分为四类：部分同台，近似同台，有限级数全同态与完全同态。

$f([x_1],[x_2],...,[x_n])\rarr [f(x_1,x_2,...,x_n)]$

部分同态加密

同态加密最初级的阶段被称为部分同态加密，定义就是密文只有一种同态特性，指同态加密算法只对加法或乘法（其中一种）有同态的性质。

假如说我们可以通过一个加法同态加密的算法来计算$F$的话，那么代表了这个函数F肯定就只能包含私密输入
$x_i$的任意线性组合（加法运算）。一个可行的例子就是把各项私密输入乘以一个常数，然后相加起来：

$f(x_1,...,x_n)\rarr c_1x_1+c_2x_2+...+c_nx_n$

常见的加法同态加密算法就是基于循环群$G$的ElGamal加密算法。

假如我们拥有两条消息$m_0,m_1$的加密，分别为$ct_0,ct_1$，$ct_0=(v_0=g^{y_0},e_0=pk^{y_0}\cdot g^{m_0}),ct_1=(v_1=g^{y_1},e_1=pk^{y_1}\cdot g^{m_1})$

我们把两条密文的两个部分各自相乘的话，可以得到一个新的密文$\hat{ct}$

$\hat{ct}=ct_0\cdot ct_1 = (\hat{v}=g^{y_0+y_1},\hat{e}=pk^{y_0+y_1}\cdot g^{m_0+m_1})$

我们得到的结果恰恰就是原文$m_0+m_1$加在一起之后所对应的加密密文！这样的话，如果我们得到了两条ElGamal加密算法的密文，我们就可以通过这样的方法得到密文的任意线性组合了。

RSA加密就是一个乘法同态的系统。

假如我们拥有两条消息$m_0,m_1$的加密，分别为$ct_0,ct_1$，$ct_0=m_0^e(modN),ct_1=m_1^e(modN)$

我们把两条密文的两个部分各自相乘的话，可以得到一个新的密文$\hat{ct}$

$\hat{ct}=ct_0\cdot ct_1 = m_0^e\cdot m_1^e=(m_0\cdot m_1)^e$

近似同态加密（Somewhat Homomorphic Encryption）

单纯的部分同态加密算法（RSA,ElGamal）无法完成加密的线性组合。

如果我们有近似同态加密算法的话，那么我们就可以在密文上同时计算加法与乘法了。但是,因为这一阶段是近似同态（Somewhat Homomorphic）的，所以可以做的加法和乘法次数非常有限，可以计算的函数$F$也在一个有限的范围内。

基于配对（Pairing）的循环群加密算法

配对（pairing）是基于某些特有的椭圆曲线循环群可以进行的一种特殊运算，我们用$e(\cdot,\cdot)$，它的作用是把两个循环群中的值映射到第三个循环群中：$e(g^x\in G,g^y\in G)\rarr g^{xy}_T \in G_T$

但是，Pairing这一特殊属性并不会出现在所有的循环群当中，通过拥有Pairing属性的循环群，我们只能做非常有限的乘法计算。假如说我们当前的群$G$支持Pairing，但是新的映射群$G_T$并不支持任何Pairing，那就代表了如果我们要基于当前的体系进行同态加密运算，可以运算的函数F虽然可以包涵任意的线性组合，但是只能包涵最多一层乘法在里面。

这一局限性证明了这个系统是近似同态的，因为我们不能计算任意逻辑和深度的函数F。

有限级数全同态加密

我们已经可以对密文进行任意的加法乘法组合了，没有任何对于次数的局限性。

但是之所以被称之为有限级数全同态的原因是，这个阶段的算法会引入一个新的复杂度上限$L$的概念，这一复杂度上限约束了函数$F$的复杂度。如果我们可以把$F$用二进制电路$C$来表示的话，那么$C$的深度和大小一定要在$L$的范围之内: $\vert C \vert \le L$

全同态加密（Fully Homomorphic Encryption，FHE）

一个全同态加密的系统没有任何计算方法的限制，我们可以在没有密钥的情况下，把密文任意的组合起来，形成新的密文，并且新的密文，无论计算的复杂度，都可以完美的被还原成原文。

一个全同态加密系统，一共拥有四个算法：

1. 密钥生成算法$KeyGen(1^\lambda)\rarr sk$，生成加密与解密需要用到的密钥$sk$。

2. 加密算法$Enc(sk,m)\rarr ct$，把原文$m$加密成密文$ct$

3. 解密算法$Dec(sk,ct)\rarr m$，还原密文

4. 运算算法$Eval(F,ct_1,...ct_l)\rarr \hat ct$，把l个密文组合起来，通过一个二进制逻辑电路$F$，最后得到密文$\hat ct$，$Dec(sk,\hat ct)=F(m_1,...,m_l)$

现在我们来看看这个系统的属性（Properties）。首先，这个体系必须得是正确的（Correctness）。如果我们任意选择一个电路F，并且任意选择一组原文消息$m_1,...m_l$。如果我们拥有一开始$KeyGen$算法生成的密钥的话，那么$Dec(sk,Eval(F,Enc(sk,m_1),...Enc(sk,m_l)))=F(m_1,...,m_l)$

其次，这个系统需要达到语义安全。

为了让全同态加密体系变得有实际的使用意义，我们必须还得加一条额外的规定：简短性（Compactness）。简单来说，$Eval$这个算法的输出结果大小必须独立于二进制电路$F$的大小: $\forall F, sk, ct_i \larr Enc(sk,m_i),\vert Eval(F,ct_1,...,ct_l) \vert =poly(\lambda)$

如果没有简短性的要求，我们可以做出一个作弊的全同态加密：

1. 密钥生成、加密算法可以任意选择一个语义安全的对称加密算法。
2. $Eval(F,ct_i)\rarr (F,ct_i)$ ：运算算法$Eval$要做的事情很简单，直接把对于$F$的描述和原来的密文$ct_i$全部输出到新的密文$\hat {ct}$当中。
3. $Dec(sk,(F,ct_i))\rarr F(Dec(sk,ct_1),...,Dec(sk,ct_l))$ ：最后在解密的时候，先把密文全部依次解密回原文，然后再根据对F的描述手动跑一下得到原来的结果。

只要满足正确、语义安全、简短这三个要素，我们就拥有一个有意义（Non-trivial）的全同态加密体系了。

全同态加密的历史回顾

1978年，密码学界的几个大牛Rivest，Adleman和Dertouzos在他们的论文On Data Banks and Privacy Homomorphisms中第一次提到了对于密文进行一定的计算，可以间接地对原文进行操作的系统构想。到后来这一想法就被重新总结命名为全同态加密了。

直到2009年，在斯坦福读书的PhD Craig Gentry突然灵光一现，攻破了FHE算法的难关。在他的博士毕业论文中，他第一次给出了一个合理并且安全的全同态加密系统！这一系统基于理想格（ideal lattice）的假设。Gentry09提出来的全同态系统，我们往往称之为第一代全同态加密系统。

在2011年的时候，两位大佬Brakerski和Vaikuntanathan提出了一个新的全同态加密体系，这一体系基于格（lattice）加密的另一种假设Learning With Errors（LWE）。在同一年，Brakerski，Gentry与Vaikuntanathan这三人一起把这个体系做完了，并且正式发表出来。他们发明的全同态系统简称为BGV系统。BGV系统是一个有限级数的同态加密系统，但是可以通过Bootstrapping的方式来变成全同态系统。BGV系统相比起Gentry09提出的系统，使用了更加实际一点的LWE假设。一般来说我们都把BGV系统称之为第二代全同态加密系统。

2013年，Gentry又卷土重来了。Gentry，Sahai和Waters三个大佬推出了新的GSW全同态加密系统。GSW系统和BGV相似，本身具有有限级数全同态性质，基于更加简单的LWE假设，并且通过Bootstrapping可以达到全同态。我们一般把GSW系统称为第三代全同态加密系统。