🤖 machine learning

CHEHAB RL: Learning to Optimize Fully Homomorphic Encryption Computations

本文介绍了 CHEHAB RL，这是一个深度强化学习框架，它通过学习应用向量化重写规则，实现了全同态加密代码优化的自动化，从而与现有最先进方法相比，显著提升了执行速度、减少了噪声增长并大幅加快了编译速度。

原作者： Bilel Sefsaf, Abderraouf Dandani, Abdessamed Seddiki, Arab Mohammed, Eduardo Chielle, Michail Maniatakos, Riyadh Baghdadi

发布于 2026-01-28

📖 1 分钟阅读☕ 轻松阅读

CC BY 4.0

原作者： Bilel Sefsaf, Abderraouf Dandani, Abdessamed Seddiki, Arab Mohammed, Eduardo Chielle, Michail Maniatakos, Riyadh Baghdadi

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

大局观：“锁着的盒子”问题

想象一下，你拥有一个非常珍贵的秘密，比如你的银行密码或医疗记录。你想把这个秘密发送给一个陌生人（云服务器）来对它进行一些数学运算，但你非常害怕他们会偷看并窃取你的秘密。

全同态加密 (Fully Homomorphic Encryption, FHE) 是解决这个问题的神奇方案。它就像是把你的数据放入一个锁着的透明盒子中。你可以把这个盒子交给陌生人，让他们去摇晃、撞击或混合盒中的内容（执行计算），而无需打开锁或看到里面的内容。当他们完成后，他们把盒子还给你，你打开锁即可看到结果。

代价： 这种魔法极其缓慢且混乱。在锁着的盒子上做数学运算比在普通数据上进行运算要慢数千倍。这就像是戴着厚重笨拙的烤箱手套并蒙着眼睛去烤蛋糕。

问题所在：编写“食谱”很难

为了让这种“锁着的盒子”数学运算变得更快，专家们必须编写非常特定的底层代码。这就像是戴着那些手套去尝试编写一份蛋糕的食谱。

太复杂： 你必须决定如何精确地将食材（数据）打包进盒子里，以免它们混淆。
太慢： 如果打包方式不对，数学运算会耗时极长，或者盒子里的“噪声”（静电/干扰）会变得非常大，导致最终结果变成垃圾。
搜索陷阱： 寻找完美的打包方式就像是在大海捞针。现有的工具试图通过逐一检查每一个位置来寻找这根针（“暴力”搜索）。这不仅耗时很长，而且经常会陷入一个虽然“还不错”但并非最优的境地。

解决方案：CHEHAB RL（“聪明的学徒”）

本文作者构建了一个名为 CHEHAB RL 的新工具。与其尝试检查每一种可能性，他们教计算机如何学习，使用的是一种叫做强化学习 (Reinforcement Learning, RL) 的技术。

把它想象成训练一名聪明的学徒厨师：

目标： 学徒的任务是重新排列锁着盒子里的食材，使数学运算尽可能快，且产生的“噪声”最少。
训练： 他们没有给学徒一本规则手册，而是让学徒尝试数百万种不同的食材排列方式。
- 如果某种排列方式让数学运算变快了，学徒就会得到一个“奖励”（甜头）。
- 如果让运算变慢或噪声变大，学徒就会得到一个“责备”（惩罚）。
数据集： 为了教导学徒，作者并没有使用随机的垃圾数据。他们使用了一个大语言模型 (LLM) —— 一个在真实世界代码上训练过的超级智能 AI —— 来生成数千个真实的“练习食谱”。这就像是让学徒在真实的蛋糕上进行练习，而不是在随机的一堆面粉和鸡蛋上练习。

它是如何工作的：“重写”游戏

该系统的核心是一个乐高 (Lego) 游戏。

你有一个由乐高积木搭建而成的结构（你的加密代码）。
你有一套规则（例如“交换这两个积木”或“将这三个合并为一个”）。
RL 智能体（学徒） 会观察这个结构，并决定：“如果我在这里应用规则 A，然后在那里应用规则 B，整个结构是否会变得更稳定、更快？”

智能体会学习一种策略 (Policy)，即如何以完美的顺序应用这些规则。它不仅仅关注单一步骤，而是观察全局，以找到最佳路径。

结果：速度、静默与效率

论文将他们的“聪明学徒”（CHEHAB RL）与目前最好的工具（称为 Coyote）进行了对比。结果如下：

执行速度（烤蛋糕的速度）： 由 CHEHAB RL 生成的代码比 Coyote 快了 5.3 倍。这就像是从缓慢的手动烤箱切换到了高速的对流烤箱。
噪声（静电/干扰）： 使用 CHEHAB RL 时，锁盒中的“噪声”增长量减少了 2.54 倍。这意味着最终结果更加清晰，不太可能被毁掉。
编译时间（编写食谱的时间）： 或许最令人惊讶的结果是：CHEHAB RL 编写优化代码所花费的时间比 Coyote 搜索代码的时间少了 27.9 倍。学徒很快就学会了策略，而 Coyote 还在疯狂地搜寻那堆稻草。

