International Association
for Cryptologic Research

In the face of an untrusted cloud infrastructure, outsourced data

needs to be protected. Fully homomorphic encryption is one solution

that also allows performing operations on outsourced data. However,

the involved high overhead of today\'s fully homomorphic encryption

techniques outweigh cloud cost saving advantages, rendering it

impractical. We present EPiC, a practical, efficient protocol for

the privacy-preserving evaluation of a fundamental operation on data

sets: frequency counting. In an IND-CPA encrypted outsourced data

set, a cloud user can specify a pattern, and the cloud will count

the number of occurrences of this pattern in a completely oblivious

manner. EPiC\'s main idea is, first, to reduce the problem of

counting to polynomial evaluation. Second, to efficiently evaluate

polynomials in a privacy-preserving manner, we extend previous work

on the Hidden Modular Group Order assumption and design a new

\\emph{somewhat homomorphic} encryption scheme. This scheme is highly

efficient in our particular counting scenario with a relatively

small number of possible patterns. 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

data sets sizes of up to 1 TByte shows only modest overhead compared

to non-private counting, attesting to EPiC\'s efficiency.