Flexway O-Sort: Enclave-Friendly and Optimal Oblivious Sorting

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.32× to 28.8× when the data fits within the hardware enclave, and by 4.1× to 208× 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.3× speedup over bitonic sort when the data fits within the enclave, and 4.9 ∼ 5.5× speedup when the data does not fit within the enclave. To the best of our knowledge, our flexway o-sort is the first concretely efficient algorithm that achieves optimality in both dimensions. Specifically, our flexway o-sort algorithm achieves (2.23 + o( 1 ))N log N work and (3 + o(1)) N B log M B N B number of page swaps where B denotes the page size, and M denotes the size of the EPC memory. Open-source implementation. We implemented our algorithm and evaluated their concrete performance. The core algorithm implementation (counting both oblivious sorting algorithms) has 1,600 lines of code. Although our implementation uses Intel SGX, the algorithm design should work for any common hardware enclave architecture. Our implementation has been made open source at https://github.com/odslib/ oblsort. Evaluation. We show that our algorithm achieves significant speedup over prior oblivious sorting algorithms for both the [EPC ≥ data] and [EPC < data] scenarios. For an array of 12 GB size, our speedup over prior algorithms is depicted in the following table where for the [EPC < data] scenario, we adopt an EPC size of 128 MB which is the same as SGXv1: Scheme Our speedup EPC ≥ data EPC < data Randomized Shellsort 28.8× 208× Bitonic (non-recursive impl.) 5.49× 38.4× Bitonic (recursive impl.) 1.32× 4.10× Multi-way bucket o-sort [43] 14.3× 12.4× We also implemented various applications that rely on oblivious sorting, including histogram, ORAM initialization, and database join. We measure the end-to-end application performance when using our flexway o-sort, and compare it with (recursive) bitonic sort as a baseline. For these applications, we achieve 1.44 ∼ 2.3× speedup when the data fits within the enclave, and 4.9 ∼ 5.5× speedup when the data does not fit within the enclave. Distribution o-sort. We also provide the distribution o-sort algorithm in Section B, which is a variant of our flexway o-sort algorithm that achieves optimal constant for the number of page swaps. Table 1 shows the performance of both our flexway o-sort and distribution o-sort algorithms in comparison with prior work. Additional result. As a byproduct, we also construct an oblivious shuffler, which randomly permutes an input array without leaking the permutation. Earlier works showed that the oblivious shuffler is also a versatile primitive in oblivious algorithms and ORAM schemes [45, 46, 30] . We give more detailed evaluation results on oblivious shuffler in Section 5.4. Technical Highlights Starting point: multi-way bucket o-sort. Ramachandran and Shi [43] constructed multi-way bucket o-sort, which is asymptotically optimal in both work and page swaps, but unfortunately suffers from astronomical constants. Their construction reduces the task of oblivious sorting N elements to an oblivious p-way MergeSplit, which can be viewed as a special sorting algorithm where the keys come from a small domain 0, 1, . . . , p -1. More precisely, a p-way MergeSplit accomplishes the following: Input: p bins each of size Z. Each bin contains real elements each marked with a key from 0, 1, . . . , p -1 and fillers. The frequency of each distinct key in the input is bounded by Z. Output: Route the real elements to p destination bins depending on their key, and each output bin is padded with fillers to its capacity Z. Ramachandran and Shi [43] showed that if we can achieve oblivious MergeSplit in O(n log n) cost where n = pZ, p = log N , and Z ∈ poly log N , then we can get oblivious sorting optimal in both work and number of page swaps.