Paper 2023/1258

Efficient Oblivious Sorting and Shuffling for Hardware Enclaves

Tianyao Gu, Carnegie Mellon University
Yilei Wang, Alibaba Group (China)
Bingnan Chen, Hong Kong University of Science and Technology
Afonso Tinoco, Carnegie Mellon University
Elaine Shi, Carnegie Mellon University
Ke Yi, Hong Kong University of Science and Technology

Oblivious sorting is arguably the most important building block in the design of efficient oblivious algorithms. We propose new oblivious sorting algorithms for hardware enclaves. Our algorithms achieve asymptotic optimality in terms of both computational overhead and the number of page swaps the enclave has to make to fetch data from insecure memory or disk. We also aim to minimize the concrete constants inside the big-O. One of our algorithms achieve bounds tight to the constant in terms of the number of page swaps. We have implemented our algorithms and made them publicly available through open source. In comparison with (an unoptimized version of) bitonic sort, which is asymptotically non-optimal but the de facto algorithm used in practice, we achieve a speedup of 2000 times for 12 GB inputs.

Available format(s)
Publication info
ObliviousSortingShufflingEnclaveSGXExternal memory algorithmCloud computing security
Contact author(s)
tianyaog @ cmu edu
fengmi wyl @ alibaba-inc com
bchenba @ cse ust hk
atinoco @ andrew cmu edu
runting @ gmail com
yike @ cse ust hk
2023-08-21: approved
2023-08-20: received
See all versions
Short URL
Creative Commons Attribution


      author = {Tianyao Gu and Yilei Wang and Bingnan Chen and Afonso Tinoco and Elaine Shi and Ke Yi},
      title = {Efficient Oblivious Sorting and Shuffling for Hardware Enclaves},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1258},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.