| Abstract | Known protocols for secure two-party computa-tion that are designed to provide full security against malicious
behavior are significantly less efficient than protocols intended
only to thwart semi-honest adversaries. We present a concrete
design and implementation of protocols achieving security
guarantees that are much stronger than are possible with
semi-honest protocols, at minimal extra cost. Specifically, we
consider protocols in which a malicious adversary may learn a
single (arbitrary) bit of additional information about the honest
party’s input. Correctness of the honest party’s output is still
guaranteed. Adapting prior work of Mohassel and Franklin,
the basic idea in our protocols is to conduct two separate
runs of a (specific) semi-honest, garbled-circuit protocol, with
the parties swapping roles, followed by an inexpensive secure
equality test. We provide a rigorous definition and prove that
this protocol leaks no more than one additional bit against a
malicious adversary. In addition, we propose some heuristic
enhancements to reduce the overall information a cheating
adversary learns. Our experiments show that protocols meeting
this security level can be implemented at cost very close to
that of protocols that only achieve semi-honest security. Our
results indicate that this model enables the large-scale, practical
applications possible within the semi-honest security model,
while providing stronger security guarantees.
|
