International Association
for Cryptologic Research

Recent techniques to reduce ORAM communication complexity down to constant in the number of blocks N. However, they induce expensive additively homomorphic encryption on both the server and the client. We present two new hybrid ORAM constructions that combine ORAM with Private Information Storage. We store and access individual ORAM buckets with PIS. As a result, our first ORAM features widetilde{O}(log N) communication complexity and a small block size of Omega(log^3 N) bit. The second ORAM features optimal O(1) communication complexity and Omega(log^4 N) bit block size. Both ORAMs have constant client-side memory complexity. A highlight of our approach is that neither client nor server are required to perform any encryption. The above properties make our ORAMs extremely lightweight, suitable for deployment even on resource-constrained devices. In addition to a theoretical analysis, we also implement our ORAMs to show their practicality and compare to related work.