Pith. sign in

REVIEW 3 major objections 4 minor 49 references

A Unified Benchmark for Privacy-preserving Vector Search

T0 review · 3 major / 4 minor · reviewed 2026-08-06 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Privacy costs 1x, 4x, 22x, 190x in vector search

desk verdict First real cross-scheme ruler for private vector search, honestly executed, but the abstract's clean cost tiers rest on an uncertified BNTM instantiation and a projected Tiptoe row. read the letter →

arxiv 2608.01192 v1 pith:IDSMBUHM submitted 2026-08-02 cs.CR cs.DBcs.PF

Anne-Marie Kermarrec , Rafael Pires , Mathis Randl , Martijn de Vos This is my paper
classification cs.CRcs.DBcs.PF
keywords privacy-preservingvectorsearchencryptednearestneighborbenchmarkParetofrontierIVFindexSAPEMVPBNTM
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper tries to establish that privacy-preserving vector search is not uniformly expensive: when all schemes are measured on one shared benchmark, they spread across a Pareto frontier instead of imposing a flat penalty. The paper builds a single harness holding corpus, index, hardware, and metrics fixed, then runs four cryptographic schemes plus an unencrypted baseline over the same workload. It finds SAP matches plaintext speed, EMVP costs about 4x, BNTM adds another 22x, and Tiptoe (which hides even the cluster choice) costs roughly 190x per query. If true, this gives practitioners a defensible scheme-selection rule and overturns the inherited belief that encrypted vector search is unaffordable.

What carries the argument

The load-bearing object is the unified benchmark harness: a single codebase implementing all five schemes over the same IVF index, with identical cluster assignments computed once on plaintext vectors, a fixed 128-bit security configuration per scheme, a common per-query pipeline (embed, route, score, top-k), and shared metric conventions including recall@10 at a common operating point. This isolates the cryptographic primitive from the rest of the retrieval pipeline, so any throughput, latency, or communication difference is attributable to the scheme rather than to index choice or hardware. The paper also relies on closed-form communication-cost formulas derived from corpus geometry and pe

What would settle it

Run the original BNTM construction with its recursive trapdoor refinement fully implemented, and measure client-side decode latency on the same MS MARCO-8.8M setup; if the client unmasking drops far below the 35ms reported here, the 22x median-latency figure would not hold. Alternatively, run Tiptoe end-to-end on the full 8.8M corpus with the actual k-means cluster-size dispersion measured; if the per-query latency is far from the projected 46 seconds, the 190x figure is wrong.

Watch

Extended reading notes

Core claim

The central claim is that, under a uniform ruler, the four privacy-preserving vector search schemes occupy distinct cost tiers that track the strength of their privacy guarantee rather than a single dramatic slowdown. Specifically: SAP, which perturbs vectors but leaves geometry visible, performs at plaintext speed; EMVP, which hides the query and corpus under encryption, runs at about 4x the throughput cost of plaintext at recall 0.9; BNTM, which adds malicious-server verifiability, adds a further 22x median-latency cost; and Tiptoe, which hides the IVF cluster choice, adds a 190x per-query cost. The paper also shows that GPU acceleration helps plaintext and SAP (roughly 1.8-1.9x) but not E

Load-bearing premise

The benchmark's cost and security numbers stand on the re-implementations being faithful: BNTM has no public reference implementation and its 128-bit security tuple could not be certified, and Tiptoe's 8.8M-passage row is extrapolated from a 100k run under the assumption that k-means cluster-size dispersion is roughly scale-invariant.

Editorial extensions

