M-ORAM revisited: Security and construction updates

Abstract

© Springer Nature Switzerland AG 2018. Oblivious Random Access Machine (ORAM) [4] was introduced in regard to secure the access patterns seen by a server when the data have been retrieved. Matrix based ORAM (M-ORAM) [5] is one of ORAM constructions. It has been introduced in the matrix data structure format and can achieve O(1) for both bandwidth overhead and computation complexity. With the impressive performance results; however, the given security proof is not well defined. We therefore revisit the paper to give a new proper proof method to construct the access sequence which is statically indistinguishable from random accesses. In addition according to our new security proof, M-ORAM has a security weakness in a specific circumstance. Hence, the improved M-ORAM construction which can solve the problem is also introduced.