安全多方计算之三：同态加密
1. 同态加密概述
同态加密首次由R.Rivest等人于1978年在《On data banks and privacy homomorphisms》中以隐私同态（Privacy homomorphism）的概念提出。同态性使得可以在加密数据上进行运算，从而保护用户数据隐私。
同态加密体制定义：对于加密体制三元组
(
G
,
E
,
D
)
(G,E,D)
(G,E,D)，其中
G
G
G表示密钥生成算法，
E
E
E表示加密算法，
D
D
D表示解密算法，称该加密体制为同态的，如果对于
G
G
G产生的每一对密钥
(
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_2right)=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
p
p，且要求
p
−
1
p-1
p−1有大素数因子，
g
∈
Z
p
∗
g in boldsymbol Z^{*}_p
g∈Zp∗是一个本原元(
Z
p
Z_p
Zp是一个有
p
p
p个元素的有限域，
Z
p
∗
Z^{*}_p
Zp∗是
Z
p
Z_p
Zp中的非零元构成的乘法群)
选一个随机数
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 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)=(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
)
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)=(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} 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)=(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
Dleft(Eleft(m_1, r_1right) Eleft(m_2, r_2right)right)=m_1 m_2
D(E(m1,r1)E(m2,r2))=m1m2 。
Eg
系统参数:
p
=
23
,
g
=
5
p=23, g=5
p=23,g=5，选择
x
=
2
x=2
x=2作为私钥，公钥
y
=
5
2
m
o
d
23
=
2
y=5^2 bmod 23=2
y=52mod23=2
对于明文消息
M
=
5
M=5
M=5, 选择随机数
r
=
5
r=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
r=6
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
×
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(5times 5,5+6) = (22,2)
E(5×5,5+6)=(22,2)因此
E
(
5
×
5
,
5
+
6
)
=
E
(
5
,
5
)
E
(
5
,
6
)
E(5times 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^2
n2的
n
n
n次剩余。
Paillier加密体制如下：
系统参数: 选取
n
=
p
q
n=pq
n=pq , 其中
p
p
p 与
q
q
q 为两个大素数, 并且
n
n
n 满足
gcd
(
n
,
ϕ
(
n
)
)
=
1
operatorname{gcd}(n, phi(n))=1
gcd(n,ϕ(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
)
(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
M
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)=gM1r1nmodn2
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)=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} 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)===(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
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
n
n个明文消息$ m_{1}, m_{2}, ldots, m_{n}$ , 及对应的密文$ c_{1}, c_{2}, ldots, c_{n}$ , 其加密算法
E
E
E与解密算法
D
D
D满足, 对于有限域上的任意可计算函数
f
f
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》给出了全同态的定义，并基于理想格构造了一系列全同方案。
一个同态的公钥加密方案
ε
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
C
C以及密文集合
Ψ
=
⟨
ψ
1
,
…
,
ψ
t
⟩
Psi=leftlanglepsi_{1}, ldots, psi_{t}rightrangle
Ψ=⟨ψ1,…,ψt⟩ , 输出为密文
ψ
psi
ψ 。
以上四种的计算复杂度是关于安全参数
λ
lambda
λ和电路
C
C
C的大小的多项式函数。
同态加密（Homomorphic Encryption）：对于许可电路集
C
ε
C_{varepsilon}
Cε上的电路
C
C
C，方案
ε
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=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ε可以被表示为大小为
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
d
d的所有电路 (这些电路中门的类型集合是相同的) 都是同态的，
ε
(
d
)
varepsilon^{(d)}
ε(d)上算法的计算复杂度是关于
λ
,
d
lambda, d
λ,d以及电路
C
mathrm{C}
C的规模的多项式函数。