Cryptology ePrint Archive: Report 2016/614

Better Two-Round Adaptive Multi-Party Computation

Ran Canetti and Oxana Poburinnaya and Muthuramakrishnan Venkitasubramaniam

Abstract: 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.

Category / Keywords: adaptive MPC

Original Publication (in the same form): IACR-PKC-2017

Date: received 12 Jun 2016, last revised 10 Jan 2017

Contact author: oxanapob at bu edu, canetti@bu edu, muthuv@cs rochester edu

Available format(s): PDF | BibTeX Citation

Version: 20170110:222109 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]