Privacy Preserving Computation in Cloud Using Reusable Garbled Oblivious RAMs

Abstract

When users store encrypted data in a cloud environment, it is important for users to ask cloud to carry out some computation on the remote data remotely. ORAM is a good potential approach to carry out this kind of remote operation. In order to use ORAM for this purpose, we still need to have garbled programs to run on ORAM. Goldwasser et al. and Lu-Ostrovsky initiated the study of garbled RAM machines in their 2013 Crypto papers. Goldwasser et al's scheme is based on fully homomorphic encryption schemes and attribute based encryption schemes for general RAM machines. Lu and Ostrovsky's scheme is based on one-time garbled circuits and for each input, one has to design as many one-time garbled circuits as ORAM CPU running steps. That is, for each execution of the program, the data owner needs to upload a new program to the cloud to run on ORAM. Using recent results on indistinguishability obfuscation, this paper designs alternative reusable garbled ORAM programs. The reusable garbled ORAM CPU constructed in this paper is of constant size while the size of the garbled ORAM CPUs by Lu and Ostrovsky depends on the number of ORAM CPU running steps.