Combining ORAM with PIR to Minimize Bandwidth Costs

Cloud computing allows customers to outsource the burden of data management and benefit from economy of scale, but privacy concerns limit its reach. Even if the stored data are encrypted, access patterns may leak valuable information. Oblivious RAM (ORAM) protocols guarantee full access pattern privacy, but even the most efficient ORAMs proposed to date incur large bandwidth costs. We combine Private Information Retrieval (PIR) techniques with the most bandwidth-efficient existing ORAM scheme known to date (ObliviStore), to create OS+PIR, a new ORAM with bandwidth costs only half those of ObliviStore. For data block counts ranging from 2^20 to 2^30, OS+PIR achieves a total bandwidth cost of only 11X-13X blocks transferred per client block read+write, down from ObliviStore's 18X-26X. OS+PIR introduces several enhancements in addition to PIR in order to achieve its lower costs, including mechanisms for eliminating unused dummy blocks.