Efficient Computations over Encrypted Data Blocks

Abstract

Secure computation (i.e., performing computation while keeping inputs private) is a fundamental problem in cryptography. In this paper, we present an efficient and secure 2-party computation protocol for any function computable via a monotone formula over equality statements between data blocks, under standard cryptographic assumptions. Our result bypasses roadblocks in previous general solutions, like Yao’s garbled circuits and Gentry’s lattice-based fully homomorphic encryption, by performing secure computations over data blocks (instead of bits) and using typical-size (instead of impractically large) cryptographic keys. An important efficiency property achieved is that the number of cryptographic operations in the protocol is sublinear in the size of the circuit representing the computed function. Even though not as general as in the two mentioned techniques, the class of formulae in our result contains a large number of well-known computational problems (while previously, only single specific problems were known to satisfy the mentioned sublinear efficiency property). Our main underlying technique is a new cryptographic primitive, perhaps of independent interest, that we call real-or-random conditional transfer, built as a variant of the well-known Rabin’s oblivious transfer primitive.

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

Secure two-party computation is a fundamental cryptographic primitive with significant application potential. In the formulation of interest for this paper, there are two parties, Alice and Bob, who would like to interactively compute a function f on their inputs x and y, respectively, such that at the end of the protocol: Bob obtains f(x, y); an efficient adversary corrupting Alice learns nothing new about Bob’s input y; and an efficient adversary corrupting Bob learns nothing new about Alice’s input x, in addition to what is efficiently computable from f(x, y). The first general solution to this problem for any arbitrary function f was presented in [16], assuming that the adversary is semi-honest (i.e., he follows the protocol as the corrupted party but may at the end try any polynomial-time algorithm to learn about the other party’s input). Another important general solution for any arbitrary f was given in [10] in the scenario of secure computation among more than 2 parties. The generality of such solutions is so attractive that, even if decades after their introduction, researchers are considering improvements and optimizations (see, e.g., [11, 13]), thus bringing them closer to being usable in practice, at least in some specific scenarios (i.e., with the help of additional servers [1]). An important roadblock in this process is represented by the fact that the ‘garbled circuit’ technique from [16], using a boolean circuit representation of the function f, requires cryptographic operations for all input bits and gates in the circuit.

Recently, another general and powerful cryptographic primitive, fully homomorphic encryption, has been realized [5]. This primitive allows arbitrary polynomial-time computations over encrypted data and thus can be applied to construct secure 2-party computation protocols for any arbitrary polynomial-size circuit. Even in this case, researchers are recently considering improvements and optimizations, trying to bring it closer to being usable in practice (see, e.g., [6]). The roadblock for garbled circuits does not apply here, since fully homomorphic encryption solutions typically do operate over data blocks (instead of bits). However, another roadblock on the way to efficiency appears here: the security of all known constructions of fully homomorphic encryption is based on problems whose required key lengths are significantly high and the overall scheme is only theoretically efficient, but not in practice.

In this paper, we look for alternative approaches that attempt to combine the best features from both approaches: computing over encrypted data blocks (as in fully homomorphic encryption), limited requirements on key lengths (as in garbled circuits), and achieving solutions for a large class of problems (as in both).

Our Contribution. Our main result is an efficient and secure 2-party protocol for any polynomial-size and equality-based monotone formula, under standard cryptographic assumptions. Here, equality-based monotone formulae can be represented as polynomial-size monotone circuits on top of equality gates whose inputs are data blocks owned by either one of the two parties. The security of our protocol is proved based on the existence of secure 2-party protocols for simpler tasks: pseudo-random function evaluation and scalar product computation, which, in turn, were previously proved secure based on standard number-theoretic assumptions with conventional key lengths (see, e.g., [4, 7, 12, 15]). The main efficiency property is the protocol’s time complexity, as it only requires a number of cryptographic operations sub-linear in the size of the circuit computing the function. Specifically, it improves over the garbled circuit technique from [16] by a factor equal to the size of a data block. In practice, depending on the block size required by the specific application, this can be anywhere between a small and a very large improvement. Although not as general as the set of all polynomial-size boolean circuits, equality-based polynomial-size monotone formulae are a large class of circuits including important classes of problems, like text/pattern matching, publish/subscribe predicates, set disjointness and operations, search problems, etc.

To establish this result, we introduce a notion of real-or-random conditional transfer evaluation protocols (a variant of Rabin’s oblivious transfer protocols [14]), and present one such efficient protocol for equality, and-of-equality, and or-of-equality conditions, which might be results of independent interest. These protocols compose to any monotone formula over equalities. Moreover, they perform computations over data blocks (instead of bits), and thus improve over the solution based on the garbled circuit technique from [16] by a factor equal to the size of a data block.

2 Definitions and Background

In this section we give definitions and background useful in the rest of the document. Definitions in Sect. 2.1 are specific to the main problem of interest in the paper, and include equality-based formulae, secure 2-party function evaluation protocols, and efficiency requirements. Definitions in Sect. 2.2 are specific to our solutions to the main problem considered, and include pseudo-random functions, and secure 2-party protocols for pseudo-random function evaluation, scalar product evaluation, and real-or-random conditional transfer.

2.1 Efficient and Secure 2-Party Evaluation of Equality-Based Formulae

Algebraic Structure. We consider a ring $(R,+,\cdot )$ as the underlying algebraic structure for data blocks input to te two parties Alice and Bob. We assume values in R can be represented as $\ell$-bit strings using conventional, one-to-one, and polynomial-time computable and invertible, encoding from R to the set of $\ell$-bit binary strings.

Equality-Based Formulae. We study 2-party protocols for the computation of a subclass of boolean circuits, called equality-based formulae, and defined as follows.

Let $x=(x(1),\ldots ,x(a))$ and $y=(y(1),\ldots ,y(b))$ denote two sequences of values from ring R. An (x, y)-equality gate is a function that takes as input two values $x(i),y(j)\in R$, for some known $i\in \{1,\ldots ,a\}$ and $j\in \{1,\ldots ,b\}$, and returns 1 if $x(i)=y(j)$ and 0 otherwise. Let $f:\{0,1\}^n\rightarrow \{0,1\}$ be a boolean formula. We say that f is an equality-based formula if there exists an integer m and a boolean formula $g:\{0,1\}^m\rightarrow \{0,1\}$ such that f can be written as $g(z_1,\ldots ,z_m)$, where, for $h=1,\ldots ,m$, each variable $z_h$ is the output of an (x(i), y(j))-equality gate, for some $i\in \{1,\ldots ,a\}$ and $j\in \{1,\ldots ,b\}$. Thus, the length of the input to formula f is $n=O(m\ell )$. In our 2-party formulation of the formula evaluation problem, Alice is given x as input, Bob is given y as input and is returned f(x, y) as output. We say that f is monotone if the associated formula g only contains AND and OR gates.

Examples of equality-based monotone formulae include several variations of formulae related to well-known computational problems, such as string or pattern matching, set disjointness, publish/subscribe predicates, etc.

Secure 2-Party Function Evaluation Protocols. Let $\sigma$ denote a security parameter. A function over the set of natural numbers is negligible if for all sufficiently large natural numbers $\sigma \in {\mathcal N}$, it is smaller than $1/p(\sigma )$, for all polynomials p. Two distribution ensembles $\{D^0_\sigma :\sigma \in {\mathcal N}\}$ and $\{D^1_\sigma :\sigma \in {\mathcal N}\}$ are computationally indistinguishable if for any efficient algorithm A, the quantity $|\text{ Prob }[x\leftarrow D^0_\sigma :A(x)=1]-\text{ Prob }[x\leftarrow D^1_\sigma :A(x)=1]|$ is negligible in $\sigma$ (i.e., no efficient algorithm can distinguish if a random sample came from one distribution or the other). In a 2-party protocol execution, a party’s view is the sequence containing the party’s input, the party’s random string, and all messages received during the execution.

We use the simulation-based definition from [8] for security of 2-party function evaluation protocols in the presence of semi-honest adversaries (i.e., adversaries that corrupt one party, follow the protocol as that party and then attempt to obtain some information about the other party’s input). According to this definition, a protocol $\pi$ to evaluate a (possibly probabilistic) function f satisfies simulation-based security in the presence of a semi-honest adversary, if there exists two efficient algorithms $Sim_A,Sim_B$ (called the simulators), such that:

• 1. let $out_{S,B}$ be $Sim_B$’s output on input Bob’s input and Bob’s output (if any); then, it holds that the pair ($out_{S,A}$, Bob’s output) is computationally indistinguishable from the pair (Alice’s view, Bob’s output); and

