1. 项目概述：为什么我们需要在密文上做计算？

想象一下，你有一份极其敏感的医疗数据，比如基因序列，需要交给一个强大的云端服务器进行分析。你既希望利用服务器的算力，又绝对不想让服务器看到你的原始数据。怎么办？全同态加密（Fully Homomorphic Encryption, FHE）就是为这种场景而生的“魔法”。它允许你在加密状态下（也就是密文）直接进行计算，服务器处理完加密数据后，把加密的结果返回给你，你用自己的密钥解密，就能得到明文计算的结果。整个过程，你的原始数据对服务器而言，始终是一团无法理解的乱码。

FHEW库，是近年来在效率和实用性上取得显著突破的一个FHE实现方案。它的名字来源于几位核心贡献者（Ducas, Micciancio, Peikert, Regev）姓氏的首字母，也代表了其设计目标：Fast Homomorphic Encryption over the Torus（基于环面的快速全同态加密）。与早期如Gentry蓝图式的复杂方案相比，FHEW更注重在特定类型计算（特别是布尔电路和算术运算）上的高效实现。对于开发者而言，掌握FHEW的核心操作——加法、连加和乘法，就等于拿到了在密文世界中进行基础数据处理的钥匙。这不仅仅是学术上的好奇，更是构建隐私计算应用，如加密数据库查询、隐私保护机器学习推理等，必须跨越的实践门槛。

2. FHEW核心概念与快速上手

在深入代码之前，我们需要理解FHEW赖以生存的几个关键数学概念和它独特的“计算单元”。如果你对“环面”、“LWE”感到陌生，别担心，我们可以用更工程化的视角来理解。

2.1 理解FHEW的“计算单元”：累加器与自举

FHEW最巧妙的设计之一是它将复杂的同态运算，分解为两个核心步骤，并通过一个叫做“累加器”的组件来高效完成。你可以把累加器想象成一个特殊的、能在密文状态下工作的“寄存器”。

1. 初始计算（同态累加）：首先，FHEW使用基于LWE问题的加密方案进行基础的加法操作。LWE密文就像给明文数据加上了厚厚的、由随机噪声构成的“外壳”。每次同态加法，都会让这个噪声“外壳”变厚一点。如果只做加法，噪声增长是线性的，还算可控。
2. 噪声管理（自举程序）：然而，同态乘法（或更复杂的门电路）会导致噪声呈指数级增长，很快就能让密文无法正确解密。FHEW的杀手锏是“自举”。自举是一个神奇的过程：它以一个噪声很大的密文作为输入，内部对其进行一次完整的解密操作（当然是在加密状态下进行的），然后输出一个全新的、噪声很小的、加密着相同信息的密文。这个过程就像是给密文“刷新”了一次，重置了噪声水平。FHEW的自举效率很高，使其能够支持任意深度的计算。

在FHEW中，连加操作是展示其威力的一个典型场景。它不仅仅是多个加法的简单循环，而是通过精心设计的算法，将多次加法与自举操作交织在一起，在控制噪声的同时完成计算。而乘法，在布尔电路下通常通过AND门实现，FHEW提供了高效的同态NAND门操作，结合自举，就能构建出完整的算术乘法逻辑。

2.2 环境搭建与第一个密文

理论说了不少，我们直接动手。FHEW的官方实现是C++库，我们首先从编译和安装开始。

# 1. 克隆仓库 git clone https://github.com/lducas/FHEW.git cd FHEW # 2. 编译库。FHEW使用Makefile，通常直接make即可。 # 如果你的系统支持，可以开启多线程编译加速 make -j$(nproc) # 3. 编译后，静态库文件 `libfhew.a` 会生成在 `lib` 目录下， # 头文件在 `include` 目录下。 # 你可以运行自带的测试程序验证编译是否成功 ./bin/fhew-test

如果看到测试通过的提示，环境就准备好了。现在，我们写一个最简单的程序：生成密钥，加密一个比特（0或1），然后解密它。虽然简单，但这是所有复杂操作的起点。

