International Association
for Cryptologic Research

Recent research results on \"bucketed\" ORAM reduce com- munication of N-capacity storage with blocks of length l bits down to poly-logarithmic complexity O(l · log^3 N ). The individual buckets, how- ever, are constructed using traditional ORAMs which have worst-case communication complexity being linear in their size. PIR protocols are able to provide better worst-case bounds, but have traditionally been less practical than ORAM due to the fact that they require O(N) computa- tion complexity on the server. This paper presents Path-PIR, a hybrid construction between PIR and ORAM that overcomes the individual weaknesses of each. Path-PIR\'s main idea is to replace the individual buckets in the ORAM construction by Shi et al. [15] with buckets backed by PIR. We show that this leads to substantially smaller data transfer costs for many databases of practical size and lower worst-case costs, O(l · log^2 (N) + log^3 (N)), than the existing construction. Additionally, the typically high computational cost of PIR is offset by the small size of the individual buckets. We also show that Path-PIR has very low latency, i.e., a low amount of data is required before a user receives the result of his data request (less than 10 times the block size). Using Amazon EC2, we demonstrate that monetary cost induced by the server\'s PIR computation are far outweighed by the savings in data transfer.