• 2. let $out_{S,B}$ be $Sim_A$’s output on input Alice’s input and Alice’s output (if any); then, it holds that the pair (Alice’s output, $out_{S,B}$) is computationally indistinguishable from the pair (Alice’s output, Bob’s view).

In the above, the first (resp., second) condition says that a semi-honest adversary’s view when corrupting Alice (resp., Bob), can be generated by an efficient algorithm not knowing Bob’s (resp., Alice’s) input, and thus the adversary does not learn anything about the uncorrupted party’s input.

Efficiency Requirements. We will consider the following efficiency metrics, relative to a single execution of a given secure 2-party protocol:

• 1. time complexity: time between the protocol execution’s beginning and end;

• 2. communication complexity: length of all messages exchanged; and

• 3. round complexity: number of messages exchanged.

All efficiency metrics are expressed as a function of the security parameter $\sigma$, and parameters $a,b,\ell$ associated with the equality-based function that is input to the protocol. In evaluating protocol latency, we will pay special attention to the number of asymmetric cryptography operations (e.g., modular exponentiations in a large group) and of symmetric cryptographic operations (e.g., block cipher executions), since the former are typically orders of magnitude more expensive than the latter (although the latter might be applied a larger number of times). As a comparison result, we will target the general solution from [16] for the 2-party secure evaluation of function f(x, y), where x is Alice’s input and y is Bob’s input, which requires O(|y|) asymmetric cryptography operations and $O(|C_f|)$ symmetric cryptography operations, if $C_f$ denotes the size of the boolean circuit computing f. Even if we will mainly focus our efficiency analysis on time complexity, our design targets minimization of all the mentioned efficiency metrics.

2.2 Protocols and Cryptographic Primitives Used in Our Solutions

Secure Evaluation Protocols for Specific Functions. In our solutions, we use or build constructions of 2-party secure evaluation protocols for the following functionalities: pseudo-random function, scalar product, and real-or-random conditional transfer.

A secure pseudo-random function evaluation protocol (briefly, sPRFeval protocol) is a protocol between two parties: Alice, having as input a key k for a PRF F, and Bob, having as input a string x, where the description of F is known to both parties. The protocol is defined as a secure function evaluation of the value F(k, x), returned to Bob (thus, without revealing any information about x to Alice, or any information about k to Bob in addition to F(k, x)). Efficient constructions of sPRFeval protocols, based on the hardness of number-theoretic problems, were given in [4, 12].

A secure scalar product evaluation protocol (briefly, sSPeval protocol) is a protocol between two parties: Alice, having as input a t-component vector $x=(x_1,\ldots ,x_t)$ of values in R, and Bob, having as input a t-component vector $y=(y_1,\ldots ,y_t)$ of values in R. The protocol is defined as a secure function evaluation of the value $\sum _{i=1}^tx_iy_i$, computed over R and returned to Bob (thus, without revealing any information about the y values to Alice, or any information about vector x to Bob in addition to t and $\sum _{i=1}^tx_iy_i$). Efficient constructions of sSPeval protocols, based on the hardness of number-theoretic problems, were given in [7, 15].

A secure real-or-random conditional transfer protocol for the condition predicate p (briefly, p-srCTeval protocol, or srCTeval protocol when p is clear from the context) is a protocol between two parties: Alice, having as input a message m and a string x, and Bob, having as input a string y. The protocol is defined as a secure function evaluation of the value $m'$, returned to Bob, where $m'=m$ if $p(x,y)=1$ or $m'$ is computationally indistinguishable from a string random and independent from m, and of the same length as m, if $p(x,y)=0$. Thus, an execution of the protocol does not reveal any information about y to Alice, or any information about x to Bob in addition to $m'$, and $m'$ only reveals m when $p(x,y)=1$ or the (possibly padded) length of m when $p(x,y)=0$. Also, note that if m is a pseudo-random string, then at the end of a p-srCTeval protocol, Bob does not obtain any information about the value of predicate p. The notion of a p-srCTeval protocol is new but a close variant of the conditional oblivious transfer notion in [2, 3]. Specifically, it differs in additionally requiring the pseudo-randomness of $m'$ when $p(x,y)=0$. Thus, an srCTeval protocol is a conditional oblivious transfer protocol in the sense of [2, 3], but the converse may not be true. In particular, in a conditional oblivious transfer protocol, Bob may obtain information about the value of predicate p. The notion from [2, 3] is, in turn, a variant of the much studied oblivious transfer protocol notion from [14].

