Amora: Communication-Efficient Private Approximate Nearest Neighbors Search

1 Introduction

• Pacmann’s graph-based search offers precise guidance but retrieves only one vertex’s vector and neighbor list per O(N)-communication PIR query.The paper calls this the per-vertex cost model and identifies it as the source of Pacmann’s online inefficiency.Source: §1 · pp. 1–2
• SimplePIR can return an entire database column per query, but combining each vertex’s vector and neighbor list creates a trade-off between balanced matrices and retrieving more vertices.Balanced matrices limit the number of vertices per column, while packing in more vertices makes queries more costly.Source: §1 · p. 2
• Amora separates distance and traversal payloads: VecPIR retrieves partition-level distances, while NbrPIR retrieves only the neighbor lists needed for expanded candidates.This dual-PIR layout shifts communication amortization from per-vertex to per-partition.Source: §1 · p. 2
• Batch PIR combines concurrent queries, centroid pruning skips distant partitions, and TopCand seeds jump-style navigation with close vertices from retrieved partitions.These techniques reduce the PIR queries needed to reach a target accuracy.Source: §1 · p. 2
• Amora reduces online communication by 93–99% compared to Pacmann while achieving higher search accuracy.The evaluation covers five datasets, spanning 96–1024 dimensions and up to 10 million vectors.Source: §1 · p. 2

2.1 Approximate Nearest Neighbors Search

• Graph-based ANNS uses greedy traversal of a proximity graph and currently offers the best accuracy–throughput trade-off on most benchmarks, but its data-dependent access pattern complicates privacy protection.Cluster-based and hash-based methods offer alternative search strategies, with cluster restriction potentially limiting accuracy and hash methods requiring many tables for high recall.Source: §2.1 · p. 2

2.2 Private Approximate Nearest Neighbors Search

• Multi-server PANNS can use distributed point functions across non-colluding servers, but the non-collusion assumption is difficult to enforce in practice.Servan-Schreiber et al. and Song et al. are examples of this line of work.Source: §2.2 · p. 3
• Single-server cluster-based PANNS limits search to a few partitions, while graph-based schemes such as Pacmann improve accuracy through multi-hop traversal but incur storage or communication costs.Compass assumes a client-owned encrypted database, and PrivANN relies on a TEE with additional side-channel concerns.Source: §2.2 · p. 3

3.1.1 Approximate Nearest Neighbors Search.

• ANNS returns database vectors that approximate the query’s k nearest neighbors, with quality measured by Recall or mean reciprocal rank.Source: §3.1.1 · p. 3

3.1.2 Graph-Based ANNS.

• Graph-based ANNS represents vectors as vertices connected to approximate neighbors and greedily expands the closest unvisited candidates until the search ends.The search maintains a candidate min-heap and a result max-heap, then returns the top-k results.Source: §3.1.2 · p. 3

3.1.3 Single-Server PANNS.

• The single-server preprocessing model lets a client store a compact hint and then privately query a public database without revealing its query vector.The stated privacy focus is query privacy; the database itself does not require protection.Source: §3.1.3 · p. 3

3.2.1 LWE and Regev Encryption.

• Regev encryption based on LWE is additively homomorphic, allowing ciphertext sums to decrypt to plaintext sums when accumulated error remains small.Source: §3.2.1 · p. 3

3.2.2 SimplePIR.

• SimplePIR is a single-server PIR scheme using Regev encryption and server-side preprocessing, and one query can reconstruct an entire database column.The client reuses the offline hint across queries.Source: §3.2.2 · pp. 3–4

3.3 Threat Model

• The protocol assumes a semi-honest server and defines query privacy through indistinguishability from a simulation given only the database size.Client-side timing side channels are out of scope, though padding client work to a fixed budget can remove them if needed.Source: §3.3 · p. 4

4 Design Overview

• The combined layout places each partition’s vertices in one PIR column, but storing both vectors and neighbor lists makes columns heavy and creates a balance-versus-information trade-off.A balanced matrix amortizes queries over few vertices; denser columns raise communication costs.Source: §4 · p. 4
• The dual-PIR split stores vector dimensions across VecPIR columns for partition-level distances and places neighbor lists in NbrPIR subgroup columns.This separates the two payloads because all retrieved vertices contribute distances, but only expanded candidates need neighbor lists.Source: §4 · pp. 4–5, Figure 1 · p. 4
• Batch PIR combines queries into one matrix multiplication, centroid pruning skips distant partitions, and TopCand seeds the candidate heap with close vertices from retrieved partitions.These optimizations target communication rounds, database scans, and navigation through distant regions.Source: §4 · p. 5
• Offline, the server builds the partitioned graph and PIR hints and sends hints and centroids; online, the client uses centroid entry and alternates batched neighbor-list and distance queries.The fixed iteration count and batch sizes make the communication pattern identical across queries.Source: Figure 2 · p. 4, §4 · p. 5

• The section elaborates Amora’s system design and summarizes the paper’s notation in Table 1.Source: §5 · p. 5

• VecPIR stores each vertex’s quantized vector across d consecutive columns, with vertices in a partition stacked as rows.The database is a K × (C·d) matrix; partition c occupies column block [c·d, (c+1)·d).Source: §5.1 · p. 5
• The client constructs a partition-specific query vector by placing the quantized query vector in that partition’s column block.The remaining positions in q_c are zero, and Δ = floor(q/p) is the scaling factor.Source: §5.1 · p. 5
• One VecPIR query returns a noisy inner product between the query and each of the K vertices in the target partition.The client recovers the inner products using the precomputed hint matrix; the plaintext modulus is chosen to retain ranking precision.Source: §5.1 · p. 5

5.2.1 Split encoding.

• Each neighbor’s partition index and local index are packed into an integer and split into t parts to fit the per-entry bit width.The parts are stored in separate matrix rows and recovered independently.Source: §5.2.1 · p. 5

5.2.2 Subgroup organization.

• NbrPIR divides each partition into subgroups of at most S vertices, with one subgroup per column to balance the matrix dimensions.The matrix has S·M0·t rows and C·gmax columns, and shorter neighbor lists or subgroups are padded to those maxima.Source: §5.2.2 · p. 6

5.2.3 Vertex-to-subgroup mapping.

• A candidate’s neighbor list is located by its partition’s subgroup column and its offset within that subgroup.The client queries the subgroup column and extracts the target vertex’s M0·t rows.Source: §5.2.3 · p. 6

5.3 Efficient Private Search

• Each VecPIR query returns distances for all K vertices in a partition, while each NbrPIR query retrieves neighbor lists for S vertices in a subgroup.The search iteratively expands the closest candidate, queries its subgroup, then requests distances for neighbors’ uncached partitions.Source: §5.3 · p. 6

5.3.1 Batch PIR.

• Batch PIR packs multiple queries into one matrix multiplication, amortizing a database scan and merging multiple round trips.For VecPIR, one batch resolves distances to K·Bv vertices; NbrPIR similarly retrieves Bn subgroups in one round trip.Source: §5.3.1 · p. 6

5.3.2 TopCand exploration.

• TopCand adds the tc closest vertices from each retrieved partition as navigation seeds for jump-style exploration.Distances for the remaining vertices are still available from the same VecPIR query and help tighten the result heap’s admission threshold.Source: §5.3.2 · p. 6

5.3.3 Centroid-based pruning.

• Centroid-based pruning orders pending partitions by centroid distance and removes those beyond α·d*best before selecting the next VecPIR batch.Centroid sorting is performed on the client without online communication, and α is fixed per dataset.Source: §5.3.3 · p. 6

5.3.4 Selective decryption and caching.

• Selective decryption caches each retrieved subgroup ciphertext and decrypts only rows for vertices actually visited.Later candidates in the same subgroup reuse the cached ciphertext without additional communication.Source: §5.3.4 · p. 6

5.3.5 Compressed storage.

• Amora keeps the PIR databases compact by storing small-range values compactly and zero-extending them to the LWE word size at query time.VecPIR stores uint8-quantized vectors, while NbrPIR stores b-bit parts.Source: §5.3.5 · p. 6

5.4.1 Offline preprocessing.

• Offline preprocessing builds and partitions a proximity graph, divides partitions into subgroups, quantizes vectors, computes centroids, and constructs separate vector and neighbor-list PIR databases.The server performs SimplePIR setup and sends the hint matrices, shared random matrices, and centroids to the client; this one-time distribution is amortized over later queries.Source: §5.4.1 · p. 7

5.4.2 Online PANNS.

• Centroid entry selects the closest entry partitions locally, then VecPIR retrieves distances for their vertices to seed the candidate and result heaps.The initial centroid-distance computation needs no online communication because the client already has the centroids.Source: §5.4.2 · p. 7
• Each fixed search iteration retrieves batches of neighbor subgroups, processes candidates, prunes pending partitions by centroid distance, and uses VecPIR to obtain distances for selected partitions.Top-tc vertices from each newly queried partition seed navigation, while top-k vertices enter the result heap; cached distances also resolve deferred neighbors.Source: §5.4.2 · pp. 7–8
• After T iterations, the client returns the top-k results using exactly 1 + T VecPIR rounds and T NbrPIR rounds, with fixed batch sizes.Padding maintains the same communication pattern across queries, and LWE-encrypted query vectors make real and dummy slots computationally indistinguishable to the server.Source: §5.4.2 · p. 8

6.1.1 Online communication.

• Online communication sums VecPIR and NbrPIR uploads and downloads; optimal partition and subgroup sizes balance their respective upload and download costs.For VecPIR, the costs scale with C·d and N/C; for NbrPIR, they scale with approximately N/S and S·M0·t.Source: §6.1.1 · p. 8
• VecPIR retrieves distances for all vertices in a partition per query, so visiting vertices across c partitions requires c queries rather than one per accessed vertex.This amortizes communication over a partition, and the analysis says the per-compared-vertex cost is constant independent of dimensionality at the optimal partition count.Source: §6.1.1 · pp. 8–9

6.1.2 Offline communication.

• The client downloads hint matrices, shared random matrices, and partition centroids once, and this offline communication is amortized over subsequent queries.The downloaded material also serves as the client-side storage requirement.Source: §6.1.2 · p. 9

6.2 Computation Cost

• Amora’s server performs dense database-matrix multiplications for PIR, while Pacmann is faster per round but requires more rounds; their amortized per-vertex computation is comparable.Amora’s workload maps to GPU and SIMD acceleration, while the computation gap versus Pacmann grows with N·z and, for high-dimensional data, with N·d.Source: §6.2 · p. 9

6.3 Security Analysis

• Under the LWE assumption, Amora satisfies query privacy in the semi-honest model; the server learns only communication-round timing, not the query, queried partitions or subgroups, or individual distances.Fixed rounds, fixed batch dimensions, padding, and indistinguishable LWE query columns make the transcript independent of query content.Source: §6.3 · p. 9

7.2.3 Preprocessing and storage.

• Amora’s offline communication is 82–98% smaller than Pacmann’s, and its client storage holds hints and partition centroids rather than a database replica.Pacmann’s offline phase requires downloading the entire database for Piano.Source: §7.2.3 · p. 10

7.2.4 Computation and latency.

• Amora has 45–66% lower latency at matched accuracy on SIFT1M, Deep1M, SIFT10M, and AGNEWS, but latency is slightly higher on MSMARCO.On MSMARCO, latency is 1.771 s for Amora versus 1.557 s for Pacmann; the reported crossover depends on N·d and network RTT.Source: §7.2.4 · p. 10

7.2 Overall Comparison

• Amora reduces per-query online communication by 93–99% versus Pacmann across all five datasets and achieves higher accuracy on all five.The comparison is configured at the minimum rounds reaching Recall@10 = 0.9 and MRR@10 = 0.24; Table 2 presents the overall comparison.Source: §7.2.1 · p. 10, §7.2.2 · p. 10, §7.2 · p. 10

7.3.1 Amora surpasses both graph-based baselines with far less

• Amora surpasses Pacmann’s 24-round accuracy within 7 rounds on SIFT1M, SIFT10M, and MSMARCO, within 11 on Deep1M, and matches it on AGNEWS within 3 rounds.These operating points use 93–99% less online communication; Amora’s most expensive setting also costs less than Pacmann’s cheapest on every dataset.Source: §7.3.1 · p. 11

7.3.2 Convergence speed is related to scale and dimensionality.

• Convergence varies with scale and dimensionality: fewer partitions at smaller N or larger d mean fewer VecPIR queries to reveal partitions and faster convergence.AGNEWS converges fastest with C* = 27, while Deep1M and SIFT10M have C* = 102 and 279 and are slowest at the stated three-round budget.Source: §7.3.2 · p. 12

7.3.3 Iterative graph traversal outperforms single-round retrieval.

• Against single-round cluster-based retrieval, Amora saves 97–99% of communication on the four recall datasets and 97% on MSMARCO while improving accuracy.Tiptoe also has substantially lower accuracy than Amora at three rounds on all five datasets; the paper attributes the cluster methods’ gap to not iteratively refining across partition boundaries.Source: §7.3.3 · p. 12

7.4.1 Fewer rounds translate into lower latency.

• On four datasets, Amora’s accuracy gains flatten early, and its fewer rounds translate into 45–66% lower latency despite added computation.At the reported latency points, Pacmann has lower accuracy; network round-trip delay accounts for most latency on those datasets.Source: §7.4.1 · p. 12

7.5.1 Optimization techniques.

• Batching reduces latency, TopCand improves accuracy under tight budgets on most datasets, and centroid pruning improves accuracy on all five at the operating points.Disabling batching raises matched-accuracy latency by 1.6–2.3×; disabling TopCand reduces recall or MRR on four datasets, and disabling pruning lowers recall or MRR on all five.Source: §7.5.1 · p. 12

(e) MSMARCO

• On MSMARCO, the dual-PIR split is a necessary design.Source: (e) MSMARCO · p. 13, Figure 6 · p. 13

7.6.1 Result-heap capacity

• Recall@10 on SIFT10M rises from 0.895±0.002 at ef = 10 to 0.920±0.002 at ef = 50, while communication and latency stay flat.The authors set ef = 50, where accuracy is in the flat range.Source: §7.6.1 · p. 13, Figure 7 · p. 13

7.6.2 TopCand count tc

• MRR@10 on MSMARCO stays between 0.239 and 0.247 across tc, while tc = 2 is best on AGNEWS and larger tc lowers accuracy on three other datasets.Source: §7.6.1 · p. 13, Figure 8 · p. 13

7.6.1 Result-heap capacity

• At C*, communication is minimal on every dataset; raising C to 4C* lowers accuracy across all five, while lowering C helps only some.The authors use C* on all datasets for minimum communication and high accuracy.Source: §7.6.1 · p. 14, Figure 9 · p. 14

8 Conclusion

• Amora pairs partitioned SimplePIR with a dual-PIR split: VecPIR returns partition distances, while NbrPIR retrieves subgroup neighbor lists.Source: §8 · p. 14
• Batch PIR reduces communication rounds and database scans, centroid-based pruning directs queries toward promising regions, and TopCand seeds jump-style graph navigation.Source: §8 · p. 14
• Across five datasets, Amora reduces online communication by 93–99% over competitors while achieving higher search accuracy.Source: §8 · p. 14