// demo_encrypt_decrypt.cpp #include “fhew.h“ // 主要头文件 #include <iostream> int main() { // 1. 初始化参数。FHEW::Setup() 会设置全局参数，如多项式维度、模数等。 // 这些参数直接关系到安全强度和性能，一般使用库推荐的默认值。 FHEW::Setup(); // 2. 生成密钥对。包括一个私钥(SK)和一个用于自举的“计算密钥”(BK)。 LWE::SecretKey sk; LWE::BootstrappingKey bk; LWE::KeyGen(sk); // 生成私钥 LWE::BKGen(bk, sk); // 用私钥生成自举密钥 // 3. 加密一个比特。假设我们要加密明文 bit = 1。 int plain_bit = 1; LWE::CipherText ct; LWE::Encrypt(&ct, sk, plain_bit); std::cout << “明文比特: “ << plain_bit << std::endl; // 4. 解密这个密文。 int decrypted_bit = LWE::Decrypt(sk, ct); std::cout << “解密得到的比特: “ << decrypted_bit << std::endl; // 5. 清理全局参数 FHEW::Cleanup(); return 0; }

使用如下命令编译并运行：

g++ -std=c++11 -I./include demo_encrypt_decrypt.cpp ./lib/libfhew.a -o demo -lntl -lgmp -lm ./demo

你应该能看到输出“明文比特: 1”和“解密得到的比特: 1”。恭喜，你已经完成了在FHE世界里的“Hello World”。

注意：在实际应用中，BootstrappingKey体积非常大，是主要的通信和存储开销。服务端（计算方）持有BK即可进行同态计算，而私钥SK必须由数据所有者（客户端）严格保密。

3. 同态加法与连加的实现与解析

有了加密和解密的基础，我们开始探索密文上的计算。同态加法是其中最直观的操作。

3.1 基础同态加法的实现

FHEW支持两种类型的加法：明文与密文相加，以及密文与密文相加。我们先看一个例子，计算Enc(1) + Enc(1)，理论上结果应该是Enc(0)（因为在比特域，1+1=0，进位被忽略，这是布尔电路的特点）。

// demo_hom_add.cpp #include “fhew.h“ #include <iostream> int main() { FHEW::Setup(); LWE::SecretKey sk; LWE::BootstrappingKey bk; LWE::KeyGen(sk); LWE::BKGen(bk, sk); // 加密两个比特 1 LWE::CipherText ct1, ct2; LWE::Encrypt(&ct1, sk, 1); LWE::Encrypt(&ct2, sk, 1); // 进行同态加法 LWE::CipherText ct_sum; LWE::Add(&ct_sum, ct1, ct2); // 密文 + 密文 // 解密结果 int result = LWE::Decrypt(sk, ct_sum); std::cout << “Enc(1) + Enc(1) 的解密结果: “ << result << std::endl; // 预期输出 0 (因为 1+1=0 mod 2) FHEW::Cleanup(); return 0; }

LWE::Add函数在底层做了什么呢？它实际上是对两个LWE密文的向量进行逐系数的模加运算。从噪声角度看，两个密文相加，其内部的噪声也近似相加了。虽然噪声增长了，但仍在可解密的范围内，并且增长是线性的。

3.2 连加操作与噪声控制

如果我们连续做很多次加法呢？比如想计算一个加密计数器。简单的循环调用LWE::Add会导致噪声线性累积，最终超出上限。这时就需要引入“连加”算法，并适时使用自举来刷新噪声。

FHEW库提供了一个高效的连加函数LWE::FHEWAddMany。它并不是简单循环，而是利用了一种称为“电路自举”的优化技术，在计算加法链的过程中更有效地管理噪声。下面我们实现一个加密计数器，从0开始，连续加1多次。

