[Resource Topic] 2015/055: Richer Efficiency/Security Trade-offs in 2PC

Welcome to the resource topic for 2015/055

Richer Efficiency/Security Trade-offs in 2PC

Authors: Vladimir Kolesnikov, Payman Mohassel, Ben Riva, Mike Rosulek


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.

ePrint: https://eprint.iacr.org/2015/055

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .