整数上全同态加密方案分析
陈智罡博客：http://blog.sciencenet.cn/blog-411071-617182.html
《Fully Homomorphic Encryption over the Integers》简称DGHV方案
《Computing Arbitrary Functions of Encrypted Data》简称 CAFED论文
我是先从陈智罡的博客开始学习全同态加密的，毕竟是中文写的，添加了不少自己的理解，比直接阅读英文论文来的简单。但因为陈智罡已经详细地阅读过英文文献，所以有许多关于全同态加密的基本概念并没有介绍的很清楚。这时候如果我们想弄懂那些基本概念，我们就该阅读《Fully Homomorphic Encryption over the Integers》这篇英文论文了。论文篇幅有点长，如果想加快进度，可以先翻译成中文再进行阅读。至于Gentry写的《Computing Arbitrary Functions of Encrypted Data》，这相当于一篇科普类型的文章，不过如果你把它想的太简单，我想说你错了。这里面也有许多专业的名词，简单来说Gentry就是把他的博士论文简化了来给我们介绍全同态加密，可大神的思路岂是我们这些凡人可以简单领悟的。当然了，Gentry的物理比喻简直是太精妙了，让人不得不佩服。接下来我就先从Gentry的物理比喻开始整理我的学习思路。
1. Alice的珠宝店
Alice是一家珠宝店的老板，她想让工人把金子、钻石等稀有材料加工成项链、手链等。但是工人在加工的过程中有可能会偷这些稀有材料呀，毕竟这些稀有材料都很值钱呢…因此能不能有一种方法，让工人可以对稀有材料进行加工，但是不能得到任何稀有材料？
Alice想的解决办法：Alice将这些稀有材料锁在一个密闭的、透明的盒子里面，这个盒子安装了一个手套。工人可以带着这个手套，对盒子内部的稀有材料进行处理。但是由于盒子是锁着的，所以工人不仅拿不到稀有材料，连处理过程中掉下的任何材料都拿不到。加工完成后，Alice拿回这个盒子，把锁打开，就得到加工完成的成品。
这个盒子大概是这个样子的：
看起来Alice想的这个办法不错，刚好Acme Glovebox公司生产这样的手套箱，所以Alice从Acme Glovebox公司订购了一个手套箱。 但不幸的是，她收到的手套箱是有缺陷的。主要缺陷是：工人使用手套1分钟后，手套变得很硬无法再继续使用。但有一些复杂的作品需要一个多小时才能组装完成。
值得注意的是：手套箱中有一个单向插入插槽，如同邮局的邮箱一样。它们也很灵活，可以通过插槽将一个盒子放在另一个盒子里面。
为了解决手套箱的缺陷，Alice又想到了新的办法，Alice还是非常聪明的嘛。
Alice想到的解决办法是：Alice给工人一个手套箱，1号盒子（包含需要加工的原材料）。同时她还给了工人几个额外的手套箱，其中2号盒子包含1号盒子的钥匙，3号盒子包含2号盒子的钥匙等等。为了组装一个复杂的设计，工人加工1号盒子里的材料，直到手套变硬。然后，他将1号盒子放在2号盒子中，其中2号盒子中已经包含1号盒子锁的钥匙。使用2号盒子的手套，他用钥匙打开1号盒子，提取部分组装好的饰品，然后在2号盒子内继续装配，直到手套变硬。然后，他将2号盒子放在3号盒子内，依此类推。当工人们最后在n号盒子里面完成他的装配时，他把盒子交给Alice。
当然，Alice注意到，除非工作人员可以在(i + 1)号盒子内打开 i 号盒子，并且还有时间(i + 1)号盒子的手套变硬之前，可以对饰品进行加工，这就要求解锁操作（加上一点点组装工作）花费不到一分钟的时间。如此看来只要她有足够多的有缺陷的手套箱，就可以装配任何一件饰品，不管多么复杂！
这部分说的有些啰嗦和复杂，请耐心地多阅读几遍吧！