同态加密之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 N2) , N ) = 1gcd(L(g^λ mod N^2),N)=1gcd(L(gλmodN2),N)=1，后面会发现这里的 g=n+1。其中 Z 表示整数，下标表示该整数集合里有多少个元素；L(x)=x − 1N \frac{x-1}{N}Nx−1​， μ = ( L ( gλm o d N2) ) − 1mod    Nμ = (L(g^λ mod N^2))^{-1} \mod Nμ=(L(gλmodN2))−1modN；
  4. 公钥为 (N,g)；
  5. 私钥为(λ,μ)。

加密过程

对于任意明文消息 m∈ Z Nm∈Z_N m∈ZN​，任意选择一随机数 r∈ Z N ∗r∈Z_{N}^* r∈ZN∗​，计算得到密文 c ：

c=E(m)= g m r N m o d   N 2c=E(m)=g^mr^N \mod N^2 c=E(m)=gmrNmodN2

解密过程

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

m=D(c)= L( c λmod N 2)L( g λmod N 2)m o d    N=L( c λmod N 2)∗μ m o d    Nm=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

加法同态的性质

对于任意明文 m1，m2∈ Z Nm1，m2∈Z_N m1，m2∈ZN​和任意r1，r2∈ Z N ∗r1，r2∈Z_N^* r1，r2∈ZN∗​，对应密文c1=E[m1,r1]，c2=E[m2,c2]c1=E[m1,r1]，c2=E[m2,c2] c1=E[m1,r1]，c2=E[m2,c2]满足：

c 1⋅ c 2=E [ m1, r1]⋅E [ m2, r2]= gm 1+ m 2 ⋅ ( r 1⋅ r 2)N  m o d  N 2c_{1} \cdot c_{2}=E\left[m_{1}, r_{1}\right] \cdot E\left[m_{2}, r_{2}\right]=g^{m_{1}+m_{2}} \cdot\left(r_{1} \cdot r_{2}\right)^{N} \bmod N^{2} c1​⋅c2​=E[m1​,r1​]⋅E[m2​,r2​]=gm1​+m2​⋅(r1​⋅r2​)NmodN2

解密后得到：

D [ c1⋅ c2]=D [ E [ m 1, r 1]⋅ E [ m 2, r 2]   mod   N2]= m 1+ m 2  m o d   ND\left[c_{1} \cdot c_{2}\right]=D\left[E\left[m_{1}, r_{1}\right] \cdot E\left[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

即我们得到了：c1∗c2=m1+m2c1*c2=m1+m2 c1∗c2=m1+m2。密文乘等于明文加。

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

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

算法理论

由上式结论不难知道：μ= λ −1 μ=λ^{-1} μ=λ−1（g=n+1）。此外，还有 r λnm o d   N 2=1r^{λn}\mod N^2=1 rλnmodN2=1。

具体算法理论证明，参见：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("加密耗时s：",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("解密耗时s：",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加密耗时s： 0.298203706741333解密耗时s： 0.08876276016235352原始数据: [3.1415926, 100, -4.6e-12]a+5= 8.1415926a-3 0.14159260000000007b*1= 100c/-10.0= 4.6e-13True

原始输出：

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

594028911422209127900687225025888435104143735624740865684443157489572422235940789206927022710130400216062911225043272961620077683744586826716009950456274579657346266787400697748627000500418982062125720145083595286290689356511561050034589378294988530870333018543952400509575823371263067029816952672878333126830199122089869212716557928331321865684261987498358971979105185232864236160888322230472274197606737045337517121766623442822052454179574821549218677808020146338478558710965092205962048875081082061020835375944632775663599761170876116801234201028756739014984640927821609310541862790081520353932541832508051248201224689389716638880437259316956249713408122736098400373406186759249796373637556299585535314798954082031438712202950555020056154909663609093875544429427835286950318516638611005189213429699059540559270539256110320763800358299869294954878475975767806121717680031375299808709846636140664504646588469799220716699577174744942216048966783706471941964725762377544138051443745189139161618794687198365296279931367857123160517848298232639420667057497974982955630024643785510864692434777749649068617066717504570131600487808965693314342121315645646993448311004999193535756597976896791889897514267674569532234756593580678428717217091
725037899723628901580897139639231429469322751375888938730660602604274229874486150201297406504157939947528991478714388943944201528124288430354364231236389628543988863802881927627061705608081567032954309877512701648905463852468828750987243184163793796212024326243852761255262543153843882913223989533033703680463022717276152219287107741529103387344782517823136969073692524190287553958379848782322856204731668015741728883517234881639539389101150415875683269319029664513133484428999546315946575870284387724336654542081205125120595297949908969862969103991096698666458256858767772032163810844027965959247950116209042132351109507381256262360505976007848405004881261850288572072158995448077243156562853381911502224881712630421054222011260167497899396001172725981118002459364905693310926348456220265060033839052952914629380786428717602264193102933996451449299729208060812106919417895728958945870762206977076872453871000988134106413514712523248078249363386875849030771701156785378676785005934063208057491771254987233115251822823832884271244599613379898278563402923532857981626623558018727340685793935102555675219720049974367555611692535671318193206624204286175621171760105641223750257069280416238463223625810169297046868940677578803461625885257

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