💻 computer science

Oblivis: A Framework for Delegated and Efficient Oblivious Transfer

The paper presents Oblivis, a modular framework for delegated and efficient Oblivious Transfer that enables thin clients to securely retrieve database records via proxies without leaking query intent, featuring a highly optimized "Supersonic OT" protocol that achieves significant speedups and performs efficiently even on constrained hardware.

Original authors: Aydin Abadi, Yvo Desmedt

Published 2026-03-17

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Aydin Abadi, Yvo Desmedt

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are at a massive, high-security library (the Database). You want to borrow a specific book, but you have two big problems:

You are too weak to climb the shelves: You are a "thin client" (like a smartphone or a smartwatch) and can't do the heavy lifting required to find the book yourself.
You don't want the librarian to know what you're reading: If you ask for "The Secret Recipe for World Domination," the librarian (or the security guard watching you) might sell that information to your competitors or the government.

Usually, you'd have to ask a Proxy (a middleman, like a financial advisor or a cloud server) to ask the library for you. But then, the Proxy knows what you want, and the Library knows you asked. Everyone is watching everyone.

This paper introduces Oblivis, a new set of "magic tricks" (protocols) that let you get your book without anyone knowing which book you picked, even if you can't do the work yourself.

Here is how the four main tricks work, explained with simple analogies:

1. The "Blind Delegation" Trick (Delegated-Query OT)

The Problem: You can't climb the shelves, so you ask a Proxy to do it. But if you tell the Proxy "Get me Book #5," the Proxy knows your secret.
The Solution: You split your secret request into two tiny, meaningless puzzle pieces.

You give Piece A to Proxy 1 and Piece B to Proxy 2.
Proxy 1 and Proxy 2 are like two chefs who don't trust each other. They mix their pieces together to build the final request.
The Magic: Neither Proxy knows the full picture. Proxy 1 thinks they are helping with a random task; Proxy 2 thinks the same. Only when they combine their work does the Library get a request that looks like it came from you, but neither Proxy knows what you actually asked for.

2. The "Ghost Request" Trick (Delegated-Unknown-Query OT)

The Problem: Sometimes, you don't even know which book you want! Maybe a financial advisor tells you, "Get the report for Client X," but you (the client) don't know which report that is.
The Solution: A third party (the Advisor) knows the secret number, but you don't.

The Advisor splits the secret number and gives pieces to the Proxies.
The Proxies build the request.
The Magic: The Library sends back a pile of wrapped gifts. You don't know which one is yours, but you have a special "magic key" (a hidden marker) that only fits the correct gift. You try the key on every gift until one clicks open. The Library and the Proxies never knew which gift you were looking for, and you never knew the number yourself—you just got the right result.

3. The "Shared Warehouse" Trick (Multi-Receiver OT)

The Problem: Imagine a giant warehouse where Company A, Company B, and Company C all store their files in the same building to save money. If Company A asks for a file, they don't want Company B or the warehouse manager to know how many files Company A has, or that they are looking at a specific file.
The Solution: The system treats the whole warehouse as one giant pool of data.

When you ask for your file, the system generates a response for everyone in the warehouse at once, but encrypts it so only your specific slice of the data is visible to you.
The Magic: It's like the warehouse manager hands you a single envelope. You don't know how many other envelopes exist, and the manager doesn't know which specific envelope you picked. You just get your file, and the total size of the warehouse remains a secret.

4. The "Supersonic" Trick (Supersonic OT)

The Problem: All these magic tricks are usually slow because they require complex math (like heavy lifting). You want something fast enough to run on a tiny Raspberry Pi computer.
The Solution: A new, super-fast method that doesn't rely on heavy math at all.

Instead of complex locks, it uses a simple "Swap or Don't Swap" game.
The Magic: Imagine you have two boxes, one with a prize and one empty. You tell a friend (the Proxy) to swap the boxes if they flip a coin, and you tell the Sender to swap them if they flip a coin.
- If both flip the same way (Swap/Swap or No Swap/No Swap), the prize ends up in the box you want.
- If they flip differently, the prize ends up in the other box.
- Because the coins are random, the Sender and Proxy have no idea which box you actually wanted.
The Result: This is incredibly fast. The paper shows it running in 1.36 milliseconds on a tiny Raspberry Pi. That's faster than the blink of an eye!

Why Does This Matter?

In our modern world, we rely on the cloud, financial advisors, and medical portals. We often have to trust these middlemen with our private data. Oblivis changes the rules:

Privacy: Your middleman (Proxy) can't spy on you.
Delegation: You don't need a supercomputer to stay private; your phone can do it.
Speed: It's fast enough for real-time use, even on slow devices.

Think of Oblivis as a universal "Invisibility Cloak" for your digital requests. It lets you reach into a giant database, grab exactly what you need, and walk away without anyone (not the database, not the middleman, not even your own device) knowing what you touched.

1. Problem Statement

Modern data-driven services increasingly rely on cloud platforms and edge devices where clients are often "thin" (resource-constrained) and cannot interact directly with databases. Instead, they rely on intermediaries (proxies, brokers, or gateways) to mediate access.

The Core Challenge: Clients need to retrieve specific records without revealing their query intent (the index of the record) or metadata (e.g., total database size, access patterns) to the database or the intermediary.
Limitations of Existing OT: Traditional Oblivious Transfer (OT) protocols assume direct client-database interaction. They fail in delegated settings because:
1. They require the receiver to compute the query locally, preventing delegation to a proxy.
2. They often reveal metadata (like database size) in multi-receiver or merged-database scenarios.
3. They typically require large local storage on the client to achieve constant-size responses.
4. Information-theoretic OT (unconditionally secure) usually requires multiple senders, noisy channels, or trusted setups, making them impractical for lightweight clients.

