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

SIAM Journal on Discrete Mathematics

Privacy and Communication Complexity

Eyal Kushelvitz

Published May 1, 1992• 118 citations
Publisher

Abstract

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.

DOI
10.1137/0405021

Related papers

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

Communication Complexity of Private Simultaneous Quantum Messages Protocols

Akinori Kawachi, Harumichi Nishimura

The private simultaneous messages model is a non-interactive version of the multiparty secure computation, which has been intensively studied to examine the communication cost of the secure computation. We consider its quantum counterpart, the private simultaneous quantum messages (PSQM) model, and examine the advantages of quantum communication and prior entanglement of this model. In the PSQM model, $k$ parties $P_1,\ldots,P_k$ initially share a common random string (or entangled states in a stronger setting), and they have private classical inputs $x_1,\ldots, x_k$. Every $P_i$ generates a quantum message from the private input $x_i$ and the shared random string (entangled states), and then sends it to the referee $R$. Receiving the messages, $R$ computes $F(x_1,\ldots,x_k)$. Then, $R$ learns nothing except for $F(x_1,\ldots,x_k)$ as the privacy condition. We obtain the following results for this PSQM model. (1) We demonstrate that the privacy condition inevitably increases the communication cost in the two-party PSQM model as well as in the classical case presented by Applebaum, Holenstein, Mishra, and Shayevitz. In particular, we prove a lower bound $(3-o(1))n$ of the communication complexity in two-party PSQM protocols with a shared random string for random Boolean functions of $2n$-bit input, which is larger than the trivial upper bound $2n$ of the communication complexity without the privacy condition. (2) We demonstrate a factor two gap between the communication complexity of PSQM protocols with shared entangled states and with shared random strings by designing a multiparty PSQM protocol with shared entangled states for a total function that extends the two-party equality function. (3) We demonstrate an exponential gap between the communication complexity of PSQM protocols with shared entangled states and with shared random strings for a two-party partial function.

arXiv:2105.07120•Leibniz international proceedings in informatics•Jan 1, 2021•7 citations

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

Multi-Party Protocols, Information Complexity and Privacy

Iordanis Kerenidis, Adi Rosén, Florent Urrutia

We introduce a new information-theoretic measure, which we call Public Information Complexity (PIC), as a tool for the study of multi-party computation protocols, and of quantities such as their communication complexity, or the amount of randomness they require in the context of information-theoretic private computations. We are able to use this measure directly in the natural asynchronous message-passing peer-to-peer model and show a number of interesting properties and applications of our new notion: The Public Information Complexity is a lower bound on the Communication Complexity and an upper bound on the Information Complexity; the difference between the Public Information Complexity and the Information Complexity provides a lower bound on the amount of randomness used in a protocol; any communication protocol can be compressed to its Public Information Cost; and an explicit calculation of the zero-error Public Information Complexity of the k -party, n -bit Parity function, where a player outputs the bitwise parity of the inputs. The latter result also establishes that the amount of randomness needed by a private protocol that computes this function is Ω ( n ).

arXiv:1606.06872•ACM Transactions on Computation Theory•Mar 17, 2019•2 citations

Private Interactive Communication Across an Adversarial Channel.

Ran Gelles, Amit Sahai, Akshay Wadia

Abstract. Consider two parties Alice and Bob, who hold private inputs x and y, and wish to compute a function f(x, y) privately in the information theoretic sense; that is, each party should learn nothing beyond f(x, y). However, the communication channel available to them is noisy. This means that the channel can introduce errors in the transmission between the two parties. Moreover, the channel is adversarial in the sense that it knows the protocol that Alice and Bob are running, and maliciously introduces errors to disrupt the communication, subject to some bound on the total number of errors. A fundamental question in this setting is to design a protocol that remains private in the presence of large number of errors. If Alice and Bob are only interested in computing f(x, y) correctly, and not privately, then quite robust protocols are known that can tolerate a constant fraction of errors. However, none of these solutions is applicable in the setting of privacy, as they inherently leak information about the parties ’ inputs. This leads to the question whether we can simultaneously achieve privacy and error-resilience against a constant fraction of errors. We show that privacy and error-resilience are contradictory goals. In particular, we show that for every constant c> 0, there exists a function f which is privately computable in the error-less setting, but for which no private and correct protocol is resilient against a c-fraction of errors.

