Cryptology ePrint Archive: Report 2015/055

Richer Efficiency/Security Trade-offs in 2PC

Vladimir Kolesnikov and Payman Mohassel and Ben Riva and Mike Rosulek

Abstract: The dual-execution protocol of Mohassel \& Franklin (PKC 2006) is a highly efficient (each party garbling only one circuit) 2PC protocol that achieves malicious security apart from leaking an {\em arbitrary, adversarially-chosen} predicate about the honest party's input. We present two practical and orthogonal approaches to improve the security of the dual-execution technique.

First, we show how to greatly restrict the predicate that an adversary can learn in the protocol, to a natural notion of ``only computation leaks''-style leakage. Along the way, we identify a natural security property of garbled circuits called {\em property-enforcing} that may be of independent interest.

Second, we address a complementary direction of reducing the probability that the leakage occurs. We propose a new dual-execution protocol --- with a very light cheating-detection phase and each party garbling $s+1$ circuits --- in which a cheating party learns a bit with probability only $2^{-s}$. Our concrete measurements show approximately $35\%$ reduction in communication for the AES circuit, compared to the best combination of state of the art techniques for achieving the same security notion.

Combining the two results, we achieve a rich continuum of practical trade-offs between efficiency \& security, connecting the covert, dual-execution and full-malicious guarantees.

Category / Keywords: cryptographic protocols / secure two-party computation

Original Publication (in the same form): IACR-TCC-2015

Date: received 22 Jan 2015, last revised 6 Apr 2015

Contact author: rosulekm at eecs oregonstate edu

Available format(s): PDF | BibTeX Citation

Version: 20150406:203733 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]