TU Darmstadt

ULB

TUprints

Advancing MPC: From Real-World Applications to LUT-Based Protocols

Yalame, Hossein (2024)
Advancing MPC: From Real-World Applications to LUT-Based Protocols.
Technische Universität Darmstadt
doi: 10.26083/tuprints-00028168
Ph.D. Thesis, Primary publication, Publisher's Version

Text
Dissertation_HosseinYalame_100924.pdf
Copyright Information: In Copyright.
Download (14MB)

Item Type:

Ph.D. Thesis

Type of entry:

Primary publication

Title:

Advancing MPC: From Real-World Applications to LUT-Based Protocols

Language:

English

Referees:

Schneider, Prof. Dr. Thomas ; Patra, Prof. Dr. Arpita

Date:

15 October 2024

Place of Publication:

Darmstadt

Collation:

235 Seiten in verschiedenen Zählungen

Date of oral examination:

10 September 2024

DOI:

10.26083/tuprints-00028168

Abstract:

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 & 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&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&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.

Alternative Abstract:

Alternative Abstract

Language

Sichere Mehrparteienberechnung (im Englischen secure multi-party computation, MPC) ist ein kryptografisches Protokoll, das es mehreren Parteien ermöglicht, gemeinsam eine öffentliche Funktion unter Verwendung ihrer privaten Eingaben zu berechnen und dabei die Vertraulichkeit dieser Eingaben zu gewährleisten, während nur das Endergebnis offengelegt wird. Diese Technologie ist in einer Reihe von Bereichen von entscheidender Bedeutung, einschließlich des datenschutzfreundlichen maschinellen Lernens (im Englischen privacy preserving machine learning, PPML) und des aufkommenden Bereichs des föderierten Lernens (im Englischen federated learning, FL). Die derzeitigen Ansätze für MPC erfordern jedoch einen erheblichen Kommunikations- und Rechenaufwand, was zu erhöhten Kommunikations- und Laufzeitkosten im Vergleich zu nicht-privaten Gegenstücken führt.

In dieser Arbeit werden die Machbarkeit und das Verbesserungspotenzial von MPC für reale Anwendungen untersucht, wobei der Schwerpunkt auf zwei kritischen Aspekten liegt: 1) Diese Arbeit zeigt, wie MPC in praktischen Anwendungen praktikable Lösungen zur Wahrung der Privatsphäre bietet. 2) Sie zeigt neue Methoden auf, die die Rechen- und Kommunikationseffizienz der MPC deutlich verbessern.

Praktische Dienste zum Schutz der Privatsphäre Viele Dienste des maschinellen Lernens (ML) sind auf Trainingsdaten angewiesen, die sensible Informationen aus verschiedenen Quellen enthalten. MPC im PPML ermöglicht es mehreren Parteien, gemeinsam an ihren gemeinsamen Daten zu arbeiten, ohne ihre individuellen Eingaben einander preiszugeben. Basierend auf bestehenden praktischen Diensten zur Wahrung der Privatsphäre untersucht unsere Forschung die Effizienz solcher Dienste, indem sie sich auf das Clustering konzentriert – eine wichtige unüberwachte ML-Technik zur Gruppierung von Daten. Unsere umfassende Überprüfung und Analyse von 59 Arbeiten, die sich dem datenschutzbewahrenden Clustering widmen, zeigen Informationslecks in der Mehrheit dieser Arbeiten auf (49 von 59). Wir implementieren und bewerten vier effiziente und vollständig private Protokolle: Cheon et al. (SAC’19), Mohassel et al. (PETS’20), Meng et al. (CCSW’21) und Bozdemir et al. (ASIAC-CS’21), wobei jedes Protokoll die Privatsphäre bei einem anderen Clustering-Algorithmus verbessert. Zusätzlich führen wir Benchmarks dieser Protokolle durch, um ihre Clustering-Qualität, Kommunikationseffizienz und Rechenüberlast zu bewerten und so einen detaillierten Vergleich ihrer Wirksamkeit zu bieten.

Aufbauend auf unserer Untersuchung des datenschutzbewahrenden Clusterings, erweitert sich unsere Forschung auf FL, eine verteilte ML-Methode, die den Datenschutz inhärent gewährleistet. Kunden können durch einen Aggregator ein globales Modell trainieren, ohne ihre Trainingsdaten offenzulegen. FL verbessert nicht nur die Privatsphäre, sondern profitiert auch von der Rechenleistung und den Daten potenziell Millionen von Kunden gleichzeitig. Jedoch ist FL anfällig für Poisoning-Angriffe durch bösartige Kunden, die falsche Daten einführen, und für Inference-Angriffe durch bösartige Aggregatoren, die Informationen aus den Modellen der Kunden ableiten können. Um diese Probleme anzugehen, beinhaltet unsere Forschung eine kritische Analyse und Identifizierung von Schwachstellen in der einzigen bestehenden Lösung (Liu et al., IEEE TIFS’21), die sowohl Vergiftungsangriffe als auch Inferenzangriffe gleichzeitig behandelt, was zur Einführung von FLAME führt. FLAME ist darauf ausgelegt, sowohl gegen Poisoning- als auch Inference-Angriffe zu schützen. Durch unsere umfangreichen Bewertungen über verschiedene ML-Anwendungen und Datensätze hinweg verhindert FLAME effektiv Poisoning-Angriffe, ohne die Genauigkeit des Modells zu beeinträchtigen. Darüber hinaus entwickeln, implementieren und bewerten wir spezialisierte Protokolle zur Zwei-Parteien-Berechnung (im Englischen secure two-party computation, 2PC), die die Privatsphäre der Trainingsdaten der Kunden und den Schutz gegen Inference-Angriffe auf deren Modelle gewährleisten.

