隐私向量检索不再随库规模线性变慢：HNSecW把在线搜索压到对数时间，十亿级数据上仍保住召回
核心概要
在查询与数据库双方都需保密的对称隐私场景下，HNSecW把基于HNSW图索引的近似最近邻搜索改造成可在安全多方计算中执行的全数据无关流程，使单次查询的在线通信与本地计算达到对数复杂度。此前同类协议多采用聚类式流程，在线通信随数据库规模线性增长。在百万到十亿级基准上，HNSecW保持与明文HNSW相当的召回，并在广域网上相对2PC PANTHER取得最高数量级的端到端加速。
深度剖析
近似最近邻搜索现在可以在查询和数据库互为秘密的条件下，以随数据库规模对数增长的在线代价完成，而不再随库规模线性增长。 此前最接近的MPC方案SANNS与PANTHER走聚类路线，先把数据库分成若干簇再检索相关簇，在线通信随数据库规模线性增长，在MPC下每次额外的向量访问都带来沉重通信。 在SIFT-1M、GIST-1M、DEEP-100M、BIGANN-1B等基准上，HNSecW在广域网2PC配置下相对PANTHER取得最高数量级的端到端延迟加速，并减少最高数量级的通信量。
搜索过程被改造成不依赖私有输入的执行流程：每层走固定步数，候选集、结果集和已访问集都变成定长数组并按固定规则更新。 原版HNSW的停止条件、集合大小和访问地址都随查询与数据变化，直接放进MPC会泄露信息；通用做法是套用分布式ORAM隐藏访问，但每次访问都要付出与库规模相关的代价。 做法是离线随机重排图与向量表，并为每层复制一份独立重排的向量表，使每次访问的物理地址互不重复；在百万到十亿级、维度从数十到上千的十个基准数据集上完成了评估。
多查询与批量查询各有对应扩展：顺序查询用跨查询缓存复用已取过的节点和向量，批量查询则让所有查询共享取回的向量并并行推进。 若沿用单查询方案，每个查询后都要重新打乱表，在线延迟无法接受；顺序多查询的摊还代价为对数级，批量协议把关键路径进一步压到对数级。 在广域网上扫描查询数量时，摊还延迟随查询数增加而下降并趋近在线部分的下限，HNSecW在摊还掉离线开销后低于PANTHER，四个数据集呈现同一趋势。
启示与展望
评估覆盖SIFT-1M、GIST-1M、DEEP-100M、BIGANN-1B等十个百万到十亿级数据集，维度从数十到上千，采用半诚实2PC（ABY）与3PC（MP-SPDZ）两种配置，并在局域网与广域网两种网络条件下测量。索引由数据库所有者在线下本地构建，协议面向查询与数据库双方均需保密的对称隐私场景。
固定步数上界来自对HNSW终止行为的经验标定，而非最坏情况的理论保证；HNSW在任意数据上已知的渐近界仍为线性。批量协议的关键路径分析依赖扩展版本中的证明。索引构建与动态图更新尚未纳入安全协议，是作者列出的后续方向。