There is a fundamental tension between our desire to aggregate data for useful purposes and our desire to protect the privacy of individuals. The canonical example is voting, in which we wish to add up votes without revealing any individual votes. Secure computation is a branch of cryptography that mediates and in some cases transforms this tension, allowing us to satisfy these conflicting needs to a far greater level than naively would seem possible. The research is primarily concerned with the basic theory of secure computation, determining under what conditions it is possible to obtain useful information from multiple sources of data while maximally protecting the privacy of this data. It also considers special cases under which secure computation may be particularly efficient and practical. Practical secure computation solutions would be useful for a number of applications, including electronic voting, e-commerce and access control systems.
Specific goals of this investigation include: : Classifying the power of general classes of secure computation systems, particularly those with probabilistic output behavior. : Further developing the theory of errorless reductions among secure computation primitives, in which the goals are achieved with certainty as opposed to merely with high probability. : Developing more efficient protocols for voting systems with sophisticated vote-counting mechanisms (e.g., instant runoff voting), and for other preference aggregation problems. : Finding ways to use extant information services as a means for implementing secure computations and as a resource for bridging the gap between abstract protocols and real systems.
Level of effort statement We note that the amount of summer support recommended for the principal investigator has been reduced to one month per year. At the recommended level of support, the principal investigator will make every attempt to meet the original scope of the project, as well as his level of effort. 1
