Hole-Free Differentially Private Multiparty Laplace Mechanism

Abstract Differential privacy (DP) employs noise addition methods to protect individual data privacy. These methods integrate a controlled quantity of random noise into a database query response to obscure the presence of any specific individual in the dataset. Previous studies exposed challenges when a query response is calculated using standard numerical formats like floating-point or fixed-point arithmetic, which can lead to output limitations that potentially compromise privacy protections. To overcome these challenges, the Google DP team developed algorithms to approximate the Laplace and Gaussian mechanisms. These algorithms generate noise from discrete distributions and round the query response to a predetermined level of precision. Building on this research, our study introduces three multiparty computation protocols to implement the Laplace mechanism. These protocols are specifically designed for linear queries and can handle real-valued functions on floating-point inputs. They offer information-theoretic security against passive adversaries, with potential extensions for protection against malicious threats. The three protocols cater to different application needs by balancing interactive operations, round complexities, and failure probabilities. Not only do our proposed protocols adhere to the strict standards of DP, but they also enhance the application to real-valued queries, showcasing their practicality and effectiveness.