Computer Security and Cryptography Reading Group
May 2004 List

URL: http://www.cs.wisc.edu/areas/sec/Yao1982.pdf

URL: http://www.cs.wisc.edu/areas/sec/yao1982-ocr.pdf
(OCR'ed version, might contain errors)

Two millionaires wish to know who is richer; however, they do not want to find out inadvertently any additional information about each other's wealth. How can they carry out such a conversation?

This is a special case of the following general problem. Suppose m people wish to compute the value of a function f(x₁, x₂, x₃,..., x_m), which is an integer-valued function of $m$ integer variables x_i of bounded range. Assume initially person P_i knows the value of x_i and no other x's. Is it possible for them to compute the value of f, by communicating among themselves, without unduly giving away any information about the values of their own variables? The millionaires' problem corresponds to the case when m = 2 and f(x₁, x₂) = 1 if x₁ < x₂, and 0 otherwise. In this paper, we will give precise formulation of this general problem and describe three ways of solving it by use of one-way functions (i.e., functions which are easy to evaluate but hard to invert). These results have applications to secret voting, private querying of database, oblivious negotiation, playing mental poker, etc. We will also discuss the complexity question ``How many bits need to be exchanged for the computation'', and describe methods to prevent participants from cheating. Finally, we study the question ``What cannot be accomplished with one-way functions''.

URL: http://doi.acm.org/10.1145/28395.28420

We present a polynomial-time algorithm that, given as a input the description of a game with incomplete information and any number of players, produces a protocol for playing the game that leaks no partial information, provided the majority of the players is honest.

Our algorithm automatically solves all the multi-party protocol problems addressed in complexity-based cryptography during the last 10 years. It actually is a completeness theorem for the class of distributed protocols with honest majority. Such completeness theorem is optimal in the sense that, if the majority of the players is not honest, some protocol problems have no efficient solution.