💻 computer science

Hardware-Friendly Randomization: Enabling Random-Access and Minimal Wiring in FHE Accelerators with Low Total Cost

该论文提出了一种硬件友好的随机化方案，通过在加速器端按需生成 RLWE 随机多项式，在保持极低客户端开销的同时，显著降低了全同态加密加速器的通信延迟、布线复杂度及功耗。

原作者： Ilan Rosenfeld, Noam Kleinburd, Hillel Chapman, Dror Reuven

发布于 2026-02-24

📖 1 分钟阅读☕ 轻松阅读

原作者： Ilan Rosenfeld, Noam Kleinburd, Hillel Chapman, Dror Reuven

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

这篇论文提出了一种让**全同态加密（FHE）**硬件加速器变得更高效、更省电、更便宜的新方法。

为了让你更容易理解，我们可以把整个系统想象成一家超级繁忙的“加密数据加工厂”。

1. 背景：工厂里的“随机原料”难题

什么是全同态加密？
想象一下，你有一封绝密信件（数据），你想让外面的工厂帮你处理（计算），但你不想把信拆开给他们看。全同态加密就是那把神奇的锁，让工厂能在信封不拆开的情况下直接计算，最后把结果还给你，你解开锁就能得到正确答案。

现在的痛点：
在这个工厂里，处理数据需要一种特殊的“随机原料”（论文里叫多项式 $\mathbf{a}$ ）。

传统做法： 客户（你）把这种原料全部打包，通过快递（网络）寄给工厂。
问题： 这种原料非常巨大（可能高达几十兆甚至几吉字节）。如果工厂要处理成千上万个任务，快递费（通信带宽）就太贵了，而且工厂仓库（内存）也装不下这么多原料。

现有的改进方案：
以前，人们想了一个办法：客户只寄一个**“种子”**（比如一个密码），工厂收到后，用这个种子在内部“变”出原料来。这就像只寄了一张食谱，工厂自己按食谱做菜。

新问题： 工厂内部为了“变”出这些原料，需要把原料从“中央厨房”运送到几千个“灶台”（计算单元）。
- 布线太乱： 就像在工厂里拉几千根长电线，既占地方又费电。
- 排队太慢： 以前的“变”原料机器是串行的（像流水线，必须按顺序 1、2、3... 变），如果灶台 100 号急着要第 50 个原料，它得等前 49 个都变完才能拿到。这导致工厂效率低下，或者需要巨大的仓库来存半成品。

2. 这篇论文的解决方案：分布式“微型厨房”

这篇论文提出了一种**“硬件友好的随机化”**方案，彻底改变了工厂的运作模式。

核心比喻：从“中央厨房”到“分布式微型厨房”

旧模式（中央厨房）：
工厂只有一个巨大的中央厨房，负责生产所有原料，然后通过长长的传送带（布线）送到各个灶台。
- 缺点： 传送带太长，电线太粗（需要厚金属层），耗电巨大，而且一旦传送带堵塞，整个工厂都得停。
新模式（分布式微型厨房）：
论文建议，在每个灶台旁边都装一个小厨房（微型 PRNG 引擎）。
- 怎么运作？ 客户只寄一个“种子”给工厂。工厂里的每个小厨房都拿着这个种子，加上自己独有的“标签”（比如：我是第 3 号灶台，我要做第 5 号原料），然后独立地、并行地开始生产原料。
- 好处 1：省电线（低布线成本）。 小厨房就在灶台旁边，原料直接递过去，不需要拉长电线。这就省去了昂贵的“厚金属层”布线，像把长距离输电变成了“伸手递东西”。
- 好处 2：省电。 以前长距离传输数据要消耗大量电力（论文说能省下几十瓦，相当于少开几盏大灯），现在几乎不耗电。
- 好处 3：随叫随到（随机访问）。 以前必须按顺序生产，现在灶台 100 号可以直接喊：“我要第 50 号原料！”，它的小厨房立刻就能算出来，完全不需要等前面的。这就像你点外卖，以前要按顺序出餐，现在每个厨师都能独立做你的菜，想吃什么立刻就有。

另一个创新：如何保证“变”出来的原料是完美的？

