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

Compliance Cautions: Investigating Security Issues Associated with U.S. Digital-Security...

Rock Stevens (University of Maryland), Josiah Dykstra (Independent Security Researcher), Wendy Knox Everette (Leviathan Security Group), James Chapman (Independent Security Researcher), Garrett Bladow (Dragos), Alexander Farmer (Independent Security Researcher), Kevin Halliday (University of Maryland), Michelle L. Mazurek (University of Maryland)

Read More

Not All Coverage Measurements Are Equal: Fuzzing by Coverage...

Yanhao Wang (Institute of Software, Chinese Academy of Sciences), Xiangkun Jia (Pennsylvania State University), Yuwei Liu (Institute of Software, Chinese Academy of Sciences), Kyle Zeng (Arizona State University), Tiffany Bao (Arizona State University), Dinghao Wu (Pennsylvania State University), Purui Su (Institute of Software, Chinese Academy of Sciences)

Read More

Measuring the Deployment of Network Censorship Filters at Global...

Ram Sundara Raman (University of Michigan), Adrian Stoll (University of Michigan), Jakub Dalek (Citizen Lab, University of Toronto), Reethika Ramesh (University of Michigan), Will Scott (Independent), Roya Ensafi (University of Michigan)

Read More

On Using Application-Layer Middlebox Protocols for Peeking Behind NAT...

Teemu Rytilahti (Ruhr University Bochum), Thorsten Holz (Ruhr University Bochum)

Read More