If this is right

  • Practitioners can choose a scheme by matching the privacy guarantee to the budget: SAP for hiding raw contents at near-zero cost, EMVP for full encryption at 4x, BNTM for verifiability at 22x, Tiptoe for access-pattern hiding at 190x.
  • Encrypted vector search is affordable on commodity servers: EMVP sustains about 12 queries per second at recall 0.9 on the full 8.8M-passage corpus on one machine.
  • GPU acceleration should not be assumed to help encrypted schemes: it pays off only for plaintext and SAP, and the deciding factor is memory bytes read per query, not the cryptographic construction.
  • Wire bytes and memory bytes rank schemes differently: BNTM sends very little over the network but reads nearly as much memory as EMVP, so network-optimized schemes can still be bandwidth-bound.
  • For the strongest privacy tier (Tiptoe), recall is structurally capped by the single-cluster search and by quantization, independent of throughput.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The cost tiers are likely to shift as implementations mature: the BNTM client-side unmasking is an upper bound because the paper omits the original scheme's recursive trapdoor refinement, and that refinement targets exactly the client decode step that dominates BNTM's latency.
  • Because all schemes share a plaintext-trained IVF partition, the benchmark isolates the cryptographic layer but does not tell how each scheme would perform on graph indexes like HNSW; the three encryption-based schemes cannot use query-dependent graph traversal at all, so the 4x/22x/190x ratios are specific to IVF.
  • A testable extension would be to run the same harness at different security levels (e.g., 192-bit or 256-bit) to measure how the cost tiers stretch, since all schemes were fixed at 128-bit and the ratios may not hold there.
  • Tiptoe's low recall might be partially recoverable by enabling its published recall-boosting extensions (recursive cluster splitting and boundary double-assignment), which the benchmark deliberately disabled to keep the comparison controlled.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 4 minor

Summary. The paper presents a unified experimental benchmark for privacy-preserving vector search. It implements four cryptographic schemes (SAP, EMVP, BNTM, Tiptoe) plus a plaintext baseline in a single harness over a shared IVF index, using MS MARCO embeddings (100k and 8.8M passages), fixed seeds, cold caches, a performance governor, and three repetitions. It reports recall@10, throughput, end-to-end latency, communication volume, index-build time, CPU-vs-GPU behavior, and parallel scaling. The headline claims are that the schemes form a Pareto frontier in privacy/performance/recall: SAP matches plaintext, EMVP costs about 4x throughput, BNTM adds malicious-server verifiability at 22x median latency, and Tiptoe hides the cluster choice at 190x per-query cost, with GPU acceleration helping only plaintext and SAP. The authors release all artifacts and provide closed-form communication-cost expressions in an appendix.

Significance. If the headline claims survive scrutiny, this is a valuable resource: it is the first common-ruler comparison of these schemes, it isolates the cryptographic primitive by using a shared IVF index, and it separates wire bytes from memory bandwidth, showing that a low network footprint does not predict server throughput. The careful measurement controls (fixed seed, cold cache, frequency governor, repetitions), the validation of Tiptoe against the authors' reference implementation, and the public artifact release are genuine strengths. However, the quantitative conclusions currently rest on two load-bearing points that need correction: BNTM is benchmarked with an uncertified LPN tuple at a claimed 128-bit level, and SAP's 'matches plaintext' result is measured at beta=0, i.e., with no perturbation and hence no meaningful privacy. The Tiptoe full-scale numbers are also partly extrapolated under an unvalidated scale-invariance assumption. These issues do not destroy the benchmark's value, but they must be addressed before the abstract's comparative cost claims can be accepted.

major comments (3)
  1. [Section 3 (Per-scheme parameters), Table 5] BNTM is the load-bearing gap. The paper states, 'we could not certify the concrete security level of the resulting tuple' after instantiating lambda=128 through the original paper's heuristic, and Table 5 lists (n,n1,delta,epsilon,mu)=(1024,128,0.125,0.7,n^{-0.3}). There is no public reference implementation and no independent LPN-estimator check. The abstract and Figure 1 then report BNTM's 22x median-latency cost as if it were at the same 128-bit security level as EMVP and Tiptoe. The 'same ruler' premise of the benchmark requires a certified or at least independently estimated security level. Please either re-instantiate BNTM with parameters validated by an LPN estimator at 2^128, or explicitly present BNTM as an uncertified instantiation and remove its cost from the same-security headline comparisons.
  2. [Section 3 (β=0 default), Section 4.1, Table 2, Figure 7(a)] The claim 'SAP matches Plaintext' is measured with β=0, the no-perturbation setting. Section 2.3 itself states that scaling alone is distance-preserving and insecure. A server seeing scale-only ciphertexts can recover the corpus geometry, so the benchmark's headline SAP point is not a privacy-preserving configuration. Since β has no query-time latency cost, server throughput is indeed β-invariant, but recall at fixed nprobe drops as β increases; a fair 'SAP at recall 0.9' comparison would require the throughput achieved at a privacy-relevant β and a higher nprobe, not the β=0 operating point. The abstract and Figure 1 should either report SAP at a nonzero perturbation or clearly label the curve as 'SAP without perturbation'.
  3. [Section 4.1 and Appendix A.2, Table 3 footnote] The 8.8M Tiptoe row is extrapolated, not measured. Table 3 marks Tiptoe † at 8.8M as estimated from closed-form expressions, and Appendix A.2 projects m_max=9186 from the 100k max-to-mean ratio under the assumption that k-means cluster-size dispersion is 'roughly scale-invariant,' explicitly stating that the 8.8M corpus was not partitioned through Tiptoe's encoder. This assumption is unvalidated and directly affects the extrapolated 46 s/query throughput figure in Section 4.1 and the bottom row of Table 3. The 190x headline is measured at 100k and is not affected, but the full-scale Tiptoe claims need either validation at an intermediate scale or a sensitivity analysis, and the estimated rows should not be presented with the same weight as measured rows.
