Suppose that Alice has a secret bit $a$ and Bob has a secret bits $b_1,b_2$ and that Alice and Bob want to compute the function $h(a,b_1,b_2)=b_1 \wedge (b_2 \oplus a)$ using Yao's Garbled Circuit protocol.

a) Suppose that Alice selects two random permutations $\pi_1, \pi_2: \{(0,0),(0,1),(1,0),(1,1)\} \to \{(0,0),(0,1),(1,0),(1,1)\}$. Write down the garbled circuit that Alice sends Bob.

b) Suppose that Alice is malicious, but Bob behaves honestly during the execution of the protocol. Write down a garbled circuit that Alice can send Bob to extract the secret bit $b_1$ directly.

I was able to work out complete part (a), but I can't wrap my head on how to deal with the fact Alice is malicious. When she is malicious,

  • She does not garbled the circuit at all or for $h$.
  • She can stop midway in the garbling process
  • She can not return Bob query about his bit.

Can someone help me understand this?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.