Software Engineering and Applications 软件工程与应用, 2013, 2, 43-46 http://dx.doi.org/10.12677/sea.2013.22008 Published Online April 2013 (http://www.hanspub.org/journal/sea.html) A Proof Based on the Somewhat Homomorphic Encryption Scheme* Jing Yang1, Mingyu Fan1, Guangwei Wang1, Zhiyin Kong2 1University of Electronic Science and Technology of China, Chengdu 2Science and Technology on Information Assurance Laboratory, Beijing Email: ay4922@163.com Received: Feb. 4th, 2013; revised: Feb. 19th, 2013; accepted: Mar. 1st, 2013 Copyright © 2013 Jing Yang et al. This is an open access article distributed under the Creative Commons Attribution License, which permits unre- stricted use, distribution, and reproduction in any medium, provided the original work is properly cited. Abstract: In the Gentry’s Homomorphic encryption scheme, Somewhat homomorphic encryption is the base of Gen- try’s homomorphic encryption. For the present study is based on the most Somewhat homomorphism encryption scheme to develop without Somewhat homomorphism encryption scheme proof, this paper gives a proof based on Somewhat homomorphism encryption scheme. Keywords: Somewhat Homomorphic Encryption; Homomorphism; Decryption 基于 Somewhat 同态加密方案的一种证明* 杨 竞1,范明钰 1,王光卫 1,孔志印 2 1电子科技大学计算机学院,成都 2信息保障技术重点实验室,北京 Email: ay4922@163.com 收稿日期:2013 年2月4日;修回日期:2013年2月19 日;录用日期:2013 年3月1日 摘 要:在Gentry 的同态加密理论中,Somewhat 同态加密是 Gentry 框架中的全同态加密方案的基础。由于目 前的研究多数是基于 Somewhat 同态加密方案的拓展而少有对 Somewhat同态加密方案的证明,本文给出基于 Somewhat同态加密方案的一种证明。 关键词:Somewhat 同态加密;同态性;解密 1. 引言 目前,云计算有着巨大的发展前景,云计算的应 用已经成为企业和政府的一种趋势。但是云计算的应 用存在巨大的瓶颈,那就是云计算的安全问题[1]。在 云背景下,为了保障安全,云服务商需要对用户加密 后的数据进行操作,但是如果采用传统的密码算法, 必须先解密用户加密的明文,才能进行云计算处理。 而采用同态加密算法,可以对用户加密后的数据进行 操作而不用先解密,这样就可以解决云计算的安全问 题。 1978 年Rivest,Adleman 和Dertouzos[2]提出了“秘 密同态”的概念,即一种算法可以像对明文一样对密 文进行各种计算。Rivest 等人给出了同态加密方案的 4个算法。Rivest 方案满足加法和乘法的同态,小数 据加密问题,能够抵御已知明文攻击和已知密文攻 击。 *资助信息:受信息保障技术重点实验室(Science and Technology on Information Assurance Laboratory)开放基金资助。 在Rivest 等人提出“秘密同态”的概念之后,国 Copyright © 2013 Hanspub 43 基于 Somewhat 同态加密方案的一种证明 内外学者对同态加密进行了大量的研究[3],但所提出 的方案均不能做到同态计算任意深度电路或任意次 数多项式处理[4],全同态加密是密码学者多年来一直 期望解决的问题。全同态加密能够在没有密钥的条件 下,对加密数据进行任意复杂的操作,以实现相应的 明文操作。直到2009 年,Gentry[5,6]基于理想格提出 了第一个全同态加密方案,并在他的博士论文中对全 同态加密做了详尽的研究,解决了这个困扰密码学界 30 年的问题。 Gentry 提出的思路由以下三个方面组成: 1) 提出了自举性的思想,所谓自举性,是指一个 同态方案能够同态处理自己的解密电路以及扩展解 密电路。由于加密中噪声的存在(本文的 4.1 有关于噪 声的定义和描述),加法同态和乘法同态会使噪声增 加,因此方案的同态处理能力是有限的。如果方案具 有自举性,就可以通过同态解密来降低密文的噪声, 扩大其同态处理能力,以致能够处理任何复杂的布尔 电路。 2) 描述了一个具有自举性,使用理想格的公钥加 密理论。基于格的密码体系在加密算法上有低电路复 杂度,理想格提供了加法同态和乘法同态。 3) 引入了“压缩解密电路”的技术,降低解密算 法的计算复杂度。该技术产生了辅助解密计算的预处 理密文信息的技术。 在文献[7]中,对 Gentry 方案的证明了在整数环 上的全同态加密算法。由于现在文献多数在于阐述 Gentry 的方案而很少给出详细证明,本文给出 Somewhat 同态加密方案的解密正确性和同态性的一 种证明。 2. 相关定义 2.1. 同态 设R表示明文空间,S表示密文空间。 ,ab R , E是上的加密函数,如果存在算法 和 RS ,使 其满足: ,Ea bEa Eb (1) ,Ea bEaEb (2) 我们可以利用 和 Ea Eb的值计算出 Ea b 和 Ea b,而不需要知道 的值。我们称满足式(1) 的算法为满足加法同态,满足式(2)的算法为满足乘法 同态。 ,ab 2.2. 最近整数 对于只有一个整数位的有理小数 01232 eeeee ,即 则 12 012 22ee ee 01 mod 2ee mode2e,用符号 表示取最近整 数,即 12, 1ee e 2。 3. Somewhat 同态加密方案 在Gentry[3,5,6]的框架中,Somewhat 同态加密方案 是全同态加密方案的基础,记为: ,,,SHEkeygen Enc Dec Evaluate,由以下几个 部分组成: 参数选取: ,2 , 2 , 4 , 5 ,其中: 为安全参数。安全 参数与方案的安全性相关,通常取几十到几百比特。 keygen :随机选择 比特的奇素数 和p 比特的 奇素数q,令 Npq 。然后选取两个随机整数 0, 2lp , 2,2h 。并计算 2 x pl h (3) 设置公钥 , p kNx,私钥 s kp。 ,Encpk m:给定消息 。选择两个随机 整数 0,1m 12,2r 和 2,2 2 r ,根据公钥 , p kNx。计算 12 2modcm rrxN (4) c作为密文输出。 ,Decsk c:根据给定的密文c,利用私钥 sk 计 算 modmod2mc p (5) 12 ,,, ,, t Evaluatepk Cccc:给定一个具有t输入 的布尔电路 C和t个密文 ci,将电路中的加法门和乘 法门替换成整数上模 N的加法门和乘法门。将t个密 文输入到扩展的电路中执行其所有操作,输出电路的 结果 ,,cEvaluatepk C c ,验证其是否满足 12 ,,,, t sk cCmmm Dec 。 4. SHE 方案的一种证明 证明包括了两个部分,分别是解密正确性证明和 Copyright © 2013 Hanspub 44 基于 Somewhat 同态加密方案的一种证明 同态正确性证明。下面就从这两个方面进行证明。 4.1. 解密正确性证明 1) 由加密算法 中的式(4),将 ,Encpk m Npq 带入其中,可得: 12 2modcm rrxpq (6) 2) 将2 x pl h带入式(6)中,得 12 22mocm rrplhpq d (7) 继续化简,得: 12 2 22mocm rrplrhpq d b p (8) 3) 根据模的定义,我们可知存在一个 k,使得 mo dabak (9) 由式(9)我们可得: 22 22 2mod 2rpl rhpqrpl rhkpq (10) 代式(10)入式(8),有: 12 2 2cmrrh prlkq (11) 4) 设 取值在 modc 2, 2pp之间,则有: modcpcpcp (12) 而cp事实上是求 c除以p的整数商,由步骤3 最终化简得到的式(11)再除以p: 12 2 2mrrh crl kq pp (13) 由式(13),可知整数商即 2 rl kq 。 5) 为了使得 2 cprl kq,我们必须要求 12 21 2 mrrh p 这时 12 2cpcp mrrh 0,1 (14) 6) 再对式(14)进行模 2运算,明文就可以正确地 恢复了。我们定义下面式 称为噪声。所 以,当噪声的绝对值小于时,就可以正确的解密。 12 2mrrh 2 4.2. 同态正确性证明 在Gentry 的同态框架中,在电路内部中各个节点 更新着密文,使得密文的噪声在允许范围内,电路的 每一层都保证了噪声可控,任意深度的电路或多项式 都可以被同态处理。为了能够更新密文,就需要方案 能够同态处理其解密电路以及扩展的解密电路。下面 对somewhat同态方案进行同态正确性证明。 1) 设两个明文为和,分别对其用 Somewhat 同态加密方案进行加密: 0 m1 m 12 2mod, ii ii cm rrxNi (15) 在解密正确性的步骤 2我们已知存在整数 和 使 得 0 k1 k 122 2, iiiiii cmrhrrlpkpqi 0,1 (16) 2) 再进行加运算 010110201121 20021 1 2ccmmr hrr hr rl kqrl kqp (17) 可见满足: 01 0 ,EncmEncmEncmEncm 1 其中 , 0,1 ii Enc mci 。噪声变化为: 0110201121 01020111 21 2 22 mmr hrr hr mrhrmrhr (18) 3) 再对 和进行乘法运算,可以简要表示乘 法结果为 0 c1 c 010 1 2ccmmABp (19) 可见满足 01 0 ,Enc mEnc mEnc mEnc m 1 , 其中 , 0,1 ii mc iEnc 。噪声变化为: 0 10102011121 22 2mmAmr hrmr hr (20) 4) 由式 (18)可见噪声在加法运算中是线性增长 的,而由式(19)可见噪声乘法运算中是平方增长的, 所以对方案的评估能力主要在于电路乘法深度或多 项式深度。 通过上述对于Somewhat 同态加密方案的解密正 确性和同态正确性的验证,证明了Somewhat同态加 密方案在解密和同态性的正确性。 5. 结语 同态加密方案在 1978 年由Rivest 等人提出到 2009 年Gentry 提出基于理想格的同态加密方案,经 历了 30 多年的时间。自Gentry 提出了 Somewhat 同 态加密方案,学术界对其进行了大量的研究,但是都 Copyright © 2013 Hanspub 45 基于 Somewhat 同态加密方案的一种证明 Copyright © 2013 Hanspub 46 是对于 Somewhat同态加密方案的表述,而少有验证。 我们通过整理已有的Somewhat 同态加密方案的资 料,对于 Somewhat 同态加密方案的解密正确性和同 态性进行了证明,并给出了证明的详细步骤。 参考文献 (References) [1] 冯登国, 张敏, 张妍等. 云计算安全研究[J]. 软件学报, 2011, 22(1): 71-83. [2] R. L. Rivest, L. Adleman and M. L. Deaouzos. On data banks and privacy homomorphism. In R. A. DeMillo, Ed., Foundations of secure computation. New York: Academic Press, 1978: 169- 179. [3] J. Domingo-Ferrer. A provably secure additive and multiplica- tive privacy homomorphism. In Proceedings of the 5th Interna- tional Conference on Information Security. Berlin: Springer- Verlag, 2002: 471-483. [4] N. P. Smart. 密码术与编码[M]. 武汉: 湖北辞书出版社, 2008: 126-128. [5] C. Gentry. A fully homomorphic encryption scheme. Stanford: Stanford University, 2009. [6] G. Gentry, S. Halevi. Implementing Gentry’s fully homomorphic encryption scheme. Advances in Cryptology-EUROCRYPT 2011 Lecture Notes in Computer Science, 2011, 6632: 129-148. [7] 徐鹏, 刘超, 斯雪明. 基于整数多项式环的全同态加密算法 [J]. 计算机工程, 2012, 24: 1-4. |