Interactive Secure Function Computation

Abstract

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.

30 pages. Revised based on comments from the reviewers

References in corpus (7)

• Distributed Channel Synthesis
• Secure Multiterminal Source Coding with Side Information at the Eavesdropper
• Common Information and Secret Key Capacity
• Secure Lossless Compression with Side Information
• Robust Privacy-Utility Tradeoffs under Differential Privacy and Hamming Distortion
• On the Public Communication Needed to Achieve SK Capacity in the Multiterminal Source Model
• Communication and Randomness Lower Bounds for Secure Computation

Cited by in corpus (1)

• Randomized Distributed Function Computation (RDFC): Ultra-Efficient Semantic Communication Applications to Privacy