Oblivious RAM with Worst-Case Logarithmic Overhead View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2021-08-11

AUTHORS

Gilad Asharov , Ilan Komargodski , Wei-Kai Lin , Elaine Shi

ABSTRACT

We present the first Oblivious RAM (ORAM) construction that for N memory blocks supports accesses with worst-caseO(logN)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(\log N)$$\end{document} overhead for any block size Ω(logN)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\varOmega (\log N)$$\end{document} while requiring a client memory of only a constant number of memory blocks. We rely on the existence of one-way functions and guarantee computational security. Our result closes a long line of research on fundamental feasibility results for ORAM constructions as logarithmic overhead is necessary.The previous best logarithmic overhead construction only guarantees it in an amortized sense, i.e., logarithmic overhead is achieved only for long enough access sequences, where some of the individual accesses incur Θ(N)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\varTheta (N)$$\end{document} overhead. The previously best ORAM in terms of worst-case overhead achieves O(log2N/loglogN)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(\log ^2 N/\log \log N)$$\end{document} overhead.Technically, we design a novel de-amortization framework for modern ORAM constructions that use the “shuffled inputs” assumption. Our framework significantly departs from all previous de-amortization frameworks, originating from Ostrovsky and Shoup (STOC ’97), that seem to be fundamentally too weak to be applied on modern ORAM constructions. More... »

PAGES

610-640

Book

TITLE

Advances in Cryptology – CRYPTO 2021

ISBN

978-3-030-84258-1
978-3-030-84259-8

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-030-84259-8_21

DOI

http://dx.doi.org/10.1007/978-3-030-84259-8_21

DIMENSIONS

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


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": "Bar-Ilan University, Ramat Gan, Israel", 
          "id": "http://www.grid.ac/institutes/grid.22098.31", 
          "name": [
            "Bar-Ilan University, Ramat Gan, Israel"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Asharov", 
        "givenName": "Gilad", 
        "id": "sg:person.016347606461.90", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016347606461.90"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "NTT Research, Sunnyvale, CA, USA", 
          "id": "http://www.grid.ac/institutes/None", 
          "name": [
            "Hebrew University of Jerusalem, Jerusalem, Israel", 
            "NTT Research, Sunnyvale, CA, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Komargodski", 
        "givenName": "Ilan", 
        "id": "sg:person.012204235441.12", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012204235441.12"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Cornell University, New York, USA", 
          "id": "http://www.grid.ac/institutes/grid.5386.8", 
          "name": [
            "Cornell University, New York, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Lin", 
        "givenName": "Wei-Kai", 
        "id": "sg:person.015030115735.91", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015030115735.91"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "CMU, Pittsburgh, USA", 
          "id": "http://www.grid.ac/institutes/grid.147455.6", 
          "name": [
            "CMU, Pittsburgh, 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"
      }
    ], 
    "datePublished": "2021-08-11", 
    "datePublishedReg": "2021-08-11", 
    "description": "We present the first Oblivious RAM (ORAM) construction that for N memory blocks supports accesses with worst-caseO(logN)\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$O(\\log N)$$\\end{document} overhead for any block size \u03a9(logN)\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$\\varOmega (\\log N)$$\\end{document} while requiring a client memory of only a constant number of memory blocks. We rely on the existence of one-way functions and guarantee computational security. Our result closes a long line of research on fundamental feasibility results for ORAM constructions as logarithmic overhead is necessary.The previous best logarithmic overhead construction only guarantees it in an amortized sense, i.e., logarithmic overhead is achieved only for long enough access sequences, where some of the individual accesses incur \u0398(N)\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$\\varTheta (N)$$\\end{document} overhead. The previously best ORAM in terms of worst-case overhead achieves O(log2N/loglogN)\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$O(\\log ^2 N/\\log \\log N)$$\\end{document} overhead.Technically, we design a novel de-amortization framework for modern ORAM constructions that use the \u201cshuffled inputs\u201d assumption. Our framework significantly departs from all previous de-amortization frameworks, originating from Ostrovsky and Shoup (STOC\u00a0\u201997), that seem to be fundamentally too weak to be applied on modern ORAM constructions.", 
    "editor": [
      {
        "familyName": "Malkin", 
        "givenName": "Tal", 
        "type": "Person"
      }, 
      {
        "familyName": "Peikert", 
        "givenName": "Chris", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-030-84259-8_21", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-030-84258-1", 
        "978-3-030-84259-8"
      ], 
      "name": "Advances in Cryptology \u2013 CRYPTO 2021", 
      "type": "Book"
    }, 
    "keywords": [
      "memory blocks", 
      "Oblivious RAM construction", 
      "client memory", 
      "logarithmic overhead", 
      "overhead", 
      "RAM construction", 
      "block size", 
      "ORAM constructions", 
      "access sequence", 
      "worst-case overhead", 
      "block", 
      "size", 
      "security", 
      "incurs", 
      "construction", 
      "memory", 
      "computational security", 
      "results", 
      "long line", 
      "feasibility results", 
      "ORAM", 
      "Oblivious RAM", 
      "rams", 
      "constant number", 
      "number", 
      "one-way functions", 
      "function", 
      "lines", 
      "research", 
      "sequence", 
      "terms", 
      "framework", 
      "input", 
      "existence", 
      "sense", 
      "individuals", 
      "assumption", 
      "logarithmic", 
      "Ostrovsky", 
      "Shoup", 
      "overhead construction"
    ], 
    "name": "Oblivious RAM with Worst-Case Logarithmic Overhead", 
    "pagination": "610-640", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1140318705"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-030-84259-8_21"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-030-84259-8_21", 
      "https://app.dimensions.ai/details/publication/pub.1140318705"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-05-10T10:45", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220509/entities/gbq_results/chapter/chapter_288.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-030-84259-8_21"
  }
]
 

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-030-84259-8_21'

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-030-84259-8_21'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-030-84259-8_21'

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-030-84259-8_21'


 

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

137 TRIPLES      23 PREDICATES      66 URIs      59 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-030-84259-8_21 schema:about anzsrc-for:08
2 anzsrc-for:0804
3 schema:author Nccd731c0bd52456f914384880887076a
4 schema:datePublished 2021-08-11
5 schema:datePublishedReg 2021-08-11
6 schema:description We present the first Oblivious RAM (ORAM) construction that for N memory blocks supports accesses with worst-caseO(logN)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(\log N)$$\end{document} overhead for any block size Ω(logN)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\varOmega (\log N)$$\end{document} while requiring a client memory of only a constant number of memory blocks. We rely on the existence of one-way functions and guarantee computational security. Our result closes a long line of research on fundamental feasibility results for ORAM constructions as logarithmic overhead is necessary.The previous best logarithmic overhead construction only guarantees it in an amortized sense, i.e., logarithmic overhead is achieved only for long enough access sequences, where some of the individual accesses incur Θ(N)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\varTheta (N)$$\end{document} overhead. The previously best ORAM in terms of worst-case overhead achieves O(log2N/loglogN)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(\log ^2 N/\log \log N)$$\end{document} overhead.Technically, we design a novel de-amortization framework for modern ORAM constructions that use the “shuffled inputs” assumption. Our framework significantly departs from all previous de-amortization frameworks, originating from Ostrovsky and Shoup (STOC ’97), that seem to be fundamentally too weak to be applied on modern ORAM constructions.
7 schema:editor N74294c1f6ecc471f8ff030a7edb6a8c2
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N3b732b2f2fba49859e237a903dd07415
12 schema:keywords ORAM
13 ORAM constructions
14 Oblivious RAM
15 Oblivious RAM construction
16 Ostrovsky
17 RAM construction
18 Shoup
19 access sequence
20 assumption
21 block
22 block size
23 client memory
24 computational security
25 constant number
26 construction
27 existence
28 feasibility results
29 framework
30 function
31 incurs
32 individuals
33 input
34 lines
35 logarithmic
36 logarithmic overhead
37 long line
38 memory
39 memory blocks
40 number
41 one-way functions
42 overhead
43 overhead construction
44 rams
45 research
46 results
47 security
48 sense
49 sequence
50 size
51 terms
52 worst-case overhead
53 schema:name Oblivious RAM with Worst-Case Logarithmic Overhead
54 schema:pagination 610-640
55 schema:productId N00ba243b00a145ccbafaa0ef099eac43
56 N9e6e2b516b3947b3837e5c16f69aba83
57 schema:publisher Nbcc73edce13f405b941f743099d387fc
58 schema:sameAs https://app.dimensions.ai/details/publication/pub.1140318705
59 https://doi.org/10.1007/978-3-030-84259-8_21
60 schema:sdDatePublished 2022-05-10T10:45
61 schema:sdLicense https://scigraph.springernature.com/explorer/license/
62 schema:sdPublisher N6edaa335edc14bb9bb3f40c4a93394ea
63 schema:url https://doi.org/10.1007/978-3-030-84259-8_21
64 sgo:license sg:explorer/license/
65 sgo:sdDataset chapters
66 rdf:type schema:Chapter
67 N00ba243b00a145ccbafaa0ef099eac43 schema:name doi
68 schema:value 10.1007/978-3-030-84259-8_21
69 rdf:type schema:PropertyValue
70 N3b732b2f2fba49859e237a903dd07415 schema:isbn 978-3-030-84258-1
71 978-3-030-84259-8
72 schema:name Advances in Cryptology – CRYPTO 2021
73 rdf:type schema:Book
74 N4905dff8d6ed4004bd33b63994035b76 rdf:first sg:person.015030115735.91
75 rdf:rest Nd16fa81eb7b04d4ea290518054f9436e
76 N5142feef86e443709e0e46312363068a rdf:first N6918d7e946fb48d7a0ade679ae2c1cdd
77 rdf:rest rdf:nil
78 N6918d7e946fb48d7a0ade679ae2c1cdd schema:familyName Peikert
79 schema:givenName Chris
80 rdf:type schema:Person
81 N6edaa335edc14bb9bb3f40c4a93394ea schema:name Springer Nature - SN SciGraph project
82 rdf:type schema:Organization
83 N74294c1f6ecc471f8ff030a7edb6a8c2 rdf:first Nd32c97ae7ae54be8a8fa0d30140734e5
84 rdf:rest N5142feef86e443709e0e46312363068a
85 N9e6e2b516b3947b3837e5c16f69aba83 schema:name dimensions_id
86 schema:value pub.1140318705
87 rdf:type schema:PropertyValue
88 Nbcc73edce13f405b941f743099d387fc schema:name Springer Nature
89 rdf:type schema:Organisation
90 Nccd731c0bd52456f914384880887076a rdf:first sg:person.016347606461.90
91 rdf:rest Nd387e8be645a4380b8f3cdd7f1c57bc7
92 Nd16fa81eb7b04d4ea290518054f9436e rdf:first sg:person.014706274717.52
93 rdf:rest rdf:nil
94 Nd32c97ae7ae54be8a8fa0d30140734e5 schema:familyName Malkin
95 schema:givenName Tal
96 rdf:type schema:Person
97 Nd387e8be645a4380b8f3cdd7f1c57bc7 rdf:first sg:person.012204235441.12
98 rdf:rest N4905dff8d6ed4004bd33b63994035b76
99 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
100 schema:name Information and Computing Sciences
101 rdf:type schema:DefinedTerm
102 anzsrc-for:0804 schema:inDefinedTermSet anzsrc-for:
103 schema:name Data Format
104 rdf:type schema:DefinedTerm
105 sg:person.012204235441.12 schema:affiliation grid-institutes:None
106 schema:familyName Komargodski
107 schema:givenName Ilan
108 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012204235441.12
109 rdf:type schema:Person
110 sg:person.014706274717.52 schema:affiliation grid-institutes:grid.147455.6
111 schema:familyName Shi
112 schema:givenName Elaine
113 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014706274717.52
114 rdf:type schema:Person
115 sg:person.015030115735.91 schema:affiliation grid-institutes:grid.5386.8
116 schema:familyName Lin
117 schema:givenName Wei-Kai
118 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015030115735.91
119 rdf:type schema:Person
120 sg:person.016347606461.90 schema:affiliation grid-institutes:grid.22098.31
121 schema:familyName Asharov
122 schema:givenName Gilad
123 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016347606461.90
124 rdf:type schema:Person
125 grid-institutes:None schema:alternateName NTT Research, Sunnyvale, CA, USA
126 schema:name Hebrew University of Jerusalem, Jerusalem, Israel
127 NTT Research, Sunnyvale, CA, USA
128 rdf:type schema:Organization
129 grid-institutes:grid.147455.6 schema:alternateName CMU, Pittsburgh, USA
130 schema:name CMU, Pittsburgh, USA
131 rdf:type schema:Organization
132 grid-institutes:grid.22098.31 schema:alternateName Bar-Ilan University, Ramat Gan, Israel
133 schema:name Bar-Ilan University, Ramat Gan, Israel
134 rdf:type schema:Organization
135 grid-institutes:grid.5386.8 schema:alternateName Cornell University, New York, USA
136 schema:name Cornell University, New York, USA
137 rdf:type schema:Organization
 




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


...