@inproceedings{8869e0e868734067ad174a8a1b073752,
title = "Bucket Oblivious Sort: An Extremely Simple Oblivious Sort",
abstract = "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.",
author = "Gilad Asharov and Chan, {T. H.Hubert} and Kartik Nayak and Rafael Pass and Ling Ren and Elaine Shi",
note = "Publisher Copyright: {\textcopyright} 2020 by SIAM.; 3rd SIAM Symposium on Simplicity in Algorithms, SOSA 2020 ; Conference date: 06-01-2020 Through 07-01-2020",
year = "2020",
language = "English (US)",
series = "3rd SIAM Symposium on Simplicity in Algorithms, SOSA 2020",
publisher = "Society for Industrial and Applied Mathematics Publications",
pages = "8--14",
editor = "Martin Farach-Colton and Gortz, {Inge Li}",
booktitle = "3rd SIAM Symposium on Simplicity in Algorithms, SOSA 2020",
address = "United States",
}