Oct 2026· Proceedings on Privacy Enhancing Technologies· Vol 2026, pp. 1088-1105· 0 citations· 54 references
Computer Science
TL;DR
RingOA is introduced, the first three-party OA protocol that supports ET while directly producing arithmetic shares, and two practical applications are developed: a fully oblivious full-text search protocol for pattern matching over secret-shared string datasets, and a fully oblivious range-search protocol supporting statistical queries over secret-shared numerical sequences.
Abstract
Many privacy-preserving data analysis tasks based on multi-party computation require oblivious retrieval of data elements for downstream use. As database sizes grow, this retrieval step becomes a dominant bottleneck, highlighting the need for more efficient oblivious access (OA) primitives that retrieve a database entry without revealing the accessed position. A common approach uses distributed point functions (DPFs), which reduce communication but still incur local computation that scales linearly with the database size. Early termination (ET) optimization reduces local computation, but applying it yields only Boolean shares that require costly conversion for arithmetic use. This incompatibility between ET and arithmetic outputs makes it difficult for OA to scale efficiently on large databases. We introduce RingOA, the first three-party OA protocol that supports ET while directly producing arithmetic shares. Our method eliminates the need for share conversion and preserves the computational benefits of ET. RingOA achieves a 13.1x to 15.7x improvement in runtime on databases exceeding one billion entries compared to a state-of-the-art OA protocol. Building on RingOA, we construct an oblivious rank query, a core primitive underlying many structured-data analyses. We develop two practical applications: a fully oblivious full-text search protocol for pattern matching over secret-shared string datasets, and a fully oblivious range-search protocol supporting statistical queries over secret-shared numerical sequences. Experiments on real large-scale genomic datasets show that these applications achieve practical performance, demonstrating the utility of our OA protocol and its applications.
: Oblivious RAM (ORAM) is a general-purpose storage technique that hides memory access patterns, protecting data, queries, and results from untrusted honest-but-curious servers. While traditional ORAM supports only basic reads and writes, recent works have addressed the problem of enabling richer queries by designing oblivious versions of simple data structures (e.g., maps, sets, queues). In this paper, we take a distinct step by introducing two building blocks that make it easy to construct many advanced oblivious and compressed data structures efficiently and securely. Our approach builds on recent results showing that most (compressed) data structures can be implemented using two fundamental primitives: Rank and Select, which count and locate symbol occurrences within a sequence. We present the first oblivious implementations of Rank and Select that require only a single ORAM access per operation, use O(1) client-side space, and add negligible client computation overhead. Thanks to their simplicity and efficiency, our oblivious Rank and Select provide a foundation for building a wide range of other oblivious compressed data structures, enabling privacy-preserving (compressed) data storage, indexing, and search in the cloud.
Mariagiovanna Rotundo, P. Ferragina· International Conference on...· 0 citations
We present Orq, a system that enables collaborative analysis of large private datasets using cryptographically secure multiparty computation (MPC). Orq protects data against semi-honest or malicious parties and can efficiently evaluate relational queries with multi-way joins and aggregations that have been considered notoriously expensive under MPC. To do so, Orq eliminates the quadratic cost of secure joins by leveraging the fact that, in practice, the structure of many real queries allows us to join records and apply the aggregations “on the fly” while keeping the result size bounded. On the system side, Orq contributes generic oblivious operators, a data-parallel vectorized query engine, a communication layer that amortizes MPC network costs, and a dataflow API for expressing relational analytics — all built from the ground up. We evaluate Orq in LAN and WAN deployments on a diverse set of workloads, including complex queries with multiple joins and custom aggregations. When compared to state-of-the-art solutions, Orq significantly reduces MPC execution times and can process one order of magnitude larger datasets. For our most challenging workload, the full TPC-H benchmark, we report results entirely under MPC with Scale Factor 10 — a scale that had previously been achieved only with information leakage or the use of trusted compute.
Eli Baum, Sam Buxbaum, Nitin Mathai et al.· ACM Transactions on Computer...· 0 citations
This work proposes a practical non-interactive encrypted retrieval framework for RAG based on threshold selection, and introduces a precision-stable mask polarization method that ensures accurate recovery of selected documents.
Yang Gao, Gang Quan, Scott Piersall et al.· arXiv.org· 0 citations
Modern Log-Structured Merged-tree (LSM) based key-value stores achieve high performance through sequential writes and structured data organization, but this design implicitly exposes rich side-channel information at the storage layer. Even in the presence of encryption, adversaries can exploit observable artifacts, such as data placement regularity, update propagation, and inter-level transformations, to infer sensitive properties of the underlying workload. These leakages arise not from data content, but from the tight coupling between logical semantics and physical layout. We address this problem by introducing a lightweight, permutation-based obfuscation layer that randomizes data placement while preserving efficient query semantics. Our design leverages a four-round Feistel-based pseudo-random permutation, which provides strong PRP security by the Luby-Rackoff theorem to construct a keyed, invertible mapping without maintaining auxiliary mapping tables, while ensuring that storage-level representations are difficult to correlate with logical data semantics. Rather than applying randomization at a single stage, we embed the permutation mechanism throughout the data life-cycle. We further explore design variants that control the granularity and frequency of permutation to balance security guarantees with system overhead. We implement a C++ prototype and conduct controlled micro-benchmarks to evaluate the performance impact of the proposed mechanism. Results show that key transformation and block-level shuffling introduce less than 1% overhead in average operation latency for insertions, lookups, deletions, and compaction. We further provide a qualitative security analysis showing that the design eliminates key-order preservation and disrupts insertion-order locality in the storage layout. These findings suggest that Feistel-based shuffling is a lightweight and practical complement to existing encryption-based defenses for LSM-based systems.
Tieming Geng, Chin-Tser Huang· International Conference on...· 0 citations
: In this paper, we study the problem of storing and searching in datasets of variable-length strings, a core primitive in key-value stores, (graph) DBs, and search engines. However, enabling such search capabilities in ORAM scenarios, where data are stored on an honest-but-curious server, remains challenging. We address this problem by proposing a practical design that combines Ring ORAM (Ren et al., 2015) to hide access patterns to outsourced data, with a Patricia trie (Ferragina and Grossi, 1999; Ferragina et al., 2025) for space-efficient search over variable-length strings. The resulting scheme supports search over variable-length string datasets in an ORAM scenario, while retaining efficient storage and access both on the client and the server. We evaluated our scheme on datasets having size up to 273 GB, showing that it supports complex string queries, with only 2 Ring ORAM accesses on the server, incurring a client-server communication cost below 3 MiB, a client memory footprint of at most 200 MB, and negligible client computation time per query. Although we assume bounded-length strings, the bound is high enough to handle most practical use cases.
Mariagiovanna Rotundo, Giuseppe Persiano, P. Ferragina· International Conference on...· 0 citations
: We study the problem of enabling users to perform range queries over a cloud-managed database without revealing which records are retrieved, while also allowing users to verify the correctness of the returned results. Existing approaches support either query privacy through Private Information Retrieval (PIR) or query result authentication through Authenticated Data Structures (ADSs), but not both simultaneously for range queries. To address this problem, we present an Authenticated Private Information Retrieval (APIR) protocol for range queries with guarantees of soundness and completeness. We first propose a baseline scheme that combines PIR with Merkle Hash Trees (MH-trees), achieving authenticated query processing but incurring high communication and storage overhead due to redundant verification objects (VOs). To improve efficiency, we further introduce the APIR-tree , a novel authenticated data structure that embeds values at every node, enabling nodes to serve as VOs for their ancestors and eliminating redundancy. Simulation results show that the APIR-tree reduces storage overhead by up to 25 × and communication costs by an order of magnitude while preserving strong privacy and authenticity guarantees.
