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

Abstract:

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