基于Somewhat同态加密方案的一种证明 A Proof Based on the Somewhat Homomorphic Encryption Scheme

doi:10.12677/SEA.2013.22008

设为首页加入收藏期刊导航网站地图

期刊菜单

文章导航

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

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 等人提出“秘密同态”的概念之后，国

基于 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)

我们可以利用和







Eb的值计算出





Ea b



和





Ea b，而不需要知道的值。我们称满足式(1)

的算法为满足加法同态，满足式(2)的算法为满足乘法

同态。

,ab

2.2. 最近整数

对于只有一个整数位的有理小数





01232

eeeee



，即则

012

22ee ee



 





mod 2ee



 mode2e，用符号表示取最近整

数，即





12, 1ee e 2。

3. Somewhat 同态加密方案

在Gentry[3,5,6]的框架中，Somewhat 同态加密方案

是全同态加密方案的基础，记为：





,,,SHEkeygen Enc Dec Evaluate，由以下几个

部分组成：

参数选取：







，2





，









，











，











，其中：



为安全参数。安全

参数与方案的安全性相关，通常取几十到几百比特。

keygen ：随机选择



比特的奇素数和p



比特的

奇素数q，令 Npq



。然后选取两个随机整数

0, 2lp











，





2,2h



 。并计算

pl h



 (3)

设置公钥





kNx，私钥

kp。





,Encpk m：给定消息。选择两个随机

整数



0,1m





12,2r





 和





2,2



 ，根据公钥





kNx。计算

2modcm rrxN



 (4)

c作为密文输出。





,Decsk c：根据给定的密文c，利用私钥 sk 计

算





modmod2mc p

 (5)





,,, ,,

Evaluatepk Cccc：给定一个具有t输入

的布尔电路 C和t个密文 ci，将电路中的加法门和乘

法门替换成整数上模 N的加法门和乘法门。将t个密

文输入到扩展的电路中执行其所有操作，输出电路的

结果





,,cEvaluatepk C c

，验证其是否满足







,,,,

sk cCmmm

Dec 。

4. SHE 方案的一种证明

证明包括了两个部分，分别是解密正确性证明和

基于 Somewhat 同态加密方案的一种证明

同态正确性证明。下面就从这两个方面进行证明。

4.1. 解密正确性证明

1) 由加密算法中的式(4)，将



,Encpk m



Npq



带入其中，可得：

2modcm rrxpq  (6)

2) 将2

pl h带入式(6)中，得





22mocm rrplhpq d

(7)

继续化简，得：





12 2

22mocm rrplrhpq d





(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：







2mrrh

crl kq









(13)

由式(13)，可知整数商即 2

rl kq



。

5) 为了使得 2

cprl kq，我们必须要求



mrrh

 这时



2cpcp mrrh



0,1

(14)

6) 再对式(14)进行模 2运算，明文就可以正确地

恢复了。我们定义下面式称为噪声。所

以，当噪声的绝对值小于时，就可以正确的解密。



2mrrh

4.2. 同态正确性证明

在Gentry 的同态框架中，在电路内部中各个节点

更新着密文，使得密文的噪声在允许范围内，电路的

每一层都保证了噪声可控，任意深度的电路或多项式

都可以被同态处理。为了能够更新密文，就需要方案

能够同态处理其解密电路以及扩展的解密电路。下面

对somewhat同态方案进行同态正确性证明。

1) 设两个明文为和，分别对其用 Somewhat

同态加密方案进行加密：

2mod,

ii ii

cm rrxNi



  (15)

在解密正确性的步骤 2我们已知存在整数和使

得





122

iiiiii

cmrhrrlpkpqi  0,1

(16)

2) 再进行加运算



010110201121

20021 1

2ccmmr hrr hr

rl kqrl kqp

 

 (17)

可见满足：

















01 0

,EncmEncmEncmEncm 1

其中





, 0,1

Enc mci

。噪声变化为：







0110201121

01020111 21

mmr hrr hr

mrhrmrhr

 

  (18)

3) 再对和进行乘法运算，可以简要表示乘

法结果为

010 1

2ccmmABp



 (19)

可见满足



















01 0

,Enc mEnc mEnc mEnc m 1

，

其中





, 0,1

mc iEnc 。噪声变化为：







0 10102011121

22 2mmAmr hrmr hr (20)

4) 由式 (18)可见噪声在加法运算中是线性增长

的，而由式(19)可见噪声乘法运算中是平方增长的，

所以对方案的评估能力主要在于电路乘法深度或多

项式深度。

通过上述对于Somewhat 同态加密方案的解密正

确性和同态正确性的验证，证明了Somewhat同态加

密方案在解密和同态性的正确性。

5. 结语

同态加密方案在 1978 年由Rivest 等人提出到

2009 年Gentry 提出基于理想格的同态加密方案，经

历了 30 多年的时间。自Gentry 提出了 Somewhat 同

态加密方案，学术界对其进行了大量的研究，但是都

基于 Somewhat 同态加密方案的一种证明

是对于 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.