Privacy-Preserving Locator Services by Multi-Party Deterministic Noise Generation
Xi Liu, Yuzhe Tang, Katchaguy Areekijseree, Amin Fallahi and Shuang Wang
Syracuse University, Syracuse University, Syracuse University, Syracuse University, University of California, San Diego

In emerging federated database systems, such as Health Information Exchange (or HIE), an important yet understudied problem is the privacy-preserving sharing of personal records among autonomous data owners. The goal poses technical design challenges, including the assured privacy preservation under background-knowledge attacks, and scalable and secure multi-party computations on private big-data in a large-scale system. To tackle the challenges, we propose a protocol, multi-party deterministic noising or MPDN, which deterministically injects noises to the published meta-data while staying aware of the background knowledge. It also optimizes the performance of multi-party computation (or MPC) by pre-computation on the public background knowledge. The pre-computation exhibits data-level parallelism and we leverage general-purpose computing on graphics processing units (GPGPU) in our implementation to exploit the parallelism and to further optimize performance. The proposed protocol is implemented on open-source MPC software (i.e., GMW) and its efficiency with a speedup of more than an order of magnitude is demonstrated in a geo-distributed setting. Through evaluation on real-world datasets, the assurance of privacy preservation is also verified.