Distributed Data Mining with Differential Privacy

With recent advances in communication and data storage technology, an explosive amount of information is being collected and stored in the Internet. Even though such vast amount of information presents great opportunities for knowledge discovery, organizations might not want to share their data due to legal or competitive reasons. This posts the challenge of mining knowledge while preserving privacy. Current efficient privacy-preserving data mining algorithms are based on an assumption that it is acceptable to release all the intermediate results during the data mining operations. However, it has been shown that such intermediate results can still leak private information. In this work, we use differential privacy to quantitatively limit such information leak. Differential privacy is a newly emerged privacy definition that is capable of providing strong measurable privacy guarantees. We propose Secure group Differential private Query (SDQ), a new algorithm that combines techniques from differential privacy and secure multiparty computation. Using decision tree induction as a case study, we show that SDQ can achieve stronger privacy than current efficient secure multiparty computation approach, and better accuracy than current differential privacy approach while maintaining efficiency.