Yao’s garbled circuit is a wellknown
technique for secure twoparty computation. While it is very efficient in the
semihonest model; in case of malicious adversary, the major challenge is to
ensure that the constructed garbled circuit corresponds to the correct
function. The cutandchoose 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 cutandchoose 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_{1} 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_{2} 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_{1}
can construct a single incorrect circuit that computes this function: If the
first bit of P_{2}’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_{2}’s first input bit is 0,
then P_{2} 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_{2}
is 1, then he receives the same output in all and doesn’t abort. Based on whether P_{2} aborts or
not, P_{1} can learn the first bit of P_{2}’s input. To
overcome this attack, the criteria is for P_{2} to take majority value
as output. In the new cutandchoose technique, the output of all the evaluation circuits
need to be consistent. To enable this, an
additional small secure computation is run after the cutandchoose phase
so that if P_{2} catches P_{1} cheating (namely, if P_{2}
receives inconsistent outputs in evaluation circuits) then in the second secure
computation it learns P_{1}'s full input x. This enables P_{2} to locally compute the correct output
once again. Thus, it is no longer necessary for P_{2} to take the
majority output. The protocol proceeds in two phases as outlined below
Phase
1  CutandChoose

Parties
P_{1} (with input x) and P_{2}
(with input y) run the usual protocol based on cutandchoose of garbled
circuit secure for malicious adversary. P_{1} 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_{2}
give the same output z, then P_{2}
stores z locally. Otherwise P_{2}
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_{2}
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_{1}
and P_{2} run a protocol that is secure for malicious adversary with
error 2^{s }(using the previous cutandchoose protocol with 3s circuits).

P_{1}’s
input is the same input x used in
phase 1. P_{1} 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_{2} 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_{2}’s input is a valid proof of inconsistent output values, then P_{2}
receives P_{1}’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_{1} cheated. Therefore, it
is necessary to open and check circuits only after Phase 2.
Output Determination
If P_{2}
received a single output z in phase
1, then P_{2 }outputs z and
halts. Otherwise if P_{2} had received inconsistent outputs in phase 1,
then it obtains the value of P_{1}’s input x in phase 2. Using this input x,
P_{2} can locally compute the function output z = f(x, y).
P_{1} is completely
clueless regarding whether z was
obtained in phase 1 or locally computed. This prevents the earlier attack that
we discussed where P_{1} could get some information about P_{2}’s
input by tweaking a single circuit that computes function dependent on P_{2}’s input. The
main problem in that case was that based on whether P_{2} aborts or
not, P_{1} could conclude about P_{2}’s input. In this case P_{1}
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_{1}
corrupt
: Suppose P_{1} is corrupt and does not construct all the garbled
circuits correctly. The only scenario in which P_{2} 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_{2} 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_{2} 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_{2}
corrupt
: The way P_{2} can cheat is by trying to obtain the input of P_{1}
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_{1} is honest) and thus P_{2} will be unable to formulate
a valid proof of inconsistency that can be used in Phase 2.
This modified cutandchoose
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.
No comments:
Post a Comment