Rings for Privacy: An Architecture for Large Scale Privacy-Preserving Data Mining

摘要

This article proposes a new architecture for privacy-preserving data mining based on Multi Party Computation (MPC) and secure sums. While traditional MPC approaches rely on a small number of aggregation peers replacing a centralized trusted entity, the current study puts forth a distributed solution that involves all data sources in the aggregation process, with the help of a single server for storing intermediate results. A large-scale scenario is examined and the possibility that data become inaccessible during the aggregation process is considered, a possibility that traditional schemes often neglect. Here, it is explicitly examined, as it might be provoked by intermittent network connectivity or sudden user departures. For increasing system reliability, data sources are organized in multiple sets, called rings, which independently work on the aggregation process. Two different protocol schemes are proposed and their failure probability, i.e., the probability that the data mining output cannot guarantee the desired level of accuracy, is analytically modeled. The privacy degree, the communication cost and the computational complexity that the schemes exhibit are also characterized. Finally, the new protocols are applied to some specific use cases, demonstrating their feasibility and attractiveness.