]> Cryptography - Secure Function Evaluation

Suppose there are $u$ users and each user $i$ possesses ${x}_{i}\in \left\{0,1{\right\}}^{n}$ and a function ${F}_{i}:\left\{0,1{\right\}}^{\mathrm{nu}}\to \left\{0,1{\right\}}^{m}$. Then we wish to construct a protocol such that at its completion, each user $i$ knows ${F}_{i}\left({x}_{1},...,{x}_{u}\right)$ 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 anything 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\prime$-private protocol for some $t\prime \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 {𝔽}_{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}←{𝔽}_{p},1\to 2:{r}_{1},1\to 3:{s}_{1}$

User 2: ${r}_{2},{s}_{2}←{𝔽}_{p},2\to 1:{r}_{2},2\to 3:{s}_{2}$

User 3: ${r}_{3},{s}_{3}←{𝔽}_{p},3\to 1:{r}_{3},3\to 2:{s}_{3}$

(can be done in parallel)

User 1: publishes ${y}_{1}=\left({x}_{1}-{r}_{1}-{s}_{1}\right)+{r}_{2}+{r}_{3}$

User 2: publishes ${y}_{2}=\left({x}_{1}-{r}_{2}-{s}_{2}\right)+{r}_{1}+{s}_{3}$

User 3: publishes ${y}_{3}=\left({x}_{1}-{r}_{3}-{s}_{3}\right)+{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 $\left[{x}_{1},{r}_{1},{s}_{1},{r}_{2},{r}_{3},{y}_{2},{y}_{3},{x}_{1}+{x}_{2}+x3\right]$. 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}←{𝔽}_{p}$, setting ${y}_{1}=\left({x}_{1}-{r}_{1}-{s}_{2}\right)+{r}_{2}+{r}_{3}$, and outputing $\left[{x}_{1},{r}_{1},{x}_{1},{r}_{2},{r}_{3},{y}_{2},z-{y}_{1}-{y}_{2},z\right]$. 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 $\left(n-2\right)$-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\left(x\right)$ 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\left(x\right)=y$, ${F}_{B}\left(x,y\right)=\left(y=f\left(x\right)\right)?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 \left\{0,1\right\}$ for $i=1,...,u$, ${F}_{i}=...={F}_{u}=\mathrm{MAJORITY}\left({x}_{1},...,{x}_{u}\right)$.

• Threshold signatures: Let $\mathrm{PK},\mathrm{SK}$ be a public/private key pair for some signature scheme. Take $\mathrm{SK}={\mathrm{SK}}_{1}\oplus ...\oplus {\mathrm{SK}}_{u}$. ${x}_{i}={\mathrm{SK}}_{i}$ for $i=1,...,u$, ${F}_{i}=...={F}_{u}=\mathrm{Sign}\left({\mathrm{SK}}_{1}\oplus ...\oplus {\mathrm{SK}}_{u},M\right)$.

• Private auctions: (sealed bid, 2nd-price auction) ${x}_{i}$ = bid of user $i$. Let $S=2\mathrm{ND}-\mathrm{MAX}\left({x}_{1},...,{x}_{u}\right)$. ${F}_{1}=...={F}_{u}=\left({x}_{i}=\mathrm{MAX}\left({x}_{1},...,{x}_{u}\right)\right)?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>2$, $⌊n/2⌋-1$-private (information theoretic result)