Secure computation

Secure computation is an important concept in the field of cryptography and is closely related to the idea of zero-knowledgeness. It refers to computational systems in which multiple parties wish to jointly compute some value based on individually held secret bits of information, but do not wish to reveal their secrets to one another in the process. For example, two individuals who each possess some secret information—$x$ and $y$, respectively—may wish to jointly compute some function $f(x,y)$ without revealing any information about $x$ and $y$ other than can be reasonably deduced by knowing the actual value of $f(x,y)$, where "reasonably deduced" is often interpreted as equivalent to computation within polynomial time. The primary motivation for studying methods of secure computation is to design systems that allow for maximum utility of information without compromising user privacy.

Secure computation was formally introduced in 1982 by A. Yao [Andrew C. Yao, [http://www.cs.wisc.edu/areas/sec/yao1982-ocr.pdf Protocols for secure computations] (extended abstract)] (incidentally, the first recipient of the Knuth Prize) as secure two-party computation, and was shortly thereafter generalized to secure multiparty computation by Goldreich, Micali and Wigderson.

References