RingOA: Fast Oblivious Access for Large-Scale Privacy-Preserving Structured Data Analysis
Tomoki Uchiyama (Paper author · Waseda University), Kana Shimizu (Paper author · Waseda University)
Privacy Enhancing Technologies Symposium (PETS) 2026 · Day 2 · Alpaca
Overview
In an era where data privacy is paramount, the ability to perform complex analytical tasks on sensitive, privately-held datasets without compromising confidentiality is a critical challenge. The talk "RingOA: Fast Oblivious Access for Large-Scale Privacy-Preserving Structured Data Analysis," presented by Divya Sharma (a PhD student from Masaryk University) and based on work by Tomoki Uchiyama and Kana Shimizu from Waseda University, introduces a novel protocol designed to tackle this very issue. RingOA provides a fast and efficient solution for Oblivious Access (OA), a fundamental building block in Secure Multi-Party Computation (MPC), specifically tailored for extremely large, secret-shared databases.

Key moments
- 0:00 Introduction to Oblivious Access: The Challenge
- 2:00 DPF for Oblivious Access: Advantages and Bottleneck
- 3:30 Limitations of existing DPF approaches for arithmetic shares
- 4:30 Introducing Ring-O-Wear: Fast Oblivious Access Protocol
- 6:00 Ring-O-Wear's key idea: Sign correction for signed vectors
- 6:40 Performance evaluation: Ring-O-Wear outperforms existing methods
- 7:50 Applications: Privacy-preserving structured data analysis
RingOA: Fast Oblivious Access for Large-Scale Privacy-Preserving Structured Data Analysis
Speakers: Tomoki Uchiyama (Paper author, Waseda University), Kana Shimizu (Paper author, Waseda University)
Conference: PETS
YouTube: https://www.youtube.com/watch?v=fZKjaJtKv-M
Overview
In an era where data privacy is paramount, the ability to perform complex analytical tasks on sensitive, privately-held datasets without compromising confidentiality is a critical challenge. The talk "RingOA: Fast Oblivious Access for Large-Scale Privacy-Preserving Structured Data Analysis," presented by Divya Sharma (a PhD student from Masaryk University) and based on work by Tomoki Uchiyama and Kana Shimizu from Waseda University, introduces a novel protocol designed to tackle this very issue. RingOA provides a fast and efficient solution for Oblivious Access (OA), a fundamental building block in Secure Multi-Party Computation (MPC), specifically tailored for extremely large, secret-shared databases.
The core problem RingOA addresses is the need to retrieve an element from a secret-shared database at a secret index without revealing the index itself. This capability is crucial for privacy-preserving data analysis tasks, such as credit searches or range queries on sensitive structured data. Existing methods often suffer from significant computational bottlenecks, particularly when dealing with databases containing up to a billion entries. RingOA distinguishes itself by combining the benefits of efficient Distributed Point Functions (DPFs) with a direct output format compatible with arithmetic MPC, thereby achieving superior performance and broadening the scope of practical privacy-preserving applications.
This work is significant because it pushes the boundaries of practical secure computation, making large-scale privacy-preserving data analysis more feasible. By drastically reducing the computational overhead for oblivious access on arithmetic-shared data, RingOA enables organizations to unlock insights from sensitive datasets while maintaining strict privacy guarantees, fostering trust and compliance in data-driven decision-making processes.
Background
▶ Watch: Introduction to Oblivious Access: The Challenge (0:00)
The foundation of RingOA lies in the domain of Secure Multi-Party Computation (MPC), particularly those relying on secret sharing. In secret sharing-based MPC, data is split into multiple shares, distributed among several parties, such that no single party learns the original data. Computations are then performed distributively on these shares. A recurring requirement in many MPC protocols, especially those involving database lookups or structured data analysis, is Oblivious Access (OA), sometimes referred to as Private Information Retrieval (PIR).
The challenge in OA is that parties need to retrieve an element from a database where both the database itself and the index of the desired element are secret-shared. The goal is to obtain the secret-shared element corresponding to the secret index without revealing any information about the index to the parties holding the database shares. For instance, if a bank wanted to check a customer's credit score (stored in a secret-shared database) based on a secret-shared customer ID (the index), OA would ensure that neither the bank nor the customer learns the specific credit score or the customer ID of the query.
A common and efficient approach to implement OA is through Distributed Point Functions (DPFs). A DPF allows a generator to create compact "keys" that compactly represent shares of a unit vector (a vector with a single '1' at a specific index and '0' elsewhere) corresponding to the secret index. Each party holding a DPF key can then locally compute its share of this unit vector. The crucial advantage of DPFs is that the online communication required to perform the oblivious access is constant, meaning it does not increase with the size of the database. This makes DPFs particularly attractive for very large databases, such as those with up to 1 billion entries, which RingOA targets. Once each party has its share of the unit vector, they can perform an inner product with their respective database shares. Since the unit vector share effectively "selects" one element, this inner product yields the secret-shared element at the secret index.
However, a significant bottleneck in traditional DPF-based OA arises from the local computation required to expand the DPF key into a full unit vector share. This expansion often involves a pseudo-random function (PRF) applied iteratively in a tree-like structure, leading to computation that is linear in the database size. For a database with a billion entries, this linear computation becomes prohibitively expensive. To mitigate this, techniques like auto-termination have been developed. Auto-termination leverages the structure of DPFs, which are often built using pseudo-random functions (PRFs) in a tree. Instead of expanding the DPF tree all the way to the leaves, auto-termination allows the expansion to stop early when certain conditions are met, effectively skipping computations for large branches of the tree. This significantly reduces the number of PRF calls and, consequently, the local computation. Auto-termination is most effective for single-bit DPFs, where each output is only one bit.
Existing DPF-based OA protocols face a dilemma:
- Variant Share Database: Protocols using single-bit DPFs can benefit greatly from auto-termination, enabling additive access. However, these often produce Boolean shares, which require a costly conversion to arithmetic shares if the subsequent MPC computations are performed in an arithmetic domain (e.g., operations over a finite field or ring).
- Arithmetic Share Database: Protocols designed for arithmetic share databases allow direct use of the retrieved value in arithmetic MPC without conversion. However, existing protocols in this category have generally been unable to fully leverage the benefits of auto-termination with single-bit DPFs, leading to higher computational costs for large databases.
The goal of RingOA is to bridge this gap: to apply the full advantages of auto-termination (from single-bit DPFs) directly to an arithmetic share database, thereby combining the best of both worlds without costly conversions.
Key Findings
▶ Watch: Limitations of existing DPF approaches for arithmetic shares (3:30)
RingOA's primary contribution is the development of a fast three-party protocol that achieves full additive auto-termination with single-bit DPFs while directly producing an arithmetic share output for an arithmetic share database. This represents a significant advancement by overcoming the limitations of prior work, which either sacrificed auto-termination efficiency for arithmetic compatibility or required expensive share conversions.
The key findings and contributions of RingOA are:
- Direct Arithmetic Output with Auto-termination: RingOA is the first protocol to combine the efficiency benefits of auto-termination (derived from single-bit DPFs) with the direct output of arithmetic shares. This eliminates the need for costly Boolean-to-arithmetic share conversions, making it highly efficient for subsequent arithmetic MPC computations.
- Novel Sign Correction Technique: The protocol introduces a clever "sign correction" mechanism. When single-bit DPF shares are combined in an arithmetic setting, they can produce a "signed vector" (+1 or -1) rather than a pure unit vector. RingOA derives a correction value from the DPF keys and applies it to the inner product result, ensuring the correct database element is retrieved.
- Enhanced Performance for Large Databases: Through its design, RingOA significantly outperforms existing DPF-based OA protocols, especially as the database size increases. For databases with up to 1 billion entries, each oblivious access can be completed in approximately 1 to 2 seconds, demonstrating practical viability.
- Three-Party Replicated Secret Sharing Model: The protocol is designed for a three-party replicated secret sharing setting, which offers a good balance between security and efficiency. This model assumes an honest-but-curious adversary and does not require a trusted dealer.
- Practical Applications: RingOA is not just a theoretical construct; it enables practical applications for privacy-preserving structured data analysis, such as secure credit searches and range queries, which were previously bottlenecks due to the overhead of oblivious access.
- Open Implementation: The authors provide an open implementation of RingOA, facilitating adoption and further research in the field.
In essence, RingOA delivers a highly efficient and practical solution for a fundamental problem in privacy-preserving computation, making large-scale secure data analysis more accessible and performant.
Technical Deep Dive
▶ Watch: Introducing Ring-O-Wear: Fast Oblivious Access Protocol (4:30)
RingOA operates within a specific protocol setting designed for efficiency and security:
- Three-Party Replicated Secret Sharing: The database and other sensitive inputs are shared among three parties. In this scheme, each party holds two shares, meaning shares are replicated across the parties. For example, if a secret
sis shared, party P1 might hold sharess1ands2, P2 holdss2ands3, and P3 holdss3ands1. The secret can be reconstructed by any two parties combining their shares (e.g.,s = s1 + s2 + s3if using additive sharing over a ring). This model ensures that no single party learns the secret. - Oblivious Model without a Trusted Dealer: The protocol assumes an honest-but-curious (semi-honest) adversarial model, where parties follow the protocol specifications but may attempt to infer private information from the data they observe. Crucially, there is no need for a trusted dealer to set up the initial secret shares or distribute keys, simplifying deployment.
The protocol execution is divided into two phases:
- Offline Phase: In this phase, parties engage in input-independent computations to prepare necessary cryptographic material. This includes generating DPF keys and authentication tokens. This phase can be performed ahead of time, before any specific query is known, and its cost is amortized over many online queries.
- Online Phase: Once the offline preparations are complete, parties can perform oblivious access efficiently. This phase is designed to be as fast as possible, as it directly impacts the real-time performance of applications.
The key idea behind RingOA's efficiency and ability to combine auto-termination with arithmetic output lies in its novel approach to handling the indicator shares produced by single-bit DPFs. Let's break down this core concept:
Traditionally, a single-bit DPF generates shares of a unit vector (e.g., [0, 0, 1, 0, 0]) where the '1' indicates the secret index. When working in an arithmetic ring (a set with addition, subtraction, and multiplication operations, like integers modulo N), if parties were to simply add their respective indicator shares, the result would not necessarily be a unit vector. For example, if party A has [0, 0, 1, 0] and party B has [0, 0, 0, 1], their sum would be [0, 0, 1, 1], which is not a unit vector.
RingOA's innovation addresses this by recognizing that when two shares from a single-bit DPF are combined (specifically, subtracted in a particular way), the result is a signed vector. This signed vector is similar to a unit vector, but instead of a '1' at the secret index, it can have either a +1 or a -1. For example, if the secret index is i, the combined vector might look like [0, ..., +1 (at i), ..., 0] or [0, ..., -1 (at i), ..., 0].
While this signed vector still correctly points to the target database element, the crucial difference is the potential sign flip. If an inner product is performed with this signed vector and the database shares, the retrieved database element might have its sign flipped (i.e., +value becomes -value, or vice versa). This is problematic for arithmetic computations where the exact value is required.
To correct this, RingOA introduces a sign correction value. This value is cleverly derived directly from the DPF keys during the DPF expansion process. Each party, during its local computation of the DPF, can determine the sign associated with its share. By combining this information, the parties can collectively compute a secret-shared correction value that is either +1 or -1.
The final step is to apply this correction. After computing the inner product of the signed vector shares and the database shares (which might yield +value or -value), the parties multiply this intermediate result by the secret-shared sign correction value. This multiplication effectively flips the sign back if it was incorrect, ensuring that the final output is the correct, secret-shared database element (e.g., +value) at the secret index.
This technique is the lynchpin of RingOA's design. It allows the protocol to:
- Utilize single-bit DPFs, which benefit maximally from auto-termination, drastically reducing local computation.
- Work directly with arithmetic share databases, avoiding costly Boolean-to-arithmetic conversions.
- Produce a direct arithmetic output, ready for subsequent arithmetic MPC operations.
The talk highlights that RingOA "clearly outperforms" other approaches as database size increases, especially compared to the "SPD share approach" and "variant share database" methods. The "variant share database" approach, while supporting auto-termination, requires a conversion step. RingOA achieves comparable or better performance without this conversion, directly determining the arithmetic share. This efficiency is underscored by the benchmark showing that even for databases with 1 billion entries, each oblivious access requires only 1 to 2 seconds, making it a highly practical solution for large-scale privacy-preserving data analysis.
Demo / Proof of Concept
▶ Watch: Performance evaluation: Ring-O-Wear outperforms existing methods (6:40)
While the talk did not feature a live, step-by-step demonstration in the recording, the presenter explicitly stated, "We also provide applications to structured data analysis based on Ring-Go-Way such as privacy-preserving credit search and range search. And we also provide uh open implementation down here." This indicates that a proof of concept (PoC) in the form of an open-source implementation exists, and it has been applied to concrete use cases.
The mention of privacy-preserving credit search serves as an excellent example of a real-world application benefiting from RingOA. In such a scenario, a financial institution might want to query a customer's credit score (an element in a database) based on their secret-shared ID (the index) without revealing the ID to the database holder or the score to the querying party beyond what is necessary for the computation. RingOA's efficient oblivious access makes this type of query feasible on massive credit databases.
Similarly, range search (e.g., finding all customers with a credit score between X and Y, or all transactions within a certain date range) is another complex structured data analysis task. Implementing range queries efficiently in a privacy-preserving manner often decomposes into multiple oblivious access operations. RingOA's speed for individual accesses would significantly accelerate such composite queries.
The existence of an "open implementation" further solidifies RingOA's proof of concept. It means that the theoretical design has been translated into working code, allowing researchers and practitioners to verify its performance, security, and utility. This availability is crucial for fostering adoption and enabling further development in the field of privacy-preserving technologies. The performance results cited in the talk (1-2 seconds for 1 billion entries) are likely derived from this implementation, demonstrating its practical efficiency.
Defensive Implications
▶ Watch: Applications: Privacy-preserving structured data analysis (7:50)
RingOA presents significant defensive implications, not in the traditional sense of protecting against direct attacks, but rather in empowering organizations to proactively defend against data breaches and privacy violations by enabling secure data processing. Its primary defensive value lies in facilitating privacy-preserving data analysis on sensitive, structured datasets.
Here's how RingOA strengthens defensive postures:
- Enabling Privacy by Design: By providing an efficient mechanism for oblivious access, RingOA allows organizations to build applications and services that are private by design. Data can be secret-shared and processed without ever being exposed in plaintext, mitigating the risk of inadvertent data leaks or malicious exfiltration during analytical operations.
- Compliance with Data Protection Regulations: Regulations like GDPR, CCPA, and others mandate strong privacy protections for personal data. RingOA offers a cryptographic primitive that can help organizations comply with these regulations by ensuring that sensitive queries and data lookups are performed without revealing underlying personal identifiers or data values.
- Secure Collaboration and Data Sharing: Organizations often need to collaborate or share data for joint analysis (e.g., fraud detection across banks, medical research across hospitals). RingOA provides a tool that allows such collaborations to occur securely, where each party can query or contribute to a shared database without revealing their specific queries or parts of their private data to other participants.
- Mitigating Insider Threats: Even within an organization, access to sensitive data can be a risk. By using secret-sharing and oblivious access, the number of individuals or systems with plaintext access to entire datasets can be minimized. Analysts can perform necessary queries without ever seeing the raw, identifiable data.
- Enhanced Data Utility with Strong Privacy: Historically, strong privacy often came at the cost of data utility or computational efficiency. RingOA demonstrates that it's possible to achieve high levels of privacy (computational secrecy for queries and data) while maintaining practical performance for large-scale analytical tasks. This means organizations don't have to choose between privacy and insights.
- Foundation for Complex Secure Analytics: Oblivious access is a fundamental building block for many advanced privacy-preserving protocols. By making this primitive extremely fast and scalable, RingOA paves the way for the practical deployment of more complex secure data analysis techniques, such as secure machine learning inference, secure statistics, and more sophisticated search functionalities on encrypted or secret-shared data.
In essence, RingOA equips defenders with a powerful cryptographic tool to manage and process sensitive information securely, turning a potential data liability into a secure asset that can be analyzed for valuable insights without compromising privacy.
Key Takeaways
- RingOA is a novel, fast three-party protocol for Oblivious Access (OA), specifically designed for large-scale privacy-preserving structured data analysis.
- It effectively addresses the computational bottleneck of DPF-based OA by combining the full benefits of auto-termination (from single-bit DPFs) with direct arithmetic share output, eliminating costly share conversions.
- The protocol employs a clever sign correction technique derived from DPF keys, enabling accurate retrieval of arithmetic values from signed vectors.
- RingOA demonstrates superior performance, achieving 1 to 2 seconds per access for databases containing up to 1 billion entries, making large-scale secure queries practical.
- It supports critical applications like privacy-preserving credit search and range search, enhancing secure data utility and compliance.
- An open implementation of RingOA is provided, facilitating adoption and further research in secure multi-party computation.
About the Speaker(s)
The work on RingOA was authored by Tomoki Uchiyama and Kana Shimizu, both affiliated with Waseda University. While the talk itself was presented by Divya Sharma from Masaryk University, the foundational research and development of the RingOA protocol are attributed to Uchiyama and Shimizu. Their work contributes to the field of secure multi-party computation, focusing on practical and efficient cryptographic protocols for privacy-preserving data analysis.
Reviews
Dr. Zero (Offensive Security Researcher) — SOLID
Uchiyama and Shimizu solved a massive bottleneck in Oblivious Access by killing the Boolean-to-arithmetic conversion tax. Getting a PIR query across a billion-record database down to 1-2 seconds without a trusted dealer is serious engineering. The semi-honest threat model is a standard academic crutch, but the sign correction math is elegant enough to make this a strong win for PETS.
Heather Calloway (CISO) — SOLID
This is academic cryptographic research that solves a massive performance bottleneck in Secure Multi-Party Computation (MPC). The business reality is that querying billion-record datasets across organizational boundaries without exposing plaintext is becoming computationally viable. It is not an immediate operational playbook, but it is a critical signal for how we will manage third-party data risk in the near future.
→ Top-rated talks at Privacy Enhancing Technologies Symposium (PETS) 2026
All talks from Privacy Enhancing Technologies Symposium (PETS) 2026