Abstract
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.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
Domain size \(|\mathcal {D}_k|\) indicates the number of different values a field can take.
- 2.
\(\Vert X\Vert =\lceil \log _2|X|\rceil \) denotes size in bits of X.
References
Amazon Elastic MapReduce. http://aws.amazon.com/elasticmapreduce/
Apache. Hadoop (2010). http://hadoop.apache.org/
Babai, L., Fortnow, L.: Arithmetization: a new method in structural complexity theory. Comput. Complex. 1(1), 41–66 (1991). ISSN 1016-3328
Boneh, D., Di Crescenzo, G., Ostrovsky, R., Persiano, G.: Public key encryption with keyword search. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 506–522. Springer, Heidelberg (2004)
Brakerski, Z., Vaikuntanathan, V.: Fully homomorphic encryption from Ring-LWE and security for key dependent messages. In: Rogaway, P. (ed.) CRYPTO 2011. LNCS, vol. 6841, pp. 505–524. Springer, Heidelberg (2011)
Dean, J., Ghemawat, S.: MapReduce: simplified data processing on large clusters. In: Proceedings of Symposium on Operating System Design and Implementation, San Francisco, USA, pp. 137–150 (2004)
Dwork, C.: Differential privacy. In: Bugliesi, M., Preneel, B., Sassone, V., Wegener, I. (eds.) ICALP 2006. LNCS, vol. 4052, pp. 1–12. Springer, Heidelberg (2006)
Gentry, C.: Fully homomorphic encryption using ideal lattices. In: STOC 2009, pp. 169–178 (2009)
Gentry, C., Halevi, S.: Implementing gentry’s fully-homomorphic encryption scheme. In: Paterson, K.G. (ed.) EUROCRYPT 2011. LNCS, vol. 6632, pp. 129–148. Springer, Heidelberg (2011)
Kamara, S., Raykova, M.: Parallel homomorphic encryption. In: Adams, A.A., Brenner, M., Smith, M. (eds.) FC 2013. LNCS, vol. 7862, pp. 213–225. Springer, Heidelberg (2013)
Lauter, K., Naehrig, N., Vaikuntanathan, V.: Can homomorphic encryption be practical?. In: Proceedings of ACM Workshop on Cloud Computing Security, Chicago, USA (2011)
Shamir, A.: IP = PSPACE. J. ACM 39(4), 869–877 (1992). ISSN 0004–5411
Song, D., Wagner, D., Perrig, A.: Practical techniques for searches on encrypted data. In: Proceedings of Symposium on Security and Privacy, Berkeley, USA, pp. 44–55 (2000)
Trostle, J., Parrish, A.: Efficient computationally private information retrieval from anonymity or trapdoor groups. In: Burmester, M., Tsudik, G., Magliveras, S., Ilić, I. (eds.) ISC 2010. LNCS, vol. 6531, pp. 114–128. Springer, Heidelberg (2011)
Vaikuntanathan, V.: Computing blindfolded: new developments in fully homomorphic encryption. In: FOCS 2011, Washington, DC, USA, pp. 5–16 (2011). ISBN 978-0-7695-4571-4
van Dijk, M., Gentry, C., Halevi, S., Vaikuntanathan, V.: Fully homomorphic encryption over the integers. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 24–43. Springer, Heidelberg (2010)
Vo-Huu, T.D., Blass, E.-O., Noubir, G.: EPiC Source Code. http://www.ccs.neu.edu/home/noubir/projects/epic
Acknowledgement
This work was partially supported by NSF grant 1218197.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Vo-Huu, T.D., Blass, EO., Noubir, G. (2015). EPiC: Efficient Privacy-Preserving Counting for MapReduce. In: Bouajjani, A., Fauconnier, H. (eds) Networked Systems . NETYS 2015. Lecture Notes in Computer Science(), vol 9466. Springer, Cham. https://doi.org/10.1007/978-3-319-26850-7_29
Download citation
DOI: https://doi.org/10.1007/978-3-319-26850-7_29
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-26849-1
Online ISBN: 978-3-319-26850-7
eBook Packages: Computer ScienceComputer Science (R0)