Databases · arXiv:2611.16516 v1 · submitted 12 Nov 2026 · 57 references
Authenticated Approximate Nearest Neighbor Search in Outsourced Vector Databases
The paper says
“Approximate Nearest Neighbor (ANN) search has become a fundamental query primitive in modern vector databases for managing large-scale embedding data. To support growing vector collections, organizations increasingly outsource database management and query processing to third-party clouds.”
more of the abstract
However, untrusted service providers may return suboptimal or fabricated results, posing a serious threat to ANN search integrity. Existing authenticated ANN approaches face substantial scalability challenges. They typically require transmitting high-dimensional vectors for distance verification and rely on topology-agnostic authentication structures, resulting in excessive communication and verification overhead. In this paper, we propose VIDA, a novel and efficient scheme for authenticated graph-based ANN search. VIDA replaces raw vector transmission with compact vector commitments and employs an aggregated Inner Product Argument to efficiently verify multiple distance computations. Furthermore, we introduce MeST, a topology-aware authenticated data structure that aligns authentication paths with graph traversal, significantly reducing structural proof overhead. Additionally, we design a quantization-aware authentication strategy that exploits distance bounds for pruning, reducing the number of exact distances requiring cryptographic authentication. Extensive experiments demonstrate that the proposed schemes substantially improve the efficiency of authenticated ANN search, achieving up to a 6.6 × speedup in end-to-end latency and reducing data transfer time by up to 99.2% compared with state-of-the-art methods.
from the abstract
Pith says
Machine review · deepseek-v4-flash · 13 Nov 2026 · what was read was not recorded · not checked by a person
It can be wrong. Challenge this review or reply to it.
Holds up, with conditions. Well-engineered system with impressive latency results, but the security proof for the aggregated IPA protocol has a gap that should be addressed before acceptance. This line is wrong
2 major objections · 5 minor
How often objections from reviews like this one are right: not yet measured
Not checked: figures, code, what the 57 references say.
The paper says, at Appendix B, Theorem 7.1
The review did not quote this passage.
Pith says: Objection 1 of 2 · major
The knowledge-soundness proof of the IPA aggregation protocol relies on rewinding the adversary to obtain n transcripts and then solving a Vandermonde system. The authors state that 'while extending to n branches introduces a polynomial reduction loss, the success probability remains non-negligible for polynomial n,' but they do not provide a concrete bound or analysis.
more of objection 1
For the Forking Lemma, the extractor's success probability is typically ε' ≥ ε^n / poly(λ). In practical deployments, n (the number of visited nodes) can be thousands (e.g., high-recall scenarios on OpenAI3072). Even if ε is non-negligible (e.g., 1/λ), ε' becomes negligible for n ≥ 2. Thus the claimed knowledge soundness does not hold for the parameter regime targeted by VIDA. This is a load-bearing issue: the security of the entire scheme depends on the aggregation protocol being secure. The authors must either provide a proof with tighter bound (e.g., constant-size aggregation by reducing n, or using a different technique like batch proofs with logarithmic dependence) or explicitly analyze how the extractor's success probability depends on n and justify that it remains non-negligible for the maximum n encountered in their experiments.
The paper says, at Appendix B, Theorem 7.1
The review did not quote this passage.
Pith says: Objection 2 of 2 · major
The proof sketch assumes the extractor can obtain n valid transcripts with distinct challenges from an adversary that succeeds with non-negligible probability. However, the General Forking Lemma typically requires that the adversary's success probability is at least (some polynomial factor) to obtain two transcripts; extending to n transcripts would require either a more complex lemma or a different approach.
more of objection 2
The paper does not cite or include a version of the Forking Lemma that provides n forks with only polynomial loss. The extractor construction therefore lacks a rigorous foundation.
5 minor objections
The paper says, at Section II, Definition 2.1
Pith says: minor objection 1 of 5
The security definition references an ideal result from a 'deterministic ANN algorithm,' but ANN algorithms are inherently approximate. The definition should clarify that the ideal result is the output of a designated deterministic algorithm (e.g., HNSW with fixed parameters) rather than the exact nearest neighbors. The text implicitly assumes this, but making it explicit would avoid confusion.
The paper says, at Section IV-C, Equation (1)
Pith says: minor objection 2 of 5
The Fiat-Shamir challenge in Equation (1) is computed as r = H(C_q | C_1 | IP_1 | ... | C_n | IP_n). For security, the adversary's view should include all commitments and inner products. However, the inner products IP_i are claimed values that the prover computes; if they are included before verification, the adversary could choose them adaptively. The proof should address that the challenge is bound to these values via the hash.
show 3 more
The paper says, at Section VIII-A
Pith says: minor objection 3 of 5
The experimental section states that the source code is available, but it is not checked whether the implementation includes all cryptographic primitives (e.g., Bulletproofs with Ristretto255). This is a minor reproducibility concern.
The paper says, at Table I
Pith says: minor objection 4 of 5
The notation table lists symbols but does not include definitions for some used in Section VI (e.g., η_j, H_exaj, H_quaj). Adding these would improve readability.
The paper says, at Appendix D
Pith says: minor objection 5 of 5
Figure 13 and 14 are duplicates of earlier figures; it would be clearer to present only unique additional results rather than repeating the same panels.
What would settle it
Derive the extractor's success probability for the aggregated IPA protocol from Appendix B, using the standard General Forking Lemma (Pointcheval‑Stern) and the concrete parameters from the experiments: n ≈ 1000, security parameter λ = 128. Compute the maximum adversary advantage ε for which the extractor still succeeds with non‑negligible probability. If ε must be ≥ 0.99 for n=1000, then the proof is insufficient; if ε can be plausibly small (e.g., 2^{-80}), the proof collapses.
from the skeptic's reading
How the review went
4 readings by deepseek-v4-flash · 13 Nov 2026
- Reader holds up, with conditions
- Skeptic partly agrees
- Editor wrote the verdict above
- Referee major revision: 2 major objections, 5 minor
Not run on this paper: the simulated authors' defence.
Pith did not check this review's objections against the paper.
The review in full
The review in brief, machine-written
This paper tackles a real and timely problem—authenticating approximate nearest neighbor search in outsourced vector databases. The authors propose VIDA, which combines vector commitments, an aggregated inner-product argument (IPA), and a topology-aware Merkle spanning tree (MeST). The engineering is solid and the experimental evaluation is the strongest part: VIDA achieves up to 6.6× end-to-end speedup and reduces data transfer by 99.2% over baselines on high-dimensional datasets. The ablation study shows that both aggregation and MeST contribute meaningfully. The paper is clearly written and the problem is well-motivated.
However, the security proof for the core aggregation primitive has a gap that warrants careful consideration. The stress-test note is on point: the knowledge-soundness proof in Appendix B rewinds the adversary n times to obtain n transcripts, then solves a Vandermonde system. The authors claim that extending to n branches introduces a polynomial reduction loss and that success probability remains non-negligible for polynomial n. But the standard Forking Lemma gives a bound of roughly εn / poly(λ). For realistic workloads where n is in the thousands (the number of visited nodes in high-recall search), this becomes negligible even if ε is non-negligible. The paper does not provide a concrete bound or justify why n is small enough. This is not a minor oversight; it affects the entire security claim of the scheme. A plausible fix would be to use a different aggregation technique that avoids exponential dependence, or to restrict the aggregation to smaller batches with a formal argument.
Other concerns are minor. The paper does not discuss timing side channels from proof generation, and the offline construction overhead is non-trivial (5× build time over baselines), but these are acceptable trade-offs. The quantization-aware variant shows limited gains under low recall or low-dimensional settings, which the authors honestly acknowledge in Appendix E.
Overall, this is a serious piece of work that deserves a proper peer review. The experimental results are compelling, but the security proof needs to be tightened before it can be trusted. I would bring this to a reading group with the caveat that the proof is under scrutiny, and I would cite it only after the security analysis is resolved.
The strongest objection
The security of VIDA's core aggregation primitive depends on the claim that the aggregation protocol satisfies computational knowledge soundness (Theorem 7.1). The proof in Appendix B uses the General Forking Lemma to rewind the adversary n times, obtaining n valid transcripts with distinct Fiat‑Shamir challenges. The extractor then solves a Vandermonde system to recover the individual witnesses. The authors state that ‘while extending to n branches introduces a polynomial reduction loss, the success probability remains non‑negligible for polynomial n.’ This statement is not justified with a concrete bound. The Forking Lemma typically gives a reduction of the form ε' ≥ ε^n / poly(λ), where ε is the original adversary advantage and ε' is the extractor's advantage. For realistic workloads, n (the number of visited nodes) can be in the thousands (e.g., high‑recall search on OpenAI3072). If ε is, say, 1/λ (non‑negligible), then ε' ≈ (1/λ)^n, which is negligible for n ≥ 2. Thus the extractor's success probability may be negligible, and the knowledge soundness argument fails for the parameter regime in which the scheme is deployed. The paper does not address this issue or provide an alternative proof technique that avoids exponential dependence on n.
The reader identified the lack of concrete security bounds and reliance on rewinding as the weakest assumption. My concern sharpens this: the proof's exponential dependence on n creates a concrete gap for the parameter sizes used in the experiments. However, the overall scheme is still likely sound because other knowledge‑sound arguments for batch proofs (e.g., Bulletproofs aggregation) use more robust techniques (e.g., splitting lemmas with polynomial loss). The paper could address this by either adopting a different aggregation scheme with a tighter reduction or by explicitly bounding n to a small constant and arguing that visited sets remain small. The empirical results are strong, and the problem is well‑motivated. Therefore, I do not change the verdict; the paper remains conditionally acceptable subject to a tightened security analysis or an explicit discussion of the reduction loss for practical n.
The referee's report
If the security proofs hold, VIDA represents a significant advance in verifiable outsourced ANN search, addressing the bandwidth bottleneck that has limited prior approaches. The combination of vector commitments, aggregated IPA, topology-aware ADS, and quantization-aware pruning is novel and practically motivated. The experimental evaluation is thorough and demonstrates clear improvements over baselines on diverse datasets and network conditions.
Pith's reading of the paper (a machine's summary, not the authors')
The paper aims to solve the problem of verifying the integrity of approximate nearest neighbor search when the vector database is outsourced to an untrusted cloud. Existing solutions require transmitting entire high-dimensional vectors to the client for distance recomputation, causing severe bandwidth bottlenecks. VIDA replaces raw vectors with compact Pedersen commitments and uses an aggregated inner product argument to verify distances without revealing the vectors. Additionally, a topology-aware Merkle spanning tree (MeST) aligns the authentication structure with the graph traversal pattern, reducing structural proof size. The paper demonstrates up to a 6.6× end-to-end latency improvement and 99.2% reduction in data transfer time over prior methods.
What carries the argument. The key machinery is threefold: (1) vector commitments (Pedersen commitments) that bind to a vector without revealing it, (2) an aggregated inner product argument (AggIPA) that batch-verifies multiple inner products between the query vector and visited data vectors using a single proof, and (3) the MeST index, a Merkle tree built as a distance-aware minimum spanning tree of the proximity graph, which places co-visited nodes close together in the tree to minimize proof size.
Core claim. The central discovery is that by combining vector commitments with an aggregated inner product argument, the client can authenticate distance computations for all visited graph nodes from a single compact proof, eliminating the transmission of high-dimensional vectors. Moreover, constructing the Merkle authentication tree as a distance-aware spanning tree of the proximity graph significantly compresses the structural authentication paths for frequently co-visited nodes. Together these techniques make verifiable ANN search practical for large-scale high-dimensional datasets.
The premise it rests on. The security of the aggregated IPA protocol relies on the random oracle model and the discrete logarithm assumption; if either is broken, the verification can be forged. Additionally, the proof for aggregation requires rewinding the adversary a polynomial number of times, which assumes the adversary's success probability remains non-negligible after rewinding.
If the paper is right (Pith's inferences, not the authors')
Outsourced vector databases can now offer verifiable ANN search with latency comparable to unauthenticated search, enabling trust in cloud-based retrieval-augmented generation and recommendation systems.
The aggregation technique reduces client-side verification cost from linear in the number of visited nodes to nearly constant, making high-recall searches feasible even on bandwidth-constrained networks.
MeST's topology-aware construction generalizes to other graph-based query verification problems beyond ANN, such as shortest-path or subgraph queries.
The quantization-aware extension further reduces the number of exact-distance authentications, extending the approach to scenarios with extremely limited bandwidth or device memory.
The IPA aggregation proof could likely be further compressed using recursive SNARKs, potentially reducing proof size below the current constant-size implementation and lowering verification time further.
MeST's distance-aware spanning tree could be adapted for verifiable graph navigation in other contexts, such as authenticated shortest-path queries on road networks or provenance tracking in graph databases.
The security model assumes an honest data owner and client; a malicious client colluding with the cloud could break verification in weaker trust models, so practical deployments may need additional safeguards against client-side attacks.
Check this review
Pith stored no record of this review's passes and took no fingerprint of it. Reviews made by code from 13 Nov 2026 on carry both.
How often reviews like this one are right
Reviews like this one: written by deepseek-v4-flash, where what was read was not recorded.
How often objections from reviews like this one are right: not yet measured
Reviews by people
This review was written by a machine. No person has reviewed this paper on Pith yet. A scientist listed on Pith can review it for a fee, and their review is published here whatever it concludes.
The paper
Abstract
Approximate Nearest Neighbor (ANN) search has become a fundamental query primitive in modern vector databases for managing large-scale embedding data. To support growing vector collections, organizations increasingly outsource database management and query processing to third-party clouds. However, untrusted service providers may return suboptimal or fabricated results, posing a serious threat to ANN search integrity. Existing authenticated ANN approaches face substantial scalability challenges. They typically require transmitting high-dimensional vectors for distance verification and rely on topology-agnostic authentication structures, resulting in excessive communication and verification overhead. In this paper, we propose VIDA, a novel and efficient scheme for authenticated graph-based ANN search. VIDA replaces raw vector transmission with compact vector commitments and employs an aggregated Inner Product Argument to efficiently verify multiple distance computations. Furthermore, we introduce MeST, a topology-aware authenticated data structure that aligns authentication paths with graph traversal, significantly reducing structural proof overhead. Additionally, we design a quantization-aware authentication strategy that exploits distance bounds for pruning, reducing the number of exact distances requiring cryptographic authentication. Extensive experiments demonstrate that the proposed schemes substantially improve the efficiency of authenticated ANN search, achieving up to a 6.6 × speedup in end-to-end latency and reducing data transfer time by up to 99.2% compared with state-of-the-art methods.
The paper's own sentences, arranged, kept beside the review and separate from it. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. No sentence in this record was written by a model.
abstract compiled · 2026-11-13
The authors' main claim, as the classifier picked it out 1.00
“Extensive experiments demonstrate that the proposed schemes substantially improve the efficiency of authenticated ANN search, achieving up to a $6.6\times$ speedup in end-to-end latency and reducing data transfer time by up to 99.2% compared with state-of-the-art methods.”
How the main claim is stated: asserted 1.00
What the abstract itself states, as probabilities: claims first 0.07 · states limitation 0.07 · human participants 0.02 · controlled comparison 0.65 · randomized assignment 0.01 · states quantitative result 0.99 · compares with prior results 0.97 · mentions code or data availability 0.02
The abstract, sentence by sentence
This table labels the abstract only (arXiv listing abstract v1). The number is the probability the classifier gave the label.
| Sentence | Role | The authors' own work | States the main conclusion | Strength |
|---|---|---|---|---|
| Approximate Nearest Neighbor (ANN) search has become a fundamental query primitive in modern vector databases for managing large-scale embedding data. | background 1.00 | 0.05 | 0.01 | asserted 1.00 |
| To support growing vector collections, organizations increasingly outsource database management and query processing to third-party clouds. | background 1.00 | 0.04 | 0.01 | asserted 0.97 |
| However, untrusted service providers may return suboptimal or fabricated results, posing a serious threat to ANN search integrity. | background 0.91 | 0.05 | 0.02 | hedged possibility 0.93 |
| Existing authenticated ANN approaches face substantial scalability challenges. | gap 0.75 | 0.05 | 0.02 | asserted 1.00 |
| They typically require transmitting high-dimensional vectors for distance verification and rely on topology-agnostic authentication structures, resulting in excessive communication and verification overhead. | gap 0.75 | 0.04 | 0.02 | asserted 1.00 |
| In this paper, we propose VIDA, a novel and efficient scheme for authenticated graph-based ANN search. | contribution 1.00 | 0.89 | 0.14 | asserted 1.00 |
| VIDA replaces raw vector transmission with compact vector commitments and employs an aggregated Inner Product Argument to efficiently verify multiple distance computations. | method 0.85 | 0.93 | 0.08 | asserted 1.00 |
| Furthermore, we introduce MeST, a topology-aware authenticated data structure that aligns authentication paths with graph traversal, significantly reducing structural proof overhead. | contribution 0.80 | 0.94 | 0.05 | asserted 1.00 |
| Additionally, we design a quantization-aware authentication strategy that exploits distance bounds for pruning, reducing the number of exact distances requiring cryptographic authentication. | contribution 0.62 | 0.94 | 0.03 | asserted 1.00 |
| Extensive experiments demonstrate that the proposed schemes substantially improve the efficiency of authenticated ANN search, achieving up to a $6.6\times$ speedup in end-to-end latency and reducing data transfer time by up to 99.2% compared with state-of-the-art methods. | result 1.00 | 0.97 | 0.86 | asserted 1.00 |
What kind of paper the classifier reports this is: method or tool 1.00 · evidence from observation or experiment 0.99
What was examined, and what was not
Sources read
- arXiv listing abstract v1
Not examined
- full text
- figures and tables
- references and citing sentences
- relations to other papers
Levels run
- P abstract
Not run
- S sections
- T body sentences
- C citations
- R cross-paper relations
How the labels were made
Compiled by classifier-1.13.0 via TypeSafe API, question bank abstract-p1-20260923, 2026-11-13: 1 request, 7,488 input tokens.
Every quoted sentence on this record is the authors'. Every label is from Pith's closed vocabulary, with the probability shown beside it. This record as JSON
Figures (15)
Showing 13 of the paper's 15 figures. Figures are the authors', reproduced from the paper.
References (57)
- [1] “Milvus,” https://milvus.io, [Accessed: 2026-6-1] on Pith
- [2] “Qdrant,” https://qdrant.tech, [Accessed: 2026-6-1] on Pith
- [3] “Weaviate,” https://weaviate.io, [Accessed: 2026-6-1] on Pith
- [4] P. Lewis, E. Perez, A. Piktus, F. Petroni, V . Karpukhin, N. Goyal, H. K ¨uttler, M. Lewis, W.-t. Yih, T. Rockt ¨aschelet al., “Retrieval- augmented generation for knowledge-intensive NLP tasks,”Proc. Adv. Neural Inf. Process. Syst., vol. 33, pp. 9459–9474, 2020 on Pith
- [5] S. Zhang, L. Yao, A. Sun, and Y . Tay, “Deep learning based recom- mender system: A survey and new perspectives,”ACM Comput. Surv., vol. 52, no. 1, pp. 1–38, 2019 on Pith
- [6] V . Karpukhin, B. Oguz, S. Min, P. S. Lewis, L. Wu, S. Edunov, D. Chen, and W.-t. Yih, “Dense passage retrieval for open-domain question answering,” inProc. Conf. Empir. Methods Nat. Lang. Process. (EMNLP), 2020, pp. 6769–6781 on Pith
- [7] Y . Liu, J. Cui, Z. Huang, H. Li, and H. T. Shen, “SK-LSH: An efficient index structure for approximate nearest neighbor search,”Proc. VLDB Endow., vol. 7, no. 9, pp. 745–756, 2014 on Pith
- [8] H. Jegou, M. Douze, and C. Schmid, “Product quantization for nearest neighbor search,”IEEE Trans. Pattern Anal. Mach. Intell., vol. 33, no. 1, pp. 117–128, 2010 on Pith
- [9] Y . A. Malkov and D. A. Yashunin, “Efficient and robust approxi- mate nearest neighbor search using hierarchical navigable small world graphs,”IEEE Trans. Pattern Anal. Mach. Intell., vol. 42, no. 4, pp. 824–836, 2018 on Pith
- [10] C. Fu, C. Xiang, C. Wang, and D. Cai, “Fast approximate nearest neighbor search with the navigating spreading-out graph,”Proc. VLDB Endow., vol. 12, no. 5, pp. 461–474, 2019 on Pith
- [11] J. J. Pan, J. Wang, and G. Li, “Survey of vector database management systems,”VLDB J., vol. 33, no. 5, pp. 1591–1615, 2024 on Pith
- [12] Y . Song, X. Zhou, C. S. Jensen, and J. Xu, “Vector search for the future: From memory-resident, static heterogeneous storage, to cloud- native architectures,” inProc. ACM Manage. Data, 2026 on Pith
- [13] Z. Niu, X. Tian, X. Peng, and X. Chen, “BlendHouse: A cloud-native vector database system in ByteHouse,” inProc. IEEE Int. Conf. Data Eng. (ICDE). IEEE, 2025, pp. 4332–4345 on Pith
- [14] N. Upreti, H. V . Simhadri, H. S. Sundar, K. Sundaram, S. Boshra, B. Perumalswamy, S. Atri, M. Chisholm, R. R. Singh, G. Yanget al., “Cost-effective, low latency vector search with azure cosmos db,”Proc. VLDB Endow., vol. 18, no. 12, pp. 5166–5183, 2025 on Pith
- [15] Y . Zhang, J. Katz, and C. Papamanthou, “IntegriDB: Verifiable SQL for outsourced databases,” inProc. ACM SIGSAC Conf. Comput. Commun. Secur. (CCS), 2015, pp. 1480–1491 on Pith
- [16] Y . Zhang, D. Genkin, J. Katz, D. Papadopoulos, and C. Papamanthou, “vSQL: Verifying arbitrary SQL queries over dynamic outsourced databases,” inProc. IEEE Symp. Secur. Privacy (SP). IEEE, 2017, pp. 863–880 on Pith
- [17] X. Li, C. Weng, Y . Xu, X. Wang, and J. Rogers, “ZKSQL: Verifiable and efficient query evaluation with zero-knowledge proofs,”Proc. VLDB Endow., vol. 16, no. 8, 2023 on Pith
- [18] L. Lu, Z. Wen, Y . Yuan, Q. He, J. Chen, and Z. Liu, “ANNProof: Build- ing a verifiable and efficient outsourced approximate nearest neighbor search system on blockchain,”Future Gener. Comput. Syst., vol. 156, pp. 206–220, 2024 on Pith
- [19] C. Wang, J. Zhang, X. Liu, K. Wei, and B. Feng, “Verifiable graph- based approximate nearest neighbor search,” inProc. Int. Conf. Adv. Data Min. Appl.Springer, 2024, pp. 3–17 on Pith
- [20] R. C. Merkle, “A certified digital signature,” inProc. CRYPTO. Springer, 1989, pp. 218–238 on Pith
show 37 more
- [21] “OpenAI3072,” https://huggingface.co/datasets/Qdrant/ dbpedia-entities-openai3-text-embedding-3-large-3072-1M, [Accessed: 2026-6-1] on Pith
- [22] C. Gentry, S. Halevi, and V . Lyubashevsky, “Practical non-interactive publicly verifiable secret sharing with thousands of parties,” inProc. EUROCRYPT. Springer, 2022, pp. 458–487 on Pith
- [23] J. Zhang, M. Su, X. Liu, and G. Wang, “Springproofs: Efficient inner product arguments for vectors of arbitrary length,” inProc. IEEE Symp. Secur. Privacy (SP). IEEE, 2024, pp. 3147–3164 on Pith
- [24] T. P. Pedersen, “Non-interactive and information-theoretic secure verifi- able secret sharing,” inProc. CRYPTO. Springer, 1991, pp. 129–140 on Pith
- [25] R. Henry and I. Goldberg, “Batch proofs of partial knowledge,” inProc. Appl. Cryptogr. Netw. Secur.Springer, 2013, pp. 502–517 on Pith
- [26] M. Bellare and P. Rogaway, “Random oracles are practical: A paradigm for designing efficient protocols,” inProc. ACM SIGSAC Conf. Comput. Commun. Secur. (CCS), 1993, pp. 62–73 on Pith
- [27] W. Zhou, Y . Lu, H. Li, and Q. Tian, “Scalar quantization for large scale image search,” inProc. ACM Int. Conf. Multimedia (MM). ACM, 2012, pp. 169–178 on Pith
- [28] J. Gao and C. Long, “RaBitQ: Quantizing high-dimensional vectors with a theoretical error bound for approximate nearest neighbor search,”Proc. ACM Manage. Data, vol. 2, no. 3, pp. 1–27, 2024 on Pith
- [29] B. B ¨unz, J. Bootle, D. Boneh, A. Poelstra, P. Wuille, and G. Maxwell, “Bulletproofs: Short proofs for confidential transactions and more,” in Proc. IEEE Symp. Secur. Privacy (SP). IEEE, 2018, pp. 315–334 on Pith
- [30] J. Bootle, A. Cerulli, P. Chaidos, J. Groth, and C. Petit, “Efficient zero- knowledge arguments for arithmetic circuits in the discrete log setting,” inProc. Annu. Int. Conf. Theory Appl. Cryptogr. Tech.Springer, 2016, pp. 327–357 on Pith
- [31] M. Wang, X. Xu, Q. Yue, and Y . Wang, “A comprehensive survey and experimental comparison of graph-based approximate nearest neighbor search,”Proc. VLDB Endow., vol. 14, no. 11, pp. 1964–1978, 2021 on Pith
- [32] K. Srinivasan, K. Raman, J. Chen, M. Bendersky, and M. Najork, “WIT: Wikipedia-based image text dataset for multimodal multilingual machine learning,” inProc. ACM SIGIR Int. Conf. Res. Dev. Inf. Retr., 2021, pp. 2443–2449 on Pith
- [33] C. Schuhmann, R. Vencu, R. Beaumont, R. Kaczmarczyk, C. Mullis, A. Katta, T. Coombes, J. Jitsev, and A. Komatsuzaki, “LAION-400M: Open dataset of clip-filtered 400 million image-text pairs,”arXiv preprint arXiv:2111.02114, 2021 on PithPith's reviewarXiv
- [34] “Wikipedia,” https://huggingface.co/datasets/Cohere/ wikipedia-2023-11-embed-multilingual-v3, [Accessed: 2026-6-1] on Pith
- [35] “Msmarco,” https://huggingface.co/datasets/Cohere/msmarco-v2. 1-embed-english-v3, [Accessed: 2026-6-1] on Pith
- [36] “Bulletproofs,” https://github.com/zkcrypto/bulletproofs, [Accessed: 2026-6-1] on Pith
- [37] “Toxiproxy,” https://github.com/Shopify/toxiproxy, [Accessed: 2026-6- 1] on Pith
- [38] X. Yang, H. Lin, Z. Li, F. Qian, X. Li, Z. He, X. Wu, X. Wang, Y . Liu, Z. Liao, D. Hu, and T. Xu, “Mobile access bandwidth in practice: Measurement, analysis, and implications,” inProc. ACM SIGCOMM Conf., 2022, pp. 114–128 on Pith
- [39] I. Azizi, K. Echihabi, and T. Palpanas, “Graph-based vector search: An experimental evaluation of the state-of-the-art,”Proc. ACM Manage. Data, vol. 3, no. 1, pp. 1–31, 2025 on Pith
- [40] K. Lu, M. Kudo, C. Xiao, and Y . Ishikawa, “HVS: Hierarchical graph structure based on voronoi diagrams for solving approximate nearest neighbor search,”Proc. VLDB Endow., vol. 15, no. 2, pp. 246–258, 2021 on Pith
- [41] W. Li, Y . Zhang, Y . Sun, W. Wang, M. Li, W. Zhang, and X. Lin, “Approximate nearest neighbor search on high dimensional data—experiments, analyses, and improvement,”IEEE Trans. Knowl. Data Eng., vol. 32, no. 8, pp. 1475–1488, 2019 on Pith
- [42] S. Jayaram Subramanya, F. Devvrit, H. V . Simhadri, R. Krishnawamy, and R. Kadekodi, “Diskann: Fast accurate billion-point nearest neighbor search on a single node,”Proc. Adv. Neural Inf. Process. Syst., vol. 32, 2019 on Pith
- [43] H. Ootomo, A. Naruse, C. Nolet, R. Wang, T. Feher, and Y . Wang, “Cagra: Highly parallel graph construction and approximate nearest neighbor search for GPUs,” inProc. IEEE Int. Conf. Data Eng. (ICDE). IEEE, 2024, pp. 4236–4247 on Pith
- [44] Y . Lin, K. Zhang, Z. He, Y . Jing, and X. S. Wang, “Survey of filtered approximate nearest neighbor search over the vector-scalar hybrid data,” arXiv preprint arXiv:2505.06501, 2025 on PithPith's reviewarXiv
- [45] C. Zhang, C. Xu, H. Wang, J. Xu, and B. Choi, “Authenticated keyword search in scalable hybrid-storage blockchains,” inProc. IEEE Int. Conf. Data Eng. (ICDE). IEEE, 2021, pp. 996–1007 on Pith
- [46] H. Wang, C. Xu, C. Zhang, J. Xu, Z. Peng, and J. Pei, “vChain+: Optimizing verifiable blockchain boolean range queries,” inProc. IEEE Int. Conf. Data Eng. (ICDE). IEEE, 2022, pp. 1927–1940 on Pith
- [47] P. Sun, L. Zhang, J. Liu, C. Tang, and J. Wang, “E 3FS: Efficient, secure, and verifiable fuzzy search with data updates in hybrid-storage blockchains,” inProc. IEEE Int. Conf. Data Eng. (ICDE). IEEE, 2025, pp. 3890–3903 on Pith
- [48] Z. Yao, T. Li, J. Xin, Y . Li, C. Wang, Z. Wang, D. Srivastava, and C. S. Jensen, “VGQ: Enabling verifiable graph queries on blockchain systems,” inProc. IEEE Int. Conf. Data Eng. (ICDE). IEEE, 2025, pp. 3602–3614 on Pith
- [49] C. Zhang, C. Xu, J. Xu, and B. Choi, “Distributed kNN query authenti- cation,” inProc. IEEE Int. Conf. Mobile Data Manage. (MDM). IEEE, 2018, pp. 167–176 on Pith
- [50] N. Cui, K. Qian, T. Cai, J. Li, X. Yang, J. Cui, and H. Zhong, “Towards multi-user, secure, and verifiable kNN query in cloud database,”IEEE Trans. Knowl. Data Eng., vol. 35, no. 9, pp. 9333–9349, 2023 on Pith
- [51] Z. Qiu, W. Qu, J. Zhang, and B. Yuan, “V3DB: Audit-on-demand zero-knowledge proofs for verifiable vector search over committed snapshots,”Proc. VLDB Endow., vol. 19, no. 10, pp. 2604–2616, 2026 on Pith
- [52] Y . Jiang, X. Yang, X. Liu, Y . Guo, and J. Zhang, “zkRAG: Efficiently proving RAG retrieval in zero knowledge,”Cryptology ePrint Archive, no. 2026/709, 2026. [Online]. Available: https://eprint.iacr.org/2026/709 on Pith
- [53] J. Zhu, L. Patel, M. Zaharia, and R. A. Popa, “Compass: Encrypted semantic search with high accuracy,” inProc. USENIX Symp. Oper. Syst. Des. Implement. (OSDI), 2025, pp. 915–938 on Pith
- [54] H. Chen, I. Chillotti, Y . Dong, O. Poburinnaya, I. Razenshteyn, and M. S. Riazi, “SANNS: Scaling up secure approximate k-nearest neighbors search,” inProc. USENIX Secur. Symp., 2020, pp. 2111–2128 on Pith
- [55] J. Li, Z. Huang, M. Zhang, C. Hong, J. Liu, T. Wei, and W. Chen, “Panther: Private approximate nearest neighbor search in the single server setting,” inProc. ACM SIGSAC Conf. Comput. Commun. Secur. (CCS), 2025, pp. 365–379 on Pith
- [56] M. Zhou, E. Shi, and G. Fanti, “Pacmann: Efficient private approximate nearest neighbor search,”Cryptology ePrint Archive, 2024 on Pith
- [57] Y . Liu, Y . Zhang, J. Xie, H. Li, J. X. Yu, and J. Cui, “Privacy-preserving approximate nearest neighbor search on high-dimensional data,” inProc. IEEE Int. Conf. Data Eng. (ICDE). IEEE, 2025, pp. 3017–3029. APPENDIXA MESTFORMULTI-LAYEREDGRAPHS In graph-based ANN search, a pr... on Pith
Challenges and discussion
Disagree with the review, or know something it missed? Leave a comment, or challenge this review formally: a challenge becomes a permanent entry in this paper's record, and its decision is published here.
Come back by email
A short list of the week's newly reviewed papers. Nothing is sent until you confirm from your inbox, and every email has a link that stops it. No account.
No comments yet.
Sign in to comment