Covert Two-Party Computation

Luis von Ahn

Carnegie Mellon University

5000 Forbes Ave Pittsburgh, PA 15213

biglou@cs.cmu.edu Nicholas Hopper

University of Minnesota 200 Union St SE Rm 4-192 Minneapolis, MN 55455

hopper@cs.umn.edu John Langford

TTI Chicago 1427 East 60th St, 2^{nd} Floor Chicago, IL 60637

jl@tti-c.org

ABSTRACT

We introduce covert two-party computation, a stronger notion of security than standard secure two-party computation. Like standard secure two-party computation, covert two-party computation allows Alice and Bob, with secret inputs x_{A} and x_{B} respectively, to compute a function f(x_{A}, x_{B}) without leaking any additional information about their inputs. In addition, covert two-party computation guarantees that even the existence of a computation is hidden from all protocol participants unless the value of the function mandates otherwise. This allows the construction of protocols that return f(x_{A}, x_{B}) only when it equals a certain value of interest (such as “Yes, we are romantically interested in each other”) but for which neither party can determine whether the other even ran the protocol whenever f(x_{A}, x_{B}) is not a value of interest. Since existing techniques for secure function evaluation always reveal that both parties participate in the computation, covert computation requires the introduction of new techniques based on provably secure steganography. We introduce security definitions for covert two-party computation and show that this surprising notion can be achieved by a protocol given the Decisional Diffie-Hellman assumption in the “honest but curious” model. Using this protocol as a subroutine, we present another protocol which is fair and secure against malicious adversaries in the Random Oracle Model — unlike most other protocols against malicious adversaries, this protocol does not rely on zeroknowledge proofs (or similar cut-and-choose techniques), because they inherently reveal that a computation took place. We remark that all our protocols are of comparable efficiency to protocols for standard secure two-party computation.

Categories and Subject Descriptors

F.m [Theory of Computation]: Miscellaneous; E.3 [Data]: Data Encryption

General Terms

Algorithms, Security, Theory

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for pro�t or commercial advantage and that copies bear this notice and the full citation on the �rst page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior speci�c permission and/or a fee. STOC’05, May 22-24, 2005, Baltimore, Maryland, USA. Copyright 2005 ACM 1-58113-960-8/05/0005 ...$5.00.

Keywords

Steganography, Two-Party Computation, Covert Computation, Fair two-party computation

1. INTRODUCTION

Secure two-party computation (or SFE, for secure function evaluation) allows Alice and Bob to evaluate a function of their secret inputs so that neither learns anything other than the output of the function. A real-world example often used to illustrate the applications of this primitive is when Alice and Bob wish to determine if they are romantically interested in each other. Secure two-party computation allows them to do so without revealing their true feelings unless they are both attracted. By securely evaluating the AND of the bits representing whether each is attracted to the other, both parties can learn if there is a match without risking embarrassment: if Bob is not interested in Alice, for instance, the protocol does not reveal whether Alice is interested in him.

However, although often used to illustrate the concept, this example is not entirely logical. The very use of twoparty computation already reveals possible interest from one party: “would you like to determine if we are both attracted to each other?”

A similar limitation occurs in a variety of other applications where the very use of the primitive raises enough suspicion to defeat its purpose. To overcome this limitation we introduce covert two-party computation, which, unless the output of the function is favorable to both parties, hides the fact that a computation even took place. The computation is hidden in that each party cannot determine if the other went along with the computation or simply was communicating as they normally do. More specifically, for a given set Y of interesting values, covert two-party computation guarantees the following (in addition to leaking no additional knowledge about the individual inputs): (A) no outside eavesdropper can determine whether the two parties are performing the computation or simply communicating as they normally do; (B) When f(x_{A}, x_{B}) ∈ Y, the result of the computation is revealed; but (C) neither party can determine whether the other even ran the protocol whenever f(x_{A}, x_{B}) ∉ Y. Thus whether or not a computation took place is revealed based on the output of the function.

1.1 Some Applications

Among the many applications of covert two-party computation we mention the following as examples:

• Covert Authentication. Imagine that Alex works for CIA and Bob works for Mossad (the Israeli intelligence agency). Both have infiltrated a single terrorist cell but neither knows that the other is also an undercover agent. If they can discover their “mutual interest” they could pool their efforts; thus both should be looking for potential collaborators. On the other hand, suggesting something out of the ordinary is happening to a normal member of the cell would likely be fatal. Running a covert computation in which both parties’ inputs are their signed credentials and the result is revealed only if they are allies will allow Alex and Bob to authenticate each other. If Bob is NOT an ally, he will not know that Alex was even asking for authentication, and vice-versa. Furthermore, the authentication would happen without anybody else being able to notice that something out of the ordinary happened. It is important that the existence of the computation is revealed only after the parties are mutually authenticated, since asking Charlie, a terrorist, to execute any SFE protocol could result in Alex being killed. (Similar situations occur in, e.g., planning a coup d’etat or constructing a zombie network.)

• Dating. As hinted above, covert two-party computation can be used to properly determine if two people are romantically interested in each other. It allows a person to approach another and perform a computation hidden in their normal-looking messages such that: (1) if both are romantically interested in each other, they both find out; (2) if none or only one of them is interested in the other, neither will be able to determine that a computation even took place. Of course, ordinary social interactions do not require such discretion^{1}. But if the computation further involves comparing some “unusual” dating preferences or if one of the parties is already involved with somebody else, it could be embarrassing or detrimental to reveal the need to run the protocol at all. To prevent one party from lying to determine if the other is interested, Alice and Bob could use a function which outputs a non-repudiable “certificate” of mutual interest; but even in this case it is important to guarantee that both obtain the result. If one of the parties can get the result while ensuring that the other one doesn’t, this party would be able to learn the other’s input by pretending he is romantically interested; there would be no harm for him in doing so since the other would never see the result. Two-party computation protocols in which either both parties get the result at roughly the same time or neither of them does are called “fair.” We will present a protocol for fair covert two-party computation.

• Cooperation between competitors. Imagine that Alice and Bob are competing online retailers and both are being compromised by a sophisticated hacker. Imagine also that because of the volume of their logs, neither Alice nor Bob can draw a reliable inference about the location of the hacker, and statistical analysis indicates that about twice as many attack events are required to isolate the hacker. Thus if Alice and Bob were to compare their logs, they could solve their problem. But if Alice admits she is being hacked and Bob is not, he will certainly use this information to overtake her customers, and vice-versa. Using covert computation to perform the log analysis online can break this impasse. If Alice is concerned that Bob might fabricate data to try and learn something from her logs, the computation could be modified so that when an attacker is

1except for the very shy identified, the output is both an attacker and a signed contract stating that Alice is due a prohibitively large fine (for instance, $1 Billion US) if she can determine that Bob falsified his log, and vice-versa. Similar situations occur whenever cooperation might benefit mutually distrustful competitors. For example: negotiations for a merger, contract negotiations including terms which are illegal, etc.

• Cheating in card games. Suppose two parties playing a card game want to determine whether they should cheat. Each of them is self-interested, so cheating should not occur unless both players can benefit from it. Using covert two-party computation with both players’ hands as input allows them to compute if they have an opportunity to benefit from cheating while guaranteeing that: (1) neither player finds out whether the other attempted to cheat unless they can both benefit from it; (2) none of the other players can determine if the two are secretly planning to collude. Hiding the desire to cheat (i.e., hiding that the function is being evaluated) is especially useful because such desire is greatest when a player has a weak hand, so even revealing this desire already reveals something about the player’s input.

This list of “colorful” applications is not intended to be exhaustive; we assume that the reader can see the potential benefit of this new primitive.

1.2 Synchronization

A natural question to ask about covert computation is, “Don’t the parties have to reveal that they want to use a covert protocol anyway?” This, however, is not the case: a protocol specification can include a public and well-known method for how and when to initiate the protocol. An example of such “synchronization” information could be: “if we will determine whether we both like each other, the computation will start with the first message exchanged after 5pm.” Since such details are published as part of the protocol specification, there is no need for either party to indicate that they wish to compute anything at all: if Alice is interested in computing with Bob, she starts the protocol with her first message after 5pm.

