论文是怎样炼成的（1） 

 陈智罡

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

故事没有完。

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

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

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

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

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

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

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

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

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

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

故事还没有完。

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