CS Paper Radar

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

Hao Nie, Wei Wang, Peng Xu, Haoming Yan, Laurence T. Yang, Kaitai Liang

cs.CR ·submitted 2026-10-16 07:35 UTC · v1
hot direction

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Private Vulnerability Testing for User Oversharing

cs.CR ·2026-11-04 ·Alexander Boyd, Daniel Gardham, Nishanth Sastry, Suparna De
similarity 0.69
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

Plaintext Recovery Against Post-Filtering Access Control

cs.CR ·2026-08-12 ·Zachary Espiritu, David Cash
top venue similarity 0.66
Abstract · 21 pages, 5 figures, 6 tables. Full version of https://www.usenix.org/conference/usenixsecurity26/presentation/espiritu

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.

0.47

STAR: Scalable TEE-based Anonymous Rate-limiter

cs.CR ·2026-10-28 ·Kosei Akama, Yoshimichi Nakatsuka, Koichi Moriyama, Keisuke Uehara
similarity 0.64
Abstract

Protecting Internet services from attacks such as TLS/HTTP floods requires rate limiting, yet identifying users to enforce these limits can compromise their privacy. Anonymous rate limiting promises to reconcile these goals, but existing schemes either struggle to scale or assume that services and authorities do not collude. We present STAR, which uses server-side trusted execution environments (TEEs) to overcome these limitations. By enabling lightweight cryptographic operations, TEEs make authentication efficient, but introduce a privacy challenge: malicious services can observe memory-access patterns to infer user secrets. We address this threat through countermeasures against secret-dependent memory accesses and assess our implementation using dynamic analysis. To extend these efficiency gains across servers, we also design a secure sharding mechanism that distributes client requests. We demonstrate that strong privacy guarantees can coexist with efficient authentication at scale; STAR processes authentication requests in tens of microseconds and handles approximately 13.9K requests per second per CPU core.

0.28

Private Retrieval Augmented Generation via Random Projection

cs.AI cs.CR ·2026-10-15 ·Dixi Yao, Tahseen Rabbani, Tian Li
similarity 0.62
Abstract

Retrieval-Augmented Generation (RAG) enhances the capabilities of large language models (LLMs) by querying external structured knowledge. However, it can also introduce privacy risks by leaking sensitive information from the retrieval datastore. We propose a simple method to preserve datastore privacy in RAG systems via random projection. By applying the same projection to both datastore embeddings and query embeddings, our method provably preserves semantic similarity between queries and retrieved items while substantially mitigating data extraction attacks. Across multiple RAG architectures and datasets, we show that this lightweight approach achieves superior retrieval and generation performance compared to prior methods which leverage formal differential privacy (DP) guarantees, while exhibiting comparable empirical privacy under strong attack models. Our results for the first time suggest that random projection can serve as a competitive and practical baseline for privacy-preserving RAG systems.

0.39

VerfGraph: Efficient Zero-Knowledge Verifiable Graph Query Evaluation System

cs.CR ·2026-11-03 ·Tianyi Ma, Yuncong Zhang, Yuanzhuo Yu, Boshi Yuan, Shi-Feng Sun
benchmark similarity 0.61
Abstract · 13 pages, 3 figures, 7 tables