Who knows what?

Given the guarantees that covert computation offers, it is important to clarify what the parties know and what they don’t. We assume that both parties know a common circuit for the function that they wish to evaluate, that they know which role they will play in the evaluation, and that they know when to start evaluating the circuit if the computation is going to occur. Finally, we assume adversarial parties know all such details of the protocols we construct.

1.3 Contributions and Organization

The primary contribution of this paper is to introduce a new cryptographic primitive, covert computation, and to show that this primitive is feasible by giving a construction which can covertly realize any functionality. The existence of such a primitive is in itself surprising — you could be computing something without knowing if the other party is going along with the computation — and cannot be accomplished using standard techniques. We outline the technical obstacles in this section.

Hiding the Computation vs. Hiding the Function.

Notice that covert computation is not about hiding what function Alice and Bob are interested in computing, which could be accomplished via standard SFE techniques. Covert computation hides the fact that Alice and Bob are interested in computing a function at all. This point is vital in the case of, e.g., covert authentication, where expressing a desire to do anything out of the ordinary could result in the death of one of the parties. In fact, we assume that the specific function to be computed (if any) is known to all parties. This is analogous to the difference in security goals between steganography (where the adversary is assumed to know which message, if any, is hidden and simply has to determine whether such a hidden message exists) and encryption, where the adversary is trying to decide what the hidden message is.

Can covert two-party computation be achieved by trivial composition of SFE protocols with steganography?

No. Steganographically encoding all messages of a standard secure computation protocol would yield a protocol for which no outside observer can determine whether it is being run, but would not guarantee that the participating parties themselves cannot tell that the protocol is being run. Covert two-party computation guarantees that the computation remains hidden from the participating parties (except for certain output values of the function being computed). Provably secure steganography [17], however, is an important step towards making covert two-party computation conceivable.

Security against malicious adversaries without Zero Knowledge.

Our basic protocol uses Yao’s “garbled circuit” construction for SFE as a subroutine. Unfortunately Yao’s protocol is either inherently unfair (only one party can obtain the result) or insecure against malicious adversaries (because the functionality of the circuit is concealed). Previous techniques for simultaneously obtaining security against malicious adversaries and fairness rely on zero-knowledge proofs (or similar cut-and-choose techniques) to prove that the “garbled” circuit computes the agreed-upon function. Such techniques cannot be applied in the case of covert computation, because they inherently reveal the computation.

Our solution uses a form of “reactive computation” in which the basic, unfair protocol is invoked many times as a subroutine; each time it gives an output which appears random but carries state forward to the next invocation. Since our final protocol is fair, this technique may be of independent interest; in some situations it is more efficient than any previous fair protocol for general SFE. In particular, suppose that k is a security parameter, n is the size of the inputs, c_{f} (n) is the size of a circuit to evaluate the function f, c_{h}(k, n) is the size of a circuit to evaluate a cryptographic hash function on max{k, n} bits, and c_{ot}(k, l) is the communication complexity of OT_{1}^{2} with l-bit strings and security parameter k. Then Yao’s (unfair) protocol has communication complexity O(kc_{f} (n) + nc_{ot}(k, k)); our solution can be implemented with communication complexity O(kc_{f} (n) + k^{2}c_{h}(k, n) + (k^{2} + n) c_{ot}(k, k)); and the most efficient protocol for fair secure two-party computation known prior to our work has complexity O(k^{2}c_{f} (n)+nc_{ot}(k, k^{2})) [21] (we remark, however, that this protocol is secure in the standard model whereas our security proof is in the random oracle model).

Roadmap.

The high-level view of our presentation is as follows. First, we define “ordinary” or “innocent-looking” communications. Our protocols will generate messages that are indistinguishable from “ordinary” communications — so nobody can tell if the parties are performing a computation or just communicating innocently. The first protocol we present is a modification of Yao’s “garbled circuit” two-party protocol. We show how to instantiate the encryption and oblivious transfer primitives in Yao’s protocol to yield a complete protocol for two-party secure function evaluation that generates messages indistinguishable from uniform random bits. We then use provably secure steganography to transform this into a protocol that generates messages indistinguishable from “ordinary” communications. The protocol thus constructed, however, is not secure against malicious adversaries nor is it fair (since neither is Yao’s protocol by itself). We therefore construct another protocol, which uses our modification of Yao’s protocol as a subroutine, that satisfies fairness and is secure against malicious adversaries, in the Random Oracle Model.

Related Work.

Secure two-party computation was introduced by Yao [22]. Since then, there have been several papers on the topic and we refer the reader to a survey by Goldreich [12] for further references. Constructions that yield fairness for two-party computation were introduced by Yao [23], Galil et al. [11], Brickell et al. [6], and many others (see [21] for a more complete list of such references). The notion of covert computation, however, is completely new.

Notation.

We say a function μ : ℕ → [0, 1] is negligible if for every c > 0, for all sufficiently large k, μ(k) < 1/k^{c}. We denote the length (in bits) of a string or integer s by |s| and the concatenation of string s_{1} and string s_{2} by s_{1}||s_{2}. We let U_{k} denote the uniform distribution on k bit strings. If D is a distribution with finite support X, we the minimum entropy of D is given by H_{∞}(D) = min_{x∈X}{− log_{2} Pr_{D}[x]}. The statistical distance between two distributions C and D with joint support X is defined by Δ(C, D) = (1/2) ∑_{x∈X} | Pr_{D}[x] − Pr_{C}[x]|. Two sequences of distributions, {C_{k}}_{k} and {D_{k}}_{k}, are called computationally indistinguishable, written C ≈ D, if for any probabilistic polynomial-time A, the quantity Adv_{C,D}^{A}(k) = |Pr[A(C_{k}) = 1] − Pr[A(D_{k}) = 1]| is negligible in k.

2. BIDIRECTIONAL CHANNELS

We hide the communication patterns of two-party computation protocols in “ordinary” or “innocent-looking” messages. We define ordinary communication patterns and messages in a manner similar to the channels used by [17, 2, 9]. The main difference is that our channel is shared among two participants and messages sent by each participant might depend on previous messages sent by either one of them. To emphasize this difference, we use the term bidirectional channel.

Messages are drawn from a set D of documents. For simplicity we assume that time proceeds in discrete timesteps. Each party P ∈ {P_{0}, P_{1}} maintains a history h_{P}, which represents a timestep-ordered list of all documents sent and received by P. We call the set of well-formed histories H. We associate to each party P a family of probability distributions B^{P} = {B_{h}^{P} }_{h∈H} on D.

The communication over a bidirectional channel B = (D, H, B^{P_{0}}, B^{P_{1}}) proceeds as follows. At each timestep, each party P receives messages sent to them in the previous timestep, updates h_{P} accordingly, and draws a document d ← B_{h_{P}}^{P} (the draw could result in the empty message ⊥, signifying that no action should be taken that timestep). The document d is then sent to the other party and h_{P} is updated. We assume for simplicity that all messages sent at a given timestep are received at the next one. Denote by B_{h_{P}}^{P} ≠⊥ the distribution B_{h_{P}}^{P} conditioned on not drawing ⊥. We will consider families of bidirectional channels {B_{k}}_{k≥0} such that: (1) the length of elements in D_{k} is polynomiallybounded in k; (2) for each h ∈ H_{k} and party P, either Pr[B_{h}^{P} =⊥] = 1 or Pr[B_{h}^{P} =⊥] ≤ 1 − δ, for constant δ; and (3) there exists a function ℓ(k) = ω(log k) so that for each h ∈ H_{k}, H_{∞}((B_{h}^{P})_{k} ≠⊥) ≥ ℓ(k) (that is, there is some variability in the communications).

