Score:2

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

cn flag

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?

Maarten Bodewes avatar
in flag
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 :)
js wang avatar
cn flag
@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 :)
Maarten Bodewes avatar
in flag
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.
Score:1
us flag

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

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.