More is less: Perfectly secure oblivious algorithms in the multi-server setting
Publication
, Conference
Chan, THH; Katz, J; Nayak, K; Polychroniadou, A; Shi, E
Published in: Lecture Notes in Computer Science Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics
January 1, 2018
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.
Duke Scholars
Published In
Lecture Notes in Computer Science Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics
DOI
EISSN
1611-3349
ISSN
0302-9743
Publication Date
January 1, 2018
Volume
11274 LNCS
Start / End Page
158 / 188
Related Subject Headings
- Artificial Intelligence & Image Processing
- 46 Information and computing sciences
Citation
APA
Chicago
ICMJE
MLA
NLM
Chan, T. H. H., Katz, J., Nayak, K., Polychroniadou, A., & Shi, E. (2018). More is less: Perfectly secure oblivious algorithms in the multi-server setting. In Lecture Notes in Computer Science Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics (Vol. 11274 LNCS, pp. 158–188). https://doi.org/10.1007/978-3-030-03332-3_7
Chan, T. H. H., J. Katz, K. Nayak, A. Polychroniadou, and E. Shi. “More is less: Perfectly secure oblivious algorithms in the multi-server setting.” In Lecture Notes in Computer Science Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics, 11274 LNCS:158–88, 2018. https://doi.org/10.1007/978-3-030-03332-3_7.
Chan THH, Katz J, Nayak K, Polychroniadou A, Shi E. More is less: Perfectly secure oblivious algorithms in the multi-server setting. In: Lecture Notes in Computer Science Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics. 2018. p. 158–88.
Chan, T. H. H., et al. “More is less: Perfectly secure oblivious algorithms in the multi-server setting.” Lecture Notes in Computer Science Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics, vol. 11274 LNCS, 2018, pp. 158–88. Scopus, doi:10.1007/978-3-030-03332-3_7.
Chan THH, Katz J, Nayak K, Polychroniadou A, Shi E. More is less: Perfectly secure oblivious algorithms in the multi-server setting. Lecture Notes in Computer Science Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics. 2018. p. 158–188.
Published In
Lecture Notes in Computer Science Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics
DOI
EISSN
1611-3349
ISSN
0302-9743
Publication Date
January 1, 2018
Volume
11274 LNCS
Start / End Page
158 / 188
Related Subject Headings
- Artificial Intelligence & Image Processing
- 46 Information and computing sciences