We assume that party P can draw from B_{h}^{P} for any history h, and that the adversary can draw from B_{h}^{P} for every party P and history h. We assume that the ability to draw from these distributions does not contradict the cryptographic assumptions that our results are based on. In the rest of the paper, all communications will be assumed to conform to the bidirectional channel structure: parties only communicate by sending documents from D to each other and parties not running a protocol communicate according to the distributions specified by B. Parties running a protocol strive to communicate using sequences of documents that appear to come from B. As a convention, when B is compared to another random variable, we mean a random variable which draws from the process B the same number of documents as the variable we are comparing it to.

3. COVERT TWO-PARTY COMPUTATION WITH SEMI-HONEST ADVERSARIES

We now present a protocol for covert two-party computation that is secure against semi-honest adversaries in the standard model (without Random Oracles) and assumes that the decisional Diffie-Hellman problem is hard. The protocol is based on Yao’s well-known function evaluation protocol [22].

We first define covert two-party computation formally, and we then describe Yao’s protocol and the necessary modifications to turn it into a covert computation protocol. The definition presented in this section is only against honestbut-curious adversaries and is unfair in that only one of the parties obtains the result. In Section 4 we will define covert two-party computation against malicious adversaries and present a protocol that is fair: either both parties obtain the result at roughly the same time or neither of them does. The protocol in Section 4 uses the honest-but-curious protocol presented in this section as a subroutine.

3.1 De�nitions

Formally, a two-party, n-round protocol is a pair Π = (P_{0}, P_{1}) of programs. The computation of Π proceeds as follows: at each round, P_{0} is run on its input x_{0}, the security parameter 1^{k}, a state s_{0}, and the (initially empty) history of messages exchanged so far, to produce a new message m and an internal state s_{0}. The message m is sent to P_{1}, which is run on its input x_{1}, the security parameter 1^{k}, a state s_{1}, and the history of messages exchanged so far to produce a message that is sent back to P_{0}, and a state s_{1} to be used in the next round. Denote by ⟨P_{0}(x_{0}), P_{1}(x_{1})⟩ the transcript of the interaction of P_{0} with input x_{0} and P_{1} with input x_{1}. This transcript includes all messages exchanged between P_{0} and P_{1} along with the timestep in which they were sent. After n rounds, each party P ∈ {P_{0}, P_{1}} halts with an output, denoted by Π_{P} (x_{0}, x_{1}) = Π_{P} (x̄). We say that Π correctly realizes the functionality f if for at least one P ∈ {P_{0}, P_{1}}, Pr[Π_{P} (x̄) = f(x̄)] ≥ 1 − ν(k), where ν is negligible.

For σ ∈ {0, 1}, we denote by V_{Π}^{P_{σ}} (x_{0}, x_{1}) the view of party P_{σ} on input x_{σ} when interacting with P_{1−σ} on input x_{1−σ}.

The view includes P_{σ}’s input x_{σ}, private random bits, and all messages sent by P_{0} and P_{1}. We say Π securely realizes the functionality f if Π correctly realizes f and, for any P′_{σ} and x_{1−σ}, there is a simulator P′′_{σ} and an x_{σ} such that P′′_{σ}(f(x_{0}, x_{1})) ≈ V_{Π}^{P′_{σ}} (x_{0}, x_{1}). Notice that given f(x_{0}, x_{1}), P′_{σ} could just use P′′_{σ} to simulate his interaction with P_{1−σ} without actually running Π. Thus if Π securely implements f, neither party learns more from the interaction than could be learned from just f(x_{0}, x_{1}).

Define the view of party P interacting in protocol Π up through round j by V_{Π,j}^{P}(x̄). When party P_{σ} is not executing Π but is drawing from B instead, we denote this “protocol” by Π : B_{σ}.

Definition 1. (Covert two-party protocol against honestbut-curious adversaries) We say an n-round, two-party protocol (P_{0}, P_{1}) covertly realizes the functionality f for bidirectional channel B if it securely realizes f and if it has the following additional properties:

1. (External covertness): For any input x̄,

⟨P_{0}(x_{0}), P_{1}(x_{1})⟩ ≈ B .

2. (Internal covertness): For any input x̄, V_{Π,n}^{P_{0}}(x̄) ≈ V_{Π:B_{1},n}^{P_{0}}(x̄) and V_{Π,n−1}^{P_{1}}(x̄) ≈ V_{Π:B_{0},n−1}^{P_{1}}(x̄).

3. (Final Covertness): For every PPT D there exists a PPT D′ and a negligible ν such that for any x_{1} and any distribution X_{0}, Adv_{V_{Π}^{P_{1}} (X_{0},x_{1}),V_{Π:B_{0}}^{P_{1}} (X_{0},x_{1})}^{D}(k) ≤

Adv_{f(X_{0},x_{1}),U_{l}}^{D′}(k) + ν(k).

In other words, until the final round, neither party can distinguish between the case that the other is running the protocol or just drawing from B; and after the final message, P_{0} still cannot tell, while P_{1} can only distinguish the cases if f(x_{0}, x_{1}) and U_{m} are distinguishable.

We will slightly abuse notation and say that a protocol which has messages indistinguishable from random bits (even given one party’s view) is covert for the uniform channel U.

3.2 Modifying Yao’s Protocol For Two-Party

Secure Function Evaluation

Yao’s protocol [22] securely (not covertly) realizes any functionality f that is expressed as a combinatorial circuit. The protocol is run between two parties, the Input Owner A and the Program Owner B. The input of A is a value x, and the input of B is a circuit to compute the function f. At the end of the protocol, A learns f(x) (and nothing else about f) and B learns nothing about x. At a high level view, the protocol and its modification work as follows (we describe all the details in the Appendix):

• B first produces a “garbled” version of the circuit by assigning to every wire of the circuit two random k-bit strings to denote the values 0 and 1.

• B then uses a semantically secure encryption scheme to produce a description of the circuit such that given the garbled input values corresponding to x, A can compute the garbled output.

• A and B then perform |x| executions of 1-out-of-2 oblivious transfer (OT_{1}^{2}) in which A learns the garbled input values corresponding to x and nothing else. In the Appendix, we show how to modify a OT_{1}^{2} protocol from [19] so that it is covert for the uniform channel:

Protocol 1. (Basic steganographic encoding/decoding routines)

Procedure Encode^{D}: Input: H ∈ ℍ, c ∈ {0, 1}^{m} Let j = 0 repeat:

sample s ← D, set j = j + 1 until H(s) = c OR (j > k) Output: s Procedure Decode: Input: H ∈ ℍ, s ∈ D set c = H(s) Output: c

Lemma 1. Under the Decisional Diffie-Hellman assumption, there exists a protocol which covertly realizes OT_{1}^{2} for the uniform channel.

• Finally, B sends A the encrypted description of the circuit and an interpretation table that allows A to interpret the garbled output values.

Lemma 2. It is possible to instantiate Yao’s protocol so that the garbled circuit and interpretation table are indistinguishable from uniform bits

For completeness, we describe the full protocol in the Appendix, where we also prove:

Theorem 1. Any functionality f can be covertly realized for the uniform channel, U.

3.3 Steganographic Encoding

We use provably secure steganography to transform the above protocol into a covert two-party protocol for any bidirectional channel B satisfying the properties mentioned in Section 2. We also use steganography as a building block for all other covert protocols presented in this paper. For completeness we state a construction that has appeared in various forms in [7, 17, 2, 3].

Let ℍ denote a family of hash functions H : D → {0, 1}^{c} which is pairwise independent. Let D denote an arbitrary probability distribution on D. The functions in Protocol 1 hide and recover m uniformly-chosen bits in a distribution indistinguishable from D when H_{∞}(D) = ω(log k) and m = O(log k).

Proposition 1. Let H ← ℍ. Then

Δ ((H, Encode^{D}(H, U_{m})), (H, D)) ≤ 2^{−(ℓ(k)−m)/2+1} .

The result follows from the Leftover Hash Lemma ([16], Lemma 4.8). Intuitively, it guarantees that Encode(c) will be (statistically) indistinguishable from the messages exchanged in a bidirectional channel whenever c is a uniformly chosen bit string. (When we refer to Encode with only a single argument, we implicitly assume that an appropriate H has been chosen and is publicly accessible to all parties.)

Thus, to guarantee covertness for channel B, we will ensure that all our protocols generate messages that are indistinguishable from uniformly chosen random bits and then encode these messages with Encode. Formally, suppose Π = (P_{0}, P_{1}) is an arbitrary two-party protocol which securely realizes the functionality f. We will construct a protocol Σ^{Π} = (S_{0}^{P_{0}}, S_{1}^{P_{1}}) which has the property that if V_{Π}^{P_{b}}(x̄) is indistinguishable from uniformly chosen bits (that is, Π covertly realizes f for the uniform channel), then Σ^{Π} covertly realizes the functionality f for channel B. We assume that P_{0}, P_{1} have the property that, given a partial input, they return the string ε, indicating that more bits of input are needed.

Then S_{b}^{P_{b}} has the following round function (which simply uses Encode and Decode to encode and decode all messages exchanged by P_{0} and P_{1}):

Protocol 2. (Transformation to a covert protocol)

Procedure S_{b}^{P_{b}}: Input: history h ∈ H, state, document s ∈ D draw d ← B_{h}^{P_{b}} if (state.status = “receiving”) then set state.msg = state.msg∥Decode(s); set c = P_{b}(state.msg) if (c ≠ ε) set state.status = “sending”; set state.msg = c if (state.status = “sending” and d ≠⊥) then set c, state.msg = state.msg, where |c| = m; set d = Encode^{(B_{h}^{P_{b}} ≠⊥)}(c) if state.msg = “” set state.status = “receiving” Output: message d, state

Theorem 2. If Π covertly realizes the functionality f for the uniform channel, then Σ^{Π} covertly realizes f for the bidirectional channel B.

Proof. Let k^{c} be an upper bound on the number of bits in ⟨P_{0}(x_{0}), P_{1}(x_{1})⟩. Then Σ^{Π} transmits at most 2k^{c}/m (non-empty) documents. Suppose there is a distinguisher D for V_{Σ}^{S_{b}}(x̄) from V_{Σ:B_{1−b}}^{S_{b}}(x̄) with significant advantage ϵ.

Then D can be used to distinguish V_{Π}^{P_{b}}(x̄) from V_{Π:U_{1−b}}^{P_{b}}(x̄), by simulating each round as in Σ to produce a transcript T; If the input is uniform, then Δ(T, B) ≤ (k^{c}/m)2^{2−(ℓ(k)−m)/2} = ν(k), and if the input is from Π, then T is identical to V_{Σ}^{S_{b}}(x̄). Thus D’s advantage in distinguishing Π from Π : U_{1−b} is at least ϵ − ν(k).

IMPORTANT: For the remainder of the paper we will present protocols Π that covertly realize f for U. It is to be understood that the final protocol is meant to be Σ^{Π}, and that when we state that “Π covertly realizes the functionality f” we are referring to Σ^{Π}.

3.4 Combining The Pieces

We can combine Lemma 1 along with Theorem 1 to construct a protocol which covertly realizes any two-party functionality. The final protocol, which we call covert-yao, is simple: assume that both parties know a circuit C_{f} computing the functionality f. Bob first uses the modified Yao’s protocol to create a garbled circuit for f(·, x_{B}). Alice and Bob perform |x_{A}| modified oblivious transfers for the garbled wire values corresponding to Alice’s inputs. Bob sends the garbled gates to Alice, along with the information necessary to de-garble the outputs. Finally, Alice outputs f(x_{A}, x_{B}).

Theorem 3. The covert-yao protocol covertly realizes the functionality f.

Notice that as the protocol covert-yao is described, it is necessary that Bob does not learn the output, because a malicious Bob could give Alice a garbled circuit with different operations in the gates, which could actually output some constant message giving away Alice’s participation even when the value f(x_{0}, x_{1}) would not.

4. FAIR COVERT TWO-PARTY COMPU-TATION AGAINST MALICIOUS ADVER-SARIES

The protocol presented in the previous section has two serious weaknesses. First, because Yao’s construction conceals the function of the circuit, a malicious Bob can garble a circuit that computes some function other than the result Alice agreed to compute. In particular, the new circuit could give away Alice’s input or output some distinguished string that allows Bob to determine that Alice is running the protocol. Additionally, the protocol is unfair: either Alice or Bob does not get the result.

In this section we present a protocol that avoids these problems. In particular, our solution has the following properties: (1) If both parties follow the protocol, both get the result; (2) If Bob cheats by garbling an incorrect circuit, neither party can tell whether the other is running the protocol, except with negligible advantage; and (3) Except with negligible probability, if one party terminates early and computes the result in time T, the other party can compute the result in time at most O(T). Our protocol is secure in the random oracle model, under the Decisional Diffie-Hellman assumption. We show at the end of this section, however, that our protocol can be made to satisfy a slightly weaker security condition without the use of a random oracle. (We note that the technique used in this section has some similarities to one that appears in [1].)

4.1 De�nitions

We assume the existence of a non-interactive bitwise commitment scheme with commitments that are indistinguishable from random bits. An example is the well-known scheme that commits to bit b by cmt(b; (r, x)) = r∥π(x)∥(x · r) ⊕ b, where π is a one-way permutation on domain {0, 1}^{k}, x · y denotes the inner-product of x and y over GF (2), and x, r ← U_{k}. (The integer DDH assumption implies the existence of π.) Commitment to a multiple-bit string s, CMT (s; ·), can be implemented by committing to the individiual bits of s.

Let f denote the functionality we wish to compute. We say that f is fair if for every distinguisher D_{σ} distinguishing f(X_{0}, X_{1}) from U given X_{σ} with advantage at least ϵ, there is a distinguisher D_{1−σ} with advantage at least ϵ − ν(k), for a negligible function ν. (That is, if P_{0} can distinguish f(X_{0}, X_{1}) from uniform, so can P_{1}.) We say f is strongly fair if (f(X_{0}, X_{1}), X_{0}) ≈ (f(X_{0}, X_{1}), X_{1}).

A n-round, two-party protocol Π = (P_{0}, P_{1}) to compute functionality f is said to be a strongly fair covert protocol for the bidirectional channel B if the following conditions hold:

• (External covertness): For any input x̄,

⟨P_{0}(x_{0}), P_{1}(x_{1})⟩ ≈ B

.

• (Strong Internal Covertness): There exists a PPT E (an extractor) such that if PPT D(V) distinguishes between V_{Π,i}^{P_{σ}} (x̄) and V_{Π:B_{1−σ},i}^{P_{σ}}(x̄) with advantage ϵ, E^{D}(V_{Π}^{P_{σ}} (x̄)) computes f(x̄) with probability at least ϵ/poly(k)

• (Strong Fairness): If the functionality f is fair, then for any C_{σ} running in time T such that Pr[C_{σ}(V_{Π,i}^{σ}(x̄)) = f(x̄)] ≥ ϵ, there exists a C_{1−σ} running in time O(T) such that

Pr[C_{1−σ}(V_{Π,i}^{1−σ}(x̄)) = f(x̄)] = Ω(ϵ) .

• (Final Covertness): For every PPT D there exists a PPT D′ and a negligible ν such that for any x_{σ} and distribution X_{1−σ}, Adv_{V_{Π}^{Pσ} (X_{1−σ},x_{σ}),V_{Π:B_{1−σ}}^{Pσ} (X_{1−σ},x_{σ})}^{D}(k)

≤ Adv_{f(X_{1−σ},x_{σ}),U_{l}}^{D′}(k) + ν(k).

Intuitively, the Internal Covertness requirement states that “Alice can’t tell if Bob is running the protocol until she gets the answer,” while Strong Fairness requires that “Alice can’t get the answer unless Bob can.” Combined, these requirements imply that neither party has an advantage over the other in predicting whether the other is running the protocol.

4.2 Construction