在加密里，原料必须是绝对均匀随机的，不能有任何偏差。

挑战： 用种子“变”原料的过程（拒绝采样）有时候会“失败”（变出来的数字不符合要求，得扔掉重来）。如果工厂不知道什么时候会失败，就没法安排生产计划。
论文的策略：
1. 客户多算一点： 让客户在寄种子之前，先多算几次，确保种子是“好种子”（保证工厂一定能成功变出原料）。这对客户来说只多花了不到 3% 的时间，几乎可以忽略不计。
2. 工厂稳如泰山： 工厂拿到种子后，保证能一次成功，不需要等待，也不需要复杂的排队管理。这让工厂的生产计划变得非常精准、可预测。

3. 总结：这对我们意味着什么？

这篇论文就像给未来的加密工厂做了一次**“装修升级”**：

更省钱： 不需要那么多昂贵的粗电线和厚金属层，芯片制造成本降低了。
更省电： 省去了长距离传输数据的巨大能耗，芯片更凉快，更环保。
更快： 消除了排队等待，工厂可以并行处理更多任务，速度大幅提升。
更灵活： 无论工厂需要哪个原料，都能立刻拿到，不再受限于生产顺序。

一句话总结：
这篇论文通过把“生产随机原料”的任务从“中央集权”变成“分布式自治”，解决了加密硬件中布线太贵、耗电太大、排队太慢的三大难题，让全同态加密技术真正走向大规模实用化成为可能。

论文技术总结：面向 FHE 加速器的硬件友好型随机化方案

1. 研究背景与问题定义

背景：
全同态加密（FHE）技术正逐渐从理论走向实际应用，其核心基于环学习带误差（RLWE）问题。在典型的客户端 - 服务器架构中，客户端需将加密数据（密文）和公钥（如密钥切换密钥 KSK）传输至服务器端的 FHE 加速器（ASIC）。

数据量巨大： 一个标准的 RLWE 密文包含一对多项式 $(b, a)$ ，其中 $a$ 是均匀随机多项式。为了支持高安全性（如 128 位）和自举（Bootstrapping），环维度 $N$ 通常高达 $2^{16}$ ，模数 $Q$ 可达 $2^{1600}$ 。单个多项式大小可达 13MB，而密钥切换密钥（由 $\beta$ 对多项式组成）总大小可达数百 MB 甚至 GB 级别。
传输瓶颈： 传输这些巨大的 $a$ 多项式会消耗大量带宽，成为通信延迟和内存占用的主要瓶颈。

现有方案及其局限性：
目前通用的优化方案是“种子生成法”：客户端仅发送一个小种子，服务器端利用确定性伪随机数生成器（PRNG）在硬件中实时生成 $a$ 。然而，在硬件加速器实现中，这种方法面临三大挑战：

布线成本（Wiring）： 传统的集中式 PRNG 单元需要向分布在芯片各处的并行计算单元（如模乘器）分发数据。随着并行度提高，长距离、高密度的全局布线导致巨大的功耗和金属层资源消耗。
串行依赖与随机访问受限： 基于哈希的扩展输出函数（XOF，如 SHAKE128）通常是串行的。要生成第 $k$ 个输出，必须先计算前 $k-1$ 个输出。这限制了硬件调度的灵活性，无法直接随机访问特定的 RNS（剩余数系统）肢体（limb），除非存储所有中间结果（增加内存开销）。
非确定性延迟： 拒绝采样（Rejection Sampling）过程具有随机性，导致生成样本的耗时不确定，难以在 FHE 编译器中进行静态调度。

2. 方法论与核心设计

本文提出了一种硬件友好的分布式随机化方案，旨在解决上述布线、访问灵活性和调度确定性问题。

2.1 分布式 PRNG 架构

核心思想： 摒弃集中式 PRNG，采用分布式生成策略。
实现方式： 将每个 RNS 肢体（对应一个大模数 $q$ ）划分为 $n_{seg}$ 个段（segments）。每个计算单元组配备一个本地的轻量级 PRNG 引擎。
优势： 数据生成与计算单元物理位置相邻，仅需局部短距离布线，消除了长距离全局布线的功耗和面积开销，无需使用厚金属层。

