Cryptology ePrint Archive: Report 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.

Category / Keywords: foundations / Secure computation; randomized functions; characterization

Date: received 10 Jul 2017, last revised 19 Jul 2017

Contact author: deepesh data at gmail com

Available format(s): PDF | BibTeX Citation

Short URL: ia.cr/2017/692

[ Cryptology ePrint archive ]