2
$\begingroup$

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.

$\endgroup$

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.