title: Advancing MPC: From Real-World Applications to LUT-Based Protocols
Creators: name: Yalame, Hossein
Publisher: name: UNSPECIFIED
Year: 2024

description: Secure multi-party computation (MPC) is a cryptographic protocol that allows multiple parties to collaboratively compute a public function using their private inputs, ensuring the confidentiality of these inputs while revealing only the final output. This technology is crucial in a variety of fields, including privacy preserving machine learning (PPML) and the emerging field of federated learning (FL). However, the current approaches for MPC incur significant communication and computational overhead, leading to increased communication and runtime costs in comparison to non-private counterparts.

This thesis explores the feasibility and potential improvements of MPC for real-world applications, focusing on two critical aspects:

1) This work demonstrates how MPC provides feasible privacy-preserving solutions in practical applications.

2) It identifies new methods that significantly improve the computational and communication efficiency of MPC.

Practical Privacy-Preserving Services Many machine learning (ML) services depend on training data that contains sensitive information from various sources. MPC in PPML allows multiple parties to collaboratively work on their shared data without revealing their individual inputs to each other.

Building on existing practical privacy-preserving services, our research explores the efficiency of such services by focusing on clustering—an important unsupervised ML technique for grouping data. Our comprehensive review and analysis of 59 studies dedicated to privacy-preserving clustering reveal information leakage in the majority of these studies (49 out of 59). We implement and evaluate four efficient and fully private protocols: Cheon et al. (SAC’19), Mohassel et al. (PETS’20), Meng et al. (CCSW’21), and Bozdemir et al. (ASIACCS’21), with each protocol enhancing the privacy of a different clustering algorithm. Additionally, we conduct benchmarks of these protocols to evaluate their clustering quality, communication efficiency, and computational overhead, thus providing a detailed comparison of their effectiveness.

Expanding upon our exploration of privacy-preserving clustering, our research extends to FL, a distributed ML method that inherently protects data privacy by allowing clients to jointly train a global model through an aggregator without exposing their training data. FL not only improves privacy but also benefits from the computational power and data of potentially millions of clients concurrently. However, FL is vulnerable to poisoning attacks from malicious clients introducing false data, and to inference attacks by malicious aggregator(s) who can deduce information about clients’ data from their models. To address these issues, our research involves a critical analysis and identification of vulnerabilities in the only existing solution (Liu et al., IEEE TIFS’21) that addresses both poisoning attacks and inference attacks simultaneously, leading to the introduction of FLAME. FLAME is designed to protect against both poisoning and inference attacks. Through our extensive evaluations across various ML applications and datasets, FLAME effectively prevents poisoning attacks without compromising the accuracy of the model. Moreover, we develop, implement, and benchmark specialized two-party computation (2PC) protocols within FLAME, ensuring the privacy of client training data and protection against inference attacks on their models.

This part of the thesis is based on the following three publications:

[HMSY21] A. HEGDE, H. MÖLLERING, T. SCHNEIDER, H. YALAME. “SoK: Efficient Privacy-Preserving Clustering”. In: Proceedings on Privacy Enhancing Technologies (PETs) 2021.4 (2021). 
Online: https://ia.cr/2021/809. Code: https://encrypto.de/code/SoK_ppClustering, pp. 225–248. CORE Rank A. Appendix A.

[NRC+22] T. D. NGUYEN, P. RIEGER, H. CHEN, H. YALAME, H. MÖLLERING, H. FEREIDOONI, S. MARCHAL, M. MIETTINEN, A. MIRHOSEINI, S. ZEITOUNI, F. KOUSHANFAR, A.- R. SADEGHI, T. SCHNEIDER. “FLAME: Taming Backdoors in Federated Learning”. In: USENIX Security Symposium (USENIX Security). Online: https://ia.cr/2021/025. USENIX Association, 2022, pp. 1415–1432. CORE Rank A*. Appendix B.

[SSY23] T. SCHNEIDER, A. SURESH, H. YALAME. “Comments on “Privacy-Enhanced Federated Learning Against Poisoning Adversaries””. In: IEEE Transactions on Information Forensics and Security (TIFS) 18 (2023), pp. 1407–1409. CORE Rank A. Appendix C.

MPC Protocols &amp; Optimizations Generic MPC protocols efficiently evaluate Boolean or arithmetic circuits using two main approaches: 1) low-latency, utilizing the garbled circuit (GC) protocol for constant-round solutions, and 2) high-throughput, employing the Goldreich-Micali-Wigderson (GMW) protocol to minimize communication and improve parallelization. A notable feature of these protocols is their division into two phases: an input-independent setup phase that allows for pre-computing expensive cryptographic primitives such as oblivious transfer (OT), resulting in an extremely fast online phase once inputs are available.

The challenge with GC-based protocols lies in the computational overhead of cryptographic operations, like advanced encryption standard (AES), during the online phase. For instance, the most efficient scheme today requires computing 9 fixed-key AES operations for each AND gate (Rosulek and Roy, CRYPTO’21). While GMW-based protocols avoid cryptographic operations in the online phase, they are impeded by the communication rounds needed, which depend on the depth of the circuit being evaluated.

To improve the efficiency of GC-based protocols, we explore the use of vector AES (VAES), a recent innovation by Intel that enables the parallel computation of multiple AES operations. Our aim is to utilize these cutting-edge hardware capabilities to optimize GC-based protocols for practical applications.

For the GMW-based protocols, we aim to achieve practical efficiency through function-dependent pre-processing, which yields substantial improvements by using knowledge of the underlying function to be evaluated. This approach is particularly beneficial in contexts like machine learning as a service (MLaaS), where a single function is repeatedly evaluated with different inputs. Our developments, ABY2.0 and FLUTE, improve the online communication efficiency of the GMW protocol in a two party setting. We also design efficient protocols for the secure evaluation of multi-input AND gates and look-up tables (LUTs), alongside novel constructions based on LUTs to enhance private function evaluation (PFE) efficiency. Moreover, we automatically generate circuits optimized for these protocols.

Another area of our research addresses the common MPC assumption of symmetric trust, which assumes that all parties are either semi-honest or malicious. However, this assumption may not align with the asymmetric nature of trust found in real-world scenarios, shaped by reputation, power dynamics, and incentives. To accommodate this, we extend our 2PC framework from ABY2.0 to an honest-majority three-party computation (3PC) setting, designed to handle scenarios where only one party is malicious while the other parties remain semi-honest. This extension considers cases where the malicious party acts as a helper in ABY2.0 or serves as the evaluating party in the 3PC setting.

This part of the thesis is based on the following five publications:

[MSY21] J. - P. MÜNCH, T. SCHNEIDER, H. YALAME. “VASA: Vector AES Instructions for Security Applications”. In: Annual Computer Security Applications Conference (ACSAC). Online: https://ia.cr/2021/1493. Code: https://encrypto.de/code/VASA. ACM, 2021, pp. 131–145. CORE Rank A. Appendix D.

[PSSY21] A. PATRA, T. SCHNEIDER, A. SURESH, H. YALAME. “ABY2.0: Improved Mixed-Protocol Secure Two-Party Computation”. In: USENIX Security Symposium (USENIX Security). Online: https://ia.cr/2020/1225. USENIX Association, 2021, pp. 2165–2182. CORE Rank A*. Appendix E.

[BHS+23] A. BRÜGGEMANN, R. HUNDT, T. SCHNEIDER, A. SURESH, H. YALAME. “FLUTE: Fast and Secure Lookup Table Evaluations”. In: IEEE Symposium on Security and Privacy (IEEES&amp;P). Online: https://ia.cr/2023/499. Code: https://encrypto.de/code/FLUTE. IEEE, 2023, pp. 515–533. CORE Rank A*. Appendix F.

[DGS+23] Y. DISSER, D. GÜNTHER, T. SCHNEIDER, M. STILLGER, A. WIGANDT, H. YALAME. “Breaking the Size Barrier: Universal Circuits meet Lookup Tables”. In: International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT). Vol. 14438. LNCS. Online: https://ia.cr/2021/809. Code: https://encrypto.de/code/LUC. Springer, 2023, pp. 3–37. CORE Rank A. Appendix G.

[BSS+24] A. BRÜGGEMANN, O. SCHICK, T. SCHNEIDER, A. SURESH, H. YALAME. “Don’t Eject the Impostor: Fast Three-Party Computation with A Known Cheater.” In: IEEE Symposium on Security and Privacy (IEEE S&amp;P). Online: https://ia.cr/2023/1744. Code: https://encrypto.de/code/MOTION-FD. IEEE, 2024. CORE Rank A*. Appendix H.

This thesis is dedicated to advancing the practical application of MPC in real-world scenarios. It focuses on optimizing low-level building blocks and developing efficient privacy-preserving solutions that are specifically designed for practical use cases.