💻 computer science

Private Embedding Lookup with Encrypted Compact Queries under Fully Homomorphic Encryption

本文提出了独立向量评估（Independent Vector Evaluation, IVE），这是一种在全同态加密下进行隐私嵌入查找的新方法，它通过使用线性无关表示取代了高昂的独热向量生成，从而在摊还查找时间上实现了高达 78.4 倍的加速。

原作者： Daehyun Jang, Jaehee Kang, Hanee Rhee, Jung Hee Cheon

发布于 2026-06-03

📖 1 分钟阅读☕ 轻松阅读

CC BY 4.0

原作者： Daehyun Jang, Jaehee Kang, Hanee Rhee, Jung Hee Cheon

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

想象一下，你拥有一个存储在巨型服务器上的庞大秘密图书馆（即嵌入表/embedding table）。其中的每一本书都代表一个特定的词汇或概念，而每本书内部都包含一个独特的“指纹”（即嵌入向量/embedding vector），这能帮助计算机理解该词的含义。

通常情况下，当你想要向服务器提问时，你会发送一个词。服务器会在它的图书馆中查找该词，提取出它的指纹，然后利用它来给你答案。

隐私问题：
你不希望服务器知道你询问的是哪个词。也许你正在询问某种医疗症状、财务秘密或敏感信息。如果你直接发送这个词，服务器就会看到它。但如果你发送一个加密代码，服务器又无法读取它来找到对应的书。

旧方法（“独热编码/One-Hot”法）：
过去，为了保持你的问题具有私密性，你必须发送一个特殊的加密列表。想象一下这个列表在图书馆中每一个词的位置都有一个槽位（数以百万计的槽位）。你对你所选词汇所在的那个槽位进行加密并标记为“1”，而在其他所有位置标记为“0”。

问题所在： 服务器必须检查每一个槽位，才能找到那个“1”。这就像服务器必须走遍图书馆的每一个过道，检查每一本书，仅仅为了找到你想要的那个。这需要耗费大量的时间和计算能力，使得整个过程非常缓慢。

新方法（IVE - 独立向量评估/Independent Vector Evaluation）：
这篇论文提出了一种聪明的捷径。作者意识到，服务器实际上并不需要那个特定的列表，它只需要某种能指向正确书籍的独特代码，只要服务器知道如何将该代码转换回正确的指纹即可。

可以这样理解：

旧方法： 你发送了一张地图，上面有一个特定的房子被标上了巨大的红“X”，而其他地方都是空白。服务器必须扫描整张地图来寻找这个“X”。
新方法 (IVE)： 你发送了一组简单的坐标（比如“左转，然后走3个街区”）。服务器拥有一种秘密公式（一种基变换/change of basis），能瞬间将这些坐标转化为你想要的那栋房子的精确地址。

它是如何运作的（魔术技巧）：

秘密代码： 客户端发送的不是“1和0”的列表，而是一个紧凑的加密数字。
数学魔法： 服务器使用一种被称为离散余弦变换 (DCT) 的数学工具。你可以把它看作是一个特殊的翻译器。它通过简单的数学运算（数值的幂），将你简单的加密数字快速转化为一个独特的“指纹”代码，而不是进行缓慢、沉重的检查。
转换过程： 服务器拥有一个预先计算好的“字典”（基变换矩阵），它知道如何将你的新“指纹”代码转换回旧方法原本会找到的那个精确的图书指纹。

为什么这很重要：

速度： 旧方法像是走遍每一个过道；而新方法则像是使用 GPS。论文显示，这种方法使查找速度提升了高达 78 倍。
效率： 它节省了大量的计算机能量。在测试中，仅用于“寻找书籍”的时间占比从总时间的 99.6% 降至了 66.3%。
隐私： 服务器仍然无法得知你的具体词汇，但它获取答案的速度更快了。

简而言之：
作者找到了一种方法，让服务器不再需要进行一百万次微小的检查来寻找你的秘密词汇。相反，他们给了它一个简单的加密线索和一个神奇的翻译密钥。这使得服务器几乎可以瞬间找到所需的信息，在保护你的秘密的同时，不会让计算机等待太久。

技术摘要：基于全同态加密的私密嵌入查找与紧凑查询

问题陈述

在利用全同态加密（FHE）进行隐私保护机器学习（PPML）的过程中，对于依赖离散输入的模型（如自然语言处理 NLP 和推荐系统），其推理过程存在一个关键瓶颈。这些模型通常以**嵌入层（embedding layer）**作为起始，将离散索引（例如词标记/token）映射为连续向量。

在 FHE 环境下，服务器无法根据加密索引进行标准的内存访问，因此必须通过同态算术来实现查找。现有方法面临以下权衡：

客户端查找： 客户端发送加密的嵌入向量。这会导致与嵌入维度 ( $d$ ) 成正比的巨大通信开销，对于大型表格（如拥有 190 万个标记的 GloVe）而言是难以承受的。
基于独热码（One-Hot）生成的服务端查找： 客户端发送紧凑的加密标量索引。服务器必须同态地构建一个独热向量来选择嵌入。前人的工作（Kim 等人，ICML 2024）通过使用加密指示函数（EIF）实现了这一点，但这需要 $O(p \log p)$ 次同态操作（其中 $p$ 是表格大小），消耗了大量的乘法深度，并成为了推理流水线中的主要成本。

