Cryptalphabet Soup: DPFs meet MPC and ZKPs
Date
2023-09-22
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Secure multiparty computation (MPC) protocols enable multiple parties to collaborate on a computation using private inputs possessed by the different parties in the computation. At the same time, MPC protocols ensure that no participating party learns anything about the other parties’ private inputs beyond what they can infer from the computation’s output and their own inputs. MPC has wide ranging applications for privacy protecting systems. However, these systems have been plagued by limited performance, lack of scalability, and poor accuracy. In this thesis, we demonstrate several novel techniques for using distributed point functions (DPFs) in combination with MPC to obtain significant performance improvements in several different applications. Namely, using novel observations about the structure of the most efficient available DPF construction in the literature, we show that DPF keys from untrusted sources can be checked for correctness using an MPC protocol between the two key holders, with direct applications in sender-anonymous messaging. We expand these observations to produce the most efficient available method to evaluate piecewise-polynomial functions, also known as splines. The scalability and efficiency of this method allows for splines to be used for extremely high accuracy approximation of non-linear functions in MPC. Furthermore, the protocols proposed in this thesis far outperform prior solutions both in large-scale asymptotic measurements and in concrete benchmarks using high-performance software implementations at both small- and large-scale.
Description
Keywords
Cryptography, Secure Multiparty Computation, MPC, Zero-Knowledge Proof, ZKP, Distributed Point Function, DPF, Function Secret Sharing, FSS, Private Information Retrieval, PIR, Sender-Anonymous Messaging, Privacy-Enhancing Technology, Privacy Preserving Machine Learning
Citation
Storrier, K. (2023). Cryptalphabet soup: DPFs meet MPC and ZKPs (Master's thesis, University of Calgary, Calgary, Canada). Retrieved from https://prism.ucalgary.ca.