Oblivious RAM with O((logN)3) Worst-Case Cost View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2011

AUTHORS

Elaine Shi , T. -H. Hubert Chan , Emil Stefanov , Mingfei Li

ABSTRACT

Oblivious 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. More... »

PAGES

197-214

Book

TITLE

Advances in Cryptology – ASIACRYPT 2011

ISBN

978-3-642-25384-3
978-3-642-25385-0

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-25385-0_11

DOI

http://dx.doi.org/10.1007/978-3-642-25385-0_11

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1013921435


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0804", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Data Format", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "UC Berkeley/PARC, USA", 
          "id": "http://www.grid.ac/institutes/None", 
          "name": [
            "UC Berkeley/PARC, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Shi", 
        "givenName": "Elaine", 
        "id": "sg:person.014706274717.52", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014706274717.52"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "The University of Hong Kong, Hong Kong", 
          "id": "http://www.grid.ac/institutes/grid.194645.b", 
          "name": [
            "The University of Hong Kong, Hong Kong"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Chan", 
        "givenName": "T. -H. Hubert", 
        "id": "sg:person.010251411300.37", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010251411300.37"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "UC Berkeley, USA", 
          "id": "http://www.grid.ac/institutes/grid.47840.3f", 
          "name": [
            "UC Berkeley, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Stefanov", 
        "givenName": "Emil", 
        "id": "sg:person.015427206066.62", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015427206066.62"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "The University of Hong Kong, Hong Kong", 
          "id": "http://www.grid.ac/institutes/grid.194645.b", 
          "name": [
            "The University of Hong Kong, Hong Kong"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Li", 
        "givenName": "Mingfei", 
        "id": "sg:person.012247710241.37", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012247710241.37"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2011", 
    "datePublishedReg": "2011-01-01", 
    "description": "Oblivious 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.", 
    "editor": [
      {
        "familyName": "Lee", 
        "givenName": "Dong Hoon", 
        "type": "Person"
      }, 
      {
        "familyName": "Wang", 
        "givenName": "Xiaoyun", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-25385-0_11", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-642-25384-3", 
        "978-3-642-25385-0"
      ], 
      "name": "Advances in Cryptology \u2013 ASIACRYPT 2011", 
      "type": "Book"
    }, 
    "keywords": [
      "Oblivious RAM", 
      "data access patterns", 
      "worst-case cost", 
      "useful primitive", 
      "access patterns", 
      "untrusted server", 
      "worst-case behavior", 
      "data access requests", 
      "access requests", 
      "RAM construction", 
      "data buckets", 
      "data blocks", 
      "realistic settings", 
      "Oblivious RAM construction", 
      "RAM storage", 
      "binary tree", 
      "tree edges", 
      "rams", 
      "primitives", 
      "server", 
      "cost", 
      "large number", 
      "asymptotic performance", 
      "novel technique", 
      "clients", 
      "applications", 
      "scheme", 
      "requests", 
      "storage", 
      "performance", 
      "work", 
      "operation", 
      "construction", 
      "technique", 
      "trees", 
      "bucket", 
      "block", 
      "edge", 
      "patterns", 
      "behavior", 
      "setting", 
      "number", 
      "paper", 
      "storage outsourcing applications", 
      "outsourcing applications", 
      "higher worst-case cost", 
      "Such poor worst-case behavior", 
      "poor worst-case behavior", 
      "novel Oblivious RAM constructions", 
      "poly-logarithmic worst-case cost", 
      "constant client-side storage", 
      "client-side storage", 
      "worst-case asymptotic performance"
    ], 
    "name": "Oblivious RAM with O((logN)3) Worst-Case Cost", 
    "pagination": "197-214", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1013921435"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-25385-0_11"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-25385-0_11", 
      "https://app.dimensions.ai/details/publication/pub.1013921435"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2021-12-01T20:09", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20211201/entities/gbq_results/chapter/chapter_411.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-25385-0_11"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-25385-0_11'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-25385-0_11'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-25385-0_11'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-25385-0_11'


 

This table displays all metadata directly associated to this object as RDF triples.

145 TRIPLES      23 PREDICATES      79 URIs      72 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-25385-0_11 schema:about anzsrc-for:08
2 anzsrc-for:0804
3 schema:author N3ab8ce6c93294a89a9970fca606c6ad1
4 schema:datePublished 2011
5 schema:datePublishedReg 2011-01-01
6 schema:description Oblivious 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.
7 schema:editor N587022bd71cb4e54a555328667e272e4
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf N459d18ada60b45aab8cc66da83bbcfdb
12 schema:keywords Oblivious RAM
13 Oblivious RAM construction
14 RAM construction
15 RAM storage
16 Such poor worst-case behavior
17 access patterns
18 access requests
19 applications
20 asymptotic performance
21 behavior
22 binary tree
23 block
24 bucket
25 client-side storage
26 clients
27 constant client-side storage
28 construction
29 cost
30 data access patterns
31 data access requests
32 data blocks
33 data buckets
34 edge
35 higher worst-case cost
36 large number
37 novel Oblivious RAM constructions
38 novel technique
39 number
40 operation
41 outsourcing applications
42 paper
43 patterns
44 performance
45 poly-logarithmic worst-case cost
46 poor worst-case behavior
47 primitives
48 rams
49 realistic settings
50 requests
51 scheme
52 server
53 setting
54 storage
55 storage outsourcing applications
56 technique
57 tree edges
58 trees
59 untrusted server
60 useful primitive
61 work
62 worst-case asymptotic performance
63 worst-case behavior
64 worst-case cost
65 schema:name Oblivious RAM with O((logN)3) Worst-Case Cost
66 schema:pagination 197-214
67 schema:productId N1e3461fa8b8b4a82acc21dd1a5cb4a7e
68 N6e108320d7ac4854a6599997a0bdff8b
69 schema:publisher Ne07095b9dfa347bd835063da9a518bc0
70 schema:sameAs https://app.dimensions.ai/details/publication/pub.1013921435
71 https://doi.org/10.1007/978-3-642-25385-0_11
72 schema:sdDatePublished 2021-12-01T20:09
73 schema:sdLicense https://scigraph.springernature.com/explorer/license/
74 schema:sdPublisher N69ecc4dafdb0448d9695660441936c3f
75 schema:url https://doi.org/10.1007/978-3-642-25385-0_11
76 sgo:license sg:explorer/license/
77 sgo:sdDataset chapters
78 rdf:type schema:Chapter
79 N068ee9fd87774c149d070fc0c4ebbebe rdf:first sg:person.015427206066.62
80 rdf:rest Nbc9cc40efc6e417fb12f3c7aaa1ff41f
81 N1e3461fa8b8b4a82acc21dd1a5cb4a7e schema:name dimensions_id
82 schema:value pub.1013921435
83 rdf:type schema:PropertyValue
84 N3ab8ce6c93294a89a9970fca606c6ad1 rdf:first sg:person.014706274717.52
85 rdf:rest N7c62d62aaf7b4a8fa0521f038a57d267
86 N459d18ada60b45aab8cc66da83bbcfdb schema:isbn 978-3-642-25384-3
87 978-3-642-25385-0
88 schema:name Advances in Cryptology – ASIACRYPT 2011
89 rdf:type schema:Book
90 N4c526185dd5f4095b0dcc0574e436139 schema:familyName Wang
91 schema:givenName Xiaoyun
92 rdf:type schema:Person
93 N587022bd71cb4e54a555328667e272e4 rdf:first Ne2bb7b0304a54f84a4b0e26a9353d5af
94 rdf:rest N651e88a019c44a8d9e4276630e53d444
95 N651e88a019c44a8d9e4276630e53d444 rdf:first N4c526185dd5f4095b0dcc0574e436139
96 rdf:rest rdf:nil
97 N69ecc4dafdb0448d9695660441936c3f schema:name Springer Nature - SN SciGraph project
98 rdf:type schema:Organization
99 N6e108320d7ac4854a6599997a0bdff8b schema:name doi
100 schema:value 10.1007/978-3-642-25385-0_11
101 rdf:type schema:PropertyValue
102 N7c62d62aaf7b4a8fa0521f038a57d267 rdf:first sg:person.010251411300.37
103 rdf:rest N068ee9fd87774c149d070fc0c4ebbebe
104 Nbc9cc40efc6e417fb12f3c7aaa1ff41f rdf:first sg:person.012247710241.37
105 rdf:rest rdf:nil
106 Ne07095b9dfa347bd835063da9a518bc0 schema:name Springer Nature
107 rdf:type schema:Organisation
108 Ne2bb7b0304a54f84a4b0e26a9353d5af schema:familyName Lee
109 schema:givenName Dong Hoon
110 rdf:type schema:Person
111 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
112 schema:name Information and Computing Sciences
113 rdf:type schema:DefinedTerm
114 anzsrc-for:0804 schema:inDefinedTermSet anzsrc-for:
115 schema:name Data Format
116 rdf:type schema:DefinedTerm
117 sg:person.010251411300.37 schema:affiliation grid-institutes:grid.194645.b
118 schema:familyName Chan
119 schema:givenName T. -H. Hubert
120 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010251411300.37
121 rdf:type schema:Person
122 sg:person.012247710241.37 schema:affiliation grid-institutes:grid.194645.b
123 schema:familyName Li
124 schema:givenName Mingfei
125 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012247710241.37
126 rdf:type schema:Person
127 sg:person.014706274717.52 schema:affiliation grid-institutes:None
128 schema:familyName Shi
129 schema:givenName Elaine
130 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014706274717.52
131 rdf:type schema:Person
132 sg:person.015427206066.62 schema:affiliation grid-institutes:grid.47840.3f
133 schema:familyName Stefanov
134 schema:givenName Emil
135 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015427206066.62
136 rdf:type schema:Person
137 grid-institutes:None schema:alternateName UC Berkeley/PARC, USA
138 schema:name UC Berkeley/PARC, USA
139 rdf:type schema:Organization
140 grid-institutes:grid.194645.b schema:alternateName The University of Hong Kong, Hong Kong
141 schema:name The University of Hong Kong, Hong Kong
142 rdf:type schema:Organization
143 grid-institutes:grid.47840.3f schema:alternateName UC Berkeley, USA
144 schema:name UC Berkeley, USA
145 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...