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.