第 35 卷 第 4 期 电 子 科 技 大 学 学 报 Vol.35 No.4 2006 年 8 月 Journal of University of Electronic Science and Technology of China Aug. 2006 对G-Paillier加密体制的改进与分析 姜正涛1 ，柳 毅 2，王育民2 (1. 北京航空航天大学计算机学院 北京 100083; 2. 西安电子科技大学综合业务网国家重点实验室 西安 710071) 【摘要】通过适当地选择参数改进了推广的Paillier (G-Paillier)加密体制，减少运算量，提高了加密体制的效率；证明了 改进后加密体制的安全性(单向性、语意安全性)与G-Paillier加密体制的安全性是等价的。 关 键 词 概率加密体制; 安全性分析; n次剩余问题; 单向性 中图分类号 TP309+.7 文献标识码 A Improvements and Analysis of G-Paillier Encryption Scheme JIANG Zheng-tao1，LIU Yi2，WANG Yu-min2 (1. School of Computer Science, Beijing University of Aeronautics and Astronautic Beijing 100083; 2. National Key Lab. of Integrated Service Networks, Xidian Univ. Xi’an 710071) Abstract The efficiency of the generalized Paillier (G-Paillier) encryption scheme is improved by choosing proper parameters. The efficiency of the improved G-Paillier scheme and the original G-Paillier scheme is compared. The security (one-wayness security, semantic security) equivalence of the improved encryption scheme and the G-Paillier encryption scheme is verified. Key words probabilistic encryption scheme; security analysis; nth residuosity; one-wayness 基于计算和判断 上的n次剩余问题，文献[1-2]提出了一种抵抗CCA2攻击的概率加密体制，该体制具 有语意安全性，可直接用于加密电子投票等有意义的明文消息；文献[3-4]对这一体制的应用与安全性做了 有意义的探讨和分析；文献[5]推广了这一体制，并运用它所具有的同态加密的性质给出了在电子投票方面 的应用。 2nZ * 加密体制效率的高低直接影响它能否在实际中应用。一种安全的、高效的加密体制会给密码应用领域 带来巨大的影响，而且一种安全的加密体制还应是能够抵抗CCA2攻击的概率加密体制。本文在不降低 G-Paillier体制(即推广的Paillier体制)的安全性的前提下，选择适当形式的加密参数，明文加密时用乘法运算 代替指数运算；同时也改进了解密算法，提高了体制的效率，降低了需要传输公共参数的数据量；并证明 了改进的加密体制与G-Paillier体制一样，在相同的困难问题假设下具有单向和语意安全等特性。 1 G-Paillier加密体制 G-Paillier加密体制(设为加密体制1)下， pq nZH ≅ * H 可以看作 中形如 元素的集合， n = 为RSA模； Z sn 1+∈ snZh 1+snZ ，且 5nh * * * 1 ≅+ [5]。 HG × ，其中 是阶为 (s≥1)的循环 sn G 群， 1.1 相关参数 (1) 公开参数 (2) 秘密参数 n = pq lcmλ = 1.2 加、解密过程 ， p ( * 1( 1+∈ snZg += ，满足 ,1 )1 ；整数 满足d − − q g 1 + n xn ) j d mod mod n Z∈ ， s * n ，解密用户知道 0≡d λmod ； +∈Zj snZm ∈ ， Hx ∈ 。 =nj 1),( ， 是待加密的消息。 (1) 加密用户随机选取 (2) 解密用户计算 ≡ dC * 1+∈ snZr C mod d rgC nm = ，计算 n + n 1( s jdm 1 += ) s n mod + s 1 s 1 + 。 (*)，并恢复明文 mod n m = ( jd ) 1− jdm mod sn 。 收稿日期：2003 − 12 − 02 作者简介：姜正涛(1976 − )，男，博士，主要从事密码等可信计算和抗毁生存等方面的研究. 

第 4 期 姜正涛 等: 对 G-Paillier 加密体制的改进与分析 529 1.3 效率分析 上做两次大指数模乘法运算和一次模乘法运算。 (1) 加密阶段，加密用户需在 (2) 解密阶段，解密用户首先需要做模指数运算，计算求出 的值；然后由 求 1+snZ dC dC i = jdm mod sn (*)； 最后根据文献[5]的算法，计算以下参数： ) mod i ((1 n + 2 n ((1 + n ) mod ) i 3 n n i ) mod = i ⎛ ⎞ 1 − ⎜ ⎟ 2 ⎝ ⎠ n n mod L L i ⎧ = 1 ⎪ ⎪ = i ⎪⎪ 2 ⎨ ⎪ M ⎪ ⎪ = = i ⎪ ⎩ i s 2 (1) L ((1 + n ) mod i n s 1 + ) − i s 1 − 2 ⎛ ( ⎜ ⎝ ⎞ ⎟ ⎠ n + + L i s 1 − s ⎛ ⎜ ⎝ ⎞ ⎟ ⎠ s 1 − n )mod s n 由于计算 i l ⎞ ⎛ ⎟+⎝ ⎜ l 1 ⎠ l n 至少需要 次模乘法运算 l2 l = 1,2, −L s , 1 ，于是这个过程远远大于 次模乘法运算。 22s 但本文不区分除法和乘法运算，也没有考虑求 的幂运算。 2 改进的G-Paillier加密体制 2.1 相关参数 ln 改进的G-Paillier加密体制(设为加密体制2)下，参数选择同于G-Paillier加密体制，其中 g += 1 ；解密指 n d 1≡sdn 数 满足 2.2 加、解密过程 λmod ； snZm ∈ 是待加密的消息。 (1) 加密用户随机选取 nZy ∈ * ，计算 (2) 解密用户计算 Cy ≡ d mod ；n m 2.3 效率分析 = C 1( += sn y C − ymn ) n mod s n s + 1 n 。 s n mod 1 1 + − 。 (1) 加密过程主要包括求 的指数模乘法运算和2次模乘法运算。对于经常加密的用户，可以 mod +s 1 事先随机选取多个 ，并秘密保存。加密时只需随机选择其中一个进行加密运 算，这样在加密时只需做两次模乘法运算即可。 n mod +s 1 y s n ，做预计算 nZy ∈ * n y s n (2) 解密过程主要包括1次大指数模乘法运算、1次小指数模乘法运算和2次模乘法运算。本文也不区分 乘法与除法运算。 3 两种加密体制的运算效率比较 nZr ∈ * 加密体制2的加密阶段选取的随机数 与加密体制1的加密阶段选取的随机数 + ， 则 = y y 1+∈ snZy 0 * * 1+∈ snZr ny L1 + 相比，提高了 sny + ， 其 中 s 运 算 的 效 率 ， 并 且 没 有 降 低 体 制 的 安 全 性 。 事 实 上 ， 若 y ∈ s , Z k , n 1,2, = L k ；且有： n s y mod n s 1 + = ( y 0 + y n 1 + +L y n s s ) mod s n sn 1 + = sn y 0 mod n + s 1 改进的G-Paillier加密体制与G-Paillier加密体制的效率比较见表1。图中2−E(ns+1)表示2个modns+1指数运 算；1−M(ns+1)表示1个modns+1乘法运算；>>s2−M(mod)表示远远多于s2个modnk形式的模乘法运算，且k=1， 2，…，s+1。 表1 运算效率比较 加密 解密 加密体制1 加密体制2 2−E(ns+1) 1−M(ns+1 ) 1−E(ns+1) >>2s2−M(mod) 1−E(ns+1) 2−M(ns+1) 1−E(ns+1) 1−E(n) 1−M(n) 

电 子 科 技 大 学 学 报 第 35 卷 530 当s≥1时，由于E(ns+1)的计算量远远大于E(n)的计算量(分别计算 ， d λ< )，显然加密体制2的效率要比加密体制1的效率高，即使在最坏的情况下也至少减少了(s+1)lbn−lbn=slbn 次“平方-乘法”运算。1−E(n)大约需要lbn次“乘法-平方”运算，当n为1 024比特的RSA模时，约需1 024 次模n的“乘法-平方”运算，当s≥23时(2s2≥1 024)，改进的加密体制无论加密还是解密均比G-Paillier加密 体制的效率高。而当s是比较小的数时(如s=3,4等)，加密体制2的解密效率可能不及加密体制1的解密效率高， 但此时(最坏的情况)从加、解密的整个过程来看，仍然比加密体制1少做了slogn次“平方-乘法”运算。 snZm ∈ mod +s 1 C d mod ， 和 n g n m 表2是当RSA模数为1 024比特的合数时，需要传输公共参数的数据量比较。 表2 传输数据比较 加密体制1 传输数据量/(bit) n,g (1 024+(s+1)×1 024) 加密体制2 n (1 024) 可以证明加密体制2的加密阶段选取的随机数 nZr ∈ * 比，提高了运算的效率，并且没有降低体制的安全性。事实上，若 中 ky k ，且 Z∈ n 另外，可以对加密体制2做进一步改进，在加密时，密文 1,2 = L， 。 , s RSA中的公开密钥；解密指数d满足 de ≡ 1 mod ϕ n )( Cy ≡ d mod n 和 4 安全性分析 1+∈ snZr 与加密体制1的加密阶段选取的随机数 sny + ny L1 1+∈ snZy ，则 + + = y y 0 * * s 相 ，其 e C mod ymn ) 1( += n ； )(⋅ϕ 是欧拉函数。解密时计算 Cym 1 − + n 1 = − e s s mod n 1 + ； 为公开参数，同于 e 定理 1 当且仅当加密体制1是单向的，加密体制2是单向的。 C 证明 体制1的密文是 1( = 1 nmmm 献[5]的算法，知道 = + + 1 2 sn mn y n (1 ) mod + ；体制2的密文是 ) 后，可以求得整数M满足： 1( + + n ( ) snm + (1 = + n ) mod rx nm s 1 − m n y mod L s 1 + + s+ 1 n jm 1 + n s s s s m n 1 +L s C 2 = 1( + ymn ) s n mod n s 1 + 。根据文 = m 2C n s s ) 1 + n y nM mod (2) M 与 恢 复 M 的困难性，来讨论由密文 恢 2C 同 样 ， 知 道 M 后 也 可 通 过 计 算 求 得 式 (2) 中 相 应 的 。 因 此 ， 攻 击 者 恢 复 在计算上是等价的，可以通过分析由密文 恢复 = + nmmm + 2 复明文m的困难性。 L + 1 s 1 − snm 假设加密体制2不是单向的，即攻击者能够由 计算2C M ，当且仅当可以由 2C 1+snZ 1( * + 计算 g 中的 n 次剩余；当且仅当可以由 。于是，加密 体制1无单向性；反之，假设加密体制1无单向性，可以用类似的方法证明加密体制2也无单向性。因此，加 密体制2与加密体制1的单向性是等价的。 r 都是加密者随机选取的，所以由 H 的定义可知，x 是 jm jmmod j ，求得 j 后计算 ，由文献[5]对 (1−= M ，由于 和y mod ) n mod n ( ) 1( += rx nm xn ) j jm mod n s 1 + 计算 求得 C 1 sn sn = ) jm 1 + s s 定义 1 如果在仅知道两条明文 m′ 、m ′′ 以及其中一条明文对应的密文 的情况下，攻击者不能判断C C 是哪条明文对应的密文，就说此加密体制具有语意安全特性。 文献[1]给出了判断 n 次剩余的定义，为了便于讨论，本文给出推广判断高次剩余的定义。 定义 2 判断 次剩余已知 n sCS 称为判断 次剩余问题，记为 。 ，判断是否存在一个元素 1+∈ snZw 1+∈ snZg gw ，满足 kn sn ≡ n s mod + s 1 的问题， 定理 2 加密体制2与加密体制1的语意安全性是等价的，且均等价于 。 证明 由定理1，给定明文 和 ，攻击者可以求得具有式(2)形式的 和 。当且仅当能够判断加 2M 密体制1的密文对应的明文消息，于是能够判断加密体制2的密文对应的明文消息。 m′ m ′′ sCS 1M 因此，加密体制2与加密体制1的语意安全性是等价的，并且显然等价于 问题的困难性。 定理 3 当且仅当由 是困难的，加密体制2(即加密体制1)是单向的。 mod +s 1 y sn mod sCS y s n 求 n n (下转第566页)