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

IEEE Transactions on Information Theory

Privacy, additional information and communication

Reuven Bar-Yehuda, Benny Chor, Eyal Kushilevitz Z, Alon Orlitsky

Published Jan 1, 1993• 56 citations
Publisher

Abstract

Two parties, each holding one input of a two-variable function, communicate in order to determine the value of the function. Each party wants to expose as little of its input as possible to the other party. The authors prove tight bounds on the minimum amount of information about the individual inputs that must be revealed in the computation of most functions and of some specific ones. They also show that a computation that reveals little information about the individual inputs may require many more message exchanges than a more revealing computation.>

DOI
10.1109/18.265501

Related papers

Revealing Additional Information in Two-Party Computations ⋆

Andreas Jakoby

Abstract. A two-argument function is computed privately by two parties if after the computation, no party should know anything about the other inputs except for what he is able to deduce from his own input and the function value. In [1] Bar-Yehuda, Chor, Kushilevitz, and Orlitsky give a complete characterisation of two-argument functions which can be computed privately (in the information-theoretical sense) in the Honest-But-Curious model and study protocols for “non-private ” functions revealing as little information about the inputs as possible. The authors define a measure which determines for any function f the additional information E(f) required for computing f and claim that f is privately-computable if and only if E(f) = 0. In our paper we show that the characterisation is false: we give a privately-computable function f with E(f) = 0 and another function g with E(g) =0thatisnot privately-computable. Moreover, we show some rather unexpected and strange properties of the measure for additional information given by Bar-Yehuda et al. and we introduce an alternative measure. We show that for this new measure the minimal leakage of information of randomized and deterministic protocols are equal. Finally, we present some general relations between the information gain of an optimal protocol and the communication complexity of a function. 1

•Jan 29, 2014•0 citations

Privacy and Communication Complexity

Eyal Kushelvitz

Each of two parties $P_\mathcal{X} $ and $P_\matcal{Y} $ holds an n-bit input, x and y, respectively. They wish to privately compute the value of $f( x,y )$. That is, $P_\mathcal{X} $ should not learn any additional information about y (in the information-theoretic sense) other than what follows from its input x and the function value $f ( x,y )$, and similarly, $P_\mathcal{Y} $ should not learn any additional information about x. In this paper, the two following basic questions in the theory of private computations are considered: 1. Which functions can be privately computed? 2. What is the communication complexity of protocols that privately compute a function f (in the case that such protocols exist)? A complete combinatorial characterization of privately computable functions is given. This characterization is used to derive tight bounds on the rounds complexity of any privately computable function and to design optimal private protocols that compute these functions. It is shown that for every $1 \leq g ( n ) \leq 2\cdot ( 2^n - 1)$ there are functions that can be privately computed with $g( n )$-rounds of communication, but not with $( g ( n ) - 1 )$-rounds of communication. This implies that the communication costs of private protocols can be exponentially higher than the communication costs of nonprivate protocols. Interestingly, randomization helps neither to increase the set of privately computable functions, nor to improve the rounds complexity of these functions.

SIAM Journal on Discrete Mathematics•May 1, 1992•118 citations

Privacy and communication complexity

Eyal Kushilevitz Z

Each of two parties P/sub 1/ and P/sub 2/ holds an n-bit input, x and y, respectively. They wish to compute privately the value of f(x,y). Two questions are considered: (1) Which functions can be privately computed? (2) What is the communication complexity of protocols that privately compute a function f (in the case in which such protocols exist)? A complete combinatorial characterization of privately computable functions is given. This characterization is used to derive tight bounds on the rounds complexity of any privately computable function and to design optimal private protocols that compute these functions. It is shown that for every 1>

Annual Symposium on Foundations of Computer Science•Jan 1, 1989•160 citations

Lower bounds and optimal protocols for three-party secure computation

Sundara Rajan S, Shijin Rajakrishnan, Andrew Thangaraj +1 more

The problem of three-party secure computation, where a function of private data of two parties is to be computed by a third party without revealing information beyond respective inputs or outputs is considered. New and better lower bounds on the amount of communication required between the parties to guarantee zero probability of error in the computation and achieve information-theoretic security are derived. Protocols are presented and proved to be optimal in some cases by showing that they achieve the improved lower bounds.

IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2016•1 citation

There Is Always an Exception: Controlling Partial Information Leakage in Secure Computation.

Máté Horváth, Levente Buttyán, Gábor Székely +1 more

Private Function Evaluation (PFE) enables two parties to jointly execute a computation such that one of them provides the input while the other chooses the function to compute. According to the traditional security requirements, a PFE protocol should leak no more information, neither about the function nor the input, than what is revealed by the output of the computation. Existing PFE protocols inherently restrict the scope of computable functions to a certain function class with given output size, thus ruling out the direct evaluation of such problematic functions as the identity map, which would entirely undermine the input privacy requirement. We observe that when not only the input x is confidential but certain partial information g(x) of it as well, standard PFE fails to provide meaningful input privacy if g and the function f to be computed fall into the same function class.

•Jan 1, 2019•0 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
Two parties, each holding one input of a two-variable function, communicate in order to determine the value of the function. Each party wants to expose as little of its input as possible to the other party. The authors prove tight bounds on the minimum amount of information about the individual inputs that must be revealed in the computation of most functions and of some specific ones. They also show that a computation that reveals little information about the individual inputs may require many more message exchanges than a more revealing computation.>
Abstract. A two-argument function is computed privately by two parties if after the computation, no party should know anything about the other inputs except for what he is able to deduce from his own input and the function value. In [1] Bar-Yehuda, Chor, Kushilevitz, and Orlitsky give a complete characterisation of two-argument functions which can be computed privately (in the information-theoretical sense) in the Honest-But-Curious model and study protocols for “non-private ” functions revealing as little information about the inputs as possible. The authors define a measure which determines for any function f the additional information E(f) required for computing f and claim that f is privately-computable if and only if E(f) = 0. In our paper we show that the characterisation is false: we give a privately-computable function f with E(f) = 0 and another function g with E(g) =0thatisnot privately-computable. Moreover, we show some rather unexpected and strange properties of the measure for additional information given by Bar-Yehuda et al. and we introduce an alternative measure. We show that for this new measure the minimal leakage of information of randomized and deterministic protocols are equal. Finally, we present some general relations between the information gain of an optimal protocol and the communication complexity of a function. 1
Each of two parties $P_\mathcal{X} $ and $P_\matcal{Y} $ holds an n-bit input, x and y, respectively. They wish to privately compute the value of f(x,y)f( x,y )f(x,y). That is, $P_\mathcal{X} $ should not learn any additional information about y (in the information-theoretic sense) other than what follows from its input x and the function value f(x,y)f ( x,y )f(x,y), and similarly, $P_\mathcal{Y} $ should not learn any additional information about x. In this paper, the two following basic questions in the theory of private computations are considered: 1. Which functions can be privately computed? 2. What is the communication complexity of protocols that privately compute a function f (in the case that such protocols exist)? A complete combinatorial characterization of privately computable functions is given. This characterization is used to derive tight bounds on the rounds complexity of any privately computable function and to design optimal private protocols that compute these functions. It is shown that for every 1≤g(n)≤2⋅(2n−1)1 \leq g ( n ) \leq 2\cdot ( 2^n - 1)1≤g(n)≤2⋅(2n−1) there are functions that can be privately computed with g(n)g( n )g(n)-rounds of communication, but not with (g(n)−1)( g ( n ) - 1 )(g(n)−1)-rounds of communication. This implies that the communication costs of private protocols can be exponentially higher than the communication costs of nonprivate protocols. Interestingly, randomization helps neither to increase the set of privately computable functions, nor to improve the rounds complexity of these functions.
Each of two parties P/sub 1/ and P/sub 2/ holds an n-bit input, x and y, respectively. They wish to compute privately the value of f(x,y). Two questions are considered: (1) Which functions can be privately computed? (2) What is the communication complexity of protocols that privately compute a function f (in the case in which such protocols exist)? A complete combinatorial characterization of privately computable functions is given. This characterization is used to derive tight bounds on the rounds complexity of any privately computable function and to design optimal private protocols that compute these functions. It is shown that for every 1>
The problem of three-party secure computation, where a function of private data of two parties is to be computed by a third party without revealing information beyond respective inputs or outputs is considered. New and better lower bounds on the amount of communication required between the parties to guarantee zero probability of error in the computation and achieve information-theoretic security are derived. Protocols are presented and proved to be optimal in some cases by showing that they achieve the improved lower bounds.
Private Function Evaluation (PFE) enables two parties to jointly execute a computation such that one of them provides the input while the other chooses the function to compute. According to the traditional security requirements, a PFE protocol should leak no more information, neither about the function nor the input, than what is revealed by the output of the computation. Existing PFE protocols inherently restrict the scope of computable functions to a certain function class with given output size, thus ruling out the direct evaluation of such problematic functions as the identity map, which would entirely undermine the input privacy requirement. We observe that when not only the input x is confidential but certain partial information g(x) of it as well, standard PFE fails to provide meaningful input privacy if g and the function f to be computed fall into the same function class.
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.