More is Less: Perfectly Secure Oblivious Algorithms in the Multi-server Setting View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2018-10-26

AUTHORS

T.-H. Hubert Chan , Jonathan Katz , Kartik Nayak , Antigoni Polychroniadou , Elaine Shi

ABSTRACT

The problem of Oblivious RAM (ORAM) has traditionally been studied in the single-server setting, but more recently the multi-server setting has also been considered. Yet it is still unclear whether the multi-server setting has any inherent advantages, e.g., whether the multi-server setting can be used to achieve stronger security goals or provably better efficiency than is possible in the single-server case.In this work, we construct a perfectly secure 3-server ORAM scheme that outperforms the best known single-server scheme by a logarithmic factor. In the process we also show, for the first time, that there exist specific algorithms for which multiple servers can overcome known lower bounds in the single-server setting. More... »

PAGES

158-188

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-030-03332-3_7

DOI

http://dx.doi.org/10.1007/978-3-030-03332-3_7

DIMENSIONS

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


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, Pokfulam, Hong Kong", 
          "id": "http://www.grid.ac/institutes/grid.194645.b", 
          "name": [
            "The University of Hong Kong, Pokfulam, 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": "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": "Katz", 
        "givenName": "Jonathan", 
        "id": "sg:person.01354261156.67", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01354261156.67"
        ], 
        "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 Tech, New York, USA", 
          "id": "http://www.grid.ac/institutes/None", 
          "name": [
            "Cornell Tech, New York, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Polychroniadou", 
        "givenName": "Antigoni", 
        "id": "sg:person.012233055347.82", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012233055347.82"
        ], 
        "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-10-26", 
    "datePublishedReg": "2018-10-26", 
    "description": "The problem of Oblivious RAM (ORAM) has traditionally been studied in the single-server setting, but more recently the multi-server setting has also been considered. Yet it is still unclear whether the multi-server setting has any inherent advantages, e.g., whether the multi-server setting can be used to achieve stronger security goals or provably better efficiency than is possible in the single-server case.In this work, we construct a perfectly secure 3-server ORAM scheme that outperforms the best known single-server scheme by a logarithmic factor. In the process we also show, for the first time, that there exist specific algorithms for which multiple servers can overcome known lower bounds in the single-server setting.", 
    "editor": [
      {
        "familyName": "Peyrin", 
        "givenName": "Thomas", 
        "type": "Person"
      }, 
      {
        "familyName": "Galbraith", 
        "givenName": "Steven", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-030-03332-3_7", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-030-03331-6", 
        "978-3-030-03332-3"
      ], 
      "name": "Advances in Cryptology \u2013 ASIACRYPT 2018", 
      "type": "Book"
    }, 
    "keywords": [
      "multi-server setting", 
      "single-server setting", 
      "Oblivious RAM", 
      "stronger security goals", 
      "single-server case", 
      "multiple servers", 
      "ORAM scheme", 
      "security goals", 
      "oblivious algorithms", 
      "specific algorithms", 
      "algorithm", 
      "better efficiency", 
      "logarithmic factor", 
      "lower bounds", 
      "scheme", 
      "server", 
      "inherent advantages", 
      "rams", 
      "bounds", 
      "advantages", 
      "goal", 
      "efficiency", 
      "work", 
      "setting", 
      "process", 
      "time", 
      "cases", 
      "first time", 
      "problem", 
      "factors", 
      "single-server scheme", 
      "Secure Oblivious Algorithms"
    ], 
    "name": "More is Less: Perfectly Secure Oblivious Algorithms in the Multi-server Setting", 
    "pagination": "158-188", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1107848414"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-030-03332-3_7"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-030-03332-3_7", 
      "https://app.dimensions.ai/details/publication/pub.1107848414"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-01-01T19:08", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220101/entities/gbq_results/chapter/chapter_135.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-030-03332-3_7"
  }
]
 

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-03332-3_7'

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-03332-3_7'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-030-03332-3_7'

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-03332-3_7'


 

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