2. Methodology: The Oblivis Framework

The authors propose Oblivis, a modular framework comprising four main components designed to address delegation, privacy, and efficiency simultaneously. The framework operates under a semi-honest adversary model where parties do not collude.

A. Delegated-Query OT (DQ-OT)

Goal: Allow a receiver ( $R$ ) to outsource the computationally expensive query generation to two non-colluding proxies ( $P_1, P_2$ ).
Mechanism:
- $R$ secret-shares its query index $s$ into two bits ( $s_1, s_2$ ) and sends random values ( $r_1, r_2$ ) to the proxies.
- The proxies sequentially compute partial queries based on their shares. $P_2$ computes a pair of group elements based on $s_2$ , sorts them, and sends them to $P_1$ .
- $P_1$ combines these with its share $s_1$ to generate the final query pair $(\beta_0, \beta_1)$ .
- Key Insight: The final query structure sent to the Sender ( $S$ ) is mathematically identical to a standard Naor-Pinkas OT query, even though $R$ never computed it. Neither proxy learns the full index $s$ .

B. Delegated-Unknown-Query OT (DUQ-OT)

Goal: Support scenarios where the receiver does not know the query index (e.g., a third-party issuer $T$ determines the record based on hidden policies).
Mechanism:
- $T$ splits the index $s$ and sends shares to proxies.
- $S$ appends a random "marker" value ( $r_3$ ) to the messages before encryption.
- $S$ randomly permutes the response pair.
- $R$ decrypts both options and identifies the correct message by checking which one contains the marker $r_3$ , without needing to know $s$ beforehand.

C. Multi-Receiver Variants (DQMR-OT & DUQMR-OT)

Goal: Handle merged cloud databases where multiple organizations share a single logical database.
Mechanism:
- Privacy: Prevents receivers from learning the total number of records ( $z$ ) and prevents the sender from learning which receiver queried which record.
- Technique: Uses Additive Homomorphic Encryption (e.g., Paillier). The sender generates responses for all $z$ records. A proxy performs a homomorphic "filtering" operation using an encrypted selection vector (1-hot vector) to isolate the specific record for the intended receiver, discarding the rest.

D. Generic Compiler for Constant-Size Responses

Goal: Eliminate the need for clients to store the entire encrypted database to achieve $O(1)$ download complexity.
Mechanism:
- The receiver encrypts a selection vector (1-hot) and sends it to the sender.
- The sender homomorphically multiplies the response vector by the encrypted selection vector and sums the results.
- The sender returns a single encrypted value (constant size), which the receiver decrypts to get the message.

E. Supersonic OT

Goal: A highly efficient, information-theoretic (unconditionally secure) 1-out-of-2 OT that requires no public-key cryptography, no noisy channels, and no trusted setup.
Mechanism:
- Uses a Controlled-Swap mechanism and One-Time Pads.
- $R$ shares its index $s$ between $S$ and a proxy $P$ .
- $S$ encrypts messages with keys agreed upon with $R$ , then permutes the pair based on $S$ 's share.
- $P$ permutes the received pair based on its share and sends only one element to $R$ .
- Security: Relies on the secrecy of the shares and the randomness of the one-time pads. It achieves information-theoretic security without multiple senders.

3. Key Contributions

Delegation: First OT protocols allowing secure outsourcing of query generation to proxies without revealing the query index.
Hidden Queries: Protocols where the receiver does not even know the index of the record they are retrieving (DUQ-OT).
Multi-Receiver Privacy: Solutions for merged databases that hide the total database size and access patterns from both senders and receivers.
Constant-Size Responses: A generic compiler that reduces receiver download complexity to $O(1)$ without requiring local storage of the database.
Supersonic OT: A new, extremely fast, information-theoretic OT protocol that is post-quantum secure and lightweight.

4. Results and Evaluation

The authors implemented Supersonic OT in C++ and evaluated it on a MacBook Pro (M3) and a Raspberry Pi 4.

Performance:
- Speed: Supersonic OT achieves a 92.8× speedup over the "Simplest OT" (a highly efficient base OT) and a 2.6× to 106× speedup over standard OT extensions (IKNP) depending on the number of invocations.
- Latency: A single transfer takes 0.53 ms on a laptop and 1.36 ms on a Raspberry Pi 4.
- Scalability: Even with 100,000 invocations, the total runtime remains modest (28 ms on Mac, 196 ms on Pi).
Security:
- Supersonic OT provides Information-Theoretic Security (unconditional security), making it Post-Quantum secure.
- It achieves this without the heavy requirements of previous IT-OT schemes (no noisy channels, no multiple senders, no trusted initializer).
Comparison: It outperforms state-of-the-art OT extensions for small to medium batch sizes and remains competitive for large batches, while offering superior security guarantees (IT-security vs. computational security).

5. Significance

Practicality for Thin Clients: Oblivis enables resource-constrained devices (IoT, mobile) to perform private queries via proxies without heavy cryptographic overhead or local storage.
Cloud Privacy: It addresses critical privacy leaks in multi-tenant cloud environments (e.g., merged databases) where current solutions inadvertently reveal metadata about other tenants.
Post-Quantum Readiness: By offering an information-theoretic solution that is efficient and easy to implement (relying only on symmetric crypto and basic arithmetic), Oblivis provides a robust path forward for privacy in the era of quantum computing.
New Paradigm: The framework shifts the paradigm from "client computes query" to "client delegates query," enabling new architectures for secure data access in financial, healthcare, and SaaS environments.

In summary, Oblivis bridges the gap between theoretical privacy primitives and practical, scalable deployment in modern cloud and edge computing ecosystems, offering a suite of tools that are both faster and more secure than existing alternatives.