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

Private Interactive Communication Across an Adversarial Channel

Ran Gelles, Amit Sahai, Akshay Wadia

Published Sep 28, 2015• 5 citations
Publisher

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

DOI
10.1109/tit.2015.2483323

Related papers

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

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

Correcting errors without leaking partial information

Yevgeniy Dodis, Adam Smith

This paper explores what kinds of information two parties must communicate in order to correct errors which occur in a shared secret string W. Any bits they communicate must leak a significant amount of information about W --- that is, from the adversary's point of view, the entropy of W will drop significantly. Nevertheless, we construct schemes with which Alice and Bob can prevent an adversary from learning any useful information about W. Specifically, if the entropy of W is sufficiently high, then there is no function f(W) which the adversary can learn from the error-correction information with significant probability.This leads to several new results: (a) the design of noise-tolerant "perfectly one-way" hash functions in the sense of Canetti et al. [7], which in turn leads to obfuscation of proximity queries for high entropy secrets W; (b) private fuzzy extractors [11], which allow one to extract uniformly random bits from noisy and nonuniform data W, while also insuring that no sensitive information about W is leaked; and (c) noise tolerance and stateless key re-use in the Bounded Storage Model, resolving the main open problem of Ding [10].The heart of our constructions is the design of strong randomness extractors with the property that the source W can be recovered from the extracted randomness and any string W' which is close to W.

ACM Symposium on Theory of Computing (STOC)•May 22, 2005•172 citations
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.
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.
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.
This paper explores what kinds of information two parties must communicate in order to correct errors which occur in a shared secret string W. Any bits they communicate must leak a significant amount of information about W --- that is, from the adversary's point of view, the entropy of W will drop significantly. Nevertheless, we construct schemes with which Alice and Bob can prevent an adversary from learning any useful information about W. Specifically, if the entropy of W is sufficiently high, then there is no function f(W) which the adversary can learn from the error-correction information with significant probability.This leads to several new results: (a) the design of noise-tolerant "perfectly one-way" hash functions in the sense of Canetti et al. [7], which in turn leads to obfuscation of proximity queries for high entropy secrets W; (b) private fuzzy extractors [11], which allow one to extract uniformly random bits from noisy and nonuniform data W, while also insuring that no sensitive information about W is leaked; and (c) noise tolerance and stateless key re-use in the Bounded Storage Model, resolving the main open problem of Ding [10].The heart of our constructions is the design of strong randomness extractors with the property that the source W can be recovered from the extracted randomness and any string W' which is close to W.