### 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.

Available format(s)
Category
Foundations
Publication info
Preprint.
Keywords
Secure computationrandomized functionscharacterization
Contact author(s)
deepesh data @ gmail com
History
Short URL
https://ia.cr/2017/692

CC BY

BibTeX

@misc{cryptoeprint:2017/692,
author = {Deepesh Data and Manoj Prabhakaran},
title = {Towards Characterizing Securely Computable Two-Party Randomized Functions},
howpublished = {Cryptology ePrint Archive, Paper 2017/692},
year = {2017},
note = {\url{https://eprint.iacr.org/2017/692}},
url = {https://eprint.iacr.org/2017/692}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.