初探全同态加密之四：Bootstrapping的原理与实现lg...

作者：Steven Yue，原刊于作者知乎

在上一期的文章中，我们学习并且深入了解了GSW全同态加密系统的具体构造。通过这一构造，我们可以对加密的密文进行相加和相乘的操作，并且通过二进制分解的方法，把密文中噪声的增加速度控制在一个可控的区间之内。（详情点击《初探全同态加密之三：构建GSW全同态加密系统》）

GSW的有限级数限制

Alice的珠宝店

Alice开了一家珠宝店，每天她需要把不同的珠宝（钻石、黄金）加工拼接起来，然后把完成的首饰卖给顾客。

过了一阵子后，Alice觉得自己忙不过来，于是决定雇佣Bob作为她的员工。然而，Alice担心Bob会趁着她不注意，偷偷的把加工完剩余的边角料藏起来，或者是加工的时候偷工减料为自己牟利，所以一直放不下心来。

直到有一天，Alice突然想到了一个idea。

Alice买来了一个手套箱（Glove Box），就是那种做实验用的密封的箱子，中间有两个带有手套的洞，手可以伸进去碰到箱子里面。她的想法很简单：只需要把所有的原材料全部锁在箱子里，然后Alice保管着可以开锁的钥匙，Bob就偷不走了。Bob想要加工这些原材料也很简单，只需要把手伸进去隔着手套加工珠宝，就可以完成工作了。

这个手套箱还有一个巧妙的小设计，有一个单向的进口，外面的人可以投任何东西进来。Bob可以通过这个进口把部分的原材料从外面投入手套箱内，但是无法打开手套箱把它们取出来。

整个idea一切都很完美，正当Alice买回来了一个手套箱，准备进行实践的时候，她突然发现了这个箱子的几个问题：

1. 首先，套上手套的Bob的加工手艺并没有以前那么精湛了。也许原本只需要半天的活，现在可能要磨蹭两三天才能干完。

2. 其次，虽然手套箱上了锁之后，Alice就可以放心Bob不会偷走珠宝了。但是这样的代价就是，当Bob加工完了之后，他并没有办法直接把加工完的珠宝拿出来给顾客，而是得等Alice过来了才能打开来。这样一来如果Alice很忙的话，可能顾客得Alice忙完了才能拿到自己买的商品。

3. 以上的两点问题，Alice勉强都可以接受，但是接下来的第三点是最致命的。Alice发现，这个手套箱具有一定的使用寿命，也就是说Bob只能在这个箱子里加工珠宝L次，然后这个箱子就会坏掉，变得无法再继续加工。如果已经达到了损耗的临界值，然后Bob继续尝试使用的话，那么里面的珠宝就有可能会彻底的被搞坏，变得无法修复。

当Alice发现手套箱的这三个特点之后，她开始思考如何有效的让Bob使用这一新发明。

Alice的平行世界：FHE

看到这里，想必熟悉FHE构造的读者们一定会对Gentry举的这个Alice的珠宝店例子非常亲切。Alice发明的手套箱其实就是暗指FHE系统！我们来比较一下这两者之间的共同性：

1. Alice拥有手套箱的钥匙，所以可以打开盒中的东西。这代表了FHE加密系统的解密正确性。

2. Bob可以通过单向的入口把东西投入手套箱中，但是无法取出任何东西。这代表了我们讨论的FHE加密系统是一个安全的public key（公钥）的加密系统，即任意第三方都可以创造密文但不能解开密文。

3. Bob可以通过两个手套口，任意的加工放在手套箱中的物品，但是效率比起直接加工要慢上许多。这一步对应了FHE中的同态计算（Eval）。

4. 最后，手套箱的使用寿命，以及使用了若干次之后就会坏掉这一设定，完美的吻合了Lattice结构的FHE系统中的噪声以及上限。想要增加使用寿命，一种方法是把盒子做的更大、更昂贵，这对应着在FHE中把对应的parameters增大。

那么现在问题来了，Alice可以如何不改进手套箱，但是增加它的使用寿命呢？我们继续回到Alice的世界中来看看Gentry是怎么描述的。

手套箱中的奥秘

一筹莫展的Alice看着一个只能用有限次的手套箱，非常的失望。这一有限的加工次数决定了Bob可以加工的珠宝的复杂程度。按照现在这个样子，Bob只能加工一些半成品出来，然后需要Alice去开锁，再把半成品放到一个新的手套箱中，继续让Bob加工。

这样一来，Alice基本上得全程在旁边看着。原本雇Bob来是为了减少负担的，没想到现在反而还更加加重了工作压力。

直到有一天，Alice在看Bob加工珠宝的过程中，突然灵机一动：假如我事先知道了Bob加工一个珠宝需要两个手套箱，我能不能想办法可以让Bob在没有钥匙的情况下把未加工完的半成品从第一个手套箱中转移到第二个手套箱中呢？

Alice回去之后想了半天，终于想出了一个绝妙的想法：

