Secure Sublinear Time Differentially Private Median Computation

—In distributed private learning, e.g., data analysis, machine learning, and enterprise benchmarking, it is common-place 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 provide differential privacy for small data sets (sublinear in the size of the data universe) and prune large data sets with a relaxed notion of differential privacy providing limited group privacy. 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 over multiple AWS regions (from Ohio to N. Virgina, Canada and Frankfurt) with a large real-world data set with a practical runtime of less than 7 seconds for millions of records.