Paper 2016/614

Better Two-Round Adaptive Multi-Party Computation

Ran Canetti, Oxana Poburinnaya, and Muthuramakrishnan Venkitasubramaniam


The only known two-round multi-party computation protocol that withstands adaptive corruption of all parties is the ingenious protocol of Garg and Polychroniadou [TCC 15]. We present protocols that improve on the GP protocol in a number of ways. First, concentrating on the semi-honest case and taking a different approach than GP, we show a two-round, adaptively secure protocol where: Only a global (i.e., non-programmable) reference string is needed. In contrast, in GP the reference string is programmable, even in the semi-honest case. Only polynomially-secure indistinguishability obfuscation for circuits and injective one way functions are assumed. In GP, sub-exponentially secure IO is assumed. Second, we show how to make the GP protocol have only RAM complexity, even for Byzantine corruptions. For this we construct the first statistically-sound non-interactive Zero-Knowledge scheme with RAM complexity.

Available format(s)
Publication info
Published by the IACR in PKC 2017
adaptive MPC
Contact author(s)
oxanapob @ bu edu
canetti @ bu edu
muthuv @ cs rochester edu
2017-01-10: revised
2016-06-16: received
See all versions
Short URL
Creative Commons Attribution


      author = {Ran Canetti and Oxana Poburinnaya and Muthuramakrishnan Venkitasubramaniam},
      title = {Better Two-Round Adaptive Multi-Party Computation},
      howpublished = {Cryptology ePrint Archive, Paper 2016/614},
      year = {2016},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.