Effcient Non-Interactive Secure Computation

From Bauman National Library
This page was last modified on 22 December 2015, at 05:17.
Efficient Non-interactive Secure Computation
Towards a Game Theoretic View of Secure Computation.png
Authors Yuval Ishai1 [@: 1] ,
Eyal Kushilevitz [@: 2] ,
Rafail Ostrovsky [@: 3]
Manoj Prabhakaran [@: 4]
Published 2011
Download Original paper


Abstract. Suppose that a receiver R wishes to publish an encryption of her secret input x so that every sender S, holding an input y, can reveal f(x; y) to R by sending her a single message. This should be done while simultaneously protecting the secrecy of y against a corrupted R and preventing a corrupted S from having an unfair influence on the output of R beyond what is allowed by f. When the parties are semi-honest, practical solutions can be based on Yao’s garbled circuit technique. However, for the general problem when the parties, or even S alone, may be malicious, all known polynomial-time solutions are highly inefficient. This is due in part to the fact that known solutions make a non-black-box use of cryptographic primitives, e.g., for providing non-interactive zero-knowledge proofs of statements involving cryptographic computations on secrets.

Motivated by the above question, we consider the problem of secure two-party computation in a model that allows only parallel calls to an ideal oblivious transfer (OT) oracle with no additional interaction. We obtain the following results.

  • Feasibility. We present the first general protocols in this model which only make a black-box use of a pseudorandom generator (PRG). All previous OT-based protocols either make a non-black-box use of cryptographic primitives or require multiple rounds of interaction.
  • Efficiency.We also consider the question of minimizing the asymptotic number of PRG calls made by such protocols.We show that calls are sufficient for each gate in a (large) boolean circuit computing f, where k is a statistical security parameter guaranteeing at most simulation error of a malicious sender. Furthermore, the number of PRG calls per gate can be made constant by settling for a relaxed notion of security which allows a malicious S to arbitrarily correlate the event that R detects cheating with the input of R. This improves over the state of the art also for interactive constant-round black-box protocols, which required PRG calls per gate, even with similar relaxations of the notion of security.

Combining the above results with 2-message (parallel) OT protocols in the CRS model, we get the first solutions to the initial motivating question which only make a black-box use of standard cryptographic primitives.


This work is motivated by the following variant of the problem of computing on encrypted data [1] [2]. Suppose that a receiver R wishes to publish a semantically secure encryption of her secret input x so that any sender S, holding an input y, can reveal f(x; y) to R by sending her a single message. (The message can be seen as an encryption of f(x; y) that the receiver can decrypt.)We want this process to protect the secrecy of y against a corrupted R and, at the same time, prevent a corrupted S from having an unfair influence on the output of R beyond what is allowed by f. We refer to this flavor of computing on encrypted data as non-interactive secure computation (NISC).

As a concrete motivating scenario for NISC, consider a receiver Roberta who wishes to publish an encrypted version of her personal profile x on her public web page towards finding a suitable partner for dating. A solution to our problem would allow an arbitrary sender Sam, with personal profile y, to send an email message to Roberta which reveals his verifiable contact information only if the two profiles match. (The matching criteria can either be determined by a public algorithm which is embedded into f, or alternatively specified in Roberta’s secret profile.) In order to protect the secrecy of Roberta’s profile x, its encryption should be semantically secure. In order to protect the secrecy of Sam’s profile y, he should be ensured that no information is revealed to Roberta other than what is implied by the output of f. Finally, to help protect Roberta against eager senders who try to force a match, she should be ensured that every strategy of such a sender corresponds to some valid profile y.

Standard techniques for secure computation and computing on encrypted data perform quite well when the parties are guaranteed to be semi-honest. For instance, practical NISC protocols in this setting can be obtained by combining Yao’s garbled circuit technique [3] [4] and any two-message oblivious transfer (OT) protocol [5] [6]. Lowcommunication (but at this point less practical) solutions can be obtained using homomorphic encryption for general functions [7] or for restricted classes of functions [8] [9] [10] [11].

For some of the above protocols, protecting S against a malicious R can come at a relatively low cost. In protocols based on Yao’s construction this can be done (in the CRS model) by using efficient 2-message UC-secure OT protocols [12] (see also [13]). However, known techniques for protecting R against a malicious S either involve additional rounds of interaction [14] or are highly inefficient. For instance, this is the case if S is required to prove, using non-interactive zero-knowledge (NIZK), that he constructed a valid garbled circuit [5] [15]). Such proofs seem very costly even with the best known NIZK techniques. Moreover, even from a qualitative point of view, such NIZK-based solutions leave much to be desired in that they inherently require to make a non-black-box use of the underlying cryptographic primitives [5] [15]. For instance, while the semi-honest version of Yao’s protocol can be implemented by making a black-box use of (parallel) 2-message OT and a pseudorandom generator (PRG), this is not the case for a NIZK-based variant which is secure against malicious senders.

The above state of affairs motivates the study of NISC protocols which only make a black-box use of standard cryptographic primitives.We further simplify the problem by allowing S and R to engage in parallel invocations of an ideal OT oracle, but without allowing any additional interaction.4 We refer to such a protocol as a NISC protocol in the OT-hybrid model, or NISC/OT protocol for short. More formally, a NISC/OT protocol for is a protocol which UC-securely realizes f using only parallel calls to an ideal OT oracle.

Our main motivation for considering this a good model for NISC is the aforementioned existence of efficient UC-secure 2-message implementations of OT in the CRS model. Indeed, using the UC composition theorem [16], NISC/OT protocols can be combined with such 2-message OT protocols to yield NISC protocols in the CRS model that have the same communication pattern as in the initial motivating example.

Additional advantages of OT-based protocols include the generality advantage of being able to realize OT in a variety of models and under a variety of standard assumptions, as well as efficiency advantages such as the possibility of precomputing the necessary OTs [17] [18] and the possibility to amortize the cost of this precomputation [19] [20] [21]. См. [22] for further discussion.

