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 前端到明文层 IRCHLOE 接受 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 前端→明文层 IRArith、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 和 C17底层基于 SEAL 的统一 FHE 库使用 BFV、TFHE、CKKS 等参数达到 128 位安全。基准透明循环包括数据库查询、SVM 分类、图像分割、KMeansoblivious 循环包括 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 前端→明文层 IRArith/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、EmitCPolygeist 将 C 转成 MLIRCHLOE 的四层方言明文层、统一加密层、操作密文层、基础密文层。3. 循环优化与程序分析需要掌握循环分布、循环分割、循环展开、循环向量化循环携带依赖、边界变量、变量向量化分支展平与多路复用成本模型与 DAG 上的最小成本变换选择闭式递推分析C-finite 递推、Gosper 可求和等静态循环分析归纳变量、最大迭代次数oblivious 循环的分支优化选择向量 ℓ 的构造4. 安全模型与实验方法需要掌握半诚实两方计算威胁模型FHE 参数选择与 128 位安全基准设计透明循环 vs oblivious 循环性能指标延迟、内存、加速比对比方法Transpiler、HEIR、PEGASUS、OpenFHE 多项式近似理解 CHLOE 的适用边界嵌套依赖、混合电路数据复用、内存开销。