自己的沙场:全同态加密研究分享 http://blog.sciencenet.cn/u/chzg99 不要对我说生命中无聊的事,不要对我说失败是命运的事。

博文

整数上全同态加密方案分析(1)--献给全同态加密的初学者

已有 16735 次阅读 2012-9-27 12:54 |个人分类:信息安全|系统分类:科研笔记|关键词:的,加密,美国人,初学者,密码学| 美国人, 初学者, 密码学, 加密

    这篇文章是我当时给国外一个学者写的全同态加密的介绍。对方要求尽可能以简单的例子呈现,当时写着写着就成了一篇通俗的科普文章,我尽量用口语,假设对方没有密码学的深厚背景。由于简单的例子也需要大量的计算量,曾经为了一个小例子,我计算了好几天,还是没有出来,所以也就放弃了举例子的想法。愿此文能够领你进入全同态加密的门槛。国内好像没有这种科普学术的期刊。国外有个科学美国人就不错。好了,那就开始吧!


一篇论文看完了,如果都看懂了的话,很多人觉得案例都是小菜一碟,但是在我写这个案例的时候我发觉论文看懂了,更需要案例或者说实现来进一步深入或者夯实,因为只有通过具体的实现步骤,才能发现有些在论文中的一些细节问题,反过来更可以促进对论文的理解。

整数上全同态加密方案有两篇非常经典的论文,一篇是《Fully Homomorphic Encryption over the Integers》以下简称DGHV方案,还有一篇是Gentry写的《Computing Arbitrary Functions of Encrypted Data》简称 CAFED论文。入门者适合先阅读CAFED论文,这并不是说这篇论文简单,只是因为这篇文章的写法很通俗(严格意义上这篇文章并不是一篇真正的论文,是给杂志写的文章,有点科普性质),有一个很好的比喻的例子“Glovebox”贯穿于整个论文中,Gentry的文笔很好写的也很生动,对有些地方进行了背景解释,而这些解释恰好是DGHV论文中没有说的,当然一开始要想把CAFED论文彻底读懂也不是那么容易的。这个时候可以开始阅读DGHV这篇论文。这篇论文对于我来说是百读不厌,因为有些地方就算读了一百篇也不见得可以理解,而且这篇文章很适合深挖,有些很有趣的地方,例如噪声参数的设置等等。还有一篇论文就是全同态的经典论文《Fully homomorphic encryption using ideal lattices》,如果对格不熟悉的话,可以读这篇文章的前面三分之一,因为有详细的全同态的定义、层级全同态、允许电路、增强解密电路、bootstrable、重加密原理,以及如何通过递归实现全同态的,尤其是递归实现全同态的过程,在论文中还是值得反复理解的。剩下的当然还有Gentry的博士论文,也可以分阶段阅读。

这篇文章就算是我的一个阅读笔记吧,我打算写两个部分,一个是实现过程,另一个是方案的参数分析。

一、       方案实现过程

1、  全同态加密方案

至于什么是全同态等等形式化定义我就不说了,请参阅论文。

全同态加密用一句话来说就是:可以对加密数据做任意功能的运算,运算的结果解密后是相应于对明文做同样运算的结果。有点穿越的意思,从密文空间穿越到明文空间,但是穿越的时候是要被蒙上眼睛的。另外上面的那句话是不能说反的,例如:运算的结果加密后是相应于对明文做同样运算结果的加密,这样说是不对的,因为加密不是确定性的,每次加密由于引入了随机数,每次加密的结果都是不一样的,同一条明文对应的是好几条密文。而解密是确定的。

全同态具有这么好的性质,什么样的加密方案可以符合要求呢?往下看:

Enc(m):   m+2r+pq

Dec(c):   (c mod p) mod 2=c – p*c/p」)mod 2 = Lsb(c) XOR Lsb(c/p)

上面这个加密方案显然是正确的,模p运算把pq消去,模2运算把2r消去,最后剩下明文m 。这个公式看上去很简单,但是却很耐看,需要多看看。

公式中的p是一个正的奇数,q是一个大的正整数(没有要求是奇数,它比p要大的多),p q在密钥生成阶段确定,p看成是密钥。而r是加密时随机选择的一个小的整数(可以为负数)。明文m {0,1},是对“位”进行加密的,所得密文是整数。

上面方案的明文空间是{0,1},密文空间是整数集。

全同态加密方案中除了加密、解密还有一个非常重要的算法就是:Evaluate,它的作用就是对于给定的功能函数f以及密文c1,c2,,ct等做运算f (c1,c2,,ct)。在这里就是对密文做相应的整数加、减、乘运算。

