Distributed Oblivious Compaction and Applications to Joins

The Hong Kong University of Science and Technology
Department of Computer Science and Engineering


MPhil Thesis Defence


Title: "Distributed Oblivious Compaction and Applications to Joins"

By

Mr. Xian WANG


Abstract:

Cloud service providers, such as Amazon and Google, employ cryptographic 
primitives and trusted execution environments (TEEs) to safeguard private 
data. TEEs play a crucial role in enabling privacy-preserving computations; 
however, they are vulnerable to access-pattern and side-channel attacks when 
solely relying on encryption. Recent advancements in TEE-based oblivious 
databases aim to mitigate these vulnerabilities by protecting memory access 
patterns and isolating software side channels. Significantly, recent 
research (VLDB'20; USENIX-SEC'25) has introduced effective oblivious 
primitives for database operations, including join and sort operations. 
Nevertheless, these single-server solutions encounter scalability challenges 
due to the limited size of the Enclave Page Cache (EPC) and the overhead 
associated with intensive page swaps, particularly when dealing with large 
datasets. To address these constraints, research initiatives such as Opaque 
(NSDI'17) and Jodes (VLDB'25) have investigated distributed oblivious 
primitives for database joins within TEEs. Despite these advancements, 
challenges persist, including performance bottlenecks, large constants in 
computational complexity, and a lack of full parallelism.

This thesis proposes scalable and distributed oblivious algorithms that 
prioritize parallelism, algorithmic complexity, practical constants, and 
communication costs. We introduce the first distributed oblivious compaction 
and expansion algorithms across multiple servers. Our work also includes 
improved distributed oblivious sorting and aggregation tree algorithms that 
are more efficient. Additionally, we apply the above algorithms and 
implement new scalable and distributed oblivious joins. These algorithms 
have smaller constants and communication overhead and are fully 
parallelized. The improved aggregation tree algorithm offers O(log N) 
complexity and O(1) communication overhead, and the remaining algorithms 
have O(N log N) complexity and O(N) communication overhead. Our extensive 
evaluations show speedups of 5.8 to 27.7x for compaction, up to 11.0x for 
sorting, and 3.55x for aggregation trees. Our joins surpass baselines by 
1.43 to 89.2x, demonstrating superior scalability.


Date:                   Friday, 27 June 2025

Time:                   2:00pm - 4:00pm

Venue:                  Room 3494
                        Lifts 25/26

Chairman:               Dr. Shuai WANG

Committee Members:      Dr. Dimitris PAPADOPOULOS (Supervisor)
                        Prof. Cunsheng DING