HNSecW: A Logarithmic-Time MPC Protocol for Approximate Nearest Neighbor Search

1 INTRODUCTION

• Symmetric privacy protects both the querier’s query and the database owner’s data, unlike plaintext-query or data-disclosure approaches.The paper motivates this setting with applications such as private healthcare and threat-intelligence searches.Source: §1 · p. 1
• MPC ANN faces costly vector accesses and data-dependent stopping and memory-access patterns that are difficult to make oblivious efficiently.The cited discussion notes that naive ORAM-based hiding incurs prohibitive communication overhead.Source: §1 · p. 2

1.1 Our Results

• HNSecW redesigns HNSW with fixed-bound, data-independent control flow and fixed-size arrays supporting oblivious updates.This is the paper’s approach to making the search logic and data structures oblivious.Source: §1.1 · p. 2
• Offline reshuffling and partial database duplication provide O(1) online overhead per graph-index and vector access, with at most 2× more vector storage.For sequential queries, double-visited structures reuse earlier graph-node and vector accesses without additional online reshuffling.Source: §1.1 · p. 2
• On large-scale ANN benchmarks, HNSecW reaches recall over 0.9, matching the state-of-the-art plaintext ANN algorithm; at the same target recall, it achieves up to 22× WAN speedup and 46× less communication than 2PC PANTHER.Source: §1.1 · p. 2
• The protocol extends to U sequential queries at amortized O(U log N) cost and batch queries with critical-path length O(log^2 U + log N).The batch protocol processes U queries simultaneously; the sequential protocol shares one offline reshuffle.Source: §1.1 · p. 2

2.1 Notation

• The notation defines a dataset of N vectors in R^d, with v[j] denoting coordinate j of vector v.Source: §2.1 · p. 3

2.2 𝑘-Nearest Neighbor Search

• Linear scan computes distances to all N vectors, while graph-based search greedily traverses nearby nodes; high-dimensional Delaunay graphs can become impractical.ANN relaxes exact nearest-neighbor retrieval to meet a target recall, and HNSW is cited as a state-of-the-art method for high-dimensional data.Source: §2.2 · p. 3, §2.3 · p. 3

2.3 Approximate 𝑘-NN and Hierarchical Navigable Small World

• HNSW uses nested graph layers, with sparse upper layers for coarse navigation and denser lower layers for refinement; each layer maintains candidate, result, and visited sets.Search proceeds from an upper-layer entry point toward lower layers, returning neighbors from visited nodes.Source: §2.3 · p. 3

2.4 Secure Multi-Party Computation

• MPC jointly computes over secret-shared inputs, and oblivious execution requires fixed operation sequences, fixed-size data structures, and indistinguishable address sequences.The paper treats MPC protocols as black boxes and describes computation over secret shares.Source: §2.4 · p. 4
• Generic DORAM hides secret-indexed array accesses but retains O(N) computation and stateful sequential access, motivating a specialized oblivious-access algorithm.The paper distinguishes symmetric MPC from client-server, storage-outsourcing, and query-private search models.Source: §2.4 · p. 4

3 SYSTEM OVERVIEW

• The database owner holds the private vector dataset and HNSW graph, the querier holds the private query, and MPC servers jointly execute the search.The threat model assumes a semi-honest PPT adversary corrupting at most t MPC servers and one or both input parties; the protocol claims simulation-based security.Source: §3 · p. 4, §3.1 · p. 4

3.1 Threat Model

• The functionality protects query and database privacy while returning the top-k result vectors to the querier and preserving correctness.The querier and servers learn nothing about the query, dataset, or graph beyond what the public parameters and output imply.Source: §3.1 · p. 5

3.2 Single-Query

• Single-query HNSW traversal hides access patterns through oblivious fixed-size search state, fixed iteration bounds, monotonic candidate/result sets, and independently shuffled per-layer tables.The fixed bound is derived from HNSW stopping behavior; the authors report negligible recall loss. Fixed-size arrays use oblivious sorting and tail truncation.Source: §3.2 · p. 5

3.3 Multiple-Query

• Two global visited structures cache graph neighbor lists and vectors across queries, so underlying shuffled tables are accessed at most once globally.Subsequent queries scan the cache and use a real or dummy access step, avoiding per-query online reshuffling.Source: §3.3 · p. 5

3.4 Parallel-Enhanced Batch Model

• Batch processing uses synchronized iterations and oblivious duplicate removal to reach circuit depth O(log2 U + log N), rather than the sequential extension’s O(U).It evaluates accessed vectors against the batch’s queries, avoiding a massive cache; extra evaluations do not affect correctness.Source: §3.4 · p. 5

3.5 Implementation & Experiment Summary

• Up to 22× end-to-end latency and 46× communication improvement over existing work on WAN 2PC; Recall@k≥0.9 for at least 95% of queries across the evaluated k values.The evaluation covers 10 ANN benchmarks, with N from 60K to 1B, in LAN and WAN settings.Source: §3.5 · p. 6

4.1 Making Logic Flow Oblivious

• ef(0) = k + 10 covers at least 95% of tests for all k ≥ 5 across the evaluated datasets.The setting follows tests where ef* is the smallest base-layer value achieving at least 90% recall.Source: §4.1 · p. 6
• Upper-layer residual steps are bounded by a constant, but base-layer residuals are substantially larger, motivating a separate base-layer bound.The authors note that termination-strategy design remains active research, while logarithmic growth in search steps preserves the complexity guarantee.Source: §4.1 · p. 6
• The protocol fixes search steps at 8 per upper layer and ⌈log2(N·d/M)⌉ + ef(0) + 7 at the base layer, continuing with dummy nodes when needed.This makes execution data-independent, with O(1) steps per upper layer and O(log(N·d/M)) at the base layer.Source: §4.1 · p. 7

4.2 Making Data Structures Oblivious

• Oblivious W uses insertion of all M elements followed by sorting and truncation; V becomes a fixed-growth list, and C a fixed-length array with oblivious updates.The visited list permits duplicates, while the candidate array retains the top T entries after sorting.Source: §4.2 · p. 7

4.3 Making Access Patterns Oblivious

• Offline reshuffling anonymizes addresses, while independently reshuffled per-layer vector tables prevent repeated physical vector accesses across layers.Graph tables are also independently reshuffled by layer, so revisiting a logical node in another layer reads unrelated locations.Source: §4.3 · pp. 7–8

4.4 Put It All Together

• The complete protocol secret-shares padded per-layer graph and vector tables, and fixed public parameters keep the logic flow and update schedule independent of private inputs.The security sketch states that each lookup accesses a distinct physical address, yielding a random sequence of distinct addresses.Source: §4.4 · p. 8, §4.4.1 · p. 8

4.4.2 Complexity Analysis.

• O(kd + k^2 log2 k + d log N) communication and local computation bound a single oblivious HNSW query.The analysis derives the base-layer and upper-layer costs for fixed public parameters.Source: §4.4.2 · p. 8

5 MULTIPLE QUERY PROTOCOL

• A naive approach would reshuffle after each query, so the protocol instead shares one offline reshuffle and reuses cached accesses.Per-query online reshuffling is described as impractical because of its latency.Source: §5 · pp. 8–9

5.1 Double Visitor Arrays

• A single global visited set would make search incorrect when queries have overlapping paths, motivating separate graph-side and vector-side caches..Source: §5.1 · p. 9
• Global graph and vector caches retain previously accessed node information and vector contents for later queries.Each lookup follows a fixed schedule, using a real or dummy access depending on whether the item is cached.Source: §5.1 · p. 9

5.1.1 Security Sketch.

• Fixed schedules hide cache hits, and accesses to real and dummy nodes remain non-repetitive after graph reshuffling.The security sketch states that the vector accesses are likewise non-repetitive and data-anonymized.Source: §5.1.1 · p. 10

