Garbled circuits: How can the sender safely retrieve the output?

Question

I've read a few papers about how Yao's Garbled Circuit protocol can be made secure against malicious adversaries, but I haven't seen any mentioning how the sender safely retrieves the output of the function after the receiver computes it.

Suppose Alice is the sender, that is to say she garbles the circuit and sends it to Bob. Now suppose the whole protocol goes fine and at the end Bob outputs the right answer. In the context of two-party secure computation, both parties should be able to obtain the right output of the function, but what if Bob is malicious and doesn't simply send back the answer to Alice?

At that point, Bob could either stop the protocol or send a wrong answer to Alice. Does there exist a mechanism which can both prevent Bob from knowing the output until Alice knows it too, and ensure that what Alice obtains is the right output?

Answer 1

There are two separate issues here:

Guaranteed output / fairness: how does the protocol prevent Bob from withholding Alice's output (guaranteed output), or at least prevent him from learning the output himself when he decides to withhold output from Alice (fairness)? The short answer is that garbled circuit protocols do not provide any such guarantees. The standard definition of malicious security in this area is "security with abort". This model allows a malicious party to learn their output first and subsequently prevent the honest party from receiving output.

The reason for this is that it is impossible to guarantee fairness in general, for 2-party secure computation. This is due to an old result of Richard Cleve (Limits on the security of coin flips when half the processors are faulty, STOC 1986). Since fairness is impossible for some 2-party functions, and garbled circuits give you secure 2PC of any function, you cannot hope for a typical garbled circuit protocol with fairness.

Output authenticity: how does the protocol prevent Bob from lying about the output to Alice, in the case that Bob doesn't withhold her output altogether? There are several approaches but one I like is to just have Bob present the output wire labels back to Alice. Wire labels have an "authenticity" property: the evaluator only learns one on each wire and cannot guess the complementary one. Hence they act as a kind of "proof" to Alice that this was indeed the correct output.

This is the main idea but there are quite a few pitfalls to avoid. It helps if all circuits in the cut-and-choose have the same output wire labels. But then if some of those circuits are opened during cut-and-choose, it breaks the "authenticity" property. So you have to arrange things in a clever order: After Bob evaluates the circuits, he commits to the output wire labels. Then the check-circuits can be opened. If they are all good, only then does Bob open the commitment to the output wire labels.

• Two-output Secure Computation With Malicious Adversaries: abhi shelat and Chih-hao Shen, Eurocrypt 2011 (uses a different technique but focuses explicitly on getting output to the sender)

• Garbled Circuits Checking Garbled Circuits: More Efficient and Secure Two-Party Computation: Payman Mohassel and Ben Riva, Crypto 2013 (uses the wire-label-authenticity idea I mentioned)

• Zero-Knowledge Using Garbled Circuits: Marek Jawurek and Florian Kerschbaum and Claudio Orlandi, CCS 2013 (uses the wire-label-authenticity idea as the basis of a ZK proof: possibly malicious GC evaluator has to convince the GC generator of the circuit's output)