We turn to the feasibility question of minimizing the assumptions on which NISC/OT protocols can be based. In the OT-hybrid model, any polynomial-time computable functionality can be efficiently realized unconditionally [23] [21] [22]. However, it is wide open whether the same is true for constant-round protocols. (This question is related to the corresponding question in the honest-majority MPC setting [24], which in turn is related to other wide open questions [25].) Given the lack of progress on this front, a second best alternative is to base general NISC/OT protocols on any one-way function, or equivalently a PRG. As noted above, Yao’s protocol provides such a solution in the semi-honest model. Moreover, it is shown in [22] (see Appendix B of [26]) how to get a similar protocol in the malicious NISC/OT model; however, this protocol inherently makes a non-black-box use of the PRG. This motivates the following main question:

Are there NISC/OT protocols for general functions which only make a blackbox use of a PRG?

A second goal of this work is to push the asymptotic efficiency limits of constantround black-box protocols by minimizing the number of calls to the underlying cryptographic primitive. Existing constant-round black-box protocols in the OT-hybrid model (such as [27] [14] and their variants) require calls to a PRG (or symmetric encryption) for each gate in the circuit, where k is a statistical security parameter guaranteeing at most simulation error for a malicious sender.5 This should be compared to the best protocols in the semi-honest model [3] [4] which require only PRG calls per gate.

Our Results

We obtain the following main results.

  • Feasibility. We present the first general NISC/OT protocols which only make a

black-box use of a PRG. All previous protocols in the OT-hybrid model either make a non-black-box use of cryptographic primitives [22] or require multiple rounds of interaction (cf. [14]).

  • Efficiency. We also consider the question of minimizing the asymptotic number of

PRG calls made by such protocols.We show that calls are sufficient for each gate in a (large) boolean circuit computing f, where k is a statistical security parameter guaranteeing at most simulation error of a malicious sender.6 Furthermore, the number of PRG calls per gate can be made constant by settling for a relaxed notion of security which allows a malicious S to arbitrarily correlate the event that R detects cheating with the input of R. This improves over the state of the art also for interactive constant-round black-box protocols, which required 2-Ω(κ) PRG calls per gate, even with similar relaxations of the notion of security.

Combining the above results with 2-message (parallel) OT protocols in the CRS model, we get the first solutions to the initial motivating question which only make a black-box use of standard cryptographic primitives. On re-using public keys. A standard security caveat that applies to many non-interactive protocols in the public key model (cf. [28][29][30][31]) is that re-using the same receiver’s public key for multiple sender messages may be problematic if the sender can learn the receiver’s output on these messages. Indeed, the standard (UC-)security guarantee of our protocols only applies when an independent receiver message is used in each session. While the receiver’s output does not reveal additional information about the receiver’s input (other than what is allowed by f), it may reveal information about the secret randomness embedded in the public key, which may in turn compromise the receiver’s security when leaking multiple outputs without refreshing the public key. Our protocols are indeed susceptible to this type of attacks.

We stress that re-using the same public key for multiple sender messages is always safe (in the sense of providing the natural “real-ideal” security guarantee) if the receiver refreshes the public key after revealing an output or using it in another protocol. This seems to be a very mild requirement in many practical scenarios in which sender messages are infrequent or can be aggregated before taking any action.

Similarly to [31], we can provide t-time reusable public keys (for which up to t outputs can be revealed before the key needs to be refreshed) at a much better cost than publishing t independent public keys. We note, however, that (non-black-box) NIZKbased NISC protocols are not susceptible at all to this type of attacks, and leave the possibility of obtaining a similar result using black-box constructions as an interesting open question.

On asymptotic vs. practical efficiency. As is usual in theoretical work in cryptography, we focus on optimizing asymptotic efficiency and do not try to optimize or even analyze the underlying hidden constants. Moreover, in doing so we focus on the typical case where the circuit size is much bigger than the input size which in turn is much bigger than the security parameter, and sometimes ignore low-order additive terms that depend on the smaller quantities. These optimization goals may conflict with practical efficiency. The question of optimizing NISC protocols towards practical implementations is left for future work.

Overview of Techniques

At a high level, our NISC/OT protocols are obtained using the following modular steps:

  1. Statistically secure NISC/OT protocols for functions. Here we can rely on a

previous protocol from [22] (see Appendix B of [26]). We also present an asymptotic efficiency improvement by applying “MPC in the head” techniques in the spirit of [32]. This is presented in Section 3.

  1. Computationally secure NISC protocols for general functions in the -hybrid

model (allowing the parties a single call to an ideal functionality). Here we combine a particular implementation of Yao’s garbled circuit construction with the use of unconditional one-time MACs to guarantee that a malicious sender can either deliver a correct output to the receiver or the receiver detects cheating and aborts. However, these protocols allow a malicious sender to correlate the event of the receiver aborting with the receiver’s input. We present two variants of the protocol: the first (Section 5) allows arbitrary correlations with the receiver’s inputs, and is the most efficient protocol we obtain in this work. The second variant (Section 6) is slightly less efficient but allows only correlations that can be expressed as disjunctions of circuit wires and their negations.

  1. Finally, we present (in Section 7) an efficient general reduction of full security

to security with the latter type of “correlated abort”. The idea is to transform the original circuit into a new, randomized, circuit in which disjunctions of wires or their negations provide essentially no information about the input. A special case of this transformation is implicit in [33]. We reduce the general case to honestmajority MPC in the semi-honest model and instantiate it using a recent efficient protocol from [34].

We also present (in Section 4) a direct ad-hoc construction of NISC protocols in the -hybrid model, which is asymptotically less efficient but is somewhat simpler than that obtained by combining steps 2 and 3 above.


Below we define a non-interactive secure computation scheme (NISC). NISC may involve a trusted setup, an ideal implementation of some (non-reactive) functionality H. We shall refer to such an NISC scheme as .

An scheme for a function is a 2-party protocol between Receiver and Sender, of the following format:

  • Receiver gets an input and Sender gets an input .
  • The two parties invoke an instance of H with inputs of their choice, and Receiver

obtains outputs from .

  • Sender may send an additional message to Receiver.
  • Receiver carries out a local computation and outputs f(x; y) or an error message.

The correctness and secrecy requirements of an NISC scheme can be specified in terms of UC security.We shall denote the security parameter by k and require that for a protocol to be considered secure, the simulation error be . An NISC/H scheme for f is required to be a UC-secure realization of the following functionality in the H-hybrid model.

  • accepts from Receiver and from Sender, and outputs f(x; y)

to Receiver and an empty output to Sender. If y is a special input error, then the output to Receiver is error.

In particular, we will be interested in NISC/OT schemes, where OT stands for a functionality that provides (parallel) access to multiple instances of . Oblivious transfer. In this case, the additional message from the sender to the receiver can be implemented using a single additional OT call. We define a relaxed notion of security which is useful in the context of NISC, but may also be of broader interest.

Security with input-dependent abort. Given an SFE functionality F, we define a functionality which behaves as follows: first accepts a description of a predicate from the adversary (e.g., in the form of a PPT algorithm); after receiving inputs from all the parties, computes the outputs to the parties as F does; but before delivering the outputs to the parties, runs with all the inputs; if k outputs abort, then replaces the output to the honest parties by the message abort. Otherwise delivers the output from F to all the parties.

Though we defined security with input-dependent abort as a general security notion, we shall exclusively focus on 2-party functionalities Ff as defined above.

Security with wire-disjunction triggered abort. For a 2-party SFE functionality F as above, outputting f(x; y) to only Receiver, we define a functionality which is a restriction of in which the algorithm k for determining aborting is restricted to be of the following form: includes a set W of pairs of the form (w; b), where w is a wire in a fixed circuit C for computing the function f, and abort if and only if there exists a pair W such that when C is evaluated on (x; y), the wire w takes the value b. We will also consider the stronger notion of input-disjunction triggered abort where the disjunction can only involve input wires.

Protocol making a black-box use of a PRG. We are interested in NISC/OT schemes that do not rely on any cryptographic assumption other than the security of a PRG. Further, the scheme should be able to use any PRG provided to it, in a black-box fashion. Formally, we consider fully black-box reductions [35] from NISC/OT to PRG.

Towards a more concrete measure of efficiency, we require NISC/OT protocols to be secure and measure complexity as a function of k and the circuit size of f. Security against corrupted senders will be statistical. To achieve the above goal against a computationally bounded corrupted receiver, we need to use a PRG for which the advantage of any PPT adversary in distinguishing the output of the PRG from a random string (of the appropriate length) is . To this end a PRG can have a longer computational security parameter, k, that defines the length of its seed (k is a function of k, but for simplicity we denote it as a separate parameter). The PRGs considered below have input and output length .

Efficiency: Communication and Cryptographic Overheads. The best known NISC/OT scheme secure against passive corruption is provided by Yao’s garbled circuit construction (see below) and forms the benchmark for efficiency for us. There are three aspects in which a scheme can be more expensive compared to the garbled circuit (over OT) scheme:

  • The complexity of . For instance, if is the parallel OT functionality OT, then

the number of instances of OTs and the total length of the OT strings provide natural measures of complexity of . (Note that a NISC/H scheme invokes a single instance of .) If H is a more involved functionality, we shall be interested in complexity measures related to securely realizing .

  • Communication overhead.We shall include in this any communication directly between

the two parties and any communication between the parties and .We define the communication overhead of a NISC scheme as the ratio of total communication in the NISC scheme and the total communication in Yao’s garbled circuit (over OT) scheme.

  • Cryptographic overhead. Yao’s garbled circuit scheme makes a black-box use of

PRG. To evaluate a function that is computed by a circuit C, it uses calls to a PRG (with input and output lengths ). The ratio between the number of such calls made by a NISC scheme and Yao’s garbled circuit scheme can be defined as the cryptographic overhead of the NISC scheme.

Garbled Circuit. There are two main variants of Yao’s garbled circuit construction in the literature, one following the original construction of Yao [3] [4] and one following the presentation in [36] [37]. The former allows a negligible probability of error while evaluating the circuit (since a “wrong” key may decrypt a ciphertext encrypted using different key, without being detected), whereas the latter includes pointers with the keys indicating which ciphertexts they are intended for. In this work, we follow the latter presentation (with a few simple changes). Below we describe the version of garbled circuit we shall use.

Consistent with our use of garbled circuits, we shall refer to two parties Receiver (with input x) and Sender (with input y) who wish to evaluate a function represented as a boolean circuit C, with binary gates. Given such a circuit C and input y for Sender, the garbled circuit for C is constructed as follows. For each (non-output) wire w in C, two k-bit strings and are randomly chosen, as well as a random bit . The random bit is used to mask the values on the wires during evaluation of the garbled circuit (if w is an output wire, or an input wire belonging to Receiver, then we set ). The garbled circuit YC consists of the following:

  • For each gate g (with input wires u; v and output wire w), for each ,

an encryption

where where u, v are the input wires to gate g and w its output wire, and Encr is a symmetric-key encryption scheme with a mild one-time semantic security guarantee (see below).

  • For each input-wire w for which the value is already fixed (i.e., w is an input wire

that belongs to Sender), the pair , where is the value of that input wire.

Note that if gate g has input wires u; v and output wire w, then for any values , given and where and , one can obtain (Kzw; c), where and . Hence, given and for each inputwire w belonging to Receiver (note that for such ), one can evaluate C(x; y) (note that an output wire w has ).

The privacy guarantee of a garbled circuit is that, given x and f(x; y), it is possible to construct a simulation which is computationally indistinguishable (with at most a distinguishing advantage ) from where is the garbled circuit constructed for Sender’s input y, and are keys of the form where w are the input wires for Receiver.

For the above security guarantee to hold, encryption Encr only needs to be one-time semantically secure (even if one of the two keys is revealed) [37]. But it is convenient for us to restrict ourselves to a concrete instantiation of an encryption scheme. A particular instance of an encryption scheme, that satisfies the requirements for a garbled circuit, can be defined in terms of black-box access to a pseudorandom generator or, more conveniently, in terms of a pseudorandom function. For each key , let the pseudorandom function initialized with the keyK be denoted by where is the set of indices for the gates in the circuit C and k0 is the maximum length of the messages to be encrypted (k + 1 above, but longer in the variants used in some of our schemes).9 Then the encryption Encr is defined as follows:


where t = (g; a; b) is a “tag” that is used once with any key.

A Statistical NISC/OT Protocol for A Statistical NISC/OT Protocol for N C 0   {\displaystyle NC^{0}~\,\!}

