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
-
[Yao’82,Yao’86,GMW’87,G’97] 2-party SFE (using complexity assumptions)
-
[BGW’87] \(n\)-party SFE for \(n\gt 2\), \(\lfloor n/2 \rfloor - 1\)-private (information theoretic result)