SCS Undergraduate Thesis Topics

2005-2006 | ||

Student | Advisor(s) | Thesis Topic |

Yinmeng Zhang | Lenore Blum/Luis von Ahn | Covert Multi-Party Computation |

We introduce an extension of {\it covert two-party computation} (as introducted by von Ahn, Hopper, Langford in 2005), to multiple parties. {\it Covert computation} is a stronger notion of security than standard secure computation. Like standard secure multi-party computation, covert multi-party computation allow $n$ parties with secret $x_1$ through $x_n$ respectively, to compute a function $f(x_1,\dots,x_n)$ without leaking any additional information about their inputs. In addition, covert multi-party computation guarantees that even the existence of a computation is hidden from all protocol participants unless the value of the function mandates otehrwise. This allows the construction of protocols that return $f(x_1,\dots,x_n)$ only when it equals a certain value of interest (such as ``Yes, we want to collude with each other'') but for which {\em no party can determine whether anyone else even ran the protocol whenever $f(x_1,\dots,x_n)$ is not a value of interest.} Since existing techniques for secure function evaluation always reveal that both parties participate in the computation, covert computation requires the introduction of new techniques based on provably secure steganography. We introduce two plausible security definitions for covert multi-party computation and show that the first is too strong, but that its relaxation can be achieved by a general protocol.

Close this window