安全多方计算之三：同态加密

1. 同态加密概述

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

同态加密体制定义：对于加密体制三元组( G , E , D ) (G,E,D)(G,E,D)，其中G GG表示密钥生成算法，E EE表示加密算法，D DD表示解密算法，称该加密体制为同态的，如果对于G GG产生的每一对密钥( e , d ) (e,d)(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_2\right)=1∀m1,m2∈M,Pr(D(E(m1,e)C⨀E(m2,e),d)=m1M⨀m2)=1其中，M \mathcal{M}M表示明文集合，C \mathcal{C}C表示对应的密文集合，⨀ M \bigodot_{\mathcal{M}}⨀M与⨀ C \bigodot_{\mathcal{C}}⨀C分别表示明文集合与密文集合中的运算符。若对应加法运算符，称其为加同态；若对应乘法运算符，称其为乘同态。

2. 乘同态的ElGamal加密方案

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

选一个随机数x ( 1 < x < p − 1 ) x(1<x<p-1)x(1<x<p−1)作为私钥，计算y ≡ g x   m o d   p y \equiv g^x \bmod py≡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 pc≡grmodp,c′≡myrmodp

解密：m ≡ ( c ′ / c x )   m o d   p m \equiv (c^{'}/c^{x}) \bmod pm≡(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 ) E\left(m_1, r_1\right)=\left(c_1, c’_1\right)=(g^{r_1} \bmod p, m_1y^{r^1} \bmod p)E(m1,r1)=(c1,c’1)=(gr1modp,m1yr1modp)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 ) E\left(m_2, r_2\right)=\left(c_2, c’_2\right)=(g^{r_2} \bmod p, m_2y^{r^2} \bmod p)E(m2,r2)=(c2,c’2)=(gr2modp,m2yr2modp)有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} E\left(m_1, r_1\right) E\left(m_2, r_2\right) &= \left(g^{r_1}\bmod p, m_1y^{r_1} \bmod p\right) \times_{\text {模 } \mathrm{p} \text { 笛卡尔积 }} \left(g^{r_2}\bmod p, m_2y^{r_2} \bmod p\right) \\ &=\left(g^{r_1+r_2} \bmod p, (m_1 m_2)y^{r_1+r_2} \bmod p\right) \\ &=E\left(m_1 m_2, r_1+r_2\right) \end{aligned}E(m1,r1)E(m2,r2)=(gr1modp,m1yr1modp)×模 p 笛卡尔积 (gr2modp,m2yr2modp)=(gr1+r2modp,(m1m2)yr1+r2modp)=E(m1m2,r1+r2)即 D ( E ( m 1 , r 1 ) E ( m 2 , r 2 ) ) = m 1 m 2 D\left(E\left(m_1, r_1\right) E\left(m_2, r_2\right)\right)=m_1 m_2D(E(m1,r1)E(m2,r2))=m1m2 。

Eg

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

对于明文消息 M = 5 M=5M=5, 选择随机数 r = 5 r=5r=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 23\right)=(20,22)E(5,5)=(55mod23,25⋅5mod23)=(20,22)选择随机数 r = 6 r=6r=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 23\right)=(8,21)E(5,6)=(56mod23,26⋅5mod23)=(8,21)则E ( 5 , 5 ) E ( 5 , 6 ) = ( 20 × 8   m o d   23 , 22 × 21   m o d   23 ) = ( 22 , 2 ) E(5,5)E(5,6)=(20 \times 8 \bmod 23,22 \times 21 \bmod 23)=(22,2)E(5,5)E(5,6)=(20×8mod23,22×21mod23)=(22,2)可验证E ( 5 × 5 , 5 + 6 ) = ( 22 , 2 ) E(5\times 5,5+6) = (22,2)E(5×5,5+6)=(22,2)因此E ( 5 × 5 , 5 + 6 ) = E ( 5 , 5 ) E ( 5 , 6 ) E(5\times 5,5+6) = E(5,5)E(5,6)E(5×5,5+6)=E(5,5)E(5,6)

3. 加同态的Paillier加密方案

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

Paillier加密体制如下：

