Secure and efficient multi-server oblivious random access machine in a malicious execution environment

Abstract

An oblivious distributed file system is provided using an oblivious random access machine (ORAM), including an ORAM balanced tree structure, where each node in the tree is configured to store data blocks, the structure including at least two shares. The system also includes at least two ORAM servers, each of the servers configured to communicate with a client ORAM device, and programmed to facilitate storage of a different subset of the shares of the tree structure using a distributed file system and to implement an access procedure of a tree-based ORAM using the tree structure, including a retrieval phase and an eviction phase. In the retrieval phase, the servers utilize an authenticated Private Information Retrieval (PIR) protocol to retrieve data blocks as requested from the client ORAM device. In the eviction phase, the servers utilize a linear secret sharing scheme.