Chloe：基于多级向量化与控制路径缩减的全同态加密上的循环变换
一、核心问题
论文的核心问题是：现有 FHE 编译器对“非平凡循环结构”的支持不足，导致 FHE 上程序表达能力和执行效率受限。
具体来说：
FHE 允许在密文上计算，但密文计算与明文计算行为差异很大。逻辑电路、比较、分支等非算术操作在 FHE 上通常比算术电路昂贵得多。
循环是结构化程序的基本控制结构，程序中大量运行时间集中在循环中；很多非代数表达式，如级数、积分、超越函数等，也依赖循环实现。
现有 FHE 编译器大致分为：
专用编译器：擅长优化算术电路和 SIMD 向量化，但不擅长比较、分支、逐位操作等非算术计算；
通用编译器：能把任意程序转成布尔电路，但性能开销大；
跨方案编译器：结合 CKKS、TFHE 等方案平衡效率与通用性，但对循环，尤其是复杂循环，优化仍不充分。
循环有两个基本要素：循环体和循环条件。论文把 FHE 上的循环分为两类：
透明循环 transparent loop：循环条件是明文/公开的，可以直接分析控制结构；
oblivious loop：循环条件是加密/私有的，编译器难以判断循环何时终止。
因此，论文要回答的是：如何设计一个编译器基础设施，使含非平凡循环结构的程序能够被转换成 FHE 上高效可执行的算法。
二、研究难点
论文指出的研究难点主要有以下几类。
循环体可能包含任意程序段，混合了算术与非算术操作。
例如循环体里既有加法、乘法，又有if条件判断。现有编译器要么只支持纯算术循环的展开和向量化，要么虽然能处理分支，但无法利用 SIMD FHE 算子，性能下降明显。FHE 中分支不能像明文一样“选择性执行”。
在密文条件下，if语句通常需要执行所有可能分支，再根据加密条件做多路复用。这会使循环体变成顺序结构，增加控制路径和计算成本。混合电路循环难以直接向量化。
算术部分适合 SIMD 批处理，非算术部分适合 PBS/SIMD-PBS；但二者混在一起时，需要先分割、分析类型、做成本评估和类型对齐，否则无法正确选择编码方式、密文格式和 FHE 算子。oblivious 循环的终止条件不可知。
如果循环条件是密文，默认情况下循环可能变成“无限循环”。现有方案要么强制完全展开，要么周期性进行客户端-服务器交互检查终止状态，二者代价都很高。需要建立 FHE 算子成本模型。
不同变换选项，如展开、槽编码 SIMD、系数编码 SIMD、PBS-SIMD 等，成本差异大；还需要考虑段与段之间的密文格式转换、编码转换成本。没有成本模型就无法自动选择最优编译方案。循环携带依赖和嵌套依赖会限制优化。
如果非算术操作带有循环携带依赖，就难以批处理；如果算术语句和非算术语句之间存在即时数据依赖，循环分割和 SIMD 优化可能无法进行，退化为类似 HEIR 的顺序if-else执行。内存开销与性能之间存在权衡。
SIMD-PBS 能显著降低延迟，但可能增加内存消耗；嵌套依赖和混合电路数据复用场景下，SIMD优化不适用，性能与内存表现会接近其他编译器。
三、关键技术
1. 多级中间表示与方言架构
解决的问题：
从 C ss语言程序到 FHE 算子之间跨度很大，需要同时表达明文计算、密文类型、向量类型、循环结构、底层 LWE/RLWE/RGSW 密文和具体 FHE 库 API。
解决方案：
用多级 IR 把这三个跨度拆开，每层只处理一个维度，并在中间层做循环分割、成本分析和类型对齐，最后才落到具体 FHE 算子。这样既保持了 C 程序的通用性，又能针对 FHE 的特点做细粒度优化成四层方言结构：
第 1 步：C 前端到明文层 IR：CHLOE 接受 C 类语言，用 Polygeist 把 C 程序转成 MLIR 的 SSA 形式 IR。
明文层 Plaintext Layer：用 Arith, Memref, Affine, Func 等方言。这一层还没有区分明文和密文，也没有 FHE 算子。通用优化如公共子表达式消除、死代码消除可以在这里做。
Arith表达算术计算；Memref表达数组和内存访问；Affine表达循环和仿射控制流；Func表达函数结构。
第 2 步：明文层到统一加密层fhe：把程序映射到fhe方言，即统一加密层。
统一加密层 Unified Encrypted Layer：定义fhe方言，用plain和cipher区分明文变量和密文变量，尽量把可明文计算的部分优化掉。
CHLOE 把输入变量及其派生变量标记为cipher，其余标记为plain。这样做的目的是尽量把明文计算留在普通编译器管线里，只把必须对密文做的计算下沉到 FHE 算子。比如循环边界、常量、索引计算等如果能用明文完成，就不生成 FHE 算子。
在这一层，程序还会被划分为算术区域和非算术区域。分支在这一层会被改写成“执行所有分支 + 根据加密条件多路复用”的形式，因为 FHE 不支持真正的选择性执行。
第 3 步：fhe层到操作密文层encVec、encScalar、encLoop
操作密文层 Operational Ciphertext Layer：统一fhe方言还不够细，因为一个加密向量可以 lowering 成多种形式：
一个 RLWE 密文；
一组 LWE 密文；
一个 RLWE 数组；
槽编码还是系数编码。
所以 CHLOE 进一步定义操作密文层：
encLoop方言：定义适合循环结构的操作，比如新的IF操作，便于循环分割、依赖分析和循环条件处理。encVec方言：定义EncVector和PlainVector，并在这里决定向量化方式、编码方法、编码参数、数据布局。encScalar：处理标量密文。
第 4 步：操作密文层到基础密文层LWE、RLWE、RGSW
再往下，encVec/encLoop被 lowering 到基础密文层
基础密文层 Fundamental Ciphertext Layer：定义LWE、RLWE、RGSW方言，与底层 FHE 库 API 一一对应，用于最终代码生成。
第 5 步：基础密文层到 MLIR EmitC 和 FHE 库
最后，CHLOE 通过MLIR EmitC工具链，把LWE、RLWE、RGSW方言转成对底层 FHE 库的调用。论文实现基于 SEAL 构建统一 FHE 库，最终生成可执行代码。
整个跨度可以概括为一条 lowering 链
C 程序
→Polygeist 前端
→明文层 IR：Arith、Memref、Affine、Func
→统一加密层fhe：区分plain/cipher，划分算术/非算术区域
→操作密文层encVec/encScalar/encLoop：循环分割、向量化选择、成本分析、类型对齐、oblivious 循环优化
→基础密文层LWE/RLWE/RGSW：绑定具体密文格式和加密参数
→MLIR EmitC
→底层 FHE 库调用/可执行代码
2. 透明循环变换：循环分割、类型分析与成本感知类型对齐
解决的问题：
透明循环中循环体可能同时包含算术和非算术操作，直接整体处理无法有效利用 SIMD，也难以选择合适 FHE 算子。
解决方案：
论文把混合电路透明循环的变换分为三个子过程。
2.1 循环分割 Loop Segmentation
目标是把复杂循环体拆成多个相互独立的简单循环，每个循环只包含一种类型的操作。
先把混合循环拆成纯算术循环和纯非算术循环，再分别优化。具体步骤包括：
分支展平 Branch Flattening：追踪分支中变量的 Def-Use 链；如果变量在分支外被引用，就在引用点前插入多路复用操作，根据加密
IF条件保留或清除变量值。循环携带依赖分析：检查非算术操作是否带有循环携带依赖。如果非算术操作的操作数是循环携带变量，则停止进一步分割和批处理；否则标记为 SIMD 兼容。
算子分组 Operator Grouping：根据操作类型把循环体划分为算术段和非算术段。当变量被不兼容类型的算子多次引用时，在类型切换边界插入分割算子，这类变量称为边界变量。
循环拆分 Loop Splitting：根据指令执行顺序重建循环，保证下游段所需变量在前面的段中产生；把边界变量转成向量化变量，使定义和使用分离到不同循环段后仍能正确连接。
2.2 分段类型分析与成本模型
解决的问题：
拆分后要判断每个段是否值得 SIMD 向量化，以及选择展开、槽编码 SIMD、系数编码 SIMD、PBS-SIMD 等哪种变换。
解决方案：
对非算术段：
SIMD-PBS 批量求值：如果循环迭代之间没有依赖，非算术段可以整体向量化：把输入向量编码进 RLWE 密文，用一次 SIMD-PBS 对所有元素逐槽应用同一个函数。
连续非算术函数合并为一次 PBS：如果连续两个非算术操作作用于同一个密文，且中间结果仍在函数表定义域内，就可以把两个函数表复合成一个，只调用一次 PBS。因为 PBS 的昂贵成本主要来自盲旋转和外部乘积，减少调用次数直接减少 bootstrapping 开销。
迭代次数少时直接展开：如果循环迭代次数很少，比如 4 次或 8 次，SIMD 的打包、编码、转换开销可能超过收益。此时编译器可以选择完全展开，逐次执行非算术操作。
对算术段：
槽编码 SIMD：把循环迭代向量编码进 RLWE 槽中，利用槽编码下同态乘法的逐槽语义，做批量逐元素加法和乘法。
系数编码 SIMD：把向量元素放在多项式系数上，利用多项式乘法和线性变换做批量运算。
直接展开：如果迭代次数少，或者段内存在妨碍批处理的依赖，直接展开逐次执行可能更便宜。
建立成本模型：以“次数为 N 的多项式乘法次数”为主要成本度量，覆盖明文-密文乘法、密文-密文乘法、旋转、外部乘积，以及线性变换、PBS、SIMD-PBS、PackLWE 等高级算子。
2.3 成本感知类型对齐 Cost-Aware Type Alignment
解决的问题：
不同循环段可能使用不同密文格式、编码方式和 FHE 方案，段与段之间需要插入转换算子；如何选择整体成本最低的变换组合。
解决方案：
把程序表示为 Def-Use 依赖图：顶点是代码段，边是依赖关系。整体成本为：
总成本 = 各段计算成本之和 + 各边转换成本之和。
算法遍历所有可能的变换组合，为每个循环段选择Unroll、Slot_SIMD、Coeff_SIMD、PBS_SIMD等变换，并在段间自动插入密文类型转换、编码转换等操作，最终选择总成本最小的变换图。
3. 混合电路向量化技术
解决的问题：
循环中算术和非算术计算混合时，如何分别利用 SIMD 能力，而不是退化成低效的逐位或逐条执行。
解决方案：
非算术部分使用PBS / SIMD-PBS，把比较、条件函数等转成对密文的函数求值；连续非算术函数可通过函数复合合并为一次 PBS。
算术部分使用SIMD 批处理：槽编码适合向量元素级并行；系数编码适合某些多项式系数布局；迭代次数少时直接展开。
通过循环分割把算术段和非算术段分开，使每段都能采用最合适的向量化方式。
通过类型对齐插入
STOC、CTOS、EXT_RCTLWE、PACKLWE等转换算子，桥接槽编码与系数编码、LWE 与 RLWE 等格式。
4. oblivious 循环的闭式分析与控制路径缩减
解决的问题：
循环条件加密时，编译器不知道循环何时终止；完全展开会产生大量控制路径，交互式检查代价高。
oblivious 循环的闭式分析是指：对循环条件加密、本质上在计算递推序列的循环，尝试推导通项公式，把“迭代 n 次”变成“直接计算第 n 项”，从而彻底避免展开。
控制路径缩减是指：在无法闭式求解时，通过静态分析确定最大迭代次数、通过分支优化高效生成同态选择指示，减少必须处理的候选路径数量。
for (i = 0; i < cipher(200); i++) { ... } 循环条件200加密，无法在编译时决定循环何时终止
“控制路径”：程序在密文条件下可能走的不同执行轨迹
解决方案：
CHLOE 把 oblivious 循环分为三类并分别处理：
闭式 oblivious 循环：
对递推关系做闭式分析。若循环可表示为 C-finite 递推等具有闭式表达的形式，就直接转成解析表达式，避免迭代。例如线性递推、带等值条件判断的线性递推可化为 C-finite 形式。这样可把循环转成单行表达式，显著提升性能。数值型 oblivious 循环 numeric loop：
如果循环变量是归纳变量，可根据其数据类型静态确定最大迭代次数。例如uint8_t变量最多 256 次。CHLOE 允许自定义数据类型，程序设计师可缩小循环变量域以减少展开次数。一般 oblivious 循环 general loop：
如果循环变量不是归纳变量，编译时无法确定展开次数，需要插入客户端-服务器通信等协议级原语保证终止。
5. 安全模型与实验评估方法
解决的问题：
验证 CHLOE 在真实 FHE 参数和基准程序上的性能与通用性。
解决方案：
威胁模型：半诚实安全两方计算模型，客户端和服务器均为半诚实对手；所有输入数据归客户端所有；编译可由客户端或服务器执行。
实验平台：基于 MLIR 19.0.0 和 C++17，底层基于 SEAL 的统一 FHE 库；使用 BFV、TFHE、CKKS 等参数，达到 128 位安全。
基准：透明循环包括数据库查询、SVM 分类、图像分割、KMeans；oblivious 循环包括 Fibonacci、Markov 状态转移矩阵、复利、可变长度向量求和、条件向量更新等。
对比对象：Transpiler、HEIR、PEGASUS、基于 OpenFHE 的多项式近似方案等。
四、主要结论与贡献
论文的主要结论和贡献可以概括为以下几点。
提出 CHLOE：首个可端到端处理非平凡循环的 FHE 编译器框架。
据作者所述，CHLOE 是第一个无需人工干预即可对含非平凡循环的程序进行端到端变换的 FHE 编译器。它结合静态分析和动态分析，对含嵌套分支的复杂循环做多层优化。提出混合电路向量化方法。
论文指出，含算术和非算术计算的循环不能简单整体向量化；需要通过循环分割、分布、成本分析和类型对齐，找到正确变换模式，才能充分利用 FHE 的 SIMD 能力。系统处理 oblivious 循环。
通过闭式表达式避免完全展开；通过静态分析区分数值型与一般型 oblivious 循环；通过新的分支优化方法降低迭代选择成本。必要时使用 SIMD-PBS、多项式近似或 EXTProduct 生成选择向量。实验证明显著性能提升。
摘要和贡献部分给出：相比最先进 FHE 编译器，性能提升从 1.5× 到 54×，含 oblivious 循环的程序最高可达 10^5×；透明循环应用程序上可达 3.2×–54× 加速；oblivious 循环相对人工辅助的全展开方案可达 1.5×–10^5× 加速。评测中还展示了数据库查询、SVM、图像分割、KMeans 等场景的加速。提出成本驱动的程序变换。
以多项式乘法次数等为成本模型，联合考虑循环段计算成本和段间转换成本，通过依赖图遍历选择最小成本变换组合，自动插入转换算子。指出局限与后续方向。
内存开销：SIMD-PBS 可能增加内存消耗；
嵌套依赖：算术与非算术语句存在即时数据依赖时，循环分割受限，性能接近 HEIR；
混合电路数据复用：同一向量元素同时用于算术和非算术语句时存在实现限制，可通过在分割循环间插入密文转换算子解决
五、知识体系
学习这篇论文建议建立四层知识体系，并按“密码学基础 → 编译基础设施 → 循环优化方法 → 实验与安全”的顺序推进。
1. FHE 密码学与算子基础
需要掌握：
FHE 基本概念：密文计算、安全性、半诚实模型；
三类方案：BFV/BGV、CKKS、FHEW/TFHE；
三类密文：LWE、RLWE、RGSW；
编码方式：槽编码 slot encoding、系数编码 coefficient encoding；
关键算子：密文加法、乘法、旋转、外部乘积 EXTProduct、PBS、SIMD-PBS、HomPoly；
转换算子：
EXT_RCTLWE、PACKLWE、STOC、CTOS；为什么 PBS 能计算非算术函数，为什么 SIMD-PBS 能批量处理。
2. 编译器与 MLIR 基础设施
需要掌握：
编译流水线：前端、IR、优化 pass、后端代码生成；
C 程序
→Polygeist 前端
→明文层 IR：Arith/Memref/Affine/Func
→统一加密层fhe：区分plain/cipher，划分算术/非算术区域
→操作密文层encVec/encScalar/encLoop：
→ 透明循环：分割 → 类型分析 → 成本感知类型对齐
→ oblivious 循环：闭式分析 → 静态分析 → 分支优化
→基础密文层LWE/RLWE/RGSW：绑定密文格式和加密参数
→MLIR EmitC
→底层 FHE 库调用 / 可执行代码
每一级只解决一个维度的跨度：
前端解决“C 语法到 SSA IR”；
fhe层解决“明文/密文区分和区域划分”；
操作密文层解决“循环怎么拆、怎么向量化、格式怎么对齐”；
基础密文层解决“用哪种密文和参数”；
后端解决“怎么落到库调用”。
SSA 形式：每个变量只赋值一次的 IR，让数据依赖显式化，是后续分析的基础
Def-Use 链：描述“某个定义的值流向哪些使用点”，是局部数据依赖分析的核心工具；
依赖图：把 Def-Use 关系提升为图结构，顶点是语句或代码段，边是依赖，用于全局重排、并行化、成本分析和变换选择；
MLIR 方言 dialect、lowering、EmitC；
Polygeist 将 C 转成 MLIR；
CHLOE 的四层方言：明文层、统一加密层、操作密文层、基础密文层。
3. 循环优化与程序分析
需要掌握：
循环分布、循环分割、循环展开、循环向量化；
循环携带依赖、边界变量、变量向量化；
分支展平与多路复用；
成本模型与 DAG 上的最小成本变换选择；
闭式递推分析：C-finite 递推、Gosper 可求和等；
静态循环分析：归纳变量、最大迭代次数；
oblivious 循环的分支优化：选择向量 ℓ 的构造
4. 安全模型与实验方法
需要掌握：
半诚实两方计算威胁模型；
FHE 参数选择与 128 位安全；
基准设计：透明循环 vs oblivious 循环；
性能指标：延迟、内存、加速比；
对比方法：Transpiler、HEIR、PEGASUS、OpenFHE 多项式近似；
理解 CHLOE 的适用边界：嵌套依赖、混合电路数据复用、内存开销。