]> Cryptography - Secure Function Evaluation

Suppose there are u users and each user i possesses x i{0,1 } n and a function F i:{0,1 } nu{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 ji.

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 ut users are honest. A protocol is t-secure if the adversary learns nothing about the ut user inputs beyond the outputs of the t corrupt parties.

    Usually, the goal is to construct a t-secure, t-private protocol for some tt.

  • 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 𝔽 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 2 :r 1 ,1 3 :s 1

User 2: r 2 ,s 2 𝔽 p,2 1 :r 2 ,2 3 :s 2

User 3: r 3 ,s 3 𝔽 p,3 1 :r 3 ,3 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 𝔽 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 ,zy 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 (n2 )-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{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 ...SK u. x i=SK i for i=1 ,...,u, F i=...=F u=Sign(SK 1 ...SK u,M).

  • Private auctions: (sealed bid, 2nd-price auction) x i = bid of user i. Let S=2 NDMAX(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>2 , n/2 1 -private (information theoretic result)