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

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


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)=1m1,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 pp,且要求p − 1 p-1p1有大素数因子,g ∈ Z p ∗ g \in \boldsymbol Z^{*}_pgZp是一个本原元(Z p Z_pZp是一个有p pp个元素的有限域,Z p ∗ Z^{*}_pZpZ p Z_pZp中的非零元构成的乘法群)

选一个随机数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 pygxmodp作为公钥

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

解密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,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_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,255mod23)=(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,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^2n2n nn次剩余。

Paillier加密体制如下:

系统参数: 选取n = p q n=pqn=pq , 其中 p ppq 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((p7)(q7)), 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} .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 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)=gM2r2nmodn2E ( 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}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 dd的所有电路 (这些电路中门的类型集合是相同的) 都是同态的,ε ( d ) \varepsilon^{(d)}ε(d)上算法的计算复杂度是关于 λ , d \lambda, dλ,d以及电路C \mathrm{C}C的规模的多项式函数。

相关文章
|
14天前
|
安全 搜索推荐 前端开发
揭秘 HTTPS 加密协议:保护你的网上安全之道
揭秘 HTTPS 加密协议:保护你的网上安全之道
227 0
|
14天前
|
算法 安全 Shell
SSH:加密安全访问网络的革命性协议
SSH:加密安全访问网络的革命性协议
48 9
|
14天前
|
NoSQL 安全 MongoDB
MongoDB安全机制:认证、授权与加密
【4月更文挑战第30天】MongoDB提供全面的安全机制,包括认证(用户名/密码、LDAP、Kerberos、x.509证书)、授权(基于角色的访问控制,RBAC)和加密(TLS/SSL、透明数据加密TDE、字段级加密FLE),确保数据保密性、完整性和可用性。通过合理配置这些机制,企业可保障数据安全,应对不断变化的安全威胁。
|
14天前
|
安全 Java Go
【Go语言专栏】Go语言中的加密与安全通信
【4月更文挑战第30天】本文介绍了Go语言中的加密与安全通信。通过使用golang.org/x/crypto/ssh/terminal库实现终端加密,以及golang.org/x/net/websocket库实现WebSocket安全通信。文章展示了安装库的命令、加密操作及WebSocket通信的示例代码。此外,还列举了安全通信在数据传输加密、用户认证、密码保护和文件加密等场景的应用。掌握这些知识对开发安全的Web应用至关重要。
|
14天前
|
存储 安全 算法
【专栏】保护数据安全的重要性以及安全加密算法在数据保护中的应用
【4月更文挑战第27天】在数字化时代,数据安全至关重要,关系到个人隐私、企业商业机密、国家安全及经济发展。安全加密算法(如对称加密、非对称加密和哈希算法)在保护数据方面发挥关键作用。它们应用于电子商务、金融、物联网、云存储和数字签名等领域,确保信息传输和存储的安全。面对日益复杂的挑战,我们需要持续研究和应用加密技术,提高数据安全意识,共同维护数字世界的繁荣与安全。
|
14天前
|
安全 算法 网络安全
|
14天前
|
SQL 安全 网络安全
IDEA DataGrip连接sqlserver 提示驱动程序无法通过使用安全套接字层(SSL)加密与 SQL Server 建立安全连接的解决方法
IDEA DataGrip连接sqlserver 提示驱动程序无法通过使用安全套接字层(SSL)加密与 SQL Server 建立安全连接的解决方法
112 0
|
14天前
|
安全 搜索推荐 API
【现代密码学】笔记 补充7-- CCA安全与认证加密《introduction to modern cryphtography》
【现代密码学】笔记 补充7-- CCA安全与认证加密《introduction to modern cryphtography》
142 0
|
14天前
|
算法 Java 数据安全/隐私保护
java MD5 32位加密
java MD5 32位加密
23 0
|
14天前
|
Java 数据安全/隐私保护
Java实现最电话号码的简单加密源码
Java实现最电话号码的简单加密源码
23 0