同态加密之Paillier算法

admin • • 区块链

同态加密之Paillier算法

0，背景介绍

同态加密，即原来在明文上的运算操作，经过同态加密后在密文上同样可以进行。一般有半同态和全同态加密之分：

  • 半同态加密 （Partial Homomorphic Encryption, PHE）：只支持某些特定的运算法则 f ,PHE 的优点是原理简单、易实现，缺点是仅支持一种运算(加法或乘法)；

  • 层次同态加密（Liveled HE，LHE）：一般支持有限次数的加密算法,LHE 的优点是同时支持加法和乘法，并且因为出现时间比 PHE 晚，所以技术更加成熟、一般效率比 FHE 要高很多、和 PHE 效率接近或高于 PHE，缺点是支持的计算次数有限。

  • 全同态加密 （Fully Homomorphic Encryption, FHE）：支持无限次的任意运算法则 f，FHE 有以下类别：基于理想格的 FHE 方案、基于 LWE/RLWE 的 FHE 方案等等。FHE 的优点是支持的算子多并且运算次数没有限制，缺点是效率很低，目前还无法支撑大规模的计算。

    第一个满足加法和乘法同态的同态加密方法直到2009年才由Craig Gentry提出。目前来说，全同态加密算法性能较差，应用较少。比较常用的是半同态加密算法，实现方式有 RSA （乘法同态）、Elgamal、Paillier （加法同态）等。

1，Paillier算法介绍

密钥生成

  1. 随机选择两个质数 p 和 q 满足 gcd(pq,(p-1)(q-1)) =1，这个条件保证了 p 和 q 的长度相等；
  2. 计算 N=pq 和 λ=lcm(p−1,q−1)，其中 lcm 表示最小公倍数；
  3. 随机选择 g∈Z∗N^2，满足

    g

    c

    d

    (

    L

    (

    g

    λ

    m

    o

    d

    N

    2

    )

    ,

    N

    )

    =

    1

    gcd(L(g^λ mod N^2),N)=1

    gcd(L(gλmodN2),N)=1，后面会发现这里的 g=n+1。其中 Z 表示整数，下标表示该整数集合里有多少个元素；L(x)=

    x

    −

    1

    N

    frac{x-1}{N}

    Nx−1​，

    μ

    =

    (

    L

    (

    g

    λ

    m

    o

    d

    N

    2

    )

    )

    −

    1

    m

    o

    d

      

    N

    μ = (L(g^λ mod N^2))^{-1} mod N

    μ=(L(gλmodN2))−1modN；

  4. 公钥为 (N,g)；
  5. 私钥为(λ,μ)。

加密过程

对于任意明文消息

m

∈

Z

N

m∈Z_N

m∈ZN​，任意选择一随机数

r

∈

Z

N

∗

r∈Z_{N}^*

r∈ZN∗​，计算得到密文 c ：

c

=

E

(

m

)

=

g

m

r

N

m

o

d

  

N

2

c=E(m)=g^mr^N mod N^2

c=E(m)=gmrNmodN2

解密过程

对于密文$ c∈Z_{N2}*$，计算得到明文 m ：

m

=

D

(

c

)

=

L

(

c

λ

m

o

d

N

2

)

L

(

g

λ

m

o

d

N

2

)

m

o

d

  

N

=

L

(

c

λ

m

o

d

N

2

)

∗

μ

m

o

d

  

N

m=D(c)=frac{L(c^λ mod N^2)} {L(g^λmod N^2)} mod N=L(c^λ mod N^2)*μ mod N

m=D(c)=L(gλmodN2)L(cλmodN2)​modN=L(cλmodN2)∗μmodN

加法同态的性质

对于任意明文

m

1

，

m

2

∈

Z

N

m1，m2∈Z_N

m1，m2∈ZN​和任意

r

1

，

r

2

∈

Z

N

∗

r1，r2∈Z_N^*

r1，r2∈ZN∗​，对应密文

c

1

=

E

[

m

1

,

r

1

]

，

c

2

=

E

[

m

2

,

c

2

]

c1=E[m1,r1]，c2=E[m2,c2]

c1=E[m1,r1]，c2=E[m2,c2]满足：

c

1

⋅

c

2

=

E

[

m

1

,

r

1

]

⋅

E

[

m

2

,

r

2

]

=

g

m

1

+

m

2

⋅

(

r

1

⋅

r

2

)

N

 

m

o

d

 

N

2

c_{1} cdot c_{2}=Eleft[m_{1}, r_{1}right] cdot Eleft[m_{2}, r_{2}right]=g^{m_{1}+m_{2}} cdotleft(r_{1} cdot r_{2}right)^{N} bmod N^{2}

c1​⋅c2​=E[m1​,r1​]⋅E[m2​,r2​]=gm1​+m2​⋅(r1​⋅r2​)NmodN2

解密后得到：

D

[

c

1

⋅

c

2

]

=

D

[

E

[

m

1

,

r

1

]

⋅

E

[

m

2

,

r

2

]

 

m

o

d

 

N

2

]

=

m

1

+

m

2

 

m

o

d

 

N

Dleft[c_{1} cdot c_{2}right]=Dleft[Eleft[m_{1}, r_{1}right] cdot Eleft[m_{2}, r_{2}right] bmod N^{2}right]=m_{1}+m_{2} bmod N

D[c1​⋅c2​]=D[E[m1​,r1​]⋅E[m2​,r2​]modN2]=m1​+m2​modN

即我们得到了：

c

1

∗

c

2

=

m

1

+

m

2

c1*c2=m1+m2

c1∗c2=m1+m2。密文乘等于明文加。

通过分析发现，密文乘时，含有的明文是在指数上相加的，所以解密后就可以得到明文相加结果。

