If Alice and Bob are only interested in computing f(x,y) correctly, and not privately, then quite robust protocols are known that can tolerate a constant fraction of errors. However, none of these solutions is applicable in the setting of privacy, as they inherently leak information about the parties' inputs. This leads to the question whether we can simultaneously achieve privacy and error-resilience against a constant fraction of errors.
We show that privacy and error-resilience are contradictory goals. In particular, we show that for every constant c > 0, there exists a function f which is privately computable in the error-less setting, but for which no private and correct protocol is resilient against a c-fraction of errors.Category / Keywords: foundations / Interactive communication, coding, adversarial noise, private function evaluation, information-theoretic security. Date: received 6 May 2013 Contact author: gelles at cs ucla edu Available format(s): PDF | BibTeX Citation Version: 20130508:203106 (All versions of this report) Short URL: ia.cr/2013/259 Discussion forum: Show discussion | Start new discussion