系统参数: 选取n = p q n=pqn=pq , 其中 p pp 与 q qq 为两个大素数, 并且 n nn 满足 gcd ⁡ ( n , ϕ ( n ) ) = 1 \operatorname{gcd}(n, \phi(n))=1gcd(n,ϕ(n))=1, 选取 随机整数 g ∈ ( Z / n 2 Z ) g \in\left(Z / n^{2} Z\right)g∈(Z/n2Z) , 满足g c d ( L ( g λ   m o d   n 2 ) , n ) = 1 gcd \left(L\left(g^{\lambda} \bmod n^{2}\right), n\right)=1gcd(L(gλmodn2),n)=1 , 则公钥为 ( n , g ) (n, g)(n,g) , 私钥为 λ ( n ) = lcm ⁡ ( ( p − 7 ) ， ( q − 7 ) ) \lambda(n)= \operatorname{lcm}((p-7) ，(q-7))λ(n)=lcm((p−7)，(q−7)), M MM 为明文消息。

加密: 选择随机数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{L\left(C^{\lambda(N)} \bmod n^{2}\right)}{L\left(g^{\lambda(N)} \bmod n^{2}\right)} \bmod nM=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 E\left(m_{1}, r_{1}\right)= g^{M^{1}} r_{1}^{n} \bmod n^{2}E(m1,r1)=gM1r1nmodn2E ( m 2 , r 2 ) = g M 2 r 2 n   m o d   n 2 E\left(m_{2}, r_{2}\right)=g^{M_{2}} r_{2}^{n} \bmod n^{2}E(m2,r2)=gM2r2nmodn2有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} E\left(m_{1}, r_{1}\right) E\left(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} \\ = & E\left(m_{1}+m_{2}, r_{1} r_{2}\right) \end{aligned}E(m1,r1)E(m2,r2)===(gm1r1nmodn2)(gm2r2nmodn2)g(m1+m2)(r1r2)nmodn2E(m1+m2,r1r2)即 D ( E ( m 1 , r 1 ) E ( m 2 , r 2 ) ) = m 1 + m 2 D\left(E\left(m_1, r_1\right) E\left(m_2, r_2\right)\right)=m_1+m_2D(E(m1,r1)E(m2,r2))=m1+m2 。

4. 全同态加密方案

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

全同态加密方案是指, 对于n nn个明文消息$ m_{1}, m_{2}, \ldots, m_{n}$ , 及对应的密文$ c_{1}, c_{2}, \ldots, c_{n}$ , 其加密算法E EE与解密算法D DD满足, 对于有限域上的任意可计算函数f ffD ( f ( E ( m 1 ) , E ( m 2 ) , … , E ( m n ) ) = f ( m 1 , m 2 , … , m n ) D\left(f\left(E\left(m_{1}\right), E\left(m_{2}\right), \ldots, E\left(m_{n}\right)\right)=f\left(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》给出了全同态的定义，并基于理想格构造了一系列全同方案。

一个同态的公钥加密方案 ε \mathcal{\varepsilon}ε 中包含以下四种算法: 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 CC以及密文集合 Ψ = ⟨ ψ 1 , … , ψ t ⟩ \Psi=\left\langle\psi_{1}, \ldots, \psi_{t}\right\rangleΨ=⟨ψ1,…,ψt⟩ , 输出为密文ψ \psiψ 。

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

同态加密（Homomorphic Encryption）：对于许可电路集C ε C_{\varepsilon}Cε上的电路 C CC，方案ε \rm{\varepsilon}ε是同态的，如果在 C ε C_{\varepsilon}Cε 上对于由K e y G e n ε KeyGen_{\varepsilon}KeyGenε 产生的公钥私钥对( P u , P r ) (Pu, Pr)(Pu,Pr) , 电路C ∈ C ε C \in C_{\varepsilon}C∈Cε , 任意明文 Π 1 , … , Π t \Pi_{1}, \ldots, \Pi_{t}Π1,…,Πt 以及任意密 文 Ψ = ⟨ ψ 1 , … , ψ t ⟩ , ( \Psi=\left\langle\psi_{1}, \ldots, \psi_{t}\right\rangle, \quad\left(\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)=C\left(\Pi_{1}, \ldots, \Pi_{t}\right)ψ← Evaluate ε(Pu,C,Ψ)⇒ Decrypt ε(Pr,ψ)=C(Π1,…,Πt)

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

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

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