Abstract
In recent years there has been massive progress in the development of technologies for storing and processing of data. If statistical analysis could be applied to such data when it is distributed between several organisations, there could be huge benefits. Unfortunately, in many cases, for legal or commercial reasons, this is not possible.
The idea of using the theory of multi-party computation to analyse efficient algorithms for privacy preserving data-mining was proposed by Pinkas and Lindell. The point is that algorithms developed in this way can be used to overcome the apparent impasse described above: the owners of data can, in effect, pool their data while ensuring that privacy is maintained.
Motivated by this, we describe how to securely compute the mean of an attribute value in a database that is shared between two parties. We also demonstrate that existing solutions in the literature that could be used to do this leak information, therefore underlining the importance of applying rigorous theoretical analysis rather than settling for ad hoc techniques.
Chapter PDF
Similar content being viewed by others
References
Aggarwal, G., Mishra, N., Pinkas, B.: Secure computation of the k th-ranked element. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 40–55. Springer, Heidelberg (2004)
Algesheimer, J., Camenisch, J.L., Shoup, V.: Efficient computation modulo a shared secret with application to the generation of shared safe-prime products. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, pp. 417–432. Springer, Heidelberg (2002)
Ben-Or, M., Goldwasser, S., Wigderson, A.: Completeness theorems for non-cryptographic fault-tolerant distributed computation. In: 20th ACM Symposium on Theory of Computing, pp. 1–10. ACM Press, New York (1988)
Canetti, R.: Security and composition of multiparty cryptographic protocols. Journal of Cryptology 13(1), 143–202 (2000)
Canetti, R., Lindell, Y., Ostrovsky, R., Sahai, A.: Universally composable two-party computation. In: 34th ACM Symposium on Theory of Computing, pp. 494–503. ACM Press, New York (2002)
Chanm, D., Crépeau, C., Damgård, I.: Multiparty unconditionally secure protocols. In: 20th ACM Symposium on Theory of Computing, pp. 11–19. ACM Press, New York (1988)
Du., W.: A Study of Several Specific Secure Two-party Computation Problems. PhD thesis, Department of Computer Science, Purdue University (2001)
Du, W., Atallah, J.: Privacy-preserving cooperative scientific computations. In: 14th IEEE Computer Security Foundations Workshop, pp. 273–282 (2001)
Du, W., Atallah, M.J.: Privacy-preserving cooperative statistical analysis. In: 2001 ACSAC: Annual Computer Security Applications Conference, pp. 102–110 (2001)
Du, W., Atallah, M.J.: Secure multi-party computation problems and their applications: A review and open problems. In: New Security Paradigms Workshop, pp. 11–20 (2001)
Du, W., Han, Y.S., Chen, S.: Privacy-preserving multivariate statistical analysis: Linear regression and classification. In: 4th SIAM International Conference on Data Mining (2004)
Du, W., Zahn, Z.: Building decision tree classifier on private data. In: Workshop on Privacy, Security, and Data Mining at The 2002 IEEE International Conference on Data Mining (ICDM), pp. 1–8 (2002)
Du, W., Zhan, Z.: A practical approach to solve secure multi-party computation problems. In: New Security Paradigms Workshop, pp. 127–135 (2002)
Feigenbaum, J., Ishai, Y., Malkin, T., Nissim, K., Strauss, M., Wright, R.N.: Secure multiparty computation of approximations. In: Orejas, F., Spirakis, P.G., van Leeuwen, J. (eds.) ICALP 2001. LNCS, vol. 2076, pp. 927–938. Springer, Heidelberg (2001); Full version on Cryptology ePrint Archive, Report 2001/024
Freedman, M.J., Nissim, K., Pinkas, B.: Efficient private matching and set intersection. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 1–19. Springer, Heidelberg (2004)
von zur Gathen, J., Gerhard., J.: Modern computer algebra, 2nd edn. Cambridge University Press, New York (2003)
Goldreich, O.: Foundations of Cryptography, Basic Applications, vol. 2. Cambridge University Press, Cambridge (2004)
Goldreich, O., Micali, S., Wigderson, A.: How to play any mental game: A completeness theorem for protocols with honest majority. In: 19th ACM Symposium on Theory of Computing, pp. 218–229. ACM Press, New York (1997)
Goldreich, O., Vainish, R.: How to solve any protocol problem - an efficiency improvement. In: Pomerance, C. (ed.) CRYPTO 1987. LNCS, vol. 293, pp. 73–86. Springer, Heidelberg (1988)
Lindell, Y., Pinkas, B.: Privacy preserving data mining. In: Bellare, M. (ed.) CRYPTO 2000. LNCS, vol. 1880, p. 36. Springer, Heidelberg (2000)
Lindell, Y., Pinkas, B.: Privacy preserving data mining. Journal of Cryptology 15(3), 117–206 (2002)
Naor, M., Pinkas, B.: Oblivious transfer and polynomial evaluation. In: 31st ACM Symposium on Theory of Computing, pp. 245–254. ACM Press, New York (1999), Full version available at http://www.wisdom.weizmann.ac.il/%7Enaor/onpub.html
Naor, M., Pinkas, B.: Efficient oblivious transfer protocols. In: 12th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 448–457 (2001)
UK Government. Data protection act (1998), Available at http://www.hmso.gov.uk/acts/acts1998/19980029.htm
Vaidya, J., Clifton, C.: Privacy preserving naive bayes classifier for vertically partitioned data. In: 4th SIAM International Conference on Data Mining (2004)
Vaidya, J.S.: Privacy Preserving Data Mining over Vertically Partitioned Data. PhD thesis, Department of Computer Science, Purdue University (2004)
Wang, X., Pan, V.Y.: Acceleration of Euclidean algorithm and rational number reconstruction. SIAM Journal on Computing 32(2), 548–556 (2003)
Yao, A.C.: How to generate and exchange secrets. In: 27th Annual Symposium on Foundations of Computer Science, pp. 162–167. IEEE Computer Society Press, Los Alamitos (1986)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Kiltz, E., Leander, G., Malone-Lee, J. (2005). Secure Computation of the Mean and Related Statistics. In: Kilian, J. (eds) Theory of Cryptography. TCC 2005. Lecture Notes in Computer Science, vol 3378. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-30576-7_16
Download citation
DOI: https://doi.org/10.1007/978-3-540-30576-7_16
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-24573-5
Online ISBN: 978-3-540-30576-7
eBook Packages: Computer ScienceComputer Science (R0)Springer Nature Proceedings Computer Science
Keywords
- Secure Computation
- Leak Information
- Oblivious Transfer
- Privacy Preserve Data Mining
- Oblivious Transfer Protocol
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.