Oblivious random access machine (ORAM) constructions can be used to hide a client's access pattern from a trusted but curious storage server. The privacy provided comes at the cost of increasing communication overhead, storage overhead, and computation overhead of the system. Recursive matrix-based ORAM (RM-ORAM) is a new ORAM construction, which is designed for constrained storage space devices. RM-ORAM significantly reduces the client storage usage by using recursion, while the computational and bandwidth overhead are slightly increased as a tradeoff. However, it can achieve better overall asymptotic performance than other existing ORAM schemes, e.g., recursive Path ORAM. In this paper, we present the construction and its theoretical analysis. In addition, we present how to select the appropriate number of data blocks, which are being downloaded per level of recursion and the appropriate size of reserved space on the client. We provide theoretical security and performance analysis, as well as experimental results to illustrate how RM-ORAM satisfies security requirements and provides improved performance compared with other ORAM schemes.

Oblivious RAM can hide a client's access pattern from an untrusted storage server. However current ORAM schemes incur a large communication overhead and/or client storage overhead, especially as the server storage size grows. We have proposed a matrix-based ORAM, M-ORAM, that makes the communication overhead independent of the server size. This requires selecting a height of the matrix; we present how to select the height to match the functionality of the well-known Path ORAM. We then given both theoretical models and experimental results that show M-ORAM can achieve a lower communication overhead than Path ORAM, without a significant increase in maximum client storage overhead.