Spruce: Scalable Private Outsourced Retrieval Using Compact Embeddings

📄 arXiv: 2609.03376v1 📥 PDF

作者: Peichun Hua, Yunming Xiao

分类: cs.CR, cs.IR, cs.LG

发布日期: 2026-09-03

备注: 22 pages, 10 tables, 6 figures

💡 一句话要点

提出Spruce以解决安全外包检索中的效率问题

🎯 匹配领域: 支柱一：机器人控制 (Robot Control)

关键词: 私有检索 外包计算 加密协议 紧凑编码 多方计算 检索效率 数据安全

📋 核心要点

  1. 现有方法在大规模文档检索中面临效率低下的问题，尤其是在加密保护下，查询的计算和通信成本极高。
  2. Spruce通过学习紧凑的二进制编码和优化的加密协议，提升了检索效率，同时保持了检索质量。
  3. 在多个语料库的实验中，Spruce的检索速度比现有方法快4.8到6.7倍，且保留了93.9%到97.3%的检索质量。

📝 摘要（中文）

检索增强生成（RAG）已成为大规模文档集合的标准构建模块，但在将向量索引外包给不可信云时，组织面临着保护专有语料和用户查询的挑战。加密保护在大规模语料中计算、相关随机性和通信量随之增加，导致现有安全实现效率低下。本文提出Spruce（可扩展私有外包检索），通过与加密协议共同设计表示，学习紧凑的二进制编码，替代全精度重排序的评分，显著提高检索效率。实验表明，Spruce在多个语料库上保持了原始搜索质量，并在速度上实现了显著提升。

🔬 方法详解

问题定义：本文旨在解决在不可信云环境中进行大规模文档检索时，如何高效且安全地处理查询的问题。现有方法在加密保护下，计算和通信成本过高，导致效率低下。

核心思路：Spruce的核心思路是通过与加密协议共同设计紧凑的二进制编码，替代传统的全精度重排序评分，利用Hamming距离计算提高检索效率。

技术框架：Spruce的整体架构包括两个主要模块：紧凑编码学习模块和基于多方计算的检索模块。前者负责生成紧凑的二进制表示，后者则执行安全的检索操作。

关键创新：Spruce的主要创新在于其固定半径协议，避免了多轮候选选择，同时实现了私有集群修剪，显著减少了计算量。与现有方法相比，Spruce在保持检索质量的同时，提升了检索速度。

关键设计：Spruce在参数设置上进行了优化，采用了高效的Hamming距离计算，并设计了一种单核操作的经销商，消除了云端OT预处理瓶颈。

🖼️ 关键图片

fig_0
img_1
img_2

📊 实验亮点

Spruce在多个语料库上的实验结果显示，检索速度比现有最优方法快4.8到6.7倍，完全扫描的时间为0.21到2.97秒，私有修剪的速度提升达到13.1到22.9倍，保留93.9%到97.3%的检索质量，展示了其在效率和质量上的显著优势。

🎯 应用场景

Spruce的研究成果在多个领域具有广泛的应用潜力，尤其是在需要保护用户隐私和数据安全的场景，如金融、医疗和法律文档检索等。通过提高检索效率，Spruce能够帮助组织在不牺牲安全性的前提下，快速获取所需信息，提升决策效率。

📄 摘要（原文）

Retrieval-Augmented Generation (RAG) has made dense retrieval over large document collections a standard building block. Organizations increasingly outsource vector indexes to untrusted clouds, exposing proprietary corpora and user queries. Cryptographic protection is challenging because each query searches corpus-scale state, causing computation, correlated randomness, and communication to grow with the corpus. At million-document scale, a naive secure implementation takes minutes and about 90 GB of communication per query. Even recent optimized systems require 10--22 seconds. We propose Spruce (Scalable Private Outsourced Retrieval Using Compact Embeddings), which co-designs representations with the cryptographic protocol. Spruce learns compact binary codes that preserve candidates for full-precision reranking, replacing corpus-wide embedding scoring with efficient Hamming-distance computation under two-server multi-party computation (MPC). A corpus-calibrated fixed-radius protocol avoids multi-round candidate selection while preserving retrieval quality. Spruce also provides private cluster pruning, which trades minor quality loss for substantially less computation, and a one-core owner-operated dealer that removes cloud OT preprocessing bottlenecks. Across four corpora containing 383K--5.42M documents, Spruce preserves the original search quality with median candidate sets of only 382--1,952. At 10 Gbps inter-server bandwidth, full scans take 0.21--2.97 seconds, $4.8$--$6.7\times$ faster than the closest measured prior work. Private pruning takes 0.06--1.09 seconds, achieves $13.1$--$22.9\times$ speedups, and retains $93.9\%$--$97.3\%$ of full-float NDCG. On the largest corpus, pruning and the dealer jointly improve sustained throughput by $31.5\times$ at 1 Gbps per link.