Paper 2013/086

Efficient Private File Retrieval by Combining ORAM and PIR

Travis Mayberry and Erik-Oliver Blass and Agnes Chan

Abstract

Recent research results on tree-based Oblivious RAM by Shi et al. obtain communication complexity for an N-capacity storage with blocks of size l bits of O(l · log3(N)) in the worst-case. The individual nodes in the tree, however, are constructed using traditional ORAMs which have worst-case communication complexity linear in their capacity and block size. PIR protocols are able to provide better worst-case bounds (decoupling capacity from block size), but have traditionally been less practical than ORAM due to the fact that they require O(N) computational complexity on the server. This paper presents Path-PIR, a hybrid ORAM construction, using techniques from PIR, that overcomes the individual weaknesses of each. Path-PIR significantly reduces communication complexity when the block size of the ORAM is large. Compared to existing work, this leads to orders of magnitude smaller data transfer costs for practically sized databases and achieves asymptotic communication of only O(l·log2 (N)) for large block sizes. Additionally, the typically high computational cost of PIR is negated by the tree structure of the ORAM, which requires that only a small fraction of the database be computed over for each query. We also investigate the concept of an ORAM’s latency, which is the amount of communication required before users receive the result of their query. We show that Path-PIR achieves smaller latency than any existing scheme, only about four times the block size. Using Amazon EC2 as an example, we demonstrate that even with the additional cost on PIR computation, Path-PIR provides a significant monetary saving compared to related work.