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

Bobtail: Improved Blockchain Security with Low-Variance Mining

George Bissias (University of Massachusetts Amherst), Brian N. Levine (University of Massachusetts Amherst)

Read More

HFL: Hybrid Fuzzing on the Linux Kernel

Kyungtae Kim (Purdue University), Dae R. Jeong (KAIST), Chung Hwan Kim (NEC Labs America), Yeongjin Jang (Oregon State University), Insik Shin (KAIST), Byoungyoung Lee (Seoul National University)

Read More

SVLAN: Secure & Scalable Network Virtualization

Jonghoon Kwon (ETH), Taeho Lee (ETH), Claude Hähni (ETH), Adrian Perrig (ETH)

Read More

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

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

Read More