As before, we have two parties, P_{0} (Alice) and P_{1} (Bob), with inputs x_{0} and x_{1}, respectively, and the function Alice and Bob wish to compute is f : {0, 1}^{l_{0}} × {0, 1}^{l_{1}} → {0, 1}^{l}, presented by the circuit C_{f}. The protocol proceeds in three stages: COMMIT, COMPUTE, and REVEAL. In the COMMIT stage, Alice picks k + 2 strings, r_{0}, and s_{0}[0], s_{0}[1], …, s_{0}[k], each k bits in length. Alice computes commitments to these values, using a bitwise commitment scheme which is indistinguishable from random bits, and sends the commitments to Bob. Bob does likewise (picking strings r_{1}, s_{1}[0], …, s_{1}[k]).

The next two stages involve the use of a pseudorandom generator G : {0, 1}^{k} → {0, 1}^{l} which we will model as a random oracle for the security argument only: G itself must have an efficiently computable circuit. In the COMPUTE stage, Alice and Bob compute two serial runs (“rounds”) of the covert Yao protocol described in the previous section. If neither party cheats, then at the conclusion of the COM-PUTE stage, Alice knows f(x_{0}, x_{1}) ⊕ G(r_{1}) and Bob’s value s_{1}[0]; while Bob knows f(x_{0}, x_{1}) ⊕ G(r_{0}) and Alice’s value s_{0}[0]. The REVEAL stage consists of k rounds, where each round consists of two runs of the covert-yao protocol. At the end of each round i, if nobody cheats, Alice learns the i^{th} bit of Bob’s string r_{1}, labeled r_{1}[i] and also Bob’s value s_{1}[i]. After k rounds in which neither party cheats, Alice thus knows r_{1} and can compute f(x_{0}, x_{1}) by computing the exclusive-or of G(r_{1}) with the value she learned in the COM-PUTE stage, and Bob can likewise compute the result.

Each circuit sent by Alice must check that Bob has obeyed the protocol; thus at every round of every stage, the circuit that Alice sends to Bob takes as input the opening of all of Bob’s commitments, and checks to see that all of the bits Alice has learned so far are consistent with Bob’s input. The difficulty to overcome with this approach is that the result of the check cannot be returned to Alice without giving away that Bob is running the protocol. To solve this problem, Alice’s circuits also take as input the last value s_{0}[i−1] that Bob learned. If Alice’s circuit ever finds that the bits she has learned are inconsistent with Bob’s input, or that Bob’s input for s_{0}[i − 1] is not consistent with the actual value of s_{0}[i − 1], the output is a uniformly chosen string of the appropriate length. Once this happens, all future outputs to Bob will also be independently and uniformly chosen, because he will have the wrong value for s_{0}[i], which will give him the wrong value for s_{0}[i + 1], etc. Thus the values s_{0}[1], …, s_{0}[k] serve as “state” bits that Bob maintains for Alice. The analogous statements hold for Bob’s circuits and Alice’s inputs.

Protocol 3. (Fair covert two-party computation)

Inputs and setup. To begin, each party P_{σ} chooses k + 2 random strings r_{σ}, s_{σ}[0],…,s_{σ}[k] ← U_{k}. P_{σ}’s inputs to the protocol are then X_{σ} = (x_{σ}, r_{σ}, s_{σ}[0], …, s_{σ}[k]).

COMMIT stage. Each party P_{σ} computes the commitment κ_{σ} = CMT (X_{σ}; ρ_{σ}) using randomness ρ_{σ}, and sends this commitment to the other party. Denote by K_{σ} the value that P_{σ} interprets as a commitment to X_{1−σ}, that is, K_{0} denotes the value Alice interprets as a commitment to Bob’s input X_{1}.

COMPUTE stage. The COMPUTE stage consists of two serial runs of the covert-yao protocol.

1. Bob garbles the circuit compute_{1} shown in figure 1, which takes x_{0}, r_{0}, s_{0}[0], …,s_{0}[k], and ρ_{0} as input and outputs G(r_{1}) ⊕ f(x_{0}, x_{1})∥s_{1}[0] if K_{1} is a commitment to X_{0}. If this check fails, COMPUTE_{1} outputs a uniformly chosen string, which has no information about f(x_{0}, x_{1}) or s_{1}[0]. Bob and Alice perform the covertyao protocol; Alice labels her result F_{0}∥S_{0}[0].

2. Alice garbles the circuit compute_{0} shown in figure 1, which takes x_{1}, r_{1}, s_{1}[0],…,s_{1}[k], and ρ_{1} as input and outputs G(r_{0}) ⊕ f(x_{0}, x_{1})∥s_{0}[0] if K_{0} is a commitment to X_{1}. If this check fails, compute_{0} outputs a uniformly chosen string, which has no information about f(x_{0}, x_{1}) or s_{0}[0]. Bob and Alice perform the covertyao protocol; Bob labels his result F_{1}∥S_{1}[0].

REVEAL stage. The REVEAL stage consists of k rounds, each of which consists of 2 runs of the covert-yao protocol:

1. In round i, Bob garbles the circuit reveal_{1}^{i} shown in figure 1, which takes input x_{0}, S_{0}[i−1], r_{0}, s_{0}[0 … k], ρ_{0} and checks that:

• Bob’s result from the COMPUTE stage, F_{1}, is consistent with x_{0}, r_{0}.

• The bit R_{1}[i − 1] which Bob learned in round i − 1 is equal to bit i − 1 of Alice’s secret r_{0}. (By convention, and for notational uniformity, we will define R_{0}[0] = R_{1}[0] = r_{0}[0] = r_{1}[0] = 0)

• The state S_{0}[i−1] that Bob’s circuit gave Alice in the previous round was correct. (Meaning Alice obeyed the protocol up to round i − 1.)

• Finally, that the state S_{1}[i−1] revealed to Bob in the previous round was the state s_{0}[i − 1] which Alice committed to in the COMMIT stage.

If all of these checks succeed, Bob’s circuit outputs bit i of r_{1} and state s_{1}[i]; otherwise the circuit outputs a uniformly chosen (k + 1)-bit string. Alice and Bob perform covert-yao and Alice labels the result R_{0}[i], S_{0}[i].

2. Alice garbles the circuit reveal_{0}^{i} depicted in figure 1 which performs the analogous computations to reveal_{1}^{i}, and performs the covert-yao protocol with Bob. Bob labels the result R_{1}[i], S_{1}[i].

After k such rounds, if Alice and Bob have been following the protocol, we have R_{1} = r_{0} and R_{0} = r_{1} and both parties can compute the result. The “states” s are what allow Alice and Bob to check that all previous outputs and key bits (bits of r_{0} and r_{1}) sent by the other party have been correct, without ever receiving the results of the checks or revealing that the checks fail or succeed.

Theorem 4. Construction 3 is a strongly fair covert protocol realizing the functionality f

Proof. (Sketch) The correctness of the protocol follows by inspection. The two-party security follows by the security of Yao’s protocol. Now suppose that some party, wlog Alice, cheats (by sending a circuit which computes an incorrect result) in round j. Then, the key bit R_{0}[j + 1] and state S_{0}[j + 1] Alice computes in round j + 1 will be randomized; and with overwhelming probability every subsequent result that Alice computes will be useless. Assuming Alice can distinguish f(x_{0}, X_{1}) from uniform, she can still compute the result in at most 2^{k−j} time by exhaustive search over the remaining key bits. By successively guessing the round at which Alice began to cheat, Bob can compute the result in time at most 2^{k−j+2}. If Alice aborts at round j, Bob again can compute the result in time at most 2^{k−j+1}. If Bob cheats in round j by giving inconsistent inputs, with high probability all of his remaining outputs are randomized; thus cheating in this way gives him no advantage over aborting in round j − 1. Thus, the fairness property is satisfied.

If G is a random oracle, neither Alice nor Bob can distinguish anything in their view from uniformly chosen bits without querying G at the random string chosen by the other. So given a distinguisher D running in time p(k) for V_{Π,i}^{P_{0}}(x̄) with advantage ϵ, it is simple to write an extractor which runs D, recording its queries to G, picks one such query (say, q) uniformly, and outputs G(q) ⊕ F_{0}. Since D can only have an advantage when it queries r_{1}, E will pick q = r_{1} with probability at least 1/p(k) and in this case correctly outputs f(x_{0}, x_{1}). Thus the Strong Internal Covertness property is satisfied.

