Perfectly Secure Oblivious Parallel RAM View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2018-11-08

AUTHORS

T.-H. Hubert Chan , Kartik Nayak , Elaine Shi

ABSTRACT

We show that PRAMs can be obliviously simulated with perfect security, incurring only \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 \log \log N)$$\end{document} blowup in parallel runtime, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(\log ^3 N)$$\end{document} blowup in total work, and O(1) blowup in space relative to the original PRAM. Our results advance the theoretical understanding of Oblivious (Parallel) RAM in several respects. First, prior to our work, no perfectly secure Oblivious Parallel RAM (OPRAM) construction was known; and we are the first in this respect. Second, even for the sequential special case of our algorithm (i.e., perfectly secure ORAM), we not only achieve logarithmic improvement in terms of space consumption relative to the state-of-the-art, but also significantly simplify perfectly secure ORAM constructions. Third, our perfectly secure OPRAM scheme matches the parallel runtime of earlier statistically secure schemes with negligible failure probability. Since we remove the dependence (in performance) on the security parameter, our perfectly secure OPRAM scheme in fact asymptotically outperforms known statistically secure ones if (sub-)exponentially small failure probability is desired. Our techniques for achieving small parallel runtime are novel and we employ special expander graphs to derandomize earlier statistically secure OPRAM techniques—this is the first time such techniques are used in the constructions of ORAMs/OPRAMs. More... »

PAGES

636-668

Book

TITLE

Theory of Cryptography

ISBN

978-3-030-03809-0
978-3-030-03810-6

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-030-03810-6_23

DOI

http://dx.doi.org/10.1007/978-3-030-03810-6_23

DIMENSIONS

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


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": "The University of Hong Kong, Hong Kong, China", 
          "id": "http://www.grid.ac/institutes/grid.194645.b", 
          "name": [
            "The University of Hong Kong, Hong Kong, China"
          ], 
          "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": "VMware Research, Palo Alto, USA", 
          "id": "http://www.grid.ac/institutes/None", 
          "name": [
            "University of Maryland, College Park, USA", 
            "VMware Research, Palo Alto, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Nayak", 
        "givenName": "Kartik", 
        "id": "sg:person.011031600672.42", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011031600672.42"
        ], 
        "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"
      }
    ], 
    "datePublished": "2018-11-08", 
    "datePublishedReg": "2018-11-08", 
    "description": "We show that PRAMs can be obliviously simulated with perfect security, incurring only \\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 \\log \\log N)$$\\end{document} blowup in parallel runtime, \\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 ^3 N)$$\\end{document} blowup in\u00a0total work, and O(1) blowup in space relative to the original PRAM. Our results advance the theoretical understanding of Oblivious (Parallel) RAM in several respects. First, prior to our work, no perfectly secure Oblivious Parallel RAM (OPRAM) construction was known; and we are the first in this respect. Second, even for the sequential special case of our algorithm (i.e., perfectly secure ORAM), we not only achieve logarithmic improvement in terms of space consumption relative to the state-of-the-art, but also significantly simplify perfectly secure ORAM constructions. Third, our perfectly secure OPRAM scheme matches the parallel runtime of earlier statistically secure schemes with negligible failure probability. Since we remove the dependence (in performance) on the security parameter, our perfectly secure OPRAM scheme in fact asymptotically outperforms known statistically secure ones if (sub-)exponentially small failure probability is desired. Our techniques for achieving small parallel runtime are novel and we employ special expander graphs to derandomize earlier statistically secure OPRAM techniques\u2014this is the first time such techniques are used in the constructions of ORAMs/OPRAMs.", 
    "editor": [
      {
        "familyName": "Beimel", 
        "givenName": "Amos", 
        "type": "Person"
      }, 
      {
        "familyName": "Dziembowski", 
        "givenName": "Stefan", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-030-03810-6_23", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-030-03809-0", 
        "978-3-030-03810-6"
      ], 
      "name": "Theory of Cryptography", 
      "type": "Book"
    }, 
    "keywords": [
      "parallel runtime", 
      "OPRAM scheme", 
      "negligible failure probability", 
      "Oblivious Parallel RAM", 
      "perfect security", 
      "Oblivious RAM", 
      "ORAM constructions", 
      "secure scheme", 
      "security parameter", 
      "secure one", 
      "parallel RAM", 
      "runtime", 
      "RAM construction", 
      "space consumption", 
      "first time such techniques", 
      "failure probability", 
      "expander graphs", 
      "such techniques", 
      "PRAM", 
      "logarithmic improvement", 
      "scheme", 
      "small failure probability", 
      "security", 
      "rams", 
      "algorithm", 
      "technique", 
      "graph", 
      "blowup", 
      "work", 
      "construction", 
      "special case", 
      "space", 
      "art", 
      "probability", 
      "theoretical understanding", 
      "respect", 
      "improvement", 
      "terms", 
      "consumption", 
      "one", 
      "results", 
      "state", 
      "parameters", 
      "fact", 
      "total work", 
      "cases", 
      "understanding", 
      "dependence", 
      "original PRAM", 
      "secure Oblivious Parallel RAM (OPRAM) construction", 
      "Oblivious Parallel RAM (OPRAM) construction", 
      "Parallel RAM (OPRAM) construction", 
      "sequential special case", 
      "secure ORAM constructions", 
      "secure OPRAM scheme", 
      "small parallel runtime", 
      "special expander graphs", 
      "secure OPRAM techniques", 
      "OPRAM techniques", 
      "time such techniques", 
      "ORAMs/OPRAMs", 
      "OPRAMs", 
      "Secure Oblivious Parallel RAM"
    ], 
    "name": "Perfectly Secure Oblivious Parallel RAM", 
    "pagination": "636-668", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1109772574"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-030-03810-6_23"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-030-03810-6_23", 
      "https://app.dimensions.ai/details/publication/pub.1109772574"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2021-11-01T18:50", 
    "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_202.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-030-03810-6_23"
  }
]
 

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-03810-6_23'

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-03810-6_23'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-030-03810-6_23'

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-03810-6_23'


 

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

