最近，我一直在阅读有关FHE的文章，看来引导是开发FHE方案的核心概念。但是，我不完全了解其背后的想法。我知道基于Gentry设计的方案是基于噪声的，并且噪声随同态操作的增加而增加，如果噪声超过特定阈值，则解密将失败。我猜想引导程序是为解决此问题而开发的。但是究竟是什么引导程序？

我遇到了以下定义，但我不明白它想说什么。


定义：$ \ mathcal如果{C} $评估方案能够同态地评估其自己的解密电路以及一个附加的$ \ mathsf {NAND} $门，则称其为Bootstrappable。

知道$ \ mathcal {C} $评估方案是什么，但是“同态评估其自己的解密电路”到底意味着什么，以及为什么“加一个$ \ mathsf {NAND} $门”呢？

#1 楼

首先，从您的问题出发，不清楚您是否理解“电路”部分。所以我将从这里开始。使用（大多数）FHE方案，您正在评估电路，或者将一堆门钩在一起。通常，我们根据和/或非门来考虑电路。但是事实证明，您可以从其他类型的门构建电路。 NAND本身在功能上是完整的。因此，仅需一个NAND门，便可以构建任何电路。这就是为什么我们需要一种可以计算至少一个“与非”门的方案（除了其自己的解密电路之外）。

正如您所说，FHE方案会给密文增加噪声。因此，您可以评估输入密文上的电路，但是这样做可能会增加太多噪音，无法再解密。这就是我们面临的问题。重要的是要记住，电路的输入是密文，电路的输出是密文。

金特里给我们提供了某种同态加密方案。在评估过多的门之后，噪声变得太多，我们将无法再解密。但是，他展示出，通过将解密算法用于他的方案，并将其转换为电路，并向该电路传递密文和私钥的加密版本，您将得到的是相同明文的密文，但是噪音消失了。此外，该密码使您可以在两个密文上运行至少一个“与非”门（两个等效于“与非”的门）和解密电路，而不会产生太大的噪声。说我们可以同态执行一个“与非”门和解密电路，并且在噪声方面仍然可以。给定类似(A NAND B) NAND (C NAND (D NAND A))的电路，我们实际上将其执行为（例如，DEC是使用私钥加密版本的解密电路）：

DEC(
  DEC(
    A NAND B
  ) 
  NAND 
  DEC(
    C NAND 
    DEC(D NAND A)
  )
)


因此，在每个NAND之后，您都需要插入一个DEC以消除噪音。我应该注意，即使您最后评估的是DEC，输出的值也是加密的。