想象一下，你正试图保护一份秘密食谱的安全，同时又要请一位巨大的、动作极快的机器人厨师为你烹饪。你不想让机器人看到食材（你的私密数据），而机器人也不想看到食谱（公司的秘密模型）。通常情况下，为了保持秘密，你必须把食材锁进保险箱，把保险箱送到机器人那里，等待它解锁，进行烹饪，然后再重新锁好。但如果有一种方法，能让你给机器人一个锁着的盒子，而机器人竟然能在不打开盒子的情况下直接在盒子里进行“烹饪”呢？这就是**全同态加密（Fully Homomorphic Encryption, FHE）的魔力。它就像一只特殊的厨房手套，让你可以在食材仍处于密封透明袋中的情况下进行搅拌和切割。问题在于，这种“烹饪”过程极其缓慢且笨拙，尤其是当食谱涉及到从成千上万种选项组成的庞大且落满灰尘的“图书馆”中查找特定食材时。这正是推荐模型（Recommendation Models）**面临的挑战——这些智能算法决定了你接下来该看哪部电影或购买哪件产品。它们依赖于巨大的“嵌入表（embedding tables）”——即通过将像“披萨”或“纽约”这样简单的词汇转化为复杂的数学代码的巨型列表。当这些表格被锁在秘密袋子里时，寻找正确的代码会变成一场缓慢且昂贵的数学噩梦，可能需要耗费数小时。
于是，由纽约大学和 LG Electronics 的研究人员设计的全新解决方案 HE-LRM 应运而生，旨在让这种秘密烹饪变得更快。把旧的方法想象成在秘密图书馆里找一本特定的书，你必须逐一检查每一排书架，即使你只需要其中一本。这既缓慢又浪费能源。研究人员意识到，与其检查整个图书馆，不如将书的索书号分解成更小、更简单的数字（比如将“14”分解为“1”和“4”），并利用这些数字直接跳到正确的位置。他们称之为数字分解（digit decomposition）。通过在客户端（你的一方）发送请求之前先进行这些数学运算，他们避免了在服务端进行沉重且缓慢的计算工作。
此外，他们还想出了如何将多个不同的图书馆打包进一个巨大的、组织有序的仓库中。与其为每一个类别（如“电影”、“地点”和“年龄”）分别发送请求，不如将所有的查找表以对角线形式堆叠在一个巨大的网格中。这样一来，机器人厨师就可以用一次巨大的、并行的“抓取”动作拿走所有需要的食材，而不是进行数十次微小的往返。结果是，该系统比之前的尝试都要快得多。在标准计算机处理器上，他们成功地在约 24 秒内完成了一项健康预测任务的完整私密推荐，并在 228 到 489 秒之间完成了复杂的电影推荐任务。虽然这些时间对于手机上的实时应用来说仍然太长，但研究人员展示了，如果你使用专门为这类数学运算设计的特殊、超高速计算机芯片（GPU 或 ASIC），时间可以缩短到仅几秒钟甚至不到一秒。这表明在不久的将来，我们或许终于能够实现在无需向云端交出任何私密数据的情况下，获得个性化的推荐服务。
技术摘要：HE-LRM
问题陈述
全同态加密（FHE）能够实现针对加密数据的隐私保护神经推理，然而现有方案主要解决的是具有稠密输入（如 CNN、MLP）的模型。深度学习推荐模型（DLRM）提出了一个截然不同的挑战，因为它们依赖于通过大规模嵌入表（embedding tables）处理的大量稀疏类别输入。
在标准的 DLRM 中，稀疏特征通过嵌入表查找被映射为稠密向量。在 FHE 上下文中（特别是在使用 CKKS 方案时），直接索引并非原生支持；仅支持 SIMD 加法、乘法和循环旋转。朴素的加密查找方法面临严重的扩展性问题：
- 通信开销： 对于拥有 k 行的表，其“独热”（one-hot）编码需要一个大小为 k 的向量。对于像 Criteo 这样工业级的规模化数据集（3380 万行），每次推理需要上传超过 1,000 个密文（>1 GiB）。
- 服务端计算成本： 先前的研究（例如 Kim 等人 [10]）试图通过让服务端从加密索引构建独热选择器来减轻上传成本。然而，这需要深层的算术电路（指示函数），这会消耗大量的乘法深度，通常需要昂贵的自举（bootstrapping）操作。
- 内存与结构泄露： 现有的压缩技术通常要求客户端存储学习到的编码映射（这会泄露嵌入相关性），或者导致效率低下的槽位利用率和高内存占用。
方法论：HE-LRM
作者提出了 HE-LRM，这是一个针对 DLRM 推理优化的端到端 FHE 系统。该方案通过三个核心技术创新解决了嵌入查找的瓶颈问题：
1. 基于客户端数字分解的压缩
HE-LRM 没有依赖于服务端构建独热向量或会泄露结构的学习型编码映射，而是采用了一种基于**数字分解（digit decomposition）**的确定性客户端侧压缩技术。
- 机制： 将大小为 k×d 的原始嵌入表分解为 ℓ 个较小的 p×d 表（其中 k≈pℓ）。
- 过程： 客户端将一个类别索引 i 分解为一个基数为 p 的数字元组 (i0,i1,…,iℓ−1)。
- 隐私： 客户端在本地构建这些较小数字的独热编码并对其进行加密。服务端既看不到原始索引，也不需要执行昂贵的同态指示函数。这种压缩是在训练过程中端到端学习的，不会向客户端泄露映射结构。
2. 分块对角线打包策略
DLRM 通常使用多个嵌入表（例如 Criteo 中的 26 个）。HE-LRM 引入了分块对角线打包策略来同时处理这些表。
- 实现： 多个嵌入表被对角线连接成一个大的权重矩阵。
- 益处： 这允许客户端将所有特征的独热编码连接成单个向量。随后，服务端可以执行单次**大步小步（BSGS）**矩阵-向量乘法，以并行方式检索所有表的嵌入。这最大化了密文槽位的利用率，并避免了顺序处理表格带来的开销。
3. 优化的线性变换
系统利用**双提升 BSGS（double-hoisted BSGS）**算法进行矩阵-向量乘法。
- 不同于以往需要为嵌入向量的每个维度进行单独旋转（这会消耗额外的乘法层级）的“表乘法”（Table-Mult）方法，BSGS 方法将查找视为标准的线性变换。
- 这把操作简化为单个乘法层级，消除了在查找阶段进行中间自举的需求。
核心贡献
- 首个端到端 FHE DLRM： HE-LRM 是第一个支持 FHE 下 DLRM 中稠密和稀疏特征的系统，并在 UCI 心脏病和 Criteo 数据集上得到了验证。
- 56 倍加速： 提出的客户端数字分解和 BSGS 查找策略在大型嵌入维度（768）下，比最先进的方案（CodedHeLUT）实现了 56 倍的加速。这是通过避免服务端指示函数、减少乘法深度消耗（从约 10 层降至 1 层）以及消除查找阶段的自举需求实现的。
- 并行多表查找： 分块对角线打包策略实现了跨多个嵌入表的并行高效查找，与单独处理表格相比，显著降低了通信和计算开销。
- 清晰的泄露剖面： 该方法遵循半诚实威胁模型，即客户端仅知道输入维度和表的大小，但无法获知嵌入值、相关性或模型参数。
实验结果
作者使用开源的 Orion FHE 框架在单线程 CPU（Intel Xeon Gold 5218）上评估了 HE-LRM。
- UCI 心脏病数据集： 实现了 24 秒 的端到端推理延迟。
- Criteo 数据集： 根据压缩率的不同（范围从 10× 到 105×），实现了 228 至 489 秒 的延迟。
- 高度压缩的模型（≈103× 至 105×）显示出相似的延迟（约 230 秒），因为与网络的其余部分相比，嵌入查找时间变得微不足道（3–5 秒），且 BSGS 操作可以在单个密文上执行。
- 压缩程度较低的模型需要更多密文，从而增加了矩阵-向量乘法的延迟。
- 硬件预测：
- GPU： 使用 Cheddar 加速器的预测表明，相比 CPU 有 ~200 倍的加速，将 Criteo 推理缩短至约 1 秒。
- ASIC： 使用 Osiris 成本模型的预测表明，对于压缩模型，可以实现亚秒级延迟（~0.037 秒）。
重要性与主张
论文声称 HE-LRM 弥补了隐私计算中的一个关键空白，证明了隐私保护推荐系统正趋于实际部署。
- 可扩展性： 该工作证明了 FHE 中的“嵌入瓶颈”可以在不牺牲隐私或不需要客户端持有模型权重的情况下得到解决。
- 系统效率： 通过将索引编码的复杂性转移到客户端（通过确定性分解）并在服务端利用高效的线性代数（BSGS），该系统避免了与朴素独热编码相关的极高自举成本和巨大的通信开销。
- 更广泛的适用性： 作者指出，这种加密嵌入查找原语不仅限于 DLRM，也适用于基于 Transformer 的模型，这表明它是一种可用于未来隐私推理系统的可复用抽象。
作者对目前的 CPU 性能保持谦逊（对于大型模型需要数分钟），强调在 GPU 和 ASIC 硬件上展示的加速对于实现现实世界的生产部署是必要的。
每周获取最佳 computer science 论文。
受到斯坦福、剑桥和法国科学院研究人员的信赖。
请查收邮箱确认订阅。
出了点问题，再试一次？
无垃圾邮件，随时退订。