pith. sign in

arxiv: 2605.20944 · v1 · pith:H6NNXXTBnew · submitted 2026-05-20 · 💻 cs.NE · cs.CR

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

Sebastian Gruber , Tobias Harzfeld , Christoph G. Schuetz , Florian Wohner , Thomas Lor\"unser This is my paper

Pith reviewed 2026-05-21 02:09 UTC · model grok-4.3

classification 💻 cs.NE cs.CR
keywords privacy-preserving optimizationsecure multi-party computationevolutionary algorithmstime constraintsdistributed optimizationgenetic algorithmassignment problemtraveling salesperson problem
0
0 comments X

The pith

Evolutionary algorithms combined with secure multi-party computation allow privacy-preserving optimization to finish within strict deadlines.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper demonstrates a method for multiple parties to jointly optimize a problem while keeping their private data hidden, even when a hard time limit applies. It uses evolutionary algorithms to generate candidate solutions and applies secure multi-party computation only to evaluate the quality of those candidates. This selective use of the slower privacy mechanism keeps total runtime low enough to meet the deadline. The authors also explore adding noise to evaluation results to further shield inputs from an honest-but-curious provider, and they measure the resulting quality trade-off on assignment and traveling-salesperson instances.

Core claim

By restricting expensive MPC operations to a small number of fitness evaluations inside an evolutionary search loop, the combined method reduces privacy-related runtime overhead enough that a solution can still be returned before the given time bound expires. Obfuscation of the evaluation outcomes provides extra input protection at the cost of some solution quality.

What carries the argument

A hybrid loop that runs evolutionary search to propose candidates and invokes MPC only for their fitness evaluation, with optional result obfuscation.

If this is right

  • Time-critical privacy-preserving optimization becomes feasible for assignment and traveling-salesperson problems using genetic algorithms or NSGA-II.
  • The number of secure evaluations can be controlled by population size and generation count to respect the time bound.
  • Obfuscation strength can be tuned to trade input protection against solution quality in both single- and multi-objective cases.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same selective-MPC pattern could be tested on other evolutionary or swarm methods that already keep evaluation budgets low.
  • In practice the approach would require an early-stopping rule that aborts further MPC calls once the remaining time is insufficient.
  • Extending the method to dynamic or streaming problems would need a way to reuse prior MPC results across changing time windows.

Load-bearing premise

The evolutionary algorithm needs so few MPC fitness evaluations that the total time, including communication and any obfuscation, still stays inside the deadline.

What would settle it

A run on a concrete problem instance and deadline where the measured wall-clock time for the required MPC evaluations plus overhead exceeds the allowed limit.

Figures

Figures reproduced from arXiv: 2605.20944 by Christoph G. Schuetz, Florian Wohner, Sebastian Gruber, Thomas Lor\"unser, Tobias Harzfeld.

