File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: Oblivious RAM with O((log N)3) worst-case cost

TitleOblivious RAM with O((log N)3) worst-case cost
Authors
KeywordsAsymptotic performance
Data access
Data blocks
ITS data
Novel techniques
Untrusted server
Issue Date2011
PublisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/
Citation
The 17th International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT 2011), Seoul, South Korea, 4-8 December 2011. In Lecture Notes in Computer Science, 2011, v. 7073, p. 197-214 How to Cite?
AbstractOblivious RAM is a useful primitive that allows a client to hide its data access patterns from an untrusted server in storage outsourcing applications. Until recently, most prior works on Oblivious RAM aim to optimize its amortized cost, while suffering from linear or even higher worst-case cost. Such poor worst-case behavior renders these schemes impractical in realistic settings, since a data access request can occasionally be blocked waiting for an unreasonably large number of operations to complete. This paper proposes novel Oblivious RAM constructions that achieves poly-logarithmic worst-case cost, while consuming constant client-side storage. To achieve the desired worst-case asymptotic performance, we propose a novel technique in which we organize the O-RAM storage into a binary tree over data buckets, while moving data blocks obliviously along tree edges.
DescriptionLNCS v. 7073 entitled: Advances in Cryptology – ASIACRYPT 2011
Persistent Identifierhttp://hdl.handle.net/10722/139993
ISBN
ISSN
2023 SCImago Journal Rankings: 0.606

 

DC FieldValueLanguage
dc.contributor.authorShi, Een_US
dc.contributor.authorChan, HTHen_US
dc.contributor.authorStefanov, Een_US
dc.contributor.authorLi, Men_US
dc.date.accessioned2011-09-23T06:04:29Z-
dc.date.available2011-09-23T06:04:29Z-
dc.date.issued2011en_US
dc.identifier.citationThe 17th International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT 2011), Seoul, South Korea, 4-8 December 2011. In Lecture Notes in Computer Science, 2011, v. 7073, p. 197-214en_US
dc.identifier.isbn978-364225384-3-
dc.identifier.issn0302-9743-
dc.identifier.urihttp://hdl.handle.net/10722/139993-
dc.descriptionLNCS v. 7073 entitled: Advances in Cryptology – ASIACRYPT 2011-
dc.description.abstractOblivious RAM is a useful primitive that allows a client to hide its data access patterns from an untrusted server in storage outsourcing applications. Until recently, most prior works on Oblivious RAM aim to optimize its amortized cost, while suffering from linear or even higher worst-case cost. Such poor worst-case behavior renders these schemes impractical in realistic settings, since a data access request can occasionally be blocked waiting for an unreasonably large number of operations to complete. This paper proposes novel Oblivious RAM constructions that achieves poly-logarithmic worst-case cost, while consuming constant client-side storage. To achieve the desired worst-case asymptotic performance, we propose a novel technique in which we organize the O-RAM storage into a binary tree over data buckets, while moving data blocks obliviously along tree edges.-
dc.languageengen_US
dc.publisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/-
dc.relation.ispartofLecture Notes in Computer Scienceen_US
dc.rightsThe original publication is available at www.springerlink.com-
dc.subjectAsymptotic performance-
dc.subjectData access-
dc.subjectData blocks-
dc.subjectITS data-
dc.subjectNovel techniques-
dc.subjectUntrusted server-
dc.titleOblivious RAM with O((log N)3) worst-case costen_US
dc.typeConference_Paperen_US
dc.identifier.emailChan, HTH: hubert@cs.hku.hken_US
dc.identifier.authorityChan, HTH=rp01312en_US
dc.description.naturepostprint-
dc.identifier.doi10.1007/978-3-642-25385-0_11-
dc.identifier.scopuseid_2-s2.0-82955173838-
dc.identifier.hkuros193269en_US
dc.identifier.volume7073-
dc.identifier.spage197-
dc.identifier.epage214-
dc.publisher.placeGermany-
dc.customcontrol.immutablesml 131009-
dc.identifier.issnl0302-9743-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats