Cryptology ePrint Archive: Report 2011/508

Secure Two-Party Computation with Low Communication

Ivan Damgård and Sebastian Faust and Carmit Hazay

Abstract: We propose a 2-party UC-secure protocol that can compute any function securely. The protocol requires only two messages, communication that is poly-logarithmic in the size of the circuit description of the function, and the workload for one of the parties is also only poly-logarithmic in the size of the circuit. This implies, for instance, delegatable computation that requires no expensive off-line phase and remains secure even if the server learns whether the client accepts its results. To achieve this, we define two new notions of extractable hash functions, propose an instantiation based on the knowledge of exponent in an RSA group, and build succinct zero-knowledge arguments in the CRS model.

Category / Keywords: Secure Two-Party Computation, Extractable Hash Functions, Communication and Round Complexity, Non-Interactive Secure Computation, Delegatable Computation

Date: received 16 Sep 2011, last revised 13 Mar 2012

Contact author: carmit at cs au dk

Available format(s): PDF | BibTeX Citation

Note: Construction based on weaker extractability assumption

Version: 20120313:203032 (All versions of this report)

Short URL: ia.cr/2011/508

Discussion forum: Show discussion | Start new discussion