- Rating
- 2
- Confidence
- 4
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
The paper proposes MESS for private semantic search across multiple non-colluding servers. The client uses server-specific IsoHash mappings to convert embeddings into binary codes, perturbs the codes using randomized response, and stores encrypted vectors alongside them. Each server builds an HNSW index over its perturbed codes. For a query, the client sends a perturbed code to every server, receives encrypted candidates, and decrypts and reranks them locally. The paper gives a per-server privacy leakage analysis and reports up to 15× lower latency than Compass on specific workloads.
Critical strengths
- The design allows ordinary HNSW search over perturbed codes, so the search is performed over noisy "plaintext", rather than HE ciphertext. Under the reported LAN setting on TripClick, MESS is 15.08× faster than Compass, reducing query latency from 340.70 ms to 22.60 ms.
- The experiments cover several retrieval workloads and show how replication helps recover search quality after perturbation.
- The repository includes open-source code that can be audited, which is good.
Critical weaknesses
-
I find the trust assumption way too demanding. The default setting uses 64 mutually non-colluding servers. There is no joint-view guarantee even for two colluding servers. It is unclear what practical deployment supports this assumption. The previous schemes usually assume two or up to three servers, and even in the multi-server regime, most will assume constant-rate collusion like 1/2 or 1/3.
-
The reported speedup is not an apples-to-apples comparison. The systems differ in (a) trust assumptions: MESS assumes many non-colluding servers, while Compass does not require this assumption; (b) security guarantees: MESS provides per-server differential privacy bounds, while Compass provides cryptographic protection, including access-pattern hiding; and (c) resource use: MESS searches 64 logical shards, emulated on one machine, but it is unclear whether the baselines use the same total resources and parallelism. A simple baseline would partition the database into 64 shards, run Compass on each shard in parallel, and merge the results. Each shard would contain only 1/64 of the database.
-
Relevant baselines are missing, including BiSON[1] and Speakeasy[2]. The comparisons would clarify whether MESS offers a compelling privacy and performance tradeoff.
[1]: Das S, Ravi R, Chandran N, et al. BiSON: Billion-Scale Oblivious Nearest-Neighbor Search in Milliseconds. IEEE EuroS&P 2026 [2]: Speakeasy: Billion-Scale Two-Server Private Semantic Search: https://openreview.net/forum?id=toYFHz24kU
Questions for authors
- What privacy remains if two or more servers pool their observations? How much additional noise would be needed to protect against collusion, and what would this cost in recall and latency?
- How much of the speedup remains against Compass running in parallel on 64 database shards, at matched recall and total resource budgets? Does that gain justify the stronger trust assumption and weaker privacy guarantee?