本研究的目标是实现私密嵌入查找（Private Embedding Lookup, PEL），既能保持紧凑的客户端通信（仅发送标量索引），又能最小化服务端的同态计算成本，避免昂贵的独热码生成步骤。

方法论：独立向量评估（IVE）

作者提出了独立向量评估（Independent Vector Evaluation, IVE），该方法完全绕过了独热向量的构建过程。

核心洞察

服务器并不严格需要一个独热向量 ( $e_j$ ) 来检索嵌入 $M_j$ 。它只需要一个在不同索引之间具有线性无关性的索引 $j$ 的表示。如果一组向量 $\{v_j\}$ 是线性无关的，则存在一个基变换矩阵 $L$ ，使得 $L v_j = e_j$ 。因此，嵌入检索可以重写为：
$M_j = M e_j = M (L v_j) = (M L) v_j$
由于 $M$ 和 $L$ 在明文状态下是已知的，服务器可以预计算矩阵 $M' = ML $。随后的在线任务从生成独热向量转变为同态地评估向量$ v_j$。

向量构建与稳定性

为了确保在支持近似算术的 CKKS 方案下的效率和数值稳定性：

效率： 向量 $v_j$ 使用单个加密值 $\alpha_j$ 的连续幂次进行构建。这使得服务器能够使用标准算术操作（乘法）来生成向量分量，而不是复杂的等值测试。
稳定性： 为了防止基变换过程中的误差放大，矩阵 $L$ 必须是良置的（理想情况下是正交的）。作者利用了**离散余弦变换（DCT）**矩阵。通过使用单位根并分离实部和虚部，他们构建了一个与 CKKS 复数算术能力相匹配的正交基。

算法流程

客户端： 将索引 $j$ 加密为值 $\alpha_j$ （由单位根导出），并将其作为紧凑的标量查询进行传输。
服务端（IVE 阶段）：
- 接收加密的 $\alpha_j$ 。
- 使用乘法树（对数深度）计算幂次 $\alpha_j^0, \alpha_j^1, \dots, \alpha_j^{p/2}$ 。
- 通过共轭运算分离实部和虚部，从而形成向量 $v_j$ 。
- 此过程需要 $O(p)$ 次同态操作，较之于生成独热码所需的 $O(p \log p)$ 有显著降低。
服务端（PCMM 阶段）：
- 在预计算矩阵 $M' = ML $与生成的向量$ v_j$ 之间执行明文-密文矩阵乘法（PCMM）。
- 由此产生加密的嵌入向量。

主要贡献

独立向量评估（IVE）： 一种新颖的算法，用评估线性无关向量族取代了加密独热码生成。它将向量生成的复杂度从 $O(p \log p)$ 降低到 $O(p)$ 同态操作。
基于 DCT 的正交基： 通过使用 DCT 正交矩阵实例化 IVE，确保了数值稳定性，减轻了 CKKS 近似在执行基变换时固有的误差放大问题。
集成的 PEL 流水线： 作者将 IVE 与 PCMM 集成，以高效处理批处理查询。该流水线支持同时处理多个标记查询，通过 CKKS SIMD 插槽实现成本摊销。
端到端实现： 该方法在类 FastText 的文本分类流水线中得到了实现，证明了其在实际、隐私敏感的推理任务中的可行性。

实验结果

作者使用三个嵌入数据集（GloVe.6B.50d、GloVe.42B.300d 和 GPT-2）以及在 Enron-Spam 数据集上的端到端 FastText 推理，评估了 IVE-PEL 相对于先前最先进技术（Kim 等人）的表现。

向量生成加速： IVE-PEL 显著缩短了向量生成的时间。对于子表大小 $\log p = 10$ 的情况，在 GloVe.6B.50d 上，向量生成时间从约 424 ms（Kim 等人）降至约 3.15 ms（IVE-PEL），在该特定阶段实现了 134.6 倍的加速。
总流水线加速： 根据数据集和嵌入维度的不同，摊销后的查找时间提升了 18.5 倍至 78.4 倍。最大的增益出现在向量生成成为主要成本的场景中。
乘法深度： IVE-PEL 消耗的乘法深度约为独热码生成方法所需的 1/3，这允许使用更大的子表规模和更高的压缩质量，而不会耗尽 CKKS 的噪声预算。
端到端影响： 在 Enron-Spam 分类任务中，使用 IVE 替代独热码方法后，向量生成在总加密推理时间中的占比从 99.6% 降至 66.3%，大幅降低了整体延迟。

意义与主张

论文声称 IVE-PEL 解决了私密嵌入查找中的“缺失设计点”：即在实现紧凑客户端通信（标量索引）的同时，避免了高昂的服务端同态独热码生成成本。

通过将检索过程与对独热基的需求解耦，作者证明了私密嵌入查找可以使其适用于轻量级客户端和大规模模型。结果表明，IVE-PEL 使服务端嵌入成为一种可行的替代方案，能够在不牺牲用户输入索引机密性的情况下，为 NLP 和推荐模型提供高效的隐私保护推理。该方法在大幅提高计算效率的同时，保持了底层模型的准确性（如 IMDB 情感分类和垃圾邮件检测结果所示）。