Pseudo-Random Function Families. A family of functions $\{r_n:n\in {\mathcal N}\}$ is a random function family if, for each value of the security parameter n, the function $r_n$ associated with that value is chosen with distribution uniform across all possible functions of the pre-defined input and output domains. A family of keyed functions $\{F_n(k,\cdot ):n\in {\mathcal N}\}$ is a pseudo-random function family (briefly, a PRF family, first defined in [9]) if, after key k is randomly chosen, no efficient algorithm allowed to query an oracle function $O_n$ can distinguish whether $O_n$ is $F_n(k,\cdot )$ or $O_n$ is a random function $R_n(\cdot )$ over the same input and output domain, with probability greater than 1 / 2 plus a negligible (in n) quantity. In practice, finite versions of PRF families (for a fixed value of the security parameter n) are implemented using very efficient and standard cryptographic primitives like block ciphers (e.g., AES), which are conjectured to behave like a pseudo-random function.

3 Real-or-Random Conditional Transfer Protocols

In this section we present our 2-party srCTeval protocols for secure evaluation of the following 3 predicates: (1) equality predicate $p_{=}$, on input x, y, returns 1 if $x=y$ and 0 otherwise; (2) OR-of-equalities predicate $p_{or,=}$, on input $x_0,x_1,y_0,y_1$, returns 1 if $(x_0=y_0)\vee (x_1=y_1)$ and 0 otherwise; (3) AND-of-equalities predicate $p_{and,=}$, on input $x_0,x_1,y_0,y_1$, returns 1 if $(x_0=y_0)\wedge (x_1=y_1)$ and 0 otherwise.

3.1 An srCTeval Protocol for the Equality Predicate

In this subsection we show the following result.

Theorem 1

Assume the existence of pseudo-random permutation families F and prF, and of an sPRFeval protocol for prF. There exists a (black-box) construction of a 2-party srCTeval protocol $\pi _{=}$ for the secure evaluation of predicate $p_{=}$, only requiring 1 execution of the sPRFeval protocol for prF and O(1) executions of F.

When the sPRFeval protocol is instantiated using the protocol in [12], one execution of prF and of the sPRFeval protocol only require O(1) asymmetric cryptography operations. Moreover, in practice, F can be instantiated using a symmetric cryptography primitive like a block cipher. Thus, $\pi _{=}$ only requires a total of O(1) asymmetric and O(1) symmetric cryptography operations, while using the general solution from [16] for the same predicate would require $O(\ell )$ asymmetric and $O(\ell )$ symmetric cryptography operations, where $\ell$ is the length of the input strings x, y. We prove Theorem 1 by describing protocol $\pi _{=}$, and showing its efficiency and security properties.

Informal and Formal Description. Alice non-interactively computes a ‘generated value’ $v_A$ for her input string x, as the output of pseudo-random function prF on input x. Bob computes, interactively with Alice, a ‘received value’ $v_B$ for his input string y, as the output of an sPRFeval protocol for pseudo-random function prF on input y. Finally, Alice sends to Bob an encryption of m using pseudo-random function F and $v_A$ as a key. Bob will return the value $m'$ obtained by decrypting Alice’s encryption using pseudo-random function F and $v_b$ as a key. Note that if $x=y$, then $v_A=v_B$ and Bob will be able to invert u into $m'=m$, while on the other hand if $x\ne y$, then $m'$ is computationally indistinguishable from a random string independent from m, by the properties of the pseudo-random function prF. We now proceed more formally.

Our equality-OT protocol is a conditional OT protocols where the condition is an equality between a string x input to Alice and a string y input to Bob. It uses an arbitrary pseudo-random function family $\{F\}$, (which can be implemented using a block cipher like AES), and the pseudo-random function family $\{prF\}$, along with its associated sPRFeval protocol (which can be implemented using the function family and protocol in [12]). Assuming Alice wants to transfer some $\ell$-bit value m to Bob under the condition that Alice’s $\ell$-bit string x is equal to Bob’s $\ell$-bit string y, the 2-party sCTeval protocol $\pi _{=}$ goes as follows:

• 1. Alice randomly chooses key k and computes $v_A = prF(k,x)$;

• 2. Alice and Bob run the sPRFeval protocol to return $v_B = prF(k,y)$ to Bob;

• 3. Alice sets key $k_A= v_A$, randomly chooses string r, computes $u = F(k_A, r)\oplus m$ and sends r, u to Bob;

• 4. Bob sets key $k_B= v_B$, computes $w' = F(k_B, r)$, $m'=u\oplus w'$ and returns: $m'$.

Remark. We note that if input values x, y are known to be drawn from a uniform or pseudo-random distribution, then steps 1 and 2 in $\pi _{=}$ can be replaced by setting $v_A=x$ and $v_B=y$. We denote such simplified protocol by $\pi _{=}^s$.

Properties of $\pi _{=}$ . We now show the efficiency and security properties of $\pi _{=}$.

The most interesting efficiency property of $\pi _{=}$ is its time complexity, in that it only requires 1 application of an sPRFeval protocol and O(1) applications of pseudo-random function F, thus resulting in O(1) asymmetric and O(1) symmetric cryptography operations, instead of O(|y|) modular exponentiations and $O(|x|+|y|)$ block cipher applications, as required by the general solution from [16]. Round and communication complexity of $\pi _{=}$ are also very efficient; specifically, as for the round (resp., communication) complexity, $\pi _{=}$ only requires at most one message (resp., $O(\ell )$ communication) more than those required by the sPRFeval protocol.

The security property is obtained by showing two efficient simulator algorithms $Sim_A$, $Sim_B$ that satisfy the simulation-based security definition in Sect. 2 for protocol $\pi _{=}$.

Algorithm $Sim_A$ takes as input m, x. First of all, it computes k and $v_A$ as in step 1 of $\pi _{=}$. Then, it simulates Alice’s view in step 2 by running, on input k, x, the analogue simulator associated with the sPRFeval subprotocol. Finally, it computes r, u as in step 3 of $\pi _{=}$, and returns: $(view_{A,sPRFeval},r,u)$, where $view_{A,sPRFeval}$ denotes Alice’s view during the simulation of the sPRFeval protocol. The correctness of the simulation directly follows from the analogue correctness property of the simulator for the sPRFeval subprotocol.