A central building block of our protocols for general functions f is a statistically secure protocol for “simple” functions g in which each output bit depends on just a small number of input bits. We say that g(x; y) is d-local if each of its output bits depends on at most d input bits. Towards an asymptotic measure of efficiency, we will (implicitly) consider an infinite family of finite functionalities n. We say that such a family is in if there exists an absolute constant d such that each is d-local. The precise locality d of the functions we will employ is small, and will be hidden in the asymptotic analysis.

Our general protocols for evaluating a function f(x; y) will typically require the evaluation of functions g(a; b) where the receiver’s input a is short (comparable in length to x) but the sender’s input b and the output are long (comparable to the circuit size of f). We would therefore like the number of OT invocations to be comparable to the receiver’s input length , and the total communication complexity (in the OT-hybrid model) to be as close as possible to the output length .

The semi-honest model. In the semi-honest model, there are several known techniques for obtaining perfectly secure protocols that meet these requirements (cf. [38] and references therein): in such protocols the number of OTs is exactly and the total communication complexity is (with a hidden multiplicative constant depending at most exponentially on d). Our goal is to get similar efficiency in the malicious model without introducing additional interaction.

Previous results. A statistically secure NISC/OT protocol for functions in the malicious model is implicit in [39]. (Via known reductions, this can be extended to functions in low complexity classes such as with a polynomial complexity overhead.) A more efficient protocol was given in [22] (see Appendix B of [26]). The protocol from [22] can also provide computational security for general functions, but this requires a non-black-box use of a pseudorandom generator. From here on we focus on the case of functions.

The protocol of [22] is based on a reduction to multi-party computation (MPC) in the semi-honest model, in the spirit of the MPC-based zero-knowledge protocols of [32]. Instantiated with standard MPC protocols, and settling for a relaxed notion of security, discussed in Section 3.2 below, its communication complexity is, where is the output length of f and k is a statistical security parameter guaranteeing simulation error of . (Here and in the following we will assume that and ignore low order terms in the efficiency analysis for simplicity.)

Overview of New Protocol

We present a different approach for NISC/OT that reduces the multiplicative overhead from to . Our general approach employs perfectly secure MPC protocols for the malicious model. The efficiency improvement will be obtained by plugging in the recent perfectly secure protocol from [34].

Given an function g(a; b), where , our construction has a similar high level structure to that of [22] [26]:

  1. Start with a perfectly secure NISC/OT protocol for g in the semi-honest model in which the receiver uses its original input bits a as the sequence of OT choices. Several such protocols with a constant overhead can be found in the literature (see [38] and references therein).
  2. Use the sender’s algorithm in to define a “certified OT” functionality COT, which is similar to parallel OT except that it verifies that the pairs of strings (together with an additional witness) provided by the sender satisfy a given global consistency predicate. If this verification fails, a special error message is delivered to the receiver. Concretely, we will employ a COT functionality in which the sender’s witness includes its randomness and its input b, and the predicate verifies that the pairs of strings are as prescribed by the protocol. (For efficiency reasons, it may be useful to include in the witness the values of intermediate wires in the sender’s computation. This standard technique can be used to transform an arbitrary predicate into one in .)
  3. Take a perfectly secure MPC protocol for a multi-party functionality corresponding to COT, and use it to obtain a statistically secure two-party NISC/OT protocol for COT. This is the main novel contribution of the current section, which will be described in detail below.
  4. Use for obtaining an NISC/OT protocol for g with security in the malicious model. This can be done in a straightforward way by using COT to emulate while ensuring that the sender does not deviate from its prescribed algorithm. Note that the protocol makes a non-black-box use of , and thus in our black-box setting we cannot apply it to protocols which make use of cryptographic primitives.

Relaxing Security

A (standard) technical subtlety that we need to address is that our direct implementation of will not realize the functionality COT under the standard notion of security, but rather under a relaxed notion of security that we refer to as security with “input-value disjunction (IVD) abort”. This is similar to the notion of security with wire-value disjunction (WVD) abort from Section 6, except that here the disjunctive predicate applies only to input values. That is, the ideal functionality is augmented by allowing a malicious sender to specify a disjunctive predicate in the receiver’s input bits (such as ) which makes the functionality deliver if the receiver’s input satisfies the predicate. (Otherwise the output of the original functionality is delivered.)

A standard method for upgrading security with IVD-abort into full security is by letting the receiver “secret-share” its input (cf. [39] [14]). Concretely, the receiver encodes x into a longer input x0 in a way that ensures that every disjunctive predicate in x0 is either satisfied with overwhelming probability, or alternatively is completely independent of x. The original functionality g is then augmented to a functionality h that first decodes the original input and then computes g. (To prevent cheating by a malicious receiver, the decoding function should output a valid input x for any string x0.)

One can now apply any protocol for h which is secure with IVD-abort in order to obtain a fully secure protocol for the original functionality g.We note that the functionality h will not be in ; thus, the overhead for realizing it unconditionally (even in the semi-honest model) will be too big for our purposes. Instead, we apply the security boosting reduction only at higher level protocols which offer computational security and rely on Yao’s garbled circuit construction. For such protocols, we only pay an additive price comparable to the circuit size of the decoder, which we can make linear in the input length.

We finally suggest a concrete method to encode x into x' as above. A simple method suggested in [39] [14] is to let x0 be an additive sharing of x into k + 1 shares (over ). This has the disadvantage of increasing the length of x by a factor of k, which we would like to avoid. Better alternatives were suggested in the literature (see, e.g., [40]) but these still increase the input length by a constant factor and significantly increase the circuit size. Instead, we suggest the following encoding method. Let be a k-wise independent generator. That is, for a random r, the bits of G(r) are k-wise independent. Then the encoding is defined by , где where the ri are uniformly random strings of length . The corresponding decoder is defined by .

The following lemma is straightforward.

Lemma 1. For every disjunctive predicate P(x'), the following holds: (1) If P involves at most k literals, then is completely independent of x. (2) Otherwise, .

We note that efficient implementations of G can be based on expander graphs [41]. In particular, for any constant 0 < c < 1 there is an implementation of G (with circuit size ) where . Thus, in the typical case where , the encoding size is .

The following corollary shows that, from an asymptotic point of view, boosting security with IVD-abort into full security comes essentially for free both in terms of the circuit size and the receiver’s input length.

Corollary 1. Let f(x; y) be a functionality with circuit size s and receiver input size . Then, there exists a functionality h(x'; y) and a linear-time computable encoding function Enc such that:

  • A fully secure protocol for f can be obtained from any protocol for h which is

secure with IVD-abort by letting the parties in run with inputs x' = Enc(x) and y.

  • The circuit size of h is .
  • The receiver’s input length in h is .

Realizing COT via Robust MPC

It remains to describe an efficient protocol for COT which is secure with IVDabort. In this section, we reduce this task to perfectly robust MPC in the presence of an honest majority.

We consider an MPC network which involves a sender S, n servers , and receivers for simplicity, we assume that receivers do not send, but only receive messages in the protocol. (We will later set .) All parties are connected via secure point-to-point channels as well as a common broadcast medium. Define the following multi-party version of COT: the sender’s input consists of pairs of strings and a witness w. The other players have no input. The output of receiver is if , and otherwise it is .

Now, assume we are given an MPC protocol COT that realizes this multiparty COT functionality and provides the following security guarantees. The adversary may attack up to of the servers, as well as any number of the other players (sender and receivers). For such an adversary, the protocol provides perfect correctness and, moreover, if the adversary is semi-honest we are also guaranteed privacy. Such a protocol, with the desired complexity, appears in [34]. We now use to construct a COT protocol as follows.

  1. Sender runs the MPC protocol “in his head” (a-la [32]), where its input ( pairs of strings and a witness w serve as inputs for the sender S of . It creates strings with the views of the n servers in this run, as well as with the views of the receivers.
  2. Let u be an integer such that . The sender and the receiver apply one parallel call to an OT in which the receiver selects, for each , a view (where the n selection bits are the COT-receiver input) as well as each of the n server views with probability .
  3. Receiver checks for inconsistencies among the views that it read (namely, for each pair of views , corresponding to players A;B, all messages from A to B reported in should be consistent with what an honest A computes in based on ). If any such inconsistency is found or if any of the selected receiver views has a output, then the receiver outputs ; otherwise, the receiver outputs the output of the selected receivers.

To analyze the protocol above, first note that if both Sender and Receiver are honest then the output of protocol is always correct (in particular, because so is ).

Next, consider the case of a dishonest Receiver (and honest Sender). Since, we use ideal OTs the Receiver can only choose it’s selection bits which will yield exactly one of (for each ) and each of the n server views with probability . By the choice of u, the expected number of server views that the receiver will obtain, denoted and, moreover, only with a negligible probability . Whenever , the privacy property of assures that from (semi-honest) views of ` servers and any number of receivers, no additional information (other than what the output of those receivers contain) is learned about the input of the Sender.

Finally, consider the case of a dishonest Sender (and honest Receiver). The COT simulator, given the Sender’s view (in particular, the views of the MPC players), constructs the inconsistency graph G, whose nodes are the MPC players and an edge between nodes A;B whenever the corresponding views are inconsistent. In addition, G' is the sub-graph induced by the n nodes corresponding to the servers. The simulator starts by running a polynomial-time 2-approximation (deterministic) algorithm for finding minimal vertex-cover in the graph G'; i.e, the algorithm outputs a vertex cover B whose size is not more than twice the size of a minimal vertex-cover Consider two case, according to the size of B.

Case 1: . In this case the simulator outputs with probability 1; we argue that in the real COT protocol, the receiver outputs with probability negligibly less than 1. This is because and so there must be a matching in G' of size larger than (the size of a minimal vertex-cover of a graph is at most twice the size of a maximal matching). This, together with the choice , implies that the probability that the l` servers picked by the Receiver do not contain an edge of G' is . In all other cases, the Receiver outputs ?. (A similar argument was made in [19]; for more details, see there.)

Case 2: . In this case, the COT simulator passes the views of the MPC sender and of all servers in B to the MPC simulator. The MPC simulator extracts an effective sender input (i.e., pairs of strings and a witness w). If this input does not satisfy the predicate P then output (by the perfect correctness of , on such input always outputs as well). It remains to deal with the case where the predicate does hold. For this, the COT simulator picks each server with probability (as does the honest receiver in ) and if there is any inconsistency among the set T of selected views then the receiver outputs ; otherwise, the simulator also compares the view of each of the receivers with each of the servers in T. It prepares a disjunctive predicate, Pd, consisting of the literals corresponding to receivers which have at least one such inconsistency (i.e., the predicate is satisfied exactly if the Receiver will select any of the problematic views; in both cases this leads to a output). It sends to the functionality the input extracted by the simulator along with the predicate .

To conclude, let us summarize the complexity of our construction and compare it with the one in [22, Appendix B] (essentially the two constructions are incomparable with advantages depending on the spectrum of parameters).

Theorem 1. The above protocol is a secure protocol with IVD abort for computing any function g(a; b), where . Its communication complexity is . (Recall that ) The number of OT calls is .

Theorem 2. [22] There exists a secure protocol with IVD abort for computing any NC0 function g(a; b), where whose communication complexity is and number of OT calls is .

A Direct Protocol for A Direct Protocol for N I S C / N C 0   {\displaystyle NISC/NC^{0}~\,\!}

Our first construction follows a cut-and-choose approach in the spirit of previous constantround protocols making black-box access to cryptographic primitives [33, 31]. The price we pay for this relatively simple solution is O(k) cryptographic and communication overheads. In particular, we show the following.

Theorem 3. For any function that has a polynomial sized circuit C with n input wires for the first input, there exists an functionality with -bit long output and -bit input from Receiver, such that there is an NISC/HC scheme for FC that makes a black-box use of a PRG, invoking the PRG O(|C|) times, and with total communication. (Recall that k is a statistical security parameter and k is a computational one.)

We shall defer the proof of this theorem to Section 8, where a more general result is presented (see Theorem 6).

A Lean Protocol with Input-Dependent AbortA Lean N I S C / N C 0   {\displaystyle NISC/NC^{0}~\,\!} Protocol with Input-Dependent Abort

In this section, we present a NISC scheme for , which allows input-dependent abort. This scheme is very efficient: the communication overhead over the garbled circuit scheme is (a small) constant and the cryptographic overhead is just 1 (allowing the PRGs to output a slightly longer string).We shall present the scheme first as a NISC/HC scheme, for an NC0 functionality , and then apply the result of Section 3 to obtain an NISC/OT scheme.

Theorem 4. For any function that has a polynomial sized circuit C with n input wires for the first input, there exists an functionality with -bit long output and -bit input from Receiver, such that there is an scheme for C that makes a black-box use of a PRG, invoking the PRG times, and with total communication. PROOF SKETCH: The details of the proof appears in the full version of this paper. At a high-level, this scheme allows Receiver to verify that each pointer bit uncovered in the garbled circuit is correct as follows: each pointer bit is tagged using a MAC (with a key provided by Receiver). However since this bit should be kept secret until the corresponding entry in the garbled circuit is decrypted, a share of the tag is kept encrypted with the pointer bit, and the other share is provided to Receiver. Sender, who does not know the MAC key, can create the one share that he must encrypt, and an functionality takes the MAC key from Receiver, computes the MAC tag and hands over the other share to Receiver. Input dependent abort is obtained since, intuitively, the sender can only use wrong MACs in some entries which will make the Receiver abort in case those entries are decrypted.

with Wire-Disjunction Triggered AbortN I S C / N C 0   {\displaystyle NISC/NC^{0}~\,\!} with Wire-Disjunction Triggered Abort

We extend the scheme in Section 5, to achieve the stronger security guarantee of security with wire-disjunction triggered abort. Similar to the previous scheme, this scheme ensures (partial) correctness of the garbled circuit via an functionality which provides the share of a MAC to Receiver. However, the MAC is not just on a single pointer bit, but also on the key stored in the garbled circuit entry. This scheme has some features of the scheme in Section 4 in that Sender provides a table of purported outputs from a PRF, some of which will be verified by Receiver during decoding. However, this construction avoids the overhead, at the expense of settling for security with wire-disjunction triggered abort.

This construction involves a statistically secure, one-time MAC for k bit messages. It will be important for us to implement this MAC scheme using circuits. This can be done following [20], if the message is first encoded appropriately. Since the encoding itself is not an functionality, we require Sender to provide the encoding, along with values of all the wires in a circuit that computes the encoding. Then an circuit can verify this encoding, and in parallel create the MAC tag.

In the full version we prove the following theorem.

Theorem 5. For any function that has a polynomial sized circuit C with n input wires for the first input, there exists an functionality with -bit long output and -bit input from Receiver, such that there is an NISC/HC scheme for C that makes a black-box use of a PRG, invoking the PRG times, and with total communication.

Compared to Theorem 4, this construction is asymptotically less efficient, since the output of is longer , as C will now be required to deliver the entire garbled srcuit to Receiver).

From Security with WDT-Abort to Full Security

In this section, we discuss general methods for converting any NISC scheme satisfying security with wire disjunction triggered (WDT) abort into an NISC with full security, based on semi-honest secure MPC protocols. Our transformation formalizes and generalizes such a transformation that was given in the work of [24, 25] (and our intuition below follows their intuition) in the context of constructing stateful hardware circuits that remain private even when an adversary can tamper with the values on wires. We note that the construction of [24] also had to deal with multiple other issues that do not concern us, which added complexity to their solution. Outlined below, our solution can be seen as a simplification of their construction. The benefit of the transformation outlined in this section over the simple majoritybased approach discussed earlier is the potential for greater efficiency. We will first formalize the encoding notion that we use to deal with WDT attacks, then we present an outline of our general transformation, and then show how to invoke this transformation using known semi-honest MPC protocols from the literature to obtain higher levels of efficiency. Our transformation is captured by means of a new encoding, that we define below. The details of realizing this transformation are presented in the full version.

Definition 1. (WDT-resilient encoding) A randomized circuit family C' together with an efficient randomized encoding algorithm family Enc and an efficient deterministic decoding algorithm family Dec is a WDT-resilient encoding of a circuit C that takes two inputs if the following properties hold.

  • (Correctness) For all (x; y) in the domain of C, we have that

  • (Malicious Receiver Security) There exists a randomized efficient machine RecSim

such that for every x' in the range of Enc (but not necessarily in the image of Enc), there exists x in the domain of Enc such that for every y such that (x; y) is in the domain of C, the output distribution of is identical to the distribution C'(x'; y).

  • (WDT-Malicious Sender Security) For any set S of wires in C' or their negations, let to be the event that the disjunction of the values specified

by S, when the input of C' is (Enc(x); y), is satisfied. The probability space is over the random gates of C' and the randomness used by Enc. For any such S and for all , and y such that and are in the domain of C, we have:

Public-Code NISC

So far we only considered NISC schemes which rely on an OT oracle that gets inputs from both the sender and the receiver. As discussed in the introduction, this can be combined with a 2-message implementation of OT to get a protocol which does not require any active action from the receiver except publishing an encryption of her input.

In this section we discuss this variant of NISC, called Public-Code NISC or PCNISC for short. In more detail, this flavor of NISC allows Receiver to publish an encoding of her input x, and later let one or more Senders compute on the encoding of x using their private inputs y, and send it back to her; she can decode this message and recover the value f(x; y) (and nothing more). There could be a setup like a common reference string (CRS), or correlated random variables.

Formally, a PC-NISC scheme for a function consists of the following four PPT algorithms.

  • Setup: takes only the security parameter as an input and outputs a pair of strings

. These strings are meant to be given to the two parties (Receiver and Sender, respectively).

  • Encode: takes an input , and a setup string , and outputs a string c

encoding x (or possibly an error message, if appears malformed).

  • Compute: takes an encoding c, an input and a setup string and outputs

an “encoded output” (or an error message if c appears malformed).

  • Decode: takes an encoded output and a setup string , and outputs (or an

error message if the encoded output appears malformed).

Ideally, in a PC-NISC scheme, a single published encoding can be used by Receiver to carry out multiple computations. To define the security of a PC-NISC scheme, below we define the functionality , which allows T invocations before letting a corrupt Sender manipulate the outcome.

  • accepts an input x from Receiver.
  • Then in each round, it accepts an input y from Sender. and outputs f(x; y) to Receiver

(and an empty output to Sender). If y is a special command error, the output to Receiver is error.

  • There is a bound T on the number of inputs accepts from corrupt Senders

before correctness is compromised. More formally, a corrupt Sender is allowed to include with its input a command where is an arbitrary PPT algorithm, and after T such rounds, in each subsequent such round, outputs to Receiver.

Now, given a PC-NISC scheme k consider the 2-party protocol (in a model, which simply makes a fresh pair available to the two parties) in which Receiver, on input x, sends to Sender; on receiving an input y reactively from the environment, Sender sends to Receiver, and Receiver outputs Decode(u). We say that k is a secure PC-NISC scheme if the protocol . is a UC secure realization of the functionality . We shall be interested in NISC schemes for .

Defining . The goal of PC-NISC was to avoid the live availability of Receiver, when Sender is executing the scheme. However it is still possible to consider such a scheme in an -hybrid model, if the functionality itself allows Receiver to send an input, and subsequently have multiple rounds of independent interactions with Sender, delivering a separate output to Receiver in each round. We shall use this convention as an intermediate step in achieving PC-NISC/OT and PC-NISC/CRS schemes, which can be specified in the plain model (i.e., without reference to a hybrid-model) in terms of the Setup algorithm. In PC-NISC/CRS, Setup sets to be a randomly generated string, according to some probability distribution that will be specified by the scheme.

In PC-NISC/OTvar, Setup outputs several instances of correlated random variables: in each instance, Receiver gets two random bits and Sender gets random bits such that . They can be readily used in a PC-NISC scheme for evaluating the OT function, in which Receiver has a choice bit c, Sender has two inputs and , and Receiver obtains . Hence a NISC/OT scheme for a function f can be easily turned into a PC-NISC/OTvar scheme for f if the number of sessions to be supported the Encode and Compute algorithms will incorporate and ; further, Compute will include the message sent by Sender in the NISC/OT scheme; Decode involves first applying to obtain the outcome of OT, before carrying out the local computation of the NISC/OT scheme.

The main challenge in constructing a PC-NISC scheme, beyond that already present in constructing NISC schemes, is to be able to support a larger number of computations for the same input encoding.

First, we observe that the NISC/OT scheme for functionalities from Section 3 can be extended into a PC-NISC/OTvar supporting T adding a poly(k; T) amount to communication and cryptographic complexities. This is done by increasing the number of servers in the underlying MPC used in this scheme.

In the full version we prove the feasibility result below, analogous to – indeed extending – Theorem 3.

Theorem 6. For any function that has a polynomial sized circuit C with n input wires for the first input, there exists an functionality with -bit long output and -bit input from Receiver, supporting T computations, such that there is a C scheme for f that makes a black-box use of a PRG, invoking the PRG times, and with total communication.

Note that the above NISC scheme is already for , and can be translated to a PC-NISC scheme for f supporting T executions, as described earlier. Thus, given this scheme, we can combine it with a PC-NISC/OTvar for (also described above) to obtain a PC-NISC/OTvar for . A proof of Theorem 6 is given in the full version.

Authors' contacts

Cite error: Invalid <references> tag; parameter "group" is allowed only.

Use <references />, or <references group="..." />


  1. Rivest, R.L., Adleman, L., Dertouzos, M.L.: On data banks and privacy homomorphisms. In: Foundations of Secure Computation (Workshop, Georgia Inst. Tech., Atlanta, Ga., 1977), pp. 169–179. Academic, New York (1978)
  2. Sander, T., Young, A., Yung, M.: Non-interactive cryptocomputing for NC1. In: FOCS, pp. 554–567 (1999)
  3. 3.0 3.1 3.2 Yao, A.C.-C.: How to generate and exchange secrets. In: Proc. 27th FOCS, pp. 162–167. IEEE, Los Alamitos (1986)
  4. 4.0 4.1 4.2 Lindell, Y., Pinkas, B.: A proof of yao’s protocol for secure two-party computation. Electronic Colloquium on Computational Complexity (ECCC) (063) (2004)
  5. 5.0 5.1 5.2 Cachin, C., Camenisch, J., Kilian, J.,M¨uller, J.: One-Round Secure Computation and Secure Autonomous Mobile Agents. In: Montanari, U., Rolim, J.D.P.,Welzl, E. (eds.) ICALP 2000. LNCS, vol. 1853, pp. 512–523. Springer, Heidelberg (2000)
  6. Gentry, C., Halevi, S., Vaikuntanathan, V.: i-hop homomorphic encryption and rerandomizable yao circuits. In: Rabin, T. (ed.) CRYPTO2010. LNCS, vol. 6223, pp. 155–172. Springer, Heidelberg (2010)
  7. Gentry, C.: Fully homomorphic encryption using ideal lattices. In: STOC, pp. 169–178. ACM, New York (2009)
  8. Boneh, D., Goh, E.-J., Nissim, K.: Evaluating 2-DNF Formulas on Ciphertexts. In: Kilian, J. (ed.) TCC 2005. LNCS, vol. 3378, pp. 325–341. Springer, Heidelberg (2005)
  9. Ishai, Y., Paskin, A.: Evaluating Branching Programs on Encrypted Data. In: Vadhan, S.P. (ed.) TCC 2007. LNCS, vol. 4392, pp. 575–594. Springer, Heidelberg (2007)
  10. Melchor, C.A., Gaborit, P., Herranz, J.: Additively homomorphic encryption with d-operand multiplications. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 138–154. Springer, Heidelberg (2010)
  11. Peikert, C., Vaikuntanathan, V., Waters, B.: A Framework for Efficient and Composable Oblivious Transfer. In: Wagner, D. (ed.) CRYPTO 2008. LNCS, vol. 5157, pp. 554–571. Springer, Heidelberg (2008)
  12. Damg°ard, I., Nielsen, J.B., Orlandi, C.: Essentially Optimal Universally Composable Oblivious Transfer. In: Lee, P.J., Cheon, J.H. (eds.) ICISC 2008. LNCS, vol. 5461, pp. 318–335. Springer, Heidelberg (2009)
  13. 14.0 14.1 14.2 14.3 14.4 Lindell, Y., Pinkas, B.: An Efficient Protocol for Secure Two-Party Computation in the Presence of Malicious Adversaries. In: Naor, M. (ed.) EUROCRYPT 2007. LNCS, vol. 4515, pp. 52–78. Springer, Heidelberg (2007)
  14. 15.0 15.1 Horvitz, O., Katz, J.: Universally-Composable Two-Party Computation in Two Rounds. In: Menezes, A. (ed.) CRYPTO 2007. LNCS, vol. 4622, pp. 111–129. Springer, Heidelberg (2007)
  15. Canetti, R.: Universally composable security: A new paradigm for cryptographic protocols. Electronic Colloquium on Computational Complexity (ECCC) TR01-016 (2001), Previous version “A unified framework for analyzing security of protocols” availabe at the ECCC archive TR01-016. Extended abstract in FOCS 2001 (2001)
  16. Beaver, D., Goldwasser, S.: Multiparty computation with faulty majority. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 589–590. Springer, Heidelberg (1990)
  17. Beaver, D.: Precomputing Oblivious Transfer. In: Coppersmith, D. (ed.) CRYPTO 1995. LNCS, vol. 963, pp. 97–109. Springer, Heidelberg (1995)
  18. Beaver, D.: Correlated pseudorandomness and the complexity of private computations. In: Proc. 28th STOC, pp. 479–488. ACM, New York (1996)
  19. Naor, M., Pinkas, B.: Efficient oblivious transfer protocols. In: SODA, pp. 448–457 (2001)
  20. 21.0 21.1 Ishai, Y., Kilian, J., Nissim, K., Petrank, E.: Extending Oblivious Transfers Efficiently. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 145–161. Springer, Heidelberg (2003)
  21. 22.0 22.1 22.2 22.3 22.4 22.5 22.6 22.7 22.8 Ishai, Y., Prabhakaran, M., Sahai, A.: Founding Cryptography on Oblivious Transfer – Efficiently. In: Wagner, D. (ed.) CRYPTO 2008. LNCS, vol. 5157, pp. 572–591. Springer, Heidelberg (2008)
  22. Goldreich, O., Micali, S., Wigderson, A.: How to play ANY mental game. In: ACM (ed.) Proc.19th STOC, pp. 218–229. ACM, New York (1987), See [15, ch. 7] for more details
  23. Beaver, D., Micali, S., Rogaway, P.: The round complexity of secure protocols (extended abstract). In: STOC, pp. 503–513. ACM, New York (1990)
  24. Ishai, Y., Kushilevitz, E.: On the Hardness of Information-Theoretic Multiparty Computation. In: Cachin, C., Camenisch, J. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 439–455. Springer, Heidelberg (2004)
  25. 26.0 26.1 26.2 26.3 Ishai, Y., Prabhakaran, M., Sahai, A.: Founding cryptography on oblivious transfer - efficiently, Preliminary full version on http://www.cs.uiuc.edu/˜mmp/
  26. Mohassel, P., Franklin, M.K.: Efficiency tradeoffs for malicious two-party computation. In: Yung, M., Dodis, Y., Kiayias, A., Malkin, T.G. (eds.) PKC 2006. LNCS, vol. 3958, pp. 458– 473. Springer, Heidelberg (2006)
  27. Kilian, J., Micali, S., Ostrovsky, R.: Minimum resource zero-knowledge proofs (extended abstract). In: FOCS, pp. 474–479. IEEE, Los Alamitos (1989)
  28. Kalai, Y.T., Raz, R.: Succinct non-interactive zero-knowledge proofs with preprocessing for logsnp. In: FOCS, pp. 355–366. IEEE, Los Alamitos (2006)
  29. Gennaro, R., Gentry, C., Parno, B.: Non-interactive verifiable computing: Outsourcing computation to untrusted workers. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 465–482. Springer, Heidelberg (2010)
  30. 31.0 31.1 Chung, K.-M., Kalai, Y., Vadhan, S.P.: Improved delegation of computation using fully homomorphic encryption. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 483–501. Springer, Heidelberg (2010)
  31. 32.0 32.1 32.2 Ishai, Y., Kushilevitz, E., Ostrovsky, R., Sahai, A.: Zero-knowledge from secure multiparty computation. In: STOC, pp. 21–30. ACM, New York (2007)
  32. Ishai, Y., Prabhakaran, M., Sahai, A., Wagner, D.: Private Circuits II: Keeping Secrets in Tamperable Circuits. In: Vaudenay, S. (ed.) EUROCRYPT 2006. LNCS, vol. 4004, pp. 308–327. Springer, Heidelberg (2006)
  33. 34.0 34.1 34.2 Damg°ard, I., Ishai, Y., Krøigaard, M.: Perfectly Secure Multiparty Computation and the Computational Overhead of Cryptography. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 445–465. Springer, Heidelberg (2010)
  34. Reingold, O., Trevisan, L., Vadhan, S.P.: Notions of Reducibility between Cryptographic Primitives. In: Naor, M. (ed.) TCC 2004. LNCS, vol. 2951, pp. 1–20. Springer, Heidelberg (2004)
  35. Naor, M., Pinkas, B., Sumner, R.: Privacy preserving auctions and mechanism design. In: ACM Conference on Electronic Commerce, pp. 129–139 (1999)
  36. 37.0 37.1 Applebaum, B., Ishai, Y., Kushilevitz, E.: Computationally private randomizing polynomials and their applications. In: IEEE Conference on Computational Complexity, pp. 260–274. IEEE Computer Society, Los Alamitos (2005)
  37. 38.0 38.1 Ishai, Y., Kushilevitz, E., Ostrovsky, R., Sahai, A.: Cryptography with constant computational overhead. In: STOC, pp. 433–442. ACM, New York (2008)
  38. 39.0 39.1 39.2 Kilian, J.: Founding cryptography on oblivious transfer. In: STOC, pp. 20–31. ACM, New York (1988)
  39. Pinkas, B., Schneider, T., Smart, N.P., Williams, S.C.: Secure Two-Party Computation Is Practical. In: Matsui, M. (ed.) ASIACRYPT 2009. LNCS, vol. 5912, pp. 250–267. Springer, Heidelberg (2009)
  40. Mossel, E., Shpilka, A., Trevisan, L.: On epsilon-biased generators in nc0. Random Struct. Algorithms 29(1), 56–81 (2006)

Cite error: <ref> tags exist for a group named "@:", but no corresponding <references group="@:"/> tag was found, or a closing </ref> is missing