以上方案可以看成是对称加密方案。下面来考虑公钥加密方案。其实把pq看成公钥就OK。由于q是公开的,所以如果把pq看成公钥,私钥p立刻就被知道了(p=pq/q)。怎么办呢?看上面加密算法中,当对明文0进行加密时,密文为2r+pq, 所以我们可以做一个集合{xixi=2ri+pqi},公钥pk就是这个集合{xi},加密时随机的从{xi}中选取一个子集S,按如下公式进行加密:

Enc(m):   m+2r+sum(S); 其中sum(S)表示对S中的xi进行求和。

由于sum(S)是一些0的加密密文之和,所以对解密并不影响,整个解密过程不变。

这个方案是安全的,就是我们所说的DGHV方案。其安全性依赖于一个困难问题“近似GCD问题”。就是给你一些xi,你求不出p来(由于整数上全同态研究热了,近似GCD也成了研究的一个点)。

为了说明方便,我们还是采取pq为公钥的方案(尽管不安全,但是不影响说明过程)。所以加密和解密还是按照一开始的公式,现在pq为公钥,p还是私钥,q是公开参数。再重复一遍我们的加密解密算法:

Enc(m):   m+2r+pq

Dec(c):   (c mod p) mod 2=c – p*c/p」)mod 2 = Lsb(c) XOR Lsb(c/p)

另外在这里约定:一个实数模p为:a mod p = a -a/p*p, a」表示最近整数, 即有唯一整数在(a-1/2, a+1/2]中。所以a mod p的范围也就变成了(-p/2p/2 ](这个牢记)。这个和我们平时说的模p范围是不一样的,平时模p范围是[0, p-1],那是因为模公式中取得是向下取整:a mod p = a –floora/p*p

Lsb是最低有效位,因为是模2运算,所以结果就是这个二进制数的最低位。

 

2、  可怕的噪音

由于公钥pq是公开的,所以知道密文c后可以减去公钥得到:

c-pq= m+2r

由于存在r的干扰,所以无法识别明文m。我们就把m+2r称为噪音。另外在解密时只有当c mod p=m+2r <p/2, 再对它进行模2运算才能正确解密:

m+2rmod 2= m

如果噪音大于p/2时,c mod p就不再等于m+2r,解密就可能无法正确恢复出明文。所以噪音是影响解密的关键。而噪音会在密文计算中增长,下面来看看增长的势头:

假设c1= m1+2r1+pq1; c2= m2+2r2+pq2; 其中c1是对密文m1的加密,c2是对密文m2的加密。

密文加和乘运算:

c1+c2=(m1+m2)+2(r1+r2)+p(q1+q2)

c1*c2=( m1+2r1)(m2+2r2)+p(pq1q2+m1q2+m2q1+2r1q2+2r2q1)

 

(c1+c2) mod p= (m1+m2)+2(r1+r2)

c1*c2 mod p=( m1+2r1)(m2+2r2)

由上可见:密文之和的噪音是各自密文的噪音之和;而密文乘积的噪音是噪音之积。因此噪音的主要来源还是乘法运算,在乘法运算中噪音被放大的很快。

例如:设p=11, q=5, m1=0, m2=1,然后分别随机选取r1=1r2= - 4, 有:

c1=Enc(m1)=m1+2r1+pq=0+2*(-1)+11*5=53;  c1 mod p= -2, Dec(c1)=0.

c2=Enc(m2)=m2+2r2+pq=1+2*1+11*5=58;  c2 mod p= 3, Dec(1)=1.

因为c1 mod p c2 mod p 都是在(-p/2p/2)范围内,所以解密正确。c1c2称之为新鲜密文,就是直接由明文生成的密文,在新鲜密文中噪音是在一定合理的范围内的。

我们再来看看c1*c2:

c*=c1*c2=53*58=3074; c* mod p=5, Dec(c*)=1m1*m2=0, 解密错误,错误的原因是噪音c* mod p= -6 不在(-p/2p/2)范围内。

看来对密文运算会造成噪音的增大,当噪音超出范围,解密就失败,这意味着对密文运算不可能是无限次的(也就是Evaluate运算功能函数的电路深度是有限的,这在后面我们说到电路时会看到)。到这里我们只得到了一个运算时噪音范围不能超过p/2的同态方案(Somewhat 同态方案),看来似乎用这个方案实现全同态是行不通的。我们需要的是全同态方案即Evaluate可以运行任意功能函数,而不是某一类功能函数(这叫同态方案)。估计多少英雄好汉到了这里就觉得没戏了,于是另寻他路,于是一个突破就擦肩而过。那么下面让我们分析一下症结所在。





http://blog.sciencenet.cn/blog-411071-617182.html

上一篇:加载NTL 到 DEV C++中
下一篇:整数上全同态加密方案分析(3)--献给全同态加密的初学者

1 江洋

该博文允许注册用户评论 请点击登录 评论 (5 个评论)

数据加载中...
扫一扫,分享此博文

Archiver|手机版|科学网 ( 京ICP备07017567号-12 )

GMT+8, 2020-4-7 02:05

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部