2.2 域分离与随机访问机制

为了克服 XOF 的串行依赖并支持随机访问，方案引入了双重域分离（Domain Separation）：

输入构造： PRNG 的输入字符串由 Seed || q || id_seg 拼接而成。
- Seed：公共种子。
- q：当前处理的 RNS 模数（肢体索引）。
- id_seg：段索引。
效果： 由于输入包含模数 $q$ 和段索引，加速器可以直接请求生成任意特定模数下的任意特定段，而无需按顺序生成之前的所有数据。这实现了真正的随机访问（Random-Access）。

2.3 确定性调度与拒绝采样优化

确定性保障： 客户端负责验证种子，确保生成的样本数量满足要求。服务器端加速器被保证能成功生成所需数据，无需处理拒绝采样的失败重试逻辑。
算法流程（Algorithm 1 & 2）：
1. 客户端根据目标模数集合和段大小，计算所需的哈希输入。
2. 利用哈希函数（如 SHAKE128）生成固定长度的比特流。
3. 执行拒绝采样：将比特流切分为 $w$ 位样本，仅接受落在 $[0, q)$ 范围内的样本。
4. 若样本不足，客户端更换种子重试（概率极低），确保服务器端无阻塞。
参数权衡： 通过调整段长度（len）和哈希输出长度，可以在支持更多模数集合（灵活性）与硬件面积/功耗之间取得平衡，同时保证整体生成失败率低于 3%。

3. 关键贡献

消除布线瓶颈： 提出分布式 PRNG 架构，将随机数生成逻辑下沉到计算单元本地，显著降低了芯片内部的全局布线密度和功耗（预计在高吞吐量配置下每芯片节省数十瓦特）。
实现真正的随机访问： 通过基于模数和段索引的域分离，打破了传统哈希 PRNG 的串行依赖，允许加速器按需生成任意 RNS 肢体，无需预生成或存储中间状态。
确定性执行模型： 将种子验证和失败重试移至客户端，使服务器端加速器获得确定性的执行轮廓（Deterministic Execution Profile），消除了运行时的停顿（Stalls）和气泡，简化了硬件控制逻辑。
低客户端开销： 引入的额外计算（如种子验证）在客户端密钥生成阶段仅增加不到 3% 的开销，且仅发生一次。

4. 实验结果与参数分析

硬件配置示例： 假设芯片尺寸为 15mm x 15mm，包含 16,384 个 32 位模乘器，频率 1GHz。
功耗对比：
- 集中式方案： 数据平均传输距离 7.5mm，带宽密度高，估算布线功耗高达 19.7W。
- 分布式方案： 数据仅在极短距离传输，消除了长距离布线的功耗，且可使用更细间距的导线，无需厚金属层。
参数选择：
- 支持 SHAKE128 和 KangarooTwelve。
- 哈希输出长度固定为 1344 位，生成 42 个 32 位字。
- 限制模数集合仅包含 HWNAF（非相邻形式汉明重量） $\le 5$ 的 NTT 友好素数，以优化模减硬件。
- 在保持 MRP（多剩余多项式）生成失败率 $<3\%$ 的前提下，支持多种模数大小组合，且种子空间（288 位）足以满足安全性要求。

5. 意义与展望

意义：
该方案解决了 FHE 硬件加速器扩展性中的关键工程瓶颈。随着加速倍数的增加，内部通信和布线成本往往成为限制性能的主要因素。本文提出的方法不仅大幅降低了功耗和布线复杂度，还通过随机访问能力提升了硬件调度的灵活性，使得大规模加密应用能够在更低的能耗和硬件成本下运行。

未来工作：

研究更细粒度的拒绝采样技术，利用哈希生成的所有比特以减少浪费。
探索非肢体维度的随机访问（例如，同时生成同一系数索引的不同 RNS 肢体）。
评估其他哈希原语在硬件实现中的效率。

总结：
这是一项针对 FHE 加速器硬件架构的实质性改进，通过算法与硬件的协同设计（Co-design），在保持安全性的前提下，显著提升了系统的能效比和可扩展性，为 FHE 技术的广泛落地提供了重要的基础设施支持。