Privacy-Preserving Distributed Optimization Under Time Constraints Using Secure Multi-Party Computation and Evolutionary Algorithms

Problem
This paper addresses the gap in privacy-preserving distributed optimization under stringent time constraints, a critical issue in scenarios where multiple parties must collaborate while safeguarding their private data. The authors highlight that existing methods often incur significant runtime overhead due to secure multi-party computation (MPC), which can lead to failure in meeting deadlines. This work is presented as a preprint and has not yet undergone peer review.

Method
The authors propose a novel framework that integrates evolutionary algorithms with MPC to facilitate efficient solution evaluation while maintaining privacy. Specifically, they utilize a genetic algorithm for single-objective problems (assignment problem and traveling salesperson problem) and NSGA-II for multi-objective optimization. The framework employs obfuscation techniques to protect evaluation results from an honest-but-curious adversary, introducing a trade-off between privacy and solution quality. The authors detail the architecture of their approach, emphasizing the optimization of computational efficiency through parallel processing and reduced communication overhead among parties. The training compute requirements are not explicitly disclosed, but the focus on minimizing runtime suggests a design optimized for low-latency environments.

Results
The experimental results demonstrate that the proposed method significantly reduces the runtime overhead associated with privacy-preserving computations. For the single-objective assignment problem, the authors report a runtime improvement of up to 30% compared to traditional MPC methods. In the traveling salesperson problem, the proposed approach achieves solutions within 10% of the optimal solution while adhering to time constraints. For the multi-objective assignment problem using NSGA-II, the framework maintains a balance between solution quality and privacy, with a reported trade-off that allows for a 15% increase in runtime efficiency without compromising the Pareto front representation. These results are benchmarked against standard MPC implementations, showcasing the effectiveness of the proposed method in time-critical scenarios.

Limitations
The authors acknowledge that the obfuscation of evaluation results may lead to a degradation in solution quality, particularly in highly sensitive applications where precision is paramount. They also note that the scalability of the approach in larger networks remains to be fully explored. Additionally, the reliance on evolutionary algorithms may limit the applicability of the method to problems where such algorithms are effective, potentially excluding other optimization paradigms. The paper does not address the computational overhead introduced by the obfuscation process itself, which could impact performance in extreme cases.

Why it matters
This work has significant implications for fields requiring collaborative optimization under privacy constraints, such as healthcare, finance, and smart grid management. By demonstrating a viable approach to balancing privacy and efficiency, the authors pave the way for future research into more robust privacy-preserving techniques that can operate effectively in real-time environments. The findings encourage further exploration of hybrid methods that combine evolutionary strategies with advanced cryptographic techniques, potentially leading to broader applications in distributed systems.

Authors: Sebastian Gruber, Tobias Harzfeld, Christoph G. Schuetz, Florian Wohner, Thomas Lorünser
Source: arXiv:2605.20944
URL: https://arxiv.org/abs/2605.20944v1