Leaking information for giving the yao's garbled circuit's garbled output

Question

I am currently reading the paper: Efficiency Tradeoffs for Malicious Two-Party Computation. The paper describes a $k$-leak model and gives an example that leaking 1 bit could turn Yao's garbled circuit from semi-honest resistance to malicious resistance.

At page 14, it says that Alice gives it garbled output to Bob --- the garbled circuit creator. But won't Bob re-construct all Alice input by Alice's garbled output and the transition table (since Bob is the circuit creator)?

How this exactly leaks only 1 bit of input?

Answer 1

The description on page 14 is confusing to me too. I believe the important thing to note is that the paper proposes to use a "conditional disclosure of secrets" protocol, citing [AIR01]. So when the outline says:

Alice discloses $W_a$ to Bob if $O_1 = O_2$, and a random value $r_a \in \{0, 1\}^{|W_a|}$ otherwise.

.. the word "discloses" is probably meant to refer to a conditional disclosure protocol, not just simply sending $W_a$. If Alice sends $W_a$ to Bob, then you are right, Bob can learn Alice's circuit output which is more than one bit of leakage.

There have been many papers building on this classic dual-execution paradigm. Based on those papers, I would recommend the following very simple way of performing the final stage of dual-execution, as long as you are OK with a random oracle. Regarding notation, let $[x]_A$ denote a garbled output encoding of $x$, in an encoding chosen by Alice.

1. Alice evaluates Bob's circuit to get output $O_1$ and its garbled output $[O_1]_B$. Alice knows the encoding she used for her own circuit outputs so she can also compute $[O_1]_A$
2. Bob evaluates Alice's circuit to get output $O_2$ and its garbled encoding $[O_2]_A$. Bob knows the encoding he used for his own circuit outputs so he can also compute $[O_2]_B$
3. Alice computes $h_A = H( [O_1]_A, [O_1]_B )$ and sends it to Bob.
4. Bob computes $h_B = H( [O_2]_A, [O_2]_B )$. If $h_A = h_B$ he accepts the output $O_2$, otherwise he aborts.

If Alice is honest and Bob is corrupt, Bob can learn only a single garbled output $[\cdot]_A$ under Alice's encoding, by the authenticity property of Alice's garbled circuit. So Bob cannot query $H$ on any valid encoding $[x]_A$ except for $[O_2]_A$. If $O_1 \ne O_2$ then Bob can never query $H$ at the same point that Alice did, so her value $h_A$ looks uniformly random to Bob. I.e., it doesn't leak any information about $O_1$ other than the fact that $O_1 \ne O_2$.

I have focused on how to convince Bob that the output is correct. To convince Alice also, you must do the same hash comparison in both directions. But you can't use exactly the same hash function calls in both directions -- use a different nonce for the "hash calls to convince Alice" vs "hash calls to convince Bob."