New big-data analysis platforms can enable distributed computation on encrypted data by utilizing trusted computing primitives available in commodity server hardware. We study techniques for ensuring privacy preserving computation in the popular MapReduce framework. In this paper, we first show that protecting only individual units of distributed computation (e.g. map and reduce units), as proposed in recent works, leaves several important channels of information leakage exposed to the adversary. Next, we analyze a variety of design choices in achieving a stronger notion of private execution that is the analogue of using a distributed oblivious-RAM (ORAM) across the platform. We develop a simple solution which avoids using the expensive ORAM construction, and incurs only an additive logarithmic factor of overhead to the latency. We implement our solution in a system called (MR)-R-2, which enhances an existing Hadoop implementation, and evaluate it on seven standard MapReduce benchmarks. We show that it is easy to port most existing applications to (MR)-R-2 by changing fewer than 43 lines of code. (MR)-R-2 adds fewer than 500 lines of code to the TCB, which is less than 0.16% of the Hadoop codebase. (MR)-R-2 offers a factor of 1.3 x to 44.6 x lower overhead than extensions of previous solutions with equivalent privacy. (MR)-R-2 adds a total of 17% to 130% overhead over the insecure baseline solution that ignores the leakage channels (MR)-R-2 addresses.
