title: Towards Deployable MPC: Flexible and Efficient Tools for Real-World Applications
Creators: name: Tkachenko, Oleksandr
Publisher: name: UNSPECIFIED
Year: 2022

description: Secure multi-party computation (MPC) allows two or more parties to compute an arbitrary function on their private inputs while revealing nothing beyond the output of the function. MPC is a generic technique that can be used to build privacy-preserving solutions for a large number of real-world, privacy-sensitive applications such as collaborative medical research or machine learning on sensitive data. This, however, poses big challenges: 1) the current tools for MPC are fine-tuned for particular tasks and are challenging to adopt or extend to other tasks which is though required in many use cases, and 2) MPC imposes a significant communication and computational overhead compared to the cleartext computation, rendering most “naïvely constructed” privacy-preserving protocols impractical for the real-world use. We address both challenges in this thesis. Firstly, we design and implement an open-source flexible and efficient framework for MPC and secure outsourcing, where MPC is outsourced to a smaller number of non-colluding parties who gain no information about the inputs nor about the intermediate or final results of the computation. Secondly, we design, implement, and evaluate the first linear-communication circuit-based private set intersection (PSI) protocol, i.e., it can can be combined with arbitrary MPC functionalities, e.g., reveal the intersection only if the intersection size is larger than some threshold. Thirdly, we design, implement, and evaluate two MPC protocols for specific tasks: 1) WiFi fingerprint based indoor localization and 2) similar sequence queries on genomic data. Generic MPC Tools and Protocols To run MPC protocol for real tasks, we need tools for MPC that can be used to implement arbitrary applications in a privacy-preserving way. There exist several open-source MPC frameworks but all of them are either efficient or they can be modified without a significant time investment, but not both at the same time. As a consequence, a significant amount of time is spent by researchers in an attempt to understand and modify MPC frameworks, which often crash after incautious modifications, thus slowing down the research. To address this problem, we develop MOTION, an open-source C++ framework for implementing and combining MPC protocols and primitives. In contrast to prior work, MOTION combines both efficiency and flexibility. It allows to implement and combine MPC protocols and optimizations while learning and modifying only the relevant parts of the framework, which is due to the novel asynchronous design. In MOTION, we combine three different generic MPC protocols for two or more parties. We also design and implement novel efficient conversions between some of those protocols and optimize low-level building blocks. Finally, we show that MOTION is often substantially more efficient than other MPC frameworks. While MOTION can evaluate arbitrary functionalities, we also investigate a more specific but yet generic class of functionalities. PSI is a well-known building block for privacy-preserving applications, and it has generated a long line of research. PSI allows two parties to compute set intersection on their private input sets without revealing any information beyond the intersection. The notion of PSI we improve in this part of the thesis is called circuit-based PSI (C-PSI), and it allows to perform arbitrary MPC while hiding the intersection result, e.g., the parties can compute complex statistics on the intersection result. We design the first C-PSI protocol with linear communication based on sophisticated hashing techniques and oblivious programmable pseudo-random functions. Beyond better asymptotic communication complexity, we show that an implementation of our C-PSI protocol is significantly more efficient compared to prior work in terms of both computation and communication. This part of the thesis is based on the following publications: [BDST22] L. BRAUN, D. DEMMLER, T. SCHNEIDER, O. TKACHENKO. “MOTION - A Framework for Mixed-Protocol Multi-Party Computation”. In: ACM Transactions on Privacy and Security (TOPS) 25 (2 2022). Accepted for publication. Online: https://ia.cr/2020/1137. Code: https://encrypto.de/code/MOTION. CORE Rank A. Appendix A. [PSTY19] B. PINKAS, T. SCHNEIDER, O. TKACHENKO, A. YANAI. “Efficient Circuit-based PSI with Linear Communication”. In: Advances in Cryptology – EUROCRYPT’19. Vol. 11478. LNCS. Online: https://ia.cr/2019/241. Code: https://encrypto.de/code/OPPRF- PSI. Springer, 2019, pp. 122–153. CORE Rank A*. Appendix B. MPC Applications &amp; Optimizations MPC is not yet widely adopted in real applications. The main reason is the high communication and computational overhead of MPC compared to cleartext computation. Furthermore, the design of efficient MPC protocols requires expert knowledge in computer science, cryptography, and circuit design. Tools such as HyCC (Büscher et al., CCS’19) lift this requirement for small applications but are yet not suitable for large and complex problems. In this thesis, we build MPC-based protocols for two privacy-sensitive real-world applications: 1) indoor localization and 2) similar sequence queries on genomic databases. To improve the efficiency of our protocols, we use optimized building blocks such as our currently smallest circuit for finding k-nearest neighbors. This part of the thesis is based on the following two publications: [JLL+ 19] K. JÄRVINEN, H. LEPPÄKOSKI, E. S. LOHAN, P. RICHTER, T. SCHNEIDER, O. TKACHENKO, Z. YANG. “PILOT: Practical Privacy-Preserving Indoor Localization using OuTsourcing”. In: IEEE European Symposium on Security and Privacy (EuroS&amp;P’19). IEEE, 2019, pp. 448–463. Appendix C. [ST19] T. SCHNEIDER, O. TKACHENKO. “EPISODE: Efficient Privacy-PreservIng Similar Sequence Queries on Outsourced Genomic DatabasEs”. In: ACM ASIA Conference on Computer and Communications Security (ASIACCS’19). Full version: https://ia.cr/2021/029. ACM, 2019, pp. 315–327. CORE Rank A. Appendix D. This thesis contributes to making MPC more flexible but also more efficient for a generic use by optimizing low-level building blocks, and it introduces efficient privacy-preserving solutions for two concrete real-world applications.