TFHE：环面上全同态加密方案
主要参考论文：
Chillotti I, Gama N, Georgieva M, et al. Faster fully homomorphic encryption: Bootstrapping in less than 0.1 seconds[C]//international conference on the theory and application of cryptology and information security. Springer, Berlin, Heidelberg, 2016: 3-33. Chillotti I, Gama N, Georgieva M, et al. Faster packed homomorphic operations and efficient circuit bootstrapping for TFHE[C]//International Conference on the Theory and Application of Cryptology and Information Security. Springer, Cham, 2017: 377-408.
全同态与TFHE
全同态算法在2013年左右大致分为两个大类，一类为 BGV方案，另一类为 GSW方案，而TFHE属于类GSW分支，并且是FHEW方案的一个改进，TFHE方案是目前最快的全同态加密方案。
全同态加密中的噪声
众所周知，全同态加密是有噪声(error)的。假设有一布尔电路如下图：
在明文状态下评估该布尔电路，没有任何问题：
然而，要在全同态加密的密文状态下评估该布尔电路，不但评估时间变得十分漫长，噪声也随着经过的门电路的数量增加而增长，如果经过过多的门电路，则很可能导致最终的解密错误(解密后无法分辨0和1)。 
想要解决同态加密中的噪声问题，目前有如下两种途径：
-
LHE 层级全同态 通过设置LHE中的安全参数，使之足够大从而支持一定深度(depth)的布尔电路的评估。 想象上图中最左端的密文全都有3个level，密文每通过一个 与/或门 就会消耗一个level(取非操作相比于 与/或门 产生可忽略的噪声)，如果最终的level小于0则密文不能够正确解密，如下图所示：
-
Bootstrapping 自举 2009年Gentry提出了自举的设想。整个自举过程如下：
LHE 和 Bootstrapping 两种方案各有优缺点：
TFHE在 LHE 方案和 Bootstrapping 方案中都实现了一定的改进
TFHE
Torus 环面
TFHE全称为：Fully Homomorphic Encryption over the Torus。FHE代表全同态加密，而T代表环面(Torus)。因此，想了解TFHE，在了解什么是FHE后，还要了解什么是环面。 环面大概长下面这张图的样子，像一个甜甜圈(by Ilaria Chillotti)： 
实数环面有三条性质：
1.它是一个阿贝尔群(环面上的加法是有定义的)。 2.它拥有 Z-module 结构。 3.它不是一个环(环面上的元素之间的乘法没有定义)。
TFHE 是 FHEW 的改进，主要的优化思路是：使用 LWE 与 GSW 的”外积”，取代 GSW 与 GSW 的“内积”，从而使得计算复杂度降低了一个多项式因子。
TLWE密文的对称加密
TFHE的三种密文形式
除TLWE密文外，TFHE方案中还有两种密文：TRLWE密文与TGSW密文。将TLWE拓展到多项式环面，可得TRLWE密文，将GSW方案拓展至环面，可得TGSW密文。接下来给出TFHE三种密文格式的定义：
下面给出三种密文的明文、密文和密钥的形式，以及可以进行的运算：
TFHE的外积加速
我们发现TLWE密文和TRLWE密文只能进行线性组合，不能进行Product(积)的操作，即只能做加法不能做乘法。TFHE的研究者在定义了TLWE密文和TRLWE密文后，觉得好像离全同态加密还差一点，于是他们从GSW方案中找到了灵感。GSW方案中有一个ring product(内积)的操作： 
输入是两个TGSW samples，Z[X]是整数多项式，输出是一个TGSW sample，解密后得到两个消息的乘积，这里观察到，尽管运算是对称的，但是它产生的噪声是不对称的。TFHE的研究者基于这个特性研究出了TFHE：把其中一个输入换成TLWE类型，然后输出也变成了TLWE类型，计算变成了点乘(外积)。 
噪声本来就不对称，现在更不对称了(更小了)。然后便可以用分解的方法，把原来TGSW的每行拆开，在并行计算，将原来的叉乘(内积)都变成了点乘(外积)，得到一个很大的提速。
下面给出内积和外积的具体表达式以及直观的感受：
层次TFHE(TFHE IN LEVELED MODE)
这一部分使用层次TFHE实现一个确定型自动机的评估。使用上面所说的同态外积构造门：
设TGSW密文的消息空间为 { 0 , 1 } ∈ Z [ X ]，TLWE密文的消息空间为{ 0 , 1 / 2 } ∈ T [ X ] ，这样噪声中的∣ ∣ μ A ∣ ∣ 1 就没有了(为1)。 接下来为TFHE选择门电路，这里给出四种图灵完备的门电路组合：
1.Or, And, Not DNF logic 2.Xor, And, 1 Multivariate polynomials 3.Nand minimal indeed 4.Mux, 0, 1 Because we get binary decision diagrams for free 在LHE里面通常选择Xor这一组，FHEW选择了与非门，而(level)TFHE选择的是Mux电路，因为它可以几乎没有消耗的做二进制选择(噪声呈线性增长)。 Mux门电路的选择逻辑很简单，如果c为0则输出b，如果c为1则输出a： C M u x ( c , a , b ) = b + c ⊡ ( a − b ) CMux(c,a,b)=b+c⊡(a−b) 
在(level)TFHE的Mux门电路中有不同的线：图中深红色的线成为控制线(Control line)，传输TGSW密文，蓝色的先称为数据线(data line)，传输TLWE密文。 随后，我们便可以使用Mux门电路构造和评估任意的 查找表/布尔函数(噪声随电路深度的增加线性增长)： 
进而可以评估(输入长度已知并固定的)任意确定型(有穷)自动机：
全同态TFHE(TFHE IN FHE MODE)
为实现任意深度电路的同态评估，需要为TFHE引入自举(bootstrapping)操作。 自Gentry于2009年提出自举以来，自举从同态解密(Gentry09)，到重加密，到压缩解密函数，再到密钥交换&模交换(FHEW&TFHE使用)。在Gentry09的自举(前面有写)中，自举是一个单独的函数，仅用于减小噪声；而在TFHE中，自举可以改变消息内容。接下来介绍TFHE中的自举门(gate bootstrapping)。
我们现在有一个二进制的消息空间，消息只有false和true。设false是− 1 / 8 ( − 1 / 8 = 7 / 8 ) ，噪声小于1 / 16，设true是1/8，噪声也小于1 / 16 
然后我们把两个环面相加。它们的值可能是真或假。如果他们都是假，那会得到3 / 4(红色)，如果他们一真一假，会得0(黄色)，如果他们都是真，得到1 / 4(绿色)。： 
在能够看到明文的条件下，如何进行自举的与非操作呢？非常简单，我们把这个环面画一条线，落在线的左边就输出true，落在右边就输出false：
难点在于我们如何在密文下进行操作。TFHE给出了这样的答案：
盲旋转
1.首先将环面分为 2 N个部分，想象成图中的轮子，上面带有 2 N个槽。 2.然后将要返回的 2 N个值放入槽中，完成设置 (Setup) 步骤。 3.进行明文旋转 (PlainRotate) 过程，该过程进行旋转的人可以知道具体旋转了多少个位置。 4.进行密文旋转 (EncRotate) 过程，该过程进行旋转的人不知道旋转了多少个位置，并且得到的是加5.密的密文，无法通过旋转前后判断旋转了多少位置。可以理解为放在一个黑盒中进行了一波操作。 6.最终将 0 位置的密文取出，即为所需要的结果。
