RingOA: Fast Oblivious Access for Large-Scale Privacy-Preserving Structured Data Analysis

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.