## Cryptology ePrint Archive: Report 2010/528

**Constant-Round Private Function Evaluation with Linear Complexity**

*Jonathan Katz and Lior Malka*

**Abstract: **We consider the problem of private function evaluation (PFE) in the
two-party setting. Here, informally, one party holds an input $x$
while the other holds a circuit describing a function $f$; the goal
is for one (or both) of the parties to learn $f(x)$ while revealing
nothing more to either party. In contrast to the usual setting of
secure computation --- where the function being computed is known to
both parties --- PFE is useful in settings where the function (i.e.,
algorithm) itself must remain secret, e.g., because it is proprietary
or classified.

It is known that PFE can be reduced to standard secure computation by
having the parties evaluate a universal circuit}, and this is the
approach taken in most prior work. Using a universal circuit,
however, introduces additional overhead and results in a more complex
implementation. We show here a completely new technique for PFE that
avoids universal circuits, and results in constant-round protocols
with communication/computational complexity linear in the size of the
circuit computing $f$. This gives the first constant-round protocol
for PFE with linear complexity (without using fully homomorphic
encryption), even restricted to semi-honest adversaries.

**Category / Keywords: **cryptographic protocols / secure computation

**Publication Info: **This is the full version of the paper to appear at Asiacrypt 2011

**Date: **received 15 Oct 2010, last revised 6 Sep 2011

**Contact author: **jkatz at cs umd edu

**Available format(s): **PDF | BibTeX Citation

**Note: **(none)

**Version: **20110906:205640 (All versions of this report)

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]