11institutetext:  University of Luxembourg 22institutetext: University of
Surrey 33institutetext: IT University of Copenhagen 44institutetext:
University of California, Berkeley
Authors listed alphabetically

# A Declaration of Software Independence

Wojciech Jamroga 11 Peter Y.A. Ryan 11 Steve Schneider 22
Carsten Schürmann 33 Philip B. Stark 44

###### Abstract

A voting system should not merely report the outcome: it should also provide
sufficient evidence to convince reasonable observers that the reported outcome
is correct. Many deployed systems, notably paperless DRE machines still in use
in US elections, fail certainly the second, and quite possibly the first of
these requirements. Rivest and Wack proposed the principle of _software
independence_ (SI) as a guiding principle and requirement for voting systems.
In essence, a voting system is SI if its reliance on software is “tamper-
evident”, that is, if there is a way to detect that material changes were made
to the software without inspecting that software. This important notion has so
far been formulated only informally.

Here, we provide more formal mathematical definitions of SI. This exposes some
subtleties and gaps in the original definition, among them: what elements of a
system must be trusted for an election or system to be SI, how to formalize
“detection” of a change to an election outcome, the fact that SI is with
respect to a set of detection mechanisms (which must be legal and practical),
the need to limit false alarms, and how SI applies when the social choice
function is not deterministic.

##  1 Introduction

Using digital technologies in elections opens up possibilities of enriching
democratic processes, but it also brings a raft of new and often poorly
understood threats to election accuracy, security, integrity, and trust. This
is particularly clear with the so-called _DRE_ , Direct-Recording Electronic
voting machines, deployed widely in the U.S. after the Help America Vote Act
(HAVA) of 2002, which passed in the aftermath of the controversial 2000
presidential election. The original DREs recorded, reported, and tallied cast
votes using just software, with no paper record. Thus, an error in or change
to that software could alter the outcome without leaving a trace.

It might be argued that the software could be analysed and proven to always
deliver a correct result given the input votes. In practice, such analysis and
testing is immensely difficult and prohibitively expensive. Moreover, access
to the code is often restricted due to commercial or legal constraints. And
even if the software could be analysed completely and proven correct, there is
still the challenge of guaranteeing that the software actually running on all
the machines throughout the voting period is the “correct”, verified version.

Consequently, for paperless DRE machines, BMDs, and existing Internet voting
systems, voters, election officials et al. are required to place total blind
confidence in the correctness of the code running on the devices.

Such concerns prompted calls to add a Voter-Verifiable Paper Audit Trial
(VVPAT) to DREs, essentially a printer attached to the DRE that prints the
voter’s choice, in sight of the voter. In principle, each voter can check
whether the paper accurately recorded her preferences, and correct the record
if not.111There is considerable evidence that voters rarely check machine-
generated printout and are unlikely to notice that votes were altered. See,
e.g., [Eve07, DKM18, BMM+20, HI21].

An alternative response—piloted but not yet widely adopted for political
elections—is cryptographic end-to-end verifiable voting (E2E-V), which
provides voters a means to verify that their vote reaches the tally unaltered
and is correctly included in the tally. An accessible introduction to such
systems can be found at [BHR+17], and a more extensive description at [HR16]

To capture the essential goal of being able to detect whether faulty software
altered the outcome while remaining agnostic with respect to the technology
employed to achieve that goal (e.g., a paper record or cryptographic methods),
[RW06, Riv08] proposed the principle of _software independence_ , which seeks
to exclude systems for which the trust in the correctness of the outcome
requires trusting the software. The original definition is given as follows:

> A voting system is _software-independent_ if an (undetected) change or error
> in its software cannot cause an undetectable change or error in an election
> outcome.

[RW06, Riv08] also define a stronger requirement, a system that does not
require trusting software, and that is resilient to software-caused errors:

> A voting system is _strongly software-independent_ if it is software
> independent _and moreover, a detected change or error in an election outcome
> (due to change or error in the software) can be corrected without re-running
> the election_.

Version 2.0 of the U.S. Voluntary Voting System Guidelines [Ele21], adopted 10
February 2021, incorporates the principle of Software Independence:

> 9.1 - An error or fault in the voting system software or hardware cannot
> cause an undetectable change in election results.

The principle seems very natural and compelling. It clearly rules out
paperless DRE machines and—subject to certain assumptions about voter
eligibility and the curation of paper ballots—it clearly admits systems based
on hand-marked paper ballots supporting manual recounts, risk-limiting audits
[Sta08], and other forms of audits. However, as soon as we start to consider
applying it to other systems, such as end-to-end cryptographically verifiable
systems, things are less clear. In particular, many of the terms used in the
definition require careful interpretation:

  * •

What exactly do we mean by _the system_? Does it include pollworkers?
Auditors? Where do we draw the boundaries?

  * •

What exactly is the _software_? Does it include software involved in
determining voter eligibility? Auditing software?

  * •

What exactly does it mean to _detect_ an error? Is it enough simply to flag a
problem, or must evidence be provided that there really is a problem? What
kind of evidence? To whom is the evidence available [ADS20]? What rules out
systems that always cry “foul”, even when the election outcome is correct?

  * •

What do we mean by _outcome_ , in particular, where the social choice function
is non-deterministic?

All of this motivates a more formal statement of the principle, which is the
aim of this paper. This reveals a number of subtleties, notably that the
original definition, read literally, does not exclude systems that reject
every declared outcome: there is no penalty for false alarms. We argue that
while software independence is a necessary property for a system to be able to
deliver a verifiable outcome, it is not sufficient. We also stress the
distinction between a _system_ being _verifiable_ and an _election_ being
_verified_.

We do not here address vote anonymity, receipt-freeness, coercion resistance,
and related concerns. We focus just on the issues of detecting and correcting
wrong outcomes while controlling false alarms. In practice, of course, great
care needs to be taken in designing a system to provide sufficient
transparency and generate sufficient evidence without violating privacy
requirements.

We should also remark that, while software independence means that we should
not have to place blind faith in the correct behaviour of the code, this does
not imply that we should do away with all verification and testing of code.
The latter is still important to help ensure the smooth running of any
election run using the system, but the assurance of the outcome should not
depend on the rigor etc. of such measures.

SI is a desirable property, but the use of an SI system does not by itself
give the public adequate reason to trust election outcomes. The fact that it
is possible to detect malfunctions of the software does not mean that checks
will be performed nor that appropriate action will be taken if problems are
detected. And errors or corruption may occur outside the software, e.g.
breaches of chain of custody, faulty procedures, incorrect electoral roles,
etc.

The notion of software independence is related to notions of end-to-end
verifiability (E2E-V); we discuss the relationship in Section 3.2.

##  2 Formalizing Software Independence

In this section we set the ground for a definition that seeks to capture more
formally the spirit of the original natural-language definition. We believe it
is faithful to the spirit of the original, but as we shall see, the definition
reveals some subtleties, and motivates the game-theoretic definition of the
notion of _evidence-based elections_ [SW12, AS20], presented below.222 The
idea of evidence-based elections is that election officials should not only
find the correct winner(s), but should also produce convincing public evidence
that they found the correct winner(s)—or else admit that they cannot.

###  2.1 Software Independence… of What?

To merit public confidence, a voting system should generate evidence that can
be used to check whether it behaved correctly; typically, that involves a
tamper-evident record of voters’ expressed preferences, to which the social
choice function can be applied to check the reported result. That record might
be in the form of a well curated paper audit trail, or, as in many E2E-V
systems, data (some of which is encrypted) posted to a public bulletin board
(ledger). Furthermore, the system should provide for various checks to be
performed on this evidence by the stakeholders: voters, observers, candidates
etc. Such checks might be performed before the election starts (e.g. verifying
that a transparent ballot box is initially empty), during (e.g. Benaloh
challenges), or after (e.g. risk limiting-audits, risk-limiting tallies,
verification of zero-knowledge proofs, digital signatures etc.). We refer to
such checks generically as “audits”.

We consider _software independence as a property of a voting system ${\cal P}$
with respect to a set of audits $\mathcal{A}$_. The voting system ${\cal P}$
represents all the components and aspects relevant for how the election is
run, starting with the voting protocol, including its implementation
(software) and deployment (hardware, physical infrastructure), specification
of the environment, assumptions about human users, threat models, etc. The set
of audits $\mathcal{A}$ captures the notion of “detectability” by providing an
abstract representation of the methods available for detecting something is
amiss.

We emphasize that it only makes sense to talk about software independence with
a particular view of detection methods. For example, a voting system might be
SI if a very powerful (and expensive) kind of instrument or audit can be used,
but not if the requisite tools and methods are unaffordable, too time-
consuming, or not mandated in law or regulation. On the other hand, another
voting system might not be SI with respect to any known audit method, yet may
become SI if a new forensic method is invented.333E.g., think of what happened
to criminal forensics when DNA tests were introduced.  We elaborate on both
aspects of this characterisation below.

###  2.2 Voting System and Its Software

Let ${\cal P}$ be a specification of how the voting protocol should work. This
refers to the overall election system, including hardware, software,
procedural, and human components. More precisely, ${\cal P}$ denotes the
system running “correct” software, i.e., software that correctly computes the
chosen social choice function over the voted preferences of eligible voters.
The software, denoted ${\cal S}$, is considered a part of the system. However,
in an actual execution of the system, ${\cal S}$ may be under the control of
the adversary. Thus, ${\cal S}$ denotes a part of the system on whose correct
behaviour we do not want to rely for evidence that the result is correct. In
practise, that might comprise more than software. The spirit of the original
definition corresponds to taking ${\cal S}$ to be the software that records
and interprets votes, applies the social choice function to them, and reports
an outcome. It does not include software that may form part of the surrounding
system, such as software involved in giving each voter the correct ballot,
software used to verify voter eligibility (e.g. voter registration systems and
electronic pollbooks), or software involved in auditing the results. Nor does
it include the behavior of voters, pollworkers, or election officials.

When we want to make the software ${\cal S}$ explicit in the voting system
${\cal P}$, then we write ${\cal P}[{{\cal S}}]$. Note that it is
straightforward to generalise our approach to quantify over other parts of the
system, e.g., hardware, people, procedures, etc.

The relevant aspects of system ${\cal P}[{{\cal S}}]$ are characterized, on an
abstract level, by the following sets and functions:

  * •

$m({\cal P})$: a function that returns all the relevant mutations ${\cal
P}[{{\cal S}^{\prime}}]$ of the voting system ${\cal P}$. We consider ${\cal
P}[{{\cal S}^{\prime}}]$ as a relevant mutation of ${\cal P}[{{\cal S}}]$ if
${\cal P}[{{\cal S}^{\prime}}]$ can be obtained from ${\cal P}[{{\cal S}}]$
through changing only the software of ${\cal P}[{{\cal S}}]$, i.e., ${\cal
S}$. Hardware and processes and protocols must be the same for ${\cal
P}[{{\cal S}}]$ and ${\cal P}[{{\cal S}^{\prime}}]$. The software that can be
changed is restricted to the software involved in collecting voter selections
(votes), applying the social choice function to the votes, and reporting the
results.

  * •

