Welcome to the resource topic for 2014/669
Title:
On the Communication Complexity of Secure Function Evaluation with Long Output
Authors: Pavel Hubacek, Daniel Wichs
Abstract:We study the communication complexity of secure function evaluation (SFE). Consider a setting where Alice has a short input x_A, Bob has an input x_B and we want Bob to learn some function y = f(x_A, x_B) with large output size. For example, Alice has a small secret decryption key, Bob has a large encrypted database and we want Bob to learn the decrypted data without learning anything else about Alice’s key. In a trivial insecure protocol, Alice can just send her short input x_A to Bob. However, all known SFE protocols have communication complexity that scales with size of the output y, which can potentially be much larger. Is such output-size dependence'' inherent in SFE? Surprisingly, we show that output-size dependence can be avoided in the \emph{honest-but-curious} setting. In particular, using indistinguishability obfuscation (iO) and fully homomorphic encryption (FHE), we construct the first honest-but-curious SFE protocol whose communication complexity only scales with that of the best insecure protocol for evaluating the desired function, independent of the output size. Our construction relies on a novel way of using iO via a new tool that we call a somewhere statistically binding (SSB) hash’', and which may be of independent interest. On the negative side, we show that output-size dependence is inherent in the \emph{fully malicious} setting, or even already in an \emph{honest-but-deterministic} setting, where the corrupted party follows the protocol as specified but fixes its random tape to some deterministic value. Moreover, we show that even in an offline/online protocol, the communication of the online phase must have output-size dependence. This negative result uses an incompressibility argument and it generalizes several recent lower bounds for functional encryption and (reusable) garbled circuits, which follow as simple corollaries of our general theorem.
ePrint: https://eprint.iacr.org/2014/669
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .