MESA: Secure and Efficient Sample Alignment for Vertical Federated Learning

Abstract

Sample alignment performs a crucial role in vertical federated learning, aiming to identify shared user samples among multiple parties without exposing their private identifier data. However, most existing alignment protocols are designed for two-party scenarios, while those developed for multi-party settings suffer from limited anti-collusion capability and inefficient verification mechanisms. To address these issues, we propose an efficient and secure protocol for sample alignment in multi-party vertical federated learning (MESA). The protocol leverages a threshold oblivious pseudo-random function (T-OPRF) combined with a distributed key generation scheme to defend against collusion attacks. Moreover, an oblivious key–value store encoding (OKVS) mechanism is introduced to enable secure and efficient key–value mapping and decoding, thereby reducing communication overhead. Under the malicious security model, MESA further incorporates non-interactive zero-knowledge proof (NIZKP) to verify the consistency and validity of results submitted by clients, effectively preventing data forgery and disruption attacks. Experimental results and analysis demonstrate that MESA provides strong privacy guarantees while achieving high computation and communication efficiency in deployments involving multiple untrusted clients.