$\mathit{In}$: the set of possible input sequences. Typically, an input
sequence will comprise all the votes expressed444By _expressed_ , we mean what
the voter did: the marks the voters make on the paper or the cell they press
on a touchscreen. Of course, a confusing user interface—including poor ballot
layout—can cause voters’ expressed preferences to differ from their intended
preferences. See, e.g. [ADS20].  by the voters. Depending on the level of
granularity in our modelling, it may also include other election-related
activity, such as voter registration steps, eligibility verification, coercion
attempts, generation of cryptographic keys, where and how each vote was cast,
etc. It may also include the full expressed preferences of all the voters. In
general, $v\in\mathit{In}$ contains much more information than is needed to
determine who won.

  * •

$\Omega$: the set of possible election outcomes. Typically, an outcome is
either the tally, or the winner(s) of the election. Depending on the level of
granularity, it may also include any other publicly available output of the
voting system, such as the content of the web bulletin board. We assume that
$\Omega$ is finite.

For example, in a plurality contest with two contestants, A and B, the
possible outcomes in $\Omega$ might be “A wins,” “B wins,” and “A and B are
tied.” If the social choice function breaks ties, then there would be only two
possible outcomes: “A wins” and “B wins.”

  * •

$\mathit{exec}({\cal P}[{{\cal S}}],v)$: a function that returns the set of
all the possible executions (runs) of system ${\cal P}[{{\cal S}}]$ on the
sequence of inputs $v\in\mathit{In}$. Any particular election system with a
particular input sequence might have a number of possible executions arising
from the different choices that can be made at various points of the voting
protocol. For example if a voter is required to provide inputs other than just
selections (e.g., to decide whether to challenge an encryption, as allowed in
some E2E-V protocols), then different possible executions can arise. In
practice, there will usually be just one possible execution given $({\cal
P}[{{\cal S}}],v)$, but there may be boundary conditions (e.g. tie-breaking,
or randomness in transferring votes) where more than one result is possible.

Naturally, $\mathit{exec}({\cal P}[{{\cal S}^{\prime}}],v)$ is the set of all
possible executions of the mutated system ${\cal P}[{{\cal S}^{\prime}}]$ on
the input sequence $v$.

  * •

$\mathit{result}(E)$: the outcome of the election for execution $E$. We lift
the function to sets of executions $X$ by fixing
$\mathit{result}(X)=\\{\mathit{result}(E)\mid E\in X\\}$. In the case of the
correct system ${\cal P}[{{\cal S}}]$, we would expect any outcome in
$result(\mathit{exec}({\cal P}[{{\cal S}}],v))$ to be a valid result of the
election.

Note that the composition $\mathit{result}(\mathit{exec}({\cal P}[{{\cal
S}}],v))$ can be seen as a generalisation of a _social choice function_.

###  2.3 Available Audits

In the process of running the election, including recording, tallying, and
broadcasting the election results, the overall voting system ${\cal P}[{{\cal
S}}]$ generates evidence that can be used to audit the election. The auditing
of an election may overlap with, or be completely separate from the voting
procedure. The evidence is provided as input to a decision-making process,
represented by a function $\mathit{a}$, which then provides a judgement. The
software in $\mathit{a}$ is assumed to be trustworthy. Such an assumption of
trustworthiness needs of course to be justified, and this will usually be by
arguing that, if its inputs and intended function are public, anyone who
wishes to check the correctness of its outputs could write it again from
scratch, or a reputable authority such as the Electronic Frontier Foundation
(EFF) could provide a reference implementation.

Evidence produced in the election might include voter registration databases,
poll books, physical ballots, encrypted choices, cryptographic receipts,
public bulletin boards, zero-knowledge proofs (ZKPs), security videos, the
condition of physical seals on ballot boxes, chain-of-custody logs, logs from
telephone complaint lines or websites that record “anomalies” voters witnessed
during the election, etc. The evidence might not include the “plaintext” voter
preferences and generally will not include a voter’s actual interaction with a
DRE or BMD.

Some evidence generated during the election will be unreliable or unavailable.
For instance, paper ballots do not provide reliable evidence of the outcome if
they might have been tampered with, replaced, augmented, or lost; or if voter
eligibility checks were not sufficiently accurate. In some E2E-V systems,
plaintext votes are not available to check the correctness of the outcome; a
system designed to allow voters to check that their intent was recorded
correctly (e.g., using a VVPAT or through a Benaloh challenge) does not
provide public evidence that voter intent was correctly recorded unless there
is both evidence about the number of voters who checked, how effectively they
checked, and a mechanism by which it would become known that they found
errors, if they find errors. It must be also noted that, by the time a
preliminary outcome is available, evidence could be lost, altered, or
counterfeited; the election officials might have reacted to some detected
problems during the election; and that in turn might generate new
possibilities for things to go wrong.

Formally, the capability of the voting authorities (possibly together with
independent auditors, public observers, or with voters, e.g., in case of
mechanisms for voter verification) to detect malfunctioning of the voting
system is characterised by the set
$\mathcal{A}=\\{\mathit{a}_{1},\mathit{a}_{2},\dots\\}$ of available audit
procedures. Let $T$ and $F$ denote the truth values of _true_ and _false_ ,
respectively. Each element $\mathit{a}_{i}$ of $\mathcal{A}$ is a function
that takes an execution $E$ of the voting system, and returns an audit
judgement $\mathit{a}_{i}(E)\in\\{T,F\\}$ such that $\mathit{a}_{i}(E)=F$ only
if there is a change or error in the election outcome. (Below we also consider
audits that have a random component, and thus have some probability of
returning $T$ or $F$ for any given the voting system execution $E$.) It is
required that $\mathit{a}_{i}$ must be compatible with the voting system, in
the sense that the judgment $\mathit{a}_{i}(E)$ is based entirely on the
evidence available in the execution $E$ of the voting system.

For instance, $\mathcal{A}$ might include verifying poll book signatures,
comparing the number of pollbook signatures to the number of votes cast in
each precinct, a manual audit of results against a paper trail, checking ZKPs,
checking whether digital signatures on cryptographic receipts are authentic,
reviewing chain-of-custody records, inspecting equipment log files and
security videos, etc.

An exemplar $\mathit{a}_{i}$ might specify, among its branches, “before
opening each box of ballots for central counting, check the seal on the box
against a photograph of the seal taken in the polling place. If the seal has
been disturbed, interview everyone who has had custody of the box since it was
sealed, examine every ballot by hand for signs of tampering or forgery, and
compare the number of ballots in the box with the number of pollbook
signatures.”

##  3 Possibilistic Formulation of Software Independence

The original definition of SI talks about whether a change to the result is
always detectable. This is expressed in terms of possibilities rather than
probabilities. Here we see how far we can get with expressing SI
possibilistically without involving probabilities. We will also show that it
is natural to introduce probabilities into the audit process.

###  3.1 Basic Formulation

Using the notation introduced in Section 2, the property of Software
Independence with respect to a particular election input $v$ and audit method
$\mathit{a}$ can be expressed as follows:

$\displaystyle SI_{1}({\cal P}[{{\cal S}}],v,\mathit{a})\iff$
$\displaystyle\forall{\cal P}[{{\cal S}^{\prime}}]\in m({\cal P}[{{\cal
S}}])\;.\;$ $\displaystyle\big{(}\forall E^{\prime}\in\mathit{exec}({\cal
P}[{{\cal S}^{\prime}}],v)\;.\;\exists E\in\mathit{exec}({\cal P}[{{\cal
S}}],v)\;.\;(\mathit{result}(E)=\mathit{result}(E^{\prime}))\big{)}$
$\displaystyle{}\lor\big{(}\exists E^{\prime}\in\mathit{exec}({\cal P}[{{\cal
S}^{\prime}}],v)\;.\;\mathit{a}(E^{\prime})=F\big{)}.$

The formula states that every execution of any mutation of ${\cal P}[{{\cal
S}}]$ gives a correct result, or else the malfunction is detectable. More
precisely, either every execution of a mutation of ${\cal P}[{{\cal S}}]$
gives a result that could have been produced by the correct software, or there
is some execution that will fail the audit.

Then, Software Independence holds with respect to a set of possible election
inputs $v\in\mathit{In}$ and allowable audit procedures $\mathcal{A}$ if there
is some audit procedure $\mathit{a}\in\mathcal{A}$ such that SI holds for all
possible inputs:

$\displaystyle SI_{1}({\cal P}[{{\cal S}}],\mathcal{A})$ $\displaystyle\iff$
$\displaystyle\exists\mathit{a}\in\mathcal{A}\;.\;\forall
v\in\mathit{In}\;.\;SI_{1}({\cal P}[{{\cal S}}],v,\mathit{a}).$ (2)

Arguably, formula (3.1) captures software independence of particular
_election_ , given the set of votes and actual audit strategy used in the
election. In contrast, formula (2) expresses software independence of the
_voting system_ defined by the voting infrastructure and the available audit
strategies.

Remarks. Formulas (3.1)–(2) capture a rather weak notion of Software
Independence. First, they only say that ${\cal P}[{{\cal S}^{\prime}}]$ cannot
undetectably add incorrect outcomes to the set of possible results of the
election. However, a software mutation _removing_ some of the correct results
may as well satisfy the conditions. We address this issue in Section 3.5.

Secondly, the formalisation is based on a weak notion of detectability. The
conditions require that significant software mutations _might_ be detected
(i.e., they are detected on some possible executions), but there is no
guarantee that they can be detected for every execution that produces
incorrect outcomes.

A stronger definition of SI is obtained by replacing the right hand side of
the disjunction (3.1) as follows:

$\forall E^{\prime}\in\mathit{exec}({\cal P}[{{\cal
S}^{\prime}}],v)\;.\;\big{(}(\exists E\in\mathit{exec}({\cal P}[{{\cal
S}}],v)\;.\;\mathit{result}(E)=\mathit{result}(E^{\prime}))\lor(\mathit{a}(E^{\prime})=F)\big{)}.$

This removes the existential quantification over executions and brings
$E^{\prime}$ under the universal quantification. The first formalisation
allows for some executions of a mutation not to be caught by an audit even if
they give the wrong result. This stronger formalisation states that any
execution of a mutation that does not give the correct result should be caught
by an audit.

Note also that our formalisation is focused on the potential irregularities
due to software mutations. Thus, disturbances of the election outcome due to
failures of hardware, dishonest voter behaviour, etc., must only be handled in
${\cal P}[{{\cal S}^{\prime}}]$ if they would be caught and dealt with in the
ideal system ${\cal P}[{{\cal S}}]$.

Audit Strategies. We recall that the characterisation of $\mathcal{A}$
encapsulates the audit methods that are allowable. Considerations as to what
should be allowable can include what is possible, affordable (in terms of cost
or time), legal (to fit with local election law, preserve the anonymity of
votes, etc.), and other considerations as appropriate to the situation.
Identifying the limits of what is allowable is itself part of the
consideration as to whether a system is software independent. From a technical
point of view, the definition of $\mathcal{A}$ will also need to depend on the
evidence provided explicitly by the voting system. Thus the formalisation of
possible executions $E$ also constrains the audits that are possible, because
$\mathit{a}$ is a function on executions: two runs giving rise to the same
execution record $E$ must give the same result on audit. For example, if the
only evidence collected for audit is the set of paper ballots, then forensic
analysis of the hard disks of the voting machines is outside the scope of
audit. Conversely if the audit includes the possibility of such analysis, then
the evidence provided by an election run should include the relevant state of
the hard disks to enable the audit function to be defined.

