Approximation algorithms can sometimes provide efficient solutions when no efficient exact computation is known. In particular, approximations are often useful in a distributed setting where the inputs are held by different parties and are extremely large. Furthermore, for some applications, the parties want to cooperate to compute a function of their inputs without revealing more information than necessary.

If $\hat{f}$ is an approximation to $f$, secure multiparty computation of $\hat{f}$ allows the parties to compute $\hat{f}$ without revealing unnecessary information. However, secure computation of $\hat{f}$ may not be as private as secure computation of $f$, because the output of $\hat{f}$ may itself reveal more information than the output of $f$. In this paper, we present definitions of secure multiparty approximate computations that retain the privacy of a secure computation of $f$. We present an efficient, sublinear-communication, private approximate computation for the Hamming distance and an efficient private approximation of the permanent.