全同态加密的概念

同态：密文计算的结果解密后，等于明文计算的结果。即 Dec(Enc(a)⊕Enc(b))=a+b

全同态：支持任意深度的加法和乘法运算（不仅是单一操作，而且可以无限次组合）。

第一层：密码学基础与底层理论

FHE-Scheme（全同态加密方案）

噪声增长：每次密文计算（尤其是乘法）都会导致噪声增大，一旦噪声超过阈值，解密就会失败。这是 FHE 与普通公钥加密最大的不同。

自举（Bootstrapping）：是用公钥加密私钥，在密文状态下解密自身（“吃自己的尾巴”），从而“刷新”密文，重置噪声大小。

SIMD 批处理（Batching）：把成百上千个数据塞进一个密文里，一次计算处理所有数据（基于中国剩余定理 CRT 或复数域编码）

模数切换（Modulus Switching）和重线性化（Relinearization）：用于控制密文膨胀和噪声增长

密钥切换（Key Switching）：转换密文所使用的密钥（例如从公钥切换到私钥，或用于同态旋转）

• BGV / BFV 方案

底层数学：基于 LWE / RLWE（环上容错学习）问题。

特点：主要处理整数和模运算。采用“层级（Leveled）”同态，即在噪声耗尽前预先设定好电路深度。BGV 与 BFV 在打包（Batching）和模数切换（Modulus Switching）上略有不同。

应用：适合逻辑电路、精确整数计算。

• CKKS 方案：

底层数学：基于 RLWE。

特点：专门为浮点数/复数近似计算设计。它将消息编码在多项式的系数中，支持 SIMD（单指令多数据）批处理。

应用：隐私保护机器学习（PPML）、神经网络推理（FHE-CNN）、线性代数（FHE-Matrix Multiplication）几乎全用它。

• TFHE / FHEW 方案：

传统的 FHE 方案（如 BGV/BFV）执行一次深度计算后，密文中的“噪声”会累积到临界值，必须进行耗时的自举操作来“刷新”噪声，这曾是 FHE 实用化的最大瓶颈。

FHEW 和 TFHE 的设计截然不同：它们不再等待电路达到一定深度后才自举，而是每评估一个逻辑门（如一个 AND 门），就立即对结果密文进行一次自举。这使得它们能够处理任意深度的布尔电路。正是通过将自举操作极致地优化，FHEW 和 TFHE 才得以实用。

TFHE（全同态加密）：其最核心的创新在于实现了极快的自举（Bootstrapping）速度，将密文噪声刷新时间从秒级压缩至毫秒级，这使得对加密数据进行实时计算成为可能。与BFV/BGV擅长整数算术、CKKS擅长浮点近似计算不同，TFHE采用逐位加密，专为布尔电路（逻辑门）和低精度运算而设计，在处理比较、查表、控制流等非线性操作时具有显著优势 。

一次完整的TFHE自举（以刷新一个TLWE密文为例）通常包含以下关键步骤，其核心是盲旋转（Blind Rotation），它占据了绝大部分计算时间：

1. 初始化（Initialize）：根据输入的TLWE密文，初始化一个包含“测试多项式”的同态累加器（Homomorphic Accumulator）。

2. 盲旋转（Blind Rotation）：这是最核心、最耗时的一步。利用自举密钥（由TRGSW密文组成）与累加器中的TRLWE密文进行一系列外积运算，根据加密的输入值，在密文状态下“旋转”累加器中的多项式。

3. 样本提取（Sample Extraction）：从旋转后的TRLWE密文中，提取出一个分量（通常是常数项），将其转换为一个TLWE密文。此时，该密文的噪声已被刷新。

4. 密钥切换（Key Switching）：通过密钥切换技术，将密文从自举过程使用的中间密钥下，切换回原始的TLWE密钥，使密文格式与输入保持一致。

第二层：系统架构与工程实现

• FHE-Matrix Multiplication（FHE 矩阵乘法）

矩阵乘法是绝大多数机器学习负载的核心。在FHE中，它之所以困难，根源在于密文旋转（Rotation）的代价极高。高效的FHE矩阵乘法方案，本质上都是围绕“如何减少旋转次数”来设计的

核心技术：SIMD打包与分块策略

主流方案（如基于CKKS）利用SIMD（单指令多数据）批处理技术，将一个矩阵的多个元素打包进单个密文的不同“槽位（slot）”中。这样，一次密文运算就能同时处理数十甚至数百个数据点。在此基础上，MAT-FHE等方案通过将矩阵填充为超立方体结构，并利用按行/列旋转、密文-明文乘法等操作，避免了代价高昂的密文-密文乘法，从而支持任意维度（包括非方阵）的矩阵乘法。其实验显示，16维矩阵乘法耗时约4.23秒，比当时最优的方阵方案快约1.5倍。

定位：基础数学算子。同态加密下的矩阵乘法（涉及旋转、重线性化等复杂操作）是绝大多数高级应用的底层支撑。

• FHE-Compiler（FHE 编译器）

  负责将高级语言（如 Python/C++ 代码）转化为 FHE 可执行的底层指令，涉及计算图的优化。

一个FHE编译器需要自动完成几项关键决策：自举（Bootstrapping）的放置位置（何时刷新噪声）、模数缩放（Rescale）的管理（控制精度与噪声的平衡），以及数据在密文槽位中的布局（以最小化昂贵的旋转操作）。Orbit等工作专门利用整数线性规划来优化自举和缩放的位置。

