File Download
There are no files associated with this item.
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1137/1.9781611975031.143
- Scopus: eid_2-s2.0-85037816872
Supplementary
-
Citations:
- Scopus: 0
- Appears in Collections:
Conference Paper: Cache-Oblivious and Data-Oblivious Sorting and Applications
Title | Cache-Oblivious and Data-Oblivious Sorting and Applications |
---|---|
Authors | |
Issue Date | 2018 |
Publisher | Society for Industrial and Applied Mathematics. |
Citation | 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2018), New Orleans, LA, 7-10 January 2018. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018, p. 2201-2220 How to Cite? |
Abstract | Although external-memory sorting has been a classical algorithms abstraction and has been heavily studied in the literature, perhaps somewhat surprisingly, when data-obliviousness is a requirement, even very rudimentary questions remain open. Prior to our work, it is not even known how to construct a comparison-based, external-memory oblivious sorting algorithm that is optimal in IO-cost.
We make a significant step forward in our understanding of external-memory, oblivious sorting algorithms. Not only do we construct a comparison-based, external-memory oblivious sorting algorithm that is optimal in IO-cost, our algorithm is also cache-agnostic in that the algorithm need not know the storage hierarchy's internal parameters such as the cache and cache-line sizes. Our result immediately implies a cache-agnostic ORAM construction whose asymptotic IO-cost matches the best known cache-aware scheme.
Last but not the least, we propose and adopt a new and stronger security notion for external-memory, oblivious algorithms and argue that this new notion is desirable for resisting possible cache-timing attacks. Thus our work also lays a foundation for the study of oblivious algorithms in the cache-agnostic model. |
Persistent Identifier | http://hdl.handle.net/10722/259641 |
ISBN |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Chan, HTH | - |
dc.contributor.author | Guo, Y | - |
dc.contributor.author | Lin, WK | - |
dc.contributor.author | Shi, E | - |
dc.date.accessioned | 2018-09-03T04:11:19Z | - |
dc.date.available | 2018-09-03T04:11:19Z | - |
dc.date.issued | 2018 | - |
dc.identifier.citation | 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2018), New Orleans, LA, 7-10 January 2018. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018, p. 2201-2220 | - |
dc.identifier.isbn | 978-1-6119-7503-1 | - |
dc.identifier.uri | http://hdl.handle.net/10722/259641 | - |
dc.description.abstract | Although external-memory sorting has been a classical algorithms abstraction and has been heavily studied in the literature, perhaps somewhat surprisingly, when data-obliviousness is a requirement, even very rudimentary questions remain open. Prior to our work, it is not even known how to construct a comparison-based, external-memory oblivious sorting algorithm that is optimal in IO-cost. We make a significant step forward in our understanding of external-memory, oblivious sorting algorithms. Not only do we construct a comparison-based, external-memory oblivious sorting algorithm that is optimal in IO-cost, our algorithm is also cache-agnostic in that the algorithm need not know the storage hierarchy's internal parameters such as the cache and cache-line sizes. Our result immediately implies a cache-agnostic ORAM construction whose asymptotic IO-cost matches the best known cache-aware scheme. Last but not the least, we propose and adopt a new and stronger security notion for external-memory, oblivious algorithms and argue that this new notion is desirable for resisting possible cache-timing attacks. Thus our work also lays a foundation for the study of oblivious algorithms in the cache-agnostic model. | - |
dc.language | eng | - |
dc.publisher | Society for Industrial and Applied Mathematics. | - |
dc.relation.ispartof | Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms | - |
dc.title | Cache-Oblivious and Data-Oblivious Sorting and Applications | - |
dc.type | Conference_Paper | - |
dc.identifier.email | Chan, HTH: hubert@cs.hku.hk | - |
dc.identifier.authority | Chan, HTH=rp01312 | - |
dc.description.nature | link_to_OA_fulltext | - |
dc.identifier.doi | 10.1137/1.9781611975031.143 | - |
dc.identifier.scopus | eid_2-s2.0-85037816872 | - |
dc.identifier.hkuros | 287938 | - |
dc.identifier.spage | 2201 | - |
dc.identifier.epage | 2220 | - |
dc.publisher.place | United States | - |