CS Paper Radar

Plaintext Recovery Against Post-Filtering Access Control

Zachary Espiritu, David Cash

cs.CR ·submitted 2026-08-12 07:11 UTC · v1
top venue

Abstract

Fine-grained access control (FGAC) mechanisms such as row-level security (RLS) and document-level security (DLS) are widely deployed in databases to restrict access to data stored in physical indexing structures shared by multiple users (e.g., in multi-tenant databases, or in the implementation of least-privilege within an organization). FGAC implementations often use post-filtering where untrusted queries run over all data and private results are redacted afterwards. Prior work shows this approach can lead to side-channels that enable attackers to test if a chosen value exists in unseen data. While damaging, prior attacks do not enable the efficient recovery of rich, high-entropy data like full records or text documents. We show these side-channels are more damaging than previously thought. Using rich query interfaces (e.g., range, prefix, and conjunctive predicates), we amplify existence leakage into reconstruction attacks. We do this in two settings: - PostgreSQL (RLS timing). We exploit a timing side-channel and expressive SQL queries (e.g., ranges, conjunctions) to enumerate unknown attribute values and, in turn, full records via binary search over large domains. - Elasticsearch/OpenSearch (DLS scoring). We exploit scoring and prefix-expansion side-channels to recover indexed terms from documents. In some cases, we can extract $n$-grams in the corpus to recover approximate text. Our results show that FGAC side-channels must be evaluated in the presence of rich predicates, which can turn membership tests into scalable reconstruction of high-entropy records.

Comment
21 pages, 5 figures, 6 tables. Full version of https://www.usenix.org/conference/usenixsecurity26/presentation/espiritu
Journal ref
Proceedings of the 35th USENIX Security Symposium (2026), 3753-3772

Closest papers

Nearest neighbours by meaning across the whole index.

Aspire: Practical Batch Queries on Dynamic Encrypted Database with Full Leakage Suppression

cs.CR ·2026-10-16 ·Hao Nie, Wei Wang, Peng Xu, Haoming Yan, Laurence T. Yang +1 more
hot direction similarity 0.66
Abstract

Leakage-abuse attacks against encrypted database systems exploit semantic leakage and pose a severe threat to the confidentiality of plaintext data and queries. To address this problem, we propose a zero-leakage encrypted database that rules out leakage-abuse attacks, which fundamentally rely on semantic leakage. We first distinguish between two kinds of zero-leakage security. Ideal zero-leakage forbids the disclosure of any information beyond public parameters, whereas restricted zero-leakage additionally permits the leakage of metadata (such as database size and query timing). We show that restricted zero-leakage is sufficient to thwart leakage-abuse attacks and is achievable in practice. We then formally define adaptive restricted zero-leakage security and present Aspire, an encrypted database that satisfies this notion. Aspire integrates probabilistic batch code and minimal perfect hashing to support efficient batch keyword queries and dynamic updates while revealing only non-semantic metadata. Experimental results demonstrate the practicality and efficiency of Aspire, showing that Aspire can achieve an amortized query latency of less than 1.38 ms (7.53 s for a batch of 5461 keyword queries), with an amortized communication cost of approximately 2.95 KB (16.1 MB in total), on a $2^{22}$ key-value pairs database.

0.30

Private Vulnerability Testing for User Oversharing

cs.CR ·2026-11-04 ·Alexander Boyd, Daniel Gardham, Nishanth Sastry, Suparna De
similarity 0.66
Abstract · 19 pages, 4 figures, submitted to WWW 2027

Users can inadvertently increase their vulnerability to privacy attacks by oversharing personal information. In particular, the combination of individually innocuous attributes can place a user in a sufficiently small population to enable linkage or re-identification attacks. We present a privacy-preserving mechanism that allows users to determine whether the information they disclose places them below a predefined population threshold, without revealing their query or the data of other users. Our setting presents several practical challenges: users contributing data may be offline when queries are made, queries may select arbitrary subsets of attributes, and neither server should learn the queried population or its size. We address these challenges using secret-shared data and queries, private equality testing, and secure threshold computation. Our protocol provides computational privacy against a malicious client and semi-honest, non-colluding servers, while supporting arbitrary queries and dynamic database updates. We define reactive $f$-privacy for a dynamically evolving database and prove that our construction satisfies it, with the sequence of permitted threshold outputs defining the information available to the adversary across an execution. We optimise the protocol using oblivious-transfer extensions and pre-computation, achieving sub-second online query times for 96-bit queries on datasets of up to one million records.

0.35

Isolation Is Not Confidentiality: Security Boundaries of Geometric Access Control in RAG