// demo_continuous_add.cpp #include “fhew.h“ #include <iostream> #include <vector> int main() { FHEW::Setup(); const int n_adds = 10; // 连续加的次数 LWE::SecretKey sk; LWE::BootstrappingKey bk; LWE::KeyGen(sk); LWE::BKGen(bk, sk); // 初始加密一个0 LWE::CipherText ct_counter; LWE::Encrypt(&ct_counter, sk, 0); std::cout << “初始值 (0) 加密完成。“ << std::endl; // 创建一个明文‘1’的密文，作为增量 LWE::CipherText ct_one; LWE::Encrypt(&ct_one, sk, 1); // 方法1：朴素循环加法（不推荐用于大量操作，仅作对比） LWE::CipherText ct_naive = ct_counter; for (int i = 0; i < n_adds; ++i) { LWE::Add(&ct_naive, ct_naive, ct_one); } int naive_result = LWE::Decrypt(sk, ct_naive); std::cout << “朴素循环加法 “ << n_adds << “ 次后的结果: “ << naive_result << “ (应为 “ << n_adds % 2 << “)“ << std::endl; // 方法2：使用FHEW的优化连加API（内部可能整合了自举） // 注意：标准FHEW API可能不直接提供显式的多参数连加，通常需要结合自举门进行构建。 // 更常见的模式是：使用同态NAND门构建全加器，然后循环执行，并在每层或每隔几层后自举。 // 以下展示一种概念性的流程： LWE::CipherText ct_optimized = ct_counter; for (int i = 0; i < n_adds; ++i) { // 进行一次加法 LWE::Add(&ct_optimized, ct_optimized, ct_one); // 关键步骤：定期或每次加法后执行自举以控制噪声 // FHEW::Bootstrap 函数需要自举密钥 bk 和待刷新的密文 LWE::CipherText ct_bootstrapped; // 假设有一个 Bootstrap 函数（实际API名称可能不同，如 HomNAND in test程序） // FHEW::Bootstrap(&ct_bootstrapped, bk, ct_optimized, 某个函数); // ct_optimized = ct_bootstrapped; } // 由于标准API的调用方式较为复杂，此处示意逻辑。 // 实际开发中应参考 `src/test_fhew.cpp` 中的 HomNAND等示例。 std::cout << “提示：对于可靠的连加，请参考库中基于自举门的电路构建示例。“ << std::endl; FHEW::Cleanup(); return 0; }

实操心得：直接使用LWE::Add进行连加在实际项目中非常罕见，因为噪声会迅速累积。真正的FHE应用几乎总是将加法与自举门（如NAND）绑定在一起。FHEW示例中的HomNAND函数，内部就完成了“计算NAND”和“自举刷新”两个动作。因此，实现加法器通常是先用NAND门搭建出基本的逻辑电路（如半加器、全加器），然后让这个电路在自举的保护下运行。

4. 同态乘法的实现与电路构建

同态乘法是FHE能力的关键体现。在布尔电路下，乘法对应于AND（与）操作。由于FHEW提供了高效的同态NAND（与非）门，而NAND是逻辑完备的，我们可以用NAND来构建AND，进而构建乘法器。

4.1 从同态NAND到乘法

FHEW库的核心同态操作函数通常是HomNAND（或类似名称）。它接受两个加密的比特输入，输出它们NAND结果的密文，并且输出密文的噪声是“新鲜的”，即经过自举重置到了低水平。

// 伪代码，展示 HomNAND 的典型调用方式 LWE::CipherText ct_a, ct_b; // 输入密文，加密了比特a和b LWE::CipherText ct_nand_result; FHEW::HomNAND(&ct_nand_result, bk, ct_a, ct_b); // 使用自举密钥bk进行计算 // 现在 ct_nand_result 加密了 (a NAND b)，且噪声很低

有了NAND，我们可以实现所有其他逻辑门：

• NOT(a) = NAND(a, a)
• AND(a, b) = NOT(NAND(a, b))
• OR(a, b) = NAND(NOT(a), NOT(b))
• XOR(a, b) = ...（可以用多个NAND组合）

4.2 构建一位全加器

多位乘法的基础是一位全加器。一个全加器输入三个比特（加数A、加数B、进位Cin），输出两个比特（和S、进位Cout）。其真值表可以用逻辑门实现。这里我们给出其基于NAND门的实现逻辑，并假设我们有函数HomAND,HomXOR（它们内部由HomNAND构建）。

