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 P₁ 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 P₂ to abort in case it doesn’t receive the same output in all circuits, then it is susceptible to the following attack – A malicious P₁ can construct a single incorrect circuit that computes this function: If the first bit of P₂’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 P₂’s first input bit is 0, then P₂ 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 P₂ is 1, then he receives the same output in all and doesn’t abort. Based on whether P₂ aborts or not, P₁ can learn the first bit of P₂’s input. To overcome this attack, the criteria is for P₂ 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 P₂ catches P₁ cheating (namely, if P₂ receives inconsistent outputs in evaluation circuits) then in the second secure computation it learns P₁'s full input x. This enables P₂ to locally compute the correct output once again. Thus, it is no longer necessary for P₂ to take the majority output. The protocol proceeds in two phases as outlined below-

      Phase 1 - Cut-and-Choose  

-         Parties P₁ (with input x) and P₂ (with input y) run the usual protocol based on cut-and-choose of garbled circuit secure for malicious adversary. P₁ constructs s garbled circuits and each circuit is independently chosen as a check or evaluation circuit with probability ½.

-          If all the circuits evaluated by P₂ give the same output z, then P₂ stores z locally. Otherwise P₂ stores a “proof” that 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 P₂ 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     

-         P₁ and P₂ run a protocol that is secure for malicious adversary with error 2^-s (using the previous cut-and-choose protocol with 3s circuits).

-         P₁’s input is the same input x used in phase 1. P₁ 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 P₂ 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 P₂’s input is a valid proof of inconsistent output values, then P₂ receives P₁’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 P₁ cheated. Therefore, it is necessary to open and check circuits only after Phase 2.

Output Determination

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

P₁ is completely clueless regarding whether z was obtained in phase 1 or locally computed. This prevents the earlier attack that we discussed where P₁ could get some information about P₂’s input by tweaking a single circuit that computes function dependent on P₂’s input. The main problem in that case was that based on whether P₂ aborts or not, P₁ could conclude about P₂’s input. In this case P₁ 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

 P₁ corrupt : Suppose P₁ is corrupt and does not construct all the garbled circuits correctly. The only scenario in which P₂ 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, P₂ will receive correct output in Phase 1 itself. Now let us analyze the case where there are two different circuits with two different outputs. P₂ 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.

 P₂ corrupt : The way P₂ can cheat is by trying to obtain the input of P₁ 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 P₁ is honest) and thus P₂ 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.