该论文针对隐私保护推理中的嵌入查找问题，提出了一种基于全同态加密（FHE）的私有嵌入查找方法。在自然语言处理和推荐模型中，模型首先将离散的客户端输入映射为嵌入向量，而输入可能包含敏感信息，因此需要保护嵌入步骤的隐私。FHE允许对加密数据进行推理，但将嵌入查找从简单的表访问变为同态计算。为保持嵌入表在服务端且避免客户端传输加密的嵌入向量，该工作聚焦于服务端查找：客户端仅发送一个小的加密索引。先前的工作（ICML 2024）首先从加密索引构建一个独热向量，然后与嵌入表相乘，而独热向量的生成是主要计算开销。基于独热向量的方法在FHE中成本高昂：它对每个坐标进行等式测试来构建p维选择向量，需要O(p log p)次同态操作。该论文的关键观察是，私有嵌入查找只需要加密索引的线性无关表示，而非独热基向量。基于此，作者提出了独立向量估计（IVE）。IVE不构建独热向量，而是构造一个基于单个加密值的连续幂组成的线性无关向量，将向量生成成本降低到O(p)。然后通过预计算基变换恢复相同的嵌入向量，并使用正交离散余弦变换来减轻误差放大。实现表明，IVE相对于先前方法将摊销查找时间提高了最多78.4倍。进一步，论文评估了其在端到端加密FastText推理中的影响，其中嵌入查找是该浅层模型的主要成本。在Enron-Spam数据集上，用IVE替换独热生成后，向量生成在加密推理时间中的占比从99.6%降至66.3%。这项工作主要面向从事隐私保护机器学习和同态加密优化的研究人员。