File Download
There are no files associated with this item.
Supplementary
-
Citations:
- Appears in Collections:
Conference Paper: Bucket Oblivious Sort: An Extremely Simple Oblivious Sort
Title | Bucket Oblivious Sort: An Extremely Simple Oblivious Sort |
---|---|
Authors | |
Issue Date | 2020 |
Publisher | Society for Industrial and Applied Mathematics. |
Citation | Proceedings of the Third Symposium on Simplicity in Algorithms (SOSA 2020), Salt Lake City, Utah, USA, 6-7 January 2020, p. 8-14 How to Cite? |
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. |
Persistent Identifier | http://hdl.handle.net/10722/290710 |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Asharov, G | - |
dc.contributor.author | Chan, HTH | - |
dc.contributor.author | Nayak, K | - |
dc.contributor.author | Pass, R | - |
dc.contributor.author | Ren, L | - |
dc.contributor.author | Shi, E | - |
dc.date.accessioned | 2020-11-02T05:46:01Z | - |
dc.date.available | 2020-11-02T05:46:01Z | - |
dc.date.issued | 2020 | - |
dc.identifier.citation | Proceedings of the Third Symposium on Simplicity in Algorithms (SOSA 2020), Salt Lake City, Utah, USA, 6-7 January 2020, p. 8-14 | - |
dc.identifier.uri | http://hdl.handle.net/10722/290710 | - |
dc.description.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. | - |
dc.language | eng | - |
dc.publisher | Society for Industrial and Applied Mathematics. | - |
dc.relation.ispartof | Symposium on Simplicity in Algorithms Proceedings | - |
dc.title | Bucket Oblivious Sort: An Extremely Simple Oblivious Sort | - |
dc.type | Conference_Paper | - |
dc.identifier.email | Chan, HTH: hubert@cs.hku.hk | - |
dc.identifier.authority | Chan, HTH=rp01312 | - |
dc.identifier.doi | 10.1137/1.9781611976014.2 | - |
dc.identifier.hkuros | 318358 | - |
dc.identifier.spage | 8 | - |
dc.identifier.epage | 14 | - |
dc.publisher.place | Philadelphia, PA | - |
dc.identifier.eisbn | 9781611976014 | - |