为什么这很重要

论文声称，这是首次使用强化学习来解决 FHE 代码优化这一特定问题。

它能处理混乱的代码： 不同于以往只能处理整齐的循环代码的工具，这个系统可以处理杂乱无章、非结构化的代码（就像一团乱掉的毛线球）。
它具有可扩展性： 随着问题规模的扩大，这个“聪明学徒”会变得越来越擅长处理它们，而旧的“暴力搜索”方法则会变得越来越慢。

总结类比

想象你正在试图整理一个巨大的图书馆，书都锁在玻璃柜里。

旧方法 (Coyote)： 你雇佣了一组图书管理员，他们尝试每一种可能的书籍排列方式，以看看哪种方式找书最快。他们会感到疲惫，耗费大量时间，并且往往只能选出一个“还行”的排列方式，而非最好的。
新方法 (CHEHAB RL)： 你雇佣了一位天才图书管理员，他观看过数千段其他图书馆整理工作的视频。他学会了哪些模式是有效的。当你把一个新的图书馆交给他时，他能瞬间知道最好的整理方式，既节省时间，又让书籍更容易被找到。

论文得出结论，通过使用这种“学习”方法，我们可以让“锁着的盒子”技术在现实世界中变得更加实用，让我们能够在不等待数天的情况下，对私密数据进行复杂的数学运算。

技术摘要：CHEHAB RL：学习优化全同态加密计算

1. 问题陈述

全同态加密（FHE）能够在不解密的情况下对加密数据进行计算，从而保护隐私。然而，FHE 的计算成本仍然非常高昂；例如，一次密文乘法可能比其对应的明文操作慢 $10^6$ 倍。这种性能差距源于同态操作固有的复杂性，这些操作涉及高次多项式乘法和显著的噪声增长。

编写高效的 FHE 代码是一项复杂的、易出错的任务，需要深厚的密码学专业知识。虽然已经开发出了用于自动化 FHE 代码生成的编译器，但现有解决方案面临着显著的局限性：

结构化与非结构化代码： 像 HECO 和 CHET 这样的编译器专注于结构化（基于循环）的代码，而像 Coyote 和 Porcupine 这样的其他工具则试图同时处理结构化和非结构化（任意的、非基于循环的）代码。
搜索空间复杂度： 当前最先进的编译器（如 Coyote、Porcupine）将向量化视为一个组合搜索问题。它们依赖于手工调优的启发式算法、整数线性规划（ILP）或程序合成来探索庞大的设计空间（例如，决定哪些子表达式应该打包、数据布局、旋转插入等）。
可扩展性与局部最优： 在这个复杂的空间中，局部的决策往往会产生非局部的效应（例如，一个打包决策可能会增加未来的旋转成本）。简单的启发式算法经常陷入较差的局部最优解，而随着程序规模的增加，穷举搜索在计算上变得难以实现。

2. 方法论

本文提出了 CHEHAB RL，这是一个利用深度强化学习（RL）来自动化 FHE 代码优化的创新框架。它不再采用组合搜索，而是将问题建模为一个序列决策过程，RL 智能体通过学习一个策略来应用一系列重写规则。

2.1 框架概述

CHEHAB RL 集成在 CHEHAB FHE 编译器中。其工作流程如下：

输入： 使用 CHEHAB 领域特定语言（DSL）编写的程序，该程序被降低（lowered）为抽象语法树（AST）和数据流图（DAG）形式的中间表示（IR）。
RL 优化： RL 智能体遍历 IR，从项重写系统（TRS）中选择一系列重写规则，以实现标量代码的向量化、简化表达式并最小化噪声/延迟。
输出： 优化后的 IR 被用于生成针对 Microsoft SEAL 后端（BFV 方案）的 C++ 代码。

2.2 核心技术组件

A. 状态表示

为了向 RL 智能体表示程序 IR，作者采用了**标识符与常量不变性（ICI）**标记化技术。

归一化： 变量被重命名（例如 $v_0, v_1$ ），常量（除 0 和 1 之外）被抽象为通用标记（ $c_0, c_1$ ）。这创建了一个对于命名和特定常量值具有不变性的规范形式，将语义等价的程序折叠为相同的表示。
编码： 标记化的序列由一个 Transformer 编码器（4 层，8 个注意力头）处理，以生成固定长度的 256 维嵌入。选择这种架构而非 RNN（LSTM/GRU）是因为它能更好地建模展开后的 FHE 程序中的长程依赖关系。

B. 动作空间

动作空间的设计旨在处理大量的可能规则和应用位置。

层级策略： 智能体没有使用扁平的动作空间（规则 + 位置），而是使用了一个两步层级策略：
1. 规则选择网络： 一个 MLP 从 84 个规则中选择要应用的重写规则。
2. 位置选择网络： 第二个 MLP 选择应用该规则的具体位置（匹配索引）。
终止： 一个特殊的 END 动作允许智能体终止优化回合。