•Jan 1, 2013•0 citations

Communication and Randomness Lower Bounds for Secure Computation

Deepesh Data, Vinod M. Prabhakaran, Manoj Prabhakaran

In secure multiparty computation (MPC), mutually distrusting users collaborate to compute a function of their private data without revealing any additional information about their data to the other users. While it is known that information theoretically secure MPC is possible among n users having access to private randomness and are pairwise connected by secure, noiseless, and bidirectional links against the collusion of less than n/2 users (in the honest-but-curious model; the threshold is n/3 in the malicious model), relatively little is known about the communication and randomness complexity of secure computation, i.e., the amount of communication and randomness required to compute securely. In this paper, we employ information theoretic techniques to obtain lower bounds on communication and randomness complexity of secure MPC. We restrict ourselves to a concrete interactive setting involving three users under which all functions are securely computable against corruption of individual users in the honest-but-curious model. We derive lower bounds for both the perfect security case (i.e., zero-error and no leakage of information) and asymptotic security (where the probability of error and information leakage vanish as block-length goes to ∞). Our techniques include the use of a data processing inequality for residual information (i.e., the gap between mutual information and Gács-Körner common information), a new information inequality for three-user protocols, and the idea of distribution switching by which lower bounds computed under certain worst case scenarios can be shown to apply for the general case. Our lower bounds are shown to be tight for various functions of interest. In particular, we show concrete functions which have communication-ideal protocols, i.e., which achieve the minimum communication simultaneously on all links in the network. Also, we obtain the first explicit example of a function that incurs a higher communication cost than the input length, in the secure computation model of Feige et al. (26th Annual ACM Symposium on Theory of Computing, 1994), who had shown that such functions exist. We also show that our communication bounds imply tight lower bounds on the amount of randomness required by MPC protocols for many interesting functions.

