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?

  • $\begingroup$ Small hint for creating posts: just keep to the markdown format / editing icons to format your question. That's both easier for you and for us. Thanks :) $\endgroup$
    – Maarten Bodewes
    Feb 13, 2022 at 10:03
  • $\begingroup$ @MaartenBodewes, thanks for editing. But how could I do the "keep to the markdown format / editing icons"? Sorry to ask this stupid question, I am new to this community :) $\endgroup$
    – js wang
    Feb 13, 2022 at 19:59
  • $\begingroup$ If you are editing your post there should be a row of icons on top of that post, with a B for Bold, I for Italics, etc. These will insert markdown marks such as ** for bold and a single * for italics respectively. Please maintain a newline between sections and don't use <br> for visual line breaks in normally formatted text. $\endgroup$
    – Maarten Bodewes
    Feb 14, 2022 at 8:09

1 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."


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.