On the Communication Complexity of Secure Function Evaluation with Long Output
Pavel Hubáček, Daniel Wichs · 2015
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'