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:1605.04486 · International Conference on Distributed Computing and Networking (ICDCN)

Sending a Message with Unknown Noise

Abhinav Aggarwal, Varsha Dani, Thomas P. Hayes, Jared Saia

Published Jan 4, 2018• 5 citations
arXivHTMLPDF

Abstract

Alice and Bob are connected via a two-way channel, and Alice wants to send a message of L bits to Bob. An adversary flips an arbitrary but finite number of bits, T, on the channel. This adversary knows our algorithm and Alice's message, but does not know any private random bits generated by Alice or Bob, nor the bits sent over the channel, except when these bits can be predicted by knowledge of Alice's message or our algorithm. We want Bob to receive Alice's message and for both players to terminate, with error probability at most δ > 0, where δ is a parameter known to both Alice and Bob. Unfortunately, the value T is unknown in advance to either Alice or Bob, and the value L is unknown in advance to Bob.

DOI
10.1145/3154273.3154318

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.

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

Secure one-way interactive communication.

Abhinav Aggarwal, Varsha Dani, Thomas P. Hayes +1 more

Alice and Bob are connected via a two-way binary channel. This paper describes an algorithm to enable Alice to send a message to Bob when 1) an oblivious adversary flips an unknown number of bits, $T$, on the channel; and 2) the message length $L$, and a desired error probability, $\epsilon$ are public knowledge. With probability at least $1-\epsilon$, our algorithm ensures that Bob receives the correct message, and that Alice and Bob terminate after sending a total of $L + O \left( T + \min \left(T+1,\frac{L}{\log L} \right) \log \left( \frac{L}{\epsilon} \right) \right)$ bits. When $\epsilon = \Omega\left( \frac{1}{poly(L)} \right)$ and $T$ is large, the number of bits sent is $L + O\left( T \right)$, which is asymptotically optimal, assuming a conjecture by Haeupler.

•May 15, 2016•5 citations

Multipath Multicarrier Misinformation to Adversaries

Zhecun Liu

Wireless channels are vulnerable to eavesdroppers due to their broadcast nature. One approach to thwart an eavesdropper (Eve) is to decrease her SNR, e.g., by reducing the signal in her direction. Unfortunately, such methods are vulnerable to (1) a highly directional Eve that can increase her received signal strength and (2) Eve that is close to the receiver, Bob, or close to the transmitter, Alice. In this paper, we design and experimentally evaluate Multipath Multicarrier Misinformation to Adversaries (M3A), a system for Alice to send data to Bob while simultaneously sending misinformation to Eve. Our approach does not require knowledge of Eve’s channel or location and, with multipath channels, randomly transforms Eve’s symbols even if Eve is located one wavelength-scale distance from Bob (approximately 10 cm) or if Eve is located between Alice and Bob in their direct path (Eve is approximately 1/3 closer to Alice). In particular, our approach is to move each of Eve’s received symbols (over time and across subcarriers), to an independently random transformation as compared to Bob, without Alice or Bob knowing Eve’s location or channel. We realize this by modulating Alice’s per-subcarrier beamforming weights with an i.i.d. random binary sequence, as if Alice had a separate antenna array for each subcarrier, and could randomly turn antennas in each array on and off. We implement M3A on a real-time Massive MIMO testbed, and show that M3A increases Eve’s bit error rate up to more than two hundredfold compared to beamforming, even if she is positioned approximately a wavelength away, whether above, below, or beside Bob. Finally, to ensure reliability at Bob, we show that with M3A, Bob’s bit error rate is approximately an order of magnitude lower than achieved with prior work.

•Apr 5, 2023•0 citations

Covert communication with noise and channel uncertainties

Hien Quang Ta, Quoc‐Viet Pham, Khuong Ho‐Van +1 more

Wireless Networks•Nov 17, 2021•12 citations

M3A: Multipath Multicarrier Misinformation to Adversaries

Zhecun Liu, Keerthi Priya Dasala, Di Mu +2 more

Wireless channels are vulnerable to eavesdroppers due to their broadcast nature. One approach to thwart an eavesdropper (Eve) is to decrease her SNR, e.g., by reducing the signal in her direction. Unfortunately, such methods are vulnerable to (1) a highly directional Eve that can increase her received signal strength and (2) Eve that is close to the receiver, Bob, or close to the transmitter, Alice. In this paper, we design and experimentally evaluate Multipath Multicarrier Misinformation to Adversaries (M3A), a system for Alice to send data to Bob while simultaneously sending misinformation to Eve. Our approach does not require knowledge of Eve's channel or location and, with multipath channels, randomly transforms Eve's symbols even if Eve is located one wavelength-scale distance from Bob (approximately 10 cm) or if Eve is located between Alice and Bob in their direct path (Eve is approximately 1/3 closer to Alice). In particular, our approach is to move each of Eve's received symbols (over time and across subcarriers), to an independently random transformation as compared to Bob, without Alice or Bob knowing Eve's location or channel. We realize this by modulating Alice's per-subcarrier beamforming weights with an i.i.d. random binary sequence, as if Alice had a separate antenna array for each subcarrier, and could randomly turn antennas in each array on and off. We implement M3A on a real-time Massive MIMO testbed and show that M3A can increase Eve's bit error rate more than two hundredfold compared to beamforming, even if she is positioned approximately a wavelength away, whether above, below, or beside Bob. Finally, to ensure reliability at Bob, we show that with M3A, Bob's bit error rate is approximately an order of magnitude lower than achieved with prior work.

