1Constant Communication ORAM without Encryption

Abstract—Recent techniques 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 Õ(logN) communication complexity and a small block size of Ω(log3N) bit. The second ORAM features optimal O(1) communication complexity and Ω(log4N) bit block size. Both ORAMs have constant client-side memory complexity. The 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. I