$1$ Squareroot ORAM

Describe the square root ORAM construction in detail. In particular, describe the role of dummy items and stash

$($cache$).$ Please make sure your answer is precise. Do not use words that are not necessary and add value to the

answer. $20$ marks

Consider a memory of size $n.$ Suppose we change the size of the stash $($cache$)$ to $n^{\frac{1}{3}}.$ What would be the amortized

cost to do one read operation. Show your work. $10$ marks