ACM Annual International Conference on Mobile Computing and Networking (MobiCom)•Sep 30, 2023•3 citations

Stealthy Communication over Noisy Channels: Channel Capacity and The Role of Randomization

Abdalla Ibrahim, Johannes Rosenberger, Boulat A. Bash +2 more

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2026•0 citations
Alice and Bob are connected via a two-way channel, and Alice wants to send a message of L bits to Bob. An adversary flips an arbitrary but finite number of bits, T, on the channel. This adversary knows our algorithm and Alice's message, but does not know any private random bits generated by Alice or Bob, nor the bits sent over the channel, except when these bits can be predicted by knowledge of Alice's message or our algorithm. We want Bob to receive Alice's message and for both players to terminate, with error probability at most δ > 0, where δ is a parameter known to both Alice and Bob. Unfortunately, the value T is unknown in advance to either Alice or Bob, and the value L is unknown in advance to Bob.
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.
Alice and Bob are connected via a two-way binary channel. This paper describes an algorithm to enable Alice to send a message to Bob when 1) an oblivious adversary flips an unknown number of bits, TTT, on the channel; and 2) the message length LLL, and a desired error probability, ϵ\epsilonϵ are public knowledge. With probability at least 1−ϵ1-\epsilon1−ϵ, our algorithm ensures that Bob receives the correct message, and that Alice and Bob terminate after sending a total of L+O(T+min⁡(T+1,Llog⁡L)log⁡(Lϵ))L + O \left( T + \min \left(T+1,\frac{L}{\log L} \right) \log \left( \frac{L}{\epsilon} \right) \right)L+O(T+min(T+1,logLL​)log(ϵL​)) bits. When ϵ=Ω(1poly(L))\epsilon = \Omega\left( \frac{1}{poly(L)} \right)ϵ=Ω(poly(L)1​) and TTT is large, the number of bits sent is L+O(T)L + O\left( T \right)L+O(T), which is asymptotically optimal, assuming a conjecture by Haeupler.
Wireless channels are vulnerable to eavesdroppers due to their broadcast nature. One approach to thwart an eavesdropper (Eve) is to decrease her SNR, e.g., by reducing the signal in her direction. Unfortunately, such methods are vulnerable to (1) a highly directional Eve that can increase her received signal strength and (2) Eve that is close to the receiver, Bob, or close to the transmitter, Alice. In this paper, we design and experimentally evaluate Multipath Multicarrier Misinformation to Adversaries (M3A), a system for Alice to send data to Bob while simultaneously sending misinformation to Eve. Our approach does not require knowledge of Eve’s channel or location and, with multipath channels, randomly transforms Eve’s symbols even if Eve is located one wavelength-scale distance from Bob (approximately 10 cm) or if Eve is located between Alice and Bob in their direct path (Eve is approximately 1/3 closer to Alice). In particular, our approach is to move each of Eve’s received symbols (over time and across subcarriers), to an independently random transformation as compared to Bob, without Alice or Bob knowing Eve’s location or channel. We realize this by modulating Alice’s per-subcarrier beamforming weights with an i.i.d. random binary sequence, as if Alice had a separate antenna array for each subcarrier, and could randomly turn antennas in each array on and off. We implement M3A on a real-time Massive MIMO testbed, and show that M3A increases Eve’s bit error rate up to more than two hundredfold compared to beamforming, even if she is positioned approximately a wavelength away, whether above, below, or beside Bob. Finally, to ensure reliability at Bob, we show that with M3A, Bob’s bit error rate is approximately an order of magnitude lower than achieved with prior work.
Wireless channels are vulnerable to eavesdroppers due to their broadcast nature. One approach to thwart an eavesdropper (Eve) is to decrease her SNR, e.g., by reducing the signal in her direction. Unfortunately, such methods are vulnerable to (1) a highly directional Eve that can increase her received signal strength and (2) Eve that is close to the receiver, Bob, or close to the transmitter, Alice. In this paper, we design and experimentally evaluate Multipath Multicarrier Misinformation to Adversaries (M3A), a system for Alice to send data to Bob while simultaneously sending misinformation to Eve. Our approach does not require knowledge of Eve's channel or location and, with multipath channels, randomly transforms Eve's symbols even if Eve is located one wavelength-scale distance from Bob (approximately 10 cm) or if Eve is located between Alice and Bob in their direct path (Eve is approximately 1/3 closer to Alice). In particular, our approach is to move each of Eve's received symbols (over time and across subcarriers), to an independently random transformation as compared to Bob, without Alice or Bob knowing Eve's location or channel. We realize this by modulating Alice's per-subcarrier beamforming weights with an i.i.d. random binary sequence, as if Alice had a separate antenna array for each subcarrier, and could randomly turn antennas in each array on and off. We implement M3A on a real-time Massive MIMO testbed and show that M3A can increase Eve's bit error rate more than two hundredfold compared to beamforming, even if she is positioned approximately a wavelength away, whether above, below, or beside Bob. Finally, to ensure reliability at Bob, we show that with M3A, Bob's bit error rate is approximately an order of magnitude lower than achieved with prior work.