Oblivious Network RAM and Leveraging Parallelism to Achieve Obliviousness View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2015

AUTHORS

Dana Dachman-Soled , Chang Liu , Charalampos Papamanthou , Elaine Shi , Uzi Vishkin

ABSTRACT

Oblivious RAM (ORAM) is a cryptographic primitive that allows a trusted CPU to securely access untrusted memory, such that the access patterns reveal nothing about sensitive data. ORAM is known to have broad applications in secure processor design and secure multi-party computation for big data. Unfortunately, due to a logarithmic lower bound by Goldreich and Ostrovsky (Journal of the ACM, ’96), ORAM is bound to incur a moderate cost in practice. In particular, with the latest developments in ORAM constructions, we are quickly approaching this limit, and the room for performance improvement is small.In this paper, we consider new models of computation in which the cost of obliviousness can be fundamentally reduced in comparison with the standard ORAM model. We propose the Oblivious Network RAM model of computation, where a CPU communicates with multiple memory banks, such that the adversary observes only which bank the CPU is communicating with, but not the address offset within each memory bank. In other words, obliviousness within each bank comes for free—either because the architecture prevents a malicious party from observing the address accessed within a bank, or because another solution is used to obfuscate memory accesses within each bank—and hence we only need to obfuscate communication patterns between the CPU and the memory banks. We present new constructions for obliviously simulating general or parallel programs in the Network RAM model. We describe applications of our new model in secure processor design and in distributed storage applications with a network adversary. More... »

PAGES

337-359

Book

TITLE

Advances in Cryptology -- ASIACRYPT 2015

ISBN

978-3-662-48796-9
978-3-662-48797-6

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-662-48797-6_15

DOI

http://dx.doi.org/10.1007/978-3-662-48797-6_15

DIMENSIONS

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


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/0803", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computer Software", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "University of Maryland, College Park, USA", 
          "id": "http://www.grid.ac/institutes/grid.164295.d", 
          "name": [
            "University of Maryland, College Park, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Dachman-Soled", 
        "givenName": "Dana", 
        "id": "sg:person.011244513001.85", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011244513001.85"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of Maryland, College Park, USA", 
          "id": "http://www.grid.ac/institutes/grid.164295.d", 
          "name": [
            "University of Maryland, College Park, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Liu", 
        "givenName": "Chang", 
        "id": "sg:person.015620030511.99", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015620030511.99"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of Maryland, College Park, USA", 
          "id": "http://www.grid.ac/institutes/grid.164295.d", 
          "name": [
            "University of Maryland, College Park, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Papamanthou", 
        "givenName": "Charalampos", 
        "id": "sg:person.010450677547.30", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010450677547.30"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Cornell University, Ithaca, USA", 
          "id": "http://www.grid.ac/institutes/grid.5386.8", 
          "name": [
            "Cornell University, Ithaca, 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": "University of Maryland, College Park, USA", 
          "id": "http://www.grid.ac/institutes/grid.164295.d", 
          "name": [
            "University of Maryland, College Park, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Vishkin", 
        "givenName": "Uzi", 
        "id": "sg:person.0646157060.46", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0646157060.46"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2015", 
    "datePublishedReg": "2015-01-01", 
    "description": "Oblivious RAM (ORAM) is a cryptographic primitive that allows a trusted CPU to securely access untrusted memory, such that the access patterns reveal nothing about sensitive data. ORAM is known to have broad applications in secure processor design and secure multi-party computation for big data. Unfortunately, due to a logarithmic lower bound by Goldreich and Ostrovsky (Journal of the ACM, \u201996), ORAM is bound to incur a moderate cost in practice. In particular, with the latest developments in ORAM constructions, we are quickly approaching this limit, and the room for performance improvement is small.In this paper, we consider new models of computation in which the cost of obliviousness can be fundamentally reduced in comparison with the standard ORAM model. We propose the Oblivious Network RAM model of computation, where a CPU communicates with multiple memory banks, such that the adversary observes only which bank the CPU is communicating with, but not the address offset within each memory bank. In other words, obliviousness within each bank comes for free\u2014either because the architecture prevents a malicious party from observing the address accessed within a bank, or because another solution is used to obfuscate memory accesses within each bank\u2014and hence we only need to obfuscate communication patterns between the CPU and the memory banks. We present new constructions for obliviously simulating general or parallel programs in the Network RAM model. We describe applications of our new model in secure processor design and in distributed storage applications with a network adversary.", 
    "editor": [
      {
        "familyName": "Iwata", 
        "givenName": "Tetsu", 
        "type": "Person"
      }, 
      {
        "familyName": "Cheon", 
        "givenName": "Jung Hee", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-662-48797-6_15", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-662-48796-9", 
        "978-3-662-48797-6"
      ], 
      "name": "Advances in Cryptology -- ASIACRYPT 2015", 
      "type": "Book"
    }, 
    "keywords": [
      "secure processor design", 
      "Oblivious RAM", 
      "memory banks", 
      "secure multi-party computation", 
      "multi-party computation", 
      "processor design", 
      "multiple memory banks", 
      "RAM model", 
      "network adversary", 
      "sensitive data", 
      "ORAM constructions", 
      "untrusted memory", 
      "malicious parties", 
      "cryptographic primitives", 
      "access patterns", 
      "parallel programs", 
      "big data", 
      "network RAM", 
      "memory access", 
      "CPU", 
      "communication patterns", 
      "performance improvement", 
      "adversary", 
      "computation", 
      "obliviousness", 
      "new model", 
      "address", 
      "moderate cost", 
      "primitives", 
      "applications", 
      "parallelism", 
      "architecture", 
      "Ostrovsky", 
      "rams", 
      "cost", 
      "Goldreich", 
      "design", 
      "model", 
      "new construction", 
      "broad applications", 
      "access", 
      "construction", 
      "memory", 
      "latest developments", 
      "data", 
      "solution", 
      "words", 
      "banks", 
      "parties", 
      "improvement", 
      "program", 
      "room", 
      "patterns", 
      "development", 
      "storage applications", 
      "practice", 
      "comparison", 
      "limit", 
      "paper", 
      "cost of obliviousness", 
      "standard ORAM model", 
      "ORAM model", 
      "Oblivious Network RAM model", 
      "Network RAM model", 
      "Oblivious Network RAM", 
      "Leveraging Parallelism"
    ], 
    "name": "Oblivious Network RAM and Leveraging Parallelism to Achieve Obliviousness", 
    "pagination": "337-359", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1017143786"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-662-48797-6_15"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-662-48797-6_15", 
      "https://app.dimensions.ai/details/publication/pub.1017143786"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2021-11-01T18:47", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20211101/entities/gbq_results/chapter/chapter_143.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-662-48797-6_15"
  }
]
 

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-662-48797-6_15'

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-662-48797-6_15'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-662-48797-6_15'

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-662-48797-6_15'


 

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

162 TRIPLES      23 PREDICATES      92 URIs      85 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-662-48797-6_15 schema:about anzsrc-for:08
2 anzsrc-for:0803
3 schema:author N0b6be51b40a044d59fddfea6c5976011
4 schema:datePublished 2015
5 schema:datePublishedReg 2015-01-01
6 schema:description Oblivious RAM (ORAM) is a cryptographic primitive that allows a trusted CPU to securely access untrusted memory, such that the access patterns reveal nothing about sensitive data. ORAM is known to have broad applications in secure processor design and secure multi-party computation for big data. Unfortunately, due to a logarithmic lower bound by Goldreich and Ostrovsky (Journal of the ACM, ’96), ORAM is bound to incur a moderate cost in practice. In particular, with the latest developments in ORAM constructions, we are quickly approaching this limit, and the room for performance improvement is small.In this paper, we consider new models of computation in which the cost of obliviousness can be fundamentally reduced in comparison with the standard ORAM model. We propose the Oblivious Network RAM model of computation, where a CPU communicates with multiple memory banks, such that the adversary observes only which bank the CPU is communicating with, but not the address offset within each memory bank. In other words, obliviousness within each bank comes for free—either because the architecture prevents a malicious party from observing the address accessed within a bank, or because another solution is used to obfuscate memory accesses within each bank—and hence we only need to obfuscate communication patterns between the CPU and the memory banks. We present new constructions for obliviously simulating general or parallel programs in the Network RAM model. We describe applications of our new model in secure processor design and in distributed storage applications with a network adversary.
7 schema:editor Ndf13e949f783492e8b5550ebfe961547
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf N9e6aed16378d45cab2e80ccdd30bcb29
12 schema:keywords CPU
13 Goldreich
14 Leveraging Parallelism
15 Network RAM model
16 ORAM constructions
17 ORAM model
18 Oblivious Network RAM
19 Oblivious Network RAM model
20 Oblivious RAM
21 Ostrovsky
22 RAM model
23 access
24 access patterns
25 address
26 adversary
27 applications
28 architecture
29 banks
30 big data
31 broad applications
32 communication patterns
33 comparison
34 computation
35 construction
36 cost
37 cost of obliviousness
38 cryptographic primitives
39 data
40 design
41 development
42 improvement
43 latest developments
44 limit
45 malicious parties
46 memory
47 memory access
48 memory banks
49 model
50 moderate cost
51 multi-party computation
52 multiple memory banks
53 network RAM
54 network adversary
55 new construction
56 new model
57 obliviousness
58 paper
59 parallel programs
60 parallelism
61 parties
62 patterns
63 performance improvement
64 practice
65 primitives
66 processor design
67 program
68 rams
69 room
70 secure multi-party computation
71 secure processor design
72 sensitive data
73 solution
74 standard ORAM model
75 storage applications
76 untrusted memory
77 words
78 schema:name Oblivious Network RAM and Leveraging Parallelism to Achieve Obliviousness
79 schema:pagination 337-359
80 schema:productId Ndaad37d037fd4b2086c6d08444df69d3
81 Ne848e6bdbe9e4d3385415cac94f6804d
82 schema:publisher Ne65aa599a8c249c4957f906ba9727cae
83 schema:sameAs https://app.dimensions.ai/details/publication/pub.1017143786
84 https://doi.org/10.1007/978-3-662-48797-6_15
85 schema:sdDatePublished 2021-11-01T18:47
86 schema:sdLicense https://scigraph.springernature.com/explorer/license/
87 schema:sdPublisher N95a07d308dc44c03969e6c24d4cedcec
88 schema:url https://doi.org/10.1007/978-3-662-48797-6_15
89 sgo:license sg:explorer/license/
90 sgo:sdDataset chapters
91 rdf:type schema:Chapter
92 N055c243e7d0941d7885ad1ee65868f44 schema:familyName Cheon
93 schema:givenName Jung Hee
94 rdf:type schema:Person
95 N0b6be51b40a044d59fddfea6c5976011 rdf:first sg:person.011244513001.85
96 rdf:rest N42e72909f2b444c4af759df9091e28a2
97 N37e6155969e84799bac047f25619c68c rdf:first sg:person.0646157060.46
98 rdf:rest rdf:nil
99 N42e72909f2b444c4af759df9091e28a2 rdf:first sg:person.015620030511.99
100 rdf:rest Ne42be642d39d4e6ab3c1054c8ef5193c
101 N85a3eb1613594bc2abf806d86f3f30f0 schema:familyName Iwata
102 schema:givenName Tetsu
103 rdf:type schema:Person
104 N95a07d308dc44c03969e6c24d4cedcec schema:name Springer Nature - SN SciGraph project
105 rdf:type schema:Organization
106 N9e6aed16378d45cab2e80ccdd30bcb29 schema:isbn 978-3-662-48796-9
107 978-3-662-48797-6
108 schema:name Advances in Cryptology -- ASIACRYPT 2015
109 rdf:type schema:Book
110 Nbea27f72371c4f88add4726547d1cfc5 rdf:first N055c243e7d0941d7885ad1ee65868f44
111 rdf:rest rdf:nil
112 Ndaad37d037fd4b2086c6d08444df69d3 schema:name doi
113 schema:value 10.1007/978-3-662-48797-6_15
114 rdf:type schema:PropertyValue
115 Ndf13e949f783492e8b5550ebfe961547 rdf:first N85a3eb1613594bc2abf806d86f3f30f0
116 rdf:rest Nbea27f72371c4f88add4726547d1cfc5
117 Ne42be642d39d4e6ab3c1054c8ef5193c rdf:first sg:person.010450677547.30
118 rdf:rest Nf3312be167144169b5d6a49205e109ae
119 Ne65aa599a8c249c4957f906ba9727cae schema:name Springer Nature
120 rdf:type schema:Organisation
121 Ne848e6bdbe9e4d3385415cac94f6804d schema:name dimensions_id
122 schema:value pub.1017143786
123 rdf:type schema:PropertyValue
124 Nf3312be167144169b5d6a49205e109ae rdf:first sg:person.014706274717.52
125 rdf:rest N37e6155969e84799bac047f25619c68c
126 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
127 schema:name Information and Computing Sciences
128 rdf:type schema:DefinedTerm
129 anzsrc-for:0803 schema:inDefinedTermSet anzsrc-for:
130 schema:name Computer Software
131 rdf:type schema:DefinedTerm
132 sg:person.010450677547.30 schema:affiliation grid-institutes:grid.164295.d
133 schema:familyName Papamanthou
134 schema:givenName Charalampos
135 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010450677547.30
136 rdf:type schema:Person
137 sg:person.011244513001.85 schema:affiliation grid-institutes:grid.164295.d
138 schema:familyName Dachman-Soled
139 schema:givenName Dana
140 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011244513001.85
141 rdf:type schema:Person
142 sg:person.014706274717.52 schema:affiliation grid-institutes:grid.5386.8
143 schema:familyName Shi
144 schema:givenName Elaine
145 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014706274717.52
146 rdf:type schema:Person
147 sg:person.015620030511.99 schema:affiliation grid-institutes:grid.164295.d
148 schema:familyName Liu
149 schema:givenName Chang
150 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015620030511.99
151 rdf:type schema:Person
152 sg:person.0646157060.46 schema:affiliation grid-institutes:grid.164295.d
153 schema:familyName Vishkin
154 schema:givenName Uzi
155 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0646157060.46
156 rdf:type schema:Person
157 grid-institutes:grid.164295.d schema:alternateName University of Maryland, College Park, USA
158 schema:name University of Maryland, College Park, USA
159 rdf:type schema:Organization
160 grid-institutes:grid.5386.8 schema:alternateName Cornell University, Ithaca, USA
161 schema:name Cornell University, Ithaca, USA
162 rdf:type schema:Organization
 




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


...