MIT-LCS-TM-647 The Security Power of the Ballot Box

We show that any function f can be securely evaluated by a pro-tocol with ballots and a ballot box. That is, n mutually suspicious players, each player i possessing a secret input xi, can use ballots and ballot boxes to jointly evaluate f(x1,..., xn) = (y1,..., yn), so that (no matter how many players may collude and deviate from their pre-scribed instructions, and no matter how long they compute!) each player i learns exactly yi with the same privacy and correctness as if all players privately handed their secret inputs to a trusted party, who privately evaluates f and privately returns yi to each player i. Our protocol is (1) efficient, (2) enjoys perfect privacy, (3) guaran-tees perfect correctness, (4) is universally composable in the sense of [DoMi00] and [Can01], and (5) is always collusion-free in the sense of [LMS05], even for games with secret actions. 1 Main Theorem For any function f, mapping n private inputs to a single public output, there exists an n party protocol for a ballot-box network with public opening that securely evaluates f. We now procedure to define (1) a ballot-box network, (2) a ballot-box network with public opening and (3) the notion of securely evaluating a function. In a subsequent version of this work, we will provide a proof of our main theorem, generalize our results to functions with n inputs and n outputs and explore applications to economic mechanisms