# Secure Function Evaluation

Suppose there are $$u$$ users and each user $$i$$ possesses $$x_i\in\{0,1\}^n$$ and a function $$F_i:\{0,1\}^{nu} \rightarrow \{0,1\}^m$$. Then we wish to construct a protocol such that at its completion, each user $$i$$ knows $$F_i(x_1,...,x_u)$$ but knows nothing more about $$x_j$$ for $$j \ne i$$.

Clearly this could be done with a trusted third party, but we want to do it without one.

Security models:

• Honest-but-curious: all $$u$$ parties follow the protocol honestly, and a protocol is $$t$$-private if any $$t$$ parties who collude at the end of the protocol learn nothing beyond their own outputs from their transcripts.

To prove a protocol is $$t$$-private, we build a simulator that, when given inputs and outputs of $$t$$ colluding parties, generates $$t$$ transcripts from the same distribution as the actual protocol. (For this implies anything the colluding users can learn from their transcripts can be learnt from their inputs and outputs alone.)

• Malicious users: the adversary controls a fixed set of $$t$$ users. The remaining $$u-t$$ users are honest. A protocol is $$t$$-secure if the adversary learns nothing about the $$u-t$$ user inputs beyond the outputs of the $$t$$ corrupt parties.

Usually, the goal is to construct a $$t$$-secure, $$t'$$-private protocol for some $$t' \ge t$$.

• Dynamic adversary: in this case, at any time period, the adversary can corrupt any $$t$$ users.

## Example

Suppose we have three users, who’s secrets are $$x_1, x_2, x_3 \in \mathbb{F}_p$$, and their functions are $$F_1 = F_2 = F_3 = x_1 + x_2 + x_3$$.

Trivially, any valid protocol is 2-private because if two parties collude, they can determine the third party’s secret.

A 1-private protocol can be constructed by using secret sharing:

User 1: $$r_1,s_1\leftarrow\mathbb{F}_p, 1\rightarrow 2 : r_1, 1\rightarrow 3:s_1$$

User 2: $$r_2,s_2\leftarrow\mathbb{F}_p, 2\rightarrow 1 : r_2, 2\rightarrow 3:s_2$$

User 3: $$r_3,s_3\leftarrow\mathbb{F}_p, 3\rightarrow 1 : r_3, 3\rightarrow 2:s_3$$

(can be done in parallel)

User 1: publishes $$y_1 = (x_1-r_1-s_1)+r_2+r_3$$

User 2: publishes $$y_2 = (x_1-r_2-s_2)+r_1+s_3$$

User 3: publishes $$y_3 = (x_1-r_3-s_3)+s_1+s_2$$

Then each user computes $$y_1+y_2+y_3 = x_1+x_2+x_3$$.

1-privacy proof: user 1’s transcript is $$[x_1,r_1,s_1,r_2,r_3,y_2,y_3,x_1+x_2+x3]$$. Then we construct a simulator as follows: given $$x_1, z=x_1+x_2+x_3$$, we generate the transcript by picking $$r_1,s_1,r_2,r_3,y_2\leftarrow \mathbb{F}_p$$, setting $$y_1 = (x_1-r_1-s_2)+r_2+r_3$$, and outputing $$[x_1,r_1,x_1,r_2,r_3,y_2,z-y_1-y_2,z]$$. From user 1’s view, $$y_2$$ is random because user 1 never sees $$s_3$$. We can construct simulators for the other users in a similar fashion.

This protocol generalizes to $$n$$ parties and any linear combination, and becomes a $$(n-2)$$-private protocol. It is sometimes referred to as Benaloh’s protocol.

## Modeling Cryptographic Protocols

Practically any cryptographic protocol can be described in terms of SFE. For example:

• Identification: $$A$$ has a secret key $$x$$, and a public key $$f(x)$$ for some one-way function $$f$$, and wishes to prove possession of $$x$$ to $$B$$.

In SFE terms: $$A$$'s input is $$x$$, $$F_A = 0$$, $$B$$'s input is $$f(x) = y$$, $$F_B(x,y) = (y = f(x)) ? 1 : 0$$.

(The SFE model captures the fact that $$B$$ should not learn anything about $$x$$.)

• Key exchange: (secure against eavesdropping). Three parties, Alice, Bob, Eve. $$x_A = r, x_B = 0, x_E = 0, F_A = 0, F_B = r, F_E = 0$$, and Eve is passive, i.e. does not send any messages.

• Voting:$$x_i \in \{0,1\}$$ for $$i=1,...,u$$, $$F_i =...=F_u = MAJORITY(x_1,...,x_u)$$.

• Threshold signatures: Let $$PK, SK$$ be a public/private key pair for some signature scheme. Take $$SK = SK_1 \oplus ... \oplus SK_u$$. $$x_i = SK_i$$ for $$i=1,...,u$$, $$F_i =...=F_u = Sign(SK_1 \oplus ... \oplus SK_u, M)$$.

• Private auctions: (sealed bid, 2nd-price auction) $$x_i$$ = bid of user $$i$$. Let $$S = 2ND-MAX(x_1,...,x_u)$$. $$F_1 = ... =F_u = (x_i = MAX(x_1,...,x_u))? S : 0$$.

## Results

1. [Yao’82,Yao’86,GMW’87,G’97] 2-party SFE (using complexity assumptions)

2. [BGW’87] $$n$$-party SFE for $$n\gt 2$$, $$\lfloor n/2 \rfloor - 1$$-private (information theoretic result)

Ben Lynn blynn@cs.stanford.edu 💡