cs.CR ·2026-11-10 ·Steve Nouyep, Maxime Puys, Sébastien Salva
similarity 0.64
Abstract

Retrieval-Augmented Generation (RAG) systems increasingly rely on vector databases containing documents governed by different access-control policies. Recent search-preserving geometric approaches enforce such access control by structuring the embedding space so that transformed embeddings, which we call protected representations, remain retrievable without exposing information across policy boundaries. We provide a unified security analysis of this paradigm, covering policy isolation, representation confidentiality, query forgery resistance, and policy-membership hiding. We consider both a curious cloud service provider observing the protected representations stored in the vector database and a curious user holding aligned pairs of original embeddings and protected representations. Evaluating the available implementations of the works proposing these geometric transformation mechanisms across three encoders, we find that geometric transformations preserve retrieval utility and provide strong policy isolation, but do not provide the other security properties. A curious user can recover the original embeddings from a few hundred pairs and forge policy-compatible queries at a higher cost that grows with encoder dimension for secret per-policy transformations. Moreover, policy-dependent geometry can leak policy membership even when unauthorized retrieval is prevented. These results show that policy isolation, confidentiality, forgery resistance, and membership hiding are distinct security objectives.

0.29

Revision-Bound Evidence Cuts: Authenticated Queries and Contextual Witness Capacity

cs.CR cs.DB ·2026-10-27 ·Faruk Alpay, Taylan Alpay
similarity 0.63
Abstract · 54 pages, 10 figures

Authentic records can support unauthorized narratives when their qualifications, query scope, or counterevidence are silently dropped. We present revision-bound evidence cuts, a framework for authenticating both supporting and opposing inference obligations across changing source versions. Signed complete-update frontiers permit transport of unaffected certificates, alternative-cut recovery, and an exact certified-reuse radius given by a frontier-hypergraph transversal number. Their source obligations induce an integral model of context-bound authorization. To secure database-derived claims, we introduce an authenticated relational query contract that binds original source records, complete selected bags, counting units, parameters, and aggregates independently of execution strategy. A full-source verifier checks 16,824 Chogha Mish records across SQLite scans, indexes, and materialized views; three valid strategies agree and eight contract/view mutations are rejected. A separate 340-row NISP cohort shows that changing the admitted weighting rule can reverse a comparison while preserving every source record. A frozen English text-to-frame compiler produces qualified evidence receipts, with linguistic accuracy evaluated separately from cryptographic integrity. We also separate logical-source from transport commitments so lossless re-encoding need not invalidate unchanged scientific evidence. The SCENE prototype evaluates signed revisions, authenticated queries, scoped disclosures, and adversarial mutations at scales reaching one million source records. These guarantees rely on declared policies and independently pinned trust roots; they authenticate specified computations and obligations, not historical truth, complete counterevidence, or institutional endorsement.

0.27

Coverage Is Not Containment: A Fundamental Limit of Admission-Time Defenses Against Coordinated Poisoning of Vector Retrieval

cs.CR cs.CLcs.IR ·2026-08-17 ·Prashant Kumar Pathak, Tarun Kumar Sharma
theory similarity 0.62
Abstract · 10 pages, 9 figures. Preprint; under submission

Retrieval-augmented generation (RAG) answers a question by retrieving passages from a vector store and trusting them as context, so anyone who can add documents can try to steer the answer. A recent, appealing defense filters poisoning at ingestion, rejecting any document that behaves like a hub. We show it -- and every ingestion-time filter -- is defeated by a coordinated adversary that injects a handful of individually unremarkable documents which together surround one target query and seize its top-k (on BGE-large / BEIR, m=10 documents take 10/10; 9.9/10 on a live HNSW index). The attack is not theoretical. Realized as ordinary fluent text and run end-to-end through a BGE-large + HNSW + Qwen2.5-7B pipeline, it makes the generator emit the attacker's planted claim in 88% of targets, versus 0% without the injection. And no admission-time defense stops it: at ingestion an attack cone is geometrically identical to a legitimate niche upload, so -- measuring this directly -- the strongest trained classifier, given every feature and thousands of examples, separates the two no better than chance, catching 4.2% of attacks at a 1% false-positive rate. We prove this limit for the entire class of ingestion-time statistics (any decision from documents and reference queries alone), and it reproduces -- and worsens -- across two corpora and five encoders. The one signal that separates an attack from legitimate niche ingestion -- a query's demand -- is invisible before retrieval, which is also the escape: a retrieval-time detector that observes demand catches 100% of the attacks at the same 1% false-positive rate. Coverage of the query space by an admission gate is not containment of coordinated poisoning; robust defense must move past the front door, to demand.