Graph databases are often used to manage relationship-rich data, whose graph structure and attributes may be sensitive. In many applications, a database owner or a service provider evaluates queries over a private graph for a client. Because the graph cannot be fully disclosed and independently re-executing the query may be impractical, the client cannot directly verify the returned result. This creates a need for verifiable graph query evaluation that preserves data confidentiality. We present VerfGraph, a zero-knowledge system for verifiable graph query evaluation, which enables a client to verify that the query result was correctly computed over a committed graph data, without revealing private graph records or intermediate query values beyond the public inputs and what is implied by the query result. Building on the expansion-centric model introduced by the state-of-the-art zero-knowledge verifiable graph query evaluation system ZKGraph (ICDE'26), VerfGraph achieves more efficient and expressive zero-knowledge verifiable graph query evaluation by advancing design in two key ways. First, we propose novel operator-proof methods for core expansion and shortest-path operations that reduce costly sorting and comparison checks and eliminate edge canonicalization for bidirectional expansion. Furthermore, we introduce correctness proofs for count and weighted shortest-path operators, broadening the class of graph queries that can be verified. We evaluate VerfGraph using the LDBC Social Network Benchmark. Compared with ZKGraph on complex IC queries, VerfGraph achieves $33.9\times$-$59.7\times$ speedups in proof generation and reduces peak prover memory by factors of $4.5\times$-$6.6\times$, while maintaining millisecond-level verification and producing sub-MB proofs.

0.27

Stealing Reasoning Traces from Proprietary LLM APIs

cs.CR cs.AIcs.LG ·2026-08-10 ·Alexander Panfilov, David Schmotz, Ilia Shumailov, Luca Beurer-Kellner, Joachim Schaeffer +3 more
highly cited similarity 0.61
Abstract

Leading large language model providers now conceal their models' step-by-step reasoning, or chain-of-thought, to protect intellectual property and limit information leakage. Rather than storing these traces server-side, providers return them to the client as blocks of encrypted text, which the client passes back with each subsequent request. Building on prior research, we identify an architectural vulnerability: these encrypted blocks are fully compatible and interchangeable across different sessions, users, and models within a provider's ecosystem. We exploit this compatibility to develop a scalable decryption jailbreak. By injecting an encrypted reasoning trace from a given model into a weaker, and less safeguarded model from the same provider, we force it to decode and output the trace verbatim in plaintext, without ever jailbreaking the more capable model directly. This vulnerability enables four distinct attack vectors. First, it circumvents anti-distillation mechanisms, allowing adversaries to extract a proprietary model's reasoning, as we demonstrate across Anthropic, OpenAI, and Google. Second, it allows for large-scale private data extraction. Developers frequently share session logs publicly, unaware of contents of the encrypted blocks. By decoding 315,320 reasoning blocks scraped from public repositories, we recovered 367 Personally Identifiable Information (PII) artifacts and 182 credentials. Third, it inadvertently reveals hazardous information hidden within the reasoning process, even in cases where the model's final, visible output safely rejects a malicious request. Fourth, attackers can leverage this flaw to execute invisible prompt injections, embedding malicious payloads entirely within encrypted blocks to poison public agentic rollouts. Following responsible disclosure, we propose concrete cryptographic and system-level mitigations to secure client-side reasoning.

0.44

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

Trusted Model Environment for Private Semantic Computations

cs.CR ·2026-09-24 ·Vasisht Duddu, Xi He
similarity 0.61
Abstract

A private semantic computation primitive enables parties to privately compute over structured and unstructured data that requires understanding its semantics, context, and relationships. Standard cryptographic primitives (e.g., multiparty computation) do not readily support such computation. Generative models are well suited for such tasks but typically process data in plaintext, while cryptographic private inference remains inefficient and difficult to scale. Thus, we need a new primitive for private semantic computation. We introduce trusted model environments (TME), the first such primitive that executes generative models inside trusted execution environments (TEEs) while controlling output leakage. TME is designed to be (i) effective (correctly performs the semantic task); (ii) confidential (protects computation and sensitive inputs); (iii) utility-preserving (retains utility on other tasks); (iv) verifiable (provides tamper-resistant evidence of the computations); (v) efficient (incurs low overhead compared to baseline model computations); and (vi) scalable (supports multiple participating parties). Effectiveness follows from the generative models, while TEEs provide confidential computation. For confidentiality of sensitive inputs, we combine adversarial training to resist verbatim leakage with an information flow control module to suppress semantic leakage. For verifiability, we introduce novel attestations that let parties verify TME operations on their data and queries, along with optimizations (e.g., batching) for efficiency and scalability. We design and evaluate the proof-of-concept for TME across three applications, showing that it meets all the requirements.

0.09