Friday, November 20, 2015

Fast Cut-and-Choose Based Protocol for Malicious Adversary

Yao’s garbled circuit is a well-known technique for secure two-party computation. While it is very efficient in the semi-honest model; in case of malicious adversary, the major challenge is to ensure that the constructed garbled circuit corresponds to the correct function. The cut-and-choose technique of opening and checking s/2 circuits and using the rest as evaluation circuits achieves a cheating probability of  2 -0.32s where s is the number of garbled circuits. To achieve an error probability of 2-40, around 128 garbled circuits need to be constructed which adds heavy communication overhead. In this talk, we shall see a more efficient cut-and-choose technique which achieves a cheating probability of 2-s; thereby 40 circuits suffice to achieve the desired error probability of 2-40.

The main idea of this protocol is that the party P1 who constructs the circuit can cheat only if all the check circuits are correct and all the evaluation circuits are incorrect. The party which evaluates, checks each circuit with a probability of ½, independently of all other circuits. Thus we achieve the cheating probability of 2-s. This is unlike the previous case where only majority of the evaluation circuits needed to be correct. It is important to note why the criteria is to check only if majority of circuits have same output rather than all. Suppose the criteria was for P2 to abort in case it doesn’t receive the same output in all circuits, then it is susceptible to the following attack – A malicious P1 can construct a single incorrect circuit that computes this function: If the first bit of P2’s input is 0, then output random garbage else compute the correct function. Now if this circuit is an evaluation circuit (which happens with probability ½) and P2’s first input bit is 0, then P2 will receive a different output in this circuit and different in the others. He will abort in this case since the output of all evaluation circuits is not consistent. In contrast, if the first input bit of P2 is 1, then he receives the same output in all and doesn’t abort. Based on whether P2 aborts or not, P1 can learn the first bit of P2’s input. To overcome this attack, the criteria is for P2 to take majority value as output. In the new cut-and-choose technique, the output of all the evaluation circuits need to be consistent. To enable this, an additional small secure computation is run after the cut-and-choose phase so that if P2 catches P1 cheating (namely, if P2 receives inconsistent outputs in evaluation circuits) then in the second secure computation it learns P1's full input x. This enables P2 to locally compute the correct output once again. Thus, it is no longer necessary for P2 to take the majority output. The protocol proceeds in two phases as outlined below-

Phase 1 - Cut-and-Choose
-         Parties P1 (with input x) and P2 (with input y) run the usual protocol based on cut-and-choose of garbled circuit secure for malicious adversary. P1 constructs s garbled circuits and each circuit is independently chosen as a check or evaluation circuit with probability ½.
-          If all the circuits evaluated by P2 give the same output z, then P2 stores z locally. Otherwise P2 stores a “proofthat it received two inconsistent output values in two different circuits. Such a proof could be having a garbled value associated with 0 on an output wire in one circuit, and a garbled value associated with 1 on the same output wire in a different circuit. This is a valid proof since if P2 obtains a single consistent output, then the garbled values it receives on an output wire in different circuits are all associated with the same bit.

Phase 2 – Secure Evaluation of Cheating
-         P1 and P2 run a protocol that is secure for malicious adversary with error 2-s (using the previous cut-and-choose protocol with 3s circuits).
-         P1’s input is the same input x used in phase 1. P1 proves that he uses the same x. For this, we use the same mechanism that is used in known protocols to ensure that the same input is used for all the garbled circuits.
-         If P2 had received the consistent output z from all evaluation circuits, he inputs some random value; else his input comprises of the “proof of inconsistent output values”.
-         If P2’s input is a valid proof of inconsistent output values, then P2 receives P1’s input x, else he receives nothing.

Note: In order to make circuit for Phase 2 small for better efficiency, it is necessary to construct all of the output wires in all circuits of Phase 1 so that they have the same garbled values on all output wires. Opening a circuit to check it, reveals both values on an output wire which means that this knowledge can no longer be used as a proof that P1 cheated. Therefore, it is necessary to open and check circuits only after Phase 2.

Output Determination
If P2 received a single output z in phase 1, then P2 outputs z and halts. Otherwise if P2 had received inconsistent outputs in phase 1, then it obtains the value of P1’s input x in phase 2. Using this input x, P2 can locally compute the function output z = f(x, y).

P1 is completely clueless regarding whether z was obtained in phase 1 or locally computed. This prevents the earlier attack that we discussed where P1 could get some information about P2’s input by tweaking a single circuit that computes function dependent on P2’s input. The main problem in that case was that based on whether P2 aborts or not, P1 could conclude about P2’s input. In this case P1 receives the correct output z in both cases and has no indication regarding whether the output was obtained from Phase 1 or 2. Thus the earlier attack will not work in this case.

Analysis of the protocol
P1 corrupt : Suppose P1 is corrupt and does not construct all the garbled circuits correctly. The only scenario in which P2 will get the same wrong output for all the evaluation circuits in Phase 1 is when each check circuit is correct and each evaluation circuit is wrong. This can happen only with probability of 2-s . If all the evaluation circuits are correct, P2 will receive correct output in Phase 1 itself. Now let us analyze the case where there are two different circuits with two different outputs. P2 will obtain a valid proof of cheating and use that to learn x in phase 2, thereby enabling it to locally compute the correct output.
P2 corrupt : The way P2 can cheat is by trying to obtain the input of P1 in phase 2 even though he obtained the correct output in phase 1. However, this is not feasible since all the evaluation circuits would have been consistent (as P1 is honest) and thus P2 will be unable to formulate a valid proof of inconsistency that can be used in Phase 2.

This modified cut-and-choose protocol reduces the number of garbled circuits to be communicated in the maliciously secure Yao’s protocol. It achieves a cheating probability of 2-s with s garbled circuits.