0.47

Lineage-Aware Memory Governance: A Derivation-Gated Framework for Privacy-Preserving Column-Level Access Control in Enterprise AI Agents

cs.CR cs.AIcs.CLcs.LG ·2026-10-05 ·Venkata M Sangaraju, Sudhir Vissa
publishedtheory similarity 0.62
Abstract

Enterprise AI agents that share a memory store face two unaddressed risks: sensitive data can leak through legitimately computed results the requester could not derive, and departments can silently compute a same-named key performance indicator (KPI) through conflicting logic. Existing agent-memory systems (e.g., MemGPT, Zep, A-MEM) gate retrieval by content, ownership, and role, not derivation, missing a cached insight that embeds a forbidden column. We introduce the Analytical Memory Unit (AMU), a memory schema that attaches a full derivation (lineage) graph to every cached result, gated by a retrieval policy that serves a hit only when the requester is authorised for every column touched. Provided lineage recording is complete, we prove by construction that the policy blocks retrieval of results derived from a sensitive column outside the requester's permissions, at O(n) worst case -- a conditional design guarantee, not an empirical claim, that excludes derived features encoding sensitive information without naming their source. Eliminating measured leakage required 75-90% recorded lineage completeness, so we treat 90% as a conservative deployment target. Across six experiments, lineage-gated retrieval removes the 18.8-25.5% cross-department leakage naive content-gated memory suffers, keeping 81.5-82.6% of memory reuse at 13.8 microsecond worst-case overhead. A real-agent proof-of-concept with LLM-generated SQL is consistent with the guarantee: zero leaks over 9 round-trips, two conflicts caught automatically -- though a feasibility demonstration, not evidence of production viability. This offers a practical governance layer for shared agent memory, complementing source-layer access control and supporting EU AI Act compliance.

0.45

Differentially Private GraphRAG: Protecting Relation Connectivity and Semantics

cs.CR cs.AI ·2026-11-06 ·Jie Fu, Yuan Hong, Yue Ning, Wendy Hui Wang
similarity 0.62
Abstract

Graph Retrieval-Augmented Generation (GraphRAG) connects information across documents through entity relationships to support relational reasoning. However, black-box access to GraphRAG systems can enable adversaries to reconstruct knowledge graphs and recover both structural connectivity between entities and the semantics of their relationships. Existing defenses lack formal privacy guarantees and provide limited protection against such reconstruction attacks. We propose RelGuard, the first differentially private framework for GraphRAG, which provides formal privacy guarantees by mitigating connectivity leakage and protecting relations and their semantic meaning through relation removal. We formalize relation differential privacy (relation-DP), which bounds the distinguishability of mechanism outputs according to the semantic distance between alternative relations while accounting for relation removal. Building on this definition, we develop a four-step defense mechanism that sanitizes source documents before GraphRAG indexing by perturbing relation predicates or removing their associated connectivity using the exponential mechanism. Experiments across three GraphRAG systems and two targeted reconstruction attacks demonstrate that RelGuard provides stronger protection against reconstruction attacks than four existing defense mechanisms while better preserving downstream utility.

0.13

Structural Leakage in Graph Encryption: Attacks and Defenses

cs.CR ·2026-08-14 ·Hua Shen, Renzhi Chen, Ge Wu, Willy Susilo, Jing Chen +1 more
similarity 0.61
Abstract

Graph encryption schemes (GES) enable secure outsourcing of graph data while supporting efficient queries. This report provides a comprehensive analysis of structural leakage in GES for single-pair shortest path (SPSP) queries, integrating findings from two recent works. First, we analyze PathGES, a scheme designed to resist query recovery attacks through heavy-light decomposition (HLD) and canonical fragment encoding. Our analysis reveals that PathGES suffers from significant imbalances in HLD decomposition, with over 99% of token-path mappings being one-to-one on real-world datasets, enabling both the Falzon-Paterson attack and side-channel inference of path lengths. Second, we present Fragment Tree attack that exploits these structural weaknesses to recover query contents, achieving up to 10.24% exact recovery on sparse graphs. Third, we introduce BlindGES, an enhanced scheme incorporating a Merge-and-Divide mechanism and two-level multimap index that reduces one-to-one mappings to below 20%, cuts setup time by 50%, reduces storage overhead by 32%, and limits path length leakage to under 1%. This report systematically presents attack methodologies, defense mechanisms, security proofs, and experimental evaluations on seven real-world datasets.

0.04