Abstract
Privacy-preserving techniques for distributed computation have been proposed recently as a promising framework in collaborative inter-domain network monitoring. Several different approaches exist to solve such class of problems, e.g., Homomorphic Encryption (HE) and Secure Multiparty Computation (SMC) based on Shamir’s Secret Sharing algorithm (SSS). Such techniques are complete from a computation-theoretic perspective: given a set of private inputs, it is possible to perform arbitrary computation tasks without revealing any of the intermediate results. In this paper we advocate the use of “elementary” (as opposite to “complete“) Secure Multiparty Computation (E-SMC) procedures for traffic monitoring. E-SMC supports only simple computations with private input and public output, i.e., they can not handle secret input nor secret (intermediate) output. The proposed simplification brings a dramatic reduction in complexity and enables massive-scale implementation with acceptable delay and overhead. Notwithstanding their simplicity, we claim that a simple additive E-SMC scheme is sufficient to perform many computation tasks of practical relevance to collaborative network monitoring, such as anonymous publishing and set operations.
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
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Roughan, M., Zhang, Y.: Secure distributed data-mining and its application to large-scale network measurements. ACM Computer Communication Review 36(1) (2006)
Burkhart, M., Strasser, M., Many, D., Dimitropoulos, X.: SEPIA: Privacy-Preserving Aggregation of Multi-Domain Network Events and Statistics. In: 19th USENIX Security Symposium, Washington, DC, USA (August 2010)
Gentry, C.: Fully homomorphic encryption using ideal lattices. In: ACM symposium on Theory of Computing. ACM, New York (2009)
Ben-Or, M., Goldwasser, S., Wigderson, A.: Completeness theorems for non-cryptographic fault-tolerant distributed computation. In: ACM Symp. on Theory of computing, STOC (1988)
Atallah, M., Bykova, M., Li, J., Frikken, K., Topkara, M.: Private collaborative forecasting and benchmarking. In: Proc. ACM WPES 2004 (October 2004)
Ricciato, F., Burkhart, M.: Reduce to the max: A simple approach for massive-scale privacy-preserving collaborative network measurements (extended version). CoRR, vol. abs/1101.5509 (2011), http://arxiv.org/abs/1101.5509
Broder, A., Mitzenmacher, M.: Network applications of bloom filters: A survey. Internet Mathematics 1(4), 485–509 (2004)
Kissner, L., Song, D.: Privacy-Preserving Set Operations. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol. 3621, pp. 241–257. Springer, Heidelberg (2005)
Chaum, D.: The dining cryptographers problem: Unconditional sender and recipient untraceability. Journal of Cryptology 1(1), 65–75 (1988)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Ricciato, F., Burkhart, M. (2011). Reduce to the Max: A Simple Approach for Massive-Scale Privacy-Preserving Collaborative Network Measurements (Short Paper). In: Domingo-Pascual, J., Shavitt, Y., Uhlig, S. (eds) Traffic Monitoring and Analysis. TMA 2011. Lecture Notes in Computer Science, vol 6613. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-20305-3_9
Download citation
DOI: https://doi.org/10.1007/978-3-642-20305-3_9
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-20304-6
Online ISBN: 978-3-642-20305-3
eBook Packages: Computer ScienceComputer Science (R0)