Algorithm $Sim_B$ takes as input $y,m'$. First of all, it randomly chooses $v_B'$ and simulates Bob’s view in step 2 of $\pi _{=}$ by running, on input $y,v_B'$, the analogue simulator associated with the sPRFeval subprotocol. Then it simulates Bob’s view in step 3 and 4 of $\pi _{=}$ by randomly choosing r and setting $u'=F(v_B',r)\oplus m'$. Finally, it returns: $(view_{B,sPRFeval},r,u')$, where $view_{B,sPRFeval}$ denotes Bob’s view during the simulation of the sPRFeval protocol. The correctness of the simulation when $p(x,y)=0$ follows by using the pseudo-randomness of function prF and the analogue correctness property of the simulator for the sPRFeval subprotocol. To observe that the simulation is also correct when $p(x,y)=1$, we also note that in this case $x=y$ and therefore $v_A$, even though computed from a value x unknown to $Sim_B$, is actually constrained to be equal to $v_B$. This, together with the pseudo-randomness of function prF, suffices to show that the computation of $u'$ by $Sim_B$ is a good simulation of the value u in $\pi _{=}$.

3.2 An srCTeval Protocol for the AND-of-Equality Predicate

In this subsection we show the following result.

Theorem 2

Assume the existence of a 2-party srCTeval protocol $\pi _{=}$ for the secure evaluation of predicate $p_{=}$. There exists a (black-box) construction of a 2-party srCTeval protocol $\pi _{and,=}$ for the secure evaluation of predicate $p_{and,=}$, which only requires 2 executions of $\pi _{=}$.

We note that when we use the srCTeval protocol $\pi _{=}$ from Theorem 1, one execution of this protocol only requires O(1) asymmetric cryptography operations, and thus so does one execution of $\pi _{and,=}$. Another interesting property of this protocol is that it composes $\pi _{=}$ without any additional cryptographic assumption. (This should be contrasted with the protocol in [16], where each boolean gate requires symmetric cryptography operations.)

Informal and Formal Description of $\pi _{and,=}$ . Alice has ‘generated values’ $m,x_0,x_1\in R$ as inputs and Bob has ‘received values’ $y_0,y_1\in R$ as inputs. Alice splits her input m into random $m_0,m_1\in R$ such that $m_0\cdot m_1=m$, and runs protocol $\pi _{=}$ twice, first on input $m_0$ and then on input $m_1$. Bob computes his output as the product, in R, of the outputs from the two subprotocol executions. Note that if both equalities $x_0=y_0$ and $x_1=y_1$ hold, then the values $m_0',m_1'$ received by Bob satisfy $m_0'=m_0$ and $m'_1=m_1$ and bob can thus compute m from the received values. Instead, if at least one of the two equalities does not hold, Bob receives at least one pseudo-random value $m'_{i}$, for some $i\in \{0,1\}$, and therefore the final value computed by Bob will also be pseudo-random. Formally, the 2-party sCTeval protocol $\pi _{and,=}$ goes as follows:

• 1. Alice randomly chooses $m_0,m_1\in R$ such that $m=m_0\cdot m_1$

• 2. For $i=0,1$, Alice and Bob run srCTeval protocol $\pi _{=}$ to transfer $m_i$ to Bob, with equality $`x_i=y_i$’ as the condition, thus resulting in Bob receiving $m'_i$;

• 3. Bob computes $m'=m'_0\cdot m'_1$ and returns: $m'$.

Remark. We note that if input values $x_0,y_0,x_1,y_1$ are known to be drawn from a uniform or pseudo-random distribution, then Alice and Bob can run $\pi _{=}^s$ instead of $\pi _{=}$ in the above protocol. We denote such simplified protocol by $\pi _{and,=}^s$.

Properties of $\pi _{and,=}$ . Protocol $\pi _{and,=}$ inherits the efficiency and security properties of $\pi _{=}$. In particular, with respect to time complexity, we note that if $\pi _{=}$ only requires O(1) asymmetric and symmetric cryptography operations, so does $\pi _{and,=}$.

3.3 An srCTeval Protocol for the OR-of-Equality Predicate

In this subsection we show the following result.

Theorem 3

Assume the existence of an sSPeval protocol. There exists a (black-box) construction of a 2-party srCTeval protocol $\pi _{or,=}$ for the secure evaluation of predicate $p_{or,=}$, only requiring 1 execution of the sSPeval protocol on input 4-component vectors.

We note that when we use the sSPeval protocol from [7, 15], one execution of this protocol only requires O(1) asymmetric cryptography operations, and thus so does one execution of $\pi _{or,=}$.

Informal and Formal Description of $\pi _{or,=}$ . Alice has ‘generated values’ $m,x_0,x_1\in R$ as inputs and Bob has ‘received values’ $y_0,y_1\in R$ as inputs. Alice defines expression $f(m,x_0,x_1,y_0,y_1)=m+r\cdot (x_0-y_0)\cdot (x_1-y_1)$, where r denotes a random value chosen by Alice from the same set. After some algebraic steps, we see that $f(m,x_0,x_1,y_0,y_1)=m+r\cdot x_0\cdot x_1-r\cdot y_0\cdot x_1-r\cdot x_0\cdot y_1+r\cdot y_0\cdot y_1$, which can be rewritten as the scalar product of Alice’s vector $(m+r\cdot x_0\cdot x_1,-r\cdot x_1,-r\cdot x_0,r)$ and Bob’s vector $(1,y_0,y_1,y_0\cdot y_1)$. Thus, a single execution of the sSPeval protocol with vector length $t=4$ allows Bob to securely compute $m'=f(m,x_0,x_1,y_0,y_1)$. Note that if at least one of the equalities $x_0=y_0$ and $x_1=y_1$ hold, then $m'=m$. Instead, if both equalities do not hold, $m'$ is a random value, as so is r. Formally, the 2-party sCTeval protocol $\pi _{or,=}$ goes as follows:

• 1. Alice randomly chooses r and sets $x=(m+r\cdot x_0\cdot x_1,-r\cdot x_1,-r\cdot x_0,r)$

• 2. Bob sets $y=(1,y_0,y_1,y_0\cdot y_1)$

• 3. Alice and Bob run the sSPeval protocol where Alice uses x as input and Bob uses y as input, thus resulting in Bob receiving $m'=f(m,x_0,x_1,y_0,y_1)$.

• 4. Bob returns: $m'$.

Properties of $\pi _{or,=}$ . Protocol $\pi _{or,=}$ inherits the efficiency and security properties of the sSPeval protocol used. With respect to time complexity, we note that if the sSPeval protocol only requires O(1) asymmetric computations (as in [15]), so does $\pi _{or,=}$. This still compares favorably with $O(\ell )$ asymmetric computations which would be required by the general solution in [16].

4 Secure Evaluation of Equality-Based Monotone Formulae

In this section we present our 2-party protocol for secure evaluation of any arbitrary equality-based monotone formula over Alice and Bob’s input strings. Formally, our protocol satisfies the following result.

Theorem 4

Let f be an equality-based monotone formula with m equality gates over $\ell$-bit data blocks. Assume the existence of:

• 1. pseudo-random function families F and prF,

• 2. an sPRFeval protocol for the evaluation of prF, and

• 3. an sSPeval protocol.

It is possible to provide a (black-box) construction of a 2-party protocol $\pi _f$ for the secure evaluation of f over Alice and Bob’s input strings, which only requires O(m) executions of the sPRFeval and sSPEval protocols.

We note that the sPRFeval protocol from [4] and the sSPeval protocol from [15] only require O(1) asymmetric cryptography operations, and thus an execution of $\pi _{f}$ based on them only requires O(m) asymmetric cryptography operations, which is linear in the number of equality statements in f, and is thus sublinear in the length $n=O(m\ell )$ of the input to f. We start the proof of Theorem 4 with a description of protocol $\pi _{f}$, then continue by showing its efficiency and security properties.

Informal and Formal Descriptions of $\pi _f$ . The description of protocol $\pi$ can be divided into 4 phases: Alice’s input processing, Bob’s input processing, formula processing and output computation, which we now informally describe. The first 3 phases can be seen as an srCTeval protocol for the transfer of a random string gv with the predicate being equal to the equality-based monotone formula f. This is obtained by composing the 3 srCTeval protocols in Sect. 3. The fourth phase consists of Alice letting Bob check the result of the srCTeval protocol. We now proceed more formally.

Alice’s Input Processing. This phase can be seen as a suitable generalization of step 1 in protocol $\pi _{=}$. Then, Alice randomly chooses a key k and non-interactively generates a set of pseudo-random values in correspondence of all his input values $x(1),\ldots ,x(a)$, as $gv(i)=prF(k,x(i))$, for $i=1,\ldots ,a$.

Bob’s Input Processing. This phase can be seen as a suitable generalization of step 2 in protocol $\pi _{=}$. Specifically, Bob obtains a set of pseudo-random values in correspondence of all her input values $y(1),\ldots ,y(b)$, by running with Alice one execution of the sPRFeval protocol for each $j=1,\ldots ,b$, where Alice uses key k as input, and Bob uses y(j) as input and receives $rv(j)=prF(k_a,y(j))$ as output.

Formula Processing. In this phase, each wire of the monotone circuit representing the equality-based monotone formula will be associated with one ‘generated value’, computed by Alice, and one ‘received value’, computed by Bob with Alice’s help. First of all, Alice associates one random generated value gv with the output wire and one random generated value with each internal wire. Then, for any gate $g\in \{=,or,and\}$ in the circuit, Alice and Bob run an srCTeval protocol for the transfer of the random generated value associated with g’s output wire, where the predicate is determined by g and the generated and received values associated with g’s input wires, as follows:

• 1. if g is the equality gate with generated value $x_i$ and received value $y_j$ associated with its input wires, the predicate is ‘$x_i=y_j$’ and the protocol run by Alice and Bob is $\pi _{=}^s$, where Alice’s input is generated value gv(i) and Bob’s input is received value rv(j), and gv(i), rv(j) are as computed in the previous phases;

• 2. if g is an OR gate with generated values $x_{i_0},x_{i_1}$ and received values $y_{i_0},y_{i_1}$ associated with its input wires, the predicate is ‘$(x_{i_0}=y_{i_0})\vee (x_{i_1}=y_{i_1})$’ and the protocol run by Alice and Bob is $\pi _{or,=}^s$;

• 3. if g is an AND gate with generated values $x_{i_0},x_{i_1}$ and received values $y_{i_0},y_{i_1}$ associated with its input wires, the predicate is ‘$(x_{i_0}=y_{i_0})\wedge (x_{i_1}=y_{i_1})$’ and the protocol run by Alice and Bob is $\pi _{and,=}^s$.

The value rv returned by Bob at the end of this srCTeval protocol’s execution is defined as the received value associated with the output wire of gate g. The execution of the srCTeval protocol for all gates can be performed sequentially or even in parallel, since in each of protocols $\pi _{=}^s, \pi _{or,=}^s, \pi _{and,=}^s$, the received values are only needed by Bob at the end of the protocol.

Output Computation. In the output computation phase, Alice simply sends gv to Bob, and Bob returns 1 if $gv=rv$ and 0 otherwise.

Properties of $\pi _f$ . We now show the efficiency and security properties of $\pi _f$.

As for the time complexity, $\pi _{f}$ only requires O(m) applications of an sPRFeval protocol and O(m) applications of an sSPeval protocol. When these protocols are implemented as in [4, 15], this results in O(m) asymmetric and symmetric cryptography operations, instead of $O(m\ell )$, as required in a direct application of the general solution from [16]. The communication complexity of $\pi _f$ is $O(m\ell )$, also improving over the communication complexity $O(m\ell ^2)$ that would be obtained using [16].

The security property is obtained by showing two efficient simulator algorithms $Sim_A$, $Sim_B$ that satisfy the simulation-based security definition in Sect. 2 for protocol $\pi _{f}$. Towards that goal, we first consider the invariant property maintained by protocol $\pi _f$ across all gates in the circuit computing the equality-based monotone formula f. Specifically, for each gate g, including the circuit output gate, the generated value $gv_g$ and the received value $rv_g$ associated with gate g, satisfy the following properties:

• 1. if the subformula with g as root gate is true then $rv_g=gv_g$;

• 2. if the subformula with g as root gate is false, then $rv_g$ and $gv_g$ are pseudo-independent (i.e., computationally indistinguishable from two random and independent strings).

An alternative way to express this invariant property is that, when restricted to its first three phases only, protocol $\pi _f$ is a srCTeval protocol for the transfer of random value rv, the predicate being the circuit computing the equality-based monotone formula f on input Alice and Bob’s input strings.

This invariant is proved by induction over f, as follows. For the base case, when f is a single equality statement, observe that the first 3 phases of protocol $\pi _f$ are identical to protocol $\pi _{=}$, which is an srCTeval protocol for the equality predicate, and thus by definition satisfies the invariant. Now consider the inductive case, when the root gate of the circuit computing f is an OR gate and let $gv_0,rv_0$ (resp., $gv_1,rv_1$) be the generated and received values associated with the left (resp., right) input wire to the OR gate. By the inductive hypothesis, at least one of the equalities ‘$gv_0=rv_0$’, ‘$gv_1=rv_1$’ holds if and only if formula f is satisfied. Then the invariant for the entire circuit computing f follows by the fact that in correspondence of this OR gate $\pi _f$ runs $\pi _{or,=}$, which is an srCTeval protocol for the or-of-equalities predicate. The proof is analogue in the case where the root gate of the circuit computing f is an AND gate.

Given this invariant property, we observe that $\pi _f$ can be seen as an srCTeval protocol for the predicate determined by f (in its first 3 phases), followed by a single message, containing value gv, from Alice to Bob (in its 4th phase). Then, we construct the two simulator algorithms for $\pi _f$, as follows. Simulator $Sim_A$ is exactly the same simulator of Alice’s view associated with the srCTeval protocol, since messages received by Alice in $\pi _f$ are precisely those received in the srCTeval protocol. The construction of simulator $Sim_B$ follows the same approach, but it also needs to simulate the last message from Alice in $\pi _f$. This message is simulated by $Sim_B$ as a random string if f is false, or as equal to the received value at the end of the srCTeval protocol if f is true.

5 Conclusions

We have built a framework for the design of more efficient secure function evaluation protocols. In a nutshell, this framework is built as follows: first, we consider atomic circuit operations (i.e., equality) that can be realized through secure protocols that are more efficient than known general solutions; then, we define formulae over such atomic circuits. Our main result is a technique to compose the efficient and secure protocols for atomic circuits into efficient and secure protocols for the entire formula, across a large class of formula compositions (i.e., monotone formulae). This adds a significant amount of generality to the otherwise specialized solutions for atomic circuits. Moreover, this opens the possibility of several directions for future research, including: (a) finding other atomic circuit operations which admit secure protocols that are more efficient than general solutions and well compose with the techniques in this paper; (b) generalizing the composition techniques in this paper to larger circuit classes.