The sanity condition (or soundness) on an auditing mechanism $\mathit{a}$ for
system ${\cal P}[{{\cal S}}]$ is that any correct execution of the ideal
system will verify positively:

$\displaystyle{\textbf{sound}(\mathit{a},{\cal P}[{{\cal S}}])\iff}\forall
v\in\mathit{In}\;.\;\forall E\in\mathit{exec}({\cal P}[{{\cal
S}}],v)\;.\;\mathit{a}(E)=T.$

Although this is not stated explicitly within the original definition of
Software Independence, correct election outcomes should not be flagged by the
audit as incorrect, so we will require that every $\mathit{a}$ function in
$\mathcal{A}$ be _sound_.

###  3.2 Relationship to End-to-End Verifiability

The definitions above enable us to highlight an important distinction between
Software Independence and End-to-end Verifiability (E2E-V), cf. [BRR+15] for
an introduction and [KTV11] for a well-known formalisation. In particular, in
a description of a system ${\cal P}[{{\cal S}}]$ the component ${\cal S}$
explicitly represents only the software, and the context ${\cal P}$ remains
unchanged. This amounts to requiring that the context ${\cal P}$ is trusted in
the characterisation of SI. However, when we consider whether the system
${\cal P}[{{\cal S}}]$ is end-to-end verifiable, we consider this question
with respect to the entire system.

We should note that not all formulations of E2E-V in the literature actually
imply correctness of the outcome. Early formulations focused on the ability to
detect the corruption of any vote between casting and input to the tally
function. To achieve guarantees of correctness we also need measures to
prevent ballot stuffing and ballot collisions. Taken together, these imply a
bijection between the set of cast votes and the set of votes input to the
tally. Here we assume a definition that does encompass these requirements, as
does [KTV11]. Here they refer to such a strengthened notion, that does imply
correctness if all verification steps give true, as _global verifiability_.

To illustrate the difference, consider the following toy example, which shows
that SI does not imply E2E-V: A voting system consists of a ballot box for
paper ballots, a scanner, and a software component ${\cal S}$ that controls
the scanner, interprets the scans, applies the social choice function to the
votes, and reports the result. There is a trusted individual ${\cal I}$
(appointed by the Election Authority, say) who will also play a key part. A
description of the system formulated as ${\cal P}[{{\cal S}}]$ would include
${\cal I}$ within the definition of ${\cal P}$.

Voting: To vote, voters fill out their ballot form, run it through the
scanner, then drop it in the ballot box.

Tallying: At the end of the election, ${\cal I}$ privately counts the votes
from the ballot box and calculates the result $r_{1}$. The electronic
component ${\cal S}$ computes the result $r_{2}$ from the scans, and provides
this result to ${\cal I}$, who privately checks whether $r_{1}=r_{2}$. If so,
then ${\cal I}$ reports the result. Otherwise an alarm is raised and an audit
occurs, consisting of comparing $r_{1}$ and $r_{2}$. if they are distinct then
the audit returns the value $F$.

The system ${\cal P}[{{\cal S}}]$ is SI, because an undetected change in
${\cal S}$ cannot undetectably change the result, and the system meets the
definition in Line 3.1. Given a change to the software, either the resulting
software still gives the same result, or the audit will return the value $F$.
Note that this relies on the honesty and correct behaviour of ${\cal I}$; this
is assumed for the characterisation of SI.

The system ${\cal P}[{{\cal S}}]$ is not E2E-V. Voters are not able to check
that their vote is included in the tally, and there is no check for
independent observers that the tally is computed correctly. In particular,
${\cal I}$ can simply report a different result and not raise the alarm.

One key difference is that for SI, any part of the system that is not the
software is presumed to be acting as it should. Hence, the question is whether
a change to ${\cal S}$ can change the result when ${\cal P}$ behaves
correctly.

On the other hand for E2E-V we also consider that ${\cal P}$ can behave
dishonestly. So ${\cal P}[{{\cal S}}]$ is not E2E-V: it is possible for the
wrong result to be reported without any verification checks showing incorrect
behaviour.

A further distinction is that SI makes no mention of who does the “detecting,”
whereas E2E-V is quite explicit: each voter can perform the individual check
and anyone can perform the universal check. The example above illustrates this
point, too.

#### E2E-V $\Rightarrow$ SI:

Conversely, we can reason informally that E2E-V implies SI, via a
contrapositive argument as follows. If a system with verification mechanisms
is not SI, then by Definition 2 for some input $v$ there is a change to the
software ${\cal S}^{\prime}$ that can result in an execution $E^{\prime}$ with
an incorrect result $result(E^{\prime})$ that passes every audit
$audit\in\mathcal{A}$, i.e. it produces an undetectable change to the result.
But if the incorrectness of the result is undetectable, then the verification
mechanisms cannot detect this, and hence will verify an incorrect result. But
this means the system is not E2E-V, since E2E-V requires that if all potential
verification steps pass555I.e., every voter checks what individual voters can
check (individual verifiability), someone checks the aggregation of votes
(universal verifiability), and someone checks that every vote has come from a
different eligible voter (eligibility verifiability).  then the result is
correct. Note that here we are assuming a strong notion of verifiability, such
as global verifiability.

Observe that both audits and verifications can raise an alarm even when the
result is correct. We are not concerned with this case in this section, but
rather the converse case where the audits and verifications do not raise the
alarm even though the result is incorrect.

###  3.3 SI with Adaptive Audits

The formalization of SI by formulas (3.1)–(2) assumes that there exists a
single audit strategy in $\mathcal{A}$ that can detect malfunction and/or
tampering with the voting software. Another option is to swap the quantifiers,
and assume that different audit procedures may be applicable on different runs
of the voting system (e.g., against different kinds of threats). Now, SI with
respect to a set of available audits becomes:

$\displaystyle SI_{2}({\cal P}[{{\cal S}}],\mathcal{A})\iff\forall
v\in\mathit{In}\;.\;SI_{2}({\cal P}[{{\cal S}}],v,\mathcal{A});$
$\displaystyle SI_{2}({\cal P}[{{\cal S}}],v,\mathcal{A})\iff$
$\displaystyle\forall{\cal P}[{{\cal S}^{\prime}}]\in m({\cal P}[{{\cal
S}}])\;.\;$ $\displaystyle\big{(}\forall E^{\prime}\in\mathit{exec}({\cal
P}[{{\cal S}^{\prime}}],v)\;.\;\exists E\in\mathit{exec}({\cal P}[{{\cal
S}}],v)\;.\;(\mathit{result}(E)=\mathit{result}(E^{\prime}))\big{)}$
$\displaystyle{}\lor\big{(}\exists E^{\prime}\in\mathit{exec}({\cal P}[{{\cal
S}^{\prime}}],v)\;.\;\exists\mathit{a}\in\mathcal{A}\;.\;\mathit{a}(E^{\prime})=F\big{)}.$

That is, either every execution of any mutation of ${\cal P}[{{\cal S}}]$
gives a result that could have been produced by the correct software, or there
is some execution that will fail at least one audit procedure in the available
audit set. Again, formula (3.3) captures software independence of an election,
and (2) expresses SI of the voting system. Note that these notions of
detection are still somewhat weak in that they do not ensure that anyone can
tell _which_ $a\in\mathcal{A}$ suffices for any particular execution $E$.

###  3.4 A Refinement

Audit procedures are often nondeterministic by design (e.g., audits that
inspect a random sample of ballots, including risk-limiting audits). In our
definition of SI, it can be beneficial to separate the randomness of the audit
from randomness in the rest of the system. This view can be incorporated by
treating audit procedures as functions on system executions $E$ that return a
probability distribution on $\\{T,F\\}$.

For example, for statistical audit of the paper trail, different audit runs
result from inspecting different random samples of ballots, each of which has
some probability; for some runs, the audit might return $T$ and for others
$F$.

The soundness sanity condition on the auditing mechanism $\mathit{a}$ stays as
before.

Having separated the audit non-determinism from the system non-determinism, we
can now redefine “undetectable change” to apply to those _system runs_ for
which the probability that the audit returns $F$ is zero. Let $\mathit{Pr}$
denote probability computed with respect to the audit, treating . Now,
software independence of system ${\cal P}[{{\cal S}}]$ with respect to the
audit set $\mathcal{A}$ becomes:

$\displaystyle SI_{3}({\cal P}[{{\cal S}}],\mathcal{A})\ \,\iff\
\exists\mathit{a}\in\mathcal{A}\;.\;\forall v\in\mathit{In}\;.\;SI_{3}({\cal
P}[{{\cal S}}],v,\mathit{a});$ (4) $\displaystyle SI_{3}({\cal P}[{{\cal
S}}],v,\mathit{a})\iff$ $\displaystyle\forall{\cal P}[{{\cal S}^{\prime}}]\in
m({\cal P}[{{\cal S}}])\;.\;\forall E^{\prime}\in\mathit{exec}({\cal P}[{{\cal
S}^{\prime}}],v)\;.\;$ $\displaystyle(\exists E\in\mathit{exec}({\cal
P}[{{\cal S}}],v)\;.\;\mathit{result}(E)=\mathit{result}(E^{\prime}))\lor$
$\displaystyle\mathit{Pr}(\mathit{a}(E^{\prime})=F)>0.\qquad\qquad\qquad\qquad\qquad\qquad\mbox{}$

The definition can be equivalently phrased as follows. Let

$\displaystyle\mathit{AccResults}({\cal P}[{{\cal
S}^{\prime}}],\mathit{a},v)=\left\\{\omega\ \mid\ \exists
E^{\prime}\in\mathit{exec}({\cal P}[{{\cal S}^{\prime}}],v)\;.\;\right.$
$\displaystyle\qquad\left.\left(\omega=\mathit{result}(E^{\prime})\land\mathit{Pr}(\mathit{a}(E^{\prime})=T)=1\right)\right\\}$

be the set of _surely accepted results_ for ${\cal P}[{{\cal S}^{\prime}}]$ on
$v$. That is, these are the possible outcomes of running ${\cal P}[{{\cal
S}^{\prime}}]$ on input $v$ for which the audit has zero probability of
reporting that the outcome is wrong. Note that, for the ideal system ${\cal
P}[{{\cal S}}]$, if the audit meets the soundness condition this is just the
set of possible (correct) outcomes, i.e., $\mathit{AccResults}({\cal P}[{{\cal
S}}],\mathit{a},v)=\\{\mathit{result}(E)\ \mid\ E\in\mathit{exec}({\cal
P}[{{\cal S}}],v)\\}$. Since in that case the set does not depend on the audit
strategy, we will often write $\mathit{AccResults}({\cal P}[{{\cal S}}],v)$
instead of $\mathit{AccResults}({\cal P}[{{\cal S}}],\mathit{a},v)$. Then,
formula (3.4) can be rephrased as:

$\displaystyle SI_{3}({\cal P}[{{\cal S}}],v,\mathit{a})\iff$
$\displaystyle\forall{\cal P}[{{\cal S}^{\prime}}]\in m({\cal P}[{{\cal
S}}])\;.\;\mathit{AccResults}({\cal P}[{{\cal
S}^{\prime}}],\mathit{a},v)\subseteq\mathit{AccResults}({\cal P}[{{\cal
S}}],v).$

###  3.5 Software Resilience

The above definition says that every execution of ${\cal P}[{{\cal
S}^{\prime}}]$ either simulates a legitimate execution of ${\cal P}[{{\cal
S}}]$ or has a strictly positive chance of being “detected” by the audit. This
kind of property is arguably closest to the spirit of the proposal by Rivest
and Wack. Also, it corresponds to the intuition that, usually, the only
evidence that one has to determine a property of an election system comes from
the actual run of the system during the actual election. However, as a system
property, it is rather weak. Ideally, one would also like to guarantee the
“vice versa” condition, saying that every outcome of the ideal software can be
produced by the mutation ${\cal P}[{{\cal S}^{\prime}}]$. That is, ${\cal
P}[{{\cal S}^{\prime}}]$ not only does not introduce any illegal winners, but
also does not remove any legally possible ones. Then, every mutation ${\cal
P}[{{\cal S}^{\prime}}]$ must produce exactly the same set of acceptable
election outcomes as the ideal system ${\cal P}[{{\cal S}}]$. We call the new
property _software resilience (SR)_ , and define it formally as follows:

$\displaystyle\mathit{SR}({\cal P}[{{\cal
S}}],\mathcal{A})\iff\exists\mathit{a}\in\mathcal{A}\;.\;\forall
v\in\mathit{In}\;.\;\mathit{SR}({\cal P}[{{\cal S}}],v,\mathit{a});$
$\displaystyle\mathit{SR}({\cal P}[{{\cal S}}],v,\mathit{a})\iff$
$\displaystyle\forall{\cal P}[{{\cal S}^{\prime}}]\in m({\cal P}[{{\cal
S}}])\;.\;\mathit{AccResults}({\cal P}[{{\cal
S}^{\prime}}],\mathit{a},v)=\mathit{AccResults}({\cal P}[{{\cal S}}],v).$

In other words, $\mathit{SR}({\cal P}[{{\cal S}}],v,\mathit{a})$ requires that
every mutation ${\cal P}[{{\cal S}^{\prime}}]$ is trace-equivalent to ${\cal
P}[{{\cal S}}]$ with respect to the surely accepted election outcomes that
they can produce.

In practice of course, what the electorate needs is a way to determine, as the
end of a given election, whether the reported outcome was not only one of the
possible correct outcomes, but also fair in some sense. Where the outcome is
uniquely defined this is fine: it is enough that we can determine that it was
correct. Where the outcome is not uniquely defined, for example in the event
of a tie in a simple plurality vote resolved by the system’s software (rather
than, for instance, by a public coin toss), this is more delicate: we would
like to be able to establish that no possible outcomes were excluded by that
particular software running at the time. If the tie is resolved by the
software, there is no way to establish one the basis of observation of a
single run.

In order to resolve such situations it seems necessary to externalise the
mechanism that makes the choice amongst possible outcomes, for example based
on a publicly observable coin toss or equivalent. How to provide a truly
random source that cannot be predicted or influenced by any way is a topic in
its own right, outside the scope of this paper.

Another approach is to regard the outcome as the raw tally, and the resolution
of any ties etc. to be outside the scope of the definition. However, the
outcome can be correct even when the tally is not—indeed, this is why risk-
limiting audits can be efficient. Machine tallies of hand-marked paper ballots
are rarely if ever perfectly accurate.

Moreover, non-determinism may be buried in the tabulation algorithm itself,
and so not neatly separable. This is for instance the case in the STV variant
used in New South Wales, Australia, as well as the D’Hondt method of
allocating seats in the parliament in many European countries.

###  3.6 Thought Experiment

A simple voting system with rather a weak audit highlights some aspects of the
definitions.

Consider a voting system ${\cal P}_{\mathit{w}eak}$ defined as follows:

#### Voting

  1. 1.

Votes are cast on paper (filling in a bubble by hand), scanned, and then
deposited into a ballot box. The scans are linked to the corresponding paper
ballots in a way that allows the scan corresponding to a particular ballot to
be retrieved, and vice versa.

  2. 2.

All of the scans are then published, and the result declared.

Here the software ${\cal S}$ controls the scanning, tabulation, and reporting.
We assume that there is good physical security of the ballots, and that the
total number of ballots is known.

#### Audit

  1. 1.

Auditors check whether the number of scans matches the number of ballots. If
not, the audit returns $F$.

  2. 2.

Auditors inspect every scan and tabulate the resulting interpretation of the
votes to obtain an electoral outcome. If that outcome differs from the
reported outcome, the audit returns $F$.

  3. 3.

A paper ballot is selected at random. Its corresponding scan is retrieved and
checked to see whether the human interpretation of that scan matches the human
interpretation of the ballot. If not, the audit returns $F$.

According to the Rivest/Wack definition of SI this system is SI, because any
change in the result (caused by a change in the software) can be in principle
detected. Thus, it meets the formal characterisation in Line 3.1. However,
this audit may have a low probability of detecting an attack that alters or
substitutes scans. If the fraction of the altered scans is $\delta$, then
$\delta$ is also the chance of detecting the attack. (Moreover, this audit may
produce false alarms: the reported outcome could be correct even if some scans
were altered.)

###  3.7 Software Independence for Probabilistic Audits

The thought experiment illustrates that audits can be (and usually are)
probabilistic. Although the Rivest/Wack definition of software independence is
expressed in possibilistic terms, a comment (almost in passing) in [Riv08]
indicates that in practice there should be a high probability of detecting
software misbehaviour:

> The detection of any software misbehavior does not need to be perfect; it
> only needs to happen with sufficiently high probability, in an assumed ideal
> environment with alert voters, pollworkers, etc.

This is a rather stronger requirement, and introduces probability into the
characterisation. Where should this probability be introduced?

The idea should be that whatever mutation of ${\cal P}$ is considered, and for
any execution of that mutation, if the result has been changed then this
should be detectable with high probability. The ‘detectable’ element of this
definition is the responsibility of the audit function.

Then we can adjust the definition of Software Independence of Section 3.4 to
incorporate the additional requirement that when the result has been changed,
the audit has a probability $p_{0}>0$ to notice that:

$\displaystyle SI_{4}({\cal P}[{{\cal
S}}],\mathcal{A},p_{0})\iff\exists\mathit{a}\in\mathcal{A}\;.\;\forall
v\in\mathit{In}\;.\;SI_{4}({\cal P}[{{\cal S}}],v,\mathit{a},p_{0});$
$\displaystyle SI_{4}({\cal P}[{{\cal S}}],v,\mathit{a},p_{0})\iff$
$\displaystyle\forall{\cal P}[{{\cal S}^{\prime}}]\in m({\cal P}[{{\cal
S}}])\;.\;\forall E^{\prime}\in\mathit{exec}({\cal P}[{{\cal
S}^{\prime}}],v)\;.\;$ $\displaystyle\qquad(\exists E\in\mathit{exec}({\cal
P}[{{\cal
S}}],v)\;.\;\mathit{result}(E)=\mathit{result}(E^{\prime}))\qquad\qquad\qquad\qquad\mbox{}$
$\displaystyle\qquad{}\lor\mathit{Pr}(\mathit{a}(E^{\prime})=F)\geq p_{0}.$

This is clearly stronger than the previous definition in Equations (4)–(3.4).

##  4 Probabilistic/Game-Theoretic Definition

In the previous section, we proposed a possibilistic definition of software
independence. It was based on the assumption that we can quantify over
possibilities (possible mutations of the software, executions of the system,
etc.) but cannot formulate constraints with respect to quantitative measures
over the possibilities (e.g., probability of executions or computational
complexity of a mutation strategy). The first step towards a more quantitative
approach was discussed in Section 3.7 where we considered audits with a random
component. Here, we present a full-blown quantitative definition of SI. We
assume the following:

  1. 1.

The execution of ${\cal P}[{{\cal S}}]$ on an input $v$ defines a probability
distribution over all the possible runs in $\mathit{exec}({\cal P}[{{\cal
S}}],v)$;

  2. 2.

The execution of audit method $\mathit{a}$ given a system execution $E$
defines a probability distribution on $\\{T,F\\}$;

  3. 3.

The choice of a software mutation belongs to a potentially malicious
“attacker,” whereas the auditing method is selected by the “defender.” The
input sequence $v\in\mathit{In}$ is chosen by Nature;

  4. 4.

The defender must select the audit without knowing the mutation the attacker
selected. (However, the audit procedure can be adaptive.) The attacker knows
the defender’s audit strategy in advance, but not any random elements involved
in that strategy. E.g., the attacker might know that the auditor will examine
a random sample of ballots, but does not know which particular ballots will be
examined.

###  4.1 Terminology and Notation

As before, $\mathit{Pr}$ denotes probability. Moreover, we will use
$\mathsf{Exec({\cal P}[{{\cal S}}],v)}$, $\mathsf{Res(E)}$, and
$\mathsf{Aud(E)}$ for the random variables ranging over possible runs
$E\in\mathit{exec}({\cal P}[{{\cal S}}],v)$, possible election outcomes
$\omega\in\mathit{result}(E)$, and audit judgments in $\\{T,F\\}$,
respectively.

Election Environment. Given the input $v\in\mathit{In}$ (in particular, the
voters’ expressed preferences), the voting system ${\cal P}[{{\cal S}}]$
defines a probability distribution $\mathit{Pr}(\mathsf{Exec({\cal P}[{{\cal
S}}],v)}=E)$ over the possible runs $E\in\mathit{exec}({\cal P}[{{\cal
S}}],v)$. Similarly, given a run $E$ of the voting system,
$\mathit{Pr}(\mathsf{Res(E)}=\omega)$ denotes the probability that the
election outcome is $\omega\in\Omega$. Note that the social choice function
can be now represented by the probability distribution

$\mathit{Pr}(\mathsf{Res({\cal P}[{{\cal
S}}],v)}=\omega)=\sum_{E\in\mathit{exec}({\cal P}[{{\cal
S}}],v)}\mathit{Pr}(\mathsf{Exec({\cal P}[{{\cal
S}}],v)}=E)\cdot\mathit{Pr}(\mathsf{Res(E)}=\omega).$

Deterministic social choice functions amount to randomized functions that put
all their mass on a single $\omega\in\Omega$.