137 TRIPLES      23 PREDICATES      57 URIs      50 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-030-03332-3_7 schema:about anzsrc-for:08
2 anzsrc-for:0804
3 schema:author N6d77b8b6063d471e8300c417c6833824
4 schema:datePublished 2018-10-26
5 schema:datePublishedReg 2018-10-26
6 schema:description The problem of Oblivious RAM (ORAM) has traditionally been studied in the single-server setting, but more recently the multi-server setting has also been considered. Yet it is still unclear whether the multi-server setting has any inherent advantages, e.g., whether the multi-server setting can be used to achieve stronger security goals or provably better efficiency than is possible in the single-server case.In this work, we construct a perfectly secure 3-server ORAM scheme that outperforms the best known single-server scheme by a logarithmic factor. In the process we also show, for the first time, that there exist specific algorithms for which multiple servers can overcome known lower bounds in the single-server setting.
7 schema:editor Nc684af2b5f884856927d896a59a909d8
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf N83ba58b4b38a45f4bb95a6ef1bf88708
12 schema:keywords ORAM scheme
13 Oblivious RAM
14 Secure Oblivious Algorithms
15 advantages
16 algorithm
17 better efficiency
18 bounds
19 cases
20 efficiency
21 factors
22 first time
23 goal
24 inherent advantages
25 logarithmic factor
26 lower bounds
27 multi-server setting
28 multiple servers
29 oblivious algorithms
30 problem
31 process
32 rams
33 scheme
34 security goals
35 server
36 setting
37 single-server case
38 single-server scheme
39 single-server setting
40 specific algorithms
41 stronger security goals
42 time
43 work
44 schema:name More is Less: Perfectly Secure Oblivious Algorithms in the Multi-server Setting
45 schema:pagination 158-188
46 schema:productId N2b0868560ceb40b2b08d3ad8939d98d5
47 N7f0b7f925c764a7c9e952f4deb832df0
48 schema:publisher N8ff2af7517a34fb585993f24c8c23c9e
49 schema:sameAs https://app.dimensions.ai/details/publication/pub.1107848414
50 https://doi.org/10.1007/978-3-030-03332-3_7
51 schema:sdDatePublished 2022-01-01T19:08
52 schema:sdLicense https://scigraph.springernature.com/explorer/license/
53 schema:sdPublisher Necbd7290579c4b0b9f40f19fda047b50
54 schema:url https://doi.org/10.1007/978-3-030-03332-3_7
55 sgo:license sg:explorer/license/
56 sgo:sdDataset chapters
57 rdf:type schema:Chapter
58 N16fdde37c6f34aef9038536bdaf3aca4 rdf:first Ne9082e59a71448d5ac29d1a0648dcb66
59 rdf:rest rdf:nil
60 N2a009ad3786f4d7b9e12633a5ac8aa96 rdf:first sg:person.014706274717.52
61 rdf:rest rdf:nil
62 N2b0868560ceb40b2b08d3ad8939d98d5 schema:name doi
63 schema:value 10.1007/978-3-030-03332-3_7
64 rdf:type schema:PropertyValue
65 N3a654508e43a462b838b2dbfe0938b9a schema:familyName Peyrin
66 schema:givenName Thomas
67 rdf:type schema:Person
68 N5676d566b2c14578b625b14a54d2a1d8 rdf:first sg:person.011031600672.42
69 rdf:rest Na2fd44aad60248bc8ca620e6a3722a83
70 N6d77b8b6063d471e8300c417c6833824 rdf:first sg:person.010251411300.37
71 rdf:rest N88f63a3e4949405a82e6ca8267886a76
72 N7f0b7f925c764a7c9e952f4deb832df0 schema:name dimensions_id
73 schema:value pub.1107848414
74 rdf:type schema:PropertyValue
75 N83ba58b4b38a45f4bb95a6ef1bf88708 schema:isbn 978-3-030-03331-6
76 978-3-030-03332-3
77 schema:name Advances in Cryptology – ASIACRYPT 2018
78 rdf:type schema:Book
79 N88f63a3e4949405a82e6ca8267886a76 rdf:first sg:person.01354261156.67
80 rdf:rest N5676d566b2c14578b625b14a54d2a1d8
81 N8ff2af7517a34fb585993f24c8c23c9e schema:name Springer Nature
82 rdf:type schema:Organisation
83 Na2fd44aad60248bc8ca620e6a3722a83 rdf:first sg:person.012233055347.82
84 rdf:rest N2a009ad3786f4d7b9e12633a5ac8aa96
85 Nc684af2b5f884856927d896a59a909d8 rdf:first N3a654508e43a462b838b2dbfe0938b9a
86 rdf:rest N16fdde37c6f34aef9038536bdaf3aca4
87 Ne9082e59a71448d5ac29d1a0648dcb66 schema:familyName Galbraith
88 schema:givenName Steven
89 rdf:type schema:Person
90 Necbd7290579c4b0b9f40f19fda047b50 schema:name Springer Nature - SN SciGraph project
91 rdf:type schema:Organization
92 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
93 schema:name Information and Computing Sciences
94 rdf:type schema:DefinedTerm
95 anzsrc-for:0804 schema:inDefinedTermSet anzsrc-for:
96 schema:name Data Format
97 rdf:type schema:DefinedTerm
98 sg:person.010251411300.37 schema:affiliation grid-institutes:grid.194645.b
99 schema:familyName Chan
100 schema:givenName T.-H. Hubert
101 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010251411300.37
102 rdf:type schema:Person
103 sg:person.011031600672.42 schema:affiliation grid-institutes:None
104 schema:familyName Nayak
105 schema:givenName Kartik
106 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011031600672.42
107 rdf:type schema:Person
108 sg:person.012233055347.82 schema:affiliation grid-institutes:None
109 schema:familyName Polychroniadou
110 schema:givenName Antigoni
111 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012233055347.82
112 rdf:type schema:Person
113 sg:person.01354261156.67 schema:affiliation grid-institutes:grid.164295.d
114 schema:familyName Katz
115 schema:givenName Jonathan
116 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01354261156.67
117 rdf:type schema:Person
118 sg:person.014706274717.52 schema:affiliation grid-institutes:grid.5386.8
119 schema:familyName Shi
120 schema:givenName Elaine
121 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014706274717.52
122 rdf:type schema:Person
123 grid-institutes:None schema:alternateName Cornell Tech, New York, USA
124 VMware Research, Palo Alto, USA
125 schema:name Cornell Tech, New York, USA
126 University of Maryland, College Park, USA
127 VMware Research, Palo Alto, USA
128 rdf:type schema:Organization
129 grid-institutes:grid.164295.d schema:alternateName University of Maryland, College Park, USA
130 schema:name University of Maryland, College Park, USA
131 rdf:type schema:Organization
132 grid-institutes:grid.194645.b schema:alternateName The University of Hong Kong, Pokfulam, Hong Kong
133 schema:name The University of Hong Kong, Pokfulam, Hong Kong
134 rdf:type schema:Organization
135 grid-institutes:grid.5386.8 schema:alternateName Cornell University, Ithaca, USA
136 schema:name Cornell University, Ithaca, USA
137 rdf:type schema:Organization
 




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


...