# Mark Simkin

## Perfectly Secure Oblivious RAM with Sublinear Bandwidth Overhead

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

### Standard

Advances in Cryptology – ASIACRYPT 2019: 25th International Conference on the Theory and Application of Cryptology and Information Security Kobe, Japan, December 8–12, 2019 Proceedings. ed. / Steven D. Galbraith; Shiho Moriai. Vol. II Cham : Springer, 2019. p. 537-563 (Lecture Notes in Computer Science, Vol. 11922).

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

### Harvard

Raskin, M & Simkin, M 2019, Perfectly Secure Oblivious RAM with Sublinear Bandwidth Overhead. in SD Galbraith & S Moriai (eds), Advances in Cryptology – ASIACRYPT 2019: 25th International Conference on the Theory and Application of Cryptology and Information Security Kobe, Japan, December 8–12, 2019 Proceedings. vol. II, Springer, Cham, Lecture Notes in Computer Science, vol. 11922, pp. 537-563, 25th Annual International Conference on the Theory and Applications of Cryptology and Information Security, ASIACRYPT 2019, Kobe, Japan, 08/12/2019. https://doi.org/10.1007/978-3-030-34621-8_19

### APA

Raskin, M., & Simkin, M. (2019). Perfectly Secure Oblivious RAM with Sublinear Bandwidth Overhead. In S. D. Galbraith, & S. Moriai (Eds.), Advances in Cryptology – ASIACRYPT 2019: 25th International Conference on the Theory and Application of Cryptology and Information Security Kobe, Japan, December 8–12, 2019 Proceedings (Vol. II, pp. 537-563). Springer. Lecture Notes in Computer Science Vol. 11922 https://doi.org/10.1007/978-3-030-34621-8_19

### CBE

Raskin M, Simkin M. 2019. Perfectly Secure Oblivious RAM with Sublinear Bandwidth Overhead. Galbraith SD, Moriai S, editors. In Advances in Cryptology – ASIACRYPT 2019: 25th International Conference on the Theory and Application of Cryptology and Information Security Kobe, Japan, December 8–12, 2019 Proceedings. Cham: Springer. pp. 537-563. (Lecture Notes in Computer Science, Vol. 11922). https://doi.org/10.1007/978-3-030-34621-8_19

### MLA

Raskin, Michael and Mark Simkin "Perfectly Secure Oblivious RAM with Sublinear Bandwidth Overhead". and Galbraith, Steven D. Moriai, Shiho (editors). Advances in Cryptology – ASIACRYPT 2019: 25th International Conference on the Theory and Application of Cryptology and Information Security Kobe, Japan, December 8–12, 2019 Proceedings. Cham: Springer. (Lecture Notes in Computer Science, Vol. 11922). 2019, 537-563. https://doi.org/10.1007/978-3-030-34621-8_19

### Vancouver

Raskin M, Simkin M. Perfectly Secure Oblivious RAM with Sublinear Bandwidth Overhead. In Galbraith SD, Moriai S, editors, Advances in Cryptology – ASIACRYPT 2019: 25th International Conference on the Theory and Application of Cryptology and Information Security Kobe, Japan, December 8–12, 2019 Proceedings. Vol. II. Cham: Springer. 2019. p. 537-563. (Lecture Notes in Computer Science, Vol. 11922). https://doi.org/10.1007/978-3-030-34621-8_19

### Author

Raskin, Michael ; Simkin, Mark. / Perfectly Secure Oblivious RAM with Sublinear Bandwidth Overhead. Advances in Cryptology – ASIACRYPT 2019: 25th International Conference on the Theory and Application of Cryptology and Information Security Kobe, Japan, December 8–12, 2019 Proceedings. editor / Steven D. Galbraith ; Shiho Moriai. Vol. II Cham : Springer, 2019. pp. 537-563 (Lecture Notes in Computer Science, Vol. 11922).

### Bibtex

