International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Reusable Two-Round MPC from DDH

Authors:
James Bartusek
Sanjam Garg
Daniel Masny
Pratyay Mukherjee
Download:
Search ePrint
Search Google
Abstract: We present a reusable two-round multi-party computation (MPC) protocol from the Decisional Diffie Hellman assumption (DDH). In particular, we show how to upgrade any secure two-round MPC protocol to allow reusability of its first message across multiple computations, using Homomorphic Secret Sharing (HSS) and pseudorandom functions in NC1 — each of which can be instantiated from DDH. In our construction, if the underlying two-round MPC protocol is secure against semi-honest adversaries (in the plain model) then so is our reusable two-round MPC protocol. Similarly, if the underlying two-round MPC protocol is secure against malicious adversaries (in the common random/reference string model) then so is our reusable two-round MPC protocol. Previously, such reusable two-round MPC protocols were only known under assumptions on lattices. At a technical level, we show how to upgrade any two-round MPC protocol to a first message succinct two-round MPC protocol, where the first message of the protocol is generated independently of the computed circuit (though it is not reusable). This step uses homomorphic secret sharing (HSS) and low-depth pseudorandom functions. Next, we show a generic transformation that upgrades any first message succinct two-round MPC to allow for reusability of its first message.
Video from TCC 2020
BibTeX
@article{tcc-2020-30619,
  title={Reusable Two-Round MPC from DDH},
  booktitle={Theory of Cryptography},
  publisher={Springer},
  author={James Bartusek and Sanjam Garg and Daniel Masny and Pratyay Mukherjee},
  year=2020
}