1. 同态加密概述

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

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

2. 乘同态的ElGamal加密方案

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

选一个随机数$x(1<x<p-1)$作为私钥，计算 y ≡ g x   m o d   p y equiv g^x bmod p y≡gxmodp作为公钥

加密： C = ( c , c ′ ) C = (c,c^{'}) C=(c,c′)，其中 c ≡ g r   m o d   p , c ′ ≡ m y r   m o d   p c equiv g^{r} bmod p, c^{'} equiv m y^{r} bmod p c≡grmodp,c′≡myrmodp

解密： m ≡ ( c ′ / c x )   m o d   p m equiv (c^{'}/c^{x}) bmod p m≡(c′/cx)modp

ElGamal加密方案具有乘同态特性，对于 E ( m 1 , r 1 ) = ( c 1 , c ’ 1 ) = ( g r 1   m o d   p , m 1 y r 1   m o d   p ) Eleft(m_1, r_1right)=left(c_1, c’_1right)=(g^{r_1} bmod p, m_1y^{r^1} bmod p) E(m1​,r1​)=(c1​,c’1​)=(gr1​modp,m1​yr1modp) E ( m 2 , r 2 ) = ( c 2 , c ’ 2 ) = ( g r 2   m o d   p , m 2 y r 2   m o d   p ) Eleft(m_2, r_2right)=left(c_2, c’_2right)=(g^{r_2} bmod p, m_2y^{r^2} bmod p) E(m2​,r2​)=(c2​,c’2​)=(gr2​modp,m2​yr2modp) 有 E ( m 1 , r 1 ) E ( m 2 , r 2 ) = ( g r 1   m o d   p , m 1 y r 1   m o d   p ) × 模  p  笛卡尔积  ( g r 2   m o d   p , m 2 y r 2   m o d   p ) = ( g r 1 + r 2   m o d   p , ( m 1 m 2 ) y r 1 + r 2   m o d   p ) = E ( m 1 m 2 , r 1 + r 2 ) begin{aligned} Eleft(m_1, r_1right) Eleft(m_2, r_2right) &= left(g^{r_1}bmod p, m_1y^{r_1} bmod pright) times_{text {模 } mathrm{p} text { 笛卡尔积 }} left(g^{r_2}bmod p, m_2y^{r_2} bmod pright) \ &=left(g^{r_1+r_2} bmod p, (m_1 m_2)y^{r_1+r_2} bmod pright) \ &=Eleft(m_1 m_2, r_1+r_2right) end{aligned} E(m1​,r1​)E(m2​,r2​)​=(gr1​modp,m1​yr1​modp)×模 p 笛卡尔积 ​(gr2​modp,m2​yr2​modp)=(gr1​+r2​modp,(m1​m2​)yr1​+r2​modp)=E(m1​m2​,r1​+r2​)​即 D ( E ( m 1 , r 1 ) E ( m 2 , r 2 ) ) = m 1 m 2 Dleft(Eleft(m_1, r_1right) Eleft(m_2, r_2right)right)=m_1 m_2 D(E(m1​,r1​)E(m2​,r2​))=m1​m2​ 。

Eg

系统参数: $p=23,g=5$，选择$x=2$作为私钥，公钥 y = 5 2   m o d   23 = 2 y=5^2 bmod 23=2 y=52mod23=2

对于明文消息 $M=5$, 选择随机数 $r=5$, E ( 5 , 5 ) = ( 5 5   m o d   23 , 2 5 ⋅ 5   m o d   23 ) = ( 20 , 22 ) E(5,5)=left(5^5 bmod 23,2^5 cdot 5 bmod 23right)=(20,22) E(5,5)=(55mod23,25⋅5mod23)=(20,22)选择随机数 $r=6$, E ( 5 , 6 ) = ( 5 6   m o d   23 , 2 6 ⋅ 5   m o d   23 ) = ( 8 , 21 ) E(5,6)=left(5^6 bmod 23,2^6 cdot 5 bmod 23right)=(8,21) E(5,6)=(56mod23,26⋅5mod23)=(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^2 n2的$n$次剩余。

Paillier加密体制如下：

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

加密: 选择随机数 r ∈ Z P ∗ , E ( M ) = g m r n   m o d   n 2 . r in Z_{P}^{*}, E(M)=g^{m} r^{n} bmod n^{2} . r∈ZP∗​,E(M)=gmrnmodn2.

解密: M = L ( C λ ( N )   m o d   n 2 ) L ( g λ ( N )   m o d   n 2 )   m o d   n M=frac{Lleft(C^{lambda(N)} bmod n^{2}right)}{Lleft(g^{lambda(N)} bmod n^{2}right)} bmod n M=L(gλ(N)modn2)L(Cλ(N)modn2)​modn

Paillier加密方案具有加同态特性, 对于 E ( m 1 , r 1 ) = g M 1 r 1 n   m o d   n 2 Eleft(m_{1}, r_{1}right)= g^{M^{1}} r_{1}^{n} bmod n^{2} E(m1​,r1​)=gM1r1n​modn2 E ( m 2 , r 2 ) = g M 2 r 2 n   m o d   n 2 Eleft(m_{2}, r_{2}right)=g^{M_{2}} r_{2}^{n} bmod n^{2} E(m2​,r2​)=gM2​r2n​modn2有 E ( m 1 , r 1 ) E ( m 2 , r 2 ) = ( g m 1 r 1 n   m o d   n 2 ) ( g m 2 r 2 n   m o d   n 2 ) = g ( m 1 + m 2 ) ( r 1 r 2 ) n   m o d   n 2 = E ( m 1 + m 2 , r 1 r 2 ) begin{aligned} Eleft(m_{1}, r_{1}right) Eleft(m_{2}, r_{2}right) =&left(g^{m_{1}} r_{1}^{n} bmod n^{2}right)left(g^{m_{2}} r_{2}^{n} bmod n^{2}right) \ = & g^{(m_{1}+m_{2})}left(r_{1} r_{2}right)^{n} bmod n^{2} \ = & Eleft(m_{1}+m_{2}, r_{1} r_{2}right) end{aligned} E(m1​,r1​)E(m2​,r2​)===​(gm1​r1n​modn2)(gm2​r2n​modn2)g(m1​+m2​)(r1​r2​)nmodn2E(m1​+m2​,r1​r2​)​即 D ( E ( m 1 , r 1 ) E ( m 2 , r 2 ) ) = m 1 + m 2 Dleft(Eleft(m_1, r_1right) Eleft(m_2, r_2right)right)=m_1+m_2 D(E(m1​,r1​)E(m2​,r2​))=m1​+m2​ 。

4. 全同态加密方案

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

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

一个同态的公钥加密方案 $\epsilon$ 中包含以下四种算法: K e y G e n ε , E n c r y p t ε , D e c r y p t ε , E v a l u a t e ε KeyGen_{varepsilon}, Encrypt_{varepsilon} ,Decrypt_{varepsilon} , Evaluate_{varepsilon} KeyGenε​,Encryptε​,Decryptε​,Evaluateε​

E v a l u a t e ε Evaluate_{varepsilon} Evaluateε​ 表示在加密数据集上进行的运算, 输人是公钥, 许可电路集 C ε C_{varepsilon} Cε​ 上的电路$C$以及密文集合 Ψ = ⟨ ψ 1 , … , ψ t ⟩ Psi=leftlanglepsi_{1}, ldots, psi_{t}rightrangle Ψ=⟨ψ1​,…,ψt​⟩ , 输出为密文$\psi$ 。

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

同态加密（Homomorphic Encryption）：对于许可电路集 C ε C_{varepsilon} Cε​上的电路 $C$，方案$\epsilon$是同态的，如果在 C ε C_{varepsilon} Cε​ 上对于由 K e y G e n ε KeyGen_{varepsilon} KeyGenε​ 产生的公钥私钥对$(Pu,Pr)$ , 电路 C ∈ C ε C in C_{varepsilon} C∈Cε​ , 任意明文 Π 1 , … , Π t Pi_{1}, ldots, Pi_{t} Π1​,…,Πt​ 以及任意密 文 Ψ = ⟨ ψ 1 , … , ψ t ⟩ , ( Psi=leftlanglepsi_{1}, ldots, psi_{t}rightrangle, quadleft(right. Ψ=⟨ψ1​,…,ψt​⟩,( 其中 ψ i ← E n c r y p t ε ( p k , Π i ) ) left.psi_{i} leftarrow E n c r y p t_{varepsilon}left(p k, Pi_{i}right)right) ψi​←Encryptε​(pk,Πi​)) 满足: ψ ←  Evaluate  ε ( P u , C , Ψ ) ⇒  Decrypt  ε ( P r , ψ ) = C ( Π 1 , … , Π t ) psi leftarrow text { Evaluate }_{varepsilon}(Pu, C, Psi) Rightarrow text { Decrypt }_{varepsilon}(Pr, psi)=Cleft(Pi_{1}, ldots, Pi_{t}right) ψ← Evaluate ε​(Pu,C,Ψ)⇒ Decrypt ε​(Pr,ψ)=C(Π1​,…,Πt​)

并且 D e c r y p t ε Decrypt_{varepsilon} Decryptε​可以被表示为大小为$poly(\lambda )$的电路 D ϵ D_{epsilon} Dϵ​ 。

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

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