Encrypted Vector Similarity Computations Using Partially Homomorphic Encryption: Applications and Performance Analysis
作者: Sefik Serengil, Alper Ozpinar
分类: cs.CR, cs.CV, cs.LG
发布日期: 2025-03-07
💡 一句话要点
利用部分同态加密实现加密向量相似度计算，应用于人脸识别等领域。
🎯 匹配领域: 支柱五：交互与反应 (Interaction & Reaction) 支柱九：具身大模型 (Embodied Foundation Models)
关键词: 同态加密 向量相似度 人脸识别 隐私保护 边缘计算
📋 核心要点
- 现有全同态加密（FHE）计算复杂度高，难以在资源受限的边缘设备上实现高效的加密向量相似度搜索。
- 提出利用部分同态加密（PHE）结合向量预处理，实现加密域的余弦相似度计算，降低计算开销。
- 实验表明，PHE方案在计算速度、密钥/密文大小等方面优于FHE，更适合实际应用场景。
📝 摘要（中文）
本文探讨了使用部分同态加密（PHE）进行加密向量相似度搜索，重点关注人脸识别以及更广泛的应用，如反向图像搜索、推荐引擎和大型语言模型（LLM）。虽然存在全同态加密（FHE），但我们证明了可以使用PHE计算加密的余弦相似度，这提供了一种更实用的替代方案。由于PHE不直接支持余弦相似度，我们提出了一种预先对向量进行归一化的方法，从而能够将点积计算作为代理。我们还应用min-max归一化来处理负维度值。在LFW数据集上的实验使用了DeepFace的FaceNet128d、FaceNet512d和VGG-Face（4096d）模型，采用双塔结构。预加密的嵌入存储在一个塔中，而边缘设备捕获图像，计算嵌入，并通过加法同态加密执行加密-明文点积。我们使用LightPHE实现了这一点，评估了Paillier、Damgard-Jurik和Okamoto-Uchiyama方案，排除了其他方案，因为它们的性能或解密复杂度较高。在80位和112位安全级别（NIST安全直到2030年）的测试中，我们将PHE与FHE（通过TenSEAL）进行了比较，分析了加密、解密、操作时间、余弦相似度损失、密钥/密文大小。结果表明，PHE的计算强度较低，速度更快，并产生更小的密文/密钥，使其非常适合内存受限的环境和实际的隐私保护加密相似度搜索。
🔬 方法详解
问题定义：论文旨在解决在保护用户隐私的前提下，如何高效地进行向量相似度计算的问题。现有方法，特别是基于全同态加密（FHE）的方法，计算开销巨大，难以在资源受限的设备上部署，限制了其在实际场景中的应用。
核心思路：论文的核心思路是利用部分同态加密（PHE）的特性，结合向量预处理技术，将余弦相似度计算转化为可以在加密域高效执行的点积运算。通过预先对向量进行归一化，使得点积运算的结果等价于余弦相似度，从而避免了复杂的除法运算。
技术框架：整体框架采用双塔结构。一个塔存储预先加密的向量嵌入，另一个塔位于边缘设备上，负责捕获图像、计算嵌入并进行加密-明文点积运算。具体流程包括：1) 离线阶段：使用深度学习模型提取向量嵌入，并使用PHE算法对嵌入进行加密；2) 在线阶段：边缘设备捕获图像，提取向量嵌入，并与加密的向量嵌入进行点积运算，得到加密的相似度结果；3) 解密阶段：将加密的相似度结果解密，得到最终的相似度得分。
关键创新：最重要的技术创新点在于将余弦相似度计算转化为加密域的点积运算。通过向量归一化，避免了在加密域进行复杂的除法运算，显著降低了计算复杂度。此外，论文还探索了不同的PHE方案（Paillier、Damgard-Jurik、Okamoto-Uchiyama）在向量相似度计算中的性能表现。
关键设计：论文采用了min-max归一化来处理向量中的负值，确保归一化后的向量元素均为正数。实验中，使用了DeepFace的FaceNet128d、FaceNet512d和VGG-Face（4096d）模型提取人脸特征。评估了80位和112位安全级别下的PHE方案性能，并与FHE方案（TenSEAL）进行了对比。
🖼️ 关键图片
📊 实验亮点
实验结果表明，PHE方案在计算速度、密钥/密文大小等方面显著优于FHE方案。例如，PHE方案的计算速度比FHE方案快几个数量级，并且生成的密钥和密文更小，更适合在资源受限的边缘设备上部署。在LFW数据集上，使用FaceNet128d模型，PHE方案在保证一定安全性的前提下，实现了高效的加密向量相似度计算。
🎯 应用场景
该研究成果可应用于多种需要保护用户隐私的场景，如人脸识别、反向图像搜索、推荐系统和大型语言模型。例如，在人脸识别中，用户的面部特征可以在加密状态下进行比对，避免了敏感信息的泄露。在推荐系统中，用户的偏好可以在加密状态下进行分析，从而提供个性化的推荐服务。
📄 摘要（原文）
This paper explores the use of partially homomorphic encryption (PHE) for encrypted vector similarity search, with a focus on facial recognition and broader applications like reverse image search, recommendation engines, and large language models (LLMs). While fully homomorphic encryption (FHE) exists, we demonstrate that encrypted cosine similarity can be computed using PHE, offering a more practical alternative. Since PHE does not directly support cosine similarity, we propose a method that normalizes vectors in advance, enabling dot product calculations as a proxy. We also apply min-max normalization to handle negative dimension values. Experiments on the Labeled Faces in the Wild (LFW) dataset use DeepFace's FaceNet128d, FaceNet512d, and VGG-Face (4096d) models in a two-tower setup. Pre-encrypted embeddings are stored in one tower, while an edge device captures images, computes embeddings, and performs encrypted-plaintext dot products via additively homomorphic encryption. We implement this with LightPHE, evaluating Paillier, Damgard-Jurik, and Okamoto-Uchiyama schemes, excluding others due to performance or decryption complexity. Tests at 80-bit and 112-bit security (NIST-secure until 2030) compare PHE against FHE (via TenSEAL), analyzing encryption, decryption, operation time, cosine similarity loss, key/ciphertext sizes. Results show PHE is less computationally intensive, faster, and produces smaller ciphertexts/keys, making it well-suited for memory-constrained environments and real-world privacy-preserving encrypted similarity search.