A Comprehensive Review of Graph-Theoretic Approaches to Secure Multiparty Computation: Security Models, Optimization Techniques, and Emerging Computing Applications

Abstract

Secure Multiparty Computation (MPC) is a foundational cryptographic paradigm that enables multiple parties to collaboratively compute a function over their private inputs without revealing sensitive data. Graph-theoretic approaches have recently emerged as powerful tools for modelling communication structures, optimizing protocol efficiency, and analyzing security properties in MPC systems. This review examines advancements from 2018 to 2023 in graph-theoretic MPC, focusing on security models, optimization strategies, and emerging applications. Graph structures are central to MPC, as they define communication topology, adversarial resilience, and protocol scalability. Research shows that communication graphs, expander graphs, and network topology models significantly influence the feasibility and efficiency of MPC protocols. Additionally, graph-based formulations enable secure computation of graph problems such as intersection, union, and edit distance under both semi-honest and malicious adversarial models. Modern MPC systems integrate graph theory with cryptographic primitives such as secret sharing, homomorphic encryption, and zero-knowledge proofs. These approaches enhance privacy preservation, reduce communication complexity, and improve scalability in distributed systems. Applications span machine learning, secure data analytics, blockchain, and distributed optimization. Despite significant progress, challenges remain in balancing security guarantees with computational efficiency, especially in large-scale and dynamic networks. This review synthesizes current methodologies, highlights key trends, and identifies future research directions, including adaptive graph-based protocols, quantum-resistant MPC, and AI-driven optimization.