Two-Output Secure Computation with Malicious Adversaries

abhi shelat; Chih-hao Shen

Paper 2011/533

Two-Output Secure Computation with Malicious Adversaries

abhi shelat and Chih-hao Shen

Abstract

We present a method to compile Yao's two-player garbled circuit protocol into one that is secure against malicious adversaries that relies on witness indistinguishability. Our approach can enjoy lower communication and computation overhead than methods based on cut-and-choose and lower overhead than methods based on zero-knowledge proofs (or sigma-protocols). To do so, we develop and analyze new solutions to issues arising with this transformation: - How to guarantee the generator’s input consistency - How to support different outputs for each player without adding extra gates to the circuit of the function f being computed - How the evaluator can retrieve input keys but avoid selective failure attacks - Challenging 3/5 of the circuits is near optimal for cut-and-choose (and better than challenging 1/2) Our protocols require the existence of secure-OT and claw-free functions that have a weak malleability property. We discuss an experimental implementation of our protocol to validate our efficiency claims.

Note: remove an redundant table and a repeat section

Metadata

Available format(s): PDF
Category: Applications
Publication info: Published elsewhere. full version of our EUROCRYPT'11 paper
Contact author(s): shench @ virginia edu
History: 2011-10-01: last of 2 revisions; 2011-10-01: received; See all versions
Short URL: https://ia.cr/2011/533
License: CC BY

BibTeX

@misc{cryptoeprint:2011/533,
      author = {abhi shelat and Chih-hao Shen},
      title = {Two-Output Secure Computation with Malicious Adversaries},
      howpublished = {Cryptology {ePrint} Archive, Paper 2011/533},
      year = {2011},
      url = {https://eprint.iacr.org/2011/533}
}