Dieser Teil der Arbeit basiert auf den folgenden drei Veröffentlichungen: [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, S. 225–248. CORE Rank A. Appendix A.

MPC-Protokolle & Optimierungen Generische MPC-Protokolle bewerten Boolesche oder arithmetische Schaltkreise unter Verwendung von zwei Hauptansätzen: 1) geringe Latenz, die das Garbled-Circuit-Protokoll (GC) für Lösungen mit konstanter Runde nutzt, und 2) hoher Durchsatz, der das Goldreich-Micali-Wigderson-Protokoll (GMW) verwendet, um die Kommunikation zu minimieren und die Parallelisierung zu verbessern. Ein wichtiges Merkmal dieser Protokolle ist ihre Aufteilung in zwei Phasen: eine eingabeunabhängige Setup-Phase, die das Vorrechnen von aufwendigen kryptografischen Primitiven wie dem oblivious transfer (OT) ermöglicht, gefolgt von einer extrem schnellen Online-Phase, sobald die Eingaben verfügbar sind.

Die Herausforderung bei auf GC basierenden Protokollen liegt im Rechenaufwand kryptografischer Operationen, wie dem Advanced Encryption Standard (AES), während der Online-Phase. Beispielsweise erfordert das effizienteste heutige Schema die Berechnung von 9 festgelegten AES-Operationen für jedes AND-Gatter (Rosulek und Roy, CRYPTO’21). Während GMW-basierte Protokolle kryptografische Operationen in der Online-Phase vermeiden, werden sie durch die benötigten Kommunikationsrunden, die von der Tiefe des zu bewertenden Schaltkreises abhängen.

Um die Effizienz von auf GC basierenden Protokollen zu verbessern, erforschen wir die Verwendung von Vector AES (VAES), einer jüngsten Innovation von Intel, die die parallele Berechnung mehrerer AES-Operationen ermöglicht. Unser Ziel ist es, diese modernen Hardware-Fähigkeiten zu nutzen, um GC-basierte Protokolle für praktische Anwendungen zu optimieren.

Bei den auf GMW basierenden Protokollen zielen wir darauf ab, praktische Effizienz durch funktionsspezifische Vorverarbeitung zu erreichen, die erhebliche Verbesserungen erbrachte, indem das Wissen über die zu bewertende Funktion genutzt wurde. Dieser Ansatz ist besonders vorteilhaft in Kontexten wie maschinellem Lernen als Dienstleistung (im Englischen machine learning as a service, MLaaS), wo eine einzelne Funktion wiederholt mit verschiedenen Eingaben bewertet wird. Unsere Entwicklungen, ABY2.0 und FLUTE, haben die Online-Kommunikationseffizienz des GMW-Protokolls in einer 2PC deutlich verbessert. Wir haben auch effiziente Protokolle für die sichere Bewertung von Multi-Input-AND-Gattern und Lookup-Tabellen (LUT) entworfen, zusammen mit neuen Konstruktionen basierend auf LUTs, um die Effizienz der privaten Funktionsbewertung (im Englischen private function evaluation, PFE) zu erhöhen. Darüber hinaus haben wir automatisch Schaltkreise generiert, die für diese Protokolle optimiert sind.

Ein weiterer Bereich unserer Forschung befasst sich mit der gängigen Annahme symmetrischen Vertrauens bei MPC, die davon ausgeht, dass alle Parteien entweder halb-ehrlich sind oder zu bösartigem Verhalten fähig sind. Diese Annahme entspricht jedoch möglicherweise nicht der asymmetrischen Natur des Vertrauens, wie sie in realen Szenarien vorkommt, die durch Reputation, Machtverhältnisse und Anreize geprägt sind. Um dies zu berücksichtigen, erweitern wir unser 2PC-Framework von ABY2.0 zu einer Drei-Parteien-Berechnung (im Englischen three-party computation, 3PC) mit ehrlicher Mehrheit, das für Szenarien konzipiert ist, in denen nur eine Partei bösartig ist und die anderen Parteien halb-ehrlich sind. Diese Erweiterung berücksichtigt Fälle, in denen die bösartige Partei als Helfer in ABY2.0 agiert oder als auswertende Partei im 3PC-Szenarien dient.

Dieser Teil der Arbeit basiert auf den folgenden fünf Veröffentlichungen: [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, S. 131–145. CORE Rank A. Appendix D.

[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 (IEEE S&P). Online: https://ia.cr/2023/499. Code: https://encrypto.de/code/FLUTE. IEEE, 2023, S. 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). Bd. 14438. LNCS. Online: https://ia.cr/2021/809. Code: https://encrypto.de/code/LUC. Springer, 2023, S. 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&P). Online: https:/ / ia . cr / 2023 / 1744. Code: https://encrypto.de/code/MOTION-FD. IEEE, 2024. CORE Rank A*. Appendix H.

Diese Dissertation widmet sich der Förderung der praktischen Anwendung von MPC in realen Szenarien. Sie konzentriert sich auf die Optimierung von grundlegenden Bausteinen und die Entwicklung effizienter datenschutzbewahrender Lösungen, die speziell für praktische Anwendungsfälle konzipiert sind.

German

Status:

Publisher's Version

URN:

urn:nbn:de:tuda-tuprints-281688

Classification DDC:

000 Generalities, computers, information > 004 Computer science

Divisions:

20 Department of Computer Science > Cryptography and Privacy Engineering (ENCRYPTO)

Date Deposited:

15 Oct 2024 12:30

Last Modified: