XPORAM: A Practical Multi-client ORAM Against Malicious Adversaries

Oblivious RAM (ORAM) was proposed to solve the problem of memory disclosure, preventing the system from reverse engineering attacks. Naturally, researchers apply ORAM into the out-sourced storage scenarios widely to protect the users’ access patterns, including the sequence, the time, the correlation of the accesses, etc., which might compromise the users’ private information and be utilized by malicious adversaries to launch attacks. ORAM typically protect user information by transforming a single access to the target item into a sequence accesses to multiple items, periodically reshuffling the accessed data. However, these extra operations bring about extra storage, computation and communication cost. Especially when applied to the multi-client scenarios, the overhead will be usually multiplied considering both the security and the performance. Current multi-client ORAM schemes suffer from the large overhead because of complicated architecture or cryptographic primitive, such as fully-homomorphic encryption, private information retrieval. This paper presents \(\textsf{XPORAM}\) , an efficient Oblivious RAM scheme appropriate for practical multi-client scenarios against malicious adversaries. Using the architecture of the non-colluding model, our scheme constructs multi-party secure communication while achieving obliviousness. Our security analysis guarantees the secure deployment of \(\textsf{XPORAM}\) and our experimental results demonstrate the O(1) communication overhead and \(O(\log N)\) computation overhead without requiring any trustworthy proxy.