minor comments (4)
  1. [Figure 1 vs Section 4.4] Figure 1 says BNTM's 22x figure includes response verification, but Section 4.4 reports the BNTM latency distribution with verification disabled, and Section 3 says verification is disabled by default. The reader cannot tell which number is the headline. Add an explicit cross-reference from Figure 1 to Section 4.5, and state in Section 4.4 that the verification-enabled latency is reported in Figure 1/Table 2.
  2. [Table 5] The SAP row lists β∈{0,0.5}, but Section 4.5 sweeps β∈{0,0.25,0.5,0.75,1}. The table should match the sweep, or explain which values are used in the main throughput experiments.
  3. [Section 4.4] The text reports Plaintext median latency as 2.8 ms and later says Plaintext and SAP have a total per-query mean latency of 2.6 ms. Mean and median are being mixed without comment. Please state which statistic is used for each claim.
  4. [Section 3 (Implementation deviations)] The BNTM recursive-refinement omission is reported as leaving the measured client latency an upper bound. This should be repeated near the headline BNTM cost in Section 4.1 and Figure 1, since a reader comparing schemes at the summary level will otherwise not know the 22x figure already includes an upper-bound component.

Circularity Check

0 steps flagged · score 0.0 of 10

Benchmark findings are independent measurements; no circular derivation.

full rationale

The paper is a comparative benchmark, not a derivation chain: its headline figures (SAP matching Plaintext, EMVP at ~4x, BNTM at 22x, Tiptoe at 190x) are per-query latency, throughput, and recall measurements taken on a shared harness, or explicitly labeled extrapolations. The only extrapolated row, Tiptoe at 8.8M, is transparently derived from closed-form byte formulas, validated against measurements at 100k, and flagged with the explicit assumption that k-means cluster-size dispersion is roughly scale-invariant; it is an assumption-bound projection, not a disguised fit. No fitted parameter is renamed as a prediction. BNTM's uncertified lambda=128 tuple is a security-parameter gap, honestly disclosed in the text ('we could not certify the concrete security level of the resulting tuple'), and the 22x cost is a measured cost of that instantiation, not a quantity derived from the scheme's own security claim. Tiptoe's validation against the official Go implementation is external to this paper's authors (Henzinger et al.), so it is not a self-citation chain. The claim that SAP matches Plaintext is an empirical consequence of running the same scoring code on scaled vectors at beta=0, and the paper explicitly ties the recall behavior to the known scale-only ranking preservation; this is a stated design property, not a circular prediction. No equation in the paper reduces to its own input, and no load-bearing self-citation is present. The relevant caveats (BNTM security certification, Tiptoe extrapolation, missing recursive BNTM refinement) are correctness risks or performance limitations, not circularity.

Assumptions & free parameters 5 free parameters · 6 assumptions · 0 invented entities

The central claim rests on the benchmark design being a faithful and fair common substrate. The biggest unpaid costs are: (1) the choice of a single IVF index with Tiptoe's extensions disabled, (2) an uncertified BNTM LPN instantiation, and (3) an unmeasured Tiptoe 8.8M projection. These are experimental assumptions, not discoveries.

