Secure ComputationJoe KilianABOUT THE AUTHOR: Joe Kilian is a professor in the department of Computer Science atRutgers University. His research is in cryptology (theory and applied), algorithms and complexitytheory.Who are they trying to hire?Supp ose your university department is about to make a job offer, and a friend tells you thattheir department is also about to make an offer. Are you entering into a bidding war, or are thetwo departments interested in different people?You open your mouth to ask, “Are you making an offer to X?” then shut it, imagining ananswer of, “Actually, we were interested in someone else, but now that you’ve told me that X isavailable...”Your friend is similarly closed-mouthed. You are at an impasse. You both want to find outif you are interested in the same person, but you don’t want to reveal anything beyond this onebit of information. What can you do?This problem, and many others like it, makes simultaneous demands on the privacy andusability of sensitive data that go beyond the capabilities of conventional cryptography. En-crypting sensitive data is analogous to placing jewels in a safe. While in the safe, the jewels areprotected from theft, but you can’t wear them to the ball. Conventionally encrypted data maybe safe from prying eyes, but until it is decrypted it can’t be used, even by legitimate parties foragreed upon purposes.Secure computationIn the 1980s, Andrew Yao introduced the concept of secure computation. Imagine two people,Alice and Bob. Alice has private information x, and Bob has private information y. They wishto determine f (x, y) for some function f , without revealing anything more about x and y thanis implied by knowing f (x, y). In our job offer example above, f (x, y) is just the function that is1 when x = y and 0 otherwise. Yao created a generic solution to this problem that would worknot just for this particular f, but for any efficiently computable f . The amount of work doneby each party grows proportionally to the number of gates in a circuit computing f – essentiallythe number of single-bit operations needed to compute f .Shortly thereafter, Goldreich, Micali and Wigderson generalized Yao’s approach to multipleparties. In its most general form, we have n participants; Player i has private input xi. At theend of the secure computation, player i learns the value of fi(x1, . . . , xn), for some function fiagreed upon ahead of time, and nothing else. Note that in general the secure computation may1have different functions fifor different players; each player may learn something different aboutthe combined data. However, we will not use this generality in our later discussions.Voting has been cast as a secure computation in two different ways. Suppose we are having ayes/no vote, as with a referendum. We can identify 1 with “yes” and 0 with “no”. By computingthe sum of these inputs, one can figure out how many “yes” votes were cast. For a full-blownelection, with write-in votes, each vote may be some general string of characters (with somereasonable bound on the length). For this case, a natural (probabilistic) function to compute isone whose outputs is merely its inputs in random order. This approach is analogous to havingeach voter put their votes, written on identical slips of paper, into a box that is shaken wellbefore opening.The solutions of Yao, Goldreich-Micali-Wigderson, and hundreds of subsequent researchers,are beyond the scope of this article. To give some of the flavor of the techniques used, we givein an appendix some toy examples of protocols for testing equality and referendum voting.Even stating precisely what secure computation should obtain is much harder than it looks,and continues to be the subject of active investigation ([1, 13, 16, 2, 17]). Not only must weconsider what each participant learns when everyone follows the protocol, we must consider whata coalition of participants might learn if they pool all of their information together. Worse, wemust consider what these colluding participants might learn, or how they might influence theoutcome of the protocol, if they willfully violate the rules.In lieu of a full definition for secure computation, we give the basic motivation used in mostof the approaches. Imagine that the players all knew someone of imp ec cable character anddiscretion. Each player could then give this trusted center their private value (its input). Thetrusted center would then compute for each player the function of combined inputs that they weresupposed to learn. Its job complete, the trusted center forgets everything that is has learned.This is the “ideal” scenario.The ideal scenario is not immune from abuse. A colluding group of players can possiblygain some extra information or unduly influence the outcome of the secure computation bycoordinating their inputs and pooling all of the information they obtain. But this is relativelyinnocuous abuse, if it even is abuse, and more to the point is essentially impossible to preventin most scenarios, though some work has considered how to diminish even this modest level ofcollusion.From a thousand feet up, the goal of the cryptographic protocol for secure computation isto ensure that even if some “not too big” group of players collude, they cannot learn more orinfluence the outcome more than they could in the ideal scenario. As to what constitutes “nottoo big,” this varies from paper to pap e r, and depends on among other things the methodsused, the precise goals, and the underlying communication network. A common requirement isthat the colluders comprise less than half the total number of players: It would be terrible ifa collusion of 10% of the voters could determine the outcome of the election. However, moregeneral pos sibilities have been c onsidered than just looking at the size of the possible sets ofcolluders (c.f. [11, 6]).In a nutshell, there is Diogenes’s approach – find an honest man and trust him to combinethe secret data,1and there is the cryptographer’s approach – develop a clever protocol to be runby untrusted entities. The goal of the cryptographer is to simulate Diogenes’s trusted man evenif he doesn’t exist.1We leave as an exercise for the reader how to double the efficiency of Diogenes’s approach.2Secure computation in real lifeBut can we do it? For the first decade or so since the invention of secure computation, theanswer was a resounding, “Yes!...but not