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

Private Interactive Communication Across an Adversarial Channel.

Ran Gelles, Amit Sahai, Akshay Wadia

Published Jan 1, 2013• 0 citations
OpenAlex

Abstract

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.

Related papers

Private Interactive Communication Across an Adversarial Channel

Ran Gelles, Amit Sahai, Akshay Wadia

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 errorresilience 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.

IEEE Transactions on Information Theory•Sep 28, 2015•5 citations

Private interactive communication across an adversarial channel

Ran Gelles, Amit Sahai, Akshay Wadia

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.

Conference on Innovations in Theoretical Computer Science•Jan 12, 2014•9 citations

Efficient Interactive Coding Achieving Optimal Error Resilience over the Binary Channel

Meghal Gupta, Rachel Zhang

Given a noiseless protocol π0 computing a function f(x, y) of Alice and Bob’s private inputs x, y, the goal of interactive coding is to construct an error-resilient protocol π computing f such that even if some fraction of the communication is adversarially corrupted, both parties still learn f(x, y). Ideally, the resulting scheme π should be positive rate, computationally efficient, and achieve optimal error resilience.

arXiv:2207.01144•ACM Symposium on Theory of Computing (STOC)•May 16, 2023•2 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

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

Privacy Amplification by Public Discussion

Charles H. Bennett, Gilles Brassard A, J. Robert

In this paper, we investigate how the use of a channel with perfect authenticity but no privacy can be used to repair the defects of a channel with imperfect privacy but no authenticity. More precisely, let us assume that Alice and Bob wish to agree on a secret random bit string, and have at their disposal an imperfect private channel and a perfect public channel. The private channel is imperfect in various ways: transmission errors can occur, and partial information can leak to an eavesdropper, Eve, who also has the power to suppress, inject, and modify transmissions arbitrarily. On the other hand, the public channel transmits information accurately, and these transmissions cannot be modified or suppressed by Eve, but their entire contents becomes known to her. We consider the situation in which a random bit string x has already been transmitted from Alice to Bob over the private channel, and we describe interactive public channel protocols that allow them, with high probability: (1) to assess the extent to which the private channel transmission has been corrupted by tampering and channel noise; and (2) if this corruption is not too severe, to repair Bob’s partial ignorance of the transmitted string and Eve’s partial knowledge of it by distilling from the transmitted and received versions of the string another string, in general shorter than x, upon which Alice and Bob have perfect information, while Eve has nearly no information (or in some cases exactly none), except for its length. These protocols remain secure against unlimited computing power.

SIAM Journal on Computing•Apr 1, 1988•866 citations
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.
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 errorresilience 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.
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.
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.
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.
In this paper, we investigate how the use of a channel with perfect authenticity but no privacy can be used to repair the defects of a channel with imperfect privacy but no authenticity. More precisely, let us assume that Alice and Bob wish to agree on a secret random bit string, and have at their disposal an imperfect private channel and a perfect public channel. The private channel is imperfect in various ways: transmission errors can occur, and partial information can leak to an eavesdropper, Eve, who also has the power to suppress, inject, and modify transmissions arbitrarily. On the other hand, the public channel transmits information accurately, and these transmissions cannot be modified or suppressed by Eve, but their entire contents becomes known to her. We consider the situation in which a random bit string x has already been transmitted from Alice to Bob over the private channel, and we describe interactive public channel protocols that allow them, with high probability: (1) to assess the extent to which the private channel transmission has been corrupted by tampering and channel noise; and (2) if this corruption is not too severe, to repair Bob’s partial ignorance of the transmitted string and Eve’s partial knowledge of it by distilling from the transmitted and received versions of the string another string, in general shorter than x, upon which Alice and Bob have perfect information, while Eve has nearly no information (or in some cases exactly none), except for its length. These protocols remain secure against unlimited computing power.