本文作者东泽，来自安比技术社区的小伙伴，目前就读于斯坦福大学，研究方向密码学。

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

Bootstrapping是FHE界的开山鼻祖Craig Gentry在2009年提出的一个idea。Gentry本人其实写过一篇非常方便理解这个idea的介绍性paper：Computing Arbitrary Functions of Encrypted Data。我们这里就基于Gentry在原文中的表述方法来尝试深入了解一下。

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只能在这个箱子里加工珠宝次，然后这个箱子就会坏掉，变得无法再继续加工。如果已经达到了损耗的临界值，然后Bob继续尝试使用的话，那么里面的珠宝就有可能会彻底的被搞坏，变得无法修复。

看到这里，想必熟悉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特意选择了不需要太大力气可以几步解开的锁。

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

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

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

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

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

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

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

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

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

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

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

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

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

1. 线性乘积。这一部分非常简单，因为我们已经知道了的值（是公开的），并且我们拥有了，所以我们需要做的就是基于的第一行的值（我们只需要看解密之后的第一项），构造一个的线性函数。这个函数把中的每一项都乘以系数，然后再相加起来。最后，我们在密文上面同态计算。

2. 当我们获得了这个线性乘积的结果之后，下一步就是判断这个结果是否接近数字0。这其实是整个解密过程中最困难的一步，因为我们不能用简单的加法或者乘法来把一个中的数字变成的一个bit。这个时候，我们就需要用到一些比较复杂的逻辑，比如说我们需要判断中的值是否大于某个临界值。然后我们需要通过加法和乘法来构造出一个比较电路（Comparator Circuit）。最后，我们同态的在上计算这个Comparator Circuit就能获得最后的结果——一个加密了0或者1的密文。

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

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

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

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

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

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

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

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

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

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

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

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

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

9. FHE库的大致一览。

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

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

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