EPiC: Efficient Privacy-Preserving Counting for MapReduce
In the face of an untrusted cloud infrastructure, outsourced data needs to be protected. We present EPiC, a practical protocol for the privacy-preserving evaluation of a fundamental operation on data sets: frequency counting. We show how a general pattern, defined by a Boolean formula, is arithmetized into a multivariate polynomial and used in EPiC. To increase the performance of the system, we introduce a new efficient privacy-preserving encoding with “somewhat homomorphic” properties based on previous work on the Hidden Modular Group assumption. Besides a formal analysis where we prove EPiC’s privacy, we also present implementation and evaluation results. We specifically target Google’s prominent MapReduce paradigm as offered by major cloud providers. Our evaluation performed both locally and in Amazon’s public cloud with up to 1 TB data sets shows only a modest overhead of \(20\,\%\) compared to non-private counting, attesting to EPiC’s efficiency.