Abstract
Executing graph optimization algorithms such as the Minimum Mean Cycle (MMC) while preserving privacy has significant potential for handling sensitive information between users and companies. For example, it enables multilateral netting to solve the Minimum Cost Flow (MCF) problem [4] without disclosing mutual debts, making it highly relevant for processes like netting among multinational corporations. Aly et. al. [2] proposed an algorithm using Multi-Party Computation (MPC) to execute the MMC problem. However, this approach is based on Karp's algorithm [1], which was found by Chaturvedi et al . [3] to occasionally fail to detect cycles. In this study, we propose a revised protocol that corrects this issue and enhances its efficiency. We implemented our protocol using MP-SPDZ and confirmed that it correctly identifies the MMC, similar to traditional protocols. Our findings indicate that our proposed protocol operates correctly and more efficiently than Aly's protocol, which reduces the time/round complexity from $O(|V|^5)$ to $O(|V|^3)$ and the space complexity from $O(|V|^4)$ to $O(|V|^2)$. Furthermore, we discuss potential improvements for even more efficient algorithms.
Graph theory optimization problems play a crucial role in various domains, from computer science and engineering to economics and finance. These problems involve finding the most efficient way to navigate, connect, or utilize network structures, and solutions to these problems have far-reaching implications for improving systems and processes.
One of the representative problems in graph theory optimization is the Minimum Cost Flow (MCF) problem, which aims to find the least costly way to send a certain amount of flow through a network. The MCF problem is foundational in numerous applications, providing critical insights and optimizations.
In the financial sector, particularly in Netting, the Minimum Cost Flow (MCF) problem is often addressed to optimize the settlement of transactions and reduce systemic risk [4]. Netting involves aggregating multiple financial obligations to streamline transactions, minimize risk, and enhance efficiency. However, one of the critical challenges in this context is maintaining the privacy and confidentiality of sensitive financial data. Traditional methods for solving the MCF problem may require exposing transaction details, leading to significant privacy concerns and potential security risks.
Beyond netting, the MMC problem and its solutions have a wide array of applications across various fields:
The Minimum Mean Cycle (MMC) problem is a crucial component in solving the MCF problem. The MMC problem focuses on identifying cycles in directed graphs with the minimum average weight, which is essential for detecting inefficient paths and optimizing network performance. By incorporating the MMC problem into the solution of the MCF problem, we can achieve more accurate and efficient outcomes.
To address the privacy concerns inherent in solving the MCF problem, we explore the use of Multi-Party Computation (MPC) to securely solve the MMC problem. MPC is a cryptographic approach that allows multiple parties to collaboratively compute a function over their inputs while keeping those inputs private. By applying MPC techniques, we can solve the MMC problem without exposing sensitive data, thus preserving the privacy of financial transactions and other confidential information.
Aly et al. [2] proposed a method to solve Karp's MMC algorithm [1] using Multi-Party Computation. However, this approach has some problems and suffers from significant computational complexity and time consumption. Additionally, the Karp's algorithm [1] was found by Chaturvedi et al . [3] to occasionally fail to detect cycles.
in this study, we propose a novel approach that not only addresses these shortcomings but also offers a more efficient and practical solution for securely solving the MMC problem using MPC. Our proposed protocol aims to reduce computational and time complexities, enhance cycle detection accuracy, and ensure robust privacy protection. Our experimental results demonstrate a significant improvement in efficiency, with a reduction in time complexity from $O(|V|^5)$ to $O(|V|^3)$ and space complexity from $O(|V|^4)$ to $O(|V|^2)$.
Minimum Mean Cycle Problem and its solution is defined by Karp in 1978 [1].