@inproceedings{fb610ef1709b4c728c52d7d18e2b7caf,
title = "Perfectly Secure Oblivious RAM with Sublinear Bandwidth Overhead",
abstract = "Oblivious RAM (ORAM) has established itself as a fundamental cryptographic building block.Understanding which bandwidth overheads are possible under which assumptions has been the topic of a vast amount of previous works.In this work, we focus on perfectly secure ORAM and we present the first construction with sublinear bandwidth overhead \emph{in the worst-case}.All prior constructions with perfect security require linear communication overhead in the worst-case and only achieve sublinear bandwidth overheads in the amortized sense.We present a fundamentally new approach for constructing ORAM and our results significantly advance our understanding of what is possible with perfect security.Our main construction, Lookahead ORAM, is perfectly secure, has a worst-case bandwidth overhead of $\bigO{\sqrt{n}}$, and a total storage cost of $\bigO{n}$ on the server-side, where $N$ is the maximum number of stored data elements.In terms of concrete server-side storage costs, our construction has the smallest storage overhead among all perfectly and statistically secure ORAMs and is only a factor 3 worse than the most storage efficient computationally secure ORAM.Assuming a client-side position map, our construction is the first, among all ORAMs with worst-case sublinear overhead, that allows for a $\bigO{1}$ online bandwidth overhead without server-side computation.Along the way, we construct a conceptually extremely simple statistically secure ORAM with a worst-case bandwidth overhead of $\bigO{\sqrt{n}\frac{\log{n}}{\log{\log{n}}}}$, which may be of independent interest.",
author = "Michael Raskin and Mark Simkin",
year = "2019",
doi = "10.1007/978-3-030-34621-8_19",
language = "English",
isbn = "978-3-030-34620-1",
volume = "II",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "537--563",
editor = "Galbraith, {Steven D. } and Shiho Moriai",
booktitle = "Advances in Cryptology – ASIACRYPT 2019",
note = "25th Annual International Conference on the Theory and Applications of Cryptology and Information Security, ASIACRYPT 2019 ; Conference date: 08-12-2019 Through 12-12-2019",

}

### RIS

TY - GEN

T1 - Perfectly Secure Oblivious RAM with Sublinear Bandwidth Overhead

AU - Simkin, Mark

PY - 2019

Y1 - 2019

N2 - Oblivious RAM (ORAM) has established itself as a fundamental cryptographic building block.Understanding which bandwidth overheads are possible under which assumptions has been the topic of a vast amount of previous works.In this work, we focus on perfectly secure ORAM and we present the first construction with sublinear bandwidth overhead \emph{in the worst-case}.All prior constructions with perfect security require linear communication overhead in the worst-case and only achieve sublinear bandwidth overheads in the amortized sense.We present a fundamentally new approach for constructing ORAM and our results significantly advance our understanding of what is possible with perfect security.Our main construction, Lookahead ORAM, is perfectly secure, has a worst-case bandwidth overhead of $\bigO{\sqrt{n}}$, and a total storage cost of $\bigO{n}$ on the server-side, where $N$ is the maximum number of stored data elements.In terms of concrete server-side storage costs, our construction has the smallest storage overhead among all perfectly and statistically secure ORAMs and is only a factor 3 worse than the most storage efficient computationally secure ORAM.Assuming a client-side position map, our construction is the first, among all ORAMs with worst-case sublinear overhead, that allows for a $\bigO{1}$ online bandwidth overhead without server-side computation.Along the way, we construct a conceptually extremely simple statistically secure ORAM with a worst-case bandwidth overhead of $\bigO{\sqrt{n}\frac{\log{n}}{\log{\log{n}}}}$, which may be of independent interest.

AB - Oblivious RAM (ORAM) has established itself as a fundamental cryptographic building block.Understanding which bandwidth overheads are possible under which assumptions has been the topic of a vast amount of previous works.In this work, we focus on perfectly secure ORAM and we present the first construction with sublinear bandwidth overhead \emph{in the worst-case}.All prior constructions with perfect security require linear communication overhead in the worst-case and only achieve sublinear bandwidth overheads in the amortized sense.We present a fundamentally new approach for constructing ORAM and our results significantly advance our understanding of what is possible with perfect security.Our main construction, Lookahead ORAM, is perfectly secure, has a worst-case bandwidth overhead of $\bigO{\sqrt{n}}$, and a total storage cost of $\bigO{n}$ on the server-side, where $N$ is the maximum number of stored data elements.In terms of concrete server-side storage costs, our construction has the smallest storage overhead among all perfectly and statistically secure ORAMs and is only a factor 3 worse than the most storage efficient computationally secure ORAM.Assuming a client-side position map, our construction is the first, among all ORAMs with worst-case sublinear overhead, that allows for a $\bigO{1}$ online bandwidth overhead without server-side computation.Along the way, we construct a conceptually extremely simple statistically secure ORAM with a worst-case bandwidth overhead of $\bigO{\sqrt{n}\frac{\log{n}}{\log{\log{n}}}}$, which may be of independent interest.

U2 - 10.1007/978-3-030-34621-8_19

DO - 10.1007/978-3-030-34621-8_19

M3 - Article in proceedings

SN - 978-3-030-34620-1

VL - II

T3 - Lecture Notes in Computer Science

SP - 537

EP - 563

BT - Advances in Cryptology – ASIACRYPT 2019

A2 - Galbraith, Steven D.

A2 - Moriai, Shiho

PB - Springer

CY - Cham

T2 - 25th Annual International Conference on the Theory and Applications of Cryptology and Information Security, ASIACRYPT 2019

Y2 - 8 December 2019 through 12 December 2019

ER -