Interactive secure function computation

We consider interactive computation of randomized functions between two users with the following privacy requirement: the interaction should not reveal to either user any extra information about the other user's input and output other than what can be inferred from the user's own input and output. We also consider the case where privacy is required against only one of the users. For both cases, we give single-letter expressions for feasibility and optimal rates of communication. Then we discuss the role of common randomness and interaction in both privacy settings. We also study perfectly secure non-interactive computation when only one of the users computes a randomized function based on a single transmission from the other user. We characterize randomized functions which can be perfectly securely computed in this model and obtain tight bounds on the optimal message lengths in all the privacy settings.This work was supported by the Department of Atomic Energy, Government of India, under Project 12-R&D-TFR-5.01-0500. The work of Deepesh Data was supported by a Microsoft Research India Ph.D. Fellowship. The work of Gowtham R. Kurri was supported in part by a Travel Fellowship from the Sarojini Damodaran Foundation and in part by the Department of Science and Technology, Government of India, under an Indo-Israel Grant DST/INT/ISR/P-16/2017. The work of Jithin Ravi was supported by the European Research Council (ERC) through the European Union's Horizon 2020 Research and Innovation Programme under Grant 714161. The work of Vinod M. Prabhakaran was supported in part by a Ramanujan Fellowship from the Department of Science and Technology, Government of India, in part by the Information Technology Research Academy (ITRA), Government of India, under ITRA Mobile Grant ITRA/15(64)/Mobile/USEAADWN/01, and in part by the Department of Science and Technology, Government of India, under an Indo-Israel Grant DST/INT/ISR/P-16/2017