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

Improve this question
$\endgroup$

2 Answers 2

Reset to default
4
$\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.

Improve this answer
$\endgroup$
2
  • $\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, 2017 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, 2017 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.

Improve this answer
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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