Towards Practical Secure Computation: Exploring Applicability and Function Privacy Trade-offs

Secure Multi-Party Computation (MPC) allows multiple parties to jointly compute a public function on their private inputs without revealing anything beyond the final result. Traditionally, MPC protocols rely on representing the function as a Boolean or arithmetic circuit, and their efficiency depends on the size or depth of that circuit. However, when applications cannot be efficiently modeled in this way, they do not perform well with MPC evaluation. This highlights the need for secure, privacy-preserving protocols for more specific applications. Moreover, conventional MPC requires all parties to know the computed function, which is problematic when the function is Intellectual Property (IP). Consequently, companies are not willing to compromise the confidentiality of their IP just to ensure user privacy.

This thesis classifies secure computations using two key metrics: applicability ranging from specific to general functions, and function privacy. While MPC is recognized as a highly generalizable solution that lacks function privacy, our focus in the first part of this thesis is on specific protocols that are less generalizable and offer no function privacy. In the second part, we address the sub-category of the secure computation of general functions that provide function privacy. To achieve these objectives, we build upon prior research and design, implement, and evaluate practical protocols for the specific functions Private Information Retrieval (PIR) and Multi-Party Private Set Intersection (MP-PSI), as well as Private Function Evaluation (PFE) for general functions with function privacy.

Specific Functions. PIR is a cryptographic protocol that allows querying an entry from a public database held by servers without revealing any information about the requested entry. While some PIR solutions can be executed with a single server, these protocols typically rely on Homomorphic Encryption (HE), which requires computationally intensive cryptographic operations across the entire database. In contrast, multi-server PIR is more efficient, relying only on lightweight XOR operations over the database. However, this efficiency comes with a trade-off: multi-server PIR assumes that the servers do not collude, which is a stronger security assumption. Accelerating server computations using a GPU was an efficient approach in single-server PIR (Melchor et al., SECURWARE’08). However, achieving similar acceleration in multi-server PIR has been challenging due to the high cost of memory shift operations on GPUs compared to the cheap XOR operations. To address this, we use the multi-server PIR protocol of my master’s thesis to amortize the costs of memory shift operations across multiple queries. In particular, that protocol involves a preprocessing phase that performs most XOR operations independently of the client, allowing for efficient batch processing. Our best GPU implementation improves the preprocessing phase of PIR by several orders of magnitude compared to a CPU implementation, and the amortized total runtime outperforms state-of-the-art PIR implementations.

The second specific function we explore is MP-PSI, which allows multiple parties to learn the intersection of their respective private sets securely. Inspired by designing a solution for inter-state arms control, our motivation requires more than the standard MP-PSI, which typically outputs only the intersection elements known by all parties. Instead, we aim to develop protocols that can output intersection elements known by a threshold number of parties and optionally by a fixed subset of those parties. Existing MP-PSI protocols rely on HE or Oblivious Transfer (OT), making them less adaptable to this particular use case and less compatible with other secure computations. To bridge this gap, we design Boolean circuits for MP-PSI and its variants, which can be seamlessly integrated into any MPC protocol. Our evaluation demonstrates that our solution is applicable in real-world scenarios for the cyber arms control use case.

This part of the thesis is based on the following two publications:

[GHPS22] D. GÜNTHER, M. HEYMANN, B. PINKAS, T. SCHNEIDER. “GPU-accelerated PIR with Client-Independent Preprocessing for Large-Scale Applications”. In: 31. USENIX Security Symposium (USENIX Security’22). Online: https://ia.cr/2021/823. Code: https://encrypto.de/code/cip-pir. USENIX, 2022, pp. 1759–1776. CORE Rank A*. Appendix A.

[RKG+23] T. REINHOLD, P. KÜHN, D. GÜNTHER, T. SCHNEIDER, C. REUTER. “ExTRUST: Reducing Exploit Stockpiles with a Privacy-Preserving Depletion System for Inter-State Relationships”. In: IEEE Transactions on Technology and Society 4.2 (2023). Online: http://arxiv.org/abs/2306.00589, pp. 158–170. Appendix B.

General Functions with Function Privacy. PFE allows to securely compute a private function provided by one party on private data held by the other parties. Today’s most flexible solution involves embedding Boolean circuits into a so-called Universal Circuit (UC), which is a public function evaluated within an MPC protocol. A UC can be programmed to compute any Boolean circuit up to a specified size n. However, UCs have a size complexity of Θ(n log n), making it desirable to compress the size of the Boolean circuit computed by the UC. One promising approach is to use a function representation based on Lookup Tables (LUTs) with ρ inputs and ω outputs, denoted as (ρ → ω)-LUT. Unfortunately, UCs currently only support the evaluation of LUTs with a single output, and a high input dimension ρ > 4 significantly increases the size of the UC, leading to worse performance than traditional Boolean circuit-based solutions.

