Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1601.06562 · IEEE International Symposium on Information Theory (ISIT)

Secure computation of randomized functions

Deepesh Data

Published Jul 1, 2016• 5 citations
arXivHTMLPDF

Abstract

Two user secure computation of randomized functions is considered, where only one user computes the output. Both the users are semi-honest; and computation is such that no user learns any additional information about the other user's input and output other than what cannot be inferred from its own input and output. First we consider a scenario, where privacy conditions are against both the users. In perfect security setting, Kilian gave a characterization of securely computable randomized functions in [1], and we provide rate-optimal protocols for such functions. We prove that the same characterization holds in asymptotic security setting as well and give a rate-optimal protocol. In another scenario, where privacy condition is only against the user who is not computing the function, we provide rate-optimal protocols. For perfect security in both the scenarios, our results are in terms of chromatic entropies of different graphs. In asymptotic security setting, we get single-letter expressions of rates in both the scenarios.

DOI
10.1109/isit.2016.7541860

Related papers

Secure computation of randomized functions: Further results

Deepesh Data, Vinod M. Prabhakaran

We consider secure computation of randomized functions by two users, where both the users (Alice and Bob) have inputs, Alice sends a message to Bob over a rate-limited, noise-free link, and then Bob produces the output. We study this problem when privacy is required only against Bob, i.e., from the message, Bob must not learn any information about Alice's input other than what can be inferred by his own input and output. We give a single-letter expression for the optimal rate. We also explicitly characterize securely computable randomized functions when input has full support, which leads to a much simpler expression for the optimal rate. Recently, Data (ISIT 2016) studied the other two cases (first, when privacy is required against both the users; and second, when privacy is required only against Alice) and obtained single-letter expressions for optimal rates in both the scenarios. Yassaee, Gohari, and Aref (IEEE Transactions on Information Theory 2015) studied the case when there is no privacy requirement and obtained a single-letter expression for the optimal rate, when Alice and Bob interact for arbitrary but finite number of rounds, and both of them may produce potentially different outputs.

arXiv:1705.07081•IEEE Information Theory Workshop (ITW)•Nov 1, 2017•2 citations

Interactive Secure Function Computation

Deepesh Data, Gowtham R. Kurri, Jithin Ravi +1 more

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.

arXiv:1812.03838•IEEE Transactions on Information Theory•Mar 13, 2020•9 citations

Secure Computation to Hide Functions of Inputs

Gowtham R. Kurri, Vinod M. Prabhakaran

We consider a two-user secure computation problem in which Alice and Bob communicate interactively in order to compute some deterministic functions of the inputs. The privacy requirement is that each user should not learn any additional information about a function of the inputs other than what can be inferred from its own input and output. For the distribution-free setting, i.e., when the protocol must be correct and private for any joint input distribution, we completely characterize the set of all securely computable functions. When privacy is required only against Bob who computes a function based on a single transmission from Alice, we show that asymptotically secure computability is equivalent to perfectly secure computability. Separately, we consider an eavesdropper who has access to all the communication and should not learn any information about some function of the inputs (possibly different from the functions to be computed by the users) and show that interaction may be necessary for secure computation.

arXiv:2005.05111•IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2020•4 citations

The Role of Interaction and Common Randomness in Two-User Secure Computation

Gowtham R. Kurri, Vinod M. Prabhakaran, Jithin Ravi

We consider interactive computation of randomized functions between two users with the following privacy requirement: the interactive communication 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.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2018•0 citations

An elementary completeness proof for secure two-party computation primitives

Ye Wang, Prakash Ishwar, Shantanu D. Rane

In the secure two-party computation problem, two parties wish to compute a (possibly randomized) function of their inputs via an interactive protocol, while ensuring that neither party learns more than what can be inferred from only their own input and output. For semi-honest parties and information-theoretic security guarantees, it is well-known that, if only noise-less communication is available, only a limited set of functions can be securely computed; however, if interaction is also allowed over general communication primitives (multi-input/output channels), there are “complete” primitives that enable any function to be securely computed. The general set of complete primitives was characterized recently by Maji, Prabhakaran, and Rosulek leveraging an earlier specialized characterization by Kilian. Our contribution in this paper is a simple, self-contained, alternative derivation using elementary information-theoretic tools.

arXiv:1402.4360•IEEE Information Theory Workshop (ITW)•Nov 1, 2014•0 citations

On coding for secure computing

