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 $6nlog 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 $3times$ slower than a
non-oblivious merge sort baseline; for $2^{30}$ elements, it is $5times$
faster than bitonic sort, the de facto oblivious sorting algorithm in practical
implementations.

By admin