C. 奖励模型

智能体的训练目标是最小化一个平衡了执行时间和噪声增长的复合代价函数。

代价函数： $Cost(e) = w_{ops} \cdot C_{ops}(e) + w_{depth} \cdot D_{circuit}(e) + w_{mult} \cdot D_{mult}(e)$ $C os t (e) = w_{o p s} \cdot C_{o p s} (e) + w_{d e pt h} \cdot D_{c i r c u i t} (e) + w_{m u l t} \cdot D_{m u l t} (e)$ 。
- $C_{ops}$ ：加权操作成本之和（向量加法：1，向量乘法：100，旋转：50，标量操作：250）。
- $D_{circuit}$ ：电路深度。
- $D_{mult}$ ：乘法深度（对于 BFV 中的噪声增长至关重要）。
奖励结构：
- 步进奖励 ( $R_{step}$ )：基于每次动作后代价下降的百分比提供的即时奖励。
- 最终奖励 ( $R_{final}$ )：基于初始状态到最终状态总代价减少量的全局奖励。这可以防止智能体表现出局部贪婪性，并鼓励产生全局最优电路的序列。

D. 训练数据合成

由于缺乏现有的 FHE 优化数据集，作者使用大语言模型（LLM，Gemini 2.5 Flash）合成了 15,855 个独特的表达式。

LLM 指导： LLM 被提示输入语法规则、重写规则示例以及真实的内核模体（例如，矩阵加法、平方差），以生成多样化的、可优化的代码模式。
验证： 生成的表达式经过了语法有效性、唯一性（通过 ICI 标记化）以及排除基准程序（benchmark programs）的过滤，以确保泛化能力。

E. 训练算法

智能体使用 近端策略优化（PPO） 算法在单个多核 CPU 上进行了 200 万个时间步的训练。

3. 核心贡献

形式化： 首次将 FHE 代码优化表述为可以通过强化学习解决的序列决策问题。
CHEHAB RL 框架： 一个能够自动向量化结构化和非结构化 FHE 代码，同时最小化噪声增长和电路延迟的新型系统。它比现有的组合搜索方法具有更好的可扩展性。
LLM 合成数据集： 创建并验证了一个由 LLM 生成的大规模、多样化的训练数据集，证明了在这些数据上进行训练比在随机程序上训练能获得显著更好的智能体。
性能提升： 实证证据表明，CHEHAB RL 生成的代码在执行速度上比最先进的 Coyote 编译器快 5.3 倍，积累的噪声少 2.54 倍，且编译时间快 27.9 倍（几何平均值）。
开源： 向社区发布了 CHEHAB RL 框架。

4. 结果与评估

作者在包括图像处理滤波器、线性代数内核和随机生成的非规则多项式在内的基准测试套件上，将 CHEHAB RL 与 Coyote（一种最先进的向量化 FHE 编译器）进行了对比评估。

执行时间： CHEHAB RL 生成的代码平均比 Coyote 快 5.3 倍。在特定案例中（例如 Linear Regression 32），加速比达到了 114 倍。这归功于 RL 智能体找到了更少的运算量和更简单的布局。
噪声预算： 生成的电路平均消耗的噪声预算比 Coyote 少 2.54 倍。在 Coyote 耗尽噪声预算并导致执行失败的基准测试中，CHEHAB RL 成功生成了有效的、可运行的电路。
编译时间： 基于 RL 的编译过程比 Coyote 的搜索式方法快 27.9 倍。虽然 RL 智能体在处理小型基准测试时会产生额外开销（由于神经网络推理步骤），但在处理大型电路时，它展示了优于 Coyote 组合搜索的卓越可扩展性。
消融研究：
- LLM vs. 随机数据： 在特定基准测试中，使用 LLM 生成数据训练的智能体比使用随机数据训练的智能体快 13 倍，凸显了现实代码模式的重要性。
- 奖励设计： 结合步进奖励和最终奖励的效果优于仅使用步进奖励，这防止了陷入局部最优。
- 架构： Transformer 编码器在学习程序表示方面优于 GRU 基准模型，且层级化动作空间在学习速度和奖励方面优于扁平化动作空间。

5. 意义与主张

本文声称 CHEHAB RL 代表了 FHE 编译范式的转变。通过从启发式驱动的组合搜索转向基于学习的策略优化，该框架解决了以往方法中固有的可扩展性和局部最优问题。

作者强调，这是首次使用 RL 来解决 FHE 优化问题，成功地处理了向量化、密码学噪声积累和操作成本之间的权衡。这项工作证明，RL 智能体可以学习有效的全局变换策略，从而超越手工调优的启发式算法和 ILP 解算器，尤其是在处理非结构化代码时。利用 LLM 进行数据集合成进一步展示了在数据匮乏领域生成高质量训练数据的路径。

文章总结道，CHEHEB RL 通过显著降低加密计算的运行时间和编译时间，同时保持底层密码方案的安全保证，使得 FHE 的实际应用成为可能。