Privacy-preserving joins in untrusted environments

As cloud computing becomes the dominant computation paradigm, protecting sensitive data during processing has emerged as a critical challenge. Trusted Execution Environments (TEEs) offer a promising solution. Their ease of use, global access, and strong privacy guarantees give them a unique chance to transform cloud computing. However, executing complex data processing operations, particularly joins, within TEEs presents unique challenges due to their distinct hardware architecture. Moreover, TEEs alone may not provide sufficient protection; Active attackers can exploit side-channel vulnerabilities, such as memory access patterns, to compromise the privacy guarantees TEEs offer. This thesis investigates three fundamental aspects of implementing and deploying secure join algorithms in TEEs. First, we conduct a comprehensive experimental study of eight state-of-the-art relational joins in TEEs. We reveal new insights about their performance limitations and opportunities for improvement. Based on these insights, we provide practical guidelines for designing and deploying relational join operators in TEEs. For example, we highlight the importance of memory-efficient data structures, propose a chunking technique that reduces the data sealing time, and implement lockless synchronization that mitigates the threading bottleneck. Second, we develop a new join algorithm that takes advantage of TEE hardware features. We identify the desiderata for TEE-native processing that includes random access reduction, low memory consumption, and wait-free multi-threading. We introduce a TEE-native processing philosphy that addresses the desiderata by iteratively organizing the data. We instantiate the philosophy into a join algorithm that shows significant performance improvements both in a multi-tenant cloud scenario and as an isolated operator. We demonstrate the robustness of our algorithm and prove that efficient relational joins in TEEs are feasible. Finally, we tackle the challenge of securely joining continuous data streams. We introduce a taxonomy of five leakage profiles for oblivious stream joins. The taxonomy characterizes the performance-security tradeoff that allows users to adjust the leakage. The weakest leakage profile provides privacy guarantees comparable to deterministic encryption, while the strongest provides guarantees based on randomized encryption and full obliviousness. We then propose two families of secure stream join algorithms: Oblivious Symmetric Hash Joins (SHJ) and Oblivious Computation Approach Joins (OCA). The former is based on a widely-used Symmetric Hash Join with the addition of data encryption and ORAM-based indices. The latter removes ORAM-based indices and utilizes only oblivious operations, such as oblivious sort or shuffle. We demonstrate that the OCA joins significantly outperform the SHJ joins in latency and memory consumption in all scenarios. The outcome of this thesis is a set of practical solutions for secure join operations both for batch and stream scenarios, making privacy-preserving data processing more accessible. Our experimental evaluation shows that we accurately identify the bottlenecks and limitations of TEEs, as well as offer novel solutions to successfully overcome them.