You are looking at a specific version 20110906:205640 of this paper. See the latest version.

Paper 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.

Note: (none)

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. This is the full version of the paper to appear at Asiacrypt 2011
Keywords
secure computation
Contact author(s)
jkatz @ cs umd edu
History
2011-09-06: last of 3 revisions
2010-10-19: received
See all versions
Short URL
https://ia.cr/2010/528
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.