2
$\begingroup$

Two semi-honest parties are computing F with Yao's garbled circuit. Sender garbles it with his inputs baked in then sends it to the receiver. At this point the receiver must use OT to get his keys. What happens if OT breaks and the receiver gets both keys for every wire? It's not clear to me that this would break the sender's input privacy.

$\endgroup$
5
$\begingroup$

The problem is because sender has provided the receiver with a garbled circuit in which the sender's inputs are hard coded (or has provided keys for those inputs, which is morally the same). If the receiver has both keys for each input wire then it is trivial to narrow down the possible values of the sender's input.

Consider a concrete example, the millioniar's problem. In this problem the sender constructs a circuit that returns $1$ if the resulting value is less than or equal to the sender's wealth. If the receiver has the circuit and all input keys then it effectively has a function $f : Z_n \rightarrow Z_2$. Through trial and error we can find the sender's wealth, $X \in Z_n$ where $f(X) = 1 \wedge f(X+1) = 0$.

$\endgroup$
5
$\begingroup$

Here is a concrete example of how the receiver could extract information about the senders input:

Assume the circuit to be evaluated is the simple circuit computing $(x \oplus (y \wedge z)) = w$, where $x, y$ is the input of the sender and $z$ the input of the receiver. Note, that $w$ and $z$ alone does not reveal the value of $y$ (you can write down the truth-table to verify this).

However, if the receiver has both keys for his input $z$ he can evaluate the the garbled gate representing $y \wedge z$ for both values of $z$. Now, if $y = 0$ the receiver will obtain the same key when evaluating this gate no matter the value of $z$. If $y = 1$ the receiver will obtain different keys depending on the value of $z$. This way the receiver learns $y$, i.e., obtains more information about the senders input than he is supposed to and breaking the security of the scheme.

$\endgroup$

Your Answer

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

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