💻 computer science

ORQ: Complex Analytics on Private Data with Strong Security Guarantees

ORQ is a novel system that enables efficient, cryptographically secure collaborative analysis of large private datasets by eliminating the quadratic cost of secure joins through on-the-fly aggregation, thereby achieving TPC-H Scale Factor 10 performance under multi-party computation without relying on trusted third parties or information leakage.

Original authors: Eli Baum, Sam Buxbaum, Nitin Mathai, Muhammad Faisal, Vasiliki Kalavri, Mayank Varia, John Liagouris

Published 2026-06-24

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Eli Baum, Sam Buxbaum, Nitin Mathai, Muhammad Faisal, Vasiliki Kalavri, Mayank Varia, John Liagouris

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 the captain of a ship, and you have three other captains. Each of you holds a secret map with valuable treasure locations, but none of you trust the others enough to show your maps. You want to work together to find the best route that combines all your maps, but you don't want to reveal where your specific treasures are, or even how many treasures you have.

This is the problem Orq solves.

The Problem: The "Quadratic Explosion"

In the world of secure computing, there's a technique called Multiparty Computation (MPC). It allows people to compute things together without revealing their private data. Think of it like a group of people solving a math problem where everyone writes their numbers on a piece of paper, but they only pass around "scrambled" versions of those numbers.

However, there's a big bottleneck: Joins.
Imagine you have two lists of names. You want to find everyone who appears on both lists.

The Old Way: If you try to do this securely without revealing anything, the computers have to check every single name in List A against every single name in List B. If List A has 1,000 names and List B has 1,000 names, the computer has to do 1,000,000 checks (1,000 x 1,000).
The "Cascading" Nightmare: If you have three lists to join, the checks explode to 1,000,000,000. If you have four, it's a trillion. This is called the "quadratic blowup." It's like trying to find a needle in a haystack, but every time you look, the haystack doubles in size. Previous systems either gave up, leaked secrets to avoid this explosion, or needed a "trusted" third party (like a judge) to watch over them.

The Solution: Orq (The "Smart Sorter")

The researchers built a system called Orq that changes the rules of the game. Instead of blindly checking every combination, Orq uses a clever trick: It sorts the lists first.

Think of it like organizing a messy library.

The Old Way: You walk up to every book in the library and ask, "Is this book about cats?" You do this for every single book, even if they are all in the wrong section.
The Orq Way: You first organize the books alphabetically. Now, if you want to find all the "Cat" books, you just go to the "C" section. You don't need to check the "A" or "Z" sections.

Orq does this with data. It sorts the secret data so that matching items end up right next to each other. This turns the impossible "check everything" task into a manageable "check neighbors" task.

The Secret Sauce: "On-the-Fly" Aggregation

The paper highlights a specific insight: In most real-world questions (like "How much money did we make?"), we don't actually need to see the final list of every single transaction. We just need the total.

Orq uses a technique called Join-Aggregation.

Imagine a Relay Race: Instead of running the whole race, stopping to count every step, and then running again, Orq combines the running and the counting into one smooth motion.
As the data moves through the system, Orq joins the tables and adds up the numbers (aggregates) at the exact same time. It never creates the massive, intermediate list of all possible combinations. It keeps the size of the data bounded, like a bucket that never overflows, no matter how much water you pour in.

The Results: Speed and Scale

The researchers tested Orq in two environments:

LAN (Local Area Network): Computers in the same building.
WAN (Wide Area Network): Computers across the internet (like different countries).

What they found:

Speed: Orq is dramatically faster than previous systems. In some cases, it was 800 times faster.
Scale: They were able to run the famous TPC-H benchmark (a standard test for database performance) with a "Scale Factor 10." This means they processed 58 million rows of data entirely under secure encryption.
- Context: Previous secure systems could only handle this much data if they leaked secrets or used a trusted third party. Orq did it with zero leakage and no trusted third party.
Security: It works even if some of the computers are "malicious" (trying to cheat) or "semi-honest" (following the rules but trying to peek).

