[Resource Topic] 2022/1648: Compute, but Verify: Efficient Multiparty Computation over Authenticated Inputs

Welcome to the resource topic for 2022/1648

Compute, but Verify: Efficient Multiparty Computation over Authenticated Inputs

Authors: Moumita Dutta, Chaya Ganesh, Sikhar Patranabis, Nitin Singh


Traditional notions of secure multiparty computation (MPC) allow mutually distrusting parties to jointly compute a function over their private inputs, but typically do not specify how these inputs are chosen. Motivated by real-world applications where corrupt inputs could adversely impact privacy and operational legitimacy, we consider a notion of authenticated MPC where the inputs are authenticated, e.g., signed using a digital signature by some trusted authority. We propose a generic and efficient compiler that transforms any linear secret sharing based MPC protocol into one with input authentication.

Our compiler incurs significantly lower computational costs and competitive communication overheads when compared to the best existing solutions, while entirely avoiding the (potentially expensive) protocol-specific techniques and pre-processing requirements that are inherent to these solutions. For n-party MPC protocols with abort security where each party has \ell inputs, our compiler incurs O(n\log \ell) communication overall and a computational overhead of O(\ell) group exponentiations per party (the corresponding overheads for the most efficient existing solution are O(n^2) and O(\ell n)). Finally, for a corruption threshold t<n/4, our compiler preserves the stronger identifiable abort security of the underlying MPC protocol. No existing solution for authenticated MPC achieves this regardless of the corruption threshold.

Along the way, we make several technical contributions that are of independent interest. This includes the notion of distributed proofs of knowledge and concrete realizations of the same for several relations of interest, such as proving knowledge of many popularly used digital signature schemes, and proving knowledge of opening of a Pedersen commitment. We also illustrate the practicality of our approach by extending the well-known MP-SPDZ library with our compiler, thus yielding prototype authenticated MPC protocols.

ePrint: https://eprint.iacr.org/2022/1648

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .