File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: Oblivious data structures

TitleOblivious data structures
Authors
KeywordsCryptography
Oblivious algorithms
Security
Issue Date2014
PublisherAssociation for Computing Machinery, Inc.
Citation
The 2014 ACM Conference on Computer and Communications Security (CCS'14) Scottsdale, AZ., 3-7 November 2014. In Conference Proceedings, 2014, p. 215-226 How to Cite?
AbstractWe design novel, asymptotically more efficient data structures and algorithms for programs whose data access patterns exhibit some degree of predictability. To this end, we propose two novel techniques, a pointer-based technique and a locality-based technique. We show that these two techniques are powerful building blocks in making data structures and algorithms oblivious. Specifically, we apply these techniques to a broad range of commonly used data structures, including maps, sets, priority-queues, stacks, deques; and algorithms, including a memory allocator algorithm, max-flow on graphs with low doubling dimension, and shortestpath distance queries on weighted planar graphs. Our oblivious counterparts of the above outperform the best known ORAM scheme both asymptotically and in practice. Copyright is held by the owner/author(s). Publication rights licensed to ACM.
Persistent Identifierhttp://hdl.handle.net/10722/214753
ISBN
ISSN

 

DC FieldValueLanguage
dc.contributor.authorWang, XS-
dc.contributor.authorNayak, K-
dc.contributor.authorLiu, C-
dc.contributor.authorChan, HTH-
dc.contributor.authorShi, E-
dc.contributor.authorStefanov, E-
dc.contributor.authorHuang, Y-
dc.date.accessioned2015-08-21T11:54:13Z-
dc.date.available2015-08-21T11:54:13Z-
dc.date.issued2014-
dc.identifier.citationThe 2014 ACM Conference on Computer and Communications Security (CCS'14) Scottsdale, AZ., 3-7 November 2014. In Conference Proceedings, 2014, p. 215-226-
dc.identifier.isbn978-1-4503-2957-6-
dc.identifier.issn1543-7221-
dc.identifier.urihttp://hdl.handle.net/10722/214753-
dc.description.abstractWe design novel, asymptotically more efficient data structures and algorithms for programs whose data access patterns exhibit some degree of predictability. To this end, we propose two novel techniques, a pointer-based technique and a locality-based technique. We show that these two techniques are powerful building blocks in making data structures and algorithms oblivious. Specifically, we apply these techniques to a broad range of commonly used data structures, including maps, sets, priority-queues, stacks, deques; and algorithms, including a memory allocator algorithm, max-flow on graphs with low doubling dimension, and shortestpath distance queries on weighted planar graphs. Our oblivious counterparts of the above outperform the best known ORAM scheme both asymptotically and in practice. Copyright is held by the owner/author(s). Publication rights licensed to ACM.-
dc.languageeng-
dc.publisherAssociation for Computing Machinery, Inc.-
dc.relation.ispartofACM Conference on Computer and Communications Security Proceedings-
dc.rightsACM Conference on Computer and Communications Security Proceedings. Copyright © Association for Computing Machinery, Inc.-
dc.subjectCryptography-
dc.subjectOblivious algorithms-
dc.subjectSecurity-
dc.titleOblivious data structures-
dc.typeConference_Paper-
dc.identifier.emailChan, HTH: hubert@cs.hku.hk-
dc.identifier.authorityChan, HTH=rp01312-
dc.description.naturelink_to_OA_fulltext-
dc.identifier.doi10.1145/2660267.2660314-
dc.identifier.scopuseid_2-s2.0-84910678637-
dc.identifier.hkuros247364-
dc.identifier.spage215-
dc.identifier.epage226-
dc.publisher.placeUnited States-
dc.customcontrol.immutablesml 150902-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats