Paper 2024/627

Distributed & Scalable Oblivious Sorting and Shuffling

Nicholas Ngai, University of California, Berkeley
Ioannis Demertzis, University of California, Santa Cruz
Javad Ghareh Chamani, Hong Kong University of Science and Technology
Dimitrios Papadopoulos, Hong Kong University of Science and Technology
Abstract

Existing oblivious systems offer robust security by concealing memory access patterns, but they encounter significant scalability and performance challenges. Recent efforts to enhance the practicality of these systems involve embedding oblivious computation, e.g., oblivious sorting and shuffling, within Trusted Execution Environments (TEEs). For instance, oblivious sort has been heavily utilized: in Oblix (S&P'18), when oblivious indexes are created and accessed; in Snoopy's high-throughput oblivious key-value (SOSP'21) during initialization and when the input requests are deduplicated and prepared for delivery; in Opaque (NSDI'17) for all the proposed oblivious SQL operators; in the state-of-the-art non-foreign key oblivious join approach (PVLDB'20). Additionally, oblivious sort/shuffle find applications in Signal's commercial solution for contact discovery, anonymous Google's Key Transparency, Searchable Encryption, software monitoring, and differentially private federated learning with user privacy. In this work, we address the scalability bottleneck of oblivious sort and shuffle by re-designing these approaches to achieve high efficiency in distributed multi-enclave environments. First, we propose a multi-threaded bitonic sort optimized for the distributed setting, making it the most performant oblivious sort for small number of enclaves (up to 4). For larger numbers of enclaves, we propose a novel oblivious bucket sort, which improves data locality and network consumption and outperforms our optimized distributed bitonic-sort by up to 5-6x. To the best of our knowledge, these are the first distributed oblivious TEE-based sorting solutions. For reference, we are able to sort 2 GiB of data in 1 second and 128 GiB in 53.4 seconds in a multi-enclave test. A fundamental building block of our oblivious bucket-sort is an oblivious shuffle that improves the prior state-of-the-art result (CCS'22) by up to 9.5x in the distributed multi-enclave setting---interestingly it is better by 10% even in the single-enclave/multi-thread setting.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. IEEE S&P 2024 (Oakland)
Keywords
oblivious sortshuffledistributedscalable
Contact author(s)
nicholas ngai @ berkeley edu
idemertz @ ucsc edu
jgc @ cse ust hk
dipapado @ cse ust hk
History
2024-04-26: approved
2024-04-24: received
See all versions
Short URL
https://ia.cr/2024/627
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2024/627,
      author = {Nicholas Ngai and Ioannis Demertzis and Javad Ghareh Chamani and Dimitrios Papadopoulos},
      title = {Distributed & Scalable Oblivious Sorting and Shuffling},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/627},
      year = {2024},
      url = {https://eprint.iacr.org/2024/627}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.