Distributed Computing with Channel Noise
Abhinav Aggarwal
abhiag@cs.unm.edu

Varsha Dani
varsha@cs.unm.edu

Thomas P. Hayes
hayes@cs.unm.edu

arXiv:1612.05943v2 [cs.CR] 24 Jul 2017

Jared Saia
saia@cs.unm.edu

Abstract
A group of n users want to run a distributed protocol π over a network where communication
occurs via private point-to-point channels. Unfortunately, an adversary, who knows π, is able
to maliciously flip bits on the channels. Can we efficiently simulate π in the presence of such an
adversary?
We show that this is possible, even when L, the number of bits sent in π, and T , the number
of bits flipped by the adversary are not known in advance. In particular, we show how to create
a robust version of π that 1) fails with probability at most δ, for any δ > 0; and 2) sends
Õ(L + T ) bits, where the Õ notation hides a log(nL/δ) term multiplying L.
Additionally, we show how to improve this result when the average message size α is not
constant. In particular, we give an algorithm that sends O(L(1 + (1/α) log(nL/δ) + T ) bits.
This algorithm is adaptive in that it does not require a priori knowledge of α. We note that
if α is Ω (log(nL/δ)), then this improved algorithm sends only O(L + T ) bits, and is therefore
within a constant factor of optimal.

1

Introduction

Suppose we start with an n-party distributed computational protocol, to be executed over a network
with point-to-point communication between adjacent parties. Now, imagine a nearly omniscient
adversary, who can flip a subset of the bits sent along these communication channels. This adversary
knows the protocol, as well as the players’ inputs, and is unrestricted in terms of which bits she
will flip. Can the players even hope to carry out their protocol successfully under conditions such
as these?
Surprisingly, the answer is yes, in a surprisingly general sense! However, we will require some additional conditions. Firstly, the adversary cannot have an unlimited budget, or she could effectively
cut off all communication forever by tossing a fair coin to decide whether or not to flip each bit.
We thus restrict the adversary to flipping a total of T bits, where T is a finite number, which is
unknown to our algorithm.
Secondly, we require that the channels are private and cannot be read by the adversary, and that
players have access to private sources of randomness, which are also not readable by the adversary.
This is a crucial assumption, but one for which there are strong justifications. If the players have
access to shared secret randomness, i.e. a one-time pad, then the channels effectively become private,
even if the adversary can see the traffic on them. More generally, if the players have access to strong
cryptography, then the same conclusion holds in practice. Also, we may be interested in robusteness

1

against an oblivious adversary, such as a bursty source of line noise. Such a source may not actually
care about our protocol, but may still time its bursts in a way that happens to be bad for it.
Finally, our assumption of private channels seems to be necessary, since without it, the adversary
can institute a “man-in-the-middle” attack against any desired subset of the players. Since there
is no a priori upper or lower bound on the number of bits, T , flipped by the adversary, such an
attack can always fool the players into thinking they have successully executed the protocol and
T = 0, when in fact, all communication between the two subsets of the players was substituted by
whatever the adversary wanted.
Our Problem and Result Consider a group of n ≥ 2 users who want to run a noisefree asynchronous protocol π, whose length is unknown a priori. These users are connected via a network
of arbitrary topology that is unknown to our algorithm. The edges of the network represent binary
symmetric channels. Communication on these channels is synchronous.
An adversary is able to flip some finite number, T , of bits on any subset of the channels of the
network at any time steps. The adversary chooses π, T , and which bits to flip on the channels. The
adversary also knows our algorithm for transforming π to π 0 . However, similar to the previous work
by Dani et. al [10, 11], we assume that the advsesary neither knows the private random bits of any
user, nor the bits sent over the channels, except when it is possible to infer these from knowledge
of π and our algorithm.
Our results are be summarized in the following theorem.
Theorem 1.1. Let π be a (noisefree) asynchronous protocol for n ≥ 2 users, and let δ > 0. Then,
Algorithm 3 compiles π into a robust protocol π 0 with the following properties. For any finite set
of T (time,channel) pairs, with probability at least 1 − δ, when the adversary flips the bits on those
channels at the corresponding times, the following hold:
1. The simulation succeeds. That is, each user stops after a finite number of time steps, and each
ends in possession of his share of a valid transcript of π.


2. The total number of bits sent is O L 1 + α1 log nL
+
T
. Here L is the total number of
δ
bits and α is the average message length, for the particular transcript of π that was generated.



o
n 
n(L+T )
1
0
+ Tp
, where p ranges over all
3. The total latency of π is O max Λp 1 + α log
δ
p

communication paths in the asynchronous simulation of π, Λp is the latency of p, and Tp is
the total number of bits flipped by the adversary on edges in p.
We note the following. First, our algorithm π 0 always sends Õ(L + T ) bits, where the Õ notation
hides a logarithmic term in n, L and δ. Second, when α is Ω (log(nL/δ)), our algorithm sends only
O(L + T ) bits, and is thus within a constant factor of optimal. Finally, we stress that our algorithm
requires no a priori knowledge of T , L, α, or the network topology, but our algorithm does require
knowledge of n, or at least a polynomial good estimate of n.

1.1

Related Work

Interactive Communication Our work is related to interactive communication. The problem
of interactive communication asks how two parties can run a protocol π over a noisy channel. This
2

problem was first posed by Schulman [27, 28], who describes a deterministic method for simulating
interactive protocols on noisy channels with only a constant-factor increase in the total communication complexity. This initial work spurred vigorous interest in the area (see [3] for an excellent
survey).
Schulman’s scheme tolerates an adversarial noise rate of 1/240, even if the adversary is not oblivious. It critically depends on the notion of a tree code for which an exponential-time construction
was originally provided. This exponential construction time motivated work on more efficient constructions [4, 25, 22]. There were also efforts to create alternative codes [14, 23]. Recently, elegant
computationally-efficient schemes that tolerate a constant adversarial noise rate have been demonstrated [1, 15]. Additionally, a large number of results have improved the tolerable adversarial noise
rate [2, 6, 16, 13, 5], as well as tuning the communication costs to a known, but not necessarily
constant, adversarial noise rate [17].
Our paper builds on a result on interactive communication by Dani et al [11], which in contrast
to previous work, assumes private channels,
number of bit flips by the
pbut tolerates an unknown

adversary. Their algorithm sends L + O
L(T + 1) log L + T bits in expectation. They show
that private channels are necessary in order to tolerate unknown T .
Recently, Braverman et al [7] show a strong lower bound for coding schemes for multiparty interactive communication when π is a synchronous protocol running on a star network, even when noise is
just stochastic. Our result circumvents this lower bound since we require that π be an asynchronous
protocol.
Recent work by Censor-Hillel, Gelles and Haeupler [8], like ours, shows how to make an arbitrary
asynchronous distributed protocol robust against adversarial noise. In their case, the new protocol will succeed if up to Θ(1/n) of the messages are corrupted, and the overhead is a factor of
O(n log2 n) in the total communication. In this setting, the fraction 1/n of corrupted messages is
optimal, because the adversary can simply cut off all communication to a particular player. Notably,
their algorithm proceeds by essentially reducing to the case where the communication network is a
tree.
Our work is not directly comparable to that of [8], because we do not quantify our results in terms of
the fraction of messages that are corrupted, and more importantly, we assume that communication
takes place over private channels. In our case, the stronger assumption of private channels means
that up to a 1/ log(nL) fraction of message bits can be corrupted, and our algorithm will still
succeed with high probability, with a cost overhead that is only log(nL). In our setting, the
adversarial strategy of trying to cut off all communications to and from a single player requires
corruption of much more than a 1/n fraction of the bits, because our protocol can detect the noise,
and consequently increases the fraction of the total communication involving the beleaguered player.
Rateless Codes Rateless error correcting codes enable generation of potentially an infinite number of encoding symbols from a given set of source symbols with the property that given any subset
of a sufficient number of encoding symbols, the original source symbols can be recovered. Fountain
codes [21] and LT codes [24, 19, 18] are two classic examples of rateless codes. Erasure codes employ
3

feedback for stopping transmission [24, 19] and for error detection [18] at the receiver. Critically,
the feedback channel is typically assumed to be noise free. We differ from this model in that we
allow the adversary to flip bits on the feedback channel. Additionally, we tolerate bit flips, while
most rateless codes tolerate only bit erasures.

1.2

Formal Model

Asynchrony of π Recall that a synchronous network is one in which there is a global clock and
each message sent in the network takes one time step to be transmitted. On the other hand, an
asynchronous network is one in which messages may be arbitrarily and adversarially delayed. In
particular messages need not be received in the same order as they are sent. However, every message
must be eventually delivered in a finite amount of time.
As an example, consider a synchronous leader election algorithm in which the users start by waiting
for their ID number of clock ticks. At the end of this, if a user finds no other proclamations of a
leader, he proclaims himself as the leader. This protocol cannot be simulated in our model. To see
this, suppose processor 19 is trying to decide if he is the leader. If he hears meaningless noise on the
channel for multiple time steps of π 0 , then he does not know whether the adversary is simply inserting
this noise on a silent channel, or whether there is a processor 18 whose leadership proclamation is
getting corrupted. Even if he does not hear noise, i.e. if he hears silence all throughout, then he
knows that nobody has transmitted anything to him, but he does not know how many time-steps
of π have passed in the view of the putative processor 18.
Synchrony of π 0 We assume that our protocol π 0 runs in a synchronous network. In particular,
π 0 critically relies on the fact that all processors have synchronized clocks and that communication
time is fixed and known. We define a time step as the amount of time that it takes to send one
bit over a channel, assuming it to be the same for all the channels. As is standard in distributed
computing, we assume that all local computation is instantaneous.
Silence on the channel Similar to [11], when neither user sends on a channel, we say that the
channel is silent. In any contiguous sequence of silent channel steps, the bit received on the channel
in the first step is set by the adversary for free. By default, the bit received in the subsequent steps
of the sequence remains the same, unless the adversary pays for one bit flip each time it wants to
change the value of the bit received in any contiguous sequence of silent steps.
Additional Assumptions We assume that all users know the desired error tolerance δ for π 0 , as
well as the number of users in the network, n. However, the users do not know the values of L and
T , and they have know knowledge of the underlying topology of the network connecting the users.
We further assume that π has a mechanism for users to detect the start and end of messages they
receive. We emphasize that this mechanism need not necessarily involve using end-of-word symbols.
Techniques such as prefix-free codes that do not use any special symbols provide a good alternative.

1.3

Overview of Our Result

In simulation of π using a synchronous protocol π 0 , we assume a global clock which ticks every
time step, and allows all the users to determine how long messages they should send at any time
4

step t ≥ 1, which is only a function of n, δ and t. Once all messages of π have been exchanged in
π 0 , we are sure that the users have terminated and the protocol has ended. Our approach makes
this possible without the use of any synchronization messages across the network, yet keeping all
communication as local to the users as possible.
A key technical challenge here is termination. The length of the simulated protocol is unknown, so
the users will likely not terminate at the same time. After a user has terminated, it is a challenge
for its neighbors to detect this fact based on the bits received over the noisy channel. Our approach
makes use of authentication keys, which every user generates randomly for himself and shares with
whoever wants to communicate with him. We use this key in a way that it makes unlikely for the
adversary to successfully forge messages or silence on the channels, without detection by the affected
users. Hence, a sequence of silent channel steps will suffice, with desired probability, to indicate the
users of the termination of their neighbors.
Our main result is stated in Theorem 1.1. The proof of this theorem and details of how we deal
with the challenges above are presented in the subsequent sections.

1.4

Rate

In most prior work it is assumed that the noise rate of the channel(s) is known and may be used
as a parameter in the design of the algorithm. The parameter of interest then is the rate of the
designed code. In our work we do not assume that the noise rate is known in advance, but only
require that the adversary flip a finite number of bits. Nevertheless, in order to compare our result
with other work, we compute the coding rate of or algorithm as a function of the a posteriori noise
rate. Such a comparison is only meaningful when the adversry’s total budget is less than L, the
length of π, so for this section we will assume that T < L.
Let L0 denote the length of π 0 . Theorem 1.1 states that our algorithm achieves



1
nL
0
L ≤ CL 1 + log
+ CT
α
δ
for some constant C, where δ is the permissible failure probability for the algorithm and α is the
average message length in π. Furthermore, since T < L this translates to the absolute upper bound



1
n(L + T )
0
L ≤ CL 2 + log
(1)
α
δ



1
2nL
≤ CL 2 + log
(2)
α
δ
Let ε = T /L0 be the a posteriori noise rate. Then T = εL0 . Making this substitution for T in (1),
and using (2) to bound the L0 inside the log, we have
 !!
1
2nL
n
L
+
εCL
2
+
log
1
α
δ
L0 ≤ CL 2 + log
α
δ

5

Dividing by L,
 !
n L + εCL 2 + α1 log 2nL
L0
C
δ
≤ 2C + log
L
α
δ




C
C log(2nL/δ)
= 2C +
log(nL/δ) + log 1 + ε 2C +
α
α


C log(2nL/δ)
C log(nL/δ) εC
2C +
+
≤ 2C +
α
α
α



C log(2nL/δ)
εC
≤ 2C +
1+
α
α
To summarize, for the worst case where α = 1, the above shows that we achieve a coding rate that
increases linearly with the noise rate ε and with the logarithm of nL/δ. In particular, the coding
rate is O((1+ε) log(nL/δ)). For arbitrary α, we achieve a coding rate of O((1+ε/α) log(nL/δ)/α).

1.5

Paper Organization

The rest of this paper is organized as follows. In section 2, we describe our main algorithm for the
case where all messages in π are exactly 1 bit in length. We prove this algorithm is correct and
analyze resource costs in Section 3. In Sections 4 and 5, we describe and analyze our algorithms
for the case where messages in π are of an arbitrary size average (thereby achieving better results
for some values of the average size α). Finally, we conclude and give directions for future work in
Section 6.

2

Our Algorithm

We describe our algorithm in this section. For now, we assume that π consists of one-bit messages.

2.1

Notation and Definitions

Some helper functions and notation used in our algorithm are described here.
Algebraic Manipulation Detection Codes Our algorithm makes critical use of Algebraic Manipulation Detection (AMD) codes from [9]. For a given η > 0, called the strength of AMD encoding,
these codes provide three functions: amdEnc, amdDec and IsCodeword. The function amdEnc (m, η)
creates an AMD encoding of a message m. The function IsCodeword (m, η) takes a message m and
returns true if and only if there exists some message m0 such that amdEnc (m0 , η) = m. The function
amdDec (m, η) takes a message m such that IsCodeword (m, η) and returns a message m0 such that
amdEnc (m0 , η) = m. We summarize the results from [9] to highlight the important properties of
these functions in the following lemma.

Theorem 2.1. There exist functions amdEnc, amdDec and IsCodeword, such that for any η ∈ 0, 21
and any bit string m of length x:
 
1. amdEnc (m, η) is a string of length x + 2 log η1 .

6

2. IsCodeword (amdEnc (m, η) , η) and amdDec (amdEnc (m, η) , η) = m.
3. For any bit string s 6= 0 of length x, we have Pr (IsCodeword (amdEnc (m, η) ⊕ s, η)) ≤ η.
Error-correcting Codes These codes enable us to encode a message so that it can be recovered
even if the adversary corrupts a third of the bits. We will denote the encoding and decoding functions by ecEnc and ecDec, respectively. The following theorem, established by the results in [26],
gives the properties of these functions.
Theorem 2.2. [26] There exists a constant Ce > 0 such that for any message m, we have
|ecEnc (m) | ≤ Ce |m|. Moreover, if m0 differs from ecEnc (m) in at most one third of its bits,
then ecDec (m0 ) = m.
With respect to this constant Ce , we define two more constants C1 = 12Ce +76 and C2 = 32Ce +115,
which will be used in our algorithm.
Finally, we observe that the linearity of ecEnc and ecDec ensure that when the error correction is
composed with the AMD code, the resulting code has the following properties:
1. If at most a third of the bits of the message are flipped, then the original message can be
uniquely reconstructed by rounding to the nearest codeword in the range of ecEnc.
2. Even if an arbitrary set of bits is flipped, the probability of the change not being recognized
is at most η, i.e. the same guarantee as for the plain AMD codes.
This is because the error-correcting code is linear, so when noise η is added by the adversary to the
codeword x, effectively what happens is that the decoding function rounds the noise to the nearest
codeword. Thus ecDec (x + η) = ecDec (x) + ecDec (η) = m + ecDec (η), where m is the AMDencoded message. But now ecDec (η) is an obliviously selected string added to the AMD-encoded
codeword, and hence the result is very unlikely to be a valid message unless ecDec (η) = 0.
For a string s, we use the notation s[i] to denote the ith bit of s and s[i, j] to denote the substring
(s[i], s[i + 1], . . . , s[j − 1]). We let |s| denote the length of string s, and use the conventions that
s = (s[0], s[1], . . . , s[|s| − 1]), and for j > |s|, s[i, j] = s[i, |s|].
Silence We define the function IsSilence (s) to return true iff the string s has fewer than |s|/3
bit alternations. We also define S` = {s ∈ {0, 1}` | IsSilence (s)}. We drop the subscript when `
is clear from the context.

2.2

Algorithm Overview

For our algorithm, we assume that each pair of neighboring users communicates over a dedicated
channel. The algorithm proceeds in rounds, each of which consists of the following steps.
1. If u has a message for v, he initiates a message exchange by asking v for a key.
2. Upon receipt of this key, u sends the message along with the key.
7

3. v terminates the message exchange upon successful authentication and retrieval of the message.
4. u terminates the message exchange upon hearing silence from v.
This goes on until all the messages in π have been communicated to the intended recipients.
Rounds
For each message m in π that needs to be sent from some user u to his neighbor v, we communicate
m through a sequence of exchanges between users u, referred to as Alice, and v, referred to as
Bob, in π 0 using Algorithms 1 and 2, respectively. As mentioned above, the sequence of time steps
corresponding to steps 1-4 of the algorithm overview constitute what we call a round. Thus, each
round of π consists of exactly four words, one for each of the steps 1-4. The length of each word in
round r is denoted wr . This depends on the round number, r and is therefore a function of the time
step, that can be computed independently by each user using the clock. We note that wr gradually
increases with r.
We first assume that π has single bit messages. We will extend our results to arbitrary message
lengths in Section 4.
Now, since each message in π is just a single bit, it takes exactly one round to be communicated in
π 0 , if no successful corruption happens, and more otherwise. If a round for some message m is corrupted, we attempt resending m in the subsequent round, possibly with the security increased due
to the potentially increased word length. For technical reasons, Alice needs to distinguish between
successive messages from π. This is because Alice and Bob may have different views on whether a
particular round was successful and there may be times when Alice is resending a message that Bob
has already received. If Bob encounters two progressive rounds with no silent round in between,
which contain the same message, he needs to distinguish between whether Alice is resending the
message or whether Alice’s next message happens to be the same bits as the previous one. To
disambiguate these cases, Alice appends a bit b to each message m where b is the parity of index of
message m. We will denote the pair (m, b) by M .
For convenience, we assume that there are two bidirectional channels between each pair of (neighboring) users, one for each user to initiate a round with the other. Note that, by time-slicing, we
could achieve the same effect on a single bidirectional channel between each pair of users, at the
cost of a factor 2 increase in the number of time steps.
Both Alice and Bob generate their words for round r using a function Er (x, k), described below,
which returns the encoding of the word’s content x using the key k based on the security settings
for round r. Here x may be the message m from π, a special keyword KEY?
l used bym Alice to request
√
Bob’s key, or Bob’s key for the round. The key k is a string of length 2 log 4nπi
bits. In Alice’s
δ
first call to E , k is a random string. In Bob’s call, k is the key he received from Alice in the previous
word, but x is a random string of the appropriate length. In Alice’s second call, k is the key she
received from Bob in the previous word. Alice and Bob generate fresh random keys for each round
in which they desire to send a message.

8

The security settings are arranged so that the word length in round r is given by: The word length
in round r grows logarithmically, and is given by the following formula.:
wr = 300 dlog(nr/δ)e .

(3)

The function Er (x, k) is formally defined as follows. First, it encodes the pair (x, k) using an AMD
code with ηr = 2n2 δπ2 r2 . The result is then encoded with a (1/3)-error-correcting code, such as a
Reed-Solomon code. Finally, enough uniformly random bits are appended to bring the total word
length up to wr . These final random bits are added to ensure that, even if corrupted, any deliberately sent word is very unlikely to be mistaken for silence.
Similar to Er (x, k), we define a function Dr (m) which returns either a pair (x0 , k 0 ) such that
Er (x0 , k 0 ) = m or returns (⊥, ⊥), if no such (x0 , k 0 ) exists. It begins by stripping off the padding
at the end of m to obtain a shorter string m0 . Then it decodes the error correction, computing
m00 = ecDec (m0 ). If IsCodeword (m00 , ηr ), then D outputs amdDec (m00 , η), otherwise it returns
(⊥, ⊥).
The flow of information and control in a round is illustrated in the flowchart in Fig. 1, and specified
in detail in Algorithms 1 and 2.
At the beginning of each round, Bob must listen for a key request during the first wr time steps.
If no valid request is received, he idles until the start of the next round. Thus Bob is active in every round. For her part, Alice only participates in a round if, in π, she has a message to send to Bob.
There are certain events which may cause our algorithm to fail. More specifically, it is possible that
the adversary (1) converts one AMD codeword to another, so that the decoded content is different
from the content intended; (2) converts a non-silence word into silence; and (3) correctly guesses
some user’s key and uses it to communicate bits that are not in π. We will discuss these failure
events in detail in Section 2.3 and analyze their probabilities of occurrence in Section 3.1. However,
for the remainder of this section, we assume that none of these failure events happen.
In what follows we will describe various scenarios for what may happen in a round during the
execution of the algorithm, for a particular bidirectional channel. There are n2 such channels, and
the same round may have different scenarios enacted on it on different channels. Moreover, the
views of Alice and Bob may differ on which scenario was enacted.
Silent Rounds
Bob listens to the first word on the channel and hears silence. Since the adversary cannot manufacture silence, Alice had no message for him and nothing further happens in the round. In this case
both views agree that the round was silent.

9

Progressive Rounds
These are rounds in which the number of bits flipped by the adversary is small enough that it is
handled by the correction schemes. Such rounds proceed as follows.
Alice has a message m for Bob. She requests his key using the resend bit and the keyword KEY?.
Bob decodes Alice’s key request and obtains her key. He generates his own random key and sends
it to Alice using his knowledge of her key to authenticate his message as actually coming from
him. Alice in turn decodes Bob’s communication, obtains his key and sends m, using Bob’s key to
authenticate her communication. Bob correctly receives m, records it in his transcript of π 0 and
remains silent. Alice hears silence on the line and decides that Bob has successfully received her
message. Here both Alice and Bob agree that the round was successful.
Corrupted Rounds
These are rounds when the adversary is active, and corrupts one or more of the words in the round.
Case 1 Alice is silent, but the adversary sends Bob a key request. Then Bob sends Alice his key,
but she is not listening and remains silent. At this point the adversary can say whatever he wants
on the channel. However since he does not know Bob’s key, he cannot authenticate his message. So
Bob receives an invalid communication, and responds with noise, but again Alice is not listening.
Thus such a round is corrupted in Bob’s view, but silent in Alice’s. Note that Bob may realize that
the round was silent in Alice’s view at a later stage, but we still account for this as a corrupted
round, since Bob has already incurred a cost for the corruption.
Case 2 The adversary corrupts Alice’s key request. Then Bob does not receive a valid key request,
and hence remains silent the rest of the round. Since Bob is silent, the adversary may say whatever
he wants on the channel. In particular he may try to pretend he is Bob and send Alice a bogus key.
However since he cannot guess Alice’s key, he cannot authenticate himself as Bob. So Alice receives
an invalid communication, and stays silent until the end of the round.
Case 3 Bob receives Alice’s key request, but the adversary corrupts his communication containing
his key. Since he cannot corrupt one AMD codeword into another, Alice cannot decode the message
into a key for Bob, causing her to remain silent for the remainder of the round. Again, the adversary
cannot install a bogus message from Alice because he cannot guess Bob’s key, so Bob receives an
invalid communication.
Case 4 The adversary is inactive for the first half of the round and Alice receives Bob’s key. Then
the adversary corrupts her communication of m. Then Bob receives garbage at his end and injects
noise into the channel. Since the adversary cannot convert this noise into silence, Alice knows that
the round has failed.
In cases 2, 3 and 4, Alice and Bob both know that the round has been corrupted. Alice will retry
sending her message in the next round.

10

Case 5 The round succeeds all the way to the point where Bob correctly receives m, decides the
round is successful and remains silent. Then the adversary injects noise onto the channel causing
Alice to think the round has failed. In this case again, Alice and Bob’s views differ. However this
is not a problem because Alice will simply resend the message, and Bob will receive it again, in the
next round that is successful in his view. However Bob can recognize the message as a repetition
because of the parity bit. At that stage, of course, Bob realizes that the round was in fact, corrupted,
but this makes no difference to his future actions.

2.3

Failure Events

As mentioned before, there are certain events can cause catastrophic failure from which the algorithm
cannot recover.
1. Failure of AMD codes : The adversary’s bit flips happen to convert an AMD codeword into
another valid AMD codeword. In this case the decoded content differs from the intended
content resulting in authentification failure, when the content was Bob’s key, or incorrect
simulation of π when the content was Alice’s message.
2. Conversion to silence : The adversary’s bit flips are such that the resulting word looks like
silence to its recipient. If the noise sent by Bob in line 19 to request a resend is converted to
silence, then Alice incorrectly assumes that Bob has received her message and stops transmitting it. This results in an incorrect transcript of π. Other words being converted to silence
could result in a player being silent on the following word, which in conjuntion with guessing
the key (see below) could result in the adversary being able to say whatever he wants on the
channel.
3. Guessing the key : On a round when Alice is silent in π, the adversary can install a bogus key request on her channel to Bob. Ordinarily this is not a problem because when Bob
responds with his key, the adversary cannot read it, and therefore cannot send Bob an authenticated message. However, if he happens to guess Bob’s key, then he can send Bob a message
purporting to be from Alice, resulting in an incorrect simulation of π.
We will show in Section 3.1 that the probability of such a catastrophic failure over the entire run
of the algorithm is at most δ.

11

Alice’s protocol

Bob’s protocol

Start

Start

Send key
request
with kA .

Read bits.

Timeline
0

w

No

Valid
request?

Yes
0 ).
Send Keys (kB , kA

Read bits.

2w
No

0 =k ?
kA
A

Yes
Send
message
using
0 .
key kB

Read bits.
3w
Valid
encoding
and
0 = k ?
kB
B

Silence?

Stop

No
Send noise.

Read bits.

No

Yes

Yes

Stop

4w

Figure 1: Flowchart for Alice and Bob during each
12 round. Here w denotes the word length in the
current round.

Algorithm 1 Message exchange algorithm for the sender. Send-Message is only called at the
beginning of a round.
1: procedure SEND-MESSAGE(m)
2:
. b is a persistent variable for the parity bit. On the first call to SEND-MESSAGE, b is set
3:
. to 0. On subsequent calls it is whatever it was set to on the previous call.
4:
while true do
5:
Generate random key kA of length κr
. r is the current round number..
6:
Send Er (KEY?, kA ).
7:
M1 ← wr bits on the channel from the receiver.
8:
if IsSilence (M1 ) then
. assume the receiver has already terminated.
9:
Stay silent for 2wr time steps and return
10:
else
11:
(x, k) ← Dt (M1 )
12:
if k 6= kA then
13:
Stay silent for 2wr time steps.
14:
else
15:
kB ← x
16:
Send Et ((m, b), kB ).
17:
M2 ← wr bits on the channel from the receiver.
18:
if IsSilence (M2 ) then
19:
b ← ¬b and return

13

Algorithm 2 Message exchange algorithm for the receiver. Receive-Message is only called at the
beginning of a round.
1: procedure RECEIVE-MESSAGE( )
2:
. b̂ is a persistent variable for the parity bit. On the first call to RECEIVE-MESSAGE, b̂ is
3:
. set to 0. On subsequent calls it is whatever it was set to on the previous call.
4:
M10 ← wr bits on the channel from the sender.
5:
if IsSilence (M10 ) then
6:
Stay silent for 3wr time steps.
. r is the current round number.
7:
else
8:
(x0 , k 0 ) ← Dt (M10 )
9:
if x0 6= KEY? then
10:
Send noise for wr time steps.
11:
Stay silent for 2wr time steps.
12:
else
13:
kA ← k 0 .
14:
Generate random key kB of length κt .
15:
Send Et (kB , kA ).
16:
M20 ← wr bits on the channel from the sender.
17:
(x00 , k 00 ) ← Dt (M20 )
18:
if k 00 6= kB then
19:
Send noise for wr time steps.
20:
else
21:
(m0 , b0 ) ← x00
22:
if b0 6= b̂ different from last message then
23:
Set b̂ ← b0 and record the message m0 from the sender.
24:
Stay silent for wr time steps.

2.4

The protocol π 0

Our main protocol π 0 is presented as Algorithm 3. We make use of the definition of an I/O automaton
(see [20] Chapter 14.1.1) to represent π. We assume that for each user u in the network, π provides
an I/O automaton πu with the following properties.
• πu has a single initial state
• πu has some subset of states that are termination states. Each termination state may have a
value for u to output.
• There is a set of transition relations, each from one state to another state, each labeled with
an action, where this action may be either an input action (e.g. receiving a message) or an
output action (e.g. sending a message). These transitions satisfy the property for every state
s, for every possible input action, a, there is a transition from s to some other state that is
labelled with a.

14

Algorithm 3 Protocol π 0 , run at each node u
1: s ← initial state of πu
2: while s is not a termination state do
3:
if there is a transition relation from state s to state s0 in πu labeled with an output action
to send message m to neighbor v then
4:
Schedule SEND-MESSAGE(m) to run on the channel to v.
If no call to SEND-MESSAGE is currently running on the channel, begin immediately.
Otherwise, set up the call to begin as soon as all currently scheduled SEND-MESSAGE
calls on this channel have finished running.
5:
Transition to state s0 in πu ; s ← s0 .
6:
else
7:
repeat
8:
for each neighbor v, in parallel run RECEIVE-MESSAGE() on the channel from v.
9:
until the RECEIVE-MESSAGE calls have recorded some non-empty set S of messages
10:
for each message m in S do
11:
Let s0 be the target state on the transition relation from s with input action m.
12:
Transition to state s0 in πu ; s ← s0 .
13: Set processor u’s output based on the termination state.
14: Continue executing any remaining scheduled SEND-MESSAGE calls until all have returned.

3

Analysis

We now analyze the main algorithm as presented in Section 2. We begin by computing the failure
probability for the algorithm, by considering the three bad events as before, and then take a union
bound over all the rounds. We will then prove that the algorithm is correct and terminates in
finitely many time steps. Finally, we compute an upper bound on the expected number of bits the
algorithm sends.

3.1

Probability of Failure

We define three bad events for a round.
1. AMD Failure : The adversary is able to flip the bits to convert the message into another valid
word. In this case, the affected users end their rounds either with authentication failures or
with knowledge of bits which are not in π.
2. Conversion to Silence : The adversary is able to flip bits in such a way that some user’s
random bits look like silence to his neighbor, resulting in the latter ending his round without
the knowledge of this failure.
3. Key Installation : The adversary installs a correct key from Bob when Alice is silent (to
successfully simulate line 16 of Algorithm 1) or installs a correct key from Alice when Bob is
silent (to successfully simulate line 15 of Algorithm 2).
We now bound the probabilities of each of these failure events to eventually prove that our algorithm
succeeds with probability 1 − δ.
15

Lemma 3.1. In π 0 , AMD Failure occurs with probability at most δ/3.
Proof. Recall
that in any round, four words are exchanged between any pair of users, and that at

most n2 < n2 pairs of users may be exchanging words with each other. Furthermore, in a given
round r, the AMD failure probability for a single word is set to be at most ηr = (nπr)−2 δ/2, as
discussed in Section 2.2. Now, for 1 ≤ k ≤ 4, 1 ≤ i 6= j ≤ n and r ≥ 1, define ξi,j,k,r to be the
event that in round r, AMD failure occurs in the k th word exchanged between users i and j. Then,
Pr(ξi,j,k,r ) ≤ (nπr)−2 δ/2. Hence, by a union bound, we get


4 X
n X
[
X
δ
2δ X 1
δ


Pr
ξi,j,k,r ≤
≤
= .
2(nπr)2
π2
r2
3
k=1 i,j=1 r≥1
i6=j

i,j,k,r

r≥1

Lemma 3.2. For b ≥ 95, the probability that a b-bit string sampled uniformly at random from
{0, 1}b has fewer than b/3 bit alternations is at most e−b/19 .
Proof. Let s be a string sampled uniformly at random from {0, 1}b , where b ≥ 95. Denote by s[i]
the ith bit of s. Let Xi be the indicator random variable for the event that s[i] 6= s[i + 1], for
1 ≤ i < b. Note that
Pb−1 Let X be the number of bit alternations
Pall Xi ’s are mutually independent.
X
,
which
gives
E(X)
=
in s. Clearly, X = b−1
i
i=1 E(Xi ), using the linearity of expectation.
i=1
Since E(Xi ) = 1/2 for all 1 ≤ i < b, we get E(X) = √
(b − 1)/2. Using a multiplicative version of
Chernoff’s bound (see [12]), we have that for 0 ≤ t ≤ b − 1,
√


b−1 t b−1
2
Pr X <
−
≤ e−t /2 .
2
2
To obtain Pr(X < b/3), we set t =

b−3
√
3 b−1

to get
(b−3)2

− 18(b−1)

Pr(X < b/3) ≤ e

≤ e−b/19

for b ≥ 95,

where the condition b ≥ 95 comes from rounding the solution to a quadratic equation.
Lemma 3.3. In π 0 , Conversion to Silence occurs with probability at most δ/3.
l 
m
√
Proof. Recall that in round r, each encoded message includes 38 log 2nπr
random bits at the
δ
end. Then, Lemma 3.2 tells us that the probability
that
adversary
is
able
flip
these
random bits of


38 log

2nπr
√
δ

a word to forge silence is at most 2
≤ (nπr)−2 δ/4. Thus, similar to Lemma 3.1, for
1 ≤ k ≤ 4, 1 ≤ i 6= j ≤ n and r ≥ 1, define ξi,j,k,r to be the event that in round r, the k th word
exchanged between users i and j is converted to silence, so that Pr(ξi,j,k,r ) ≤ (nπr)−2 δ/4. Hence,
by using a similar union bound as Lemma 3.1, we get the desired bound.
−

19

Lemma 3.4. In π 0 , the adversary is able to guess the key of some user with probability at most δ/3.

16

m
l 
√
. Each such key is generated
Proof. Recall that in round r, keys are of length 2 log 4nπr
δ
uniformly at random from the set
binary strings of this length. Thus, the probability of
l of
 all m
−2 log

4nπr
√

δ
guessing this key is at most 2
≤ (nπr)−2 δ/16. Again, similar to Lemma 3.1, for
1 ≤ k ≤ 4, 1 ≤ i 6= j ≤ n and r ≥ 1, define ξi,j,k,r to be the event that in round r, the
adversary is able to guess the key in the k th word exchanged between users i and j, so that
Pr(ξi,j,k,r ) ≤ (nπr)−2 δ/16. Hence, by using a similar union bound as Lemma 3.1, we get the
desired bound.

Lemma 3.5. With probability at least 1 − δ, none of the failure events happen during a run of π 0 .
Proof. A run of protocol π 0 fails if any of the three failure events described above happen. From
Lemmas 3.1, 3.3 and 3.4, the total probability of failure is computed by using union bound over the
three failure events, which gives δ/3 + δ/3 + δ/3 = δ. Hence, the run succeeds with probability at
least 1 − δ.

3.2

Correctness

All lemmas in this section assume that none of the failure events occur. Without loss of generality,
we also assume that Alice and Bob generate their keys in every round. We use the phrase terminated
in π to mean finished executing line 13 of Algorithm 3.
Lemma 3.6. Fix a round r of π 0 . Let W be any of the four sequences of wr bits onthe channel from
(r)
(r)
Alice to Bob or the channel from Bob to Alice in this round and kA , kB be the keys that Alice and
Bob generate in this round. Then exactly one of the following hold.
1. IsSilence (W ) is true, in which case the sender on the channel was silent as well.
2. Dt (W ) = C 6=⊥, where t is the time step at which the round r began. Then,
(r)

(a) If C = (KEY?, k), then either Alice sent W with key k = kA , or Alice is silent and the
adversary sent W .
(r)

(r)

(b) If C = (k 0 , kA ), then Bob has not terminated in π yet, and he sent W with key k 0 = kB .
(r)

(c) If C = (x, kB ), then Alice sent W with content x = m(r) , where m(r) is Alice’s message
for Bob in round r.
(d) Otherwise, the adversary sent W on a silent channel.
3. Bob executed line 19 of Algorithm 2.
4. W is the outcome of adversarial tampering on the channel.
Proof. In any given round r, whenever Alice or Bob send a word to the other, this word does not
convert to silence because we assume that the failure event Conversion to Silence does not occur.
Hence, if silence is received on the channel, then the sender on the channel must have been silent
at that time. This proves part (1) of our lemma.
If, however, a valid AMD codeword is received, which decodes into C, the following cases are possi(r)
ble. Case 2(a) : If C = (KEY?, k), then either Alice issued this key request to Bob with her key kA
17

(line 6 of Algorithm 1), or she was silent. In the former case, the adversary is unable to put a key
(r)
(r)
k 6= kA in the codeword since the failure event AMD Failure does not occur, and hence, k = kA .
In the latter case, since the channel is silent, the adversary must have issued the key request with
(r)
some key k. Case 2(b) : If C = (k 0 , kA ), then since we assume that the failure event Key Installation
does not occur, it must be the case that Bob sent W and not the adversary. Thus, Bob must have
(r)
included his own key kB to the codeword along with a copy of Alice’s key (line 15 of Algoithm 2).
(r)
This is only possible when Bob has not terminated in π yet. Case 2(c) : If C = (x, kB ), then
Alice must have sent W since the the failure event Key Installation does not occur. Also, since
we assume that the failure event AMD Failure does not occur, the adversary would have not been
able to convert m(r) into another message successfully, and hence, W must contain the message
that Alice has for Bob in this round. Case 2(d) : If the AMD codeword is neither of the above
three cases, then it must be the case that the sender was on the channel at the time W was on the
channel, since AMD Failure does not occur. Hence, the adversary must have sent W on a silent
channel.
If neither silence nor an AMD codeword is received, then W is noise. The only step in π 0 where
noise is intentionally put on the channel is when Bob has to inform Alice that he did not receive
her message correctly (line 19 of Algorithm 2). Thus, if Bob sent this noise, Case 3 of our lemma
holds, else Case 4 must hold where the adversary has tampered with the bits on the channel so that
W becomes noise.
Lemma 3.7. Assume Alice calls SEND-MESSAGE(m) in some round r1 for some message m
and bit b. Then the following hold: (1) Alice returns from SEND-MESSAGE(m) in some round
r3 ≥ r1 ; and (2) either Bob records the message m (line 23 of Algorithm 2) in exactly one round r2
where r1 ≤ r2 ≤ r3 , or Bob does not record the message m between rounds r1 and r3 because Bob
terminated in π.
Proof. We first show that if Alice calls SEND-MESSAGE(m) in round r1 , then there must exist
some round r3 ≥ r1 in which this call returns. Since the adversary’s budget is finite, there must be
some round, r4 , after which no bits are ever flipped. If the call returns before round r4 , then part
(1) is proven, so we only consider the cases where the call extends past round r4 . In round r4 + 1,
after Alice has sent a key request she either hears silence, indicating that Bob has terminated in π,
and the call returns, or she correctly receives Bob’s key, and uses it to send m which Bob correctly
receives, and records (since the bit b is different than the bit in the last message recorded). Next,
Alice hears silence from Bob. This ends the call. Either way the call returns at the end of round
r4 + 1. Thus, in every case there is some round r3 ≥ r1 in which the call to SEND-MESSAGE(m)
returns.
We now prove part (2) of our lemma. We first show that the message m is recorded at most once by
Bob in the rounds r1 to r3 . By Lemma 3.6 (2(c)), the bit b0 received by Bob in line 21 of Algorithm
2 must be the same as the bit b sent by Alice from rounds r1 to r3 . Since this bit never changes,
Bob will record a message at most once in rounds r1 to r3 .
If Bob terminated in π before round r3 , then part (2) of our lemma statement does not require Bob
to record the message m, and so that part or our lemma is trivially true. Thus, for the remainder

18

of the proof, we assume that Bob has not terminated in π before round r3 .
Consider round r3 in which the call to SEND-MESSAGE(m) returns. Let M1 be the string read by
Alice on line 7 of Algorithm 1. Since Bob has not terminated, Lemma 3.6 (2(b)) guarantees that
Bob sent M1 , and therefore the call to Algorithm 2 does not return on line 9. Hence, it returns on
line 19. Since this is the last round, M1 must correctly decode to (kB , kA ) in Algorithm 1. Thus,
Alice sends Bob m using kB and hears silence subsequently. Thus, Bob must have actually been
silent at this time (Lemma 3.6 (1)), which only happens if he has either now or previously recorded
m. Hence, Bob must have recorded the message m in some round r2 ≤ r3 .
Lemma 3.8. The following holds for π 0 . For any message m that Bob records (line 23 of Algorithm 2) in some round r2 , Alice started a call to SEND-MESSAGE with the message m, in a round
r1 ≤ r2 and returned from that call in some round r3 ≥ r2 .
Proof. Consider the round r2 in which the Bob records a message m (line 23 of Algorithm 2). In
round r2 , in line 21 of Algorithm 2, let Dt (M10 ) = ((m, b), kB ). Thus, by Lemma 3.6 (2(c)), Alice
must have sent Et ((m, b), kB ), during the transmission of M10 . Hence, Alice must be in a call to
SEND-MESSAGE with the message m, and this call must have begun in some round r1 ≤ r2 .
Finally, we know by Lemma 3.7(1) that every call to SEND-MESSAGE ends in some round r3 .
Since, by the above, Alice is in the call during round r2 , it must be the case that Alice returns from
the call in some round r3 ≥ r2 .
Lemma 3.9. Algorithm π 0 terminates with a correct simulation of an asynchronous run of π.
Proof. We show that for every pair of users u and v, protocol π 0 correctly simulates a FIFO message
channel(see [20] Chapter 14.1.2) from u to v during the simulation of π. Then a direct induction
shows that for each processor u, πu0 simulates πu correctly.
Fix an arbitrary channel from u to v in the network. Let Qu,v be the queue of SEND-MESSAGE
procedures that are maintained in π 0 by u of messages to send to v.
We require the following facts:
1. In any time step, there is a transition in πu across a transition relation with an output action
to send a message m to user v, if and only if the procedure SEND-MESSAGE for message m
to user v is pushed on the queue Qu,v in that time step.
2. Every SEND-MESSAGE procedure for message m on Qu,v will eventually start at some round
r1 and end in some round r3 . Moreover, user v transitions across an input transition relation
for message m from user u at most once in some round r2 , r1 ≤ r2 ≤ r3 . Moreover, if there is
no such input transition relation, than πu has entered a termination state before round r3 .
3. For any transition along a transition relation in πv with an input action, in some round r2 , user
u started a call to SEND-MESSAGE with the message m, in a round r1 ≤ r2 and returned
from that call in some round r3 ≥ r2 .
Fact (1) follows directly from Algorithm 3 steps 3-6. The first sentence of Fact (2) follows by induction and Lemma 3.7, and the remainder of the fact follows directly from Lemma 3.7. Fact (3)
19

follows from Lemma 3.8.
Together, the facts show that no matter what the actions of the adversary, the protocol π 0 correctly
simulates a FIFO message channel from user u to user v. In particular, we have: 1) when a transition
is taken in πu with output action to send message m to user v, this message is put on a queue; 2) all
transitions in πv with an input action to receive a message m from user u are associated with the
removal of message m from the queue; and 3) all messages are eventually removed from the queue,
triggering transitions across transition relations with input actions in πv , unless πv is already in a
termination state.

3.3

Resource Costs

We now compute the expected number of bits sent and the latency of π 0 . Let τ (r) be the time step
at which the rth -round of our algorithm begins. Clearly, τ (1) = 1.

Lemma 3.10. In π 0 , round r ≥ 1 begins at time step τ (r) = Θ r log nr
.
δ
Proof. For all r ≥ 1, note that round r + 1 begins as soon as the number of time steps corresponding
to four words of the round r have passed. Hence, we can compute τ (r)P
using the recurrence
r−1
. Now, from
τ (r) = τ (r − 1) + 4wr−1 , where τ (1) = 1. This gives τ (r)
=
τ
(1)
+
4
i=1 wi

P
r−1
ni
ni
equation (3), using
wi ≤ C1 log δ + C2 , we get τ (r) ≤ 1 + 4 i=1 C1 log δ + C2 , which gives
.
τ (r) = Θ r log nr
δ

Lemma 3.11. If τ (x) ≤ z for some x ≥ 1 and z ≥ 1, then x = O(z/ log nz
δ ).
Proof. We prove
 the bound on x for the case that τ (x) =nxz. By Lemma 3.10, we know thatnxτ (x) =
nx
C x log δ , for some constant
C. Thus, z = Cx log δ , and we get (*) x ≤ z/(C log δ ).

0
≤
Cx
log
x. Taking
Note that z = Cx log nx
δ
 logs0 of both
 sides, we get that log z ≤ C log x for
nz
nx
0
some constant C , which implies
that log δ ≤ C log δ . Now plugging this back into (*), we

nz
00
get that x ≤ C z/ log δ for some constant C 00 .
Lemma 3.12. If π 0 succeeds, then it has the following resource costs.


+T .
• The number of bits sent is O L log nL
δ

n


o
)
• The latency is O max Λp log n(L+T
+
T
, where the maximum is taken over all comp
δ
p

munication paths, p, in the asynchronous simulation of π, Λp is the latency of p, and Tp is
the total number of bits flipped by the adversary on edges in p.
Proof. To bound the number of bits sent, we assume pessimistically that in every round of π 0 , there
is an attempt to send exactly one message. This maximizes the number of bits sent since word sizes
increase with time.
Since each word in π 0 is ECC encoded, the adversary must flip a constant fraction of the bits to
successfully corrupt the word, and thereby compromise the round. Let x be the number of rounds
in which some word was successfully corrupted by the adversary. Since the length of the words
increases with successive rounds, T must at least be a constant, C, times the number of bits in the
first x rounds of π 0 , and hence, we must have τ (x) ≤ (T + 1)/C.

20





. Thus, since π 0 requires L progressive rounds,

the total number of rounds is r = L + O log(n(TT+1)/δ) .
Hence the total number of bits sent is at most τ (r). By Lemma 3.10,
By Lemma 3.11, we know that x = O

T
log(n(T +1)/δ)




 

n
T
T
log
L+
O
L+
log (n(T + 1)/δ)
δ
log (n(T + 1)/δ)



n(L + T )
T
log
O
L+
log (n(T + 1)/δ)
δ




n(L + T )
O L log
+T
δ

 

nL
O L log
+T .
δ


τ (r) =
≤
=
=

The second line above follows from the fact that log(n(TT+1)/δ) ≤ T , and the third line from the
fact that if L = O(T ), log(L + T ) = O(log T ). The final line above follows fro the fact that
log(L + T ) = log(L) + log(1 + T /L) ≤ log(L) + T /L, and hence L log(L + T ) ≤ L log(L) + T . This
bounds the number of bits sent.
To bound the latency, we note that the argument above holds for any communication path p in the
asynchronous simulation of π. For the p which achieves the maximum, it follows by induction that
all other required messages will have already been received by the time they are needed, and so p
determines the overall latency.
Now we are ready to complete the proof of Theorem 1.1, in the case when the messages of π are all
single bits.
Proof of Theorem 1.1, special case. By Lemma 3.5, no failure event happens with probability at
least 1 − δ, and by Lemma 3.9, in such a situation, π 0 terminates with an asynchronous simulation
of π. Upon correct termination, the resource cost bounds hold by Lemma 3.12.

4

Simulating Protocols with Messages of Arbitrary Length

So far, we have assumed that all messages sent in the protocol π are single bit messages. In fact π
could send messages of a fixed constant size, or even of size log n and our results would still hold,
provided the initial word length was chosen long enough to be able to encode the messages in π,
the limiting factor here being that the encoding function Et (, ) can only encode strings up to some
length. In this section, we show how to go beyond this restriction and modify our algorithm to be
able to simulate protocols π of arbitrary and variable message length, and we show that the cost of
the simulation scales well relative to the average message length in π.
Before we proceed, we need to discuss what it means for π to have variable message length. After
all, even in the noise-free setting, if Alice is to send Bob a previously unspecified number of bits,
then how is Bob to know when to stop reading bits?
Here we assume that the messages from Alice to Bob in π come from a fixed prefix-free language
L = LA,B . Recall that a language L is prefix-free if for any pair of strings s and s0 in L neither
21

is a prefix of the other. Note that different prefix-free languages may be used between each pair of
players.

4.1

Algorithm

The main simulating algorithm π 0 (Algorithm 3) remains unchanged in this setting. Only the
sending and receiving algorithms need to change to reflect the fact that the message to be sent may
be longer than a single call to Et (, ) can support. In Algorithms 4 and 5 below, we highlight the
necessary changes in red.
Algorithm 4 Message exchange algorithm for the sender.
1: procedure SEND-MESSAGE(m)
2:
. b is a persistent variable for the parity bit. On the first call to SEND-MESSAGE, b is set
3:
. to 0. On subsequent calls it is whatever it was set to on the previous call.
4:
j←0
5:
while j < |m|
6:
(wr , κt ) ← Word-Params(t)
. t is the current time step.
7:
Generate random key kA of length κt .
8:
Send Et (KEY?, kA ).
9:
M1 ← wr bits on the channel from the receiver.
10:
if IsSilence (M1 ) then
. Assume the receiver has already terminated.
11:
b ← ¬b
12:
Stay silent for 2wr time steps and return
13:
else
14:
(x, k) ← Dt (M1 )
15:
if k 6= kA then
16:
Stay silent for 2wr time steps.
17:
else
18:
kB ← x
19:
M ← m[j, j + κt ]
. Next κt bits of m
20:
Send Et ((M, b), kB ).
21:
M2 ← wr bits on the channel from the receiver.
22:
if IsSilence (M2 ) then
23:
j ← j + κt
24:
b ← ¬b
25:
return

22

Algorithm 5 Message exchange algorithm for the receiver.
1: procedure RECEIVE-MESSAGE( )
2:
. b̂, µ, λ are persistent variables for the parity bit, the partially received message, and length
3:
. of the recorded message, respectively. On the first call to RECEIVE-MESSAGE, b̂ ← 0,
4:
. µ ← ∅, λ ← 0. On subsequent calls these variables are whatever they were set to on the
5:
. previous call.
6:
(wr , κt ) ← Word-Params(t)
. t is the current time step.
7:
M10 ← wr bits on the channel from the sender.
8:
if IsSilence (M10 ) then
9:
Stay silent for 3wr time steps.
10:
else
11:
(x0 , k 0 ) ← Dt (M10 )
12:
if x0 6= KEY? then
13:
Send noise for wr time steps.
14:
Stay silent for 2wr time steps.
15:
else
16:
kA ← k 0 .
17:
Generate random key kB of length κt .
18:
Send Et (kB , kA ).
19:
M20 ← wr bits on the channel from the sender.
20:
(x00 , k 00 ) ← Dt (M20 )
21:
if k 00 6= kB then
22:
Send noise for wr time steps.
23:
else
24:
(M 0 , b0 ) ← x00
25:
if µ = ∅ then
26:
if b0 6= b̂ then
27:
λ ← |M 0 |
28:
µ ← M0
29:
else
30:
if b0 6= b̂ then
31:
λ ← |M 0 |
32:
Append M 0 to µ.
33:
else
34:
Replace last λ bits of µ with M 0 .
35:
λ ← |M 0 | do
36:
if µ is a completed message of L then
37:
Record the message µ from the sender.
38:
µ←∅
39:
b̂ ← b0
40:
Stay silent for wr time steps.

23

5

Analysis

5.1

Correctness

Lemma 5.1. Assume Alice calls SEND-MESSAGE(m) in some round r1 for some message m and
bit b. Then the following hold: (1) Alice returns from SEND-MESSAGE(m) in some round r3 ≥ r1 ;
and (2) either Bob records the message m (line 37 of Algorithm 5) in exactly one round r2 where
r1 ≤ r2 ≤ r3 , or Bob does not record the message m between rounds r1 and r3 because he terminated
in π.
Proof. We first show that if Alice calls SEND-MESSAGE(m) in round r1 , then there must exist
some round r3 ≥ r1 in which this call returns. Since the adversary’s budget is finite, there must be
some round, r4 , after which no bits are ever flipped. If the call returns before or during round r4 ,
then part (1) is proven, so we only consider the cases where the call extends past round r4 . Let m0
be the part of the message that remains to be sent. For i ≥ 1 consider round r4 + i. There are two
possibilities:
(a) After Alice has sent a key request in round r4 + i, she hears silence and the call returns, or;
(b) Alice correctly receives Bob’s key, and uses it to send the next piece of m which Bob correctly
receives. Next, Alice hears silence from Bob. If this was the last piece of the message, this
ends the call. If not, the call continues into round r4 + i + 1 with a shorter remaining message.
Since the message has finite length, eventually (a) occurs. Thus, in every case there is some round
r3 ≥ r1 in which the call to SEND-MESSAGE(m) returns.
We now prove part (2) of our lemma. We first show that the message m is recorded at most once
by Bob in the rounds r1 to r3 . By Lemma 3.6 (2(c)), the bit b0 corresponding to the last partial
message for m received by Bob in line 24 of Algorithm 5 must be the same as the bit b sent by
Alice for this partial message from rounds r1 to r3 . Since this bit never changes, Bob will record m
(line 37 of Algorithm 5) at most once in rounds r1 to r3 .
If Bob terminated in π before round r3 , then part (2) of our lemma statement does not require Bob
to record the message m, and so that part or our lemma is trivially true. Thus, for the remainder
of the proof, we assume that Bob has not terminated in π before round r3 and we must show that
he records the message m exactly once.
We do this by induction on the length of m. Note that since m is a message from π, it belonged to
L , so it is actually possible for Bob to record m. If m is short enough to be sent in one piece, then
consider round r3 in which the call to SEND-MESSAGE(m) returns. Let M1 be the string read by
Alice on line 9 of Algorithm 4. Since Bob has not terminated in π, Lemma 3.6 (2(b)) guarantees
that Bob sent M1 , and therefore the call to Algorithm 4 does not return on line 9. Hence, it returns
on line 25. Since this is the last round, M1 must correctly decode to (kB , kA ) in Algorithm 4. Thus,
Alice sends Bob m using kB and hears silence subsequently. Thus, Bob must have actually been
silent at this time (Lemma 3.6 (1)), which only happens if he has either now or previously recorded
m. Hence, Bob must have recorded the message m in some round r2 ≤ r3 .

24

Now as an induction hypothesis suppose the conclusion about Bob recording a message exactly once
is true for all strings s shorter than m. Suppose m requires more than one piece to be sent. Then
since Alice continues to resend the first piece m0 until she has received confirmation that Bob has
received it, there is some round r10 < r3 in which Alice receives this confirmation. Since the same
parity bit b for this piece has been sent in all rounds r ≤ r10 , and received bit b0 agrees with b in
each of these rounds, Bob stores the partial message m0 exactly once. Let m1 be the remaining
portion of m. Clearly it is shorter than m. Now let us examine the control flow throughout the
algorithm from round r10 onwards. This looks exactly like a call to SEND-MESSAGE(m1 ) with
the persistent variable b now set to ¬b, together with a RECEIVE-MESSAGE call in which the
persistent variables b̂ set to ¬b̂ , µ set to m0 , and λ set to |m0 |. By induction hypothesis, there is
exactly one round r2 with r10 ≤ r2 ≤ r3 during which Bob records m0 ◦ m1 , which is in L . But
since m = m0 ◦ m1 , this concludes the proof.
Lemma 5.2. The following holds for protocol π 0 . For any message m that Bob records (line 37 of
Algorithm 5) in some round r2 , Alice started a call to SEND-MESSAGE(m) in a round r1 ≤ r2 and
returned from that call in some round r3 ≥ r2 .
Proof. Consider the round r2 in which the Bob records a message m (line 37 of Algorithm 5).
Suppose µ = ∅ when RECEIVE-MESSAGE was called in round r2 . Then m arose in the first
component of Dt (M10 ) in line 24 of Algorithm 5, where the second component correctly matched
kB . Specifically the first component must have been (m, b) for some b. Thus, by Lemma 3.6 (2(c)),
Alice must have sent Et ((m, b), kB ), during the transmission of M10 . Hence, Alice must be in a call
to SEND-MESSAGE with some message m̂ from L , with m as a contiguous substring, and this
call must have begun in some round r1 ≤ r2 . We must show that m̂ = m. Suppose m is a proper
contiguous substring of m̂, i.e., m̂ = m0 ◦ m ◦ m1 where at least one of m0 and m1 is not ∅. Then
m0 is not in L (since it is a prefix of m̂). Since Alice would not proceed to sending m until she had
confirmed that Bob had received m0 , she must have previously received that confirmation, meaning
that Bob previously received m0 . But in that case, Bob would have that stored as a partial message,
contradicting the assumption that µ = ∅ when RECEIVE-MESSAGE was called in round r2 . Thus
m0 = ∅. But that means that m is a prefix of m̂. Since both m and m̂ are in L , it follows that
m1 = ∅ and m̂ = m. Thus, Alice called SEND-MESSAGE(m).
Next suppose µ = s when RECEIVE-MESSAGE was called in round r2 , for some string s 6= ∅.
Then m = s ◦ x, where x is the string Bob decodes in round r2 . We first induct on the length of s
to prove that Alice’s call to SEND-MESSAGE had as input, some message m̂ from L , such that m̂
contains s◦x = m as a contiguous substring, i.e., m̂ = m0 ◦m◦m1 for some strings m0 , m1 . The case
of s = ∅ was shown above. Thus, assume there exist rounds ρ0 < ρ1 ≤ r2 and non-empty strings s0
and s1 , with s = s0 ◦ s1 such that µ = s0 when RECEIVE-MESSAGE was called in round ρ0 and
µ = s1 when RECEIVE-MESSAGE was called in round ρ1 . Here, ρ0 and ρ1 are the first rounds
with this property. Then Bob decoded s0 in round ρ0 − 1 and s1 in round ρ1 − 1. Furthermore, Bob
has not decoded any other string between decoding s0 and s1 . Then, it follows from the induction
hypothesis that s0 and s1 came from Alice, so that Alice must be in call to SEND-MESSAGE during
the course of which she sends encoded strings s0 , s1 , x in this order. Moreover, she cannot have sent
any other encoded strings in between, because had she done so, she would not have moved on from
it without acknowledgement that Bob decoded it. Since we stipulate that Bob did not decode any
other strings, it follows that the input to Alice’s call to SEND-MESSAGE had m = s0 ◦ s1 ◦ x as a
25

contiguous substring so that m̂ = m0 ◦ m ◦ m1 for some strings m0 , m1 . Note that m0 is not in L .
Now, when Bob decoded s0 , the call to RECEIVE-MESSAGE was passed ∅. Thus, from the discussion in the beginning of the proof, it follows that m0 = ∅ and therefore m1 = ∅ and m̂ = m. Thus,
in all cases, Alice did actually have a call to SEND-MESSAGE(m) that began in some round r1 ≤ r2 .
Finally, we know by Lemma 5.1(1) that every call to SEND-MESSAGE ends in some round r3 .
Since, by the above, Alice is in the call during round r2 , it must be the case that Alice returns from
the call in some round r3 ≥ r2 .

5.2

Resource Costs

We now analyze the total number of bits sent by π 0 when the messages in π may be longer than a
single bit. Let α be the average message length in π.
Lemma 5.3. If π 0 succeeds, then it has the following resource costs.


• The number of bits sent is O L 1 + α1 log nL
+T .
δ

n 


o
)
• The latency is O max Λp 1 + α1 log n(L+T
+
T
, where p is any communication path
p
δ
p

in the asynchronous simulation of π, Λp is the latency of p, and Tp is the total number of bits
flipped by the adversary on edges in p.
Proof. Call a string M encoded in Step 20 of Algorithm 4 a submessage. To upper-bound the
number of bits sent, we assume pessimistically that in every round of π 0 , there is an attempt to
send exactly one submessage. This maximizes the number of bits sent since word sizes increase with
time.
Note that each message consists of at most 1 submessage that is not of length some constant times
the word length in that round. Thus, the number of progressive rounds is no more than the number
of messages sent, L/α, plus the largest integer x such that the number of bits sent in x rounds
equals c1 L for some constant c1 > 1. By Lemma
3.11, x = O(L/ log nL
δ ).


The number of non-progressive rounds is O log(n(TT+1)/δ) , by the same argument as from the proof
of Lemma 3.12.


nL
T
Let the number of rounds r = L/α + O(L/ log δ ) + O log(n(T +1)/δ) . Then by Lemma 3.10, we
can bound τ (r) as follows.




 
T
nr 
L
τ (r) ≤
L/α + O
+O
log
;
log(nL/δ)
log (n(T + 1)/δ)
δ



L
T
n(L + T )
= O
L/α +
+
log
;
log(nL/δ) log (n(T + 1)/δ)
δ




1
n(L + T )
= O
log
+L+T .
α
δ

Finally, to bound the latency, we note that the argument above holds for any communication path
p in the asynchronous simulation of π.

26

Theorem 5.1. The protocol π 0 terminates with a correct simulation of π with probability at least
1 − δ. If π 0 terminates correctly, it has the following resource costs.
 



)
• The expected number of bits sent is O L 1 + α1 log n(L+T
+
T
.
δ


n 
• The expected latency is O max Λp 1 +
p

1
α

log



n(L+T )
δ



o
, where p is any commu+ Tp

nication path in the asynchronous simulation of π, Λp is the latency of p, and Tp is the total
number of bits flipped by the adversary on edges in p.
Proof. By Lemma 3.5, no failure event happens with probability at least 1 − δ, and by Lemma 3.9,
in such a situation, π 0 terminates with an asynchronous simulation of π. Upon correct termination,
the resource cost bounds hold by Lemma 5.3.

6

Conclusion and Future Work

We have described the first algorithm in interactive communication for n users that deals with the
case of unknown number of bits sent by the protocol, while tolerating an unbounded but finite
amount of noise. Against an adversary that flips T bits, given an δ ∈ (0, 1), our algorithm compiles
0
a noise free protocol π that sends L bits into arobust
protocol
with probability

 π that
 succeeds

n(L+T )
1
1 − δ, and upon successful termination, sends O L 1 + α log
+ T bits, where α is the
δ
average message length in π. The blowup in the number of bits is constant for long messages in π
and within logarithmic factors of the optimal, otherwise.
Several open problems remain including the following. First, can we adapt our results to interactive
communication where π is a synchronous protocol? Second, can we handle an unknown amount of
stochastic noise more efficiently, while making no assumption on the value of L or T ? Finally, for
any algorithm, what is the minimum number of private random bits required to be hidden from the
adversary to achieve robustness?

References
[1]

Zvika Brakerski and Yael Tauman Kalai. “Efficient Interactive Coding against Adversarial
Noise”. In: 53rd IEEE Annual Symposium on Foundations of Computer Science (FOCS).
2012, pp. 160–166.

[2]

Zvika Brakerski and Moni Naor. “Fast Algorithms for Interactive Coding”. In: Proceedings of
the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 2013,
pp. 443–456.

[3]

Mark Braverman. “Coding for Interactive Computation: Progress and Challenges”. In: 50th
Annual Allerton Conference on Communication, Control, and Computing (Allerton). 2012,
pp. 1914–1921.

[4]

Mark Braverman. “Towards Deterministic Tree Code Constructions”. In: Proceedings of the
3rd Innovations in Theoretical Computer Science Conference (ITCS). 2012, pp. 161–167.

27

[5]

Mark Braverman and Klim Efremenko. “List and Unique Coding for Interactive Communication in the Presence of Adversarial Noise”. In: Foundations of Computer Science (FOCS),
2014 IEEE 55th Annual Symposium on. 2014, pp. 236–245.

[6]

Mark Braverman and Anup Rao. “Towards Coding for Maximum Errors in Interactive Communication”. In: Proceedings of the Forty-third Annual ACM Symposium on Theory of Computing (STOC). 2011, pp. 159–166.

[7]

Mark Braverman, Klim Efremenko, Ran Gelles, and Bernhard Haeupler. “Constant-rate Coding for Multiparty Interactive Communication is Impossible”. In: Electronic Colloquium on
Computational Complexity (ECCC), TR15-197. 2015.

[8]

Keren Censor-Hillel, Ran Gelles, and Bernhard Haeupler. “Making Asynchronous Distributed
Computations Robust to Noise”. In: arXiv preprint arXiv:1702.07403 (2017).

[9]

Ronald Cramer, Yevgeniy Dodis, Serge Fehr, Carles Padró, and Daniel Wichs. “Detection of
Algebraic Manipulation with Applications to Robust Secret Sharing and Fuzzy Extractors”.
In: Advances in Cryptology–EUROCRYPT 2008. Springer, 2008, pp. 471–488.

[10]

Varsha Dani, Thomas P. Hayes, Mahnush Movahedi, Jared Saia, and Maxwell Young. “Interactive Communication with Unknown Noise Rate”. In: Proceedings of the 36th International
Colloquium on Automata, Languages and Programming (ICALP). 2015.

[11]

Varsha Dani, Thomas P. Hayes, Mahnush Movahedi, Jared Saia, and Maxwell Young. “Interactive Communication with Unknown Noise Rate”. In: Information and Computation (2017),
special issue devoted to selected papers from ICALP 2015.

[12]

Devdatt P Dubhashi and Alessandro Panconesi. Concentration of Measure for the Analysis of
Randomized Algorithms. Cambridge University Press, 2009.

[13]

Matthew Franklin, Ran Gelles, Rafail Ostrovsky, and Leonard Schulman. “Optimal Coding
for Streaming Authentication and Interactive Communication”. In: IEEE Transactions on
Information Theory 61.1 (2015), pp. 133–145.

[14]

Ran Gelles, Ankur Moitra, and Amit Sahai. “Efficient and Explicit Coding for Interactive
Communication”. In: Foundations of Computer Science (FOCS). 2011, pp. 768–777.

[15]

Mohsen Ghaffari and Bernhard Haeupler. “Optimal Error Rates for Interactive Coding II:
Efficiency and List Decoding”. In: Foundations of Computer Science (FOCS), 2014 IEEE
55th Annual Symposium on. IEEE. 2014, pp. 394–403.

[16]

Mohsen Ghaffari, Bernhard Haeupler, and Madhu Sudan. “Optimal Error Rates for Interactive
Coding I: Adaptivity and Other Settings”. In: Proceedings of the 46th Annual ACM Symposium
on Theory of Computing (STOC). 2014, pp. 794–803.

[17]

Bernhard Haeupler. “Interactive channel capacity revisited”. In: Foundations of Computer
Science (FOCS), 2014 IEEE 55th Annual Symposium on. IEEE. 2014, pp. 226–235.

[18]

Morteza Hashemi and Ari Trachtenberg. “Near Real-time Rateless Coding with a Constrained
Feedback Budget”. In: Communication, Control, and Computing (Allerton), 2014 52nd Annual
Allerton Conference on. IEEE. 2014, pp. 529–536.

[19]

Michael Luby. “LT Codes”. In: Foundations of Computer Science (FOCS), 2002.

[20]

Nancy A Lynch. Distributed Algorithms. Morgan Kaufmann, 1996.

28

[21]

David JC MacKay. “Fountain Codes”. In: Communications, IEE Proceedings of Communication, Speech and Vision. Vol. 152. 6. IET. 2005, pp. 1062–1068.

[22]

Cristopher Moore and Leonard J. Schulman. “Tree Codes and a Conjecture on Exponential
Sums”. In: Proceedings of the 5th Conference on Innovations in Theoretical Computer Science
(ITCS). 2014, pp. 145–154.

[23]

Rafail Ostrovsky, Yuval Rabani, and Leonard J. Schulman. “Error-Correcting Codes for Automatic Control”. In: Information Theory, IEEE Transactions on 55.7 (2009), pp. 2931–2941.

[24]

Ravi Palanki and Jonathan S Yedidia. “Rateless codes on noisy channels”. In: IEEE International Symposium on Information Theory. Citeseer. 2004, pp. 37–37.

[25]

Marcin Peczarski. “An Improvement of the Tree Code Construction”. In: Information Processing Letters 99.3 (Aug. 2006), pp. 92–95.

[26]

Irving S Reed and Gustave Solomon. “Polynomial Codes over Certain Finite Fields”. In: Journal of the society for industrial and applied mathematics 8.2 (1960), pp. 300–304.

[27]

Leonard J. Schulman. “Deterministic Coding for Interactive Communication”. In: Proceedings
of the 25th Annual ACM Symposium on Theory of Computing (STOC). 1993, pp. 747–756.

[28]

L.J. Schulman. “Communication on Noisy Channels: A Coding Theorem for Computation”.
In: Foundations of Computer Science, 1992. Proceedings., 33rd Annual Symposium on. 1992,
pp. 724–733.

29

