On the Communication Complexity of Secure Function Evaluation with Long Output

Abstract: We study the communication complexity of secure function evaluation (SFE). Consider a setting where Alice has a short input a, Bob has an input b and we want Bob to learn some function y = f(a, 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 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 \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 fully malicious setting, or even already in an 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.

joint work with Pavel Hubacek