Tomas Vinar. Privatne vypocitatelne funkcie (Privately Computable Functions). Master thesis, Comenius University Bratislava, April 1999.
Download preprint: 99mthesis.ps, 498Kb
Download from publisher: not available
Related www page: not available
Bibliography entry: BibTeX
See also: early version
Consider $n$ players where $i$th player has a number $x_i$. They want to compute a value $x=f(x_1,\dots,x_n)$ where $f$ is a given function. In addition no player wants to release any information (in information theoretic sense) which cannot be derived from the value of $x$ to other players. We call such computation unconditionally private computation. The most of thesis is a survey on results achieved in this field. However we have introduced several new achievements. We have completed a constructive proof of private functions characterization theorem in two-party case. This proof gives private protocol for every private function of two variables which optimal in number of rounds. In two-party case we also generalized most results to the case of protocols which halt with probability 1. In multi-party case we have formulated problem involving computability in the case of infinite domains. Also we bring detailed bibliography of results and survey of open problems in the field.
Last update: 10/01/2006