Active two-party computation

A large number of protocols have been proposed in the last few years for active secure two-party computation. One significant approach is based on Yao’s garbled circuit. We have already discussed garbled circuit technique previously in this blog. Informally speaking, in the standard protocol the two parties, Alice and Bob, work asymmetrically: one party (say Alice), also called the generator, constructs a garbled circuit computing the original function f, and sends it to Bob, the evaluator. He evaluates the garbled circuit producing the output f(x,y), where x and y in {0,1}ⁿ are the private inputs of Alice and Bob, respectively. A garbled circuit (GC) is nothing but an “encrypted” circuit: along with the GC the evaluator receives “random” keys corresponding to his input bits y_i; then he computes their encryption obliviously via 1-out-of-2 OTs and evaluates the circuit.

To achieve active security the “cut-and-choose” paradigm is often used. Alice produces many garbled circuits, then Bob asks Alice to open a fixed fraction of them (typically an half). He aborts if any of these check-circuits are inconsistent; otherwise he evaluates the remaining ones (the evaluation-circuits) and chooses the majority of their results as final output. While cut-and-choose solves the problem of corrupted Alice constructing the garbled circuits incorrectly, it produces some well-known byproducts. Mainly we need to ensure that the parties use the same inputs in all the evaluations. Many different approaches have been proposed to address the problems related with the cut-and-choose paradigm and malicious adversary.

In our last study group, led by Enrique, we consider three different papers LP07, LP11 and  L13. In LP07 the authors firstly provide an implementation and a full proof of security for active secure Yao’s protocol based on cut-and-choose. To ensure Alice’s input consistency they proposed an approach requiring O(s²n) commitments, where s is the statistical parameter of cut-and-choose and n is the input size. Another problem is the so called selective failure attack: a corrupted Alice could provide inconsistent random key to the Bob's input wire and its associated OT, gaining information about Bob's input. The suggested solution in LP07 requires a larger circuit and an encoding of the input bits.

We recall that Bob cannot abort even if he knows that Alice is cheating, i.e. in the case that the evaluation-circuits do not all provide the same result, and that this is the reason he takes the majority output. Now suppose that the total number of garbled circuits is s and that an half of these are opened. An adversary succeeds if s/4 circuits are incorrect and none of them is checked. So Alice can cheat with probability at most 2^-s/4. In LP07 the authors prove a bound for the error probability of 2^-s/17 . In practice this means that to achieve an error of 2^-40 we need to construct and exchange 680 circuits.

In LP11 this bound is improved to 2^-0.311s. In this work the authors not only decrease the number of circuits (132 to have an error of 2^-40), but they also remove the commitments and the necessity to encode the bit's input, incorporating the checking on the circuits and the OT. In order to obtain this result they define a new functionality, the cut-and-choose OT functionality. Their implementation is based on an instantiation of the OT protocol from PVW08 based on the DDH assumption; however while the protocol in [PVW08] is in the common reference string model, the protocol in LP11 is in the plain model.

The major drawback of this approach still remains the large number of OT needed. In LP13 the author specifically handles this issue. The main idea here is that Alice can only act incorrectly by making all of the check-circuits correct and all of the evaluation-circuits incorrect (not just the majority). If this holds, the probability that each circuit is independently chosen to be an evaluation or a check circuit is 1/2, and the probability of Alice to cheat is exactly 2^-s. This implies that to obtain an error probability of 2^-40 we need 40 circuits! This result is obtained using a "proof of cheating": if Bob obtains two different values in the evaluation phase, he is able to produce a proof that he received inconsistent outputs. Then if this proof is effectively valid, he receives Alice's input and can evaluate the circuit correctly.