For instance, in a two-candidate plurality contest with ties broken at random,
the set of outcomes can be defined as $\Omega=\\{a,b\\}$ with $a$ standing for
“Alice wins” and $b$ for “Bob wins.” If the election input $v\in\mathit{In}$
contains more votes for Alice than for Bob, then
$\mathit{Pr}(\mathsf{Res({\cal P}[{{\cal S}}],v)}=a)=1$ and
$\mathit{Pr}(\mathsf{Res({\cal P}[{{\cal S}}],v)}=b)=0$. If $v$ contains more
votes for Bob than for Alice, then $\mathit{Pr}(\mathsf{Res({\cal P}[{{\cal
S}}],v)}=a)=0$ and $\mathit{Pr}(\mathsf{Res({\cal P}[{{\cal S}}],v)}=b)=1$. If
$v$ has the same number of votes for Alice and Bob, then
$\mathit{Pr}(\mathsf{Res({\cal P}[{{\cal
S}}],v)}=a)=\mathit{Pr}(\mathsf{Res({\cal P}[{{\cal S}}],v)}=b)=\frac{1}{2}$.

If an election produces outcome $\omega$ that has probability zero, that is,
if $\mathit{Pr}(\mathsf{Res({\cal P}[{{\cal S}}],v)}=\omega)=0$, then the
outcome is presumptively incorrect.666Recall that the set of outcomes is
assumed to be finite. For a single election, if $\mathit{Pr}(\mathsf{Res({\cal
P}[{{\cal S}}],v)}=\omega)>0$, we cannot tell whether ${\cal P}[{{\cal S}}]$
assigns the _correct_ probability to $\omega$: that would require replicating
the execution. Hence, we consider an outcome $\omega$ to be _admissible_ for
${\cal P}[{{\cal S}}]$ and $v$ if the probability of that outcome is strictly
positive, that is, if $\mathit{Pr}(\mathsf{Res({\cal P}[{{\cal
S}}],v)}=\omega)>0$ (the outcome is expected to occur sometimes for that vote
profile and that social choice function). We denote the set of such outcomes
by $\mathcal{W}_{{\cal P}[{{\cal S}}],v}$.

Attack and Defense Strategies. We model the interplay between threats
(regardless of their cause) and mitigations as the election unfolds by means
of two _strategies_ that play against each other: an _attack strategy_ and a
_defense strategy_.

An _attack strategy_ $f$ interferes with the ideal operation of the election
by changing the “software” of the election system. (Recall that we use the
term “software” abstractly, to denote those things under consideration that
might behave incorrectly, which might include more than computer code,
depending on context.) Each $f$ amounts to a (possibly randomized) plan that
specifies the action that the attacker will take if a given circumstance
occurs. It involves the vulnerabilities and failure modes of the overall
election, and represents how outcomes and evidence might be altered by
failures or adversarial attacks. The involved software mutations are drawn
from $m({\cal P}[{{\cal S}}])$. The input $v$ is the set of “true” votes of
the eligible voters.

We denote the set of _feasible attack strategies_ by $\mathcal{F}_{m({\cal
P}[{{\cal S}}])}$. Note that such strategies may have to satisfy some
constraints. For instance, it might not be computationally feasible to fake a
ZKP. Or it might not be possible to alter marks on paper ballots undetectably,
to steal a ballot box and its contents undetectably, or to corrupt a
multipartisan group of auditors into faking audit results.

A _defense strategy_ $g$ conducts tests and countermeasures to judge whether
the announced outcome of the election is correct. Each $g$ amounts to a
(possibly randomized) conditional plan that specifies the actions the defender
will take in a given set of circumstances. Defense strategies consist of
actions that the “checkers” (elections officials, auditors, public, etc.) can
take before, during, and after the election to try to ensure that the outcome
is correct, and to assess whether the outcome is correct, despite the fact
that things might have gone wrong—that is, despite $f$. Clearly, they can have
random elements, such as statistical audits. Given an election run $E$,
$\mathit{Pr}(\mathsf{Aud(g,E)}=AJ)$ is the probability that the defense
strategy $g$ returns audit judgment $AJ\in\\{T,F\\}$ on $E$. The set of
possible defense strategies based on audit methods $\mathcal{A}$ is denoted by
$\mathcal{G}_{\mathcal{A}}$ The set $\mathcal{G}_{\mathcal{A}}$ is fixed after
$\mathcal{F}_{m({\cal P}[{{\cal S}}])}$ is known, but before the apparent
outcome $\omega$ is known, and without knowledge of $f$. That is, methods for
assessing the outcome may depend on the kind of evidence the system generates,
the ways the ideal evidence might be corrupted, and the execution trace $E$,
including reported tallies and outcomes. The strategies in
$\mathcal{G}_{\mathcal{A}}$ must satisfy legal and practical constraints, as
discussed above.

Both $f$ and $g$ are “interactive,” in the sense that the actions taken under
a particular $g$ can depend on circumstances generated by the actions under
$f$, and _vice versa_ , as well as on random elements. The defense strategy is
restricted to the “audits”; the attacker has no influence on audits other than
through ${\cal S}$.

Execution Semantics for Strategies. The choice of attack ($f$) and defense
($g$) strategies determine how probable different election runs are, which in
turn affects the chance that the audit identifies incorrect outcomes. We model
this through the probability distribution $\mathit{Pr}(\mathsf{Exec({\cal
P}[{{\cal S},f}],v)}=E)$ on the set of system executions, for system software
${\cal S}$, attack strategy $f$, and input votes $v$. For any given $g$, this
induces a probability distribution on the audit decisions $\mathsf{Aud(g,E)}$.
Now,

$\displaystyle\mathit{Pr}(\mathsf{Aud(f,g,v)}=AJ\mid\mathcal{W})=$
$\displaystyle\sum_{\omega\in\mathcal{W}}\ \sum_{E\in\mathit{exec}({\cal
P}[{{\cal S},f}],v)}\ \mathit{Pr}(\mathsf{Exec({\cal P}[{{\cal
S},f}],v)}=E)\cdot\mathit{Pr}(\mathsf{Res(E)}=\omega)\cdot\mathit{Pr}(\mathsf{Aud(g,E)}=AJ)$

denotes the probability that the announced outcome will be accepted (for
$AJ=T$) or rejected (for $AJ=F$), given that the announced outcome is in
$\mathcal{W}$.

As in Section 3, we take $v$ to be fixed when defining software independence
of a particular _election_. Moreover, we are interested in
$\mathcal{W}=\\{\omega\\}$, where $\omega$ is the outcome that has been
announced. In defining software independence of an _election system_ , we
quantify over the possible election inputs $v\in\mathit{In}$, and do not
condition on $\mathcal{W}=\\{\omega\\}$.

###  4.2 Game-Theoretic Definition of SI

We will cast software independence in terms of a game, in a manner analogous
to how semantic security of cryptographic algorithms is captured, or to how
estimation problems are formalized in statistical decision theory. An election
is seen as a strictly competitive game between the adversary choosing an
attack strategy $f\in\mathcal{F}_{m({\cal P}[{{\cal S}}])}$ and the checker
choosing a defense strategy $g\in\mathcal{G}_{\mathcal{A}}$. The payoffs of
the checker are multicriterial (and thus only partially ordered), and given by
the respective probabilities of false positive and false negative output of
the audit procedure. The solution concept is based on _minimax_ , i.e., the
checker minimizes the loss assuming the worst case (most damaging) of the
adversary. (Since the payoff is multicriterial, there is no minimax strategy
_sensu stricto_ , but the analysis is worst-case.) Moreover, the adversary is
assumed to adapt the attack strategy $f$ to the defense strategy $g$ selected
by the checker. On the other hand, the checker must choose the defense
strategy without knowing the attack strategy.

Formally, given a defense strategy $g\in\mathcal{G}_{\mathcal{A}}$, an
election input $v\in\mathit{In}$, and a set of admissible election outcomes
$\mathcal{W}_{{\cal P}[{{\cal S}}],v}$, we define two kinds of costs that the
checker wants to minimize:

$\displaystyle\epsilon(g,v)$ $\displaystyle=$
$\displaystyle\sup_{f\in\mathcal{F}_{m({\cal P}[{{\cal
S}}])}}\mathit{Pr}(\mathsf{Aud(f,g,v)}=F\mid\mathcal{W}_{{\cal P}[{{\cal
S}}],v}),$ $\displaystyle\delta(g,v)$ $\displaystyle=$
$\displaystyle\sup_{f\in\mathcal{F}_{m({\cal P}[{{\cal
S}}])}}\mathit{Pr}(\mathsf{Aud(f,g,v)}=T\mid\overline{\mathcal{W}}_{{\cal
P}[{{\cal S}}],v})$ $\displaystyle=$ $\displaystyle
1-\inf_{f\in\mathcal{F}_{m({\cal P}[{{\cal
S}}])}}\mathit{Pr}(\mathsf{Aud(f,g,v)}=F\mid\overline{\mathcal{W}}_{{\cal
P}[{{\cal S}}],v}).$

That is, $\epsilon$ is the largest chance that the checker rejects an
admissible outcome (_false negative_), and $\delta$ is the largest chance that
he fails to reject an inadmissible outcome (_false positive_).

######  Definition 1 ($(\epsilon,\delta)$-SI)

Consider an election where $v$ was the actual input and $g$ the used defense
strategy. The election is _$(\epsilon_{0},\delta_{0})$ -software independent_
if $\epsilon(g,v)\leq\epsilon_{0}$ and $\delta(g,v)\leq\delta_{0}$, i.e., the
probability of false negative is bounded by $\epsilon_{0}$, and the
probability of false positive is bounded by $\delta_{0}$.

Moreover, the _voting system_ is $(\epsilon_{0},\delta_{0})$-software
independent if there exists $g\in\mathcal{G}_{\mathcal{A}}$ such that for all
$v\in\mathit{In}$, the resulting election is $(\epsilon_{0},\delta_{0})$-SI.

Ideally, elections should be fully reliable. This motivates the following
definition.

######  Definition 2 (Strict SI)

An election (respectively, voting system) is _strictly software independent_
if it is $(0,0)$-software independent.

Unfortunately, strict SI might be hard to achieve in realistic scenarios. In
that case, we should at least require that the defense strategy is more
effective than random guessing. Suppose that the checker tosses a biased coin
(independently of all other election processes) that has probability $p$ of
landing heads, and then rejects the announced outcome if the coin lands heads
and accepts the outcome if the coin lands tails. That rule $g_{p}$ attains
$\epsilon(g_{p},v)=p$ and $\delta(g,v)=1-p$, so
$\epsilon(g_{p},v)+\delta(g_{p},v)=1$. By using the available evidence one
should be able to do better. This leads to the following definition:

######  Definition 3 (loose SI)

An election (respectively, voting system) is _loosely software independent_ if
it is $(\epsilon,\delta)$-software independent with $\epsilon+\delta<1$.

For example, consider a voting system based on hand-marked paper ballots kept
secure and trustworthy, with trustworthy eligibility determinations, subject
to a risk-limiting audit with risk limit $\alpha<1$. Such a voting system is
$(0,\alpha)$-SI and loosely SI. If there were an automatic recount instead of
a risk-limiting audit, the system would be strictly SI.

##  5 Conclusions

We have presented several formalisations of the notion of software
independence. In doing so we have shown that, like many security properties,
this seemingly simple and intuitive notion actually harbours many subtleties.
For example we observe that it is important to exclude trivial systems that
simply reject all runs of an election. The original definition clearly
intended this but did not explicitly require it. Many of the terms used in the
definition require precise definition. For example, “detection” should not
just mean claiming to have observed a departure from correct behaviour but
also to be able to provide evidence that such a departure did indeed occur.
This is related the notion of dispute resolution: the ability of a third party
to be able to determine whether alarm is genuine or false.

