4
$\begingroup$

I'm currently reading the book "A Pragmatic Introduction to Secure Multi-Party Computation". On pages 103-104 I came across the following related to the Cut-and-Choose technique:

If $P_2$ sees inconsistent outputs, then it is obvious to $P_2$ that $P_1$ is misbehaving. It is tempting to suggest that $P_2$ should abort in this case. However, to do so would be insecure! Suppose $P_1$’s incorrect circuits are designed to be selectively incorrect in a way that depends on $P_2$’s input. For example, suppose an incorrect circuit gives the wrong answer if the first bit of $P_2$’s input is 1. Then, $P_2$ will only see disagreeing outputs if its first bit of input is 1. If $P_2$ aborts in this case, the abort will then leak the first bit of its input. So we are in a situation where $P_2$ knows for certain that $P_1$ is cheating, but must continue as if there was no problem to avoid leaking information about its input.

To add some context to the above. They are referring to the naive Cut-and-Choose technique where $P_1$ is the garbled circuit generator and $P_2$ is the evaluator. So $P_1$ generates a bunch of GC for the preagreed function $f$ and sends them to $P_2$. Then $P_2$ chooses which of them to open based on a random coin and tells $P_1$ to open them, e.g. send all the corresponding wire labels (keys) for $P_2$ to be able to reconstruct the Look-up Table and check if it is equal to the pre-agreed one.

How can $P_1$ create an incorrect circuit that depends on the $P_2$ input so it can reveal information about it?

$\endgroup$

1 Answer 1

2
$\begingroup$

$P_1$ garbles the circuit, so he can manipulate it (e.g. swap AND and OR gates) since $P_2$ only receives permuted encrypted truth tables.

In particular, $P_1$ could add an "if-else" gate s.t. the correct output is XORed with hardcoded random noise iff the first bit of $P_2$ is one.

If $P_2$ chooses this manipulated circuit and therfore aborts, $P_1$ learns that $P_2$'s first bit is zero.

$\endgroup$

Your Answer

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

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