Privacy-preserving social network analysis for criminal investigations

ABSTRACT

Social network analysis (SNA) is now a commonly used tool in criminal investigations, but evidence gathering and analysis is often restricted by data privacy laws. We consider the case where multiple investigators want to collaborate, but do not yet have sufficient evidence that justifies a plaintext data exchange. This paper proposes a solution for privacy-preserving social network analysis where several investigators can collaborate without actually exchanging sensitive private information. An investigator can request data from other sites to augment his view without revealing personally identifiable data. The investigator can compute important metrics by means of a SNA on the subject while keeping the entire social network unknown him.

REFERENCES

• 1: Directive 95--46-EC on the protection of individuals with regard to the processing of personal data and on the free movement of such data. Available at http://ec.europa.eu/justice home/fsj/privacy, 1995.
• 2: IBM Entity Analytic Solutions. Available at http://ibm.com/db2/eas, 2005.
• 3: Mikhail J. Atallah , Florian Kerschbaum , Wenliang Du, Secure and private sequence comparisons, Proceedings of the 2003 ACM workshop on Privacy in the electronic society, October 30, 2003, Washington, DC [doi>10.1145/1005140.1005147]
• 4: Michael Ben-Or , Shafi Goldwasser , Avi Wigderson, Completeness theorems for non-cryptographic fault-tolerant distributed computation, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.1-10, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62213]
• 5: J. Brickell, and V. Shmatikov. Privacy-Preserving Graph Algorithms in the Semi-honest Model. Proceedings of AsiaCrypt, 2005.
• 6: R. Cramer, I. Damgard, and U. Maurer. General Secure Multi-party Computation from any Linear Secret-Sharing Scheme. Proceedings of EuroCrypt, 2000.
• 7: Ronald Cramer , Ivan Damgård , Jesper Buus Nielsen, Multiparty Computation from Threshold Homomorphic Encryption, Proceedings of the International Conference on the Theory and Application of Cryptographic Techniques: Advances in Cryptology, p.280-299, May 06-10, 2001
• 8: John Canny, Collaborative Filtering with Privacy, Proceedings of the 2002 IEEE Symposium on Security and Privacy, p.45, May 12-15, 2002
• 9: John Canny, Collaborative filtering with privacy via factor analysis, Proceedings of the 25th annual international ACM SIGIR conference on Research and development in information retrieval, August 11-15, 2002, Tampere, Finland [doi>10.1145/564376.564419]
• 10: I. Damgard, M. Fitzi, E. Kiltz, J. Nielsen, and T. Toft. Unconditionally Secure Constant-Rounds Multi-party Computation for Equality, Comparison, Bits and Exponentiation. Proceedings of Theoretical Cryptography Conference, 2006.
• 11: Ivan Damgård , Mats Jurik, A Generalisation, a Simplification and Some Applications of Paillier's Probabilistic Public-Key System, Proceedings of the 4th International Workshop on Practice and Theory in Public Key Cryptography: Public Key Cryptography, p.119-136, February 13-15, 2001
• 12: Yitao Duan , Jingtao Wang , Matthew Kam , John Canny, Privacy Preserving Link Analysis on Dynamic Weighted Graph, Computational & Mathematical Organization Theory, v.11 n.2, p.141-159, July 2005 [doi>10.1007/s10588-005-3941-2]
• 13: Robert W. Floyd, Algorithm 97: Shortest path, Communications of the ACM, v.5 n.6, p.345, June 1962 [doi>10.1145/367766.368168]
• 14: Keith Frikken, Privacy-Preserving Set Union, Proceedings of the 5th international conference on Applied Cryptography and Network Security, June 05-08, 2007, Zhuhai, China [doi>10.1007/978-3-540-72738-5_16]
• 15: Keith B. Frikken , Philippe Golle, Private social network analysis: how to assemble pieces of a graph privately, Proceedings of the 5th ACM workshop on Privacy in electronic society, October 30-30, 2006, Alexandria, Virginia, USA [doi>10.1145/1179601.1179619]
• 16: O. Goldreich. Secure Multi-party Computation. Available at www.wisdom.weizmann.ac.il/?oded/pp.html, 2002.
• 17: O. Goldreich , S. Micali , A. Wigderson, How to play ANY mental game, Proceedings of the nineteenth annual ACM symposium on Theory of computing, p.218-229, January 1987, New York, New York, United States [doi>10.1145/28395.28420]
• 18: W. Harper, and D. Harris. The application of link analysis to police intelligence. Human Factors 17(2), 1975.
• 19: L. Kissner, and D. Song. Privacy-Preserving Set Operations. Proceedings of CRYPTO, 2005.
• 20: P. Paillier. Public-Key Cryptosystems Based on Composite Degree Residuosity Classes. Proceedings of EUROCRYPT, 1999.
• 21: S. Pohlig, and M. Hellman. An improved algorithm for computing logarithms over GF(p) and its cryptographic significance. IEEE Transactions on Information Theory 24, 1978.
• 22: Huseyin Polat , Wenliang Du, Privacy-Preserving Collaborative Filtering Using Randomized Perturbation Techniques, Proceedings of the Third IEEE International Conference on Data Mining, p.625, November 19-22, 2003
• 23: M. Sparrow. The application of network analysis to criminal intelligence: an assessment of the prospects. Social Networks 13, 1991.
• 24: T. Toft. Primitives and Applications for Multi-party Computation. PhD dissertation, University of Aarhus, 2007.
• 25: T. Van Cangh, A. Boujraf. The Eurojust-Europol Case Study. Available at http://www.r4egov.eu/resources/details.php?Id taxonomy=6, 2007.
• 26: Jennifer Xu , Hsinchun Chen, Criminal network analysis and visualization, Communications of the ACM, v.48 n.6, p.100-107, June 2005 [doi>10.1145/1064830.1064834]
• 27: Andrew C. Yao, Protocols for secure computations, Proceedings of the 23rd Annual Symposium on Foundations of Computer Science (sfcs 1982), p.160-164, November 03-05, 1982

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Distributed applications

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.6 Security and Protection
          Subjects: Cryptographic controls

General Terms:
Algorithms, Security

Keywords:
criminal investigations, data sharing, privacy, social network analysis