We have enriched our definitions to allow for non-determinism or randomisation
in the execution of the protocols, and in particular in the social choice
function. Further, we have argued that purely possibilistic definition is not
necessarily that useful, rather one should extend that definition to account
for the probabilities of detecting erroneous behaviour.

Another insight from our formalisation is the need to precisely define when is
meant by the “system” and the “software”. By the latter we mean those parts of
the system on whose behaviour we do not want the correctness of the outcome to
depend. However, for many systems this will not include all the software of
the system, for example, the auditing components and procedures may require
software and we typically assume that such software is correct with respect to
its specification. Such assumptions can typically be justified by arguing that
auditing algorithms can typically be rerun on independent implementations, so
corruption of an instance of this software is itself detectable.

In future work we plan to apply our definitions to a representative sample of
verifiable voting systems. We also plan to generalise the notion of software
independence to include other components of the system: hardware, people,
procedures etc. This brings us back to the question of defining the boundaries
of the sub-system that we require the correctness of the outcome to be
independent.

### Acknowledgements

Peter Y.A. Ryan would like to thank the FNR (Fond Nationale de Research
Luxembourg) and the Velux Foundation for support during his sabbatical and to
ITU Copenhagen for hosting him when this work was initiated. Steve Schneider
is grateful to EPSRC for funding through the VOLT project EP/P031811/1.
Wojciech Jamroga acknowledges the support of the National Centre for Research
and Development, Poland (NCBR), and the FNR Luxembourg under the PolLux/FNR-
CORE projects VoteVerif (POLLUX-IV/1/2016) and STV (POLLUX-VII/1/2019).

## References

  * [ADS20] A.W. Appel, R. DeMillo, and P.B. Stark.  Ballot-marking devices cannot assure the will of the voters.  Election Law Journal, Rules, Politics, and Policy, 19(3), 2020.
  * [AS20] A.W. Appel and P.B. Stark.  Evidence-based elections: Create a meaningful paper trail, then audit.  Georgetown Law Technology Review, 4.2:523–541, 2020.  https://georgetownlawtechreview.org/wp-content/uploads/2020/07/4.2-p523-541-Appel-Stark.pdf.
  * [BHR+17] M. Bernhard, J.A. Halderman, R.L. Rivest, P. Vora, P.Y.A. Ryan, V. Teague, J. Benaloh, P.B. Stark, and D. Wallach.  Public evidence from secret ballots.  In R. Krimmer, M. Volkamer, N. Braun Binder, N Kersting, O. Pereira, and C. Schürmann, editors, Electronic Voting. E-Vote-ID 2017. Lecture Notes in Computer Science, 10615. Springer, 2017.
  * [BMM+20] Matthew Bernhard, Allison McDonald, Henry Meng, Jensen Hwa, Nakul Bajaj, Kevin Chang, and J. Alex Halderman.  Can voters detect malicious manipulation of ballot marking devices?  In 2020 IEEE Symposium on Security and Privacy (SP), pages 679–694, 2020.
  * [BRR+15] Josh Benaloh, Ronald Rivest, Peter YA Ryan, Philip Stark, Vanessa Teague, and Poorvi Vora.  End-to-end verifiability, 2015.  arXiv:1504.03778.
  * [DKM18] R. DeMillo, R. Kadel, and M. Marks.  What voters are asked to verify affects ballot verification: A quantitative analysis of voters’ memories of their ballots.  Technical report, 2018.
  * [Ele21] Election Assistance Commission.  Voluntary voting system guidelines VVSG 2.0, 2021.  https://www.eac.gov/sites/default/files/TestingCertification/ Voluntary_Voting_System_Guidelines_Version_2_0.pdf.
  * [Eve07] S.P. Everett.  The Usability of Electronic Voting Machines and How Votes Can Be Changed Without Detection.  PhD thesis, Rice University, 2007.
  * [HI21] A.A. Haynes and M.V. Hood III.  Georgia voter verification study.  Technical report, 2021.
  * [HR16] Feng Hao and Peter Y. A. Ryan.  Real-World Electronic Voting: Design, Analysis and Deployment.  Auerbach Publications, USA, 1st edition, 2016.
  * [KTV11] Ralf Küsters, Tomasz Truderung, and Andreas Vogt.  Verifiability, privacy, and coercion-resistance: New insights from a case study.  In 32nd IEEE Symposium on Security and Privacy, pages 538–553, 2011\.
  * [Riv08] R.L. Rivest.  On the notion of “software independence” in voting systems.  Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences, 366(1881):3759–3767, 2008.
  * [RW06] R.L. Rivest and J.P. Wack.  On the notion of “software independence” in voting systems (draft version of July 28, 2006).  Technical report, Information Technology Laboratory, National Institute of Standards and Technology, 2006.
  * [Sta08] P.B. Stark.  Conservative statistical post-election audits.  Annals of Applied Statistics, 2008.
  * [SW12] P.B. Stark and D.A. Wagner.  Evidence-based elections.  IEEE Security and Privacy, 10:33–41, 2012.


# On Noisy Network Coding for a Gaussian Relay Chain Network with Correlated
Noises

