Distributed method improves privacy and speed in solving linear programs
DISTA-LP: Privacy-Preserving Distributed Linear Programming for Metric Differential Privacy
Cryptography and Security
Summary
Ensuring privacy while solving complex math problems called linear programs can be tricky, especially when data is shared between many users and a central computer. The authors developed a system called DISTA-LP that protects user privacy by sharing only summarized, noisy data instead of detailed personal information. Their method makes these problems faster to solve and keeps users’ information safer. Tests on large city road data show their approach works well without losing accuracy.
What this means in practice
- •For urban traffic planners: Use scalable privacy-preserving optimization on road network data to improve traffic models without exposing sensitive location information.
- •For cloud data service providers: Provide privacy-enhanced distributed linear programming services that reduce data leakage risk in client computations involving sensitive metrics.$Commercial implications: Enables building and selling privacy-focused optimization platforms protecting client data during distributed computations.
Authors
Michael Oluwole, Ruiyao Liu, Aleksander Stevens, Chenxi Qiu
Abstract
Linear-programming (LP) mechanisms for metric differential privacy (mDP) enable fine-grained, task-aware utility control, but they are computationally expensive and become privacy-fragile in distributed settings: uploading user-specific LP coefficient matrices (e.g., distance and loss blocks) to a central solver can itself leak sensitive information. We present DISTA-LP, a privacy-preserving distributed mDP optimization framework that replaces raw coefficient uploads with compact surrogate parameterizations and releases only calibrated, perturbed parameter vectors, thereby reducing both upload-stage leakage and problem dimensionality. On the server side, DISTA-LP reconstructs approximate coefficients and solves a scalable mastersubproblem formulation via Benders decomposition. To certify end-to-end privacy, we introduce a probabilistic mDP (PmDP) auditor that empirically quantifies the privacy loss induced by parameter release, allocates the required privacy budget prior to optimization, and composes it with the downstream mechanism to obtain an end-to-end mDP guarantee. Experiments on large realworld road-network datasets (Rome, New York City, and London) show that DISTA-LP achieves near-zero mDP violation rates, substantially reduces computation time compared to monolithic and hybrid baselines, and matches or improves utility, thereby demonstrating stronger upload privacy and significantly improved scalability.