Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I am reading the paper Software Protection and Simulation on Oblivious RAMs by Oded Goldreich and Rafail Ostrovsky. And I wonder about the description of the "Square Root" solution of oblivious RAM simulation at page 20.

The algorithm seems simple: the aim is to 'simluate' the original RAM of size $m$ by an oblivious RAM of size $m+2\sqrt{m}$. So it uses the first $m+\sqrt{m}$ cells of the oblivious RAM to shuffle or to obscure, and uses the last $\sqrt{m}$ cells as a cache (or shelter) in case of leaking information about access frequency.

However, the first step to use the shelter reads 'first, we scan through the entire shelter and check whether the contents of the virtual word $i$ is in one of the shelter's words. '

Here, we want to simulate an original RAM access at location $i$ (for fetching the virtual word $i$) by using the shelter, and then comes the question : since we haven't known what the contents of virtual word $i$ actually was yet, how do we check whether it has been in the shelter or not?

share|improve this question
up vote 1 down vote accepted

Presumably, the shelter could store a bunch of pairs $(a,v)$ where $v$ is the contents of the virtual word at address $a$. Then, to scan through the shelter to see whether it has the value of the virtual word at address $i$, you'd just check whether the shelter contains any pair $(a,v)$ where $a=i$.

I don't know whether this is actually what Goldreich and Ostrovsky do, but it seems like one natural candidate scheme that could be used.

share|improve this answer
Ah I figured it out, thank you for your answer! – phan Aug 26 '13 at 4:09

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.