Paper 2023/1258
Efficient Oblivious Sorting and Shuffling for Hardware Enclaves
, Carnegie Mellon University, Alibaba Group (China), Hong Kong University of Science and Technology, Carnegie Mellon University, Hong Kong University of Science and TechnologyAbstract
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.
Metadata
- Available format(s)
-
PDF
- Category
- Applications
- Publication info
- Preprint.
- Keywords
- 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 - History
- 2023-08-21: approved
- 2023-08-20: received
- See all versions
- Short URL
- https://ia.cr/2023/1258
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2023/1258,
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{https://eprint.iacr.org/2023/1258}},
url = {https://eprint.iacr.org/2023/1258}
}
