Cryptography, Security, and Privacy (CrySP)

You are here

Cryptography, Security, and Privacy (CrySP) »

Fully Oblivious Algorithms

On this page:

Fast Fully Oblivious Compaction and Shuffling

Sajin Sasy, Aaron Johnson, and Ian Goldberg

Citation: Sajin Sasy, Aaron Johnson, Ian Goldberg. "Fast Fully Oblivious Compaction and Shuffling". 29th ACM Conference on Computer and Communications Security, November 2022.

Paper: CCS 2022 version; extended version. The extended version makes a small correction to the pseudocode for BORPStream in Figures 9 and 10, as well improving its notation. It also provides appendices including definitions, proofs, and additional experimentation graphs.

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 5× 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.8×—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.4× 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.2×. We additionally give parallel versions of all of our algorithms, prove that they have low parallel step complexity, and experimentally show a 5–6× 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.

Code: Version 20220901

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

Sajin Sasy, Aaron Johnson, and Ian Goldberg

Citation: Sajin Sasy, Aaron Johnson, Ian Goldberg. "Waks-On/Waks-Off: Fast Oblivious Offline/Online Shuffling and Sorting with Waksman Networks". 30th ACM Conference on Computer and Communications Security, November 2023.

Paper: CCS 2023 version; extended version. The extended version provides appendices including proofs, implementation optimizations, and additional experiments.

Abstract: 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 data. Oblivious shuffling and sorting are two fundamental primitives that are frequently used for permuting data in privacy-preserving solutions. We present novel oblivious shuffling and sorting algorithms in the offline/online model such that the bulk of the computation can be done in an offline phase that is independent of the data to be permuted. The resulting online phase provides performance improvements over state-of-the-art oblivious shuffling and sorting algorithms both asymptotically (O(β n log n) vs. O(β n log2 n)) and concretely (>5× and >3× speedups), when permuting n items each of size β.

Our work revisits Waksman networks, and it uses 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 algorithm to this end. The total costs (inclusive of offline computation) of our WaksShuffle shuffling algorithm and our WaksSort sorting algorithm are lower than all other fully oblivious shuffling and sorting algorithms when the items are at least moderately sized (i.e., β > 1400 B), and the performance gap only widens as the item sizes increase. Furthermore, WaksShuffle improves the online cost of oblivious shuffling by >5× for shuffling 220 items of any size; similarly WaksShuffle+QS, our other sorting algorithm, provides >2.7× speedups in the online cost of oblivious sorting.

Code: Version 20230704