149 TRIPLES      23 PREDICATES      88 URIs      81 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-030-03810-6_23 schema:about anzsrc-for:08
2 anzsrc-for:0804
3 schema:author N35535dbfdb0547d69f631cad8beb574f
4 schema:datePublished 2018-11-08
5 schema:datePublishedReg 2018-11-08
6 schema:description We show that PRAMs can be obliviously simulated with perfect security, incurring only \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 \log \log N)$$\end{document} blowup in parallel runtime, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(\log ^3 N)$$\end{document} blowup in total work, and O(1) blowup in space relative to the original PRAM. Our results advance the theoretical understanding of Oblivious (Parallel) RAM in several respects. First, prior to our work, no perfectly secure Oblivious Parallel RAM (OPRAM) construction was known; and we are the first in this respect. Second, even for the sequential special case of our algorithm (i.e., perfectly secure ORAM), we not only achieve logarithmic improvement in terms of space consumption relative to the state-of-the-art, but also significantly simplify perfectly secure ORAM constructions. Third, our perfectly secure OPRAM scheme matches the parallel runtime of earlier statistically secure schemes with negligible failure probability. Since we remove the dependence (in performance) on the security parameter, our perfectly secure OPRAM scheme in fact asymptotically outperforms known statistically secure ones if (sub-)exponentially small failure probability is desired. Our techniques for achieving small parallel runtime are novel and we employ special expander graphs to derandomize earlier statistically secure OPRAM techniques—this is the first time such techniques are used in the constructions of ORAMs/OPRAMs.
7 schema:editor N0ced44cd7f7d4dcf8b709ba21427347c
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf Nc25ab7183fec43d4bab1dda9c0698b27
12 schema:keywords OPRAM scheme
13 OPRAM techniques
14 OPRAMs
15 ORAM constructions
16 ORAMs/OPRAMs
17 Oblivious Parallel RAM
18 Oblivious Parallel RAM (OPRAM) construction
19 Oblivious RAM
20 PRAM
21 Parallel RAM (OPRAM) construction
22 RAM construction
23 Secure Oblivious Parallel RAM
24 algorithm
25 art
26 blowup
27 cases
28 construction
29 consumption
30 dependence
31 expander graphs
32 fact
33 failure probability
34 first time such techniques
35 graph
36 improvement
37 logarithmic improvement
38 negligible failure probability
39 one
40 original PRAM
41 parallel RAM
42 parallel runtime
43 parameters
44 perfect security
45 probability
46 rams
47 respect
48 results
49 runtime
50 scheme
51 secure OPRAM scheme
52 secure OPRAM techniques
53 secure ORAM constructions
54 secure Oblivious Parallel RAM (OPRAM) construction
55 secure one
56 secure scheme
57 security
58 security parameter
59 sequential special case
60 small failure probability
61 small parallel runtime
62 space
63 space consumption
64 special case
65 special expander graphs
66 state
67 such techniques
68 technique
69 terms
70 theoretical understanding
71 time such techniques
72 total work
73 understanding
74 work
75 schema:name Perfectly Secure Oblivious Parallel RAM
76 schema:pagination 636-668
77 schema:productId N3a10e625990c4da0a109daed250d6879
78 N90762cd1f0274a8fb2e9c2d667b22744
79 schema:publisher N5bda6eb3eaa8422ab90bc83d5353f68e
80 schema:sameAs https://app.dimensions.ai/details/publication/pub.1109772574
81 https://doi.org/10.1007/978-3-030-03810-6_23
82 schema:sdDatePublished 2021-11-01T18:50
83 schema:sdLicense https://scigraph.springernature.com/explorer/license/
84 schema:sdPublisher N998afb150ed04d768f2a7baad034ece5
85 schema:url https://doi.org/10.1007/978-3-030-03810-6_23
86 sgo:license sg:explorer/license/
87 sgo:sdDataset chapters
88 rdf:type schema:Chapter
89 N0ced44cd7f7d4dcf8b709ba21427347c rdf:first Na7cac1e01cf449c2b277ea8407f61edb
90 rdf:rest N4313f45a6a6e43138bfac61123e92d71
91 N35535dbfdb0547d69f631cad8beb574f rdf:first sg:person.010251411300.37
92 rdf:rest N7858a7a58cb2479fa76bb427165a6993
93 N3a10e625990c4da0a109daed250d6879 schema:name doi
94 schema:value 10.1007/978-3-030-03810-6_23
95 rdf:type schema:PropertyValue
96 N4313f45a6a6e43138bfac61123e92d71 rdf:first Nd629a8db99b64738b0ecac21302ea310
97 rdf:rest rdf:nil
98 N5bda6eb3eaa8422ab90bc83d5353f68e schema:name Springer Nature
99 rdf:type schema:Organisation
100 N7858a7a58cb2479fa76bb427165a6993 rdf:first sg:person.011031600672.42
101 rdf:rest Ncbf425b3c55545c68fc3fb072a16a44e
102 N90762cd1f0274a8fb2e9c2d667b22744 schema:name dimensions_id
103 schema:value pub.1109772574
104 rdf:type schema:PropertyValue
105 N998afb150ed04d768f2a7baad034ece5 schema:name Springer Nature - SN SciGraph project
106 rdf:type schema:Organization
107 Na7cac1e01cf449c2b277ea8407f61edb schema:familyName Beimel
108 schema:givenName Amos
109 rdf:type schema:Person
110 Nc25ab7183fec43d4bab1dda9c0698b27 schema:isbn 978-3-030-03809-0
111 978-3-030-03810-6
112 schema:name Theory of Cryptography
113 rdf:type schema:Book
114 Ncbf425b3c55545c68fc3fb072a16a44e rdf:first sg:person.014706274717.52
115 rdf:rest rdf:nil
116 Nd629a8db99b64738b0ecac21302ea310 schema:familyName Dziembowski
117 schema:givenName Stefan
118 rdf:type schema:Person
119 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
120 schema:name Information and Computing Sciences
121 rdf:type schema:DefinedTerm
122 anzsrc-for:0804 schema:inDefinedTermSet anzsrc-for:
123 schema:name Data Format
124 rdf:type schema:DefinedTerm
125 sg:person.010251411300.37 schema:affiliation grid-institutes:grid.194645.b
126 schema:familyName Chan
127 schema:givenName T.-H. Hubert
128 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010251411300.37
129 rdf:type schema:Person
130 sg:person.011031600672.42 schema:affiliation grid-institutes:None
131 schema:familyName Nayak
132 schema:givenName Kartik
133 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011031600672.42
134 rdf:type schema:Person
135 sg:person.014706274717.52 schema:affiliation grid-institutes:grid.5386.8
136 schema:familyName Shi
137 schema:givenName Elaine
138 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014706274717.52
139 rdf:type schema:Person
140 grid-institutes:None schema:alternateName VMware Research, Palo Alto, USA
141 schema:name University of Maryland, College Park, USA
142 VMware Research, Palo Alto, USA
143 rdf:type schema:Organization
144 grid-institutes:grid.194645.b schema:alternateName The University of Hong Kong, Hong Kong, China
145 schema:name The University of Hong Kong, Hong Kong, China
146 rdf:type schema:Organization
147 grid-institutes:grid.5386.8 schema:alternateName Cornell University, Ithaca, USA
148 schema:name Cornell University, Ithaca, USA
149 rdf:type schema:Organization
 




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


...