1. 同态加密概述

同态加密首次由R.Rivest等人于1978年在《On data banks and privacy homomorphisms》中以隐私同态（Privacy homomorphism）的概念提出。同态性使得可以在加密数据上进行运算，从而保护用户数据隐私。

同态加密体制定义：对于加密体制三元组$(G,E,D)$，其中$G$表示密钥生成算法，$E$表示加密算法，$D$表示解密算法，称该加密体制为同态的，如果对于$G$产生的每一对密钥$(e,d)$，满足$$\forall m_1,m_2\in \mathcal{M},\mathrm{Pr}\left(D(E(m_1,e)\underset{\mathcal{C}}{⨀}E(m_2,e),d)=m_1\underset{\mathcal{M}}{⨀}{m}_2\right)=1$$其中，$\mathcal{M}$表示明文集合，$\mathcal{C}$表示对应的密文集合，${⨀}_{\mathcal{M}}$与${⨀}_{\mathcal{C}}$分别表示明文集合与密文集合中的运算符。若对应加法运算符，称其为加同态；若对应乘法运算符，称其为乘同态。

2. 乘同态的ElGamal加密方案

系统参数：随机选择一个大素数$p$，且要求$p-1$有大素数因子，$g\in {\mathbf{Z}}_p^{\ast }$是一个本原元($Z_p$是一个有$p$个元素的有限域，$Z_p^{\ast }$是$Z_p$中的非零元构成的乘法群)

选一个随机数$x(1<x<p-1)$作为私钥，计算$y\equiv g^x\mathrm{mod}p$作为公钥

加密：$C=(c,c^{{}^{\prime }})$，其中$c\equiv g^r\mathrm{mod}p,c^{{}^{\prime }}\equiv m{y}^r\mathrm{mod}p$

解密：$m\equiv (c^{{}^{\prime }}/c^x)\mathrm{mod}p$

ElGamal加密方案具有乘同态特性，对于$$E\left(m_1,r_1\right)=\left(c_1,c{’}_1\right)=(g^{r_1}\mathrm{mod}p,m_1{y}^{r^1}\mathrm{mod}p)$$$$E\left(m_2,r_2\right)=\left(c_2,c{’}_2\right)=(g^{r_2}\mathrm{mod}p,m_2{y}^{r^2}\mathrm{mod}p)$$ 有$$\begin{array}{rl}E\left(m_1,r_1\right)E\left(m_2,r_2\right)& =\left(g^{r_1}\mathrm{mod}p,m_1{y}^{r_1}\mathrm{mod}p\right){\times }_{\text{模 }\mathrm{p}\text{ 笛卡尔积 }}\left(g^{r_2}\mathrm{mod}p,m_2{y}^{r_2}\mathrm{mod}p\right)\\ & =\left(g^{r_1+r_2}\mathrm{mod}p,(m_1{m}_2)y^{r_1+r_2}\mathrm{mod}p\right)\\ & =E\left(m_1{m}_2,r_1+r_2\right)\end{array}$$即 $D\left(E\left(m_1,r_1\right)E\left(m_2,r_2\right)\right)=m_1{m}_2$ 。

Eg

系统参数: $p=23,g=5$，选择$x=2$作为私钥，公钥$y=5^2\mathrm{mod}23=2$

对于明文消息 $M=5$, 选择随机数 $r=5$,$$E(5,5)=\left(5^5\mathrm{mod}23,2^5\cdot 5\mathrm{mod}23\right)=(20,22)$$选择随机数 $r=6$,$$E(5,6)=\left(5^6\mathrm{mod}23,2^6\cdot 5\mathrm{mod}23\right)=(8,21)$$则$$E(5,5)E(5,6)=(20\times 8\mathrm{mod}23,22\times 21\mathrm{mod}23)=(22,2)$$可验证$$E(5\times 5,5+6)=(22,2)$$因此$$E(5\times 5,5+6)=E(5,5)E(5,6)$$

3. 加同态的Paillier加密方案

Paillier加密方案的安全性依赖于合数剩余判定假设（DCRA，Decisional Composite Residuosity Assumption），即没有多项式时间算法来区分一个模数是否是模$n^2$的$n$次剩余。

Paillier加密体制如下：

系统参数: 选取$n=pq$ , 其中 $p$ 与 $q$ 为两个大素数, 并且 $n$ 满足 $\gcd (n,\varphi (n))=1$, 选取 随机整数 $g\in \left(Z/n^{2}Z\right)$ , 满足$gcd\left(L\left(g^{\lambda }\mathrm{mod}{n}^2\right),n\right)=1$ , 则公钥为 $(n,g)$ , 私钥为 $\lambda (n)=\mathrm{lcm}((p-7)，(q-7))$, $M$ 为明文消息。

加密: 选择随机数$r\in Z_P^{\ast },E(M)=g^m{r}^n\mathrm{mod}{n}^2.$

解密: $$M=\frac{L\left(C^{\lambda (N)}\mathrm{mod}{n}^2\right)}{L\left(g^{\lambda (N)}\mathrm{mod}{n}^2\right)}\mathrm{mod}n$$

Paillier加密方案具有加同态特性, 对于 $$E\left(m_1,r_1\right)=g^{M^1}{r}_1^n\mathrm{mod}{n}^2$$ $$E\left(m_2,r_2\right)=g^{M_2}{r}_2^n\mathrm{mod}{n}^2$$有$$\begin{array}{rl}E\left(m_1,r_1\right)E\left(m_2,r_2\right)=& \left(g^{m_1}{r}_1^n\mathrm{mod}{n}^2\right)\left(g^{m_2}{r}_2^n\mathrm{mod}{n}^2\right)\\ =& g^{(m_1+m_2)}{\left(r_1{r}_2\right)}^n\mathrm{mod}{n}^2\\ =& E\left(m_1+m_2,r_1{r}_2\right)\end{array}$$即 $D\left(E\left(m_1,r_1\right)E\left(m_2,r_2\right)\right)=m_1+m_2$ 。

4. 全同态加密方案

全同态加密体制使得可以在加密数据上进行任意计算与分析，可应用于加密云存储服务，隐私信息检索，隐私数据挖据等许多重要领域。比如许多企业需要委托第三方（云计算数据中心）对数据进行处理分析，但是数据中含有商业机密等敏感信息，可以首先使用全同态加密算法对数据加密后再发送给第三方，这样云端服务器不用解密就可以直接处理数据，完成后返给用户。用户再对数据进行解密，得到处理结果。

全同态加密方案是指, 对于$n$个明文消息$ m_{1}, m_{2}, \ldots, m_{n}$ , 及对应的密文$ c_{1}, c_{2}, \ldots, c_{n}$ , 其加密算法$E$与解密算法$D$满足, 对于有限域上的任意可计算函数$f$ $$D(f\left(E\left(m_1\right),E\left(m_2\right),\dots ,E\left(m_n\right)\right)=f\left(m_1,m_2,\dots ,m_n\right)$$Gentry, C. 于2009年在《Fully homomorphic encryption using ideal lattics》给出了全同态的定义，并基于理想格构造了一系列全同方案。

一个同态的公钥加密方案 $\epsilon$ 中包含以下四种算法: $KeyGe{n}_{\epsilon },Encryp{t}_{\epsilon },Decryp{t}_{\epsilon },Evaluat{e}_{\epsilon }$

$Evaluat{e}_{\epsilon }$ 表示在加密数据集上进行的运算, 输人是公钥, 许可电路集$C_{\epsilon }$ 上的电路$C$以及密文集合 $\Psi =⟨{\psi }_1,\dots ,{\psi }_t⟩$ , 输出为密文$\psi$ 。

以上四种的计算复杂度是关于安全参数$\lambda$和电路$C$的大小的多项式函数。

同态加密（Homomorphic Encryption）：对于许可电路集$C_{\epsilon }$上的电路 $C$，方案$\epsilon$是同态的，如果在 $C_{\epsilon }$ 上对于由$KeyGe{n}_{\epsilon }$ 产生的公钥私钥对$(Pu,Pr)$ , 电路$C\in C_{\epsilon }$ , 任意明文 ${\Pi }_1,\dots ,{\Pi }_t$ 以及任意密 文 $\Psi =⟨{\psi }_1,\dots ,{\psi }_t⟩,($ 其中${\psi }_i\leftarrow Encryp{t}_{\epsilon }\left(pk,{\Pi }_i\right))$ 满足:$$\psi \leftarrow {\text{ Evaluate }}_{\epsilon }(Pu,C,\Psi )\Rightarrow {\text{ Decrypt }}_{\epsilon }(Pr,\psi )=C\left({\Pi }_1,\dots ,{\Pi }_t\right)$$

并且 $Decryp{t}_{\epsilon }$可以被表示为大小为$poly(\lambda )$的电路 $D_{ϵ}$ 。

全同态加密（Fully Homomorphic Encryption）：方案$\mathcal{E}$是全同态的，如果该方案对于许可电路集上的所有电路都是同态的。

同等全同态加密（Leveled Fully Homomorphic Encryption）：方案集合$\left\{{\epsilon }^{(d)}:d\in Z^{+}\right\}$ 是同等全同态加密的，如果这些方案都使用相同的解密电路，且${\epsilon }^{(d)}$对于这些最大深度为$d$的所有电路 (这些电路中门的类型集合是相同的) 都是同态的，${\epsilon }^{(d)}$上算法的计算复杂度是关于 $\lambda ,d$以及电路$\mathrm{C}$的规模的多项式函数。