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

博文

论文是怎样炼成的(1) 精选

已有 11092 次阅读 2014-1-15 02:30 |个人分类:全同态|系统分类:科研笔记| 论文, style

论文是怎样炼成的(1 

 陈智罡

 

论文是怎样写出来的,如果不是作者本人,我们是无从知道其真实的出发点、灵感的获取、以及是如何解决过程中所碰到的困难的。就像历史,我们永远无法知道当时当事人真正的心思、真正的事情过程。

 

但是我们可以推测。当你读论文的时候,当你有了一定的功力的时候,读者和论文仿佛“天人合一”了,这个时候我们可以做出这种假设:如果是你的话,你能写出这篇论文么?

 

经常这样想对提高自己看问题的角度,以及做论文的方法是非常有好处的。当然,这需要你是敏感的、能够体会论文中字里行间的意义。如果你把读论文当成一种快乐的话,就会有这种体会。如果你没有这种快感,那就另当别论了。

 

下面我们来看看这篇论文是如何炼成的。

 

Homomorphic Encryption from Learning with ErrorsConceptually-Simpler Asymptotically-Faster Attribute-Based”,2013年美密会一篇全同态加密的文章,作者是:Gentry还有另外两个作者。

 

因为在这之前,全同态最好的方案就是密文是向量,密钥是向量,基于LWE上的方案。但是由于密文是向量,密文的加法是可以做的,就是正常的加法,但是密文的乘法如何做呢?你见过向量做乘积了么?而且要求密文向量乘积的结果解密后必须是原来明文的乘积。

 

Brakerski观察到一个事实,两个密文的乘积可以表示成两个密文向量的张量,说通俗点,就是用第一个向量中的每一个元素乘以第二个向量中的所有元素,相应的密钥也变成了两个相同密钥向量的张量,这样解密是正确的。然而,这样一次乘法就使得n维密文变成了n2维密文,密钥也变成了n2维。最多只能做几次乘法,密文膨胀的就使得密文计算进行不下去了。

 

Brakerski发明了一个技术:再线性化技术。该技术使得n2维密文能够魔术般的缩回到原来的n维尺寸,对应的n2维密钥变成了一个新的n维密钥。

 

这导致LWE上的全同态加密方案诞生了。但是每次密文计算后,都要用再线性化技术将密文的维数进行约减。再线性化的过程很简单,但是该过程却是一个高维矩阵的乘积,非常耗费计算量。

 

这世界是能量守恒的,此出必有彼出。

 

所以引出了一个问题,密文乘积计算如果维数不膨胀就好了。

 

上面这句话就是问题的出发点。没有人告诉你,只有靠自己在读论文中体会。尤其是对于那些没有经费开国际会议的。退一万步,就算你去开会,碰到了Gentry,他也不会平白告诉你这是个问题的。

 

有了问题必然有思考。Gentry在思考,你也在思考。相信开始时大家都差不多。

 

一个直觉就是,密文如果是矩阵(方阵)的话,方阵乘以方阵还是矩阵,维数没有任何变化,这样就不需要用再线性化技术了。

 

这个直觉我也想到了,相信很多人想到了。但是一篇论文“A Simple BGN-type Cryptosystem from LWE”让我打消了用矩阵构造的想法。这篇论文是Gentry2010年写的。这篇论文是用矩阵来构造密文的,但是方法是用Gentry的老套路。文章特别强调由于矩阵不具有交换性,所以该方案只能做一次乘法。

 

这个时候,相信大家和Gentry一样,都对矩阵构造密文做全同态不抱什么希望了。大家又在同一起跑线上了。

 

紧接着,看到一篇论文“An Efficient Homomorphic Encryption Protocol for Multi-User Systems”,作者是LiangliangXiao。这篇论文是在2012年在eprint上发出来的,一直没有发表。这篇文章也是做密文计算的,里面用到特征向量和特征矩阵,但是加密形式不同。

 

我不知道gentry看到没有。谁也不知道。

 

人的差别就在于,我看完后没有其他想法,因为功力浅。紧接着在20136月,就看到了这篇Gentry用特征向量做密钥,特征值做明文,密文是矩阵的上述文章。

 

故事没有完。

 

假设你发现了:特征向量做密钥,特征值做明文,密文可以是矩阵的方法。接下来我们看看你能够做出全同态方案么?

 

按照常理,想构造全同态方案,必须要解决噪音在计算中的增长问题。加法还和老传统一样,增长的很慢,就是噪音之和。乘法呢?你肯定发觉乘法的噪音依赖于密文,只要搞全同态的,都会发现的。

 

以往的方案,在密文乘积中,噪音要么是两个密文的噪音之积,要么噪音依赖于密钥的范数。还没有发现噪音依赖于密文的。考验人的时候到了。

 

密文的最大值就是模的值,如果密文乘积后噪音的值大于模,解密的正确性就保证不了了。这种噪音的增长依赖于密文的情况,简直是一种灾难,一个极大的坏消息,连一次乘法都进行不了。怎么办呢?

 

常规解决方法就是对密文做BitDecomp,把密文矩阵中的每一个值进行位分解,使得密文的范数变小。这是全同态中的老一套了,任何搞全同态的人都可以想到。

 

但是你能想到Flatten这个技术么?它能把密文的值重新变回0或者1,而且保证解密形式不变。这是这篇文章成立的一个最大核心点,也是最大难点。

 

从出发点到论文的炼成,也许作者和普通的研究者没有什么区别,关键是在解决关键问题上的那么一点,那一点就是点石成金了。靠什么?靠直觉? 靠运气?靠努力?说不清。

 

所以有些东西是没有办法的。想到和想不到之间也许只有一步之遥,但是有时就是跨不过去。做研究这几年,我才慢慢体会到哲学和科学原来是那么的相似。

我们经常费劲心思的把论文搞清楚,但是我们忘了,搞清楚的目的是为了什么?

 

我想,应该是为了抽象到一个更高的层次去看论文中如何解决这个问题的。这样当我们在其他地方碰到类似的情况时,直觉就会冒出来。

 

故事还没有完。

 

Gentry这篇论文在美密会上发表后,大家都看了,有人却看到了玄机。下次再说。




https://blog.sciencenet.cn/blog-411071-759220.html

上一篇:常用的时间计算复杂度
下一篇:英国访问学者答疑(四):给签证官的信
收藏 IP: 134.219.227.*| 热度|

18 曹聪 强涛 陈松战 Editage意得辑 刘军胜 唐常杰 孙爽 郭嘉琳 李宇斌 韦玉程 王志杰 杨渺 高绪仁 吴艳华 李冰 chenyuhuazililu Mathermo tenecneics

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

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

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

GMT+8, 2024-6-24 02:03

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部