{"id":"84b48e7b-1e93-4b4a-aef7-49d4a02b6683","arxiv_id":"2607.28999","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":7,"one_line_summary":"MESS builds multiple HNSW indexes over randomly perturbed binary embeddings to provide differentially private semantic search with near-plaintext accuracy and much lower latency than homomorphic encryption or ORAM baselines.","lead":"MESS is a private semantic search system that scrambles embeddings into binary codes with randomized response and indexes them in multiple HNSW graphs, letting a cloud server search without seeing plaintext vectors or queries. The paper reports up to 15.08x lower latency than Compass, an ORAM-based baseline, and includes formal differential-privacy bounds for the stored index and query traces.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Protocol trains IsoHash on the protected database (Fig. 2), while Theorem 5.1 and Sec. 5.2.1 require a fixed mapping trained on public/disjoint data; as written, the stored-index privacy proof does not apply to the implemented system.","rationale":"The reader's weakest assumption correctly identified the IsoHash training-data condition in Sec. 5.2.1. My reading sharpens this from a deployment constraint to an internal inconsistency: the protocol in Fig. 2 explicitly trains on the protected database, so the formal premise is violated by the paper's own construction. This is the single most load-bearing concern because it directly undermines Theorem 5.1, and by propagation the query-side theorems, rather than merely weakening the numerical privacy parameters. The concern is not about disagreement with the community or about the plausibility of randomized response; it is about the match between the formal model and the described system. The paper could be repaired by changing the protocol to use a public/disjoint training set and re-running the accuracy evaluation; the systems contribution—multi-graph HNSW over perturbed codes—remains plausible. Therefore I do not move the verdict beyond CONDITIONAL, and since the reader already reached CONDITIONAL, I recommend UNCHANGED. I agree with the reader that the training-data assumption is the weakest link; my point is that the text now contradicts it, which strengthens the conditionality but does not change the overall verdict category.","tokens_in":31268,"tokens_out":4050,"duration_ms":50550,"concrete_test":"Build two MESS variants with otherwise identical parameters (M=64, t=16, κ=128, p_D=0.08, p_PRR/p_IRR as used in Sec. 6): Variant A trains IsoHash on a random sample of the protected database D exactly as Fig. 2 specifies; Variant B trains IsoHash on a disjoint public sample of the same size. For the same set of at least 100 neighboring challenge pairs, compute (a) the empirical hockey-stick divergence and pair-specific XDP values using the A.2.6 methodology and (b) Recall@10 on SIFT and LAION at the Table 2 candidate pools. If Variant A shows materially larger privacy loss than Variant B, or if Variant B's Recall differs by more than ~0.01 from the reported values, then the current protocol does not support the claimed simultaneous privacy and accuracy and the paper must either change the protocol or weaken the privacy claim.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Sec. 5.2.1 states that the IsoHash mappings used in the privacy proofs must be pretrained and fixed, and that 'the training data are public, disjoint from the protected database, or excluded from the neighboring relation.' But Fig. 2 Phase 1 specifies the opposite: 'The client samples representative training data from D and trains shard-specific IsoHash parameters.' If IsoHash is trained on the protected database D, then the two neighboring databases D0 and D1 used in Theorem 5.1—which differ in one substituted embedding—produce different shard mappings H_s. Consequently, every other record's shard codes, the HNSW graph structure, and even the query-side hash mappings can change between worlds. The proof of Theorem 5.1 conditions on the selected shard set and asserts that only the t shard-local entries of the substituted record depend on the embedding; that step is false when H_s itself is world-dependent. The theorem's ēta_D-XDP guarantee therefore does not hold for the protocol as written. This is load-bearing because stored-data privacy is an essential part of the paper's central 'privacy + accuracy + efficiency' claim, and the same world-dependent mappings are reused for query generation, so the access- and search-pattern theorems inherit the same problem. The fix—train IsoHash on a genuinely public or disjoint dataset—is straightforward, but it may change the recalled accuracy and has not been evaluated.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"MESS is a private semantic search system that combines locality-sensitive hashing, randomized response, and multiple HNSW graph shards. The client hashes and perturbs embeddings before outsourcing; the server stores encrypted payloads and HNSW indices over perturbed binary codes; queries use a two-phase permanent/instantaneous randomized-response mechanism. The paper claims formal XDP guarantees for stored-data, access-pattern, and search-pattern privacy, and evaluates accuracy and latency against plaintext HNSW, Compass, and HE-Cluster baselines on SIFT, LAION, TripClick, MS MARCO, and SIFT100M. The central issue is a mismatch between the implemented protocol, which trains IsoHash on the protected database (Fig. 2), and the formal privacy analysis, which requires the ISO-LSH mappings to be fixed and trained on public/disjoint data (Sec. 5.2.1).","tokens_in":31648,"tokens_out":6913,"duration_ms":85501,"significance":"If the result holds, MESS would be a notable practical contribution: it shows a DP-based design can approach plaintext ANN accuracy and achieve far lower latency than HE/ORAM-based private search on an untrusted single server. The multi-graph approach for mitigating randomized-response rank distortion is interesting, and the empirical cross-shard inference study is a useful complement to the formal analysis. The privacy bounds are derived analytically rather than fitted, and the only fitted quantities (Appendix B.1) are explicitly labeled as model fits. However, the training-data inconsistency means the main privacy theorems do not currently apply to the system as described in the main text, and the evaluation omits the achieved formal privacy parameters. With corrections, the contribution is potentially significant.","major_comments":[{"comment":"Fig. 2 Phase 1 trains shard-specific IsoHash parameters on 'representative training data from D', but Sec. 5.2.1 requires the ISO-LSH mappings to be pretrained on data that is public, disjoint from the protected database, or excluded from the neighboring relation. If H_s is trained on D, two neighboring databases D0 and D1 differing in one substituted embedding yield different mappings H_s. Then every other record's shard codes, the HNSW graph structures, and the query-side hash mappings can differ between worlds. The proof of Theorem 5.1 conditions on a selected shard set and asserts that only the t shard-local entries of the substituted record depend on the embedding; that step is false when H_s itself is world-dependent. Theorems 5.2 and 5.3 inherit the same problem because they require fixed query mappings. Notably, the Appendix protocol (Fig. 7) already specifies a public/disjoint D","section":"§4 (Fig. 2), §5.2.1"},{"comment":"The evaluation never reports the privacy parameters actually achieved at the tested configurations. For example, App. A.2 uses storage-side p_D=0.08, which gives eta_D=ln(0.92/0.08)=2.44, but the paper does not state eta_D, eta_R, xi_SP, or representative pair-specific XDP values for the SIFT/LAION/TripClick/MS MARCO and SIFT100M settings whose recall and latency are the headline results. The abstract claims privacy, accuracy, and efficiency simultaneously; without reporting the privacy side of the trade-off, Figs. 4–6 and Tabs. 2–3 cannot be assessed as a privacy-utility frontier. Add a table of the formal privacy parameters (or representative pair-specific values) for each evaluated configuration.","section":"§6, Tabs. 2–3"},{"comment":"Theorem 5.3 only compares the workload W0=(q,...,q) with W1=(q,...,q,q'), i.e., a single split of one logical query into a new one. The prose in §2.3 and §5.2.4 promises protection of the general 'query-reuse relation' and states that the server 'cannot identify repeated queries'. A transcript containing several distinct query values and multiple repetitions involves multiple PRR groups and multiple reuse relations; the paper does not provide a composition argument or a bound for that general setting. Please either generalize the theorem to arbitrary workload adjacency (e.g., via composition over splits) or explicitly restrict the formal claim to the single-split adjacency.","section":"§5.2.4, Theorem 5.3"}],"minor_comments":[{"comment":"Typos: 'Skeched Proof' should be 'Sketch Proof' (Secs. 5.2.2–5.2.4); 'W AN' in the Fig. 4 caption and Sec. 6.2; 'iptoe' in Sec. 6.2 should be 'Tiptoe'. Also Tab. 1 has formatting glitches such as 'OursEncrypted DB'.","section":"Throughout"},{"comment":"The comparison would be clearer if the candidate pool sizes and p_D/p_q settings used in Fig. 4 were shown directly on the plots or in a table, rather than only in Appendix A.3. As written, the reader must cross-reference to know which privacy level each marker represents.","section":"§6.1"},{"comment":"The fitted coefficients gamma_cov, mu_R, sigma_R, gamma_mrr are clearly labeled as empirical fits, which is good. However, the caption of Fig. 8 says 'Normal-CDF fit' without giving the fitted coefficient values; reporting them would improve reproducibility.","section":"Appendix B.1"}],"recommendation":"major_revision","confidential_remarks":"The training-data mismatch is the key issue: the main-text protocol (Fig. 2) is inconsistent with the formal model (Sec. 5.2.1) and with the Appendix protocol (Fig. 7). This is fixable by changing the training-data assumption and re-running the accuracy evaluation, but it is load-bearing because all three privacy theorems rely on fixed, data-independent hash mappings. The missing privacy-parameter reporting is also important for the paper's central 'privacy + accuracy + efficiency' claim. I would not reject: the formal XDP derivations are coherent under their stated assumptions, and the empirical study is extensive. A careful revision could make the contribution publishable."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"First thing to know: MESS is a legitimate systems contribution, not a packaging of old tricks. The combination of shard-specific IsoHash, per-shard LSHRR, multi-graph HNSW, and PRR/IRR query perturbation is new, and the evaluation against Compass and HE-Cluster is convincing for latency and recall. The privacy theorems are standard randomized-response composition, but they are clearly stated, and the complete-view treatment of stored index, access transcript, and repeated-query transcript is more thorough than prior DP-LSH work.\n\nThe paper earns credit for honesty: the correctness model is explicitly approximate, the cross-shard inference evaluation is careful and doesn't overclaim, and the authors state the training-data assumption in Sec. 5.2.1.\n\nThe real soft spot is a mismatch between that assumption and the implementation description. The construction protocol in Fig. 2, Phase 1, trains IsoHash on the protected database D. Theorem 5.1 and Sec. 5.2.1 require the hash mapping to be fixed and independent of the neighboring pair; if the mapping is trained on D0 vs D1, everything downstream changes, so the proof's conditioning step doesn't hold. The formal protocol in Fig. 7 actually uses a separate public/disjoint Dtrain, which would fix this, but that's not what Fig. 2 says and the accuracy impact of switching to public training data isn't evaluated. This is a load-bearing gap for the stored-data privacy claim.\n\nSecond, the achieved privacy parameters are weak and underreported. Appendix A.2 gives reconstructed XDP values of 31 to 78 for the tested configuration, and the idealized complete-16-shard thresholds are 200 to 410. The paper never reports epsilon for its headline configuration, so a reader can't tell whether 'privacy' means epsilon 30 or 300. Third, no code or artifact; the authors promise it upon acceptance, but the evaluation depends on non-public parameters.\n\nThese are fixable. The central design is defensible, the accuracy and latency evidence is strong, and the cross-shard inference study is a real addition. This paper deserves a serious referee. I'd ask the authors to align the protocol description with the public-training assumption, report achieved privacy parameters, and ideally release the code. If those are addressed, it's a solid PVLDB-level systems paper.","headline":"MESS is a genuine systems contribution with a fixable but load-bearing gap: the stored-index privacy proof assumes IsoHash trained off the protected database, while the main protocol trains on it.","tokens_in":32176,"tokens_out":2669,"would_cite":true,"duration_ms":28333,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"MESS claims a differentially private semantic search system that keeps near-plaintext accuracy and runs 15x faster than ORAM-based Compass.","keywords":["private semantic search","differential privacy","locality-sensitive hashing","randomized response","HNSW index","access pattern privacy","search pattern privacy","multi-graph index"],"falsifier":"Train the shard-specific IsoHash directly on the protected database, then empirically estimate the maximum likelihood ratio of the complete server view between two neighboring embeddings that differ in a single value; if the ratio exceeds e^{η_D D_D(𝒙,𝒙′)} for any pair, the stored-data guarantee is violated. Equivalently, a cross-shard linkage procedure that correctly recovers all t shard entries of a target record would push the reconstructed XDP evidence to the complete-view threshold, showing the single-server view leaks more than the experiments indicate.","tokens_in":31144,"feed_emoji":"🔒","tokens_out":6223,"duration_ms":66085,"temperature":0.7,"pith_summary":"MESS is a system for semantic search over vector embeddings when the search index lives on an untrusted cloud server. It claims that privacy of the stored data, of individual query access patterns, and of repeated-query search patterns can all be provided through differential privacy applied to binary locality-sensitive hash codes, without the heavy machinery of homomorphic encryption or oblivious RAM. To keep retrieval quality high despite the bit-flips that create privacy, the system stores each vector in multiple independently hashed and independently perturbed hierarchical navigable small-world (HNSW) graph shards and aggregates candidates across shards. The paper backs this with formal extended-differential-privacy theorems for the stored index, the access transcript, and the repeated-query transcript, and reports that search stays close to plaintext accuracy while running in 52.53 ms/query on a 100-million-vector index, up to 15.08x faster than the ORAM-based Compass baseline.","feed_headline":"Private vector search hits 52 ms/query at 100M scale","feed_subtitle":"MESS perturbs binary hash codes, splits the index into graph shards, and cuts latency 15x below the ORAM baseline.","key_machinery":"The load-bearing mechanism is the LSH randomized-response (LSHRR) perturbation of shard-specific binary codes combined with a multi-graph HNSW index. Each shard applies its own pretrained IsoHash mapping, producing κ-bit codes from the original embeddings; randomized response flips each bit with probability p, giving an (ε d_H, 0)-XDP guarantee under the hash-induced Hamming pseudometric. To keep recall high, each embedding is routed to t of M shards with independent hash functions and independent perturbation coins, and the query is searched in all shards, with candidates aggregated before client-side exact reranking. The two-phase query perturbation—a permanent randomized response reused f","core_discovery":"The paper's central claim is that differential privacy, applied at the level of binary LSH codes, is enough to make a cloud-hosted nearest-neighbor index private in all three senses that matter—stored data, access pattern, and search pattern—without sacrificing search quality or online speed. MESS quantizes each embedding into a shard-specific binary code and flips bits with randomized response; a permanent randomized response memoized per query value, followed by a fresh instantaneous response per submission, hides both the query value and the fact that a query was repeated. Theorem 5.1 shows the complete stored multi-graph index is η_D-XDP with respect to the shard-aggregated Hamming pseud","pith_inferences":["If the IsoHash training-data disjointness condition can be met with a public auxiliary set (for example, class prototypes not in the protected database), the same design would extend to deployment settings where the protected database itself is the only data source.","The paper's Poisson-binomial overtaking model suggests a principled way to auto-tune the flip probability, routing multiplicity, and candidate budget for a target recall, which the paper does not develop into a closed-form optimizer.","Because the guarantee is XDP with a distance pseudometric, the index could also serve as a building block for differentially private publication of embeddings in federated or streaming settings, where per-pair sensitivities are auditable.","The cross-shard linkage evaluation shows practical leakage well below the perfect-association bound assumed in the formal theorem; if future linkage attacks close that gap, single-server deployments would see degraded effective privacy, motivating two-server or secret-shared variants for high-assurance settings."],"forward_implications":["If the theorems hold, users can outsource embedding search to an untrusted cloud with quantifiable leakage bounds instead of assuming full obliviousness.","DP-based approaches become a practical alternative to ORAM and homomorphic-encryption baselines for high-recall private search, changing the design space for private vector databases.","Because search over perturbed codes is one-round and avoids encrypted distance computation, the scheme can scale to hundred-million-vector datasets where cryptographic baselines are impractical.","The multi-shard redundancy gives operators a tunable privacy–accuracy–storage tradeoff through the routing multiplicity, flip probabilities, and candidate pool size.","The two-phase permanent plus instantaneous response offers a template for hiding query repetition without independent perturbation per submission."],"supporting_citations":[{"why":"Supplies the LSH randomized-response mechanism and the extended-differential-privacy definition that all three privacy theorems build on.","marker":"[14]"},{"why":"Provides the HNSW graph index that MESS privatizes and searches over.","marker":"[33]"},{"why":"The ORAM-based Compass baseline that MESS compares against for latency, communication overhead, and accuracy.","marker":"[51]"},{"why":"The IsoHash method used to produce each shard's binary codes; the paper's key training-data assumption concerns this mapping.","marker":"[26]"},{"why":"RAPPOR's memoization technique motivates the permanent randomized response that protects repeated queries from averaging attacks.","marker":"[13]"},{"why":"The Tiptoe HE/PIR system on which the HE-Cluster baseline used in the evaluation is modeled.","marker":"[17]"}],"fun_headline_variants":["Private search that's 15x faster: MESS perturbs binary codes, not encrypts","Differential privacy on binary codes makes cloud search 15x faster","MESS: private vector search without HE or ORAM, 15x lower latency","Binary codes + randomized response = fast private semantic search","Multi-graph HNSW over shuffled bits: private search at speed"],"cache_read_input_tokens":2688,"weakest_assumption_plain":"The privacy proofs assume the shard-specific IsoHash mappings are trained on data that is public, disjoint from the protected database, or excluded from the neighboring relation; if the training data overlaps or correlates with the protected embeddings, the differential-privacy bounds on the stored index and query traces no longer hold.","fun_headline_variants_meta":{"raw":{"variants":["Private search that's 15x faster: MESS perturbs binary codes, not encrypts","Differential privacy on binary codes makes cloud search 15x faster","MESS: private vector search without HE or ORAM, 15x lower latency","Binary codes + randomized response = fast private semantic search","Multi-graph HNSW over shuffled bits: private search at speed"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000522,"raw_usage":{"total_tokens":2380,"prompt_tokens":783,"completion_tokens":1597,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":527,"completion_tokens_details":{"reasoning_tokens":1498}},"tokens_in":527,"tokens_out":1597,"duration_ms":12792,"temperature":1.0,"reasoning_tokens":1498,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-05T04:22:36.818507+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Train the shard-specific IsoHash directly on the protected database, then empirically estimate the maximum likelihood ratio of the complete server view between two neighboring embeddings that differ in a single value; if the ratio exceeds e^{η_D D_D(𝒙,𝒙′)} for any pair, the stored-data guarantee is violated. Equivalently, a cross-shard linkage procedure that correctly recovers all t shard entries of a target record would push the reconstructed XDP evidence to the complete-view threshold, showing the single-server view leaks more than the experiments indicate.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"The ORAM-based Compass baseline that MESS compares against for latency, communication overhead, and accuracy."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"The IsoHash method used to produce each shard's binary codes; the paper's key training-data assumption concerns this mapping."}],"review_version":2}