4.3 Weakly Fair Covertness

We can achieve a slightly weaker version of covertness without using random oracles. Π is said to be a weakly fair covert protocol for the channel B if Π is externally covert, and has the property that if f is strongly fair, then for every distinguisher D_{σ} for V_{Π,i}^{P_{σ}} (x̄) with significant advantage ϵ, there is a distinguisher D_{1−σ} for V_{Π,i}^{P_{1−σ}} (x̄) with advantage Ω(ϵ). Thus in a weakly fair covert protocol, we do not guarantee that both parties get the result, only that if at some point in the protocol, one party can tell that the other is running the protocol with significant advantage, the same is true for the other party.

We note that in the above protocols, if the function G is assumed to be a pseudorandom generator (rather than a random oracle), then the resulting protocol exhibits weakly fair covertness. Suppose D_{σ} has significant advantage ϵ after round i = 2j, as in the hypothesis of weak covertness. Notice that given r_{1−σ}[1], …, r_{1−σ}[j−1], G(r_{1−σ})⊕f(x̄), the remainder of P_{σ}’s view can be simulated efficiently. Then D_{σ} must be a distinguisher for G(r) given the first j − 1 bits of r. But since f is strongly fair, P_{1−σ} can apply D_{σ} to G(r_{σ}) ⊕ f(x̄) by guessing at most 1 bit of r_{σ} and simulating P_{σ}’s view with his own inputs. Thus P_{1−σ} has advantage at least ϵ/2 − ν(k) = Ω(ϵ).

5. CONCLUSION AND OPEN QUESTIONS

We have presented protocols for covert two-party computation that combine steganography with cryptographic protocols whose messages are all indistinguishable from uniformly chosen random bits. Covert two-party computation can be applied whenever the use of ordinary two-party computation raises enough suspicion to defeat its intended purpose. Our protocols are secure against semi-honest adversaries under the decisional Diffie-Hellman assumption and against malicious adversaries in the Random Oracle model.

Our work leaves room for improvement and open problems. For example, given the known theoretical issues with compute_{σ}(x_{1−σ}, r, s[0 … k], ρ) = if (K_{σ} = CMT (x_{1−σ}, r, s; ρ)) then set F = G(r_{σ}) ⊕ f(x_{0}, x_{1}) set S = s_{σ}[0] else draw F ← U_{l}, S ← U_{k}. output F ∥S reveal_{σ}^{i}(x_{1−σ}, S_{1−σ}[i−1], r, s_{1−σ}[0 … k], ρ) = Let F = G(r) ⊕ f(x_{0}, x_{1}) if (K_{σ} = CMT (x_{1−σ}, r, s_{1−σ}; ρ)

and F = F_{σ} and R_{σ}[i − 1] = r[i − 1] and S_{1−σ}[i − 1] = s_{σ}[i − 1] and S_{σ}[i − 1] = s_{1−σ}[i − 1])

then

set R = r_{σ}[i], S = s_{σ}[i] else

draw R ← {0, 1}, S ← U_{k} output R∥S

Figure 1: The circuits compute and reveal.

the random oracle methodology [8, 10, 15, 4], it is an important open problem to remove the RO assumption from the security proof for Construction 3. It seems at least plausible that constructions based on concrete assumptions such as the “knowledge-of-exponent” assumption or the “generalized BBS” assumption may allow construction of standard fair covert protocols, yet the obvious applications always destroy the final covertness property. Another open question is that of improving the efficiency of the protocols presented here, either by designing protocols for specific goals or through adapting efficient two-party protocols to provide covertness.

An interesting question is whether the notion of covert two-party computation can be extended in some natural and implementable way to multiple parties. Such a generalization could have important applications in the area of anonymous communication, allowing, for instance, the deployment of undetectable anonymous remailer networks.

Shout outs to... Our homeboy Manuel Blum, our peeps Avrim Blum, Shuchi Chawla, Dr. Evil, Adam Tauman Kalai, Yael Tauman Kalai, Benny Pinkas, Mike Reiter, David Wagner, and several anonymous reviewers for their helpful comments on earlier versions of this work; the National Science Foundation for Grants CCR-0122581 and CCR-0058982 (The Aladdin Center), as well as several agencies that have supported our work on bribery but wish to remain anonymous. Luis von Ahn was partially supported by a Microsoft Research fellowship — Thanks Bill!

6. REFERENCES

[1] G. Aggarwal, N. Mishra and B. Pinkas. Secure computation of the k’th-ranked element. In: Advances in Cryptology – Proceedings of Eurocrypt ’04, pages 40–55, 2004.

[2] L. von Ahn and N. Hopper. Public-Key Steganography. In: Advances in Cryptology – Proceedings of Eurocrypt ’04, pages 323–341, 2004.

[3] M. Backes and C. Cachin. Public-Key Steganography with Active Attacks. in Theory of Cryptography Conference (TCC), pages 210-226, 2005.

[4] M. Bellare, A. Boldyreva, and A. Palacio An Uninstantiable Random-Oracle-Model Scheme for a Hybrid-Encryption Problem. In: Advances in Cryptology — Eurocrypt 2004, pages 171–188, 2004.

[5] M. Bellare and S. Micali. Non-interactive oblivious transfer and applications. Advances in Cryptology – Proceedings of CRYPTO ’89, pages 547-557, 1990.

[6] E. Brickell, D. Chaum, I. Damgärd, J. van de Graaf: Gradual and Verifiable Release of a Secret. Advances in Cryptology – Proceedings of CRYPTO ’87, pages 156-166, 1987.

[7] C. Cachin. An Information-Theoretic Model for Steganography. Information Hiding, 2nd International Workshop, pages 306-318, 1998.

[8] R. Canetti, O. Goldreich, and S. Halevi. The Random Oracle Methodology, revisited. In: Thirtieth Annual ACM Symposium on Theory of Computing, pages 209–218, 1998.

[9] N. Dedic, G. Itkis, L. Reyzin and S. Russell. Upper and Lower Bounds on Black-Box Steganography. To appear in Theory of Cryptography Conference (TCC), 2005.

[10] C. Dwork, M. Naor, O. Reignold, and L. Stockmeyer. Magic Functions. In: Proceedings of the Fortieth IEEE Symposium on Foundations of Computer Science, pages 523–534 ,1999

[11] Z. Galil, S. Haber, M. Yung. Cryptographic Computation: Secure Fault-Tolerant Protocols and the Public-Key Model. Advances in Cryptology – Proceedings of CRYPTO ’87, pages 135-155, 1987.

[12] O. Goldreich. Secure Multi-Party Computation. Unpublished Manuscript. http://philby.ucsd.edu/books.html, 1998.

[13] O. Goldreich, S. Goldwasser and S. Micali. How to construct pseudorandom functions. Journal of the ACM, vol 33, 1998.

[14] O. Goldreich, S. Micali and A. Wigderson. How to Play any Mental Game. Nineteenth Annual ACM Symposium on Theory of Computing, pages 218-229.

[15] S. Goldwasser and Y.T. Kalai. On the (in)security of the Fiat-Shamir paradigm. In: Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, pages 102–113, 2003.

[16] J. Hastad, R. Impagliazzo, L. Levin, and M. Luby. A pseudorandom generator from any one-way function. SIAM Journal on Computing, 28(4), pages 1364-1396, 1999.

[17] N. Hopper, J. Langford and L. Von Ahn. Provably Secure Steganography. Advances in Cryptology – Proceedings of CRYPTO ’02, pages 77-92, 2002.

[18] M. Naor. Bit Commitment Using Pseudorandomness. J. Cryptology 4(2): 151-158 (1991)

[19] M. Naor and B. Pinkas. Efficient Oblivious Transfer Protocols. In: Proceedings of the 12th Annual ACM/SIAM Symposium on Discrete Algorithms (SODA 2001), pages 448–457. 2001.

[20] M. Naor, B. Pinkas and R. Sumner. Privacy Preserving Auctions and Mechanism Design. Proceedings, 1999 ACM Conference on Electronic Commerce.

[21] B. Pinkas. Fair Secure Two-Party Computation. In: Advances in Cryptology – Eurocrypt ’03, pp 87–105, 2003.

[22] A. C. Yao. Protocols for Secure Computation. Proceedings of the 23rd IEEE Symposium on Foundations of Computer Science, 1982, pages 160–164.

[23] A. C. Yao. How to Generate and Exchange Secrets. Proceedings of the 27th IEEE Symposium on Foundations of Computer Science, 1986, pages 162–167.

Appendix A: Yao’s Protocol and Modi�cations

Yao’s protocol [22] securely (not covertly) realizes any functionality f that is expressed as a combinatorial circuit. Our description is based on [20]. The protocol is run between two parties, the Input Owner A and the Program Owner B. The input of A is a value x, and the input of B is a description of a function f. At the end of the protocol, B learns f(x) (and nothing else about x), and A learns nothing about f. The protocol requires two cryptographic primitives, pseudorandom functions and oblivious transfer, which we describe here for completeness.

Pseudorandom Functions. Let {F : {0, 1}^{k}×{0, 1}^{L(k)} → {0, 1}^{l(k)}}_{k} denote a sequence of function families. Let A be an oracle probabilistic adversary. We define the prfadvantage of A over F as

Adv_{F,A}^{prf}(k) = | Pr_{K}[A^{F_{K} (·)}(1^{k}) = 1] − Pr_{g}[A^{g}(1^{k}) = 1]| ,

where K ← U_{k} and g is a uniformly chosen function from L(k) bits to l(k) bits. Then F is pseudorandom if Adv_{F,A}^{prf}(k) is negligible in k for all polynomial-time A. We will write F_{K}(·) as shorthand for F_{|K|}(K, ·) when |K| is known.

Oblivious Transfer. 1-out-of-2 oblivious transfer (OT_{1}^{2}) allows two parties, the sender who knows the values m_{0} and m_{1}, and the chooser whose input is σ ∈ {0, 1}, to communicate in such a way that at the end of the protocol the chooser learns m_{σ}, while learning nothing about m_{1−σ}, and the sender learns nothing about σ. Formally, let O = (S, C) be a pair of interactive PPT programs. We say that O is correct if Pr[O_{C}((m_{0}, m_{1}), σ) = m_{σ}] ≥ 1−ϵ(k) for negligible ϵ. We say that O has chooser privacy if for any PPT S′ and any m_{0}, m_{1},

|Pr[S′(⟨S′(m_{0}, m_{1}), C(σ)⟩) = σ] − \frac{1}{2} | ≤ ϵ(k)

and O has sender privacy if for any PPT C′ there exists a σ and a PPT C′′ such that C′′(m_{σ}) ≈ V_{Π}^{C′}((m_{0}, m_{1}), σ). We say that O securely realizes the functionality OT_{1}^{2} if O is correct and has chooser and sender privacy.

Yao’s Protocol. Yao’s protocol is based on expressing f as a combinatorial circuit. Starting with the circuit, the program owner B assigns to each wire i two random k-bit values (W_{i}^{0}, W_{i}^{1}) corresponding to the 0 and 1 values of the wire. It also assigns a random permutation π_{i} over {0, 1} to the wire. If a wire has value b_{i} we say it has “garbled” value (W_{i}^{b_{i}}, π_{i}(b_{i})). To each gate g, B assigns a unique identifier I_{g} and a table T_{g} which enables computation of the garbled output of the gate given the garbled inputs. Given the garbled inputs to g, T_{g} does not disclose any information about the garbled output of g for any other inputs, nor does it reveal the actual values of the input bits or the output bit.

Assume g has two input wires (i, j) and one output wire out (gates with higher fan in or fan out can be accommodated with straightforward modifications). The construction of T_{g} uses a pseudorandom function F whose output length is k + 1. The table T_{g} is shown in figure 2. To compute f(x), B computes garbled tables T_{g} for each gate g, and sends the tables to A. Then, for each circuit input wire i, A and B perform an oblivious transfer,

\begin{matrix}πi(bi) & πj (bj) & value \\ 0 & 0 & (W{g(bi,bj) \atop out}, πout(bout)) ⊕ FW{bj \atop j} (Ig , 0) ⊕ FW{bi \atop i} (Ig , 0) \\ 0 & 1 & (W{g(bi,bj) \atop out}, πout(bout)) ⊕ FW{bj \atop j} (Ig , 0) ⊕ FW{bi \atop i} (Ig , 1) \\ 1 & 0 & (W{g(bi,bj) \atop out}, πout(bout)) ⊕ FW{bj \atop j} (Ig , 1) ⊕ FW{bi \atop i} (Ig , 0) \\ 1 & 1 & (W{g(bi,bj) \atop out}, πout(bout)) ⊕ FW{bj \atop j} (Ig , 1) ⊕ FW{bi \atop i} (Ig , 1) \end{matrix}

Figure 2: Table produced by Yao’s protocol for garbled gate g.

where A plays the role of the chooser (with σ = b_{i}) and B plays the role of the sender, with m_{0} = W_{i}^{0}∥π_{i}(0) and m_{1} = W_{i}^{1}∥π_{i}(1). A computes π_{j}(b_{j}) for each output wire j of the circuit (by trickling down the garbled inputs using the garbled tables) and sends these values to B, who applies π_{j}^{−1} to learn b_{j}. Alternatively, B can send the values π_{j} (for each circuit output wire j) to A, who then learns the result. Notice that the first two columns of T_{g} can be implicitly represented, leaving a “table” which is indistinguishable from uniformly chosen bits.

Covert Oblivious Transfer. As mentioned above, we guarantee the security of our protocols by ensuring that all the messages exchanged are indistinguishable from uniformly chosen random bits. To this effect, we present a modification of the protocol in [19] for oblivious transfer that ensures that all messages exchanged are indistinguishable from uniform when the input messages m_{0} and m_{1} are uniformly chosen. Our protocol relies on the well-known integer decisional Diffie-Hellman assumption:

Integer Decisional Diffie-Hellman. Let P and Q be primes such that Q divides P −1, let ℤ_{P}^{∗} be the multiplicative group of integers modulo P, and let g ∈ ℤ_{P}^{∗} have order Q. Let A be an adversary that takes as input three elements of ℤ_{P}^{∗} and outputs a single bit. Define the DDH advantage of A against 𝔾 = (g, P, Q) as:

Adv_{A}^{ddh}(𝔾) = | Pr_{a,b}[A(g^{a}, g^{b}, g^{ab}) = 1]− Pr_{a,b,c}[A(g^{a}, g^{b}, g^{c}) = 1]| ,

where the probability is taken over the random tape of A, and the uniform choice of a, b, c from ℤ_{Q}, and all the multiplications are over ℤ_{P}^{∗}. The Integer Decisional Diffie-Hellman assumption (DDH) for the sequence 𝔾_{k} = {(g_{k}, P_{k}, Q_{k})} states that for every PPT A, Adv_{A}^{ddh}(𝔾_{k}) is negligible in k. Setup. Let p = rq + 1 where 2^{k} < p < 2^{k+1}, q is a large prime, and gcd(r, q) = 1; let g generate ℤ_{p}^{∗} and thus γ = g^{r} generates the unique multiplicative subgroup of order q; let r̂ be the least integer r such that rr̂ = 1 mod q. Assume |m_{0}| = |m_{1}| < k/2. Let H : {0, 1}^{2k} × ℤ_{p} → {0, 1}^{k/2} be a pairwise-independent family of hash functions. Define the randomized mapping ϕ : ⟨γ⟩ → ℤ_{p}^{∗} by ϕ(h) = hr̂g^{βq}, for a uniformly chosen β ∈ ℤ_{r}; notice that ϕ(h)^{r} = h and that for a uniformly chosen h ∈ ⟨γ⟩, ϕ(h) is a uniformly chosen element of ℤ_{p}^{∗}. The following protocol is a simple modification of the Naor-Pinkas 2-round oblivious transfer protocol [19]:

