  We consider private function evaluation to provide query responses based on
private data of multiple untrusted entities in such a way that each cannot
learn something substantially new about the data of others. First, we introduce
perfect non-stochastic privacy in a two-party scenario. Perfect privacy amounts
to conditional unrelatedness of the query response and the private uncertain
variable of other individuals conditioned on the uncertain variable of a given
entity. We show that perfect privacy can be achieved for queries that are
functions of the common uncertain variable, a generalization of the common
random variable. We compute the closest approximation of the queries that do
not take this form. To provide a trade-off between privacy and utility, we
relax the notion of perfect privacy. We define almost perfect privacy and show
that this new definition equates to using conditional disassociation instead of
conditional unrelatedness in the definition of perfect privacy. Then, we
generalize the definitions to multi-party function evaluation (more than two
data entities). We prove that uniform quantization of query responses, where
the quantization resolution is a function of privacy budget and sensitivity of
the query (cf., differential privacy), achieves function evaluation privacy.
