Oblivious RAMs without cryptogrpahic assumptions
Oblivious RAMs without cryptogrpahic assumptions
复制标题
没有密码假设的遗忘 RAM
DOI：
10.1145/1806689.1806716
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
M. Ajtai
中科院分区：
文献类型：
--
作者：
M. Ajtai
在不使用任何密码学假设的情况下，基于概率（抛硬币）随机存取存储器（RAM），时间和空间需求的渐进式增加是可能的。模拟失败的概率可忽略不计。如果使用\(n\)个存储单元，那么失败的概率至多为\(n - \log n\)。1979年，皮彭杰（Pippenger）和费舍尔（Fischer）表明（见[7]），一台具有一维磁带、执行长度为\(n\)的计算的图灵机，可以由一台具有二维磁带的无感知图灵机在线模拟，时间复杂度为\(O(n\log n)\)，其中如果图灵机磁头的移动作为时间的函数与它的输入无关，那么该图灵机就是无感知的。对于随机存取存储器，无感知的概念是由戈德里赫（Goldreich）在1987年的[2]中定义的，并且他证明了一个关于它的模拟定理。如果随机存取存储器的存储访问模式（即哪些存储单元在什么时间被访问）的分布与在该随机存取存储器上运行的程序无关（前提是程序使用的时间是固定的），那么该随机存取存储器就是无感知的。也就是说，一个观察存储访问的对手除了程序的总运行时间外，不会知道机器上运行的程序的任何信息。奥斯特罗夫斯基（Ostrovsky）改进了戈德里赫的定理，他在1990年表明（见[4]、[5]、[3]），一个使用\(n\)个存储单元的随机存取存储器可以由一个具有随机预言机（其中随机比特可以被重复访问）的无感知随机存取存储器模拟，使得空间和时间需求的增加仅约为\(\ln\)因子（戈德里赫的因子约为\(\exp[(\log n)^{1/2}]\)）。在这两种情况下，如果我们接受一些未经证明的密码学假设，例如单向函数的存在，那么具有随机预言机的无感知随机存取存储器可以被一个无感知概率（抛硬币）随机存取存储器所替代。在本文中，我们表明，即使没有任何密码学假设，使用无感知抛硬币随机存取存储器进行模拟，时间和空间需求仅增加\(\ln\)因子也是可能的。
ithmic increase in the time and space requirements is possible on a probabilistic (coin flipping) RAM without using any cryptographic assumptions. The simulation will fail with a negligible probability. If n memory locations are used, then the probability of failure is at most n-log n. Pippenger and Fischer has shown in 1979, see [7], that a Turing machine with one-dimensional tapes, performing a computation of length n can be simulated on-line by an oblivious Turing machine with two dimensional tapes, in time O(n log n), where a Turing machine is oblivious if the movements of it heads as a function of time are independent of its input. For RAMs the notion of obliviousness was defined by Goldreich in 1987 in [2], and he proved a simulation theorem about it. A RAM is oblivious if the distribution of its memory access pattern, which memory cells are accessed at which time, is independent of the program running on the RAM, provided that the time used by the program is fixed. That is, an adversary watching the memory access will not know anything about the program running on the machine apart from its total time. Ostrovsky, improving Goldreich's theorem, has shown in 1990, see [4], [5], [3], that a RAM using n memory cells can a be simulated by an oblivious RAM with a random oracle (where the random bits can be accessed repeatedly) so that the increase of the space and time requirement is only about a factor of ln (Goldreich's factor was about exp[(log n)1/2]). In both cases the oblivious RAM with a random oracle, can be replaced, by an oblivious probabilistic (coin-flipping) RAM, provided that we accept some unproven cryptographic assumptions, e.g., the existence of a one-way function. In this paper we show that simulation with an oblivious, coin-flipping RAM, with only a factor of ln increase in time and space requirements, is possible, even without any cryptographic assumptions.