Virtually all "hierarchical" Oblivious RAMs use "cryptographically secure" hash functions to determine the position of an item at a given level; and implicitly assume (as can be evinced from the cost analysis in the respective papers) that these hash functions can be evaluated in $O(1)$ steps.

Then it seems to me that, if one is using $b-$bit words and simulating up to $n$ accesses, at least one of the following three conditions must hold:

  1. the hash functions are randomly selected at the beginning of the simulation from an ensemble of $n^{\omega(1)}$ functions and not revealed to the adversary (contrary to virtually all oracle/pseudorandom function conventions); this is never stated, and in many constructions the opposite is stated.
  2. the number of simulated steps, $n$, is such that $2^{b}=n^{\omega(1)}$, i.e. the size of each word in bits must be strictly superlogarithmic in $\lg n$.
  3. the probability that an adversary can distinguish the simulations of two given computations is $n^{-O(1)}$ and not $n^{-\omega(1)}$, i.e. polynomially but not negligibly small in $n$.

The argument is very simple: since each hash function is computed from the virtual address to be accessed and up to $O(1)$ additional words, i.e. $O(b)$ additional bits, the adversary who knows that at a given step one of the two possible computations will access virtual address $addr_1$, and in the other virtual address $addr_2$, can guess the remaining bits with probability $2^{-b}$. And if he guesses correctly and has access to the hash function he can distinguish between the two computations with probability $1$. Then the adversary with access to the hash function can distinguish between the two computations with probability $2^{-b}$, and either this probability is $n^{-O(1)}$ or $b=\omega(\lg n)$.

The original Goldreich-Ostrovsky construction made it clear that $n$ could grow up to $2^{\Omega(b)}$, so it was considering case 3. But virtually all hierarchical ORAM constructions in the literature of this decade (e.g. the Goodrich-Mitzenmacher "cuckoo" ORAM, the Kushilevitz-et-al. "rebalanced" ORAM, Pyramid ORAM, and several others) are very explicit about the fact that words are of $O(\lg n)$ bits, and at the same time that the adversary succeeds with probability $n^{-\omega(1)}$ ... so we can be neither in case 2 nor in case 3. Yet I find it hard to believe that we are in case 1, an incredibly non-standard model for pseudorandom functions/random oracles that is in fact never made explicit.

It seems to me I am missing something, but I have no clue about what. Even the smallest hint would be greatly appreciated.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.