Simple and efficient two-server ORAM

S. Dov Gordon, Jonathan Katz, Xiao Wang*

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We show a protocol for two-server oblivious RAM (ORAM) that is simpler and more efficient than the best prior work. Our construction combines any tree-based ORAM with an extension of a two-server private information retrieval scheme by Boyle et al., and is able to avoid recursion and thus use only one round of interaction. In addition, our scheme has a very cheap initialization phase, making it well suited for RAM-based secure computation. Although our scheme requires the servers to perform a linear scan over the entire data, the cryptographic computation involved consists only of block-cipher evaluations. A practical instantiation of our protocol has excellent concrete parameters: for storing an N-element array of arbitrary size data blocks with statistical security parameter ƛ, the servers each store 4N encrypted blocks, the client stores ƛ +2log N blocks, and the total communication per logical access is roughly 10 log N encrypted blocks.

Original languageEnglish (US)
Title of host publicationAdvances in Cryptology – ASIACRYPT 2018 - 24th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings
EditorsThomas Peyrin, Steven Galbraith
PublisherSpringer Verlag
Pages141-157
Number of pages17
ISBN (Print)9783030033316
DOIs
StatePublished - Jan 1 2018
Event24th Annual International Conference on Theory and Application of Cryptology and Information Security, ASIACRYPT 2018 - Brisbane, Australia
Duration: Dec 2 2018Dec 6 2018

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11274 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference24th Annual International Conference on Theory and Application of Cryptology and Information Security, ASIACRYPT 2018
CountryAustralia
CityBrisbane
Period12/2/1812/6/18

Fingerprint

Random access storage
Servers
Server
Private Information Retrieval
Secure Computation
Network protocols
Block Cipher
Information retrieval
Initialization
Recursion
Entire
Concretes
Communication
Evaluation
Arbitrary
Interaction

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this

Dov Gordon, S., Katz, J., & Wang, X. (2018). Simple and efficient two-server ORAM. In T. Peyrin, & S. Galbraith (Eds.), Advances in Cryptology – ASIACRYPT 2018 - 24th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings (pp. 141-157). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11274 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-030-03332-3_6
Dov Gordon, S. ; Katz, Jonathan ; Wang, Xiao. / Simple and efficient two-server ORAM. Advances in Cryptology – ASIACRYPT 2018 - 24th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings. editor / Thomas Peyrin ; Steven Galbraith. Springer Verlag, 2018. pp. 141-157 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{a215367bb4944dce839148e2b65e588c,
title = "Simple and efficient two-server ORAM",
abstract = "We show a protocol for two-server oblivious RAM (ORAM) that is simpler and more efficient than the best prior work. Our construction combines any tree-based ORAM with an extension of a two-server private information retrieval scheme by Boyle et al., and is able to avoid recursion and thus use only one round of interaction. In addition, our scheme has a very cheap initialization phase, making it well suited for RAM-based secure computation. Although our scheme requires the servers to perform a linear scan over the entire data, the cryptographic computation involved consists only of block-cipher evaluations. A practical instantiation of our protocol has excellent concrete parameters: for storing an N-element array of arbitrary size data blocks with statistical security parameter ƛ, the servers each store 4N encrypted blocks, the client stores ƛ +2log N blocks, and the total communication per logical access is roughly 10 log N encrypted blocks.",
author = "{Dov Gordon}, S. and Jonathan Katz and Xiao Wang",
year = "2018",
month = "1",
day = "1",
doi = "10.1007/978-3-030-03332-3_6",
language = "English (US)",
isbn = "9783030033316",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "141--157",
editor = "Thomas Peyrin and Steven Galbraith",
booktitle = "Advances in Cryptology – ASIACRYPT 2018 - 24th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings",

}

Dov Gordon, S, Katz, J & Wang, X 2018, Simple and efficient two-server ORAM. in T Peyrin & S Galbraith (eds), Advances in Cryptology – ASIACRYPT 2018 - 24th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 11274 LNCS, Springer Verlag, pp. 141-157, 24th Annual International Conference on Theory and Application of Cryptology and Information Security, ASIACRYPT 2018, Brisbane, Australia, 12/2/18. https://doi.org/10.1007/978-3-030-03332-3_6

Simple and efficient two-server ORAM. / Dov Gordon, S.; Katz, Jonathan; Wang, Xiao.

Advances in Cryptology – ASIACRYPT 2018 - 24th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings. ed. / Thomas Peyrin; Steven Galbraith. Springer Verlag, 2018. p. 141-157 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11274 LNCS).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

TY - GEN

T1 - Simple and efficient two-server ORAM

AU - Dov Gordon, S.

AU - Katz, Jonathan

AU - Wang, Xiao

PY - 2018/1/1

Y1 - 2018/1/1

N2 - We show a protocol for two-server oblivious RAM (ORAM) that is simpler and more efficient than the best prior work. Our construction combines any tree-based ORAM with an extension of a two-server private information retrieval scheme by Boyle et al., and is able to avoid recursion and thus use only one round of interaction. In addition, our scheme has a very cheap initialization phase, making it well suited for RAM-based secure computation. Although our scheme requires the servers to perform a linear scan over the entire data, the cryptographic computation involved consists only of block-cipher evaluations. A practical instantiation of our protocol has excellent concrete parameters: for storing an N-element array of arbitrary size data blocks with statistical security parameter ƛ, the servers each store 4N encrypted blocks, the client stores ƛ +2log N blocks, and the total communication per logical access is roughly 10 log N encrypted blocks.

AB - We show a protocol for two-server oblivious RAM (ORAM) that is simpler and more efficient than the best prior work. Our construction combines any tree-based ORAM with an extension of a two-server private information retrieval scheme by Boyle et al., and is able to avoid recursion and thus use only one round of interaction. In addition, our scheme has a very cheap initialization phase, making it well suited for RAM-based secure computation. Although our scheme requires the servers to perform a linear scan over the entire data, the cryptographic computation involved consists only of block-cipher evaluations. A practical instantiation of our protocol has excellent concrete parameters: for storing an N-element array of arbitrary size data blocks with statistical security parameter ƛ, the servers each store 4N encrypted blocks, the client stores ƛ +2log N blocks, and the total communication per logical access is roughly 10 log N encrypted blocks.

UR - http://www.scopus.com/inward/record.url?scp=85057593839&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85057593839&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-03332-3_6

DO - 10.1007/978-3-030-03332-3_6

M3 - Conference contribution

AN - SCOPUS:85057593839

SN - 9783030033316

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 141

EP - 157

BT - Advances in Cryptology – ASIACRYPT 2018 - 24th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings

A2 - Peyrin, Thomas

A2 - Galbraith, Steven

PB - Springer Verlag

ER -

Dov Gordon S, Katz J, Wang X. Simple and efficient two-server ORAM. In Peyrin T, Galbraith S, editors, Advances in Cryptology – ASIACRYPT 2018 - 24th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings. Springer Verlag. 2018. p. 141-157. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-030-03332-3_6