Lei Zhou and Wei Yu
Department of Electrical and Computer Engineering,
University of Toronto, Toronto, Ontario M5S 3G4, Canada
emails: {zhoulei<EMAIL_ADDRESS>
###### Abstract

Noisy network coding, which elegantly combines the conventional compress-and-
forward relaying strategy and ideas from network coding, has recently drawn
much attention for its simplicity and optimality in achieving to within
constant gap of the capacity of the multisource multicast Gaussian network.
The constant-gap result, however, applies only to Gaussian relay networks with
independent noises. This paper investigates the application of noisy network
coding to networks with correlated noises. By focusing on a four-node Gaussian
relay chain network with a particular noise correlation structure, it is shown
that noisy network coding can no longer achieve to within constant gap to
capacity with the choice of Gaussian inputs and Gaussian quantization. The
cut-set bound of the relay chain network in this particular case, however, can
be achieved to within half a bit by a simple concatenation of a correlation-
aware noisy network coding strategy and a decode-and-forward scheme.

##  I Introduction

The capacity region of the Gaussian relay network has been open for decades.
Recently, the capacities of several relay networks with simple structures have
been approximated to within constant number of bits. For example, for the
three-node Gaussian relay channel, Avestimehr and Tse [1] showed that the
decode-and-forward strategy achieves to within half a bit of the capacity;
Chang, Chung, and Lee [2] proved that the compress-and-forward rate is within
half a bit of the capacity, and the amplify-and-forward rate is within one
bit.

In their breakthrough work, Avestimehr and Tse [1] further showed that, the
capacity of the single-source single-destination Gaussian relay network in
general can be achieved to within constant bits via a universal relaying
scheme called quantize-map-and-forward (QMF). They also showed that, the gap
to capacity is only related to the number of nodes in the network.

Parallel to Avestimehr and Tse’s work, Lim, Kim, El Gamal, and Chung [3]
proposed a noisy network coding strategy that naturally extends the
conventional compress-and-forward scheme of Cover and El Gamal [4] and the
classic network coding by Ahlswede, Cai, Li, and Yeung [5] to noisy networks.
The main idea of noisy network coding is to derive an explicit expression of
the achievable rate for each cut-set of the network. Then, by comparing with
the cut-set upper bound, noisy network coding can be shown to achieve to
within constant gap to the capacity of general multisource multicast Gaussian
networks.

A key assumption made in both [1] and [3] is that the noises in the Gaussian
relay network are independent with each other. This assumption may not hold in
practical systems, where common interferences from other sources play a role.
In this paper, we are interested in the following question. In the context of
Gaussian relay networks with correlated noises, can noisy network coding
achieve within constant bits to the capacity as well? This paper gives a
negative answer by studying a four-node Gaussian chain network with correlated
noises. It is shown that, in a certain scenario, the noisy-network-coding rate
(with Gaussian input and Gaussian quantization) has an unbounded gap to the
cut-set bound, whereas a concatenation of a modified correlation-aware noisy
network coding strategy and a conventional decode-and-forward scheme achieves
to within half a bit of the cut-set bound in this specific case.

##  II Channel Model

Figure 1: A four-node Gaussian relay chain network

The four-node Gaussian relay chain, as depicted in Fig. 1, consists of a
source node, a destination node, and two relay nodes. The source communicates
with the destination with the help from the two relays in between. Information
passes from the source to the neighboring relay, and to the next, then finally
to the destination. The input-output relationship can be described as follows:

$\displaystyle Y_{1}$ $\displaystyle=$ $\displaystyle h_{1}X+Z_{1},$
$\displaystyle Y_{2}$ $\displaystyle=$ $\displaystyle h_{2}X_{1}+Z_{2},$
$\displaystyle Y_{3}$ $\displaystyle=$ $\displaystyle h_{3}X_{2}+Z_{3}.$

Without loss of generality, assume that the transmit power of all nodes are
normalized to one, and the variances of the receiver noises are also
normalized to one, i.e., $Z_{i}\sim\mathcal{N}(0,1)$. The receiver noises are
i.i.d. in time, but the noises $[Z_{1},Z_{2},Z_{3}]$ are correlated with the
following correlation matrix:

$K_{Z}=\left[\begin{array}[]{ccc}1&\rho_{12}&\rho_{13}\\\
\rho_{12}&1&\rho_{23}\\\ \rho_{13}&\rho_{23}&1\end{array}\right],$

where $K_{z}$ is positive semidefinite and $\rho_{ij}$ is the correlation
coefficient between $Z_{i}$ and $Z_{j}$. Note that the relay operation must be
causal in time.

##  III Suboptimality of the Noisy Network Coding

We begin by showing that using noisy network coding with the choices of
Gaussian inputs and Gaussian quantization noises, the gap between the
achievable rate and the cut-set bound can be unbounded for a Gaussian relay
chain network with a certain noise correlation structure. First, an upper
bound to the cut-set bound of the four-node relay chain can be computed as
follows:

$\displaystyle\max_{p(x,x_{1},x_{2})}\min\\{I(X;Y_{1}Y_{2}Y_{3}|X_{1}X_{2}),I(XX_{1};Y_{2}Y_{3}|X_{2}),$
(1) $\displaystyle\quad\quad\quad
I(XX_{1}X_{2};Y_{3}),I(XX_{2};Y_{1}Y_{3}|X_{1})\\}$ $\displaystyle\leq$
$\displaystyle\min\\{\max I(X;Y_{1}Y_{2}Y_{3}|X_{1}X_{2}),\max
I(XX_{1};Y_{2}Y_{3}|X_{2}),$ $\displaystyle\quad\quad\;\max
I(XX_{1}X_{2};Y_{3}),\max I(XX_{2};Y_{1}Y_{3}|X_{1})\\}$ $\displaystyle=$
$\displaystyle\min\\{\overline{C}(\mathcal{S}_{1}),\overline{C}(\mathcal{S}_{2}),\overline{C}(\mathcal{S}_{3}),\overline{C}(\mathcal{S}_{4})\\}$
$\displaystyle\triangleq$ $\displaystyle\overline{C}$

where the cut-sets are defined as $\mathcal{S}_{1}=\\{X\\}$,
$\mathcal{S}_{2}=\\{X,X_{1}\\}$, $\mathcal{S}_{3}=\\{X,X_{1},X_{2}\\}$, and
$\mathcal{S}_{4}=\\{X,X_{2}\\}$, and $\overline{C}(\mathcal{S}_{i}),i=1,2,3,4$
are the four cut-set upper bounds, which can be calculated as

$\displaystyle\overline{C}(\mathcal{S}_{1})$ $\displaystyle=$
$\displaystyle\max I(X;Y_{1}Y_{2}Y_{3}|X_{1}X_{2})$ (2) $\displaystyle=$
$\displaystyle\frac{1}{2}\log\left(1+\frac{(1-\rho_{23}^{2})h_{1}^{2}}{|K_{Z}|}\right),$

and

$\displaystyle\overline{C}(\mathcal{S}_{2})$ $\displaystyle=$
$\displaystyle\max I(XX_{1};Y_{2}Y_{3}|X_{2})$ (3) $\displaystyle=$
$\displaystyle\frac{1}{2}\log\left(1+\frac{h_{2}^{2}}{1-\rho_{23}^{2}}\right),$

and

$\displaystyle\overline{C}(\mathcal{S}_{3})$ $\displaystyle=$
$\displaystyle\max I(XX_{1}X_{2};Y_{3})$ (4) $\displaystyle=$
$\displaystyle\frac{1}{2}\log(1+h_{3}^{2}),$

and

$\displaystyle\overline{C}(S_{4})$ $\displaystyle=$ $\displaystyle\max
I(XX_{2};Y_{1}Y_{3}|X_{1})$ (5) $\displaystyle=$
$\displaystyle\frac{1}{2}\log\left(1+\frac{h_{1}^{2}+h_{3}^{2}+h_{1}^{2}h_{3}^{2}}{1-\rho_{13}^{2}}\right)$
$\displaystyle\geq$ $\displaystyle\overline{C}(\mathcal{S}_{3}),$

which is redundant.

The main point of noisy network coding is that an achievable rate can be
derived for each of the cut-sets $\mathcal{S}_{1}$, $\mathcal{S}_{2}$, and
$\mathcal{S}_{3}$ using a generalization of the compress-and-forward scheme.
For convenience, we state the achievable rates as follows.

######  Theorem 1 (Noisy Network Coding Theorem [3]).

Let $\mathcal{D}=\mathcal{D}_{1}=\mathcal{D}_{2}=\cdots=\mathcal{D}_{N}$. A
rate tuple $(R_{1},\cdots,R_{N})$ is achievable for the DMN $p(y^{N}|x^{N})$
if there exists some joint pmf
$p(q)\prod_{k=1}^{N}p(x_{k}|q)p(\hat{y}_{k}|y_{k},x_{k},q)$ such that

$\displaystyle R(\mathcal{S})$ $\displaystyle<$
$\displaystyle\min_{d\in\mathcal{\mathcal{S}}^{c}\cap\mathcal{D}}I(X(\mathcal{S});\hat{Y}(\mathcal{S}^{c}),Y_{d}|X(\mathcal{S}^{c}),Q)$
(6)
$\displaystyle\quad-I(Y(\mathcal{S});\hat{Y}(\mathcal{S})|X^{N},\hat{Y}(\mathcal{S}^{c}),Y_{d},Q)$

for all cutsets $\mathcal{S}\subseteq[1:N]$ with
$S^{c}\cap\mathcal{D}\neq\emptyset$, where
$R(\mathcal{S})=\sum_{k\in\mathcal{\mathcal{S}}}R_{k}$.

Although the quantization in the above noisy network coding theorem can in
theory have arbitrary distributions, Gaussian inputs and Gaussian quantization
noises are usually adopted for Gaussian networks [Wang_ReceiverCooperation]
[6], and are shown to achieve constant gap to capacity for networks with
uncorrelated noises [3]. Thus, this paper follows the same choice, i.e.,

$\displaystyle\hat{Y}_{i}=Y_{i}+\hat{Z}_{i}$ (7)

where the quantization noise $\hat{Z}_{i}\sim\mathcal{N}(0,\mathsf{q}_{i})$ is
independent with everything else. Now applying the noisy network coding
theorem with Gaussian inputs and Gaussian quantization noises, the following
achievable rates for cut-sets $\mathcal{S}_{1}$, $\mathcal{S}_{2}$, and
$\mathcal{S}_{3}$ can be derived:

$\displaystyle R(\mathcal{S}_{1})$ $\displaystyle=$ $\displaystyle
I(X;\hat{Y}_{1}\hat{Y}_{2}Y_{3}|X_{1}X_{2})$ (14) $\displaystyle=$
$\displaystyle h\left(\begin{array}[]{r}h_{1}X+Z_{1}+\hat{Z}_{1}\\\
Z_{2}+\hat{Z}_{2}\\\
Z_{3}\end{array}\right)-h\left(\begin{array}[]{r}Z_{1}+\hat{Z}_{1}\\\
Z_{2}+\hat{Z}_{2}\\\ Z_{3}\end{array}\right)$ $\displaystyle=$
$\displaystyle\frac{1}{2}\log\left(1+\frac{(1+\mathsf{q}_{2}-\rho_{23}^{2})h_{1}^{2}}{|K_{\beta}|}\right),$
(15)

where

$|K_{\beta}|=\left|\begin{array}[]{ccc}1+\mathsf{q}_{1}&\rho_{12}&\rho_{13}\\\
\rho_{12}&1+\mathsf{q}_{2}&\rho_{23}\\\
\rho_{13}&\rho_{23}&1\end{array}\right|,$ (16)

and

$\displaystyle R(\mathcal{S}_{2})$ $\displaystyle=$ $\displaystyle
I(XX_{1};\hat{Y_{2}}Y_{3}|X_{2})-I(Y_{1};\hat{Y}_{1}|XX_{1}X_{2}\hat{Y}_{2}Y_{3})$
(17) $\displaystyle=$
$\displaystyle\frac{1}{2}\log\left(1+\frac{h_{2}^{2}}{1+\mathsf{q}_{2}-\rho_{23}^{2}}\right)$
$\displaystyle\qquad-\frac{1}{2}\log\left(1+\frac{1-\rho_{13}^{2}}{\mathsf{q}_{1}}\right).$

and

$\displaystyle R(\mathcal{S}_{3})$ $\displaystyle=$ $\displaystyle
I(XX_{1}X_{2};Y_{3})-I(Y_{1}Y_{2};\hat{Y}_{1}\hat{Y}_{2}|XX_{1}X_{2}Y_{3})$
(20) $\displaystyle=$ $\displaystyle\frac{1}{2}\log(1+h_{3}^{2})$
$\displaystyle-\frac{1}{2}\log\frac{\left|\begin{array}[]{cc}1-\rho_{13}^{2}+\mathsf{q}_{1}&\rho_{12}-\rho_{13}\rho_{23}\\\
\rho_{12}-\rho_{13}\rho_{23}&1-\rho_{23}^{2}+\mathsf{q}_{2}\end{array}\right|}{\mathsf{q}_{1}\mathsf{q}_{2}}.$

The achievable rate is then upper bounded by the minimum of the three:

$R\leq\min\\{R(\mathcal{S}_{1}),R(\mathcal{S}_{2}),R(\mathcal{S}_{3})\\}.$
(21)

Now, consider a special scenario when the noise $Z_{3}$ is independent with
both $Z_{1}$ and $Z_{2}$, and channel strengths $h_{2}^{2}$ and $h_{3}^{2}$
scale with $h_{1}^{2}$, i.e.,

$\rho_{13}=\rho_{23}=0,$ (22)

and

$h_{2}^{2}=h_{3}^{2}=\frac{h_{1}^{2}}{1-\rho_{12}^{2}}.$ (23)

This special setting gives us the following cut-set bounds:

$\overline{C}(\mathcal{S}_{1})=\overline{C}(\mathcal{S}_{2})=\overline{C}(\mathcal{S}_{3})=\frac{1}{2}\log\left(1+\frac{h_{1}^{2}}{1-\rho_{12}^{2}}\right),$
(24)

and the following achievable rates for cut-sets $\mathcal{S}_{1}$ to
$\mathcal{S}_{3}$:

$\displaystyle R(\mathcal{S}_{1})$ $\displaystyle=$
$\displaystyle\frac{1}{2}\log\left(1+\frac{h_{1}^{2}}{1+\mathsf{q}_{1}-\frac{\rho_{12}^{2}}{1+\mathsf{q}_{2}}}\right),$
$\displaystyle R(\mathcal{S}_{2})$ $\displaystyle=$
$\displaystyle\frac{1}{2}\log\left(1+\frac{h_{1}^{2}}{(1-\rho_{12}^{2})(1+\mathsf{q}_{2})}\right)$
$\displaystyle-\frac{1}{2}\log\left(1+\frac{1}{\mathsf{q}_{1}}\right),$
$\displaystyle R(\mathcal{S}_{3})$ $\displaystyle=$
$\displaystyle\frac{1}{2}\log\left(1+\frac{h_{1}^{2}}{1-\rho_{12}^{2}}\right)$
$\displaystyle-\frac{1}{2}\log\left(1+\frac{\mathsf{q}_{1}+\mathsf{q}_{2}+1-\rho_{12}^{2}}{\mathsf{q}_{1}\mathsf{q}_{2}}\right).$

Next, we show that, the gaps
$\overline{C}(\mathcal{S}_{1})-R(\mathcal{S}_{1})$,
$\overline{C}(\mathcal{S}_{2})-R(\mathcal{S}_{2})$,
$\overline{C}(\mathcal{S}_{3})-R(\mathcal{S}_{3})$ cannot be made all finite
when $\rho_{12}^{2}\rightarrow 1$. First, the gap on the cut-set
$\mathcal{S}_{1}$ is given by

$\displaystyle\Delta(\mathcal{S}_{1})$ $\displaystyle=$
$\displaystyle\overline{C}(\mathcal{S}_{1})-R(\mathcal{S}_{1})$ (25)
$\displaystyle=$
$\displaystyle\frac{1}{2}\log\left(1+\frac{h_{1}^{2}}{1-\rho_{12}^{2}}\right)$
$\displaystyle-\frac{1}{2}\log\left(1+\frac{h_{1}^{2}}{1+\mathsf{q}_{1}-\frac{\rho_{12}^{2}}{1+\mathsf{q}_{2}}}\right),$

and the gap on the cut-set $\mathcal{S}_{2}$ is lower bounded by

$\displaystyle\Delta(\mathcal{S}_{2})$ $\displaystyle=$
$\displaystyle\overline{C}(\mathcal{S}_{2})-R(\mathcal{S}_{2})$ (26)
$\displaystyle=$
$\displaystyle\frac{1}{2}\log\left(1+\frac{h_{1}^{2}}{1-\rho_{12}^{2}}\right)+\frac{1}{2}\log\left(1+\frac{1}{\mathsf{q}_{1}}\right)$
$\displaystyle-\frac{1}{2}\log\left(1+\frac{h_{1}^{2}}{(1-\rho_{12}^{2})(1+\mathsf{q}_{2})}\right)$
$\displaystyle\geq$
$\displaystyle\frac{1}{2}\log\left(1+\frac{1}{\mathsf{q}_{1}}\right),$

and the gap on the cut-set $\mathcal{S}_{3}$ is lower bounded by the same
number as well, i.e.,

$\displaystyle\Delta(\mathcal{S}_{3})$ $\displaystyle=$
$\displaystyle\overline{C}(\mathcal{S}_{3})-R(\mathcal{S}_{3})$ (27)
$\displaystyle=$
$\displaystyle\frac{1}{2}\log\left(1+\frac{\mathsf{q}_{1}+\mathsf{q}_{2}+1-\rho_{12}^{2}}{\mathsf{q}_{1}\mathsf{q}_{2}}\right)$
$\displaystyle\geq$
$\displaystyle\frac{1}{2}\log\left(1+\frac{1}{\mathsf{q}_{1}}\right).$

Now, since

$\overline{C}-R\geq\max\\{\Delta(\mathcal{S}_{1}),\Delta(\mathcal{S}_{2}),\Delta(\mathcal{S}_{3})\\},$
(28)

in order to make $\overline{C}-R$ finite, all three gaps have to be upper
bounded by a finite number. Inspecting the gap of $\Delta(\mathcal{S}_{1})$ in
(25), in order to make it finite when $\rho_{12}\rightarrow\infty$, both
$\mathsf{q}_{1}$ and $\mathsf{q}_{2}$ have to go to zero. However, in this
case, $\Delta(\mathcal{S}_{2})$ and $\Delta(\mathcal{S}_{3})$ are apparently
unbounded. Therefore, in the scenario of (22) and (23), as $\rho_{12}^{2}$
goes to $1$, it is impossible to keep all three gaps
$\Delta(\mathcal{S}_{1})$, $\Delta(\mathcal{S}_{2})$, and
$\Delta(\mathcal{S}_{3})$ finite simultaneously. As a consequence, for the
four-node Gaussian chain network with correlated noises, the noisy network
coding achievable rate with the choice of Gaussian inputs and Gaussian
quantization noises has an unbounded gap to the cut-set upper bound.

##  IV An Optimal Concatenated Scheme

It is known that the cut-set upper bound is not always tight for the relay
channel [7, 8], but for the four-node Gaussian chain network, does the cut-set
bound have an infinite gap to capacity? Or, is it the noisy networking coding
achievable rate that has an infinite gap to capacity? To answer this question,
we show in the following that the cut-set bound (24) can actually be achieved
to within half a bit for this four-node relay network with the particular
noise correlation structure (22) by a simple concatenation of a correlation-
aware noisy network coding strategy and a conventional decode-and-forward
scheme. This justifies the suboptimality of the noisy network coding for
Gaussian relay networks with correlated noises.

Inspecting the structure of the four-node relay network in Fig. 1 and the
special correlation structure (22), it is easy to see that the last node is
essentially independent of the first three nodes in this example. Now the
first three nodes (from the source node $X$ to the second relay node $Y_{2}$)
forms a three-node Gaussian relay channel, so we can apply the noisy network
coding theorem just to the first three nodes. With the source message decoded
at $Y_{2}$, the second relay node can then re-encode the source information
and forward to the destination $Y_{3}$. With $Y_{1}$ serving as a noisy-
network-coding type of relay and $Y_{2}$ serving as a decode-and-forward type
of relay, this is essentially a concatenation of the noisy network coding and
the decode-and-forward scheme. The achievable rate of this concatenated scheme
can be derived as follows.

In the first relaying stage where $Y_{1}$ serves as a noisy-network-coding
type of relay, according to the noisy network coding theorem [3, Theorem 1],
$Y_{2}$ can decode the source message if the following rate is satisfied:

$\displaystyle R$ $\displaystyle\leq$
$\displaystyle\min\\{I(X,X_{1};Y_{2})-I(Y_{1};\hat{Y}_{1}|X,X_{1},Y_{2}),$
(29) $\displaystyle\quad\quad\;I(X;Y_{2},\hat{Y}_{1}|X_{1})\\},$

for some distribution

$p(x,x_{1},y_{1},\hat{y}_{1})=p(x)p(x_{1})p(y_{1}|x,x_{1})p(\hat{y}_{1}|x_{1},y_{1}).$

Substituting Gaussian inputs $X\sim\mathcal{N}(0,1)$,
$X_{1}\sim\mathcal{N}(0,1)$, and Gaussian quantization signal
$\hat{Y}_{1}=Y_{1}+\hat{Z}_{1}$, where
$\hat{Z}_{1}\sim\mathcal{N}(0,\mathsf{q}_{1})$ is independent with everything
else, we have the following achievable rate in the first stage:

$\displaystyle R$ $\displaystyle\leq$
$\displaystyle\min\left\\{\frac{1}{2}\log\left(1+\frac{h_{1}^{2}}{1-\rho_{12}^{2}}\right)-\frac{1}{2}\log\left(1+\frac{\mathsf{q}_{1}}{1-\rho_{12}^{2}}\right),\right.$
(30)
$\displaystyle\left.\quad\quad\;\;\frac{1}{2}\log(1+h_{2}^{2})-\frac{1}{2}\log\left(1+\frac{1-\rho_{12}^{2}}{\mathsf{q}_{1}}\right)\right\\}.$

Next, with the source message decoded at $Y_{2}$, the second relay node acts
as a decode-and-forward type of relay, which re-encodes and forwards the
source message to the destination $Y_{3}$ through the Gaussian channel of
channel gain $h_{3}$. The destination can successfully decode the source
message if

$\displaystyle R\leq\frac{1}{2}\log(1+h_{3}^{2}).$ (31)

Combining the above rate constraints (30) and (31) gives us the following
achievable rate by the concatenated scheme:

$\displaystyle R$ $\displaystyle\leq$
$\displaystyle\min\left\\{\frac{1}{2}\log\left(1+\frac{h_{1}^{2}}{1-\rho_{12}^{2}}\right)-\frac{1}{2}\log\left(1+\frac{\mathsf{q}_{1}}{1-\rho_{12}^{2}}\right),\right.$
(32)
$\displaystyle\quad\quad\;\;\frac{1}{2}\log(1+h_{2}^{2})-\frac{1}{2}\log\left(1+\frac{1-\rho_{12}^{2}}{\mathsf{q}_{1}}\right),$
$\displaystyle\quad\quad\;\;\left.\frac{1}{2}\log(1+h_{3}^{2})\right\\}.$

Comparing the above achievable rate with the cut-set upper bound with
$\rho_{12}$ and $\rho_{23}$ set to zero:

$\displaystyle\overline{C}$ $\displaystyle=$
$\displaystyle\min\left\\{\frac{1}{2}\log\left(1+\frac{h_{1}^{2}}{1-\rho_{12}^{2}}\right),\frac{1}{2}\log(1+h_{2}^{2}),\right.$
(33) $\displaystyle\quad\quad\;\;\left.\frac{1}{2}\log(1+h_{3}^{2})\right\\},$

we have the difference upper bounded by

$\overline{C}-R\leq\max\left\\{\frac{1}{2}\log\left(1+\frac{\mathsf{q}_{1}}{1-\rho_{12}^{2}}\right),\frac{1}{2}\log\left(1+\frac{1-\rho_{12}^{2}}{\mathsf{q}_{1}}\right)\right\\}$
(34)

It is easy to see that the first term monotonically increases with
$\mathsf{q}_{1}$ while the second term monotonically decreases. As a result,
to minimize the maximum of the two terms, we need

$\displaystyle\frac{1}{2}\log\left(1+\frac{1-\rho_{12}^{2}}{\mathsf{q}_{1}^{*}}\right)=\frac{1}{2}\log\left(1+\frac{\mathsf{q}_{1}^{*}}{1-\rho_{12}^{2}}\right),$
(35)

which results in the optimal correlation-aware quantization level
$\mathsf{q}_{1}^{*}=1-\rho_{12}^{2}$. Substituting $\mathsf{q}_{1}^{*}$ into
(34) gives us $\overline{C}-R<\frac{1}{2}$. Therefore, for the four-node
Gaussian chain network as shown in Fig. 1, in the scenario where
$\rho_{13}=\rho_{23}=0$, the cut-set upper bound can be achieved to within
constant gap.

Figure 2: Noisy network coding vs. concatenated scheme

Fig. 2 shows a numerical example for comparing noisy network coding and the
concatenated scheme. In the simulation, we let $h_{1}^{2}=20$dB and all other
channel parameters are set to satisfy (22) and (23). For the quantization
parameters, we choose the optimal quantization level
$\mathsf{q}_{1}=1-\rho_{12}^{2}$ and let $\mathsf{q}_{2}=1$. As can be seen
from the figure, when $\rho_{12}$ approaches to $+1$ or $-1$, both the cut-set
upper bound and the achievable rate by the concatenated scheme go to infinity.
However, the achievable rate by the noisy network coding scheme remains
finite, making the gap to the cut-set bound unbounded.

##  V Conclusion

This paper studies the optimality of the noisy network coding for a four-node
Gaussian chain network with correlated noises. It is shown that, under a
certain noise correlation structure, noisy network coding with Gaussian inputs
and Gaussian quantization noises has an infinite gap to the cut-set upper
bound. But, the upper bound can be achieved to within half a bit in this
specific case by a simple concatenation of a correlation-aware noisy network
coding strategy and a decode-and-forward scheme.

## References

  * [1] S. Avestimehr, S. Diggavi, and D. Tse, “Wireless network information flow: a deterministic approach,” _Submitted to IEEE Trans. Inf. Theory_ , 2009.
  * [2] W. Chang, S.-Y. Chung, and Y. H. Lee, “Gaussian relay channel capacity to within a fixed number of bits,” 2010. [Online]. Available: http://arxiv.org/abs/1011.5065
  * [3] S.-Y. Lim, Y.-H. Kim, A. El Gamal, and S.-Y. Chung, “Noisy network coding,” _Submitted to IEEE Trans. Inf. Theory_ , 2010.
  * [4] T. M. Cover and A. El Gamal, “Capacity theorems for the relay channel,” _IEEE Trans. Inf. Theory_ , vol. 25, no. 5, pp. 572–584, Sep. 1979.
  * [5] R. Ahlswede, N. Cai, R. Li, and R. W. Yeung, “Network information flow,” _IEEE Trans. Inf. Theory_ , vol. 46, pp. 1004 –1016, Jul 2000.
  * [6] L. Zhou and W. Yu, “Gaussian z-interference channel with a relay link: achievability region and asymptotic sum capacity,” 2010. [Online]. Available: http://arxiv.org/abs/1006.5087
  * [7] M. Aleksic, P. Razaghi, and W. Yu, “Capacity of a class of modulo-sum relay channels,” _IEEE Trans. Inf. Theory_ , vol. 55, no. 3, pp. 921–930, Mar. 2009.
  * [8] Z. Zhang, “Partial converse for a relay channel,” _IEEE Trans. Inf. Theory_ , vol. 34, no. 5, pp. 1106–1110, Sep. 1988.