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

时间:2022-12-22 08:03:14

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_2\right)=1 m1,m2M,Pr(D(E(m1,e)CE(m2,e),d)=m1Mm2)=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 p1有大素数因子, g ∈ Z p ∗ g \in \boldsymbol Z^{*}_p gZp是一个本原元( 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<p1)作为私钥计算 y ≡ g x   m o d   p y \equiv g^x \bmod p ygxmodp作为公钥

加密 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 cgrmodp,cmyrmodp

解密 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 ) 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,c1)=(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,c2)=(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_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 23\right)=(20,22) E(5,5)=(55mod23,255mod23)=(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 23\right)=(8,21) E(5,6)=(56mod23,265mod23)=(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^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 \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)=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((p7)(q7)), 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} . rZP,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 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 E\left(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 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_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 ) 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 C C以及密文集合 Ψ = ⟨ ψ 1 , … , ψ t ⟩ \Psi=\left\langle\psi_{1}, \ldots, \psi_{t}\right\rangle Ψ=ψ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} CCε , 任意明文 Π 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) ψiEncryptε(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):dZ+} 是同等全同态加密的,如果这些方案都使用相同的解密电路,且 ε ( d ) \varepsilon^{(d)} ε(d)对于这些最大深度为 d d d的所有电路 (这些电路中门的类型集合是相同的) 都是同态的, ε ( d ) \varepsilon^{(d)} ε(d)上算法的计算复杂度是关于 λ , d \lambda, d λ,d以及电路 C \mathrm{C} C的规模的多项式函数。