1
$\begingroup$

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?

$\endgroup$

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.