循环变换：CHLOE编译器专门处理FHE程序中的循环结构。它将循环区分为条件透明的循环和** oblivious循环**（循环条件本身是加密的），并分别进行多级向量化和控制路径削减，性能提升可达1.5倍至105倍。

端到端效率：Parasol编译器通过引入自定义指令集架构（ISA）和电路自举（CBS）范式，在运行时上实现了最高17倍的加速，同时程序体积缩小22倍，编译时间缩短32倍。

• FHE-Hardware（FHE 硬件加速）

FHE的计算和访存模式与普通程序截然不同，通用CPU效率极低，这催生了专用硬件的研究。

路线一：FPGA与ASIC专用加速器
FPGA（现场可编程门阵列）和ASIC（专用集成电路）可以针对FHE的核心运算（如NTT、密钥切换、自举）进行深度定制。例如，HERA是一款基于HBM（高带宽内存）FPGA的带宽高效加速器，其性能密度（每乘法器的吞吐量）可达当时最优ASIC方案的70.9倍。Hypnos则是一个软硬件协同设计框架，通过专门的分页内存管理系统来缓解FHE巨大的内存压力，在数据密集型应用上比SOTA ASIC和FPGA方案分别快2.75倍和4.72倍。

路线二：同态处理单元（HPU）——迈向通用化
更长远的方向是设计原生支持FHE的通用处理器。HPU（Homomorphic Processing Unit）在RISC-V架构基础上扩展了同态指令集架构（H-ISA），目标是让FHE计算成为一种“原生”的计算机能力。其实ASIC原型在LSTM等负载上已展现出对专用TFHE加速器1.36倍的加速比，但功耗和计算速度仍是待解的挑战。

• FHE-GPU（基于 GPU 的 FHE 加速）

GPU加速的核心思路是将FHE中高度可并行的计算模式（尤其是NTT和盲旋转）映射到数千个CUDA核心上。

定位：底层物理执行环境。因为 FHE 计算开销极大，通常需要 FPGA/ASIC（Hardware）或 GPU 来进行硬件加速。

第三层：上层算法与应用场景

• FHE-PPML（隐私保护机器学习）

它的目标是让模型拥有者（服务器）和数据拥有者（客户端）在不泄露各自秘密的前提下，完成AI计算。

核心：

• 推理（Inference）：模型是明文（或加密的），用户输入加密的数据，服务器算完返回加密结果。目前最成熟、落地最多。

• 训练（Training）：数据和模型全加密，服务器连模型权重都看不到，直接在密文上算梯度。极难，主要在学术界研究。

难点：

非线性操作。矩阵乘法（线性）好办，但神经网络里充满了ReLU、Max Pooling（找最大值）、Sigmoid这些非线性操作，FHE处理起来极其昂贵。

解决方案：

多项式近似：用高阶多项式去逼近ReLU（比如 x2x2 或 x3x3），把非线性变成同态加法和乘法。但精度容易崩。

混合协议（FHE + MPC）：线性部分用FHE（CKKS），非线性部分用安全多方计算（MPC）或者 TFHE 的可编程自举（PBS）。

• FHE-CNN（基于 FHE 的卷积神经网络）

  PPML 的具体子领域（推理/Inference）。如何在加密状态下完成 CNN 的前向传播。

卷积 (Convolution)：在 CKKS 方案下，利用SIMD Batching技术，将多维张量（如多通道图像）映射到多项式系数槽（Slots）中，将卷积转化为循环矩阵-向量乘法或点积。使用同态旋转（Rotation）与明文-密文乘法（Plaintext-Ciphertext Multiplication）替代昂贵的密文-密文乘法。

激活函数 (ReLU)：一般采用 f(x)=x^2 或 f(x)=ax^2+bx+c等低阶多项式进行近似替代。

池化层 (Pooling)：由于密文下求最大值（Max Pooling）涉及非线性比较，通常降级替换为线性计算友好的平均池化 (Average Pooling)。

• FHE-Training（FHE 模型训练）

PPML 的进阶子领域。在加密数据上直接训练模型（难度远高于推理，通常涉及多项式近似等技术）。

难点：噪声爆炸与计算深度

反向传播需要计算梯度，涉及大量链式求导与高阶乘法。每次迭代都会极大消耗噪声预算（Noise Budget），导致必须极其频繁地执行自举（Bootstrapping），计算开销远超推理。

解决方式：

限制模型复杂度：主要集中于同态逻辑回归（Logistic Regression）、线性 SVM 等浅层模型。

多项式激活与求导：使用高阶平滑多项式替代ReLU，以支持梯度的同态求导。

混合训练架构：前向/反向传播的线性部分使用 FHE 加速，非线性梯度更新交由 MPC 或联邦学习（FL）框架处理。

• FHE-Retrieval（FHE 信息检索）

密码学领域的重要分支，通常指PIR (Private Information Retrieval)，即单服务器隐私信息检索。

业务逻辑：客户端持有查询索引 i（加密），服务器持有数据库 DB（明文或密文）。服务器在同态下返回 DB[i] 的密文，且对 i 不可见，客户端解密后仅获取 DB[i]。

同态实现机制:

• 精确匹配 (Exact Match)：通常采用BFV（整数）或TFHE（布尔）。客户端发送加密的指示向量（One-hot Vector），服务器进行同态内积运算。

• 向量检索 (Vector Similarity)：面向大模型的 RAG 向量数据库。通常采用CKKS，服务器同态计算查询向量与数据库向量的内积或欧氏距离，返回最相似的 Top-K 密文。