Waks-On/Waks-Off: Fast Oblivious Offline/Online Shuffling and Sorting with Waksman Networks

As more privacy-preserving solutions leverage trusted execution environments (TEEs) like Intel SGX, it becomes pertinent that these solutions can by design thwart TEE side-channel attacks that research has brought to light. In particular, such solutions need to be fully oblivious to circumvent leaking private information through memory or timing side channels.

In this work, we present fast fully oblivious algorithms for shuffling and sorting of data. Oblivious shuffling and sorting of data are two fundamental primitives that are frequently used for permuting data in privacy-preserving solutions. We present novel oblivious shuffling and sorting algorithms that work in the offline/online model such that the bulk of the computation can be done in an offline phase independent of the data to be permuted, resulting in an online phase that is asymptotically (O(βn log n)) and concretely (>5× and >3×) more efficient than the state-of-the-art solutions for oblivious shuffling and sorting (O(β n log² n)) when permuting n items, each of size β.

Our work revisits Waksman networks, and leverages the key observation that setting the control bits of a Waksman network for a uniformly random shuffle is independent of the data to be shuffled. However, setting the control bits of a Waksman network efficiently and fully obliviously poses a challenge, and we provide a novel control bit setting algorithm to this end. The total cost (inclusive of offline computation) of our algorithms WaksShuffle and WaksSort are lower than all other fully oblivious shuffling and sorting algorithms for moderately sized problems (β > 1400 B), and the performance gap only widens with increase in item sizes. Furthermore, our shuffling algorithm WaksShuffle improves the online cost of oblivious shuffling by >5× for shuffling 220 items of any size; similarly WaksShuffle+QS provides >2.7× speedups in the online cost of oblivious sorting.