IACR News item: 28 August 2014
Pavel Hubacek, Daniel Wichs
ePrint ReportSurprisingly, 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.
Additional news items may be found on the IACR news page.