free parameters (5)
  • SAP perturbation beta (default 0) = 0 (evaluated values 0, 0.25, 0.5, 0.75, 1)
    Headline "SAP matches Plaintext" uses beta=0, the no-perturbation setting that the paper itself says is insecure (distance-preserving scaling only). At beta=0.5, recall drops to 0.82.
  • nprobe operating point = 32 (100k), 64 (8.8M) to reach recall@10 approximately 0.9
    The 4x, 22x, and related cost ratios are reported at this author-chosen operating point; different nprobe values change the ratios (Section 4.1).
  • Tiptoe quantization bits = 3 and 4 bits
    Chosen to evaluate Tiptoe; they set its recall at 0.11 (3-bit) and 0.28 (4-bit), so the 190x cost is at a different recall than the other schemes.
  • EMVP zero-padding to record length l0=1024 = 768-dim padded to 1024
    This is the authors' instantiation choice for EMVP's 128-bit regime, not inherited from the source paper's table (Section A.1).
  • Tiptoe m_max scaling ratio = 977/315 = 3.10 applied to 8.8M mean cluster size
    Used to project Tiptoe's 8.8M communication costs without partitioning that corpus; the paper states this assumes cluster-size dispersion is scale-invariant (Section A.2).
assumptions (6)
  • domain assumption A fixed IVF index trained on plaintext vectors is a fair common substrate; all schemes can natively support IVF, and measured differences are attributable to the cryptographic primitive.
    Introduced in Section 3 (IVF configuration). If a scheme's real deployment uses HNSW or another index, relative costs change.
  • ad hoc to paper Tiptoe's published recall-boosting features (recursive cluster splitting, boundary double-assignment) can be disabled for comparison without changing the scheme's privacy or validity.
    Section 3 Implementation deviations. These exclusions are what put Tiptoe's recall at 0.11 to 0.28 instead of its published operating point.
  • domain assumption BNTM's LPN parameters instantiate 128-bit security via the original paper's heuristic.
    Section 3: "we could not certify the concrete security level of the resulting tuple." The 22x cost claim and the security claim both depend on this unverified parameter choice.
  • domain assumption E5-base-v2 embeddings are unit-normalised so L2 ranking equals inner-product ranking, allowing one ground truth for all schemes.
    Stated in Section 3 Workload. If embeddings are not exactly unit-normalised in the implementation, the shared ground truth could be inconsistent.
  • ad hoc to paper k-means cluster-size dispersion is roughly scale-invariant for the same data distribution.
    Section A.2, Table 6 note: the 8.8M m_max is projected from the 100k max-to-mean ratio; Tiptoe's 8.8M communication rows are never measured.
  • domain assumption The hardness assumptions (LWE, LPN, secret dual codes) are computationally infeasible at 128-bit level.
    Invoked in Section 2.3 and per-scheme parameters; the benchmark adopts the source papers' security arguments and does not re-derive them.

how reviews work

0 comments
Cite this review

Pith. "Pith review of A Unified Benchmark for Privacy-preserving Vector Search." pith.science (2026). https://pith.science/paper/IDSMBUHM

@misc{pith2026260801192,
  author       = {Pith},
  title        = {Pith review of: A Unified Benchmark for Privacy-preserving Vector Search},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/IDSMBUHM}},
  note         = {Machine review of arXiv:2608.01192}
}
read the original abstract

Vector search powers semantic search, recommendation systems, and retrieval-augmented generation (RAG). By design, the service answering a query sees both the query embedding and, usually, the corpus against which it is matched. This is a privacy breach for both the user issuing the query and the owner of the corpus. A family of cryptographic schemes (e.g., SAP, EMVP, BNTM, Tip-toe) addresses that leak. However, as each scheme is published and evaluated on its own corpus, threat model, parameter choices, hardware, and metric conventions, the numbers cannot be compared directly. Consequently, a practitioner asking which one to deploy today has no defensible way to choose. We close that gap with a uniform experimental comparison, including a Plaintext baseline and four cryptographic backends running over the same workload, hardware, and metric definitions. Under that ruler, the schemes spread across a Pareto frontier in privacy, performance, and recall rather than imposing a flat penalty on performance. We find that the performance of SAP matches Plaintext, EMVP delivers cryptographic indistinguishability at a 4x throughput cost on CPU, BNTM adds malicious-server verifiability at a further 22x median-latency cost, and Tiptoe hides the cluster choice itself, but incurs a 190x per-query cost compared to Plaintext. GPU acceleration pays off for Plaintext and SAP but not for EMVP or BNTM. All our experiment artifacts are publicly available for reproducibility