第二天，Alice准备了两个手套箱，分别标号为A与B。Alice把A、B两个手套箱都交给Bob，并且自己留下手套箱B的钥匙。她唯独做了一件不一样的事情：把A的钥匙丢入了B当中。

这样一来，当Bob在手套箱A中加工珠宝达到损耗的临界值的时候，他接下来需要做的事情就是：把手套箱A一整个塞入手套箱B中！然后，Bob就可以直接在手套箱B中拿着实现放进去的钥匙解开里面的A箱的锁，然后把半成品的珠宝拿出来继续加工了。

整个想法瞬间震惊了所有珠宝店的人，通过这样的构造，Bob就可以不用Alice帮忙加工任意复杂度的珠宝了，两个不够就串三个，三个不够就四个。唯一需要做的就是Alice需要在开始之前把对应的钥匙丢入对应的箱子中。

为什么这样的方案可行呢？因为一开始说到了，手套箱上安装的单向入口可以放入任何东西，包括另一个手套箱，所以就可以层层嵌套啦。唯一需要注意的一点是，在手套箱B中解开箱A的锁这个步骤，也会给箱B带来一定的损耗。所以在选取锁的时候，Alice特意选择了不需要太大力气可以几步解开的锁。

Bootstrapping初见端倪

Alice所想到的这个技巧，正是我们这一期想要讨论的Bootstrapping的概念！如果拿到FHE的世界中简单的概括的话，那就是：把一个满噪音的FHE的密文加密进另一个FHE密文中，并且同态计算FHE的解密算法，把里层的密文解密还原为原文，就能获得一个全新的低噪音FHE密文。

如果乍一看有点一头雾水，不要急，我们一步一步的来看在FHE中Bootstrapping是如何实现的。

目前来说，我们还没能找到一个非常好的模型来研究Circular Security假设真正的安全性。这是因为在设计公钥加密算法的时候，我们并不会考虑到公开了密钥的密文之后会带来什么后果。有一派的看法是，因为公钥加密系统是Semantic Secure（语义安全的）的，所以密钥的密文应该看起来和其他的密文没有任何区别，所以循环安全这一假设应该很容易成立。

但是，我们近几年已经找到了很多反例，即找到了一些一定不满足Circular Security的加密系统。比如说我们手动的在某个加密系统中塞入一个后门，使得一旦拥有了循环密钥，即加密了密钥的密文之后，就可以通过这个后门来获得密钥的原文。但是这些加密系统都是人为的构造的，由于我们目前还没有在现有的公钥加密体系找到一个很自然的反例，所以我们相信Circular Security仍然是个安全的假设。

Bootstrapping的策略

看到这里，想必大家已经对Bootstrapping的概念有了一个大概的了解。

和之前介绍FHE系统不同的是，Bootstrapping其实是一个很广义、宽泛的概念。我们并没有用一系列公式来展示Bootstrapping的过程，而只是介绍了这一种思路，即同态验证解密函数。这种思路可以用于任何FHE的系统，包括BGV与GSW系统。

在深入理解Bootstrapping在GSW中到底是什么原理之前，我们先来看看，到底什么时候才需要Bootstrapping。

Bootstrapping的策略分为两种：Gate Bootstrapping与Circuit Bootstrapping。

Gate Bootstrapping

第一种Bootstrapping的策略，就是每当我们进行一次最简单的同态计算，我们就进行一轮的Bootstrapping把噪声值还原到进行计算前的量。因为我们可以把计算的函数用电路表示，而电路的最基本构成元素是逻辑门（Gate），所以这种方案又被称作Gate Bootstrapping。

熟悉逻辑电路的读者可能会知道，所有的逻辑门都可以用一个逻辑门NAND来表示。这也就是说，只要我们可以构造出一个同态计算NAND并且再进行一轮Bootstrapping的构造，我们就可以把这个构造作为一个逻辑计算模块，然后用这个模块构造出任何电路。因为Bootstrapping确保了噪声不会超过临界值，所以我们可以用这种方法来进行任何深度的电路的同态计算。

基于Gate来构造的Bootstrapping较为简单，我们在同态计算一个程序的时候，只需要写一个编译器，把这个程序转换成电路，再把电路分解为单个的逻辑门，然后把每个逻辑门再拆分成NAND，就搞定了。这样的结构等于是在应用层隐藏了Bootstrapping这件事情，因为每次进行NAND计算的时候，噪音值就已经被重新刷新了。

Circuit Bootstrapping

第二种Bootstrapping的思路和我们之前讨论的思路比较相似。我们首先使用原本的FHE系统同态计算我们想要计算的电路，直到达到了噪音临界值。然后我们再进行一轮Bootstrapping来“刷新”噪声值，以便进行后续的同态计算。

这种结构和Gate的思路相反，把Bootstrapping的概念直接暴露在了应用层。我们在进行计算的时候可以根据目前的噪声值来选择是否要进行Bootstrapping。这样的好处在于，如果我们需要同态验证的电路的复杂度不是很高的话，我们就可以很快速的进行Leveled同态计算，而不需要花额外的时间来通过Bootstrapping来刷新噪声。

