Compute, but Verify: Efficient Multiparty Computation over Authenticated Inputs

Abstract

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.

Available format(s)
Category
Cryptographic protocols
Publication info
Preprint.
Keywords
Multi-Party Computation Authentication Authenticated MPC Distributed Zero-Knowledge Distributed Proof of Knowledge
Contact author(s)
chaya @ iisc ac in
sikhar patranabis @ ibm com
nitisin1 @ in ibm com
History
2022-11-28: approved
See all versions
Short URL
https://ia.cr/2022/1648

CC BY

BibTeX

@misc{cryptoeprint:2022/1648,
author = {Moumita Dutta and Chaya Ganesh and Sikhar Patranabis and Nitin Singh},
title = {Compute, but Verify: Efficient Multiparty Computation over Authenticated Inputs},
howpublished = {Cryptology ePrint Archive, Paper 2022/1648},
year = {2022},
note = {\url{https://eprint.iacr.org/2022/1648}},
url = {https://eprint.iacr.org/2022/1648}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.