Back to search

University of Waterloo

Parallel Oblivious Joins using Radix Partitioning

Abstract

dc:description.abstract

We present parallel doubly oblivious algorithms for both non-foreign key and foreign key joins using an oblivious radix partitioning technique. Oblivious query processing enables secure execution over encrypted data when organizations outsource data to the cloud. When the cloud server processes encrypted data within hardware enclaves, the data is vulnerable to side-channel leaks caused by data-dependent memory access patterns and control flow. Our algorithms efficiently defend against these vulnerabilities by combining data partitioning with parallel execution. Specifically, we propose a doubly oblivious radix partitioning approach that divides input arrays into disjoint partitions without leaking the multiplicity of individual elements, unlike vanilla radix partitioning. This is especially important for join operations, where duplicate keys are common. To construct our join algorithm, we apply oblivious radix partitioning independently to each input table, allowing the algorithm to compare tuples only within corresponding partitions. When input tables are presorted, our oblivious join algorithm is the first to avoid combining and obliviously resorting them, yielding performance improvements over the state-of-the-art scheme, Obliviator. Beyond joins, our oblivious radix partitioning technique is a standalone primitive with applications to a broad class of problems, including oblivious aggregation and private set intersection.

Degree

thesis:*
Grantor dc:publisher
University of Waterloo
Year dc:date.issued
2025

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Ahmed, Nafis

Subjects

dc:subject × 3

Rights

Language dc:language.iso
en

Identifiers

dc:identifier.*
Handle dc:identifier.uri
https://hdl.handle.net/10012/22747

Chain of custody

source
Harvested from
University of Waterloo
Base URL
dspacemainprd01.lib.uwaterloo.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Ahmed, Nafis. Parallel Oblivious Joins using Radix Partitioning. University of Waterloo, 2025. https://hdl.handle.net/10012/22747