【英文长推】如何通过「bootstrapping」解决 FHE 方案的噪声增长问题

2009 年，Craig Gentry 在其博士论文中提出了一种名为「bootstrapping」的新方法，无需解密即可刷新密码文本。 首先，假设我们有一个加密方案 E，其明文空间 P = {0，1}（因此我们只加密 bits）和一个在 pk_1 下加密 \pi 的密文 Ψ_1。我们没有私钥 sk_1，因此无法解密 Ψ_1。但我们可以提供用户的另一个公钥，例如 pk_2，对 Ψ_1 和私钥 sk_1 的 bits 进行加密。现在，我们就有了新的密码文本（用带下划线的 Ψ_1 表示）和加密后的私钥版本（用带下划线的 sk_1 表示）。 由于采用了同态加密技术，我们可以使用加密的私钥对解密电路进行同态评估，将其转换成新的密文。通过这种评估，我们就能得到噪声更小的新密文。由于假设解密电路的噪声较小，因此最新密文的噪声一定比原始密文的噪声小。这一革命性的概念虽然最初在日常使用中效率不高，但却为 TFHE 等新方案的开发提供了指导。【原文为英文】