想象你是一名特工，试图解开一个复杂的谜题，但你只能在拼图块被锁在一个沉重且无法破坏的保险箱内时进行操作。你无法打开保险箱查看拼图块，却仍需重新排列它们以解开谜题。这就是**同态加密（HE）**所面临的挑战：在数据始终保持加密的状态下执行计算。
本文提出了一种全新的、超高效的方法，用于在数据仍锁在保险箱内时，解决一种被称为线性变换（一种在人工智能和神经网络中广泛使用的数学运算）的特定类型谜题。
以下是他们解决方案的分解，采用简单的类比说明：
1. 问题：移动数据的“繁重劳动”
在加密数据的世界中，将一条信息从保险箱内的一个位置移动到另一个位置极其昂贵。这就像试图将一架大钢琴搬上一段楼梯：它需要大量的时间、能量和专用设备（称为“旋转密钥”）。
- 旧方法：为了解开谜题，以往的方法必须将钢琴搬上楼梯数千次。这造成了巨大的交通堵塞，拖慢了整体速度，并需要巨大的仓库（内存）来存储所有密钥和中间步骤。
- 瓶颈：最大的延迟并非来自实际进行数学运算，而是不断往返于“仓库”（片外内存）以获取密钥和数据。这就像一位厨师为每一小撮盐都要跑去杂货店。
2. 解决方案：“三重提升”电梯系统
作者提出了一种名为**三重提升婴儿步 - 巨人步（TH-BSGS）**的新算法。
- “婴儿步 - 巨人步”概念：假设你需要行走 100 英里。与其迈出 100 个微小的步伐，不如迈出 10 个“巨人”步，而每个巨人步中包含 10 个“婴儿”步。这减少了你需要停下来查看地图的总次数。
- “三重提升”创新：该方法的先前版本包含两层这样的步骤。作者意识到，他们可以将“婴儿步”进一步分解为第三层。
- 类比：将“提升”想象为使用起重机吊起沉重的箱子。在旧方法中，每提升一层，你都必须停下来重新整理箱子。新的“三重提升”方法建立了一个系统，允许你一次性提升三层箱子，而无需停下来重新整理。你只需进行一次繁重的工作，数学运算便能顺畅流动。
- 结果：这大幅减少了你需要“移动钢琴”（执行密文旋转）的次数。
3. 硬件：定制的“装配线”
即使有了更好的算法，硬件也需要相应构建。作者设计了一款定制的FPGA 加速器（一种专用计算机芯片）。
- “置换电路”技巧：该过程的主要部分涉及打乱数据（就像重新排列一副扑克牌）。通常，这需要大量的临时存储空间（暂存器）并耗时很长。
- 创新：作者发现了数据打乱的具体模式。他们并未使用杂乱无章的通用打乱机器，而是构建了一条遵循该精确模式的定制传送带。
- 优势：这条定制传送带的速度是先前设计的两倍，所需空间仅为一半，因为它无需停下来将数据存储在临时缓冲区中。
4. 内存优化：“即时”厨房
本文还重新设计了数据路径，以最大限度地减少前往“杂货店”（片外内存）的行程。
- 策略：他们将计算分解为六个不同的阶段。在每个阶段中，他们仅加载所需的内容，在数据位于“柜台”（片上内存）时完成所有工作，然后才进入下一阶段。
- 结果：这防止了系统不断获取数据。与以往最佳设计相比，该方法将从外部仓库获取的数据量减少了2.9 至 4.2 倍。
结论
作者在高端芯片（Xilinx Virtex UltraScale+）上测试了他们的新系统。与针对此任务的最佳现有硬件加速器相比：
- 速度：他们将计算速度提高了5.8 倍（就纯计算时间而言）。
- 效率：他们将对外部内存的数据获取需求降低了2.9 倍。
- 成本：他们在无需比先前最佳设计显著增加硬件资源（芯片和内存）的情况下实现了这一目标。
简而言之，他们找到了一种更聪明的组织工作的方式，并构建了专用工具来执行，将原本缓慢且充满交通堵塞的过程转变为一条高效、高速的流水线。
技术摘要：基于 CKKS 同态加密与硬件加速器的三重提升婴儿步 - 巨人步线性变换
问题陈述
同态加密（HE），特别是 CKKS 方案，支持在加密数据上进行隐私保护计算，这对于医疗诊断、金融分析和基因组测序等应用至关重要。基于 HE 的神经网络和 Transformer 中的一个基本操作是线性变换（HE-LT）。虽然对角线方法通过将矩阵对角线打包进多项式来实现 HE-LT，但对于高维矩阵，它需要数量惊人的密文旋转。这些旋转涉及复杂的自同构和密钥切换操作，导致显著的计算开销和巨大的片外内存访问。现有的硬件加速器，即使是那些利用婴儿步 - 巨人步（BSGS）分解和双重提升技术的加速器，仍然遭受严重的延迟和内存带宽瓶颈，针对典型参数集往往需要数百吉字节的片外数据传输。
方法论
本文提出了一种综合解决方案，同时解决算法复杂度和硬件数据流问题：
三重提升 BSGS（TH-BSGS）算法：
作者通过进一步将“婴儿步”分解为两层，扩展了现有的双重提升 BSGS 算法，构建了一个三层结构（n=n1′n2′n3′）。
- 三重提升： 该技术应用于所有三层旋转。通过重新排序计算并将逆自同构应用于切换密钥，该算法确保每一层内的所有内部旋转仅执行一次
Decompose 操作（一个昂贵的密钥切换步骤）。
- 延迟模降（ModDown）： 与之前的提升方法类似，
ModDown 操作被延迟并合并。在 proposed 设计中，ModDown 仅应用于累加和，而非中间乘积，从而显著减少了所需的模运算数量。
- 权衡灵活性： 通过调整分解因子 n1′,n2′,n3′，该算法允许在所需切换密钥数量（内存）和计算复杂度之间进行灵活权衡。
内存优化的数据路径：
为了解决由片外内存访问引起的延迟，TH-BSGS 算法被划分为六个不同的阶段。
- 阶段划分： 算法被重构，使得数据从片外内存读取，处理后的中间结果存储并在片内重用，仅在每个阶段结束时写回。
- 数据重用： 通过精心调度切换密钥和多项式肢（limbs）的加载，该设计最大限度地提高了片内内存的重用率。例如，在中间层，切换密钥被加载到片内内存中，并在多次迭代中重用，以最小化流量。
- 并行度调整： 引入了六个并行度参数（m1 到 m6），以平衡切换密钥、多项式肢和密文的处理，确保设计符合 FPGA 片内内存的约束（例如 Xilinx U280 上的 43 MB）。
硬件加速器架构：
设计了一个高效的基于 FPGA 的加速器来实现所提出的算法。
- 优化的置换电路： 引入了一种新颖的置换电路来实现自同构 ϕr。通过利用 NTT 域中自同构的特定性质以及系数的位反转存储顺序，该设计将多路复用器的数量减少了一半（与现有技术相比），并消除了对暂存内存缓冲器的需求。这将置换操作的延迟降低了一半。
- 模块化组件： 该架构包括支持 NTT、INTT 和系数级运算的处理单元（PE）阵列；用于求和的树形加法器（TA）阵列；以及置换电路（PC）阵列。
主要贡献
- 算法创新： 提出了三重提升 BSGS 算法，该算法进一步分解婴儿步，与双重提升方法相比，减少了密文旋转和
Decompose 操作的数量。
- 数据路径优化： 一种基于阶段的内存优化策略，通过最大化片内数据重用，大幅减少了片外内存流量，该策略专门针对 TH-BSGS 算法的重新排序计算进行了定制。
- 硬件效率： 开发了一种硬件加速器，其简化的置换电路将自同构延迟降低了 50%，并消除了额外的内存缓冲。
实验结果
该设计在 Xilinx Virtex UltraScale+ (U280) 器件上进行了综合，并在三种支持 128 位安全性的不同 HE 参数集（Set-A、Set-B、Set-C）下，与最先进的硬件加速器（包括 FAME、CHAM 以及文献 [25] 中的设计）进行了评估。
- 片外内存访问： 在相同的参数设置下，与最佳 prior 设计（FAME）相比，所提出的设计将片外内存访问减少了 2.9 倍至 4.2 倍。与对角线方法相比，内存访问减少的改进幅度高达 10.6 倍。
- 计算延迟： 与 prior 硬件加速器相比，所提出的加速器实现了 2.9 倍至 10.6 倍 的计算延迟降低。
- 资源利用率： 尽管性能显著提升，该设计在硬件资源需求（LUTs、FFs、DSPs、BRAMs）方面保持与现有解决方案相当或略优。
- 算法比较： 虽然 TH-BSGS 算法与双重提升 BSGS（DH-BSGS）算法相比，将切换密钥的内存需求减少了约 3.65 倍，但由于多项式乘法主导了总复杂度，其整体计算复杂度仍与 DH-BSGS 和 BSGS 相似。
意义
本文声称，所提出的 TH-BSGS 算法及其相关的硬件加速器代表了 HE-LT 效率的重大进步。通过同时解决密钥切换的算法开销和片外内存访问的硬件瓶颈，该设计实现了更快、更具可扩展性的隐私保护线性变换。片外内存流量的减少尤为关键，因为数据传输构成了 HE-LT 操作中延迟的大部分。这项工作表明，进一步分解婴儿步，结合严格的数据路径优化和专用硬件，可以在不增加硬件资源成本的情况下带来显著的性能提升。未来的工作 noted 将专注于针对特定应用进一步优化线性变换。
每周获取最佳 computer science 论文。
受到斯坦福、剑桥和法国科学院研究人员的信赖。
请查收邮箱确认订阅。
出了点问题，再试一次？
无垃圾邮件，随时退订。