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": "2021-12-01T20:05", 
    "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_320.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 N012a4454a87845cc93210cc4260381fd
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 N52738401e06b4a51b8416847e9ad55ea
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf N916ce332e9c4412d8be7e465c4746349
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 N1686c0056b0149fcae03221c3380c172
47 N5f370dcb52754fecab2ba0250f1004aa
48 schema:publisher N310f5ff1f2f54994806f9de39af1a018
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 2021-12-01T20:05
52 schema:sdLicense https://scigraph.springernature.com/explorer/license/
53 schema:sdPublisher Nbc184c4933c74899b615a069910b78e9
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 N012a4454a87845cc93210cc4260381fd rdf:first sg:person.010251411300.37
59 rdf:rest N56b0eb4478344f60a7609a62f3f9ffd8
60 N1686c0056b0149fcae03221c3380c172 schema:name doi
61 schema:value 10.1007/978-3-030-03332-3_7
62 rdf:type schema:PropertyValue
63 N1a635efc626f4d71b10393fd03c3c138 rdf:first sg:person.011031600672.42
64 rdf:rest N886e65cf416347a082262e35db74c055
65 N310f5ff1f2f54994806f9de39af1a018 schema:name Springer Nature
66 rdf:type schema:Organisation
67 N52738401e06b4a51b8416847e9ad55ea rdf:first Nf1c9eb0d4e7e405ca4211d647c0ca510
68 rdf:rest Ndf45e50907c647d594673d8b47ef6a87
69 N56b0eb4478344f60a7609a62f3f9ffd8 rdf:first sg:person.01354261156.67
70 rdf:rest N1a635efc626f4d71b10393fd03c3c138
71 N5f370dcb52754fecab2ba0250f1004aa schema:name dimensions_id
72 schema:value pub.1107848414
73 rdf:type schema:PropertyValue
74 N886e65cf416347a082262e35db74c055 rdf:first sg:person.012233055347.82
75 rdf:rest Ned6b1cb0f40443d8970dee34d63d36e2
76 N916ce332e9c4412d8be7e465c4746349 schema:isbn 978-3-030-03331-6
77 978-3-030-03332-3
78 schema:name Advances in Cryptology – ASIACRYPT 2018
79 rdf:type schema:Book
80 Nbc184c4933c74899b615a069910b78e9 schema:name Springer Nature - SN SciGraph project
81 rdf:type schema:Organization
82 Ndf45e50907c647d594673d8b47ef6a87 rdf:first Ne604ba948e2f4c16a683eca1390ccdb8
83 rdf:rest rdf:nil
84 Ne604ba948e2f4c16a683eca1390ccdb8 schema:familyName Galbraith
85 schema:givenName Steven
86 rdf:type schema:Person
87 Ned6b1cb0f40443d8970dee34d63d36e2 rdf:first sg:person.014706274717.52
88 rdf:rest rdf:nil
89 Nf1c9eb0d4e7e405ca4211d647c0ca510 schema:familyName Peyrin
90 schema:givenName Thomas
91 rdf:type schema:Person
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)


...