Deepesh Data, Vinod M. Prabhakaran

In information theoretically secure multiparty computation, several mutually distrusting users want to jointly compute a function of their private data such that users do not learn any additional information about other users' data other than what they can infer from their own data and the function value they compute. In this work we consider asymptotically secure computation - where vanishing probability of error and vanishing information leakage are allowed as block lengths become large - in a three user setting, where two users have inputs and third user securely computes the output of a function on these two inputs. We provide generic lower bounds on the amount of communication required among users and the total amount of private randomness needed to compute any function in this three-user model. We also consider some examples where our bounds are tight. Our lower bounds are derived for the honest-but-curious security model and hence also apply for the malicious model.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2015•3 citations
Two user secure computation of randomized functions is considered, where only one user computes the output. Both the users are semi-honest; and computation is such that no user learns any additional information about the other user's input and output other than what cannot be inferred from its own input and output. First we consider a scenario, where privacy conditions are against both the users. In perfect security setting, Kilian gave a characterization of securely computable randomized functions in [1], and we provide rate-optimal protocols for such functions. We prove that the same characterization holds in asymptotic security setting as well and give a rate-optimal protocol. In another scenario, where privacy condition is only against the user who is not computing the function, we provide rate-optimal protocols. For perfect security in both the scenarios, our results are in terms of chromatic entropies of different graphs. In asymptotic security setting, we get single-letter expressions of rates in both the scenarios.
We consider secure computation of randomized functions by two users, where both the users (Alice and Bob) have inputs, Alice sends a message to Bob over a rate-limited, noise-free link, and then Bob produces the output. We study this problem when privacy is required only against Bob, i.e., from the message, Bob must not learn any information about Alice's input other than what can be inferred by his own input and output. We give a single-letter expression for the optimal rate. We also explicitly characterize securely computable randomized functions when input has full support, which leads to a much simpler expression for the optimal rate. Recently, Data (ISIT 2016) studied the other two cases (first, when privacy is required against both the users; and second, when privacy is required only against Alice) and obtained single-letter expressions for optimal rates in both the scenarios. Yassaee, Gohari, and Aref (IEEE Transactions on Information Theory 2015) studied the case when there is no privacy requirement and obtained a single-letter expression for the optimal rate, when Alice and Bob interact for arbitrary but finite number of rounds, and both of them may produce potentially different outputs.
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.
We consider a two-user secure computation problem in which Alice and Bob communicate interactively in order to compute some deterministic functions of the inputs. The privacy requirement is that each user should not learn any additional information about a function of the inputs other than what can be inferred from its own input and output. For the distribution-free setting, i.e., when the protocol must be correct and private for any joint input distribution, we completely characterize the set of all securely computable functions. When privacy is required only against Bob who computes a function based on a single transmission from Alice, we show that asymptotically secure computability is equivalent to perfectly secure computability. Separately, we consider an eavesdropper who has access to all the communication and should not learn any information about some function of the inputs (possibly different from the functions to be computed by the users) and show that interaction may be necessary for secure computation.
We consider interactive computation of randomized functions between two users with the following privacy requirement: the interactive communication 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.
In the secure two-party computation problem, two parties wish to compute a (possibly randomized) function of their inputs via an interactive protocol, while ensuring that neither party learns more than what can be inferred from only their own input and output. For semi-honest parties and information-theoretic security guarantees, it is well-known that, if only noise-less communication is available, only a limited set of functions can be securely computed; however, if interaction is also allowed over general communication primitives (multi-input/output channels), there are “complete” primitives that enable any function to be securely computed. The general set of complete primitives was characterized recently by Maji, Prabhakaran, and Rosulek leveraging an earlier specialized characterization by Kilian. Our contribution in this paper is a simple, self-contained, alternative derivation using elementary information-theoretic tools.
In information theoretically secure multiparty computation, several mutually distrusting users want to jointly compute a function of their private data such that users do not learn any additional information about other users' data other than what they can infer from their own data and the function value they compute. In this work we consider asymptotically secure computation - where vanishing probability of error and vanishing information leakage are allowed as block lengths become large - in a three user setting, where two users have inputs and third user securely computes the output of a function on these two inputs. We provide generic lower bounds on the amount of communication required among users and the total amount of private randomness needed to compute any function in this three-user model. We also consider some examples where our bounds are tight. Our lower bounds are derived for the honest-but-curious security model and hence also apply for the malicious model.