# Undoing Causal Effects of a Causal Broadcast Channel with Cooperating
Receivers using Entanglement Resources††thanks: This work was financed by the
DFG via grant NO 1129/2-1.

Stephen DiAdamo, Janis Nötzel  Emmy-Noether Gruppe Theoretisches
Quantensystemdesign
Lehrstuhl für Theoretische Informationstechnik
Technische Universität München
{stephen.diadamo<EMAIL_ADDRESS>
###### Abstract

We analyse a communication scenario over a particular causal broadcast channel
whose state depends on a modulo sum. The receivers of the broadcast receive
channel state information and collaborate to determine the channel state as to
decode their private messages. Further, the receivers of the broadcast can
collude up to the minimum non-collusion condition to determine state
information of the other non-colluding receivers. We analyse three resource
scenarios for the receivers: receivers can share entanglement without
classically communicating, can just use classical communication, or have both
entanglement and classical communication. Using results from secure multi-
party communication, we find that when the receivers can share entanglement
and communicate classically, they can receive messages from the sender at a
non-zero rate with verifiable secure collaboration. In the entanglement only
case a positive capacity is not possible. In the classical communication case,
a non-zero rate of communication is achievable but the communication
complexity overhead grows quadratically in the number of receivers versus
linear in the number of receivers with entanglement.

###### Index Terms:

Modulo summation, causal broadcast channel, secure multi-party computation,
entanglement, quantum networks

##  I Introduction

The use of entanglement resources in classical communication scenarios has
been shown to reduce communication resources [2], increase capacity of
channels [3], and enable communication [4, 5]. Entanglement can moreover be
used to improve upon protocols for secure multi-party computation and
communication [6, 7], allowing parties to compute a common function securely.
In this work, we introduce a communication scenario with a single sender
broadcasting classically encoded messages to $N$ receivers. To decode the
messages, the receivers must cooperate, or conference [8], with one another or
otherwise, because of the channel’s causal properties, the capacity of the
channel vanishes. This scenario mimics one where a sender broadcasts a message
to a collection of receivers such that either all receivers receive the
message or none of them receive it, based on their mutual cooperation.

The channel model in this work has a causal state variable that determines how
the channel transmits the sender’s messages. Specifically “causal” here means
that with each transmission made over the channel, the transmission behaviour
of the channel changes depending on a random state variable. When a message
arrives at the receiver, it is accompanied with a piece of the state
information. The state information is split between the receivers such that
alone, the best the receiver can do is randomly guess the channel state. The
receivers’ task is to cooperate to fairly determine the channel state –
essential for decoding the sender’s message. In the general case, the
receivers can collude with each other in groups to attempt to determine the
channel state unfairly, that is, where the receivers in the colluding group
determine the channel state and the others do not. To overcome this, we apply
secure multi-party protocols that work under a maximum colluding number of
receivers. We investigate protocols under three conferencing resource
scenarios.

The scenarios we consider are: when the receivers are only able to share
entanglement with each other, but are unable to classically communicate;
second, they can classically communicate but not share entanglement; and
lastly when they can both share entanglement and can classically communicate.
In these scenarios, we determine a lower-bound for the communication cost for
performing protocols that allow the receivers to fairly determine the channel
state. We find that with only classical resources, the receivers can perform a
fair and conditionally secure protocol to determine the channel state but at
the expense of additional classical resources compared to the case where they
can in addition share entanglement. We see an overall quadratic reduction of
the communication resources needed when entanglement resources are available
with an addition of provable security.

###  I-A Related Work

In this work we consider a causal broadcast channel communication scenario
with cooperating receivers. In [5], a dual scenario is considered where
instead of a cause broadcast channel, the channel is a causal multiple access
channel with cooperating senders. In that case, the receivers need not
communicate, as shared entanglement is enough to achieve a positive channel
capacity. In [9], a causal broadcast channel with channel state information at
the sender is analysed. In this work, we make use of the multi-party modulo
summation protocols developed in [10] and [11], extending and optimising them
for this this particular communication scenario when $n$ modulo sums are
needed.

###  I-B Summary of Contributions

We propose a communication model with a sender and many receivers that can be
used to ensure that either all receivers receive their message with certainty
if they cooperate or otherwise none of them receive their message. We use
protocols developed in [10, 11] to develop a scheme that is fair and secure
such that all receivers can decode messages from the sender fairly when the
protocols run honestly, even when some receivers collude. We consider the
trade-offs for allowing the receivers to share classical and quantum
resources, and find when the receivers can share entanglement and can
broadcast messages, they can verifiably securely perform the multi-party
computation needed to determine the channel state which encrypts each
transmission from the sender. We determine the communication complexity for
each case where communication is possible.

###  I-C Notation

Given a finite alphabet $\mathbf{X}$, the set of probability distributions on
it is $\mathcal{P}(\mathbf{X})$. The corresponding state space for quantum
systems on a finite dimensional Hilbert space $\mathcal{H}$ is denoted
$\mathcal{S}(\mathcal{H})$. The $n$-fold composition
$\mathbf{X}\times\ldots\times\mathbf{X}$ is written $\mathbf{X}^{n}$. A
classical channel $W$ with input alphabet $\mathbf{X}$ and output alphabet
$\mathbf{Y}$ is defined by a matrix $(w(y|x))_{x\in\mathbf{X},y\in\mathbf{Y}}$
where $w(\cdot|x)\in\mathcal{P}(\mathbf{Y})$ for all $x\in\mathbf{X}$. The set
of all such channels is denoted $C(\mathbf{X},\mathbf{Y})$. Specific channels
using in this work are: The identity map on $x\in\\{0,1\\}$, defined by
$\mathbbm{1}(x)=x$, the bit-flip on $\mathbbm{F}$ as $\mathbbm{F}(x)=x\oplus
1$, and the binary symmetric channel (BSC) with parameter $\nu\in[0,1]$
defined as $BSC(\nu)\coloneqq\nu\mathbbm{1}+(1-\nu)\mathbbm{F}.$ The entropy
of $p\in\mathcal{P}(\mathbf{X})$ is
$H(p)\coloneqq-\sum_{x\in\mathbf{X}}p(x)\log(x)$, ($\log$ being calculated
with base $2$ and using the convention $0\log(0)=0$). The mutual information
of $p\in\mathcal{P}(\mathbf{X})$ and $W\in C(\mathbf{X},\mathbf{Y})$ is
$I(p;W)\coloneqq H(p)+H(Wp)-H((W,p))$. Distribution $\pi\in\mathcal{P}(X)$
represents the uniform distribution on $X$.

##  II Channel Model

$u^{n}$$m^{N}$$u^{n}(m^{N})$$(\hat{u}^{n}_{1},x^{n}_{1})$$(\hat{u}^{n}_{N},x^{n}_{N})$$\dots$$\dots$$\mathcal{C}_{s}$
Figure 1: Depiction of the causal, state dependent, broadcast channel. The
sender at the top sends $m^{N}$ to the encoder $u^{n}$ which encodes the
message as $u^{Nn}$. After encoding, the message is put through the state
dependent channel $\mathcal{C}_{s}$, where for each bit of $u^{Nn}$ sent
through the channel, a state is selected uniformly at random game using the
modulo sum of $x^{N}$. One piece of $x^{N}$ is sent to the respective receiver
until all $x_{i}^{n}$ are received. The receivers can then use their part of
$x^{Nn}$ as input to their coordinator $q$ to receive $\gamma_{i}^{n}$ which
can be used to aid in decoding $\hat{u}_{i}^{n}$.

The broadcast channel consists of one sender and $N$ receivers, of which up to
$N-2$ can be colluding, as to satisfy maximum collusion condition. A single
sender intends to transmit a collection of private messages
$m^{N}\coloneqq(m_{1},...,m_{N})$, one to each of the respective receivers.
For message transmission, the sender uses encoder
$u^{n}:(m_{1},...,m_{N})\mapsto(u_{1}^{n},...,u_{N}^{n})$ which maps the
messages $(m_{1},...,m_{N})$ to block-length $n$ messages
$u_{i}^{n}\in\\{0,1\\}^{Nn}$ for $n$ channel uses. For convenience we define
the map $u^{n}(m_{i})\mapsto u^{n}(m^{N})_{i}$, a mapping to the $i$-th index
of the encoded message string. Between the sender and each receiver $i$ is a
state dependent binary inference channel $\mathcal{C}_{s}\in
C(\\{0,1\\},\\{0,1\\})$ with an environmentally controlled state
$s\in\\{0,1\\}$. The channel behaves as follows: When $s=0$,
$\mathcal{C}_{0}\coloneqq\mathbbm{1}$ is the identity channel, and when $s=1$,
$\mathcal{C}_{1}\coloneqq\mathbbm{F}$ is the bit flip channel. The total
channel $\mathcal{C}_{s}^{N}$ is a product of the channels, that is,

$\displaystyle\mathcal{C}_{s}^{N}\coloneqq\prod_{i=1}^{N}\mathcal{C}_{s},$ (1)

where each channel in the product shares the same state $s$.

The main requirement for channel state selection is that the state of the
channel is uniformly random between two outcomes such that for three or more
players, no receiver can infer the channel state based on their individual
state information. We use one such example as follows. Prior to transmission
of $u_{t}=\\{0,1\\}^{N}$ at time $t$, an environmental state
$x_{t}^{N}\in\\{0,1\\}^{N}$ is realized according to the uniform distribution
on $\\{0,1\\}^{N}$. For each $i$, One part $x_{i,t}$ of $x^{N}_{t}$ is sent
along with other information to receiver $i$ with no encoding or effects from
the channel when a transmission is made. The state $s$ at transmission $t$ is
selected using $s=\sum_{i}x_{i,t}\mod 2$. For convenience we define
$\Phi(x_{t}^{N})=\sum_{i}x_{i,t}\mod 2$. We use this example modulo sum
throughout this work. $\Phi(x^{Nn})$ denotes
$(\Phi(x^{N}_{1}),...,\Phi(x^{N}_{n}))$.

When the sender sends a message to the receivers, the message is encoded into
$n$ bits and transmitted over $n$ uses of $\mathcal{C}_{s}^{N}$. At each
transmission $t$ the receivers receive their part of $x^{N}$ and use it to
assist in decoding their private message from the sender. Each receiver
$i\in[N]$ can use $\\{x_{i,t}\\}_{t=1}^{n}$ to aid in selecting a decoder
$d^{n}_{i}\in C(\\{0,1\\}^{n}\times\Gamma^{n},\mathbf{M}_{i})$,
$\mathbf{M}_{i}$ the codebook for receiver $i$, which takes as input $n$
outputs of the channel $\mathcal{C}_{s}$ and a coordination parameter
$\gamma_{i}^{n}\in\Gamma^{n}$ which serves to coordinate the $N$ receivers
while decoding. The parameter $\gamma_{i}^{n}\in\Gamma^{n}$ is distributed
according to the channel $q\in C(\\{0,1\\}^{Nn},\Gamma^{Nn})$ which we call
the coordinator. Each receiver inputs their part $x_{i}^{n}$ of $x^{Nn}$ to
$q$ and receives a response $\gamma_{i}^{n}$ which is used for decoding.

######  Definition 1 (Non-signalling channel)

A channel $q\in C(\mathbf{X},\Gamma)$ is called non-signalling if, for all
$\gamma_{1},x_{1},x_{2},x_{2}^{\prime}$,

$\displaystyle\sum_{\gamma_{2}}q(\gamma_{1},\gamma_{2}|x_{1},x_{2})=\sum_{\gamma_{2}}q(\gamma_{1},\gamma_{2}|x_{1},x_{2}^{\prime})$
(2)

and for all $\gamma_{2},x_{1},x_{1}^{\prime},x_{2}$,

$\displaystyle\sum_{\gamma_{1}}q(\gamma_{1},\gamma_{2}|x_{1},x_{2})=\sum_{\gamma_{1}}q(\gamma_{1},\gamma_{2}|x_{1}^{\prime},x_{2}).$
(3)

In this work, we use various approaches at the receivers for determining the
decoding parameter $\gamma^{n}_{i}$. Here we consider the following three
scenarios:

  1. 1.

Classical communication is not available between receivers, but shared
entanglement is.

  2. 2.

Classical communication is available between receivers but not entanglement.

  3. 3.

Classical communication and shared entanglement are both available.

In the first case, correlations are non-signalling, where in the other two,
they are signalling. We define the channel formally as follows:

######  Definition 2 (Broadcast Code)

A broadcast code $C$ for block-length $n$ and $N$ receivers consists of
message sets $\mathbf{M}_{1},...,\mathbf{M}_{N}$. Moreover $C$ contains an
encoder $u^{n}(m_{1},...,m_{N})$ where
$u^{n}:(m_{1},...,m_{N})\mapsto(u_{1}^{n},...,u_{N}^{n})\subset\\{0,1\\}^{Nn}$.
Next, for each $i$, $C$ contains a causal decoder
$d^{n}_{i}(\hat{m}_{i}|u^{n}_{i},\gamma_{i}^{n})$ which decodes the channel
output when $n$ bits arrive. $d_{i}^{n}$ assigns an estimate
$\hat{m}_{i}\in\mathbf{M}_{i}$ using decoding sets
$D^{\gamma_{i}}_{i}\coloneqq\\{D^{\gamma_{i}}_{i,j}\\}_{j=1}^{|\mathbf{M}_{i}|}\subset\\{0,1\\}^{n}$
where for a fixed $i$ and $j\neq k$ $D^{\gamma_{i}}_{i,j}\cap
D^{\gamma_{i}}_{i,k}=\emptyset$.

###### Remark 3

$D^{\gamma_{i}}_{i}$ is dependent on $\gamma_{i}$ where the dependence is to
counteract the estimated the channel state.

######  Definition 4 (Transmission Error)

Let $C_{n}$ be a broadcast code with block-length $n$ and $N$ receivers
transmitting over $\mathcal{C}_{s}^{N}$ as defined in (1). Let
$M\coloneqq\prod_{i=1}^{N}|\mathbf{M}_{i}|$. The average probability for
transmission success is,

$\displaystyle\begin{aligned}
P_{succ}(C_{n})=\frac{1}{M2^{Nn}}\sum_{m^{N}}\sum_{\begin{subarray}{c}x^{Nn},\\\
\gamma^{Nn}\end{subarray}}&q(\gamma^{Nn}|x^{Nn})\cdot\\\\[-8.53581pt]
&\prod_{i=1}^{N}d^{n}_{i}(D^{\gamma_{i}^{n}}_{i,m_{i}}|\mathcal{C}^{n}_{\Phi(x^{Nn})}(u^{n}(m_{i})),\gamma_{i}^{n}).\end{aligned}$
(4)

where $\mathcal{C}^{n}_{\Phi(x^{Nn})}(u^{n}(m))$ represents the channel output
after $n$ uses of $\mathcal{C}_{\Phi(x_{t}^{N})}$ using
$\\{x^{N}_{t}\\}_{t=1}^{n}$ for transmission $t$ to send the $t$-th bit of
encoding $u^{n}(m)$. The probability of error is defined as
$P_{err}(C_{n})=1-P_{succ}(C_{n})$.

######  Definition 5 (Achievable Rate Tuple)

A rate tuple $(R_{1},...,R_{N})$ is called achievable if there exists a
sequence of causal codes $(C_{n})_{n\in\mathbb{N}}$ such that for any
$i\in\\{1,...,N\\}$,

$\displaystyle\liminf_{n\rightarrow\infty}\frac{1}{n}\log|\mathbf{M}_{i,n}|\geq
R_{i}$ (5)

while at the same time

$\displaystyle\lim_{n\rightarrow\infty}P_{err}(C_{n})=0.$ (6)

The capacity region of a channel is the closure of all achievable rate tuples.

In order to determine the channel state for each transmission in this
communication scenario, the receivers will need a scheme such that they can
determine the modulo sum of the combined state information of each other
receiver. Since some of the receivers are possibly colluding, each receiver
should not simply give away their own state information and thus use a random
variable $R_{i}$ to encode $X_{i}$ with. Formally, we enforce that for any
proposed protocol for multi-party modulo sum, it must be that for colluding
receivers $Z\subset[N],|Z|\leq N-2$ and each for all non-colluding receivers
$i\in[N]\setminus Z$,

$\displaystyle I(R_{i};Y_{Z})=0,$ (7)

where $Y_{Z}$ is all of the information obtainable by the coalition excluding
information derivative to the multi-party calculation. One might consider
enforcing $I(X_{i};Y_{z})=0$ for all $i$ as well, but for any multi-party
summation protocol, there is always a way to determine the sum of the inputs
of the non-colluding parties amongst the coalition. We also enforce a
reliability condition which is that when all $N$ receivers perform the
protocol honestly, then each of the receivers determine the channel state.
Once the channel state is determined for each transmission, they generate a
variable $\gamma^{Nn}$ which contains the state information for each
transmission $1\leq t\leq n$. With this, each receiver $i$ can choose the
respective decoding set $D^{\gamma_{i}^{n}}_{i}$.

##  III Entanglement Without Classical Communication

###### Theorem 6

When classical communication between the receivers is not available but
entanglement is, the rate region equals $0^{N}$. Moreover, without classical
communication, no protocol exists using only entanglement to compute the
modulo sum of the channel state information.

In this scenario, the receivers cannot classically communicate but can share
entanglement resources in any form distributed prior transmission. For each
transmission $t$, each receiver $i$ receives their bit $x_{i,t}$ where based
on the channel state selection mechanism, each $x_{j,t}$ is independent of
$x_{i,t}$ for $i\neq j$. The task for the receivers is to correlate themselves
such that they have a better than $p=1/2$ chance at guessing the channel
state. To do this, the parties need to devise a joint measurement on their
entangled states that can signal, contradicting the no-signaling theorem.
Because the channel state is selected using an unbiased modulo sum the channel
state equally the identity channel as it is the bit flip channel, the overall
channel is a binary symmetric channel with $p=1/2$, well known to have $0$
capacity. That the parties are malevolent makes no difference here as there is
no way for the receivers to gain any information from the other receivers.

###### Proof:

For the channel $C_{s}^{N}$, assume there is an achievable rate tuple
$(R_{1},...,R_{N})$ where for at least one $i$, $i=1$ without loss of
generality, $R_{i}>0$. Then, for any $\epsilon>0$ there is an $n$ large enough
such that,

$\displaystyle\begin{aligned}
1-{\varepsilon}\leq\frac{1}{M2^{Nn}}\sum_{m^{N}}\sum_{\begin{subarray}{c}x^{Nn}\\\
\gamma^{Nn}\end{subarray}}q&(\gamma^{Nn}|x^{Nn})\cdot&\\\\[-22.76219pt]
&\prod_{i=1}^{N}d^{n}_{i}(D^{\gamma_{i}^{n}}_{i,m_{i}}|\mathcal{C}^{n}_{\Phi(x^{Nn})}(u^{n}(m_{i})),\gamma_{i}^{n})\end{aligned}$
(8) $\displaystyle\begin{aligned}
\leq\frac{1}{\mathbf{M}_{1}2^{Nn}}\sum_{m_{1}}\sum_{\begin{subarray}{c}x^{Nn}\\\
\gamma^{Nn}\end{subarray}}q(\gamma^{Nn}&|x^{Nn})\cdot\\\\[-22.76219pt]
&d^{n}_{1}(D^{\gamma_{1}^{n}}_{1,m_{1}}|\mathcal{C}^{n}_{\Phi(x^{Nn})}(u^{n}(m_{1})),\gamma_{1}^{n}).\end{aligned}$
(9)

In order to better predict $\Phi(x^{Nn})$, the receivers coordinate with
$q(\gamma^{Nn}|x^{Nn})$. Shared entanglement alone is non-signalling [12] and
so

$\displaystyle\sum_{\gamma^{(N-1)n}}q(\gamma^{n}_{1},\gamma^{(N-1)n}|x_{1}^{n},x^{(N-1)n})=q_{1}(\gamma^{n}_{1}|x_{1}^{n}).$
(10)

The channel state $\Phi(x^{Nn})$ for channel
$\mathcal{C}^{n}_{\Phi(x^{Nn})}(\hat{u}^{n}|u^{n}(m_{1}))$ and decoder
$d_{1}^{n}$ with $n$ transmissions leads to an effective channel from sender
$1$ to receiver $1$. Let $g$ denote the channel from sender $1$ to receiver
$1$, including the reception of a copy $x$ of the state variable $x_{1}$.

$\displaystyle g(x,y|u)$
$\displaystyle=2^{-N}\sum_{x^{N}}\delta(x,x_{1})\delta(y,\Phi(x^{N})\oplus u)$
(11)
$\displaystyle=\tfrac{1}{2}\sum_{x_{1},\hat{x}}\delta(x,x_{1})\tfrac{1}{2}\delta(y,\hat{x}\oplus
x_{1}\oplus u)$ (12) $\displaystyle=\pi(x)\pi(y).$ (13)

Obviously, for the Shannon capacity $C$ of $g$ it holds $C(g)=0$. Therefore no
coding scheme, and in particular none that uses the particular random decoder

$\displaystyle\hat{d}(m|x_{1}^{n},y^{n}):=\sum_{\gamma^{n}_{1}}q(\gamma^{n}_{1}|x^{n}_{1}){\mathbbm{1}}_{D^{\gamma^{n}_{1}}_{m}}(y^{n}),$
(14)

can transmit at positive rates over $g$. This contradicts (8) and thus only
$0^{N}$ is achievable. ∎

##  IV Classical Communication Without Entanglement

In the next two cases, we develop a signalling coordinator $q$ that can be
used to achieve positive capacity.

###### Theorem 7

When classical communication is allowed between the receivers, using Strategy
2 the rate tuple $1^{N}$ is achievable and the communication complexity is
$\Omega(N^{2})$ using a conditionally secure protocol.

###### Remark 8

For unconditional security, the secrecy of each communication channel between
each pair of connected receivers must be verified, which would add a
significant communication resource overhead to the protocol. With only
classical resources, one could consider private key distribution, but with
colluding receivers this would not work since private keys could be shared in
the collusion.

When classical communication is available, the receivers can collaborate to
each send the $x_{i}$ amongst each other receiver to perfectly determine the
channel state $s$ for each transmission. When all receivers are honest,
nothing more needs to be done, however when some receivers are dishonest, more
complexity is needed in order to preserve secrecy. We can turn to theory for
secure multi-party computation (MPC), specifically secure multi-party modulo
summation to compute the common function $\Phi(x^{N})$. Since in this case the
parties are not allowed to share entanglement and are allowed only classical
communication, we only investigate purely classical strategies. In all
strategies the assumption of minimum non-colluding parties (i.e. at most $N-2$
parties can collude) is made. In the following we sketch the strategy and the
complexity analysis.

###  IV-A Strategy I: Secure multi-party modulo summation

For the first strategy, we consider a protocol that requires secure channels
between each of the receivers. We enforce this in this case in a purely
classically way (e.g. using quantum key distribution schemes is prohibited).
If we assume a standard public key cryptography system, then there is an
additional communication overhead of $\Omega(N^{2})$, since with just forward
communication as the protocol needs,

$\displaystyle(N-1)(N-2)/2=(N^{2}-3N+2)/2,$ (15)

secure channels are needed, and therefore as many public keys need to be
distributed. Commonly used public key cryptography schemes like RSA are not
unconditionally secure as they can be broken with enough computing power or a
quantum computer [13]. In contrast, as we will see in Section V, when
entanglement is available, secure communication is not necessary.

In [10], Chor and Kushilevtiz give a multi-party protocol to compute a modulo
sum with a security trade-off parameter $t\in[N]$. Here $t$ represents that no
coalition of size at most $t$ can infer any additional information from the
other receivers’ $x_{i}$ from the other $N-t$ parties other than the modulo
sum value, with $t\leq N-2$. This protocol uses $N\lceil(t+1)/2\rceil$
conferencing messages assuming preestablished secure communication channels.
For completeness we state the protocol in Protocol 1, where $t$ is assumed to
be $N-2$.

Protocol 1 Classical State Decoding

1:for $i\in\\{1,...,N-2\\}$ do

2: Receiver $i$ awaits $z_{j,i}$ from receivers $j<i$ and calculates
$w_{i}=\sum_{j=1}^{i-1}z_{j,i}\mod 2$ with $w_{1}=0$

3: Receiver $i$ selects uniformly at random
$z_{i,i+1},z_{i,i+2},...,z_{i,N-1}$ each from $\\{0,1\\}$

4: Receiver $i$ determines $z_{i,N}$ such that
$x_{i}+w_{i}=\sum_{j=i+1}^{N}z_{i,j}$ and sends $z_{i,j}$ to the respective
receiver $j>i$

5:Receiver $N-1$ computes $z_{N-1,N}=x_{N-1}+\sum_{j=1}^{N-2}z_{j,N-1}\mod 2$
and sends it to receiver $N$

6:Receiver $N$ computes $s=x_{N}+\sum_{j=1}^{N-1}z_{j,n}\mod 2$ and broadcasts
$s$ to all other receivers

The proof of correctness for this protocol is given explicitly in [10]. The
downside of using this protocol alone is that for decoding a message of length
$n$, the protocol needs to execute $n$ times. In Strategy II, we use this
protocol to generate a zero-sum random variable in the first step and then
using this zero sum random variable, one can save resources by reusing it for
each transmission. We explore the pros and cons in depth.

###  IV-B Strategy II: Modulo-zero summation from modulo summation

We consider another strategy where the receivers use Protocol 1 to produce
random variables $R=(r_{1},...,r_{N})$ such that $\sum_{i=1}^{N}r_{i}=0$ and
then perform steps 4 and 5 from Protocol 4 using this zero-sum randomness. To
generate such a zero-sum random variable, one can use the protocol defined in
[11, Protocol 2] which we include explicitly as a subprotocol in Protocol 2.
Once a zero-sum realisation is generated, it can be used repeatedly to decode
a message of length $n$. The full protocol in is given explicitly in Protocol
2.

Protocol 2 Classical Secure Multi-Party Summation

1:Each receiver $i$ generates a uniform random number $Y_{i}$ independent of
the other receivers

2:The receivers run Protocol 1 with $\\{Y_{i}\\}_{i=1}^{N}$ and each receiver
will have the result $\sum_{i=1}^{N}Y_{i}$

3:Receiver $1$ uses random variable $r_{1}=Y_{1}-\sum_{i=1}^{N}Y_{i}$,
receivers $i\in\\{2,...,N\\}$ use $r_{i}=Y_{i}$

4:To determine channel state $s_{t}$ for transmission $1\leq t\leq n$, each
receiver broadcasts $s_{i,t}\coloneqq x_{i,t}+r_{i}$. The channel state is
found by $s_{t}=\sum_{i=1}^{N}s_{i,t}\mod 2=\sum_{i=1}^{N}x_{i,t}+r_{i}\mod
2=\sum_{i=1}^{N}x_{i,t}\mod 2$

We summarize the communication complexity analysis. For establishing
(conditionally) secure connections using public key distribution techniques
requires each receiver (in the limit of increasing receivers) to send a public
key to each other receiver consuming $\Omega(N^{2})$ messages. Next, to
generate a zero-sum random variable using Protocol 1 requires $\Omega(Nt)$ for
$t$ colluding parties. Once a zero-sum random variable realisation is
successfully generated, the receivers can use step $4$ from Protocol 4 which
requires each sender use a broadcast channel to transmit their encrypted state
information. In total, the communication is therefore $\Omega(N^{2}+Nt)$.

That the zero-sum random variable can be recycled is because of its zero-sum
condition. For example, assume $N-2$ parties collude and share their $r_{i}$
with each other in an attempt to determine, without loss of generality,
$r_{1}$ and $r_{2}$. Then at the end of the protocol, the $N-2$ colluding
parties have $(x_{1}+r_{1})+(x_{2}+r_{2})+\sum_{i=3}^{N}r_{i}=x_{1}+x_{2}$,
and thus no reminisce of $r_{1}$ or $r_{2}$ remains.

##  V Classical Communication with Entanglement

###### Theorem 9

When classical communication and entanglement is allowed between the
receivers, there exists a multi-party summation protocol such the rate tuple
$1^{N}$ is achievable with classical communication complexity $\Omega(N)$ and
entanglement resource complexity $\Omega(N^{2}m)$ with unconditional security.

We sketch the proof. To determine the channel state $s$, the receivers perform
Protocol 4 for multi-party modulo summation extended from [11, Protocol 4],
which offers verifiable randomness for zero-sum random variables and
unconditional security. The protocol uses phase-GHZ states defined as follows.
Let $R^{N}\coloneqq\\{r^{N}=(r_{1},...,r_{N}):\forall
i,r_{i}\in\\{0,1\\},\sum_{i=1}^{N}r_{i}=0\\}$. The phase-GHZ state is defined
as:

$\displaystyle\ket{GHZ}_{p}\coloneqq\frac{1}{\sqrt{2^{N-1}}}\sum_{r^{N}\in
R^{N}}\ket{r^{N}}.$ (16)

This ensures every joint measurement result $\ket{GHZ}_{p}$ sums to $0$. With
security parameter $m$, we write the necessary protocols that the receivers
use to securely communicate their piece of the channel state such that the
security is verifiable.

Protocol 3 Phase-GHZ State Validation

1:With $4Nm$ copies of the $\ket{GHZ}_{p}$ state, randomly divide the states
into $4m$ groups with $n$ states each.

2:Apply measurements to the respective groups using the measurement structure
in [11, Table 1].

3:Await a broadcast from all other receivers with their measurement results
from the previous step.

4:Check that inequalities $(9)$ and $(10)$ in [11, Protocol 3] hold.

5:If the inequalities hold report success, otherwise report failure.

Protocol 4 Entanglement Assisted State Decoding

1:The $N$ receivers generate $4N^{2}m+1$ copies of the $\ket{GHZ}_{p}$ state.

2:From the $4N^{2}m+1$ $\ket{GHZ}_{p}$ states, each receiver allocates
$4N^{2}m$ of the copies, randomly selecting $4Nm$ copies from their respective
part, and applies as a sub-protocol Protocol 3. If the sub-protocol runs
successfully, they continue to the next step.

3:Each receiver $i$ measures the last remaining copy in the computational
basis and stores the output as $r_{i}$.

4:For each $x_{i,t}$, each receiver $i$ calculates $s_{i,t}\coloneqq
x_{i,t}+r_{i}$ and broadcasts all $\\{s_{i,t}\\}_{t=1}^{n}$ to all other
receivers.

5:Each receiver calculates $s_{t}=\sum_{i=1}^{N}s_{i,t}\mod
2=\sum_{i=1}^{N}x_{i,t}+r_{i}\mod 2=\sum_{i=1}^{N}x_{i}\mod 2$.

Using these protocols, the receivers can with certainty and security (with
respect to with parameter $m$) determine the channel state $s$ for each
transmission, thereby allowing for perfect decoding the message.

The communication complexity of this approach is as follows. As far as we
know, there are no protocols currently used for distributing GHZ states, and
so to estimate the communication complexity of the task we assume there is a
communal source generating $\ket{GHZ}_{p}$ states and transmitting them to the
receivers in a “frame” of qubits using one transmission to transmit the
$4N^{2}m+1$ $\ket{GHZ}_{p}$ states, namely $\Omega(1)$ classical resources to
generate $\Omega(N^{2}m)$ entanglement resources. Next, the receivers use
Protocol 3 to validate their GHZ states using $\Omega(N)$ messages over a
broadcast channel. Finally, the receivers again use $\Omega(N)$ messages to
broadcast the state information encoded with the zero-sum random variable. In
summary, $\Omega(N^{2}m)$ entanglement resources are used with $\Omega(N)$
classical resources for verifiable unconditionally secure decoding of the
state information satisfying all of the protocol requirements.

##  VI Converse Arguments

In each case, the converse arguments are the same. The broadcast channel
transmits the messages in such a way that without signalling communication
amongst the receivers, the channel acts as a $BSC(0.5)$ channel, well known to
have a capacity of $0$. Because the channel state information vector $x^{N}$
is generated i.i.d. randomly, there is no correlation between any two
receiver’s individual state information. Because of this there is no way for
the receivers to achieve any positive rate without the cooperation of all
receivers.

##  VII Conclusions and Outlook

In summary, we have constructed a communication scenario over a causal
broadcast channel such that in order for the channel to have positive
capacity, the receivers must cooperate to compute a multi-party modulo sum. We
considered three scenarios where the receivers have access to various
resources and showed that when the receivers can share entanglement and use a
separate classical broadcast channel to cooperate, they can most efficiently
determine the channel state to achieve the full capacity of the channel. We
can further investigate different methods of selecting the channel state based
results where there is a known quantum advantage.

## References

  * [1]
  * [2] D. Gavinsky, “On the role of shared entanglement,” _arXiv preprint quant-ph/0604052_ , 2006.
  * [3] C. H. Bennett, P. W. Shor, J. A. Smolin, and A. V. Thapliyal, “Entanglement-assisted classical capacity of noisy quantum channels,” _Physical Review Letters_ , vol. 83, no. 15, p. 3081, 1999.
  * [4] J. Nötzel, “Entanglement-enabled communication,” _IEEE Journal on Selected Areas in Information Theory_ , vol. 1, no. 2, pp. 401–415, 2020.
  * [5] J. Nötzel and S. DiAdamo, “Entanglement-enabled communication for the internet of things,” in _2020 International Conference on Computer, Information and Telecommunication Systems (CITS)_ , 2020, pp. 1–6.
  * [6] C. Crépeau, D. Gottesman, and A. Smith, “Secure multi-party quantum computation,” in _Proceedings of the thiry-fourth annual ACM symposium on Theory of computing_ , 2002, pp. 643–652.
  * [7] A. K. Ekert, “Quantum cryptography based on bell’s theorem,” _Physical review letters_ , vol. 67, no. 6, p. 661, 1991.
  * [8] I. Maric, R. D. Yates, and G. Kramer, “Capacity of interference channels with partial transmitter cooperation,” _IEEE Transactions on Information Theory_ , vol. 53, no. 10, pp. 3536–3548, 2007.
  * [9] U. Pereg and Y. Steinberg, “The arbitrarily varying broadcast channel with causal side information at the encoder,” _IEEE Transactions on Information Theory_ , vol. 66, no. 2, pp. 757–779, 2019.
  * [10] B. Chor and E. Kushilevitz, “A communication-privacy tradeoff for modular addition,” _Information Processing Letters_ , vol. 45, no. 4, pp. 205–210, 1993.
  * [11] M. Hayashi and T. Koshiba, “Verifiable quantum secure modulo summation,” _arXiv preprint arXiv:1910.05976_ , 2019.
  * [12] S. Popescu and D. Rohrlich, “Causality and nonlocality as axioms for quantum mechanics,” in _Causality and locality in modern physics_. Springer, 1998, pp. 383–389.
  * [13] P. W. Shor, “Algorithms for quantum computation: discrete logarithms and factoring,” in _Proceedings 35th annual symposium on foundations of computer science_. Ieee, 1994, pp. 124–134.