// 假设我们已经有了基于HomNAND实现的HomAND和HomXOR函数 void HomAND(LWE::CipherText* result, const LWE::BootstrappingKey& bk, const LWE::CipherText& ct_a, const LWE::CipherText& ct_b); void HomXOR(LWE::CipherText* result, const LWE::BootstrappingKey& bk, const LWE::CipherText& ct_a, const LWE::CipherText& ct_b); // 同态一位全加器 void HomFullAdder(LWE::CipherText* ct_sum, LWE::CipherText* ct_carry_out, const LWE::BootstrappingKey& bk, const LWE::CipherText& ct_a, const LWE::CipherText& ct_b, const LWE::CipherText& ct_carry_in) { LWE::CipherText xor_ab, and_ab, xor_abc, and_xor_cin; // 计算 a XOR b HomXOR(&xor_ab, bk, ct_a, ct_b); // 计算 a AND b HomAND(&and_ab, bk, ct_a, ct_b); // 计算 sum = (a XOR b) XOR carry_in HomXOR(ct_sum, bk, xor_ab, ct_carry_in); // 计算 carry_out = (a AND b) OR ((a XOR b) AND carry_in) // 先计算 (a XOR b) AND carry_in HomAND(&and_xor_cin, bk, xor_ab, ct_carry_in); // 再计算 carry_out = and_ab OR and_xor_cin // OR 可以通过 AND 和 NOT 实现，这里我们同样需要一个基于NAND的HomOR HomOR(ct_carry_out, bk, and_ab, and_xor_cin); // 假设HomOR已实现 }

注意事项：上面的代码是概念性的。每一次HomAND、HomXOR的调用，底层都可能包含至少一次HomNAND调用，也就意味着至少一次自举操作。构建一个全加器需要多次自举，开销很大。这直观地说明了为什么FHE计算比明文计算慢数个数量级。

4.3 串联成全字长乘法器

有了全加器，我们就可以像在数字电路设计中一样，构建一个阵列乘法器或华莱士树乘法器。例如，一个简单的4位x4位无符号乘法器，需要16个与门（生成部分积）和多个全加器进行累加。

实现步骤概览：

1. 生成部分积：对于乘数A的每一位Ai和被乘数B的每一位Bj，计算Ai AND Bj。这需要16次同态AND操作。
2. 累加部分积：将部分积按照权重错位排列，然后用全加器阵列进行加法树求和。这个过程需要大量的同态全加器操作。
3. 最终输出：加法树的结果就是加密的乘积。

核心挑战：

• 深度与自举：乘法器电路深度较大，必须精心安排自举的时机。FHEW的自举门特性使得我们可以在每一层逻辑门之后都获得“干净”的密文，因此理论上可以支持任意深度的电路，但代价是巨大的计算量。
• 性能：一次32位乘法所需的同态门操作次数是万甚至十万级别的，对应的自举操作也是同等数量级。这是当前FHE应用的主要瓶颈。

// 极度简化的概念性代码，展示流程 void HomMultiplier(std::vector<LWE::CipherText>& ct_result, // 结果向量（低位在前） const std::vector<LWE::CipherText>& ct_a, // 输入A（位向量） const std::vector<LWE::CipherText>& ct_b, // 输入B（位向量） const LWE::BootstrappingKey& bk) { int n = ct_a.size(); // 假设位宽为n std::vector<std::vector<LWE::CipherText>> partial_products(n, std::vector<LWE::CipherText>(2*n)); // 1. 生成部分积 for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { HomAND(&partial_products[i][i+j], bk, ct_a[i], ct_b[j]); } } // 2. 初始化累加器（一个2n位的寄存器，加密值为0） std::vector<LWE::CipherText> accumulator(2*n); for (auto& bit : accumulator) LWE::Encrypt(&bit, sk, 0); // 需要私钥sk，这里是个问题！ // 3. 加法树累加 (这里需要sk来生成加密0，实际中需用其他方法获得) // ... 这是一个非常复杂的循环，涉及多层全加器调用 ... // 每调用一次HomFullAdder，都意味着数次HomNAND调用。 // 4. 最终结果存入ct_result ct_result = accumulator; }

关键技巧：上面的概念代码暴露了一个关键问题：在不知道私钥sk的情况下，服务端如何获得一个加密的“0”？这是同态计算中的一个常见需求。解决方案是“公钥加密”。客户端可以在生成密钥时，也生成一个公钥pk，并用pk加密0发送给服务端。服务端持有这个Enc(0)，就可以用它来初始化变量或进行其他操作。FHEW库也支持公钥加密。

5. 实战：一个加密的投票计数器案例

为了将加法、连加和乘法串联起来，我们设计一个简单的场景：加密投票统计。假设有3个候选人（A， B， C），每个投票是一组加密的比特，表示选择（例如，[1,0,0]表示投给A）。服务器需要统计每个候选人的总票数，但全程看不到任何一张票的内容。

系统设计：

1. 客户端：生成密钥对(sk, pk)。将公钥pk和自举密钥bk发给计票服务器。对每一张选票，用pk加密成一个比特向量[Enc(voteA), Enc(voteB), Enc(voteC)]，发送给服务器。
2. 服务器：初始化三个加密计数器ct_count_A,ct_count_B,ct_count_C，初始值均为Enc(0)。
3. 每收到一张加密选票[ct_a, ct_b, ct_c]，服务器就执行：
   • ct_count_A = HomAdd(ct_count_A, ct_a)（需要实现一个安全的、带噪声管理的加法）
   • 对B和C同理。
   • 由于票数可能很多，必须在适当的时机（如每累加一定票数后）对计数器执行自举，防止噪声溢出。
4. 结果公布：服务器将最终的加密计数器[ct_count_A, ct_count_B, ct_count_C]发回给一个可信的审计方或客户端。
5. 解密：持有私钥sk的一方解密这三个计数器，得到明文票数。

服务器端核心累加逻辑（概念增强版）：这里我们不能用简单的LWE::Add，因为它不管理噪声。我们需要一个“安全的同态累加”函数，它内部可能每做一次加法就自举一次，或者采用更高效的批量自举策略。

// 一个更健壮的同态累加函数示例（伪代码/概念） void HomSafeAdd(LWE::CipherText* ct_acc, const LWE::CipherText& ct_increment, const LWE::BootstrappingKey& bk) { // 步骤1：执行同态加法 ct_acc = ct_acc + ct_increment LWE::CipherText ct_raw_sum; LWE::Add(&ct_raw_sum, *ct_acc, ct_increment); // 步骤2：对加法结果立即进行自举，刷新噪声。 // 假设 FHEW::Bootstrap 函数存在，它接受一个“函数”参数。 // 对于简单的累加（恒等函数），我们可以使用一个特殊的自举函数。 LWE::CipherText ct_bootstrapped; FHEW::Bootstrap(&ct_bootstrapped, bk, ct_raw_sum, FHEW::ID); // ID 表示恒等函数 // 步骤3：更新累加器 *ct_acc = ct_bootstrapped; } // 在投票计数循环中 for (每张票) { HomSafeAdd(&ct_count_A, current_vote_ct_a, bk); HomSafeAdd(&ct_count_B, current_vote_ct_b, bk); HomSafeAdd(&ct_count_C, current_vote_ct_c, bk); }

这个案例清晰地展示了连加操作在实际中的应用模式：“加法 -> 自举”的循环。乘法操作在这个场景中可能用于更复杂的计票规则，例如加权投票（每票乘以一个加密的权重系数）。

6. 性能调优、常见问题与排查

使用FHEW进行开发，99%的挑战来自于性能和正确性调试。

6.1 参数选择与性能影响

FHEW的初始化Setup()函数通常使用一组默认参数。但在研究或特定应用中，你可能需要调整它们。关键参数通常在params.h或fhew.h中定义：

• n：LWE问题的维度（如n=500）。增大n会提高安全性，但显著降低计算速度和增大密钥尺寸。
• N：环的维度（用于自举中的FFT，通常是2的幂，如N=1024）。增大N能容纳更复杂的自举函数，但也会增加计算开销。
• lwe::Q：密文系数的模数。它与噪声增长和计算精度直接相关。

实操建议：除非你非常了解FHE的理论，否则建议先从默认参数开始。如果遇到解密错误（噪声溢出），首先检查你的电路深度是否超出了当前参数支持的范围。可能需要使用更保守（更大）的参数，或者更频繁地插入自举操作。

6.2 常见编译与运行问题

1. 链接错误：找不到 -lntl 或 -lgmp

   • 原因：FHEW依赖NTL（Number Theory Library）和GMP（GNU Multiple Precision Arithmetic Library）这两个数学库。
   • 解决：在Linux上，使用包管理器安装。例如 Ubuntu/Debian：sudo apt-get install libntl-dev libgmp-dev。在macOS上，使用Homebrew：brew install ntl gmp。

2. 运行时错误：illegal instruction或segmentation fault

   • 原因：FHEW为了极致性能，默认编译可能使用了较新的CPU指令集（如AVX2）。如果你的CPU较老，可能不支持。
   • 解决：在Makefile中，找到CXXFLAGS，移除或替换-march=native选项。例如改为-march=x86-64 -msse2以兼容更老的CPU。然后重新make clean和make。

3. 解密结果不正确

   • 排查步骤：
     • 第一步：检查最基本的加密-解密流程。单独加密0和1，然后解密，看是否正确。
     • 第二步：如果基础加解密正确，但同态计算后出错，很可能是噪声溢出。这意味着你的计算电路太深，或者没有正确使用自举。
     • 第三步：确认你在进行连续操作（尤其是乘法或复杂电路）时，是否在适当位置调用了自举门（如HomNAND）。简单的LWE::Add不能无限使用。
     • 第四步：使用库自带的测试程序./bin/fhew-test，看所有单元测试是否通过。这可以验证库本身和你的参数是否正常。

6.3 调试技巧：如何“窥视”密文状态？

在明文编程中，我们可以随时打印变量值。在FHE中，由于没有私钥，服务器无法解密。调试变得异常困难。以下是一些策略：

• 本地模拟调试：在开发初期，可以在客户端环境（拥有私钥）模拟整个计算流程。即，在加密数据后，本地也保留一份明文副本，然后在本地用FHE库模拟服务器计算，最后对比解密结果和明文计算结果是否一致。这能帮你定位算法逻辑错误。
• 噪声水平估计：虽然不能直接解密，但有些FHE库或工具可以提供噪声大小的估计值。当估计值接近或超过安全阈值时，就意味着下一次解密可能失败。FHEW本身可能不直接提供此接口，但你可以通过理论公式估算。
• 单元测试驱动：为每一个同态函数（如你实现的HomFullAdder）编写小的、可验证的单元测试。用已知的输入（加密的0和1）进行测试，并用私钥解密验证输出。确保每个基础组件正确，再组装成大型电路。

6.4 进阶优化方向

当你熟悉基础操作后，可以考虑以下优化来提升应用性能：

• 批处理：FHEW及其变种（如TFHE）支持批处理（也叫“打包”），即用一个密文同时加密多个比特。这能大幅提高数据吞吐量，特别适合向量化计算或并行处理多个相同电路。
• 电路优化：用更少的逻辑门实现相同的功能。例如，用更优的加法器结构（如华莱士树、Kogge-Stone加法器）来减少电路深度，从而减少所需的自举次数。
• 参数微调：在满足安全需求的前提下，尝试使用更小的参数（如更小的n）。这需要在安全性和性能之间做出权衡，最好有密码学专家的指导。
• 并发计算：同态计算中的各个门电路通常是独立的，可以并行计算。利用多线程或GPU（如果库支持）可以显著缩短实际运行时间。

掌握FHEW，本质上是掌握了一种全新的、以“噪声”为核心资源进行管理的编程范式。从加法、连加到乘法，每一步都需要仔细考量噪声的增长与重置。虽然这条路充满挑战，但它是通往构建真正隐私保护应用的必经之路。当你成功运行起第一个加密的乘法器时，那种在完全加密的数据流中完成计算的感觉，无疑是令人兴奋的。