Figures

Figures reproduced from arXiv: 2608.01192 by the authors.

Figure 1
Figure 1. Comparing the five schemes on privacy guarantees and computational overhead. Each marker adds privacy guarantees [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. The four steps performed by the client and server [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗
Figure 3
Figure 3. Communication between the client and server, and the performed operations during each of the four privacy [PITH_FULL_IMAGE:figures/full_fig_p004_3.png] view at source ↗
Figures from the paper (10 more)
Figure 4
Figure 4. Figure 4: Recall@10 vs. sustained throughput (with a logarithmic horizontal axis). (a) MS MARCO-100k on [PITH_FULL_IMAGE:figures/full_fig_p007_4.png]
Figure 5
Figure 5. Figure 5: Per-query latency cumulative distribution function [PITH_FULL_IMAGE:figures/full_fig_p008_5.png]
Figure 6
Figure 6. Figure 6: Per-query latency on MS MARCO-100k. (a) The distribution of E2E query latency for each of the five schemes; all [PITH_FULL_IMAGE:figures/full_fig_p010_6.png]
Figure 7
Figure 7. Figure 7: Privacy knobs in SAP and BNTM. (a) The effect of varying SAP’s perturbation strength 𝛽 from 0 (no privacy) to 1 on recall@10, on MS MARCO-8.8M. For reference, the recall@10 of Plaintext is 0.925 (dotted line). (b) BNTM per-query time breakdown at nprobe = 32, with and …
Figure 9
Figure 9. Figure 9: The time (in seconds) to build the index for each [PITH_FULL_IMAGE:figures/full_fig_p011_9.png]
Figure 8
Figure 8. Figure 8: Performance of our schemes when increasing the [PITH_FULL_IMAGE:figures/full_fig_p011_8.png]
Figure 11
Figure 11. Figure 11: is the methodological sanity check that lets the body attribute per-scheme cost differences to the cryptographic primi￾tive rather than to the index structure. All schemes except Tiptoe overlay on the recall vs nprobe curve because every scheme rides the same plaintex…
Figure 10
Figure 10. Figure 10: Parallel scaling on a dual-socket Xeon Gold 6426Y [PITH_FULL_IMAGE:figures/full_fig_p014_10.png]
Figure 12
Figure 12. Figure 12: Recall@10 vs. sustained throughput, all schemes [PITH_FULL_IMAGE:figures/full_fig_p014_12.png]
Figure 13
Figure 13. Figure 13: plots recall against the analytical eff-bytes/q proxy from [PITH_FULL_IMAGE:figures/full_fig_p015_13.png]

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

49 extracted references · 27 canonical work pages

  1. [1]

    Sebastian Angel, Hao Chen, Kim Laine, and Srinath Setty. 2018. PIR with Com- pressed Queries and Amortized Query Processing. In2018 IEEE Symposium on Security and Privacy (SP). doi:10.1109/SP.2018.00062

    arXiv 2018

  2. [2]

    Martin Aumüller, Erik Bernhardsson, and Alexander Faithfull. 2020. ANN- Benchmarks: A benchmarking tool for approximate nearest neighbor algorithms. Information Systems87 (2020). doi:10.1016/j.is.2019.02.006

    doi:10.1016/j.is.2019.02.006 2020

  3. [3]

    Fabrice Benhamouda, Caicai Chen, Shai Halevi, Yuval Ishai, Hugo Krawczyk, Tamer Mour, Tal Rabin, and Alon Rosen. 2025. Encrypted Matrix-Vector Products from Secret Dual Codes. InProceedings of the 2025 ACM SIGSAC Conference on Computer and Communications Security(Taipei, Taiwan)(CCS ’25). Association for Computing Machinery, New York, NY, USA. doi:10.1145...

    arXiv 2025

  4. [4]

    Avrim Blum, Merrick Furst, Michael Kearns, and Richard J. Lipton. 1994. Crypto- graphic Primitives Based on Hard Learning Problems. InAdvances in Cryptology — CRYPTO’ 93. Springer Berlin Heidelberg, Berlin, Heidelberg

    work page 1994

  5. [5]

    Avrim Blum, Adam Kalai, and Hal Wasserman. 2003. Noise-tolerant learning, the parity problem, and the statistical query model.J. ACM50, 4 (July 2003). doi:10.1145/792538.792543

    work page arXiv 2003

  6. [6]

    Alexandra Boldyreva, Nathan Chenette, Younho Lee, and Adam O’Neill. 2009. Order-Preserving Symmetric Encryption. InAdvances in Cryptology - EURO- CRYPT 2009. Springer Berlin Heidelberg, Berlin, Heidelberg

    work page 2009

  7. [7]

    Mark Braverman and Stephen Newman. 2026. Practical Secure Delegated Linear Algebra with Trapdoored Matrices. InTheory of Cryptography. Springer Nature Switzerland, Cham. arXiv:2502.13060

    work page arXiv 2026

  8. [8]

    Emma Dauterman, Vivian Fang, Ioannis Demertzis, Natacha Crooks, and Raluca Ada Popa. 2021. Snoopy: Surpassing the Scalability Bottleneck of Obliv- ious Storage. InProceedings of the ACM SIGOPS 28th Symposium on Operating Systems Principles(Virtual Event, Germany)(SOSP ’21). Association for Comput- ing Machinery, New York, NY, USA. doi:10.1145/3477132.3483562

    arXiv 2021

Show all 49 references
  1. [9]

    Daniel Demmler, Peter Rindal, Mike Rosulek, and Ni Trieu. 2018. PIR-PSI: Scaling Private Contact Discovery.Proc. Priv. Enhancing Technol.2018, 4 (2018). doi:10. 1515/POPETS-2018-0037

    2018

  2. [10]

    Junfeng Fan and Frederik Vercauteren. 2012. Somewhat Practical Fully Ho- momorphic Encryption. Cryptology ePrint Archive, Paper 2012/144. https: //eprint.iacr.org/2012/144

    2012

  3. [11]

    Zhangyin Feng, Daya Guo, Duyu Tang, Nan Duan, Xiaocheng Feng, Ming Gong, Linjun Shou, Bing Qin, Ting Liu, Daxin Jiang, et al. 2020. Codebert: A pre-trained 12 model for programming and natural languages. InFindings of the association for computational linguistics: EMNLP 2020. ...

    2020

  4. [12]

    R¯usin, š Freivalds. 1979. Fast probabilistic algorithms. InInternational Symposium on Mathematical Foundations of Computer Science. Springer, 57–69

    1979

  5. [13]

    Georg Fuchsbauer, Riddhi Ghosal, Nathan Hauke, and Adam O’Neill. 2021. Ap- proximate Distance-Comparison-Preserving Symmetric Encryption. Cryptology ePrint Archive, Paper 2021/1666. https://eprint.iacr.org/2021/1666

    2021

  6. [14]

    Paul Grubbs, Kevin Sekniqi, Vincent Bindschaedler, Muhammad Naveed, and Thomas Ristenpart. 2017. Leakage-Abuse Attacks against Order-Revealing Encryption. In2017 IEEE Symposium on Security and Privacy (SP). 655–672. doi:10.1109/SP.2017.44

    2017 doi

  7. [15]

    Alexandra Henzinger, Emma Dauterman, Henry Corrigan-Gibbs, and Nickolai Zeldovich. 2023. Private Web Search with Tiptoe. InProceedings of the 29th Sympo- sium on Operating Systems Principles(Koblenz, Germany)(SOSP ’23). Association for Computing Machinery, New York, NY, USA. d...

    2023

  8. [16]

    Hong, Henry Corrigan-Gibbs, Sarah Meik- lejohn, and Vinod Vaikuntanathan

    Alexandra Henzinger, Matthew M. Hong, Henry Corrigan-Gibbs, Sarah Meik- lejohn, and Vinod Vaikuntanathan. 2023. One Server for the Price of Two: Simple and Fast Single-Server Private Information Retrieval. In32nd USENIX Security Symposium (USENIX Security 23). USENIX Associati...

    2023

  9. [17]

    Piotr Indyk and Rajeev Motwani. 1998. Approximate nearest neighbors: towards removing the curse of dimensionality. InProceedings of the thirtieth annual ACM symposium on Theory of computing. 604–613

    1998

  10. [18]

    Suhas Jayaram Subramanya, Fnu Devvrit, Harsha Vardhan Simhadri, Ravishankar Krishnawamy, and Rohan Kadekodi. 2019. DiskANN: Fast Accurate Billion-point Nearest Neighbor Search on a Single Node. InAdvances in Neural Information Processing Systems, Vol. 32. Curran Associates, In...

    2019

  11. [19]

    Herve Jégou, Matthijs Douze, and Cordelia Schmid. 2011. Product Quantization for Nearest Neighbor Search.IEEE Transactions on Pattern Analysis and Machine Intelligence33, 1 (2011). doi:10.1109/TPAMI.2010.57

    2011 doi

  12. [20]

    Vladimir Karpukhin, Barlas Oguz, Sewon Min, Patrick Lewis, Ledell Wu, Sergey Edunov, Danqi Chen, and Wen-tau Yih. 2020. Dense passage retrieval for open- domain question answering. InProceedings of the 2020 conference on empirical methods in natural language processing (EMNLP)...

    2020

  13. [21]

    Kevin Lewi and David J. Wu. 2016. Order-Revealing Encryption: New Con- structions, Applications, and Lower Bounds. InProceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security(Vienna, Aus- tria)(CCS ’16). Association for Computing Machinery, New York...

    2016

  14. [22]

    Patrick Lewis, Ethan Perez, Aleksandra Piktus, Fabio Petroni, Vladimir Karpukhin, Naman Goyal, Heinrich Küttler, Mike Lewis, Wen-tau Yih, Tim Rock- täschel, et al. 2020. Retrieval-augmented generation for knowledge-intensive nlp tasks.Advances in neural information processing ...

    2020

  15. [23]

    S. Lloyd. 1982. Least squares quantization in PCM.IEEE Transactions on Infor- mation Theory28, 2 (1982), 129–137. doi:10.1109/TIT.1982.1056489

    1982

  16. [24]

    Malkov and D

    Yu A. Malkov and D. A. Yashunin. 2020. Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs. IEEE Transactions on Pattern Analysis and Machine Intelligence42, 4 (2020). doi:10. 1109/TPAMI.2018.2889473

    2020

  17. [25]

    Carlos Aguilar Melchor, Joris Barrier, Laurent Fousse, and Marc-Olivier Killijian

  18. [26]

    John Morris, Volodymyr Kuleshov, Vitaly Shmatikov, and Alexander Rush. 2023. Text Embeddings Reveal (Almost) As Much As Text. InProceedings of the 2023 Conference on Empirical Methods in Natural Language Processing. Association for Computational Linguistics, Singapore. doi:10....

    2023 doi

  19. [27]

    Muhammad Naveed, Seny Kamara, and Charles V. Wright. 2015. Inference Attacks on Property-Preserving Encrypted Databases. InProceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security (CCS) (CCS ’15). Association for Computing Machinery, 644–655. doi:1...

    2015 doi

  20. [28]

    Sameer A Nene and Shree K Nayar. 1997. A simple algorithm for nearest neighbor search in high dimensions.IEEE Transactions on pattern analysis and machine intelligence19, 9 (1997), 989–1003

    1997

  21. [29]

    Tri Nguyen, Mir Rosenberg, Xia Song, Jianfeng Gao, Saurabh Tiwary, Rangan Majumder, and Li Deng. 2016. MS MARCO: A Human Generated MAchine Reading COmprehension Dataset.CoRR(2016). arXiv:1611.09268

    2016 arXiv

  22. [30]

    OpenAI. 2026. File Search. https://platform.openai.com/docs/assistants/tools/ file-search Accessed May 2026

    2026

  23. [31]

    James Jie Pan, Jianguo Wang, and Guoliang Li. 2024. Survey of vector database management systems.The VLDB Journal33, 5 (2024), 1591–1615

    2024

  24. [32]

    Krzysztof Pietrzak. 2012. Cryptography from Learning Parity with Noise. InSOF- SEM 2012: Theory and Practice of Computer Science. Springer Berlin Heidelberg, Berlin, Heidelberg

    2012

  25. [33]

    Pinecone. 2026. Pinecone Vector Database. https://www.pinecone.io/ Accessed May 2026

    2026

  26. [34]

    Li, and Nickolai Zeldovich

    Raluca Ada Popa, Frank H. Li, and Nickolai Zeldovich. 2013. An Ideal-Security Protocol for Order-Preserving Encoding. In2013 IEEE Symposium on Security and Privacy. doi:10.1109/SP.2013.38

    2013 doi

  27. [35]

    Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sand- hini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, et al

  28. [36]

    Shashank Rajput, Nikhil Mehta, Anima Singh, Raghunandan Hulikal Keshavan, Trung Vu, Lukasz Heldt, Lichan Hong, Yi Tay, Vinh Q Tran, Jonah Samost, et al. 2023. Recommender systems with generative retrieval. InThirty-seventh Conference on Neural Information Processing Systems

    2023

  29. [37]

    Oded Regev. 2009. On lattices, learning with errors, random linear codes, and cryptography.J. ACM56, 6, Article 34 (Sept. 2009). doi:10.1145/1568318.1568324

    2009

  30. [38]

    Nils Reimers, I Sentence-BERT Gurevych, et al. 2019. Sentence embeddings using siamese BERT-networks.arXiv preprint arXiv:1908.10084(2019)

    2019 arXiv

  31. [39]

    Harsha Vardhan Simhadri, George Williams, Martin Aumüller, Matthijs Douze, Artem Babenko, Dmitry Baranchuk, Qi Chen, Lucas Hosseini, Ravishankar Krishnaswamny, Gopal Srinivasa, Suhas Jayaram Subramanya, and Jingdong Wang. 2022. Results of the NeurIPS’21 Challenge on Billion-Sc...

    2022

  32. [40]

    Sivic and Zisserman. 2003. Video Google: a text retrieval approach to object matching in videos. InProceedings Ninth IEEE International Conference on Com- puter Vision. doi:10.1109/ICCV.2003.1238663

    2003 arXiv

  33. [41]

    Congzheng Song and Ananth Raghunathan. 2020. Information leakage in em- bedding models. InProceedings of the 2020 ACM SIGSAC conference on computer and communications security. 377–390

    2020

  34. [42]

    Yu-Che Tsai, Hsiang Hsiao, Kuan-Yu Chen, and Shou-De Lin. 2026. Concept- Aware Privacy Mechanisms for Defending Embedding Inversion Attacks. In International Conference on Learning Representations (ICLR)

    2026

  35. [43]

    Vinod Vaikuntanathan and Or Zamir. 2025. Improving Algorithmic Efficiency using Cryptography. arXiv:2502.13065 [cs.CR]

    2025 arXiv

  36. [44]

    Frank Wang, Catherine Yun, Shafi Goldwasser, Vinod Vaikuntanathan, and Matei Zaharia. 2017. Splinter: Practical Private Queries on Public Data. In14th USENIX Symposium on Networked Systems Design and Implementation (NSDI 17). USENIX Association, Boston, MA. https://www.usenix....

    2017

  37. [45]

    Liang Wang, Nan Yang, Xiaolong Huang, Binxing Jiao, Linjun Yang, Daxin Jiang, Rangan Majumder, and Furu Wei. 2022. Text Embeddings by Weakly-Supervised Contrastive Pre-training.CoRR(2022). arXiv:2212.03533

    2022 arXiv

  38. [46]

    Beekman, Raluca Ada Popa, Joseph E

    Wenting Zheng, Ankur Dave, Jethro G. Beekman, Raluca Ada Popa, Joseph E. Gonzalez, and Ion Stoica. 2017. Opaque: An Oblivious and Encrypted Distributed Analytics Platform. In14th USENIX Symposium on Networked Systems Design and Implementation (NSDI 17). USENIX Association, Bos...

    2017

  39. [47]

    how aggressive does the probe set need to be to reach 𝑋 %recall

    Wanjun Zhong, Lianghong Guo, Qiqi Gao, He Ye, and Yanlin Wang. 2024. Memo- rybank: Enhancing large language models with long-term memory. InProceedings of the AAAI conference on artificial intelligence, Vol. 38. 19724–19731. A APPENDIX This appendix collects figures that suppl...

    2024

  40. [2016]

    XPIR : Private Information Retrieval for Everyone.Proc. Priv. Enhancing Technol.2016, 2 (2016). doi:10.1515/POPETS-2016-0010

    2016 doi

  41. [2021]

    In International conference on machine learning

    Learning transferable visual models from natural language supervision. In International conference on machine learning. PmLR, 8748–8763

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.