Jodes: Efficient Oblivious Join in the Distributed Setting

Download PDF

Abstract

Trusted execution environment (TEE) has provided an isolated and secure environment for building cloud-based analytic systems, but it still suffers from access pattern leakages caused by side- channel attacks. To better secure the data, computation inside TEE enclave should be made oblivious, which introduces significant overhead and severely slows down the computation. A natural way to speed up is to build the analytic system with multiple servers in the distributed setting. However, this setting raises a new security concern—the volumes of the transmissions among these servers can leak sensitive information to a network adversary. Existing works have designed specialized algorithms to address this concern, but their supports for equi-join, one of the most important but non- trivial database operators, are either inefficient, limited, or under a weak security assumption. In this paper, we present Jodes, an efficient oblivious join al- gorithm in the distributed setting. Jodes prevents the leakage on both the network and enclave sides, supports a general equi-join operation, and provides a high security level protection that only publicizes the input sizes and the output size. Meanwhile, it achieves both communication cost and computation cost asymptotically su- perior to existing algorithms. To demonstrate the practicality of Jodes, we conduct experiments in the distributed setting compris- ing 16 servers. Empirical results show that Jodes achieves up to a sixfold performance improvement over state-of-the-art join algo- rithms.