PanORAMa: Oblivious RAM with Logarithmic Overhead
PanORAMa: Oblivious RAM with Logarithmic Overhead
复制标题
PanORAMA：具有对数开销的遗忘 RAM
DOI：
10.1109/focs.2018.00087
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Kevin Yeo
中科院分区：
文献类型：
--
作者：
Sarvar Patel;G. Persiano;Mariana Raykova;Kevin Yeo
我们提出PanORAMa，第一个不经意的RAM结构，实现通信开销O（log N log N）的数据库的N个块和任何块大小B = Ω（log N），而只需要一个恒定数量的内存块的客户端内存。我们的方案可以在“球和箱”模型中实例化，其中Goldreich和Ostrovsky [JACM 96]显示了ORAM通信的Ω（log N）下限。我们的构造遵循ORAM设计的分层方法，并依赖于两个独立利益的主要构建块：一个新的不经意哈希表构造，具有改进的摊销O（log N + poly（log log λ））的通信开销，并且N = poly（λ），假设其输入被随机混洗;以及一种互补的新的不经意随机多阵列混洗结构，当输入具有一定的熵水平时，该结构以O（Nlog log λ + Nlog N/log λ）的通信量混洗N个数据块。我们联合收割机这两个原语，以改善我们的分层ORAM结构中的洗牌时间，避免沉重的遗忘洗牌和利用熵剩余的合并级别从以前的洗牌。因此，摊销洗牌成本是渐近相同的查找复杂度在我们的建设。
We present PanORAMa, the first Oblivious RAM construction that achieves communication overhead O(log N log log N) for database of N blocks and for any block size B = Ω(log N) while requiring client memory of only a constant number of memory blocks. Our scheme can be instantiated in the "balls and bins" model in which Goldreich and Ostrovsky [JACM 96] showed an Ω(log N) lower bound for ORAM communication. Our construction follows the hierarchical approach to ORAM design and relies on two main building blocks of independent interest: a new oblivious hash table construction with improved amortized O(log N + poly(log log λ)) communication overhead for security parameter λ and N = poly(λ), assuming its input is randomly shuffled; and a complementary new oblivious random multi-array shuffle construction, which shuffles N blocks of data with communication O(N log log λ + N log N/log λ) when the input has a certain level of entropy. We combine these two primitives to improve the shuffle time in our hierarchical ORAM construction by avoiding heavy oblivious shuffles and leveraging entropy remaining in the merged levels from previous shuffles. As a result, the amortized shuffle cost is asymptotically the same as the lookup complexity in our construction.