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.