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}^{n}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*^{2}*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.
## No comments:

## Post a Comment