Paper 2022/1333

Fast Fully Oblivious Compaction and Shuffling

Abstract

Several privacy-preserving analytics frameworks have been proposed that use trusted execution environments (TEEs) like Intel SGX. Such frameworks often use compaction and shuffling as core primitives. However, due to advances in TEE side-channel attacks, these primitives, and the applications that use them, should be _fully oblivious_; that is, perform instruction sequences and memory accesses that do not depend on the secret inputs. Such obliviousness would eliminate the threat of leaking private information through memory or timing side channels, but achieving it naively can result in a significant performance cost. In this work, we present fast, fully oblivious algorithms for compaction and shuffling. We implement and evaluate our designs to show that they are practical and outperform the state of the art. Our oblivious compaction algorithm, ORCompact, is always faster than the best alternative and can yield up to a 5x performance improvement. For oblivious shuffling, we provide two novel algorithms: ORShuffle and BORPStream. ORShuffle outperforms prior fully oblivious shuffles in all experiments, and it provides the largest speed increases—up to 1.8x—when shuffling a large number of small items. BORPStream outperforms all other algorithms when shuffling a large number of large items, with a speedup of up to 1.4x in such cases. It can obtain even larger performance improvements in application settings where the items to shuffle arrive incrementally over time, obtaining a speedup of as much as 4.2x. We additionally give parallel versions of all of our algorithms, prove that they have low parallel step complexity, and experimentally show a 5–6x speedup on an 8-core processor. Finally, ours is the first work with the explicit goal of ensuring full obliviousness of complex functionalities down to the implementation level. To this end, we design Fully Oblivious Assembly Verifier (FOAV), a tool that verifies the binary has no secret-dependent conditional branches.

Note: This version makes the following minor changes to the previous ePrint version (i.e. the version uploaded on 2022-10-6): 1. Added Xian Wang to acknowledgements. 2. Added clarifying parentheses before modulus operator in Fig. 1 (Line 6), Fig. 3 (Line 7), and Fig. 4 (Line 6). 3. Corrected ORCompact (Fig. 2) by adding $mod n_1$ to Line 4. 4. Corrected ORCompact (Fig. 2) by changing $[i > m]$ to $[i \ge m]$ (Line 6). The example comparison in Sec. 3.3 was also updated to be consistent. 5. Corrected ORCPar (Fig. 4) by changing $[i > S_{n_2}]$ to $[i \ge S_{n_2}]$ (Line 8). 6. Fixed spacing issue in App. A. 7. Added clarifying parentheses before modulus operator in App. B.1. 8. In proof of Thm. 1 (App. B.1), corrected stated offset to (n_1-n_2+m) mod n_1.