Computational Secure ORAM (COMP SE-ORAM) with [omega](log n) Overhead: Amazon S3 Case Study – Random Access Location

Oblivious RAM (ORAM) is a strong-provable secured approach to accessing cloud stored objects. Many ORAM models have been proposed to improve storage, communication and privacy efficiency of the ORAM constructions with no much attention paid to a holistic approach to the oblivious cloud storage security. Statically secure ORAM models generally have the security overhead of ω̃(log
²
n) where n is the memory size. This paper proposes an ORAM model with computational security overhead of ω̃(log n) using Amazon Simple Storage (Amazon S3) as a storage model. Another benefit of this proposed model is its conceptual simplicity at implementation. The construction of this model is based on the ORAM model proposed by Kai-Min Chung, Zhenming Liu and Rafael Pass. The crucial ramification of this model is to reduce the overhead from ω̃(log
²
n) to ω̃(log n). Using the Amazon S3, security analysis was conducted with the result incurring ω̃(log n) security overhead. This is achieved by randomizing the location of the storage node.