Recursive M-ORAM: A matrix ORAM for clients with constrained storage space

Although oblivious RAM (ORAM) can hide a client’s access pattern from an untrusted server, bandwidth and local storage requirements can be excessive. Path ORAM, Matrix ORAM and other schemes can greatly bandwidth cost, but on devices with constrained storage space they require too much local storage. We design a recursive version of Matrix ORAM, where data addresses are stored on the server instead of client, and are recursively accessed with revealing important information. We analyse our algorithm and show it keeps bandwidth, client storage and computational overhead each to O(log N).