Jonas Böhler (SAP Security Research), Florian Kerschbaum (University of Waterloo)

In distributed private learning, e.g., data analysis, machine learning, and enterprise benchmarking, it is commonplace for two parties with confidential data sets to compute statistics over their combined data. The median is an important robust statistical method used in enterprise benchmarking, e.g., companies compare typical employee salaries, insurance companies use median life expectancy to adjust insurance premiums, banks compare credit scores of their customers, and financial regulators estimate risks based on loan exposures.

The exact median can be computed securely, however, it leaks information about the private data. To protect the data sets, we securely compute a differentially private median over the joint data set via the exponential mechanism. The exponential mechanism has a runtime linear in the data universe size and efficiently sampling it is non-trivial. Local differential privacy, where each user shares locally perturbed data with an untrusted server, is often used in private learning but does not provide the same utility as the central model, where noise is only applied once by a trusted server.

We present an efficient secure computation of a differentially private median of the union of two large, confidential data sets. Our protocol has a runtime sublinear in the size of the data universe and utility like the central model without a trusted third party. We use dynamic programming with a static, i.e., data-independent, access pattern, achieving low complexity of the secure computation circuit. We provide a comprehensive evaluation with a large real-world data set with a practical runtime of less than 5 seconds for millions of records even with large network delay of 80ms.

View More Papers

SODA: A Generic Online Detection Framework for Smart Contracts

Ting Chen (University of Electronic Science and Technology of China), Rong Cao (University of Electronic Science and Technology of China),...

Read More

Poseidon: Mitigating Volumetric DDoS Attacks with Programmable Switches

Menghao Zhang (Tsinghua University), Guanyu Li (Tsinghua University), Shicheng Wang (Tsinghua University), Chang Liu (Tsinghua University), Ang Chen (Rice University),...

Read More

Finding Safety in Numbers with Secure Allegation Escrows

Venkat Arun (Massachusetts Institute of Technology), Aniket Kate (Purdue University), Deepak Garg (Max Planck Institute for Software Systems), Peter Druschel...

Read More

Withdrawing the BGP Re-Routing Curtain: Understanding the Security Impact...

Jared M. Smith (University of Tennessee, Knoxville), Kyle Birkeland (University of Tennessee, Knoxville), Tyler McDaniel (University of Tennessee, Knoxville), Max...

Read More