arXiv:1512.07735•IEEE Transactions on Information Theory•May 13, 2016•32 citations
Each of two parties PXP_\mathcal{X} PX​ and P\matcalYP_\matcal{Y} 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, PXP_\mathcal{X} PX​ 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, PYP_\mathcal{Y} PY​ 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 private simultaneous messages model is a non-interactive version of the multiparty secure computation, which has been intensively studied to examine the communication cost of the secure computation. We consider its quantum counterpart, the private simultaneous quantum messages (PSQM) model, and examine the advantages of quantum communication and prior entanglement of this model. In the PSQM model, kkk parties P1,…,PkP_1,\ldots,P_kP1​,…,Pk​ initially share a common random string (or entangled states in a stronger setting), and they have private classical inputs x1,…,xkx_1,\ldots, x_kx1​,…,xk​. Every PiP_iPi​ generates a quantum message from the private input xix_ixi​ and the shared random string (entangled states), and then sends it to the referee RRR. Receiving the messages, RRR computes F(x1,…,xk)F(x_1,\ldots,x_k)F(x1​,…,xk​). Then, RRR learns nothing except for F(x1,…,xk)F(x_1,\ldots,x_k)F(x1​,…,xk​) as the privacy condition. We obtain the following results for this PSQM model. (1) We demonstrate that the privacy condition inevitably increases the communication cost in the two-party PSQM model as well as in the classical case presented by Applebaum, Holenstein, Mishra, and Shayevitz. In particular, we prove a lower bound (3−o(1))n(3-o(1))n(3−o(1))n of the communication complexity in two-party PSQM protocols with a shared random string for random Boolean functions of 2n2n2n-bit input, which is larger than the trivial upper bound 2n2n2n of the communication complexity without the privacy condition. (2) We demonstrate a factor two gap between the communication complexity of PSQM protocols with shared entangled states and with shared random strings by designing a multiparty PSQM protocol with shared entangled states for a total function that extends the two-party equality function. (3) We demonstrate an exponential gap between the communication complexity of PSQM protocols with shared entangled states and with shared random strings for a two-party partial function.
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
We introduce a new information-theoretic measure, which we call Public Information Complexity (PIC), as a tool for the study of multi-party computation protocols, and of quantities such as their communication complexity, or the amount of randomness they require in the context of information-theoretic private computations. We are able to use this measure directly in the natural asynchronous message-passing peer-to-peer model and show a number of interesting properties and applications of our new notion: The Public Information Complexity is a lower bound on the Communication Complexity and an upper bound on the Information Complexity; the difference between the Public Information Complexity and the Information Complexity provides a lower bound on the amount of randomness used in a protocol; any communication protocol can be compressed to its Public Information Cost; and an explicit calculation of the zero-error Public Information Complexity of the k -party, n -bit Parity function, where a player outputs the bitwise parity of the inputs. The latter result also establishes that the amount of randomness needed by a private protocol that computes this function is Ω ( n ).
Abstract. Consider two parties Alice and Bob, who hold private inputs x and y, and wish to compute a function f(x, y) privately in the information theoretic sense; that is, each party should learn nothing beyond f(x, y). However, the communication channel available to them is noisy. This means that the channel can introduce errors in the transmission between the two parties. Moreover, the channel is adversarial in the sense that it knows the protocol that Alice and Bob are running, and maliciously introduces errors to disrupt the communication, subject to some bound on the total number of errors. A fundamental question in this setting is to design a protocol that remains private in the presence of large number of errors. If Alice and Bob are only interested in computing f(x, y) correctly, and not privately, then quite robust protocols are known that can tolerate a constant fraction of errors. However, none of these solutions is applicable in the setting of privacy, as they inherently leak information about the parties ’ inputs. This leads to the question whether we can simultaneously achieve privacy and error-resilience against a constant fraction of errors. We show that privacy and error-resilience are contradictory goals. In particular, we show that for every constant c> 0, there exists a function f which is privately computable in the error-less setting, but for which no private and correct protocol is resilient against a c-fraction of errors.
In secure multiparty computation (MPC), mutually distrusting users collaborate to compute a function of their private data without revealing any additional information about their data to the other users. While it is known that information theoretically secure MPC is possible among n users having access to private randomness and are pairwise connected by secure, noiseless, and bidirectional links against the collusion of less than n/2 users (in the honest-but-curious model; the threshold is n/3 in the malicious model), relatively little is known about the communication and randomness complexity of secure computation, i.e., the amount of communication and randomness required to compute securely. In this paper, we employ information theoretic techniques to obtain lower bounds on communication and randomness complexity of secure MPC. We restrict ourselves to a concrete interactive setting involving three users under which all functions are securely computable against corruption of individual users in the honest-but-curious model. We derive lower bounds for both the perfect security case (i.e., zero-error and no leakage of information) and asymptotic security (where the probability of error and information leakage vanish as block-length goes to ∞). Our techniques include the use of a data processing inequality for residual information (i.e., the gap between mutual information and Gács-Körner common information), a new information inequality for three-user protocols, and the idea of distribution switching by which lower bounds computed under certain worst case scenarios can be shown to apply for the general case. Our lower bounds are shown to be tight for various functions of interest. In particular, we show concrete functions which have communication-ideal protocols, i.e., which achieve the minimum communication simultaneously on all links in the network. Also, we obtain the first explicit example of a function that incurs a higher communication cost than the input length, in the secure computation model of Feige et al. (26th Annual ACM Symposium on Theory of Computing, 1994), who had shown that such functions exist. We also show that our communication bounds imply tight lower bounds on the amount of randomness required by MPC protocols for many interesting functions.