ORAM is the acronym of an Oblivious Random-Access Machine.
The main idea is to hide the access patterns from attackers.
For example, when a client tries to access data stored in the server, the server cannot gain any information about the user access pattern.
Imagine data storage, where each data is inside a block, and that block is inside a node (or bucket.)
Each node (or bucket) may have multiple blocks inside or even none.
Now to access a block, there is a path.
And the client (who wants to access it) has a map for it, called Position Map.
The position map has information about the block’s position. Each block has its block’s position information.
So when a client wants to access, say block 7, then it will look into the position map where is the location of block 7.
Then how does it traverse the path? There are two principles.
- Principle A: Push the blocks as deep as possible. Try the deepest node first. If already full, try upper level node. But when all nodes is full, then store it in the stash.
- Principle B: Block should be always in the same path from its position.
Let’s continue with our example, the client wants to write block 7.
- Lookup block position
- Read the entire path, in this case, 1 -> 7 -> 13 -> 10 -> 6. These block is stored in stash
- Now client can modify data in 7th block.
- The client assign new random position for the block.
- Finally write path back to different node position but in the still in the same path as before.
Here is the example case with different blocks, both access patterns are indistinguishable.
That’s it for the simple explanation of ORAM!
I hope it’s useful for your quick understanding. 🙂
Credits: Slides taken from my Professor