Link analysis for private weighted graphs

ABSTRACT

Link analysis methods have been used successfully for knowledge discovery from the link structure of mutually linking entities. Existing link analysis methods have been inherently designed based on the fact that the entire link structure of the target graph is observable such as public web documents; however, link information in graphs in the real world, such as human relationship or economic activities, is rarely open to public. If link analysis can be performed using graphs with private links in a privacy-preserving way, it enables us to rank entities connected with private ties, such as people, organizations, or business transactions. In this paper, we present a secure link analysis for graphs with private links by means of cryptographic protocols. Our solutions are designed as privacy-preserving expansions of well-known link analysis methods, PageRank and HITS. The outcomes of our protocols are completely equivalent to those of PageRank and HITS. Furthermore, our protocols theoretically guarantee that the private link information possessed by each node is not revealed to other nodes. %We demonstrate the efficiency of our solution by experimental studies, comparing with existing solutions, such as secure function evaluation, decentralized spectral analysis, and privacy-preserving link-analysis.

REFERENCES

• 1: 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
• 2: Ivan Damgård , Maciej Koprowski, Practical Threshold RSA Signatures without a Trusted Dealer, Proceedings of the International Conference on the Theory and Application of Cryptographic Techniques: Advances in Cryptology, p.152-165, May 06-10, 2001
• 3: 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]
• 4: Oded Goldreich, Foundations of Cryptography: Volume 2, Basic Applications, Cambridge University Press, New York, NY, 2004
• 5: David Goldschlag , Michael Reed , Paul Syverson, Onion routing, Communications of the ACM, v.42 n.2, p.39-41, Feb. 1999 [doi>10.1145/293411.293443]
• 6: David Kempe , Frank McSherry, A decentralized algorithm for spectral analysis, Journal of Computer and System Sciences, v.74 n.1, p.70-83, February, 2008 [doi>10.1016/j.jcss.2007.04.014]
• 7: Jon M. Kleinberg, Authoritative sources in a hyperlinked environment, Journal of the ACM (JACM), v.46 n.5, p.604-632, Sept. 1999 [doi>10.1145/324133.324140]
• 8: Dahlia Malkhi , Noam Nisan , Benny Pinkas , Yaron Sella, Fairplay—a secure two-party computation system, Proceedings of the 13th conference on USENIX Security Symposium, p.20-20, August 09-13, 2004, San Diego, CA
• 9: L. Page, S. Brin, R. Motwani, and T. Winograd. The pagerank citation ranking: Bringing order to the web, 1998.
• 10: Jun Sakuma , Shigenobu Kobayashi , Rebecca N. Wright, Privacy-preserving reinforcement learning, Proceedings of the 25th international conference on Machine learning, p.864-871, July 05-09, 2008, Helsinki, Finland [doi>10.1145/1390156.1390265]
• 11: Andrew Chi-Chih Yao, How to generate and exchange secrets, Proceedings of the 27th Annual Symposium on Foundations of Computer Science, p.162-167, October 27-29, 1986 [doi>10.1109/SFCS.1986.25]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.m MISCELLANEOUS

General Terms:
Algorithms

Keywords:
hits, link analysis, pagerank, privacy, ranking