Figure 1
Figure 1. Figure 1: Architecture for privacy-preserving distributed optimization under time constraints [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Median of fitness means per generation and mean fitness of 31 individual runs over 500 generations [PITH_FULL_IMAGE:figures/full_fig_p017_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Median of fitness means per generation and mean fitness of 31 individual runs over 500 generations [PITH_FULL_IMAGE:figures/full_fig_p019_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Median GD+ per generation and GD+ of 31 individual runs over 500 generations for each obfuscation configuration on Instance ap2K100x100 with one objective obfuscated. 0 15 30 45 60 Distance ×10 3 No Obfuscation 20 Buckets 10 Buckets 05 Buckets Above 95 % Above 90 % Above 80 % 0 1 2 3 4 5 Generation ×10 2 0 15 30 45 60 Distance ×10 3 Order 0 1 2 3 4 5 Generation ×10 2 20 Quantiles 0 1 2 3 4 5 Generation ×10… view at source ↗
Figure 5
Figure 5. Figure 5: Median IGD+ per generation and IGD+ of 31 individual runs over 500 generations for each obfuscation configuration on Instance ap2K100x100 with one objective obfuscated. to improve, i.e., decrease, when the number of buckets, quantiles, or top individuals is increased. The results for above threshold obfuscation indicate no trend based on the median IGD+ . In contrast to the results for the AP and TSP insta… view at source ↗
Figure 6
Figure 6. Figure 6: Set of estimated non-dominated solution sets of Generation 500 from the run with the median IGD [PITH_FULL_IMAGE:figures/full_fig_p022_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: Median GD+ per generation and GD+ of 31 individual runs over 500 generations for each obfuscation configuration on Instance ap2K100x100 with two objectives obfuscated. considerable with 𝐴90 and substantial with 𝐴95. Individual runs with the remaining obfuscation configurations closely follow the median curve, indicating low variability across runs [PITH_FULL_IMAGE:figures/full_fig_p024_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: Median IGD+ per generation and IGD+ of 31 individual runs over 500 generations for each obfuscation configuration on Instance ap2K100x100 with two objectives obfuscated [PITH_FULL_IMAGE:figures/full_fig_p025_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: Set of estimated non-dominated solution sets of Generation 500 from the run with the median IGD [PITH_FULL_IMAGE:figures/full_fig_p026_9.png] view at source ↗
read the original abstract

In distributed optimization, multiple parties collaborate to find an optimal solution to a problem. Privacy-preserving distributed optimization uses techniques, such as secure multi-party computation (MPC), to protect the private inputs of each party. In time-critical settings, the runtime overhead introduced by privacy-preserving computations may prevent the optimization from finishing within the deadline. This paper presents an approach for privacy-preserving distributed optimization in time-critical settings that combines evolutionary algorithms for solution search and MPC for the evaluation of solutions. The approach reduces the impact of privacy-preserving computations on runtime and allows to return solution within the deadline. Obfuscation of evaluation results provides additional protection for private inputs from an honest-but-curious platform provider, but introduces a potential trade-off between protection and solution quality. This trade-off is investigated in experiments using a genetic algorithm for both the single-objective assignment problem and the traveling salesperson problem, as well as NSGA-II for the multi-objective assignment problem.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The manuscript proposes combining evolutionary algorithms (genetic algorithms and NSGA-II) with secure multi-party computation (MPC) for fitness evaluation to perform privacy-preserving distributed optimization under hard time deadlines. The core idea is that selective use of MPC plus result obfuscation reduces privacy overhead enough to meet deadlines on assignment and TSP instances, while the obfuscation introduces an explicit quality-protection trade-off that is examined empirically.

Significance. If the reported timing results on small instances hold under the stated conditions, the work supplies a practical engineering bridge between evolutionary search and MPC that addresses a real deployment constraint (hard deadlines) not typically handled by either field alone. The explicit treatment of the obfuscation trade-off and the use of both single- and multi-objective EAs are positive features.

major comments (2)
  1. [Experiments] Experiments section: the central claim that the method 'reduces the impact of privacy-preserving computations on runtime and allows to return solution within the deadline' is supported only by observed timing on small assignment and TSP instances; no analytical bound or worst-case argument is given showing that the number of MPC evaluations stays inside the deadline once communication and obfuscation costs are included for larger problem sizes.
  2. [Approach / Experiments] The manuscript treats the number of generations and per-evaluation MPC cost as observed quantities rather than deriving or bounding them; this makes the 'fits inside the deadline' claim instance-specific and limits the strength of the general contribution.
minor comments (2)
  1. [Abstract] The abstract states that 'a quality-protection trade-off was observed' yet supplies no quantitative metrics, error bars, or baseline comparisons; these should be added to the abstract or a summary table for clarity.
  2. [Approach] Notation for the obfuscation parameter and its effect on solution quality should be introduced once and used consistently across the approach and experimental sections.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the constructive comments and the recommendation of minor revision. We address each major comment below.

read point-by-point responses

  1. Referee: [Experiments] Experiments section: the central claim that the method 'reduces the impact of privacy-preserving computations on runtime and allows to return solution within the deadline' is supported only by observed timing on small assignment and TSP instances; no analytical bound or worst-case argument is given showing that the number of MPC evaluations stays inside the deadline once communication and obfuscation costs are included for larger problem sizes.

    Authors: We agree that the reported results are based on timing observations for small instances and that no analytical bounds or worst-case arguments are provided for larger sizes that incorporate communication and obfuscation overhead. The manuscript positions the work as a practical engineering approach demonstrated empirically on the tested problems rather than a theoretical guarantee. In revision we will add a dedicated limitations paragraph in the Discussion section that explicitly notes the instance-specific nature of the timing results and the lack of scalability bounds. revision: yes

  2. Referee: [Approach / Experiments] The manuscript treats the number of generations and per-evaluation MPC cost as observed quantities rather than deriving or bounding them; this makes the 'fits inside the deadline' claim instance-specific and limits the strength of the general contribution.

    Authors: The number of generations is governed by the evolutionary algorithm's convergence behavior and stopping criteria as observed in the experiments, while per-evaluation MPC costs are measured from the concrete implementation. We do not derive closed-form bounds because the contribution centers on a deployable combination that meets deadlines under realistic time constraints rather than on asymptotic analysis. We will revise the text to state the empirical basis more clearly and to qualify the generalizability of the deadline-satisfaction claim. revision: yes

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper describes an engineering approach that combines evolutionary algorithms (GA and NSGA-II) with MPC-based fitness evaluation and result obfuscation to meet time deadlines in privacy-preserving distributed optimization. All performance claims rest on empirical timing measurements from concrete experiments on small assignment and TSP instances; no mathematical derivation chain, fitted parameters presented as predictions, or self-citation load-bearing steps appear in the manuscript. The central argument is therefore self-contained against external benchmarks and does not reduce to its own inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Review performed on abstract only; no explicit free parameters, axioms, or invented entities are stated in the provided text.

pith-pipeline@v0.9.0 · 5704 in / 1084 out tokens · 26363 ms · 2026-05-21T02:09:07.010508+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

26 extracted references · 26 canonical work pages

  1. [1]

    Akiba, S

    Optuna: A Next-generation Hyperparameter Optimization Framework. InProceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining(Anchorage, AK, USA)(KDD ’19). Association for Computing Machinery, New York, NY, USA, 2623–2631. doi:10.1145/3292500.3330701 Toshinori Araki, Jun Furukawa, Yehuda Lindell, Ariel Nof, and Kazuma Ohara

    work page doi:10.1145/3292500.3330701

  2. [2]

    High-Throughput Semi-Honest Secure Three-Party Computation with an Honest Majority. InProceedings of the 2016 ACM SIGSAC Conference on Computer Privacy-Preserving Distributed Optimization Using MPC and Evolutionary Algorithms 29 and Communications Security(Vienna, Austria)(CCS ’16). Association for Computing Machinery, New York, NY, USA, 805–817. doi:10.1...

    work page doi:10.1145/2976749.2978331 2016

  3. [3]

    A fast and elitist multiobjective genetic algorithm: NSGA-II.IEEE Trans. Evol. Comput.6, 2 (2002), 182–197. doi:10.1109/4235.996017 Matthias Ehrgott. 2005.Multicriteria optimization(2 ed.). Springer. doi:10.1007/3-540-27659-9 A. E. Eiben and J. E. Smith. 2015.Representation, Mutation, and Recombination. Springer Berlin Heidelberg, Berlin, Heidelberg, 49–7...

    work page doi:10.1109/4235.996017 2002

  4. [4]

    InParallel Problem Solving from Nature, PPSN XI, Robert Schaefer, Carlos Cotta, Joanna Kołodziej, and Günter Rudolph (Eds.)

    Privacy-Preserving Multi-Objective Evolutionary Algorithms. InParallel Problem Solving from Nature, PPSN XI, Robert Schaefer, Carlos Cotta, Joanna Kołodziej, and Günter Rudolph (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 41–50. doi:10.1007/978-3-642-15871-1_5 Sebastian Gruber, Paul Feichtenschlager, and Christoph G. Schuetz

    work page doi:10.1007/978-3-642-15871-1_5

  5. [5]

    InProceedings of the Genetic and Evolutionary Computation Conference(Melbourne, VIC, Australia)(GECCO ’24)

    Using Genetic Algorithms for Privacy-Preserving Optimization of Multi-Objective Assignment Problems in Time-Critical Settings: An Application in Air Traffic Flow Management. InProceedings of the Genetic and Evolutionary Computation Conference(Melbourne, VIC, Australia)(GECCO ’24). Association for Computing Machinery, New York, NY, USA, 1246–1254. doi:10.1...

    work page doi:10.1145/3638529.3654128

  6. [6]

    InData Warehousing and Knowledge Discovery, Il Yeal Song, Johann Eder, and Tho Manh Nguyen (Eds.)

    Privacy-Preserving Genetic Algorithms for Rule Discovery. InData Warehousing and Knowledge Discovery, Il Yeal Song, Johann Eder, and Tho Manh Nguyen (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 407–417. doi:10.1007/978-3-540-74553-2_38 Hisao Ishibuchi, Hiroyuki Masuda, Yuki Tanigaki, and Yusuke Nojima

    work page doi:10.1007/978-3-540-74553-2_38

  7. [7]

    J., 2022, in Bambi C., Santangelo A., eds, , Handbook of X-ray and Gamma-ray Astrophysics

    Modified Distance Calculation in Generational Distance and Inverted Generational Distance. InEvolutionary Multi-Criterion Optimization, António Gaspar-Cunha, Carlos Henggeler Antunes, and Carlos Coello Coello (Eds.). Springer International Publishing, Cham, 110–125. doi:10.1007/978- 3-319-15892-1_8 Leqi Jiang and Zhangjie Fu

    work page doi:10.1007/978-

  8. [8]

    Privacy-preserving genetic algorithm outsourcing in cloud computing.Journal of Cybersecurity2, 1 (2020),

    work page 2020

  9. [9]

    In: Proceedings of the 2020 ACM SIGSAC Conference on Computer and Commu- nications Security

    MP-SPDZ: A Versatile Framework for Multi-Party Computation. InProceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security(Virtual Event, USA)(CCS ’20). Association for Computing Machinery, New York, NY, USA, 1575–1590. doi:10.1145/3372297.3417872 Dave S. Kerby

    work page doi:10.1145/3372297.3417872 2020

  10. [10]

    doi:10.2466/11.IT.3.1 Rudolf Kruse, Sanaz Mostaghim, Christian Borgelt, Christian Braune, and Matthias Steinbrecher

    The Simple Difference Formula: An Approach to Teaching Nonparametric Correlation1.Comprehensive Psychology3 (2014), 11.IT.3.1. doi:10.2466/11.IT.3.1 Rudolf Kruse, Sanaz Mostaghim, Christian Borgelt, Christian Braune, and Matthias Steinbrecher. 2022.Elements of Evolu- tionary Algorithms. Springer International Publishing, Cham, 255–285. doi:10.1007/978-3-0...

    work page doi:10.2466/11.it.3.1 2014

  11. [11]

    A Secure Federated Data-Driven Evolutionary Multi-Objective Optimization Algorithm.IEEE Trans. Emerg. Top. Comput. Intell.8, 1 (2024), 191–205. doi:10.1109/TETCI.2023.3313555 Manuel López-Ibáñez, Jürgen Branke, and Luís Paquete

    work page doi:10.1109/tetci.2023.3313555 2024

  12. [12]

    Reproducibility in Evolutionary Computation.ACM Trans. Evol. Learn. Optim.1, 4 (2021), 14:1–14:21. doi:10.1145/3466624 Thomas Loruenser, Florian Wohner, and Stephan Krenn

    work page doi:10.1145/3466624 2021

  13. [13]

    InProceedings of the 2022 on Cloud Computing Security Workshop(Los Angeles, CA, USA)(CCSW’22)

    A Verifiable Multiparty Computation Solver for the Linear Assignment Problem: And Applications to Air Traffic Management. InProceedings of the 2022 on Cloud Computing Security Workshop(Los Angeles, CA, USA)(CCSW’22). Association for Computing Machinery, New York, NY, USA, 41–51. doi:10.1145/3560810.3564263 Yang Lu and Minghui Zhu

    work page doi:10.1145/3560810.3564263 2022

  14. [14]

    doi:10.1016/j.automatica.2018.07.005 Tulika Mitra, Jürgen Teich, and Lothar Thiele

    Privacy preserving distributed optimization using homomorphic encryption.Automatica 96 (2018), 314–325. doi:10.1016/j.automatica.2018.07.005 Tulika Mitra, Jürgen Teich, and Lothar Thiele

    work page doi:10.1016/j.automatica.2018.07.005 2018

  15. [15]

    doi:10.1109/MDAT.2018.2794204 Nadine Pilon, Laurent Guichard, Zoltan Bazso, Giuseppe Murgese, and Marie Carré

    Time-Critical Systems Design: A Survey.IEEE Design & Test35, 2 (2018), 8–26. doi:10.1109/MDAT.2018.2794204 Nadine Pilon, Laurent Guichard, Zoltan Bazso, Giuseppe Murgese, and Marie Carré

    work page doi:10.1109/mdat.2018.2794204 2018

  16. [16]

    doi:10.1016/j.jairtraman.2021.102124 Gerhard Reinelt

    User-Driven Prioritisation Process (UDPP) from advanced experimental to pre-operational validation environment.Journal of Air Transport Management97 (2021), 102124. doi:10.1016/j.jairtraman.2021.102124 Gerhard Reinelt

    work page doi:10.1016/j.jairtraman.2021.102124 2021

  17. [17]

    Jun Sakuma and Shigenobu Kobayashi

    TSPLIB—A traveling salesman problem library.ORSA journal on computing3, 4 (1991), 376–384. Jun Sakuma and Shigenobu Kobayashi

    work page 1991

  18. [18]

    In Proceedings of the 9th Annual Conference on Genetic and Evolutionary Computation(London, England)(GECCO ’07)

    A genetic algorithm for privacy preserving combinatorial optimization. In Proceedings of the 9th Annual Conference on Genetic and Evolutionary Computation(London, England)(GECCO ’07). Association for Computing Machinery, New York, NY, USA, 1372–1379. doi:10.1145/1276958.1277214 30 Gruber et al. Christoph G. Schuetz, Thomas Lorünser, Samuel Jaburek, Kevin ...

    work page doi:10.1145/1276958.1277214

  19. [19]

    InCooperative Information Systems, Mohamed Sellami, Paolo Ceravolo, Hajo A

    A Distributed Architecture for Privacy-Preserving Optimization Using Genetic Algorithms and Multi-party Computation. InCooperative Information Systems, Mohamed Sellami, Paolo Ceravolo, Hajo A. Reijers, Walid Gaaloul, and Hervé Panetto (Eds.). Springer International Publishing, Cham, 168–185. doi:10.1007/978-3-031-17834-4_10 Kevin Schuetz, Christoph G. Sch...

    work page doi:10.1007/978-3-031-17834-4_10

  20. [20]

    In2023 IEEE Congress on Evolutionary Computation (CEC)

    Privacy-Preserving Implementation of Local Search Algorithms for Collaboratively Solving Assignment Problems in Time-Critical Contexts. In2023 IEEE Congress on Evolutionary Computation (CEC). 1–10. doi:10.1109/CEC53210.2023.10253978 Zeneng She, Wenjian Luo, Yatong Chang, Zhen Song, and Yuhui Shi

    work page doi:10.1109/cec53210.2023.10253978 2023

  21. [21]

    InAdvances in Swarm Intelligence, Ying Tan, Yuhui Shi, and Wenjian Luo (Eds.)

    On the Privacy Issue of Evolutionary Biparty Multiobjective Optimization. InAdvances in Swarm Intelligence, Ying Tan, Yuhui Shi, and Wenjian Luo (Eds.). Springer Nature Switzerland, Cham, 371–382. doi:10.1007/978-3-031-36622-2_30 Kang G. Shin and Parameswaran Ramanathan

    work page doi:10.1007/978-3-031-36622-2_30

  22. [22]

    IEEE82, 1 (1994), 6–24

    Real-time computing: a new discipline of computer science and engineering.Proc. IEEE82, 1 (1994), 6–24. doi:10.1109/5.259423 Bing Sun, Jian-Yu Li, Xiao-Fang Liu, Qiang Yang, Zhi-Hui Zhan, and Jun Zhang

    work page doi:10.1109/5.259423 1994

  23. [23]

    InWeb Information Systems Engineering – WISE 2023, Feng Zhang, Hua Wang, Mahmoud Barhamgi, Lu Chen, and Rui Zhou (Eds.)

    A Privacy-Preserving Evolutionary Computation Framework for Feature Selection. InWeb Information Systems Engineering – WISE 2023, Feng Zhang, Hua Wang, Mahmoud Barhamgi, Lu Chen, and Rui Zhou (Eds.). Springer Nature Singapore, Singapore, 260–274. doi:10.1007/ 978-981-99-7254-8_20 Florian Wohner and Thomas Loruenser. 2026.Privacy Engine. AIT Austrian Insti...

    work page 2023

  24. [24]

    A survey of distributed optimization.Annu. Rev. Control.47 (2019), 278–305. doi:10.1016/J.ARCONTROL. 2019.05.006 Xun Yi, Russell Paulet, and Elisa Bertino. 2014.Homomorphic Encryption and Applications. Springer. doi:10.1007/978-3-319- 12229-8 Zhi-Hui Zhan, Sheng-Hao Wu, and Jun Zhang

    work page doi:10.1016/j.arcontrol 2019

  25. [25]

    In2021 13th International Conference on Advanced Computational Intelligence (ICACI)

    A New Evolutionary Computation Framework for Privacy-Preserving Optimization. In2021 13th International Conference on Advanced Computational Intelligence (ICACI). 220–226. doi:10. 1109/ICACI52617.2021.9435860 Bowen Zhao, Wei-Neng Chen, Feng-Feng Wei, Ximeng Liu, Qingqi Pei, and Jun Zhang

    work page arXiv 2021

  26. [26]

    Cybern.54, 6 (2024), 3638–3651

    PEGA: A Privacy-Preserving Genetic Algorithm for Combinatorial Optimization.IEEE Trans. Cybern.54, 6 (2024), 3638–3651. doi:10.1109/TCYB.2023. 3346863

    work page doi:10.1109/tcyb.2023 2024