To overcome this challenge, we introduce two UC constructions: the LUT-based Universal Circuit (LUC) and Varying Universal Circuit (VUC), both of which support the evaluation of circuits based on (ρ → ω)-LUTs. The LUT construction has fixed LUT dimensions ρ and ω, while the VUC construction allows for the embedding of LUTs with varying input dimensions. This flexibility in the VUC constructions increases the concrete efficiency but comes with the trade-off of leaking the input dimensions of all LUTs in the circuit. Therefore, evaluating the LUC construction within an MPC protocol achieves PFE. In contrast, using the VUC construction provides a weaker function privacy guarantee, which we refer to as Varying Private Function Evaluation (VPFE). Our evaluation shows that our LUC construction outperforms the state-of-the-art UC construction by Liu et al. (CRYPTO’21), and our VUC construction further improves performance for most of our benchmark applications.

Building on these results, we developed a tool called FLUENT for Semi-Private Function Evaluation (SPFE). In SPFE, the function is divided into public and private components, with our LUC and VUC constructions used to hide the private components. FLUENT is the first tool that allows developers to easily implement semi-private functions, enabling them to mark sub-functions as public or private directly in the source code. The functions can be written in the high-level languages C or C++ or in the low-level Hardware Description Language (HDL) Verilog. We evaluated our FLUENT tool on a car insurance tariff calculation function and found that it outperformed our previous SPFE tool (CCS Poster’19).

This part of the thesis is based on the following two publications:

[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: 29. Advances in Cryptology - ASIACRYPT’23. Vol. 14438. LNCS. Online: https://ia.cr/2022/1652. Code: https://encrypto.de/code/LUC. Springer, 2023, pp. 3–37. CORE Rank A. Appendix C. [GSSY24] D. GÜNTHER, J. SCHMIDT, T. SCHNEIDER, H. YALAME. “FLUENT: A Tool for Efficient Mixed-Protocol Semi-Private Function Evaluation”. In: 40. Annual Computer Security Applications Conference (ACSAC’24). To appear. Code: https://encrypto.de/code/FLUENT. ACM, 2024. CORE Rank A. Appendix D.

Overall, this thesis significantly advances the practicality of secure computations for specific functions, including PIR and MP-PSI, as well as for general private functions within PFE, VPFE, and SPFE.

Sichere Mehrparteienberechnungen (im Englischen Secure Multi-Party Computation; MPC) ermöglichen es mehreren Parteien, gemeinsam eine öffentliche Funktion auf ihren privaten Eingaben zu berechnen, ohne etwas anderes als das Endergebnis preiszugeben. Traditionell beruhen MPC-Protokolle auf der Darstellung der Funktion als boolesche oder arithmetische Schaltung, und ihre Effizienz hängt von der Größe oder Tiefe dieser Schaltung ab. Wenn Anwendungen jedoch nicht auf diese Weise effizient modelliert werden können, schneiden sie bei der MPC-Auswertung nicht gut ab. Dies unterstreicht den Bedarf an sicheren, die Privatsphäre wahrenden Protokollen für spezifischere Anwendungen. Außerdem erfordert die herkömmliche MPC, dass alle Beteiligten die berechnete Funktion kennen, was problematisch ist, wenn es sich bei der Funktion um geistiges Eigentum (im englischen Intellectual Property; IP) handelt. Folglich sind Unternehmen nicht bereit, die Vertraulichkeit ihres geistigen Eigentums zu gefährden, nur um die Privatsphäre der Nutzer zu schützen.

In dieser Arbeit werden sichere Berechnungen anhand von zwei Schlüsselkriterien klassifiziert: Anwendbarkeit - von spezifischen bis hin zu allgemeinen Funktionen - und Funktionsschutz. Während MPC als eine hochgradig verallgemeinerbare Lösung anerkannt ist, die keinen Funktionsschutz bietet, liegt unser Fokus im ersten Teil dieser Arbeit auf spezifischen Protokollen, die weniger verallgemeinerbar sind und keinen Funktionsschutz bieten. Im zweiten Teil befassen wir uns mit der Unterkategorie der sicheren Berechnung allgemeiner Funktionen, die den Schutz von Funktionen bieten. Um diese Ziele zu erreichen, bauen wir auf früheren Forschungen auf und entwerfen, implementieren und evaluieren praktische Protokolle für die spezifischen Funktionen der privaten Datenbankabfragen (im Englischen Private Information Retrieval; PIR) und privater Mehrparteien Schnittmengenberechnungen (im Englischen Multi-Party Private Set Intersection; MP-PSI) sowie private Funktionsberechnungen (im Englischen Private Function Evaluation; PFE) für allgemeine Funktionen mit Funktionsgeheimnis.

Spezifische Funktionen. PIR ist ein kryptografisches Protokoll, das die Abfrage eines Eintrags aus einer öffentlichen Datenbank ermöglicht, die von Servern gehalten wird, ohne Informationen über den angeforderten Eintrag preiszugeben. Einige PIR-Lösungen können zwar mit einem einzigen Server ausgeführt werden, aber diese Protokolle beruhen in der Regel auf homomorpher Verschlüsselung (im Englischen Homomorphic Encryption; HE), die rechenintensive kryptografische Operationen für die gesamte Datenbank erfordert. Im Gegensatz dazu ist PIR mit mehreren Servern effizienter, da es sich nur auf leichtgewichtige XOR-Operationen in der Datenbank stützt. Diese Effizienz bringt jedoch einen Nachteil mit sich: PIR mit mehreren Servern setzt voraus, dass die Server nicht zusammenarbeiten, was eine stärkere Sicherheitsannahme darstellt. Die Beschleunigung von Serverberechnungen mithilfe eines Grafikprozessors war ein effizienter Ansatz für PIR basierend auf einem Server (Melchor et al., SECURWARE’08). Eine ähnliche Beschleunigung bei auf mehreren Servern basierendes PIR ist jedoch aufgrund der hohen Kosten von Speicherverschiebungsoperationen auf GPUs im Vergleich zu den kostengünstigeren XOR-Operationen eine Herausforderung.

Um dieses Problem zu lösen, verwenden wir das auf mehreren Servern basierende PIR Protokoll aus meiner Masterarbeit, um die Kosten der Speicherverschiebungsoperationen über mehrere Abfragen zu amortisieren. Dieses Protokoll beinhaltet insbesondere eine Vorverarbeitungsphase, die die meisten XOR-Operationen unabhängig vom Client durchführt und so eine effiziente Stapelverarbeitung ermöglicht. Unsere beste GPU-Implementierung verbessert die Vorverarbeitungsphase von PIR im Vergleich zu einer CPU-Implementierung um mehrere Größenordnungen, und die amortisierte Gesamtlaufzeit übertrifft die modernsten PIR-Implementierungen.

Die zweite spezifische Funktion, die wir untersuchen, ist MP-PSI, die es mehreren Parteien ermöglicht, die Schnittmenge ihrer jeweiligen privaten Mengen auf sichere Weise zu erfahren. Inspiriert durch die Entwicklung einer Lösung für die zwischenstaatliche Rüstungskontrolle, erfordert unsere Motivation mehr als die Standard MP-PSI Funktionalität, die normalerweise nur die Schnittmengenelemente ausgibt, die allen Parteien bekannt sind. Stattdessen wollen wir Protokolle entwickeln, die Schnittmengenelemente ausgeben können, die von einer bestimmten Anzahl von Parteien und optional von einer festen Teilmenge dieser Parteien bekannt sind. Bestehende MP-PSI-Protokolle beruhen auf HE oder unbemerkter Übertragungen (im Englischen Oblivious Transfer; OT), was sie weniger anpassungsfähig für diesen speziellen Anwendungsfall und weniger kompatibel mit anderen sicheren Berechnungen macht. Um diese Lücke zu schließen, entwerfen wir boolesche Schaltungen für MP-PSI und seine Varianten, die nahtlos in jedes MPC-Protokoll integriert werden können. Unsere Evaluierung zeigt, dass unsere Lösung in realen Szenarien für den Anwendungsfall der Cyber-Rüstungskontrolle anwendbar ist.

Dieser Teil der Dissertation basiert auf den folgenden zwei Veröffentlichungen:

[GHPS22] D. GÜNTHER, M. HEYMANN, B. PINKAS, T. SCHNEIDER. “GPU-accelerated PIR with Client-Independent Preprocessing for Large-Scale Applications”. In: 31. USENIX Security Symposium (USENIX Security’22). Online: https://ia.cr/2021/823. Code: https://encrypto.de/code/cip-pir. USENIX, 2022, S. 1759–1776. CORE Rank A*. Appendix A.

[RKG+23] T. REINHOLD, P. KÜHN, D. GÜNTHER, T. SCHNEIDER, C. REUTER. “ExTRUST: Reducing Exploit Stockpiles with a Privacy-Preserving Depletion System for Inter-State Relationships”. In: IEEE Transactions on Technology and Society 4.2 (2023). Online: http://arxiv.org/abs/2306.00589, S. 158–170. Appendix B.

Allgemeine Funktionen mit Funktionsschutz. PFE ermöglicht die sichere Berechnung einer von einer Partei bereitgestellten privaten Funktion mit privaten Daten der anderen Parteien. Die derzeit flexibelste Lösung besteht darin, boolesche Schaltungen in eine so genannte universelle Schaltung (im Englischen Universal Circuit; UC) einzubetten, bei der es sich um eine öffentliche Funktion handelt, die im Rahmen eines MPC-Protokolls ausgewertet wird. Ein UC kann so programmiert werden, dass er jede beliebige boolesche Schaltung bis zu einer bestimmten Größe n berechnet. UCs haben jedoch eine Größenkomplexität von O(nlogn), so dass es wünschenswert ist, die Größe der vom UC berechneten booleschen Schaltung zu komprimieren. Ein vielversprechender Ansatz ist die Verwendung einer Funktionsdarstellung auf der Grundlage von Lookup Tabellen (LUTs) mit ρ Eingängen und ω Ausgängen, die als (ρ →ω)-LUT bezeichnet werden. Leider unterstützen UCs derzeit nur die Auswertung von LUTs mit einem einzigen Ausgang, und eine hohe Eingangsdimension ρ > 4 erhöht die Größe der UCs erheblich, was zu einer schlechteren Leistung im Vergleich zu herkömmlichen Lösungen auf der Grundlage boolescher Schaltungen führt.

Um diese Herausforderung zu meistern, führen wir zwei UC-Konstruktionen ein: die LUT-basierte Universalschaltung (im Englischen LUT-based Universal Circuit; LUC) und die variierende Universalschaltung (im Englischen Varying Universal Circuit; VUC), die beide die Auswertung von Schaltungen auf der Basis von (ρ →ω)-LUTs unterstützen. Die LUT-Konstruktion hat feste LUT-Dimensionen ρ und ω, während die VUC-Konstruktion die Einbettung von LUTs mit variierenden Eingangsdimensionen ermöglicht. Diese Flexibilität in den VUC-Konstruktionen erhöht die konkrete Effizienz, hat aber den Nachteil, dass die Eingangsabmessungen aller LUTs in der Schaltung durchsickern. Daher wird durch die Auswertung der LUC-Konstruktion innerhalb eines MPC-Protokolls PFE erreicht. Im Gegensatz dazu bietet die Verwendung der VUC-Konstruktion eine schwächere Garantie für die Funktionsprivatheit, die wir als variierende private Funktionsauswertungen (im Englischen Varying Private Function Evaluation; VPFE) bezeichnen. Unsere Evaluierung zeigt, dass unsere LUC-Konstruktion die moderne UC-Konstruktion von Liu et al. (CRYPTO’21) übertrifft, und unsere VUC-Konstruktion verbessert die Leistung für die meisten unserer Benchmark-Anwendungen weiter.

Aufbauend auf diesen Ergebnissen haben wir ein Werkzeug namens FLUENT für die halbprivate Funktionsauswertung (im Englischen Semi-Private Function Evaluation; SPFE) entwickelt. Bei SPFE wird die Funktion in öffentliche und private Komponenten unterteilt, wobei unsere LUC- und VUC-Konstruktionen zum Verbergen der privaten Komponenten verwendet werden. FLUENT ist das erste Werkzeug, das es Entwicklern ermöglicht, halbprivate Funktionen einfach zu implementieren, indem sie Unterfunktionen direkt im Quellcode als öffentlich oder privat kennzeichnen können. Die Funktionen können in den Hochsprachen C oder C++ oder in der Low-Level Hardware Beschreibungssprache Verilog geschrieben werden. Wir haben unser FLUENT-Werkzeug an einer Funktion zur Berechnung von Kfz-Versicherungstarifen evaluiert und stellten fest, dass es unser früheres SPFE-Werkzeug (CCS Poster’19) übertrifft.

Dieser Teil der Arbeit basiert auf den folgenden zwei Veröffentlichungen:

[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: 29. Advances in Cryptology - ASIACRYPT’23. Bd. 14438. LNCS. Online: https://ia.cr/2022/1652. Code: https://encrypto.de/code/LUC. Springer, 2023, S. 3–37. CORE Rank A. Appendix C.

[GSSY24] D. GÜNTHER, J. SCHMIDT, T. SCHNEIDER, H. YALAME. “FLUENT: A Tool for Efficient Mixed-Protocol Semi-Private Function Evaluation”. In: 40. Annual Computer Security Applications Conference (ACSAC’24). To appear. Code: https://encrypto.de/code/FLUENT. ACM, 2024. CORE Rank A. Appendix D.

Insgesamt bringt diese Arbeit die Praktikabilität von sicheren Berechnungen für bestimmte Funktionen, einschließlich PIR und MP-PSI, sowie für allgemeine private Funktionen innerhalb von PFE, VPFE und SPFE erheblich voran.