6.897: Selected Topics in Cryptography March 13, 2004Lecture 12Lecturer: Ran Canetti Scribe: Dah-Yoh Lim1 RecapLast lecture we started to look at how we could realize any two-party functionality for any numberof faults in the FCRS-hybrid model. In this lecture we will finish this discussion and extend it tothe multi-party case. We will also note that we can get rid of the CRS in the case of an honestmajority. All the material in this lecture is taken from [CLOS02].In more detail, we follow the [GMW87] paradigm of first constructing a protocol secure againstsemi-honest adversaries (i.e., even the corrupted parties follow the protocol specification), thenconstructing a general compiler that transforms protocols secure against semi-honest adversariesto “equivalent” protocols secure against Byzantine adversaries.In the previous lecture we presented the ideal oblivious transfer functionality, FOT. In thislecture we will show how to realize FOTfor semi-honest adversaries in the plain model, and showhow to realize any functionality in the FOT-hybrid model.1.1 The Semi-honest Adversarial ModelRecall that there are two natural variants of the semi-honest adversarial model. In the first variantthe adversaries can change the inputs of the corrupted parties, but are otherwise passive. In thesecond variant the environment talks directly with the parties, and the adversaries only li sten(cannot even change the inputs). These variants are incomparable, because there are protocolssecure under one model but insecure under the other. We will actually need the first variant forthe compiler, but the protocol we are going to see shortly is secure under both variants.1.2 Standard FunctionalitiesRecall that in lecture 8 we defined “standard functionalities” as the functionalities which do notutilize their direct knowledge of the identities of the corrupt parties. Specifically, it consists ofan “outer shell” and a “core”. The core is an arbitrary probabilistic polynomial-time algorithm,while the shell is a simple interfacing procedure described as follows. The shell forwards anyincoming messages to the core, with the exception that notifications of corruptions of parties arenot forwarded to the core. Outgoing messages generated by the core are copied by the shell to thesubroutine output tape of the recipient. On top of these, S is allowed to delay the receiving ofinputs and sending of outputs: the shell actually notifies S about its intentions, and only carrieson to do so when S OKs it. In handling cor ruptions the shell hands an output “corrupted” to theparty that S wants to corrupt, and hands S all the I/O history so far of the corrupted party. Fromnow on all of the corrupt party’s I/O privileges is taken over by S.Notice that under this restriction we avoid the problem of not being able to realize functionalitiesthat use the knowledge of the identities of the corrupt parties in an essential way. For example,consider the ideal functionality that lets all parties know which parties are corrupted. Then this12-1functionality cannot be realized in the face of an adversary that corrupts a single random partybut instructs that party to continue following the prescribed protocol.All the functionalities following are standard ones.2 Evaluating General Functionalities in the Semi-honest, Two-party caseHere, we follow the [GMW87] paradigm. However, there are two differences. Firstly, [GMW87]considers static adversaries whereas we consider adaptive adversaries. This only makes a differencein the oblivious transfer protocol, but still the proof of security is significantly different. Thesecond difference is that [GMW87] considers function evaluation, whereas we consider more generalreactive functionalities where parties may receive new inputs during the protocol execution andeach new input may depend on the current adversarial view of the system. This only makes a smalldifference to the construction.Since we are talking about standard functionalities in which the shell is merely an interface,we will deal with the core only. Let F be an ideal two-party functionality and P0, P1be theparticipating parties.Preliminary step: Represent the ideal functionality F as a Boolean circuit.Before we can start to construct a protocol that UC-realizes F, we first represent (the core of)F via a family CFof boolean circuits (the k-th circuit in the family describes an activation ofF when the security parameter is set to k). Following [GMW87], we use arithmetic circuitsover GF(2) where the operations are addition and multiplication modulo 2.There are five types of input lines: inputs of P0, inputs of P1, inputs of S, random inputs,and local-state inputs. There are four types of output lines: outputs to P0, outputs to P1,outputs to S, and the local state for the next activation.Step 1: Input sharing. When Piis activated with new input, it notifies P1−iand does thefollowing: Firstly it shares each input bit b with P1−iby sending b1−i←R{0, 1} to P1−iandkeeping bi= b + b1−i. Secondly, for each random input line, it chooses ri←R{0, 1}. Theshares of the input lines of P1−iare set to 0.In addition, Pihas its share siof each local state line s from the previous activation. (Initially,these shares are set to 0.) Pi’s shares of the adversary input lines are set to 0. When Piisactivated by notification from P1−iit proceeds as above, except that it sets its inputs to be0. Note that at this point, the values of all input lines to the circuit are shared between theparties.Step 2: Evaluating the circuit. Let a, b denote the input values of the gate, and let c denotethe output value. So Piholds bits aiand bi(whereas P1−iholds bits a1−iand b1−i, such thata = ai+ a1−iand b = bi+ b1−i). The parties evaluate the circuit gate by gate, so that theoutput value of each gate is shared between the parties, as follows.• Addition gates: we want to perform the computation a + b = c in a shared manner, i.e.so that Piholds ciand P1−iholds c1−isuch that ci+ c1−i= c. Since Pihas aiand bi, itsimply computes ci= ai+ bi. (Since a0+ a1= a and b0+ b1= b, we have c0+ c1= c.)12-2• Multiplication gates: we want to perform the computation a ∗ b = c in a shared manner,i.e. so that Piholds ciand P1−iholds c1−isuch that ci+ c1−i= c. P0and P1use F4OTas follows: P0chooses c0at random, and plays the sender with input:v00= a0b0+ c0, v01= a0(1 − b0) + c0, v10= (1 − a0)b0+ c0, v11= (1 − a0)(1 − b0) +