A Lower Bound for One-Round Oblivious RAM
A Lower Bound for One-Round Oblivious RAM
复制标题
一轮遗忘 RAM 的下界
DOI：
10.1007/978-3-030-64375-1_16
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Hoover, Alexander
中科院分区：
文献类型：
--
作者：
Cash, David;Drucker, Andrew;Hoover, Alexander
我们对 Oblivious RAM (ORAM) 的轮复杂度进行了细粒度的研究。我们证明，任何不重复球的一轮球箱 ORAM 必须具有带宽或客户端内存，其中 N 是被模拟的内存插槽的数量。这表明此类方案严格弱于一般（多轮）ORAM 或具有服务器计算的方案，并且特别意味着 Goldreich 和 Ostrovksy（J. ACM 1996）的原始平方根 ORAM 的一轮版本是最佳的。我们通过不同于 Goldreich 和 Ostrovksy 以及 Larsen 和 Nielsen (CRYPTO 2018) 的新技术证明了这一界限，这些技术分别实现了 balls-in-bins 和一般多轮 ORAM 的 anbound。最后，我们给出了边界的较弱扩展，允许有限的球重复，并且还表明我们的边界扩展到限制形式的多轮 ORAM，其中包括最著名的结构。
We initiate a fine-grained study of the round complexity of Oblivious RAM (ORAM). We prove that any one-round balls-in-bins ORAM that does not duplicate balls must have eitherbandwidth orclient memory, whereNis the number of memory slots being simulated. This shows that such schemes are strictly weaker than general (multi-round) ORAMs or those with server computation, and in particular implies that a one-round version of the original square-root ORAM of Goldreich and Ostrovksy (J. ACM 1996) is optimal. We prove this bound via new techniques that differ from those of Goldreich and Ostrovksy, and of Larsen and Nielsen (CRYPTO 2018), which achieved anbound for balls-in-bins and general multi-round ORAMs respectively. Finally we give a weaker extension of our bound that allows for limited duplication of balls, and also show that our bound extends to multiple-round ORAMs of a restricted form that include the best known constructions.
登录
查看更多内容
是的，有一个不经意的 RAM 下界！
DOI：
--
发表时间：
2018
期刊：
IACR Cryptology ePrint Archive
影响因子：
--
作者：
Kasper Green Larsen;J. Nielsen
通讯作者：
J. Nielsen
PanORAMA：具有对数开销的遗忘 RAM
DOI：
10.1109/focs.2018.00087
发表时间：
2018
期刊：
2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS)
影响因子：
--
作者：
Sarvar Patel;G. Persiano;Mariana Raykova;Kevin Yeo
通讯作者：
Kevin Yeo
重温乱码 RAM
DOI：
10.1007/978-3-642-55220-5_23
发表时间：
2014
期刊：
2013 IEEE 26th Computer Security Foundations Symposium
影响因子：
--
作者：
Craig Gentry;S. Halevi;Steve Lu;R. Ostrovsky;Mariana Raykova;Daniel Wichs
通讯作者：
Daniel Wichs
黑盒乱码RAM
DOI：
--
发表时间：
2015
期刊：
Annual Symposium on Foundations of Computer Science
影响因子：
--
作者：
Garg, Sanjam;Lu, Steve;Ostrovsky, Rafail
通讯作者：
Ostrovsky, Rafail
论遗忘并行 RAM 的深度
DOI：
10.1007/978-3-319-70694-8_20
发表时间：
2017
期刊：
The Annals of Statistics
影响因子：
--
作者：
T;Kai;E. Shi
通讯作者：
E. Shi