0
$\begingroup$

In a lecture I was told of a a possibility to modify Yao's Garbled Circuit Protocol so that both parties in the end get each a part of the output but not the other part. This may be achieved by manipulating the Circuit.

Does anybody have some hints how this can be done?

Thanks in advance.

$\endgroup$
5
$\begingroup$

Suppose you want Alice to learn $f_A(x,y)$ and Bob to learn $f_B(x,y)$. Then have Alice choose random string $r_A$ and have Bob choose random string $r_B$. The parties should perform a secure computation where both parties learn $(f_A(x,y) \oplus r_A, f_B(x,y) \oplus r_B)$. Basically each party's designated output is masked by a one-time pad that only that party knows.

$\endgroup$
  • $\begingroup$ Hello, I am also interested in this. Can you explain how you have to modify the input to get Alice and Bob to learn $(f_A(x,y)\oplus r_A, f_B(x,y)\oplus f_B)$? $\endgroup$ – Marc Jun 13 '17 at 18:39
  • $\begingroup$ Nothing to modify, you run Yao's protocol on a circuit $g$ that takes $(x,r_A)$ from Alice, input $(y,r_B)$ from Bob, and computes $g(x,r_A,y,r_B) = (f_A(x,y)\oplus r_A, f_B(x,y) \oplus r_B)$, giving this output to both parties. $\endgroup$ – Mikero Jun 13 '17 at 20:11
2
$\begingroup$

I will give a possible solution in the semi-honest model (though possibly not the best one), but note that this is a modification of the protocol and not of the circuit. I assume Yao with point and permute, i.e., there is a random bit for each wire, and during evaluation, the evaluator learns the key and an "external value", which is just the real value XORed with the random bit (the evaluator uses this external value to know which row to decrypt at each gate, but in general cannot learn anything from it as it is independent of the real value).

1) For the output wires of the evaluator, the garbler also supplies the evaluator with the random permutation bits. Therefore, the evaluator can learn the real value of these wires from the external values. Then, the evaluator can simply not send the outputs it learnt back to the garbler.

2) For the outputs of the garbler, the evaluator does not have the permutation bits. However, it does learn the external values (and the keys). So the evaluator sends the external values back to the garbler, which of course does know the random permutation bit, so learns the true outputs.

Of course, (2) is possible also in Yao without point and permute, by letting the evaluator send back the keys (of the outputs of the garbler) back to the garbler.

I don't know how the solution would work in the malicious model, but I suppose it also depends how you go from semi-honest to malicious.

$\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.