5.1.2 Complexity Analysis.

• Total communication and local computation are O(Uk(d + k log^2 k + Uk) + (Ud + U^2) log N).The base layer costs O(Ukd + Uk^2 log^2 k + U^2k^2); the O(log N) non-base layers cost O((Ud + U^2) log N).Source: §5.1.2 · p. 10

6 BATCH QUERY PROTOCOL IN PARALLEL

• The batch protocol reduces round complexity from O(U) for sequential queries to O(log^2 U) by processing U queries in parallel.Source: §6 · p. 10
• Each iteration deduplicates queries’ nearest candidates before issuing distinct graph accesses, then deduplicates returned neighbor IDs before fetching vectors.Fetched vectors are shared across queries, while each query updates its own candidate and result sets.Source: §6 · p. 10
• Each query evaluates distances to all U·M fetched vectors, and two oblivious sorts of O(U) elements set the per-iteration round cost at O(log^2 U).Source: §6 · p. 10

7.1 Experimental Setup

• The evaluated datasets span N from 6×10^4 to 10^9, dimensions from 96 to 960, and both ℓ2 and cosine metrics.Experiments use semi-honest 2PC and 3PC; the main text reports four representative datasets from a set of ten.Source: §7.1 · p. 10

7.2 Search Accuracy and RAG Quality

• Recall ≥0.9 for at least 95% of queries across datasets and k; HNSecW visits 8×–44× fewer database vectors than PANTHER as N grows from 10^6 to 10^8.The reported 95th-percentile recall rises from approximately 0.9 at k=10 to approximately 0.95 at k=100.Source: Figure 6 · p. 11, §7.2 · p. 11

7.3.1 Single-Query Scenario.

• At matched recall, HNSecW’s WAN 2PC curve is below PANTHER’s across the tested ef(0) sweep on every dataset where PANTHER runs.The sweep covers ef(0) values from k+1 to k+50.Source: Figure 8 · p. 11, §7.3.1 · p. 12
• 4–22× faster than PANTHER on WAN in 2PC and 111×–1.6k× faster than SORT in 3PC; communication is reduced 7–46× and 185–617×, respectively.The PANTHER comparison excludes BIGANN-1B, where the existing DORAM cannot fit a PANTHER cluster.Source: Figure 9 · p. 11, §7.3.1 · p. 12

7.3.2 Multiple- and Batch-Query Scenarios.

• As U grows, amortized multi-query WAN cost falls toward the online floor; HNSecW crosses below PANTHER after offline reshuffling is amortized.The batch variant starts below the multi-query curve at small U by sharing one parallel reshuffle.Source: Figure 10 · p. 11, §7.3.2 · p. 12

7.2 Search Accuracy and RAG Quality

• At C=7, HNSecW matches the HNSW baseline on RAG quality, while larger C gives negligible improvement.Source: Table 4 · p. 12, §7.2 · p. 12

8 RELATED WORK

• Secure ANN research includes query-private, encrypted-outsourcing, and server-client MPC settings, with different assumptions about which inputs remain private.Source: §8 · p. 12
• SANNS and PANTHER use clustering-based secure ANN, while Pacmann builds a graph index for query-private search with a public database.Source: §8 · p. 12
• HNSecW secret-shares the query, database, and index among computation servers; earlier secure kNN works target smaller-scale or specialized settings.Source: §8 · p. 12

• O(log N) online time with symmetric privacy for the query and database is HNSecW’s core protocol result.Source: §9 · p. 12
• HNSecW supports single-query, sequential multi-query, and batch-query settings.Source: §9 · p. 12
• Secure index construction and dynamic graph updates are identified as future work; the database owner currently builds the index locally before queries arrive.Source: §9 · p. 12
• For secure offloading, MPC servers can insert N vectors one by one and reuse oblivious search, requiring N graph searches, O(N log N) time, and O(NM) space for degree bound M.Source: §9 · p. 12