Paper 2017/692

Towards Characterizing Securely Computable Two-Party Randomized Functions

Deepesh Data and Manoj Prabhakaran

Abstract

A basic question of cryptographic complexity is to combinatorially characterize all randomized functions which have information-theoretic semi-honest secure 2-party computation protocols. The corresponding question for deterministic functions was answered almost three decades back, by Kushilevitz (FOCS 1989). In this work, we make progress towards understanding securely computable `randomized' functions. We bring tools developed in the study of completeness to bear on this problem. In particular, our characterizations are obtained by considering only symmetric functions with a combinatorial property called `simplicity' (Maji et al. Indocrypt 2012). Our main result is a complete combinatorial characterization of randomized functions with `ternary output' kernels, that have information-theoretic semi-honest secure 2-party computation protocols. In particular, we show that there exist simple randomized functions with ternary output that do not have secure computation protocols. (For deterministic functions, the smallest output alphabet size of such a function is 5, due to an example given by Beaver, DIMACS Workshop on Distributed Computing and Cryptography 1989.) Also, we give a complete combinatorial characterization of randomized functions that have `2-round' information-theoretic semi-honest secure 2-party computation protocols. We also give a counter-example to a natural conjecture for the full characterization, namely, that all securely computable simple functions have secure protocols with a unique transcript for each output value. This conjecture is in fact true for deterministic functions, and -- as our results above show -- for ternary functions and for functions with 2-round secure protocols.