The Takeaway

Orq is like a new, super-efficient engine for a secure car. Before, trying to drive a secure car with a heavy load (complex data) was so slow and dangerous that people either didn't drive it or took off the safety locks (leaking data). Orq redesigned the engine so you can drive fast, carry a massive load, and keep the safety locks firmly in place.

They have even made the code open-source, so anyone can use this "engine" to build their own secure data analysis tools.

Technical Summary: Orq – Complex Analytics on Private Data with Strong Security Guarantees

1. Problem Statement

The paper addresses the challenge of performing complex relational analytics (specifically multi-way joins and aggregations) on large private datasets within an outsourced Secure Multiparty Computation (MPC) setting. In this setting, data owners distribute secret shares of their data to a set of untrusted, non-colluding computing parties (servers).

The core bottleneck in prior MPC systems is the cascading effect of oblivious joins. To maintain obliviousness (hiding access patterns and data distribution), standard oblivious joins on tables with $n$ records must produce a worst-case output of size $n^2$ (the Cartesian product). For queries involving multiple joins ( $k$ joins), this leads to $O(n^{k+1})$ time and space complexity, rendering complex queries intractable for large datasets.

Existing solutions face a trilemma:

Quadratic Cost: Compute the full Cartesian product (expensive).
Silent Dropping: Enforce a sub-quadratic bound by silently dropping records (incorrect).
Leakage: Leak the size of the join result to servers (insecure).

Prior works in outsourced settings (e.g., Secrecy, Scape) either suffer from quadratic costs or leak result sizes. Furthermore, many existing systems rely on trusted compute bases (TCBs) or specific data ownership models (e.g., peer-to-peer where owners are also compute parties) that do not generalize to the outsourced model where servers never see plaintext.

2. Methodology

Orq introduces a holistic system runtime designed to evaluate complex queries with $O(n \log n)$ complexity, avoiding the quadratic blowup without leaking information.

2.1 Core Insight: Data-Independent Bounds

The authors observe that in many practical collaborative analytics scenarios, the size of the query result is worst-case bounded by the input size ( $O(n)$ ), independent of the data distribution. This holds even for many-to-many joins, provided the query structure allows for decomposable aggregation. Orq leverages this observation to bound intermediate result sizes.

2.2 The Composite Join-Aggregation Operator

The central innovation is a fused Join-Aggregation operator that avoids materializing the Cartesian product.

Mechanism: Instead of joining first and then aggregating, Orq performs a "MapReduce-style" evaluation. It applies a pre-aggregation (partial evaluation) on input tables to handle duplicates, performs the join, and then applies a post-aggregation.
Implementation: The operator concatenates input tables, sorts them obliviously on the join keys, and uses a butterfly-style Aggregation Network (AggNet) to propagate values and compute aggregates in a single control flow.
Support: It supports inner, outer, semi-, and anti-joins, as well as arbitrary user-defined aggregations (sum, count, min, max, avg).
Handling Duplicates: For many-to-many joins, Orq pre-aggregates one input to create unique keys (multiplicity), joins, and then post-aggregates to combine multiplicities. This ensures the intermediate table size never exceeds the cardinality of the larger input.

2.3 Oblivious Primitives and Sorting

To support the join-aggregation operator, Orq implements state-of-the-art oblivious primitives:

Sorting: Orq provides vectorized, data-parallel implementations of Quicksort and Radixsort.
- Quicksort: Uses an iterative, shuffle-then-sort paradigm to reduce communication rounds to $O(\log n)$ .
- Radixsort: Uses a hybrid approach combining eager bit-permutation with oblivious shuffling.
- TableSort: A wrapper that extracts the sorting permutation from a padded sort and applies it to all columns of a table, avoiding redundant sorting of multiple columns.
Shuffling: Generalized oblivious shuffling primitives compatible with various MPC protocols.
Vectorization: All operators are implemented using a columnar data format, allowing independent messages within a stage to be batched and sent in a single communication round.

2.4 System Architecture

Dataflow API: Users define queries using a dataflow-style API (similar to Apache Spark) rather than SQL, allowing for concise expression of complex pipelines.
Protocol Agnosticism: Operators are built as black-box abstractions over MPC primitives ( $+, \times, \oplus, \land$ $+, \times, \oplus, \land$ ). Orq supports three protocols:
1. Semi-honest, dishonest majority (ABY, 2-party).
2. Semi-honest, honest majority (Araki et al., 3-party).
3. Malicious-secure, honest majority (Fantastic Four, 4-party).
Communication Layer: A custom TCP-based layer with lock-free ring buffers to amortize network costs, particularly in WAN settings.

3. Key Contributions

Orq System: A complete system for complex relational analytics in the outsourced MPC setting, supporting multi-way joins and aggregations with strong security guarantees (no leakage of result sizes).
Novel Join-Aggregation Operator: A technique that decomposes and eagerly applies aggregations to bound intermediate result sizes, achieving $O(n \log n)$ complexity for joins that previously required $O(n^2)$ .
Protocol-Agnostic Primitives: A unified implementation of oblivious operators (joins, sorts, aggregations) that can be instantiated with semi-honest or malicious MPC protocols.
Scalable Sorting: Data-parallel vectorized implementations of oblivious sorting that handle up to 537 million rows, significantly outperforming prior art.
Comprehensive Evaluation: The first end-to-end MPC execution of the full TPC-H benchmark (Scale Factor 10) without leakage or trusted compute.

4. Experimental Results

The authors evaluated Orq on LAN and WAN deployments across diverse workloads, including the full TPC-H benchmark and queries from prior works.

Performance vs. State-of-the-Art:
- Vs. Secrecy: Orq achieves up to 827 $\times$ lower latency. Secrecy uses $O(n^2)$ joins and single-threaded execution; Orq uses $O(n \log n)$ and vectorization.
- Vs. SecretFlow: Orq is 1.1 $\times$ to 1.5 $\times$ faster on join queries and 58 $\times$ to 85 $\times$ faster on non-join queries, despite SecretFlow leaking join result sizes. Orq achieves this without any leakage.
- Vs. MP-SPDZ: Orq's sorting is up to 189 $\times$ faster due to data-parallelism.
Scalability:
- Orq processes Scale Factor 10 TPC-H queries (average 58M rows) entirely under MPC.
- The most expensive query (Q21) completes in 42 minutes (LAN, malicious security) and 18 hours (WAN, malicious security).
- Sorting protocols scale to 537 million rows (Quicksort, SH-HM) and 134 million rows (Radixsort, Mal-HM).
Bandwidth: Orq exhibits up to two orders of magnitude lower bandwidth consumption compared to Secrecy due to asymptotic improvements.
Preprocessing: The paper benchmarks Beaver triple generation, showing that sub-quadratic protocols (Doerner et al.) offer significant bandwidth savings over traditional methods, despite higher computational overhead.

5. Significance and Claims

The paper claims that Orq represents a significant step forward in making secure analytics practical for real-world, large-scale collaborative data analysis.

Breaking the Quadratic Barrier: Orq demonstrates that efficient, fully oblivious evaluation of complex multi-way joins is possible without leaking result sizes or relying on trusted hardware.
Practicality at Scale: By successfully running the full TPC-H benchmark at Scale Factor 10 (previously only achievable with leakage or trusted compute), Orq proves that MPC can handle enterprise-scale workloads.
Generality: The system is not restricted to specific data ownership models or threat models, supporting both semi-honest and malicious adversaries in outsourced settings.
Open Source: The authors have released Orq as open-source to facilitate further research and adoption.

The authors note that while they currently require a dataflow API (rather than an automatic SQL planner), the system's performance and security properties establish a new baseline for secure relational analytics. Future work includes integrating automatic query planning and further optimizing malicious checks for WAN environments.