为什么叫加法同态呢？我们一般希望密文计算的结果和我们明文计算的结果相同，所以对于密文上是如何计算的不做要求。这时我们在明文上实现了加法的目的，就叫它加法同态。由此还扩展出了同态加和标量乘的性质。

算法理论

image-20210430211703759

image-20210430212248163

由上式结论不难知道：

μ

=

λ

−

1

μ=λ^{-1}

μ=λ−1（g=n+1）。此外，还有

r

λ

n

m

o

d

  

N

2

=

1

r^{λn}mod N^2=1

rλnmodN2=1。

image-20210430215554440

具体算法理论证明，参见：Paillier Cryptosystem理论与实践

2，pyhtotn—paillier算法演示

我们使用了 Python 实现的 paillier 算法来演示一些性质。你可以使用如下命令安装对应库：

pip install phe

具体使用可以参考：https://python-paillier.readthedocs.io/en/latest/usage.html

下面，我们使用 phe 演示 paillier 的同态加和标量乘的性质：

from phe import paillier # 开源库
import time # 做性能测试

# 测试paillier参数
print("默认私钥大小：",paillier.DEFAULT_KEYSIZE) #2048
# 生成公私钥
public_key,private_key = paillier.generate_paillier_keypair()
# 测试需要加密的数据
message_list = [3.1415926,100,-4.6e-12]
# 加密操作
time_start_enc = time.time()
encrypted_message_list = [public_key.encrypt(m) for m in message_list]
time_end_enc = time.time()
print("加密耗时ms：",time_end_enc-time_start_enc)
# 解密操作
time_start_dec = time.time()
decrypted_message_list = [private_key.decrypt(c) for c in encrypted_message_list]
time_end_dec = time.time()
print("解密耗时ms：",time_end_dec-time_start_dec)
# print(encrypted_message_list[0]) 
print("原始数据:",decrypted_message_list)

# 测试加法和乘法同态
a,b,c = encrypted_message_list # a,b,c分别为对应密文

a_sum = a + 5 # 密文加明文
a_sub = a - 3 # 密文加明文的相反数
b_mul = b * 1 # 密文乘明文,数乘
c_div = c / -10.0 # 密文乘明文的倒数

# print("a:",a.ciphertext()) # 密文a的纯文本形式
# print("a_sum：",a_sum.ciphertext()) # 密文a_sum的纯文本形式

print("a+5=",private_key.decrypt(a_sum))
print("a-3",private_key.decrypt(a_sub))
print("b*1=",private_key.decrypt(b_mul))
print("c/-10.0=",private_key.decrypt(c_div))

##密文加密文
print((private_key.decrypt(a)+private_key.decrypt(b))==private_key.decrypt(a+b)) 
#报错，不支持a*b，因为通过密文加实现了明文加的目的，这和原理设计是不一致的，只支持密文加！
print((private_key.decrypt(a)+private_key.decrypt(b))==private_key.decrypt(a*b))

输出结果：

默认私钥大小： 2048
加密耗时ms： 0.298203706741333
解密耗时ms： 0.08876276016235352
原始数据: [3.1415926, 100, -4.6e-12]
a+5= 8.1415926
a-3 0.14159260000000007
b*1= 100
c/-10.0= 4.6e-13
True

原始输出：<phe.paillier.EncryptedNumber object at 0x0000021FA8D45948>

下面展示的是，密文 a 和 a_sum 的纯文本形式：

59402891142220912790068722502588843510414373562474086568444315748957242223594078920692702271013040021606
29112250432729616200776837445868267160099504562745796573462667874006977486270005004189820621257201450835
95286290689356511561050034589378294988530870333018543952400509575823371263067029816952672878333126830199
12208986921271655792833132186568426198749835897197910518523286423616088832223047227419760673704533751712
17666234428220524541795748215492186778080201463384785587109650922059620488750810820610208353759446327756
63599761170876116801234201028756739014984640927821609310541862790081520353932541832508051248201224689389
71663888043725931695624971340812273609840037340618675924979637363755629958553531479895408203143871220295
05550200561549096636090938755444294278352869503185166386110051892134296990595405592705392561103207638003
58299869294954878475975767806121717680031375299808709846636140664504646588469799220716699577174744942216
0489667837064719419647257623775441380514437451891391616187946871983652962799313678571231605178482982326
3942066705749797498295563002464378551086469243477774964906861706671750457013160048780896569331434212131
5645646993448311004999193535756597976896791889897514267674569532234756593580678428717217091

72503789972362890158089713963923142946932275137588893873066060260427422987448615020129740650415793994752
89914787143889439442015281242884303543642312363896285439888638028819276270617056080815670329543098775127
01648905463852468828750987243184163793796212024326243852761255262543153843882913223989533033703680463022
71727615221928710774152910338734478251782313696907369252419028755395837984878232285620473166801574172888
35172348816395393891011504158756832693190296645131334844289995463159465758702843877243366545420812051251
20595297949908969862969103991096698666458256858767772032163810844027965959247950116209042132351109507381
25626236050597600784840500488126185028857207215899544807724315656285338191150222488171263042105422201126
01674978993960011727259811180024593649056933109263484562202650600338390529529146293807864287176022641931
02933996451449299729208060812106919417895728958945870762206977076872453871000988134106413514712523248078
2493633868758490307717011567853786767850059340632080574917712549872331152518228238328842712445996133798
9827856340292353285798162662355801872734068579393510255567521972004997436755561169253567131819320662420
4286175621171760105641223750257069280416238463223625810169297046868940677578803461625885257

最后提供一个paillier 实现的 go 版本：https://github.com/Roasbeef/go-go-gadget-paillier

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
THE END
分享
二维码
< <上一篇
下一篇>>