Protocol 4. COT:

1. On input σ ∈ {0, 1}, C chooses uniform a, b ∈ ℤ_{q}, sets c_{σ} = ab mod q and uniformly chooses c_{1−σ} ∈ ℤ_{q}. C sets x = γ^{a}, y = γ^{b}, z_{0} = γ^{c_{0}}, z_{1} = γ^{c_{1}} and sets x′ = ϕ(x), y′ = ϕ(y), z′_{0} = ϕ(z_{0}), z′_{1} = ϕ(z_{1}). If the most significant bits of all of x′, y′, z′_{0}, z′_{1} are 0, C sends the least significant k bits of each to S; otherwise C picks new a, b, c_{1−σ} and starts over.

2. The sender recovers x, y, z_{0}, z_{1} by raising to the power r, picks f_{0}, f_{1} ∈ H and then:

• S repeatedly chooses uniform r_{0}, s_{0} ∈ ℤ_{q} and sets w_{0} = x^{s_{0}}γ^{r_{0}}, w′_{0} = ϕ(w_{0}) until he finds a pair with w′_{0} ≤ 2^{k}. He then sets K_{0} = z_{0}^{s_{0}}y^{r_{0}}.

• S repeatedly chooses uniform r_{1}, s_{1} ∈ ℤ_{q} and sets w_{1} = x^{s_{1}}γ^{r_{1}}, w′_{1} = ϕ(w_{1}) until he finds a pair with w′_{1} ≤ 2^{k}. He then sets K_{1} = z_{1}^{s_{1}}y^{r_{1}}.

S sends w′_{0}∥f_{0}∥f_{0}(K_{0}) ⊕ m_{0}∥w′_{1}∥f_{1}∥f_{1}(K_{1}) ⊕ m_{1}

3. C recovers K_{σ} = (w′_{σ})^{rb} and computes m_{σ}.

Lemma 3. S cannot distinguish between the case that C is following the COT protocol and the case that C is drawing from U_{k}; that is,

V_{COT}^{S}(m_{0}, m_{1}, σ) ≈ V_{COT:U_{C}}^{S} (m_{0}, m_{1}, σ).

Proof. Suppose that there exists a distinguisher D with advantage ϵ. Then there exists a DDH adversary A with advantage at least ϵ/8 − ν(k) for a negligible ν. A takes as input a triple (γ^{a}, γ^{b}, γ^{c}), picks a random bit σ, sets z_{σ} = γ^{c} and picks a uniform z′_{1−σ} ∈ {0, 1}^{k}, and computes x′ = ϕ(γ^{a}), y′ = ϕ(γ^{b}), z′_{σ} = ϕ(z_{σ}); if all three are at most 2^{k}, then A outputs D(x′, y′, z′_{0}, z′_{1}), otherwise A outputs 0.

Clearly, when c ≠ ab,

Pr[A(γ^{a}, γ^{b}, γ^{c}) = 1] ≥ \frac{1}{8} Pr[D(V_{COT:U_{C}}^{S}) = 1] ,

since the elements passed by A to D are uniformly chosen and D calls A with probability at least 1/8 (since each of x′, y′, z′_{σ} are greater than 2^{k} with probability at most 1/2). But when c = ab, then

Pr[A(γ^{a}, γ^{b}, γ^{c}) = 1] ≥ (1/8 − ν(k)) Pr[D(V_{COT}^{S}) = 1] ,

since the elements passed by A to D are chosen exactly according to the distribution on C’s output specified by COT; and since the probability that D is invoked by A is at least 1/8 when c ≠ ab it can be at most ν(k) less when c = ab, by the Integer DDH assumption. Thus the DDH advantage of A is at least ϵ/8 − ν(k). Since ϵ/8 must be negligible by the DDH assumption, we have that D’s advantage must also be negligible.

Lemma 4. When m_{0}, m_{1} ← U_{k/2}, C cannot distinguish between the case that S is following the COT protocol and the case that S is sending uniformly chosen strings. That is,

V_{COT}^{C}(U_{k/2}, U_{k/2}, σ) ≈ V_{COT:U_{S}}^{C} (U_{k/2}, U_{k/2}, σ) .

Proof. The group elements w_{0}, w_{1} are uniformly chosen by S; thus when m_{0}, m_{1} are uniformly chosen, the message sent by S must also be uniformly distributed.

Lemma 5. The COT protocol securely realizes the OT_{1}^{2} functionality.

Proof. The protocol described by Pinkas and Naor is identical to the COT protocol, with the exception that ϕ is not applied to the group elements x, y, z_{0}, z_{1}, w_{0}, w_{1} and these elements are not rejected if they are greater than 2^{k}. Suppose an adversarial sender can predict σ with advantage ϵ in COT; then he can be used to predict σ with advantage ϵ/16 − ν(k) in the Naor-Pinkas protocol, by applying the map ϕ to the elements x, y, z_{0}, z_{1} and predicting a coin flip if not all are less than 2^{k}, and otherwise using the sender’s prediction against the message that COT would send. Likewise, any bit a chooser can predict about (m_{0}, m_{1}) with advantage ϵ in COT, can be predicted with advantage ϵ/4 in the Naor-Pinkas protocol: the Chooser’s message can be transformed into elements of ⟨γ⟩ by taking the components to the power r, and the resulting message of the Naor-Pinkas sender can be transformed by sampling from w′_{0} = ϕ(w_{0}), w′_{1} = ϕ(w_{1}) and predicting a coin flip if either is greater than 2^{k}, but otherwise giving the prediction of the COT chooser on w′_{0}∥f_{0}∥f_{0}(K_{0})⊕m_{0}∥w′_{1}∥f_{1}∥f_{1}(K_{1})⊕ m_{1}.

Theorem 5. Protocol COT covertly realizes the uniform-OT_{1}^{2} functionality

We can combine the components developed up to this point to make a protocol which covertly realizes any twoparty functionality. The final protocol, which we call covertyao, is simple: assume that both parties know a circuit C_{f} computing the functionality f. Bob first uses Yao’s protocol to create a garbled circuit for f(·, x_{B}). Alice and Bob perform |x_{A}| covert oblivious transfers for the garbled wire values corresponding to Alice’s inputs. Bob sends the garbled gates to Alice. Finally, Alice collects the garbled output values and sends them to Bob, who de-garbles these values to obtain the output.

Theorem 1. covert-yao covertly realizes any functionality f for the uniform channel.

Proof. That (Alice, Bob) securely realize the functionality f follows from the security of Yao’s protocol. Now consider the distribution of each message sent from Alice to Bob:

• In each execution of COT: each message sent by Alice is uniformly distributed

• Final values: these are masked by the uniformly chosen bits that Bob chose in garbling the output gates. To an observer, they are uniformly distributed.

Thus Bob’s view, until the last round, is in fact identically distributed when Alice is running the protocol and when she is drawing from U. Likewise, consider the messages sent by Bob:

• In each execution of COT: because the W_{i}^{b} from Yao’s protocol are uniformly distributed, Theorem 5 implies that Bob’s messages are indistinguishable from uniform strings.

• When sending the garbled circuit, the pseudorandomness of F and the uniform choice of the W_{i}^{b} imply that each garbled gate, even given one garbled input pair, is indistinguishable from a random string.

Thus Alice’s view after all rounds of the protocol is indistinguishable from her view when Bob draws from U.

If Bob can distinguish between Alice running the protocol and drawing from B after the final round, then he can also be used to distinguish between f(X_{A}, x_{B}) and U_{l}. The approach is straightforward: given a candidate y, use the simulator from Yao’s protocol to generate a view of the “data layer.” If y ← f(X_{A}, x_{B}), then, by the security of Yao’s protocol, this view is indistinguishable from Bob’s view when Alice is running the covert protocol. If y ← U_{l}, then the simulated view of the final step is distributed identically to Alice drawing from U. Thus Bob’s advantage will be preserved, up to a negligible additive term.