Bootstrapping的实现

了解完Bootstrapping的原理与策略之后，接下来我们终于可以来结合之前所学的看一看，如何在我们之前看到的GSW同态体系中运用Bootstrapping的概念了。

我们先重新回顾一下GSW的加密与解密结构。

这个问题解决了之后，剩下来的就是把Dec转换成MBP然后进行同态计算了，这一部分我们就不多说了。

当BV二人根据这个结构提出Bootstrapping的方案之后，大家逐渐找到了一条可以真正实现Bootstrapping的路，并且开始用代码来实现。到2014年，Halevi与Shoup在HElib（IBM的FHE库）中使用类似的概念进行Bootstrapping计算，并且可以在半个小时左右的时间内进行一次Bootstrapping，使用的参数的存储空间达到了几十个GB左右。

实际的Bootstrapping方案（Practical Bootstrapping）

看到这里的朋友们可能会不禁吐槽到，Bootstrapping这么简单的概念，居然需要在电脑上花上半个小时的时间，并且占用这么大的空间才能完成。没错，早期的FHE之所以不能投入应用，就是因为Bootstrapping的开销实在是太大了。并且抛开Bootstrapping不说，我们光是用GSW这样庞大的LWE矩阵来加密一个bit，就基本上代表已经没有什么效率可言了。

然而，这一切在2014年后开始发生了改变。

2015年的时候，Ducas与Micciancio提出了全新的【DM15】构造，属于Gate Bootstrapping的方案（即提供了一个NAND+Bootstrapping的实现），并且基于GSW系统。这一构造被称作为FHEW，标准参数下只需要0.69秒就可以完成一轮Bootstrapping！

在DM15中，作者发现GSW的解密过程中最令人头疼的第二步，其实并不需要实现完整的Comparator Circuit，可以通过一个更加简单的Accumulator（累加器）来实现。这一发现直接就大大简化了第二步所需要的计算量。主要的思路在于，如果我们合理的选择模组q的值，那么第二步比较判断的过程，就完全可以通过观察密文二进制分解之后的最高位是1还是0来完成，而不需要与q/4来进行比较了。

紧接着，在2016年的【CGGI16】中，TFHE诞生了，继承了FHEW的特点，不过进行了一系列更加优化的操作，把Bootstrapping的时间压缩到了0.05秒之内。在2017年的follow up 【CGGI17】中，又把这一下限压到了0.013秒！

TFHE所用到的技巧也非常巧妙，它的核心也是观察到FHEW所用的Accumulator的构造，发现如果把密文映射到Torus 

T（环面空间）中，那么构成这个Accumulator的构造更加简单。因为整个计算空间是一个环形的，只需要通过一个盲旋转（blind rotation）的操作，就可以提取出密文的最高位的值。

至于FHEW与TFHE的具体实现与证明，我们在这里就不多说了，以后有时间的话可以再开一篇，详细讨论一下这两种方案。

FHE库的比较

到这里，我们大概已经知道了FHE的大致发展了。从09年Gentry提出了这一概念之后，学术界和业界都在争相在计算机上实现FHE。除了我们这期提到的FHEW与TFHE之外，还有HElib，SEAL，cuFHE等等非常有名的开源库。

这些库之间并没有特别多的好坏比较，更多的只是他们适应于不同的使用需求。比如说有的库会使用很多浮点操作，有的库会使用CUDA加速，有的库会使用GPL License下的其他插件（比如FFTW），所以不能用来闭源开发等等。由于时间关系，笔者就没有一一去测试了，把这个机会留给大家去尝试一下。

写在最后

到这里，我们【初探全同态加密】这一专题就到此结束啦。我们来快速回顾一下这4期覆盖的内容：

1. 什么是加密系统，与什么是加密系统的同态性质。

2. 同态加密的分类与特性。

3. 全同态加密的定义的历史。

4. 格密码学入门以及LWE问题的介绍。

5. 基于LWE问题的Regev加密系统。

6. GSW全同态加密体系的三次尝试：矩阵特征值，加入噪音，二进制分解。

7. Bootstrapping是什么，以及具体实现策略。

8. 如何基于GSW进行Bootstrapping，以及现有的实现方案。

9. FHE库的大致一览。

这么一看，这四期已经涵盖了非常多的内容了！如果看到这里大家觉得对之前的概念有点生疏的话，不妨回去再看一遍，巩固一下知识。

距离上一篇FHE文章已经过去了很久，这段时间笔者都在努力的补更多关于格密码学的知识，在过程中重新学习一遍这些讲过的概念。每次重新学这些概念的时候，都会发现每次的理解都会变得不一样，也会发现很多见过的构造其实都有非常巧妙的相似之处。

如果看完了FHE之后，还想了解一下基于格密码学的更多高级的构造，比如ABE，NIZK，iO等等，希望大家也可以关注一波笔者在更新的【格密码学进阶】专题～

来源：金色财经