Bucket Oblivious Sort: An Extremely Simple Oblivious Sort
Publication
, Conference
Asharov, G; Chan, THH; Nayak, K; Pass, R; Ren, L; Shi, E
Published in: 3rd SIAM Symposium on Simplicity in Algorithms Sosa 2020
January 1, 2020
We propose a conceptually simple oblivious sort and oblivious random permutation algorithms called bucket oblivious sort and bucket oblivious random permutation. Bucket oblivious sort uses 6n log n time (measured by the number of memory accesses) and 2Z client storage with an error probability exponentially small in Z. The above runtime is only 3× slower than a non-oblivious merge sort baseline; for 230 elements, it is 5× faster than bitonic sort, the de facto oblivious sorting algorithm in practical implementations.
Duke Scholars
Published In
3rd SIAM Symposium on Simplicity in Algorithms Sosa 2020
Publication Date
January 1, 2020
Start / End Page
8 / 14
Citation
APA
Chicago
ICMJE
MLA
NLM
Asharov, G., Chan, T. H. H., Nayak, K., Pass, R., Ren, L., & Shi, E. (2020). Bucket Oblivious Sort: An Extremely Simple Oblivious Sort. In 3rd SIAM Symposium on Simplicity in Algorithms Sosa 2020 (pp. 8–14).
Asharov, G., T. H. H. Chan, K. Nayak, R. Pass, L. Ren, and E. Shi. “Bucket Oblivious Sort: An Extremely Simple Oblivious Sort.” In 3rd SIAM Symposium on Simplicity in Algorithms Sosa 2020, 8–14, 2020.
Asharov G, Chan THH, Nayak K, Pass R, Ren L, Shi E. Bucket Oblivious Sort: An Extremely Simple Oblivious Sort. In: 3rd SIAM Symposium on Simplicity in Algorithms Sosa 2020. 2020. p. 8–14.
Asharov, G., et al. “Bucket Oblivious Sort: An Extremely Simple Oblivious Sort.” 3rd SIAM Symposium on Simplicity in Algorithms Sosa 2020, 2020, pp. 8–14.
Asharov G, Chan THH, Nayak K, Pass R, Ren L, Shi E. Bucket Oblivious Sort: An Extremely Simple Oblivious Sort. 3rd SIAM Symposium on Simplicity in Algorithms Sosa 2020. 2020. p. 8–14.
Published In
3rd SIAM Symposium on Simplicity in Algorithms Sosa 2020
Publication Date
January 1, 2020
Start / End Page
8 / 14