Protocols for Privacy-Preserving DBSCAN Clustering

다국어 초록 (Multilingual Abstract)

Cooperative computation is one of the most important fields in computer science. In recent years, the development of networking increases the desirability of cooperative computation. But privacy concerns often prevent different parties from sharing their data. Secure multiparty computation techniques can dispel parties’ doubts about revealing privacy information in this situation. On the other hand, Data mining has been a popular research area for more than a decade. However, in many applications, the data are originally collected at different sites owned by different users. This paper considers the problem of privacy preserving DBSCAN clustering over vertically partitioned data based on some results of SMC. An efficient secure intersection protocol is first proposed. The security and complexity of the protocols are also analyzed. The results show that the protocols preserve the privacy of the data and the time complexity as well as the communication complexity is acceptable.

목차 (Table of Contents)

• Abstract
• 1. Introduction
• 2. Related work
• 2.1. Secure channel assumption and adversarial behaviors
• 2.2. Secure sum protocol
• 2.3. Millionaires’ protocol
• 2.4 Commutative encryption
• 3. Secure intersection protocol
• 3.1. Protocol
• 3.2. Analysis
• 4. Privacy preserving DBSCAN algorithm
• 4.1 Basic concepts
• 4.2 Problem formulation
• 4.3 Secure two-party clustering
• 4.4 Secure multi-party clustering
• 5. Algorithm analysis
• 5.1 Correctness
• 5.2 Worst-case time analysis
• 5.3 Worst-case communication analysis
• 5.4 Security
• 6. Conclusion
• 7. Acknowledgement
• 8. References