Tianyao Gu, Carnegie Mellon University and Oblivious Labs Inc.; Yilei Wang, Alibaba Cloud; Afonso Tinoco, Carnegie Mellon University and Oblivious Labs Inc.; Bingnan Chen and Ke Yi, HKUST; Elaine Shi, Carnegie Mellon University and Oblivious Labs Inc.
Oblivious algorithms are being deployed at large scale in real world to enable privacy-preserving applications such as Signal's private contact discovery. Oblivious sorting is a fundamental building block in the design of oblivious algorithms for numerous computation tasks. Unfortunately, there is still a theory-practice gap for oblivious sort. The commonly implemented bitonic sorting algorithm is not asymptotically optimal, whereas known asymptotically optimal algorithms suffer from large constants.
In this paper, we construct a new oblivious sorting algorithm called flexway o-sort, which is asymptotically optimal, concretely efficient, and suitable for implementation in hardware enclaves such as Intel SGX. For moderately large inputs of 12 GB, our flexway o-sort algorithm outperforms known oblivious sorting algorithms by 1.32x to $28.8x when the data fits within the hardware enclave, and by 4.1x to 208x when the data does not fit within the hardware enclave. We also implemented various applications of oblivious sorting, including histogram, database join, and initialization of an ORAM data structure. For these applications and data sets from 8GB to 32GB, we achieve 1.44 ∼ 2.3x speedup over bitonic sort when the data fits within the enclave, and 4.9 ∼ 5.5x speedup when the data does not fit within the enclave.
Open Access Media
USENIX is committed to Open Access to the research presented at our events. Papers and proceedings are freely available to everyone once the event begins. Any video, audio, and/or slides that are posted after the event are also free and open to everyone. Support USENIX and our commitment to Open Access.
