Paper 2022/1648

Compute, but Verify: Efficient Multiparty Computation over Authenticated Inputs

Moumita Dutta, Indian Institute of Science Bangalore
Chaya Ganesh, Indian Institute of Science Bangalore
Sikhar Patranabis, IBM Research, India
Nitin Singh, IBM Research, India

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 certification authority. We propose a generic and efficient compiler that transforms any linear secret sharing based honest-majority 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 honest majority 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/3$, 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.

Note: The definition of distributed proofs of knowledge has been updated for better interface with applications. The main constructions and proofs are updated for better exposition. Additional comparison to related work has been added.

Available format(s)
Cryptographic protocols
Publication info
Multi-Party ComputationAuthenticationAuthenticated MPCDistributed Zero-KnowledgeDistributed Proof of Knowledge
Contact author(s)
moumitadutta @ iisc ac in
chaya @ iisc ac in
sikhar patranabis @ ibm com
nitisin1 @ in ibm com
2023-09-21: last of 7 revisions
2022-11-28: received
See all versions
Short URL
Creative Commons Attribution


      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{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.