# Secure Multi-Function Computation with
Private Remote Sources

Onur Günlü  Matthieu Bloch  and Rafael F. Schaefer  This work has been
supported in part by the German Research Foundation (DFG) under the Grant SCHA
1944/9-1 and in part by the National Science Foundation (NSF) under the Grant
CCF 1955401.O. Günlü and R. F. Schaefer are with the Chair of Communications
Engineering and Security, University of Siegen, 57076 Siegen, Germany (email:
{onur.guenlue, rafael.schaefer}@uni-siegen.de).M. Bloch is with the School of
Electrical and Computer Engineering, Georgia Institute of Technology, Atlanta,
GA 30332 (email: matthieu.bloch@ece.gatech.edu).

###### Abstract

We consider a distributed function computation problem in which parties
observing noisy versions of a remote source facilitate the computation of a
function of their observations at a fusion center through public
communication. The distributed function computation is subject to constraints,
including not only reliability and storage but also privacy and secrecy.
Specifically,  1. the remote source should remain _private_ from an
eavesdropper and the fusion center, measured in terms of the information
leaked about the remote source;  2. the function computed should remain
_secret_ from the eavesdropper, measured in terms of the information leaked
about the arguments of the function, to ensure secrecy regardless of the exact
function used.  We derive the exact rate regions for lossless and lossy
single-function computation and illustrate the lossy single-function
computation rate region for an information bottleneck example, in which the
optimal auxiliary random variables are characterized for binary-input
symmetric-output channels. We extend the approach to lossless and lossy
asynchronous multiple-function computations with joint secrecy and privacy
constraints, in which case inner and outer bounds for the rate regions
differing only in the Markov chain conditions imposed are characterized.

##  I Introduction

Consider a scenario in which multiple terminals that observe dependent random
sequences want to compute a function of their sequences by exchanging messages
through public communication links [1, 2]. One application for which this
distributed function computation problem is relevant is network function
virtualization [3] via, e.g., software defined networking. To compute a
function of a subset of sequences, it is not always necessary for the terminal
computing the function, called _fusion center_ , to observe the exact
sequences [4]. This fact allows one to reduce the public communication rate,
also called _storage rate_ , required for reliable function computations by
using, e.g., distributed lossless source coding techniques [5]. Furthermore,
for various functions, it suffices to recover a distorted version of the
original sequence by using, e.g., distributed lossy source coding methods [6].
Lossy reconstruction allows to further reduce the amount of public storage,
which is useful for resource-limited networks such as Internet-of-Things (IoT)
devices that make aggregated decisions using lightweight mechanisms [4, 7, 8,
9, 10, 11]; see [12, 13, 14, 15, 16] for various extensions of the basic
function computation problem with reliability and storage constraints.

Reliable function computation and small public storage constraints have also
been combined with _secrecy_ constraints, requiring that the computed function
outputs be hidden from an eavesdropper [17]. In addition to the public
messages exchanged between terminals, the eavesdropper is considered to have
access to a random sequence correlated with other sequences. Various
extensions of the basic secure function computation or distributed source
coding problems have been analyzed in the literature [18, 19, 20, 21, 22, 23,
24]. Furthermore, a _privacy_ constraint has been added in [25] to the
problem. The main difference between _secrecy_ and _privacy_ is that secrecy
leakage is measured with respect to the functions computed while privacy
leakage is measured with respect to the source sequences themselves. A privacy
leakage analysis provides an upper bound on the secrecy leakage of future
function computations involving the terminals already participating in earlier
function computations [26, 27]. This is because the information leaked about
the sequence of a terminal might leak information about another function
computed by using the same sequence. We extend [25] by considering separate
privacy constraints on the source of the random sequence of the _transmitting
terminal_ that sends a public message to the fusion center.

A common assumption in the literature is that sequences observed by all
terminals are distributed according to a joint probability distribution.
However, the correlated random sequences observed by terminals in a network
generally stem from a common source of information, e.g., some sensor location
information transmitted through the network before the next function
computation starts, distorted versions of which are distributed within the
network. Thus, we posit that there exists a common true source, called the
ground truth or the remote source, hidden from all terminals and of which the
observed sequences are noisy versions. Such a hidden source model allows a
terminal to combine multiple observed sequences to obtain a single “higher
quality” random sequence, which is entirely similar to applying maximal ratio
combining over an additive white Gaussian noise (AWGN) channel. This approach
is thus useful to model the quality differences between random sequences
observed by different terminals. If the function computation network is
mistakenly modeled with a visible (or unhidden) source model, the code
construction designed for the assumed visible source model might result in
unnoticed secrecy leakage and reduction in computation reliability, as
illustrated in [27] for key agreement.

Noisy measurements of a hidden source are generally modeled as observations
through broadcast channels (BCs) [28] to have a generic measurement model that
allows noise components at different terminals to be correlated [29, 30]. Such
a hidden source model is proposed and motivated in [31] for authentication
problems and in [32, 29] for secret-key agreement problems with a privacy
constraint. As we detail in Section II, such a hidden source model results in
two different privacy leakage constraints measured with respect to the hidden
source, which is different from the single privacy leakage constraint
considered in [25] measured with respect to the random sequence observed by
the transmitting terminal. The privacy leakage and storage rates are shown
below to be different for this model, unlike in previous works. Furthermore,
the equivocation of the source is commonly used in the literature to measure
the secrecy leakage, which results in rate bounds with conditional entropy
terms. By replacing the equivocation with the mutual information terms, we
obtain rate regions with simpler notation and easier interpretations.

We consider two function computation settings. The first setting imposes a
reliable (lossless) computation of the function of interest and the other one
allows a fixed level of distortion between the computed function and the
actual function output (lossy function computation) [25]. These settings
address different applications. For instance, the lossless function
computation setting might model user/terminal identification, where the exact
identifier recovery is necessary; in contrast, the lossy function computation
setting might model user/terminal authentication, where a set of users whose
computed functions are close to a pre-defined value are authenticated. We
bound the error probability for the reliable function computation task for the
lossless setting and the expected distortion for lossy setting, respectively,
which require different proof steps. We exactly characterize the rate regions
for both settings when a single function is computed.

We further extend the function computation with privacy and secrecy problem by
considering multiple function computations with joint secrecy and privacy
constraints on all terminals involved in any function computation task. This
extension allows one to measure the total amount of information about all
computed functions within a network leaked to an eavesdropper. This extension
also allows one to correctly characterize the privacy leakage to an
eavesdropper, i.e., the amount of information about the hidden source leaked
to an eavesdropper who might observe all public messages and all side
information obtained during all (not necessarily synchronous) function
computations within the same network. Multiple function computations with
joint secrecy and privacy constraints are closely related to the multi-entity
and multi-enrollment key agreement problems in [33], where the noisy
measurements of the same hidden source are used for multiple key agreements.
Both lossless and lossy function computation settings are analyzed to provide
inner and outer bounds for the multi-function rate regions, for which only the
imposed Markov chains differ.

###  I-A Summary of Contributions

Our problem formulation introduces one secrecy and two privacy constraints, in
addition to reliability (or distortion) and storage constraints, to the single
function computation problem to characterize the resulting rate regions. These
results are strict extensions of [25] as we consider a remote source common to
all terminals with side information sequences that are noisy measurements of
the remote source. Furthermore, we also consider multiple asynchronous
function computations within the same network with joint secrecy and privacy
constraints over all terminals involved in any function computation. A summary
of the main contributions is as follows.

  * •

We derive the rate region for lossless single-function computation with
secrecy and privacy constraints. The remote source model we consider
corresponds to a physically-degraded BC and when the transmitting observes the
remote (noiseless) source outputs, the model reduces to a semi-deterministic
BC. Furthermore, we show that convexification with a time-sharing random
variable is necessary, which is missing in some previous works.

  * •

We next consider the lossless multi-function computation where a finite number
$J$ of functions are computed from different noisy measurements (observed by
different terminals) of the same remote source asynchronously. We impose one
secrecy and privacy constraints that consider the total leakage in the
network, i.e., they are joint constraints for all parties involved in any
function computation. We propose inner and outer bounds for the multi-function
rate region that differ only in the Markov chain conditions imposed on the
auxiliary random variables. The rate regions include both separate constraints
for each terminal and joint constraints for all terminals.

  * •

All inner and outer bounds for the lossless single- and multi-function
computations are extended to the corresponding lossy settings. Similar to the
lossless case, we characterize the lossy rate region for the single-function
computation, and we provide inner and outer bounds for the multi-function
computations that differ only in the Markov chains imposed.

  * •

We evaluate the rate region for a lossy single-function computation problem,
in which the measurement channel of the eavesdropper is physically-degraded
compared to the measurement channel of the fusion center. We solve an
information bottleneck problem to obtain the rate region boundary tuples.

###  I-B Organization

This paper is organized as follows. In Section II, we describe four function
computation problems with a remote source that are lossless or lossy and
single-function or multi-function computation problems. We present the rate
regions for the lossless and lossy single-function computation in Section III
in addition to inner and outer bounds with different Markov chains for the
lossless and lossy multi-function computations for any finite number of
functions. In Section IV, we solve an information bottleneck problem to
illustrate the rate region for the lossy single-function computation problem.
In Section V, we provide the detailed proof for characterizing the rate
regions of the lossless single-function computation. Similarly, we offer
proofs of the inner and outer bounds for the lossless multi-function
computations in Section VI. In Section VII, we conclude the paper.

###  I-C Notation

Upper case letters represent random variables and lower case letters their
realizations. A superscript denotes a sequence of variables, e.g.,
$\displaystyle X^{n}\\!=\\!X_{1},X_{2},\ldots,X_{i},\ldots,X_{n}$, and a
subscript $i$ denotes the position of a variable in a sequence. A random
variable $\displaystyle X$ has probability distribution $\displaystyle P_{X}$.
Calligraphic letters such as $\displaystyle\mathcal{X}$ denote sets, set sizes
are written as $\displaystyle|\mathcal{X}|$ and their complements as
$\displaystyle\mathcal{X}^{c}$. $[1\\!:\\!J]$ denotes the set
$\\{1,2,\ldots,J\\}$ for an integer $J\geq 1$ and
$[1\\!:\\!J]\\!\setminus\\!\\{j\\}$ denotes the set
$\\{1,2,\ldots,j-1,j+1,\ldots,J\\}$ for any $j\in[1\\!:\\!J]$.
$H_{b}(x)\\!=\\!-x\log x-(1\\!-\\!x)\log(1\\!-\\!x)$ is the binary entropy
function, where logarithms are to the base $2$, and $H_{b}^{-1}(\cdot)$
denotes its inverse with range $[0,0.5]$. A binary symmetric channel (BSC)
with crossover probability $p$ is denoted by BSC($p$).
$X\sim\text{Bern}(\alpha)$ is a binary random variable with $\Pr[X=1]=\alpha$.

##  II Problem Definitions

###  II-A Lossless Single-Function Computation

Consider the function computation model illustrated in Fig. 1. Three terminals
obtain noisy observations $\widetilde{X}^{n},Y^{n},Z^{n}$, respectively, of a
single i.i.d. remote source $X^{n}$, through a memoryless channel with
transition probability $p_{\widetilde{X}|X}p_{YZ|X}$. The source alphabet
$\mathcal{X}$ and measurement alphabets
$\widetilde{\mathcal{X}},\mathcal{Y},\mathcal{Z}$ are finite sets. The
objective is for the terminal observing $\widetilde{X}^{n}$ to transmit a
message $W=\mathsf{Enc}(\widetilde{X}^{n})$ over a public channel and to
enable the terminal observing $Y^{n}$ to compute a function
$f^{n}(\widetilde{X}^{n},Y^{n})$ such that

$\displaystyle
f^{n}(\widetilde{X}^{n},Y^{n})={\\{f(\widetilde{X}_{i},Y_{i})\\}}_{i=1}^{n}.$
(1)

The terminal observing $Z^{n}$ and obtaining $W$ through the public channel is
treated as an eavesdropper (Eve).

Since $P_{\widetilde{X}XYZ}$ is fixed, the separate measurement channels
$P_{\widetilde{X}|X}$ and $P_{YZ|X}$ in Fig. 1 can be modeled as a physically-
degraded BC with transition probability
$P_{XYZ|\widetilde{X}}=P_{X|\widetilde{X}}P_{YZ|X}$ and with fixed input
probability distribution $P_{\widetilde{X}}$. For such a BC, the case of a
noiseless measurement for which $\widetilde{X}^{n}=X^{n}$ can be treated as a
semi-deterministic BC.

$P_{X}$$W=\mathsf{Enc}(\widetilde{X}^{n})$$P_{YZ|X}$$P_{\widetilde{X}|X}$$\widehat{f^{n}}=\mathsf{Dec}\left(W,Y^{n}\right)$Eve$W$$X^{n}$$Y^{n}$$\widetilde{X}^{n}$$X^{n}$$Z^{n}$$\widehat{f^{n}}$$W$

Figure 1: Noisy measurements of a remote source used to compute a function
securely and privately with the help of a public communication link.

######  Definition 1.

A tuple
$(R_{\text{s}},R_{\text{w}},R_{\ell,{\text{Dec}}},R_{\ell,{\text{Eve}}})$ is
_achievable_ if, for any $\delta\\!>\\!0$, there exist $n\\!\geq\\!1$, an
encoder, and a decoder such that

$\displaystyle\Pr\Big{[}f^{n}(\widetilde{X}^{n},Y^{n})\neq\widehat{f^{n}}\Big{]}\leq\delta$
$\displaystyle(\text{reliability})$ (2)
$\displaystyle\frac{1}{n}I(\widetilde{X}^{n},Y^{n};W|Z^{n})\leq
R_{\text{s}}+\delta$ $\displaystyle(\text{secrecy})$ (3)
$\displaystyle\frac{1}{n}\log\big{|}\mathcal{W}\big{|}\leq
R_{\text{w}}+\delta$ $\displaystyle(\text{storage})$ (4)
$\displaystyle\frac{1}{n}I(X^{n};W|Y^{n})\leq R_{\ell,\text{Dec}}+\delta$
$\displaystyle(\text{privacyDec})$ (5)
$\displaystyle\frac{1}{n}I(X^{n};W|Z^{n})\leq R_{\ell,\text{Eve}}+\delta$
$\displaystyle(\text{privacyEve}).$ (6)

The region $\mathcal{R}$ is the closure of the set of all achievable tuples.
$\lozenge$

Note that the metric $I(f^{n}(\widetilde{X}^{n},Y^{n});W|Z^{n})$ might seem a
more natural way to measure the information leakage to the eavesdropper who
observes $(W,Z^{n})$ of the computed function $f^{n}(\cdot,\cdot)$. However,
the analysis of this metric depends on the specific properties of the function
$f(\cdot,\cdot)$. Since the data-processing inequality ensures that
$I(f^{n}(\widetilde{X}^{n},Y^{n});W|Z^{n})\leq
I(\widetilde{X}^{n},Y^{n};W|Z^{n})$ for all functions $f(\cdot,\cdot)$ with
equality if $f(\cdot,\cdot)$ is a bijective mapping, we instead consider the
metric in (3). The analysis then does not depend on the computed function
$f(\cdot,\cdot)$ and provides a valid upper bound on the proper secrecy-
leakage rate metric for any $f(\cdot,\cdot)$. Since
$I(\widetilde{X}^{n},Y^{n};W|Z^{n})=I(\widetilde{X}^{n};W|Z^{n})$ because of
the Markov chain $W-\widetilde{X}^{n}-(Y^{n},Z^{n})$, the equivocation
$H(\widetilde{X}^{n}|W,Z^{n})$ considered in previous works [25] captures the
same secrecy leakage as (3). Furthermore, the privacy leakage metrics in (5)
and (6) measure the information leakage about the remote source to the decoder
and eavesdropper, respectively, due to function computation. We remark that in
(3), (5), and (6), we consider conditional mutual information terms to take
into consideration the unavoidable secrecy or privacy leakage due to side
information available at the fusion center or eavesdropper.

###  II-B Lossy Single-Function Computation

Consider again the single-function computation model depicted in Fig. 1 and
replace the reliability constraint in (2) with an expected distortion
constraint to allow a distorted reconstruction of the function
$f(\cdot,\cdot)$. This defines the lossy single-function computation model,
for which the notion of achievability is as follows.

######  Definition 2.

A _lossy_ tuple
$(R_{\text{s}},R_{\text{w}},R_{\ell,{\text{Dec}}},R_{\ell,{\text{Eve}}},D)$ is
_achievable_ if, for any $\delta\\!>\\!0$, there exist $n\\!\geq\\!1$, an
encoder, and a decoder that satisfy (3)-(6) and

$\displaystyle\mathbb{E}\Big{[}d(f^{n}(\widetilde{X}^{n},Y^{n}),\widehat{f^{n}})\Big{]}\leq
D+\epsilon$ (7)

where
$d(f^{n},\widehat{f^{n}})=\frac{1}{n}\sum_{i=1}^{n}d(f_{i},\widehat{f}_{i})$
is a per-letter distortion metric. The _lossy_ region $\mathcal{R}_{\text{D}}$
is the closure of the set of all achievable lossy distortion tuples.
$\lozenge$

###  II-C Lossless Multi-Function Computation

We next extend the lossless single-function computation model by considering
that the same remote source $X^{n}$ is measured by multiple encoder and
decoder pairs to compute different functions. Consider a finite number $J\geq
1$ of encoders $\mathsf{Enc}_{j}(\widetilde{X}_{j})=W_{j}$, decoders
$\mathsf{Dec}_{j}(W_{j},Y_{j}^{n})=\widehat{f_{j}^{n}}$, and functions
$f_{j}^{n}(\widetilde{X}_{j}^{n},Y_{j}^{n})=\\{f_{j}(\widetilde{X}_{i,j},Y_{i,j})\\}_{i=1}^{n}$
for $j\in[1:J]$, where $\widetilde{X}_{j}^{n}$ is measured through the channel
$P_{\widetilde{X}_{j}|X}$ and $(Y_{j}^{n},Z_{j}^{n})$ are measured through the
BC $P_{Y_{j}Z_{j}|X}$. The eavesdropper observes $(Z_{[1:J]}^{n},W_{[1:J]})$.
This multi-function computation model is illustrated in Fig. 2 for $J=2$.

######  Definition 3.

A _multi-function_ tuple
$(R_{\text{s}},R_{\text{w},[1:J]},R_{\ell,{\text{Dec}},[1:J]},R_{\ell,{\text{Eve}}})$
with $j$-th encoder measurements through $P_{\widetilde{X}_{j}|X}$ and $j$-th
decoder measurements through $P_{Y_{j}Z_{j}|X}$ for all $j\in[1:J]$ is
_achievable_ if, for any $\delta\\!>\\!0$, there exist $n\\!\geq\\!1$, and $J$
encoder and decoder pairs such that

$\displaystyle\Pr\Bigg{[}\underset{j\in[1:J]}{\bigcup}\Big{\\{}f_{j}^{n}(\widetilde{X}_{j}^{n},Y^{n}_{j})\neq\widehat{f_{j}^{n}}\Big{\\}}\Bigg{]}\leq\delta$
(8)
$\displaystyle\\!\frac{1}{n}I(\widetilde{X}_{[1:J]}^{n},Y_{[1:J]}^{n};W_{[1:J]}|Z_{[1:J]}^{n}\\!)\\!\leq\\!R_{\text{s}}\\!+\\!\delta$
(9) $\displaystyle\frac{1}{n}\log\big{|}\mathcal{W}_{j}\big{|}\leq
R_{\text{w},j}+\delta,$ $\displaystyle\forall j\in[1:J]$ (10)
$\displaystyle\frac{1}{n}I(X^{n};W_{j}|Y_{j}^{n})\leq
R_{\ell,\text{Dec},j}+\delta,$ $\displaystyle\forall j\in[1:J]$ (11)
$\displaystyle\frac{1}{n}I(X^{n};W_{[1:J]}|Z_{[1:J]}^{n})\leq
R_{\ell,\text{Eve}}+\delta.$ (12)

The _multi-function_ region $\mathcal{R}_{\text{mf}}$ is the closure of the
set of all achievable tuples. $\lozenge$

######  Remark 1.

The storage rate constraints in (10) and the corresponding privacy leakage
rate constraints in (11) are $J$ separate constraints. However, the
reliability constraint in (8), the secrecy leakage constraint in (9), and the
privacy leakage rate constraint in (12) are joint constraints that depend on
the parameters of all $J$ encoder-decoder pairs.

$P_{X}$$W_{1}=\mathsf{Enc}_{1}(\widetilde{X}_{1}^{n})$$P_{Y_{1}Z_{1}|X}$$P_{\widetilde{X}_{1}|X}$$\widehat{f_{1}^{n}}=\mathsf{Dec}_{1}\left(W_{1},Y_{1}^{n}\right)$Eve$W_{1}$$X^{n}$$Y_{1}^{n}$$\widetilde{X}_{1}^{n}$$X^{n}$$Z_{1}^{n}$$\widehat{f_{1}^{n}}$$W_{1}$$W_{2}=\mathsf{Enc}_{2}(\widetilde{X}_{2}^{n})$$P_{Y_{2}Z_{2}|X}$$P_{\widetilde{X}_{2}|X}$$\widehat{f_{2}^{n}}=\mathsf{Dec}_{2}\left(W_{2},Y_{2}^{n}\right)$$W_{2}$$Y_{2}^{n}$$\widetilde{X}_{2}^{n}$$X^{n}$$Z_{2}^{n}$$\widehat{f_{2}^{n}}$$W_{2}$

Figure 2: Noisy measurements of the same remote source used to compute $J=2$
functions (via $2J=4$ parties) securely and privately with the help of public
communication links.

###  II-D Lossy Multi-Function Computation

Similar to Section II-B, we extend the model of Section II-C to allow
distorted function computations for multiple functions
$f_{j}^{n}(\widetilde{X}_{j}^{n},Y_{j}^{n})=\\{f_{j}(\widetilde{X}_{i,j},Y_{i,j})\\}_{i=1}^{n}$
computed from different measurements $(\widetilde{X}^{n}_{j},Y^{n}_{j})$ of
the same remote source $X^{n}$.

######  Definition 4.

A _lossy multi-function_ tuple
$(R_{\text{s}},R_{\text{w},[1:J]},R_{\ell,{\text{Dec}},[1:J]},R_{\ell,{\text{Eve}}},D_{[1:J]})$
with $j$-th encoder measurements through $P_{\widetilde{X}_{j}|X}$ and $j$-th
decoder measurements through $P_{Y_{j}Z_{j}|X}$ for all $j\in[1:J]$ is
_achievable_ if, for any $\delta\\!>\\!0$, there exist $n\\!\geq\\!1$, and $J$
encoder and decoder pairs that satisfy (9)-(12) and

$\displaystyle\mathbb{E}\Big{[}d(f_{j}^{n}(\widetilde{X}^{n}_{j},Y_{j}^{n}),\widehat{f_{j}^{n}})\Big{]}\leq
D_{j}+\delta,\qquad\quad\forall j\in[1:J]$ (13)

where
$d(f^{n},\widehat{f^{n}})=\frac{1}{n}\sum_{i=1}^{n}d(f_{i},\widehat{f}_{i})$
is a per-letter distortion metric. The _lossy multi-function_ region
$\mathcal{R}_{\text{mf,D}}$ is the closure of the set of all achievable lossy
distortion tuples. $\lozenge$

##  III Rate Regions

We first recall the notion of an admissible random variable, used in Theorems
1 and 3.

######  Definition 5 ([4]).

A (vector) random variable $U$ is admissible for a function
$f(\widetilde{X},Y)$ if $U-\widetilde{X}-Y$ form a Markov chain and
$H(f(\widetilde{X},Y)|U,Y)=0$, i.e., $(U,Y)$ determine $f(\widetilde{X},Y)$.
$\lozenge$

Define $[a]^{-}=\min\\{a,0\\}$ and $[a]^{+}=\max\\{a,0\\}$ for
$a\in\mathbb{R}$.

###  III-A Lossless Single-Function Computation

We characterize the region $\mathcal{R}$ for the lossless single function
computation problem in Theorem 1. The corresponding proof is detailed in
Section V.

######  Theorem 1.

The region $\mathcal{R}$ is the set of all tuples
$(R_{\text{s}},R_{\text{w}},R_{\ell,{\text{Dec}}},R_{\ell,{\text{Eve}}})$
satisfying

$\displaystyle R_{\text{s}}\\!\geq
I(U;\widetilde{X}|Z)+[I(U;Z|V,Q)-I(U;Y|V,Q)]^{-}$ (14) $\displaystyle
R_{\text{w}}\\!\geq\\!I(U;\widetilde{X}|Y)$ (15) $\displaystyle
R_{\ell,\text{Dec}}\\!\geq\\!I(U;X|Y)$ (16) $\displaystyle
R_{\ell,\text{Eve}}\\!\geq\\!I(U;X|Z)\\!+\\![I(U;Z|V,Q)\\!-\\!I(U;Y|V,Q)]^{-}$
(17)

such that $U$ is admissible for the function $f(\widetilde{X},Y)$ and
$(Q,V)-U-\widetilde{X}-X-(Y,Z)$ form a Markov chain. The region $\mathcal{R}$
is convexified by using the time-sharing random variable $Q$, which is
required because of the $[\cdot]^{-}$ operation. One can limit the
cardinalities of $Q$, $V$, and $U$ to $|\mathcal{Q}|\leq 2$,
$|\mathcal{V}|\leq|\widetilde{X}|+4$, and
$|\mathcal{U}|\leq(|\widetilde{X}|+4)^{2}$.

In [25], some lower bounds on the rates in the rate regions include terms with
the maximization operator $[\cdot]^{+}$. One can show that the rate regions in
[25] that include such lower bounds are not convex and can be enlarged by
using a time-sharing random variable $Q$, as considered in this work.

###  III-B Lossy Single-Function Computation

We next characterize the lossy region $\mathcal{R}_{D}$ for the lossy single
function computation problem in Theorem 2.

######  Theorem 2.

The _lossy_ region $\mathcal{R}_{D}$ is the set of all tuples
$(R_{\text{s}},R_{\text{w}},R_{\ell,{\text{Dec}}},R_{\ell,{\text{Eve}}},D)$
satisfying

$\displaystyle R_{\text{s}}\\!\geq
I(U;\widetilde{X}|Z)+[I(U;Z|V,Q)-I(U;Y|V,Q)]^{-}$ (18) $\displaystyle
R_{\text{w}}\\!\geq\\!I(U;\widetilde{X}|Y)$ (19) $\displaystyle
R_{\ell,\text{Dec}}\\!\geq\\!I(U;X|Y)$ (20) $\displaystyle
R_{\ell,\text{Eve}}\\!\geq\\!I(U;X|Z)\\!+\\![I(U;Z|V,Q)\\!-\\!I(U;Y|V,Q)]^{-}$
(21) $\displaystyle D\geq\mathbb{E}[d(f(\widetilde{X},Y),g(U,Y))]$ (22)

for some function $g(\cdot,\cdot)$ such that $(Q,V)-U-\widetilde{X}-X-(Y,Z)$
form a Markov chain. One can limit the cardinalities to $|\mathcal{Q}|\leq 2$,
$|\mathcal{V}|\leq|\widetilde{X}|+5$, and
$|\mathcal{U}|\leq(|\widetilde{X}|+5)^{2}$.

###### Proof:

The achievability proof of Theorem 2 follows from the achievability proof of
Theorem 1, except that $U$ is not necessarily admissible, and with the
addition that $P_{U|\widetilde{X}}$ and $P_{V|U}$ are chosen such that there
exists a function $g(U,Y)$ that satisfies
$g^{n}(U^{n},Y^{n})=\\{g(U_{i},Y_{i})\\}_{i=1}^{n}$ and
$\mathbb{E}[d(f^{n}(\widetilde{X}^{n},Y^{n}),g^{n}(U^{n},Y^{n}))]\leq
D+\epsilon_{n}$, where $\epsilon_{n}>0$ such that $\epsilon_{n}\rightarrow 0$
when $n\rightarrow\infty$. Since all sequence tuples
$(\widetilde{x}^{n},y^{n},u^{n})$ are in the jointly typical set with high
probability, by the typical average lemma [34, pp. 26], the distortion
constraint (22) is satisfied. The converse proof follows from the converse
proof of Theorem 1 by replacing the admissibility step in (81) with the steps

$\displaystyle
D+\delta_{n}\geq\mathbb{E}\Big{[}d\left(f^{n}(\widetilde{X}^{n},Y^{n}),\widehat{f^{n}}(W,Y^{n})\right)\Big{]}$
$\displaystyle=\frac{1}{n}\mathbb{E}\Big{[}\sum_{i=1}^{n}d\left(f_{i}(\widetilde{X}_{i},Y_{i}),\widehat{f_{i}}(W,Y^{n})\right)\Big{]}$
$\displaystyle\overset{(a)}{\geq}\frac{1}{n}\mathbb{E}\Big{[}\sum_{i=1}^{n}d\left(f_{i}(\widetilde{X}_{i},Y_{i}),g_{i}(W,Y^{n},X^{i-1},Z^{i-1},i)\right)\Big{]}$
$\displaystyle\overset{(b)}{=}\frac{1}{n}\mathbb{E}\Big{[}\sum_{i=1}^{n}d\left(f_{i}(\widetilde{X}_{i},Y_{i}),g_{i}(W,Y_{i}^{n},X^{i-1},Z^{i-1},i)\right)\Big{]}$
$\displaystyle\overset{(c)}{=}\frac{1}{n}\mathbb{E}\Big{[}\sum_{i=1}^{n}d\left(f(\widetilde{X}_{i},Y_{i}),g(U_{i},i,Y_{i})\right)\Big{]}$
(23)

where $(a)$ follows since there exists a function $g_{i}(\cdot,\cdot)$ that
results in a distortion smaller than or equal to the distortion obtained from
$\widehat{f_{i}}(W,Y^{n})$, where the distortion is measured with respect to
$f_{i}(\widetilde{X}_{i},Y_{i})$ for all $i\\!\in\\![1\\!:\\!n]$, because
$g_{i}(\cdot,\cdot)$ has additional inputs, $(b)$ follows from the Markov
chain $Y^{i-1}-(X^{i-1},Z^{i-1},W,Y_{i},Y_{i+1}^{n})-f_{i}$, and $(c)$ follows
from the definition of $U_{i}\triangleq(W,X^{i-1},Y^{n}_{i+1},Z^{i-1})$ given
in Section V-B. The cardinality bounds follow by preserving the same
probability and conditional entropy values as being preserved in Theorem 1
with the addition of preserving the value of $g(U,Y)=g(U,V,Y)$, following from
the Markov chain $V-(U,Y)-g(U,Y)$. The region $\mathcal{R}_{D}$ is convexified
by using a time-sharing random variable $Q$. ∎

All rate regions in [25, Section III] (and, naturally, all previous rate
regions recovered by manipulating the regions in [25, Section III]) can be
recovered from Theorems 1 and 2 by eliminating the remote source, i.e.,
assuming $\widetilde{X}^{n}=X^{n}$, and by rewriting the secrecy leakage
constraint in (3) as an equivocation measure rather than a mutual information.

###  III-C Lossless Multi-Function Computation

We provide inner and outer bounds for the multi-function region
$\mathcal{R}_{\text{mf}}$ defined in Section II-C in Theorem 3. The
corresponding proof is detailed in Section VI.

######  Theorem 3.

_(Inner Bound):_ An achievable multi-function region is the union over all
$P_{U_{j}|\widetilde{X}_{j}}$ and $P_{V_{j}|U_{j}}$ such that $U_{j}$ is
admissible for the function $f_{j}(\widetilde{X}_{j},Y_{j})$ for all
$j\in[1:J]$ of the rate tuples
$(R_{\text{s}},R_{\text{w},[1:J]},R_{\ell,{\text{Dec}},[1:J]},R_{\ell,{\text{Eve}}})$
satisfying

$\displaystyle
R_{\text{s}}\\!\geq\\![I(U_{[1:J]};Z_{[1:J]}|V_{[1:J]},Q)\\!-\\!I(U_{[1:J]};Y_{[1:J]}|V_{[1:J]},Q)]^{-}\\!$
$\displaystyle\qquad\qquad\quad\\!+\\!I(U_{[1:J]};\widetilde{X}_{[1:J]}|Z_{[1:J]})$
(24) $\displaystyle
R_{\text{w},j}\\!\geq\\!I(U_{j};\widetilde{X}_{j}|Y_{j}),\qquad\qquad\qquad\qquad\forall
j\in[1:J]$ (25) $\displaystyle\sum_{j=1}^{J}R_{\text{w},j}\geq
I(U_{[1:J]};\widetilde{X}_{[1:J]}|Y_{[1:J]})$ (26) $\displaystyle
R_{\ell,\text{Dec},j}\\!\geq\\!I(U_{j};X|Y_{j}),\,\qquad\qquad\quad\qquad\forall
j\in[1:J]$ (27)
$\displaystyle\\!R_{\ell,\text{Eve}}\\!\geq\\![I(U_{[1:J]};Z_{[1:J]}|V_{[1:J]},Q)\\!-\\!I(U_{[1:J]};Y_{[1:J]}|V_{[1:J]},Q)]^{-}\\!$
$\displaystyle\qquad\qquad\quad\\!+\\!I(U_{[1:J]};X|Z_{[1:J]})$ (28)

where we have

$\displaystyle
P_{QV_{[1:J]}U_{[1:J]}\widetilde{X}_{[1:J]}XY_{[1:J]}Z_{[1:J]}}$
$\displaystyle\qquad=P_{Q}P_{X}\prod_{j=1}^{J}P_{V_{j}|U_{j}}P_{U_{j}|\widetilde{X}_{j}}P_{\widetilde{X}_{j}|X}P_{Y_{j}Z_{j}|X}.$
(29)

_(Outer Bound):_ An outer bound for the multi-function region
$\mathcal{R}_{\text{mf}}$ is the union of the rate tuples in (24)-(28) over
all $P_{U_{j}|\widetilde{X}_{j}}$ and $P_{V_{j}|U_{j}}$ such that $U_{j}$ is
admissible for the function $f_{j}(\widetilde{X}_{j},Y_{j})$ and
$(Q,V_{j})-U_{j}-\widetilde{X}_{j}-X-(Y_{j},Z_{j})$ form a Markov chain for
all $j\in[1:J]$. One can limit the cardinalities to $|\mathcal{Q}|\leq 2$,
$|\mathcal{V}_{j}|\leq|\widetilde{X}_{j}|+5$, and
$|\mathcal{U}_{j}|\leq(|\widetilde{X}_{j}|+5)^{2}$ for all $j\in[1:J]$.

######  Remark 2.

The inner and outer bounds differ because the outer bounds define rate regions
for the Markov chains $(Q,V_{j})-U_{j}-\widetilde{X}_{j}-X-(Y_{j},Z_{j})$ for
all $j\in[1:J]$, which are larger than the rate regions defined by the inner
bounds that satisfy (29).

###  III-D Lossy Multi-Function Computation

We next give inner and outer bounds for the lossy multi-function region
$\mathcal{R}_{\text{mf,D}}$, defined in Section II-D, in Theorem 4.

######  Theorem 4.

_(Inner Bound):_ An achievable lossy multi-function region is the union over
all $P_{U_{j}|\widetilde{X}_{j}}$ and $P_{V_{j}|U_{j}}$ for all $j\in[1:J]$ of
the rate tuples
$(R_{\text{s}},R_{\text{w},[1:J]},R_{\ell,{\text{Dec}},[1:J]},R_{\ell,{\text{Eve}}},D_{[1:J]})$
satisfying

$\displaystyle
R_{\text{s}}\\!\geq\\![I(U_{[1:J]};Z_{[1:J]}|V_{[1:J]},Q)\\!-\\!I(U_{[1:J]};Y_{[1:J]}|V_{[1:J]},Q)]^{-}\\!$
$\displaystyle\qquad\qquad\quad\\!+\\!I(U_{[1:J]};\widetilde{X}_{[1:J]}|Z_{[1:J]})$
(30) $\displaystyle
R_{\text{w},j}\\!\geq\\!I(U_{j};\widetilde{X}_{j}|Y_{j}),\qquad\qquad\qquad\qquad\forall
j\in[1:J]$ (31) $\displaystyle\sum_{j=1}^{J}R_{\text{w},j}\geq
I(U_{[1:J]};\widetilde{X}_{[1:J]}|Y_{[1:J]})$ (32) $\displaystyle
R_{\ell,\text{Dec},j}\\!\geq\\!I(U_{j};X|Y_{j}),\,\qquad\qquad\quad\qquad\forall
j\in[1:J]$ (33)
$\displaystyle\\!R_{\ell,\text{Eve}}\\!\geq\\![I(U_{[1:J]};Z_{[1:J]}|V_{[1:J]},Q)\\!-\\!I(U_{[1:J]};Y_{[1:J]}|V_{[1:J]},Q)]^{-}\\!$
$\displaystyle\qquad\qquad\quad\\!+\\!I(U_{[1:J]};X|Z_{[1:J]})$ (34)
$\displaystyle
D_{j}\geq\mathbb{E}[d(f_{j}(\widetilde{X}_{j},Y_{j}),g_{j}(U_{j},Y_{j}))]\;\;\;\qquad\forall
j\in[1:J]$ (35)

for a set of functions $\\{g_{j}(\cdot,\cdot)\\}_{j=1}^{J}$ and where (29) is
satisfied.

_(Outer Bound):_ An outer bound for the lossy multi-function region
$\mathcal{R}_{\text{mf,D}}$ is the union of the rate tuples in (30)-(35) over
all $P_{U_{j}|\widetilde{X}_{j}}$ and $P_{V_{j}|U_{j}}$ such that
$(Q,V_{j})-U_{j}-\widetilde{X}_{j}-X-(Y_{j},Z_{j})$ form a Markov chain for
all $j\in[1:J]$. One can limit the cardinalities to $|\mathcal{Q}|\leq 2$,
$|\mathcal{V}_{j}|\leq|\widetilde{X}_{j}|~{}+~{}6$, and
$|\mathcal{U}_{j}|\leq(|\widetilde{X}_{j}|+6)^{2}$ for all $j\in[1:J]$.

###### Proof:

The inner bound proof of Theorem 4 follows from the achievability proof of
Theorem 3, except that $U_{j}$’s are not necessarily admissible, and with the
addition that $P_{U_{j}|\widetilde{X}_{j}}$ and $P_{V_{j}|U_{j}}$ are chosen
such that there exists a set of functions $\\{g_{j}(U_{j},Y_{j})\\}_{j=1}^{J}$
that satisfy
$g^{n}_{j}(U_{j}^{n},Y_{j}^{n})=\\{g_{j}(U_{i,j},Y_{i,j})\\}_{i=1}^{n}$ and
$\mathbb{E}[d(f^{n}_{j}(\widetilde{X}^{n}_{j},Y^{n}_{j}),g^{n}_{j}(U^{n}_{j},Y^{n}_{j}))]\leq
D_{j}+\epsilon_{n}$ for all $j\in[1:J]$, where $\epsilon_{n}>0$ such that
$\epsilon_{n}\rightarrow 0$ when $n\rightarrow\infty$. Since all sequence
tuples $(\widetilde{x}_{j}^{n},y_{j}^{n},u_{j}^{n})$ are in the jointly
typical set with high probability for all $j\in[1:J]$, by the typical average
lemma, the distortion constraints in (35) are satisfied. The outer bound proof
of Theorem 4 follows from the converse proof of Theorem 3 with the replacement
of the admissibility step in (108) with the steps given in (23) for random
variables and functions with the indices $j=1,2,\ldots,J$. ∎

##  IV Information Bottleneck Example

Consider the lossy single-function computation problem and suppose $X-Y-Z$
form a Markov chain. The characterization of the corresponding rate region
requires one to maximize a mutual information term upper bounded by another
mutual information term that should be minimized simultaneously, i.e., an
information bottleneck.

######  Corollary 1.

The lossy region of Theorem 2 when $X-Y-Z$ form a Markov chain is the set of
all tuples
$(R_{\text{s}},R_{\text{w}},R_{\ell,{\text{Dec}}},R_{\ell,{\text{Eve}}},D)$
satisfying

$\displaystyle R_{\text{s}}\\!\geq
I(U;\widetilde{X}|Y)=I(U;\widetilde{X})-I(U;Y)$ (36) $\displaystyle
R_{\text{w}}\\!\geq\\!I(U;\widetilde{X}|Y)=I(U;\widetilde{X})-I(U;Y)$ (37)
$\displaystyle R_{\ell,\text{Dec}}\\!\geq\\!I(U;X|Y)=I(U;X)-I(U;Y)$ (38)
$\displaystyle R_{\ell,\text{Eve}}\\!\geq\\!I(U;X|Y)=I(U;X)-I(U;Y)$ (39)
$\displaystyle D\geq\mathbb{E}[d(f(\widetilde{X},Y),g(U,Y))]$ (40)

for some function $g(\cdot,\cdot)$ such that $U-\widetilde{X}-X-Y-Z$ form a
Markov chain. One can limit the cardinality to
$|\mathcal{U}|\leq|\widetilde{X}|+2$.

The proof of Corollary 1 follows by applying steps identical to the proof of
[25, Corollary 3] to Theorem 2; therefore, we omit it. The boundary points of
the rate region defined in Corollary 1 can be obtained by maximizing $I(U;Y)$
and minimizing $I(U;\widetilde{X})$ simultaneously for a fixed $I(U;X)$ for
all $P_{U|\widetilde{X}}$ such that $U-\widetilde{X}-X-Y-Z$ form a Markov
chain. This problem is an information bottleneck problem [35, 36]. If the
distortion metric $d(\cdot,\cdot)$ is chosen to be the Hamming distance, we
then obtain the optimal function $g^{*}(u,y)$ for all
$(u,y)\\!\in\\!\mathcal{U}\\!\times\\!\mathcal{Y}$ as [25, Eq. (26)]

$\displaystyle g^{*}(u,y)=\arg\max_{f}P_{F|UY}(f|u,y)$ (41)

where $f=f(\widetilde{x},y)$ is a realization of the random function output
$F$ for any $(\widetilde{x},y)\in\mathcal{\widetilde{X}}\times\mathcal{Y}$.

Consider a measurement channel $P_{\widetilde{X}|X}$ and source $P_{X}$ for
the encoder $\mathsf{Enc}(\cdot)$ such that the inverse channel
$P_{X|\widetilde{X}}$ is a BSC$(p)$ for any $0\leq p\leq 0.5$. Furthermore,
suppose the measurement channel $P_{Y|X}$ for the decoder
$\mathsf{Dec}(\cdot)$ is a binary input symmetric output channel [37, p. 21],
which can be decomposed into a mixture of binary subchannels as defined in
[38, Section III-B] [39]. We remark that the rate region defined in Corollary
1 by (36)-(40) does not depend on the random variable $Z$. Therefore, the
measurement channel for the eavesdropper does not affect the rate region as
long as the measurement channel for the eavesdropper is physically-degraded as
compared to the channel for the decoder $\mathsf{Dec}(\cdot)$, i.e.,
$P_{YZ|X}=P_{Z|Y}P_{Y|X}$. Since $P_{\widetilde{X}XYZ}$ is fixed, the optimal
auxiliary random variable $U$ is such that $P_{\widetilde{X}|U}$ is a BSC with
crossover probability

$\displaystyle\frac{H_{b}^{-1}(H(X|U))-p}{1-2p}$ (42)

which follows from [27, Theorem 3].

$0$$0.1$$0.2$$0.3$$0.4$$0$$0.05$$0.1$$0.15$$0.2$$0.25$$0.3$Secrecy-leakage
Rate (bits/symbol)PrivacyEve-leakage Rate (bits/symbol)M=1M=2M=3 Figure 3:
Secrecy-leakage rate vs. privacyEve-leakage rate projection of the boundary
tuples
$(R_{\text{s}},R_{\text{w}},R_{\ell,{\text{Dec}}},R_{\ell,{\text{Eve}}},D)$
for $p=0.06$ and for the number of independent BSC measurements at the decoder
$M=1,2,3$.

Suppose $P_{X}\\!\sim\\!\text{Bern}(0.5)$,
$P_{\widetilde{X}|X}\\!\sim\\!\text{BSC}(p\\!=\\!0.06)$, and assume that the
measurement channel $P_{Y|X}$ consists of $M>1$ independent BSCs each with
crossover probability $0.15$, which satisfies the assumptions listed above.
Using auxiliary random variables satisfying (42), we depict the projections of
$(R_{\text{s}},R_{\text{w}},R_{\ell,{\text{Dec}}},R_{\ell,{\text{Eve}}},D)$
boundary tuples onto the $(R_{\text{s}},R_{\ell,{\text{Eve}}})$ plane in Fig.
3 for $M=1,2,3$ independent BSC measurements by the decoder
$\mathsf{Dec}(\cdot)$.

Fig. 3 suggests that given a boundary point achieved by a crossover
probability calculated as in (42), any larger secrecy-leakage rate and any
larger privacyEve-leakage rate are also achievable. Conversely, given such an
achievable boundary point, no smaller secrecy-leakage rate and no smaller
privacyEve-leakage rate is achievable. Furthermore, increasing the number $M$
of measurements at the decoder significantly decreases the corresponding
boundary point such that, e.g., when $M=3$ measurements are used as compared
to $M=1$, the maximum secrecy-leakage rate decreases by approximately
$31.45\%$ and simultaneously the maximum privacy-leakage rate to the
eavesdropper decreases by approximately $58.68\%$. These gains can be seen as
multiplexing gains, in analogy to multiple antenna systems for wireless
communications.

##  V Proof of Theorem 1

###  V-A Achievability Proof of Theorem 1

###### Proof:

We use the output statistics of random binning (OSRB) method, proposed in [40]
(see also [41]) for strong secrecy by following steps in [42, Section 1.6].
This approach simplifies the analysis compared to previous proofs in the
literature.

Fix $P_{U|\widetilde{X}}$ and $P_{V|U}$ such that $U$ is admissible and let
$(V^{n},U^{n},\widetilde{X}^{n},X^{n},Y^{n},Z^{n})$ be i.i.d. according to
$P_{VU\widetilde{X}XYZ}=P_{V|U}P_{U|\widetilde{X}}P_{\widetilde{X}|X}P_{X}P_{YZ|X}$.
We remark that since all $n$-letter random variables are i.i.d., $U^{n}$ is
also admissible.

Assign two random bin indices $(F_{\text{v}},W_{\text{v}})$ to each $v^{n}$.
Assume $F_{\text{v}}\in[1:2^{n\widetilde{R}_{\text{v}}}]$ and
$W_{\text{v}}\in[1:2^{nR_{\text{v}}}]$. Similarly, assign two indices
$(F_{\text{u}},W_{\text{u}})$ to each $u^{n}$, where
$F_{\text{u}}\in[1:2^{n\widetilde{R}_{\text{u}}}]$ and
$W_{\text{u}}\in[1:2^{nR_{\text{u}}}]$. The public message is
$W=(W_{\text{v}},W_{\text{u}})$ and the indices
$F=(F_{\text{v}},F_{\text{u}})$ represent the public choice of encoder-decoder
pairs.

Using a Slepian-Wolf (SW) [5] decoder one can reliably estimate $V^{n}$ from
$(F_{\text{v}},W_{\text{v}},Y^{n})$, such that the expected value of the error
probability taken over the random bin assignments vanishes when
$n\rightarrow\infty$, if we have [43, Lemma 1]

$\displaystyle\widetilde{R}_{\text{v}}+R_{\text{v}}>H(V|Y).$ (43)

Similarly, one can reliably estimate $U^{n}$ from
$(F_{\text{u}},W_{\text{u}},Y^{n},V^{n})$ by using a SW decoder if we have

$\displaystyle\widetilde{R}_{\text{u}}+R_{\text{u}}>H(U|V,Y).$ (44)

Thus, the reliability constraint in (2) is satisfied if (43) and (44) are
satisfied.

The public index $F_{\text{v}}$ is almost independent of $\widetilde{X}^{n}$,
so it is almost independent of $(\widetilde{X}^{n},X^{n},Y^{n},Z^{n})$, if we
have [43, Theorem 1]

$\displaystyle\widetilde{R}_{\text{v}}<H(V|\widetilde{X})$ (45)

since it results in the expected value, which is taken over the random bin
assignments, of the variational distance between the joint probability
distributions
$\text{Unif}[1\\!\\!:\\!|\mathcal{F}_{\text{v}}|]\cdot\text{Unif}[1\\!\\!:\\!\\!|\mathcal{\widetilde{X}}|^{n}]$
and $P_{F_{\text{v}}\widetilde{X}^{n}}$ to vanish when $n\rightarrow\infty$.
Furthermore, the public index $F_{\text{u}}$ is almost independent of
$(V^{n},\widetilde{X}^{n})$, so it is almost independent of
$(V^{n},\widetilde{X}^{n},X^{n},Y^{n},Z^{n})$, if we have

$\displaystyle\widetilde{R}_{\text{u}}<H(U|V,\widetilde{X}).$ (46)

To satisfy the constraints (43)-(46), we fix the rates to

$\displaystyle\widetilde{R}_{\text{v}}=H(V|\widetilde{X})-\epsilon$ (47)
$\displaystyle R_{\text{v}}=I(V;\widetilde{X})-I(V;Y)+2\epsilon$ (48)
$\displaystyle\widetilde{R}_{\text{u}}=H(U|V,\widetilde{X})-\epsilon$ (49)
$\displaystyle R_{\text{u}}=I(U;\widetilde{X}|V)-I(U;Y|V)+2\epsilon$ (50)

for any $\epsilon>0$.

Storage (Public Message) Rate: (47)-(50) result in a storage (public message)
rate $R_{\text{w}}$ of

$\displaystyle
R_{\text{w}}=R_{\text{v}}+R_{\text{u}}=I(V,U;\widetilde{X})-I(V,U;Y)+4\epsilon$
$\displaystyle\;\overset{(a)}{=}I(U;\widetilde{X}|Y)+4\epsilon$ (51)

where $(a)$ follows because $V-U-\widetilde{X}-Y$ form a Markov chain.

Privacy Leakage to the Decoder: We have

$\displaystyle I(X^{n};W,F|Y^{n})=I(X^{n};W|F,Y^{n})+I(X^{n};F|Y^{n})$
$\displaystyle\;\overset{(a)}{\leq}H(X^{n}|Y^{n})-H(X^{n}|W,F,V^{n},U^{n},Y^{n})+2\epsilon_{n}$
$\displaystyle\;\overset{(b)}{=}H(X^{n}|Y^{n})-H(X^{n}|U^{n},Y^{n})+2\epsilon_{n}$
$\displaystyle\;\overset{(c)}{=}nI(U;X|Y)+2\epsilon_{n}$ (52)

where $(a)$ follows for some $\epsilon_{n}>0$ with $\epsilon_{n}\rightarrow 0$
when $n\rightarrow\infty$ because

$\displaystyle
I(X^{n};F|Y^{n})=I(X^{n};F_{\text{v}}|Y^{n})+I(X^{n};F_{\text{u}}|F_{\text{v}},Y^{n})$
$\displaystyle\;\leq 2\epsilon_{n}$ (53)

since by (45) $F_{v}$ is almost independent of
$(\widetilde{X}^{n},X^{n},Y^{n},Z^{n})$ and by (46) $F_{u}$ is almost
independent of $(V^{n},\widetilde{X}^{n},X^{n},Y^{n},Z^{n})$ and because
$V^{n}$ determines $F_{v}$, $(b)$ follows because $V^{n}$ determines
$(F_{v},W_{v})$, $U^{n}$ determines $(F_{u},W_{u})$, and
$V^{n}-U^{n}-(X^{n},Y^{n})$ form a Markov chain, and $(c)$ follows because
$(X^{n},U^{n},Y^{n})$ are i.i.d.

Privacy Leakage to the Eavesdropper: We obtain

$\displaystyle I(X^{n};W,F|Z^{n})\overset{(a)}{=}H(W,F|Z^{n})-H(W,F|X^{n})$
$\displaystyle\;\overset{(b)}{=}H(W,F|Z^{n})-H(W_{u},F_{u},V^{n}|X^{n})$
$\displaystyle\qquad+H(V^{n}|W_{v},F_{v},W_{u},F_{u},X^{n})$
$\displaystyle\;\overset{(c)}{\leq}H(W,F|Z^{n})-H(W_{u},F_{u},V^{n}|X^{n})+n\epsilon^{\prime}_{n}$
$\displaystyle\;\overset{(d)}{=}H(W,F|Z^{n})-H(U^{n},V^{n}|X^{n})$
$\displaystyle\qquad+H(U^{n}|W_{u},F_{u},V^{n},X^{n})+n\epsilon^{\prime}_{n}$
$\displaystyle\;\overset{(e)}{\leq}H(W,F|Z^{n})-H(U^{n},V^{n}|X^{n})+2n\epsilon^{\prime}_{n}$
$\displaystyle\;\overset{(f)}{=}H(W,F|Z^{n})-nH(U,V|X)+2n\epsilon^{\prime}_{n}$
(54)

where $(a)$ follows because $(W,F)-X^{n}-Z^{n}$ form a Markov chain, $(b)$
follows since $V^{n}$ determines $(F_{v},W_{v})$, $(c)$ follows for some
$\epsilon^{\prime}_{n}>0$ such that $\epsilon^{\prime}_{n}\rightarrow 0$ when
$n\rightarrow\infty$ because $(F_{v},W_{v},X^{n})$ can reliably recover
$V^{n}$ due to the Markov chain $V^{n}-X^{n}-Y^{n}$ and by (43), $(d)$ follows
because $U^{n}$ determines $(F_{u},W_{u})$, $(e)$ follows by (44) because
$(W_{u},F_{u},V^{n},X^{n})$ can reliably recover $U^{n}$ due to the inequality
$H(U|V,Y)\geq H(U|V,X)$ that follows from

$\displaystyle H(U|V,Y)-H(U|V,X)=I(U;V,X)-I(U;V,Y)$ $\displaystyle\;\geq
I(U;V,X)-I(U;V,Y,X)=0$ (55)

since $(V,U)-X-Y$ form a Markov chain, and $(f)$ follows because
$(U^{n},V^{n},X^{n})$ are i.i.d.

We need to analyze six different decodability cases to consider whether
$(F_{v},W_{v},Z^{n})$ can recover $V^{n}$ and whether
$(F_{u},W_{u},V^{n},Z^{n})$ or $(F_{u},W_{u},Z^{n})$ can recover $U^{n}$.

_Case 1_ : Assume

$\displaystyle 0\leq$
$\displaystyle\;R_{\text{v}}+\widetilde{R}_{\text{v}}<H(V|Z),$ (56)
$\displaystyle 0\leq$
$\displaystyle\;R_{\text{u}}+\widetilde{R}_{\text{u}}<H(U|V,Z)$ (57)

so that $(F_{v},W_{v})$ are almost independent of $Z^{n}$ and are also almost
mutually independent, and $(F_{u},W_{u})$ are almost independent of
$(V^{n},Z^{n})$ and are also almost mutually independent. Using (54), we
obtain

$\displaystyle I(X^{n};W,F|Z^{n})$
$\displaystyle\leq\\!H(W_{v})\\!+\\!H(F_{v})\\!+\\!H(W_{u})\\!+\\!H(F_{u})\\!-\\!nH(U,V|X)\\!+\\!2n\epsilon^{\prime}_{n}$
$\displaystyle\leq
n(R_{\text{v}}+\widetilde{R}_{\text{v}}+R_{\text{u}}+\widetilde{R}_{\text{u}})\\!-\\!nH(U,V|X)\\!+\\!2n\epsilon^{\prime}_{n}$
$\displaystyle\overset{(a)}{=}n(I(U,V;X)-I(U,V;Y)+2\epsilon+2\epsilon^{\prime}_{n})$
$\displaystyle\overset{(b)}{=}n(I(U;X)-I(U;Y|V)-I(V;Y)+2\epsilon+2\epsilon^{\prime}_{n})$
$\displaystyle\overset{(c)}{\leq}n(I(U;X)-I(U;Y|V)-I(V;Z)+\epsilon+2\epsilon^{\prime}_{n})$
$\displaystyle\overset{(d)}{=}\\!n(I(U;X)\\!-\\![I(U;Y|V)\\!-\\!I(U;Z|V)]\\!-\\!I(U;Z)\\!+\\!\epsilon\\!+\\!2\epsilon^{\prime}_{n})$
$\displaystyle\overset{(e)}{=}\\!\\!n(I(U;X|Z)\\!+\\![I(U;Z|V)\\!-\\!I(U;Y|V)\\!+\\!\epsilon]^{-}\\!+\\!2\epsilon^{\prime}_{n})$
(58)

where $(a)$ follows by (47)-(50) and $(b)$ follows from the Markov chain
$V-U-X$, $(c)$ follows by (47), (48), and (56) such that equality is achieved
when $n\rightarrow\infty$, $(d)$ follows from the Markov chain $V-U-Z$, and
$(e)$ follows from the Markov chain $U-X-Z$.

_Case 2_ : Assume

$\displaystyle 0\leq$
$\displaystyle\;R_{\text{v}}+\widetilde{R}_{\text{v}}<H(V|Z),$ (59)
$\displaystyle H(U|V,Z)<$
$\displaystyle\;R_{\text{u}}+\widetilde{R}_{\text{u}}<H(U|Z)$ (60)

so that $(F_{v},W_{v})$ are almost independent of $Z^{n}$ and are also almost
mutually independent, and $(F_{u},W_{u})$ are almost independent of $Z^{n}$
and are also almost mutually independent; however, $(F_{u},W_{u},V^{n},Z^{n})$
can reliably recover $U^{n}$. Using (54), we have

$\displaystyle I(X^{n};W,F|Z^{n})$
$\displaystyle\\!\overset{(a)}{\leq}H(U^{n},V^{n}|Z^{n})\\!-\\!nH(U,V|X)\\!+\\!2n\epsilon^{\prime}_{n}$
$\displaystyle\\!\overset{(b)}{=}\\!n(I(U;X|Z)\\!+\\![I(U;Z|V)\\!-\\!I(U;Y|V)\\!+\\!\epsilon]^{-}\\!+\\!2\epsilon_{n}^{\prime})$
(61)

where $(a)$ follows because $V^{n}$ determines $(F_{v},W_{v})$ and $U^{n}$
determines $(F_{u},W_{u})$, and $(b)$ follows because $(V^{n},U^{n},Z^{n})$
are i.i.d., from the Markov chain $V-U-X-Z$, and by (49), (50), and (60).

_Case 3_ : Assume

$\displaystyle 0\leq$
$\displaystyle\;R_{\text{v}}+\widetilde{R}_{\text{v}}<H(V|Z),$ (62)
$\displaystyle H(U|Z)<$ $\displaystyle\;R_{\text{u}}+\widetilde{R}_{\text{u}}$
(63)

so that $(F_{v},W_{v})$ are almost independent of $Z^{n}$ and are also almost
mutually independent, and $(F_{u},W_{u},Z^{n})$ can reliably recover $U^{n}$.
Using (54), we obtain

$\displaystyle I(X^{n};W,F|Z^{n})$
$\displaystyle\\!\overset{(a)}{\leq}H(U^{n}|Z^{n})\\!+\\!H(W_{v},F_{v}|U^{n},Z^{n})\\!-\\!nH(U,V|X)\\!+\\!2n\epsilon^{\prime}_{n}$
$\displaystyle\\!\overset{(b)}{\leq}H(U^{n}|Z^{n})\\!+\\!H(V^{n}|U^{n},Z^{n})\\!-\\!nH(U,V|X)\\!+\\!2n\epsilon^{\prime}_{n}$
$\displaystyle\\!\overset{(c)}{=}n(I(U;X|Z)\\!+\\!2\epsilon^{\prime}_{n})$
$\displaystyle\\!\overset{(d)}{=}\\!n(I(U;X|Z)\\!+\\![I(U;Z|V)\\!-\\!I(U;Y|V)\\!+\\!\epsilon]^{-}\\!+\\!\\!2\epsilon^{\prime}_{n})$
(64)

where $(a)$ follows because $U^{n}$ determines $(F_{u},W_{u})$, $(b)$ follows
since $V^{n}$ determines $(F_{v},W_{v})$, $(c)$ follows from the Markov chain
$V-U-X-Z$ and because $(V^{n},U^{n},X^{n},Z^{n})$ are i.i.d., and $(d)$
follows by (49), (50), and (63).

_Case 4_ : Assume

$\displaystyle H(V|Z)<$
$\displaystyle\;R_{\text{v}}+\widetilde{R}_{\text{v}},$ (65) $\displaystyle
0\leq$ $\displaystyle\;R_{\text{u}}+\widetilde{R}_{\text{u}}<H(U|V,Z)$ (66)

so that $(F_{v},W_{v},Z^{n})$ can reliably recover $V^{n}$, and
$(F_{u},W_{u})$ are almost independent of $(V^{n},Z^{n})$ and are also almost
mutually independent. Using (54), we have

$\displaystyle I(X^{n};W,F|Z^{n})$
$\displaystyle\overset{(a)}{\leq}H(V^{n}|Z^{n})+H(W_{u},F_{u}|W_{v},F_{v},Z^{n})$
$\displaystyle\qquad-nH(U,V|X)+2n\epsilon^{\prime}_{n}$ $\displaystyle\leq
H(V^{n}|Z^{n})+H(W_{u})+H(F_{u})-nH(U,V|X)+2n\epsilon^{\prime}_{n}$
$\displaystyle\leq
n(H(V|Z)+R_{\text{u}}+\widetilde{R}_{\text{u}}-H(U,V|X)+2\epsilon^{\prime}_{n})$
$\displaystyle\overset{(b)}{=}n(H(V|Z)+H(U|V,Y)+\epsilon-H(U,V|X)+2\epsilon^{\prime}_{n})$
$\displaystyle=n(I(U;X|V)\\!-\\!I(U;Y|V)\\!+\\!I(V;X)\\!-\\!I(V;Z)\\!+\\!2\epsilon^{\prime}_{n}\\!+\\!\epsilon)$
$\displaystyle\overset{(c)}{=}n(I(U;X)-I(U;Y|V)-I(V;Z)+2\epsilon^{\prime}_{n}+\epsilon$
$\displaystyle\overset{(d)}{=}\\!n(I(U;X)\\!-\\![I(U;Y|V)\\!-\\!I(U;Z|V)]\\!-\\!I(U;Z)\\!+\\!\epsilon\\!+\\!2\epsilon^{\prime}_{n})$
$\displaystyle\overset{(e)}{=}\\!\\!n(I(U;X|Z)\\!+\\![I(U;Z|V)\\!-\\!I(U;Y|V)\\!+\\!\epsilon]^{-}\\!+\\!2\epsilon^{\prime}_{n})$
(67)

where $(a)$ follows because $V^{n}$ determines $(F_{v},W_{v})$, $(b)$ follows
because $(V^{n},Z^{n})$ are i.i.d. and by (49) and (50), $(c)$ follows from
the Markov chain $V-U-X$, $(d)$ follows from the Markov chain $V-U-Z$, and
$(e)$ follows from the Markov chain $U-X-Z$.

_Case 5_ : Assume

$\displaystyle H(V|Z)<$
$\displaystyle\;R_{\text{v}}+\widetilde{R}_{\text{v}},$ (68) $\displaystyle
H(U|V,Z)<$ $\displaystyle\;R_{\text{u}}+\widetilde{R}_{\text{u}}<H(U|Z)$ (69)

so that $(F_{v},W_{v},Z^{n})$ can reliably recover $V^{n}$, and
$(F_{u},W_{u})$ are almost independent of $Z^{n}$ and are also almost mutually
independent; however, $(F_{u},W_{u},V^{n},Z^{n})$ can reliably recover
$U^{n}$. Using (54), we have

$\displaystyle I(X^{n};W,F|Z^{n})$
$\displaystyle\overset{(a)}{\leq}H(V^{n}|Z^{n})+H(W_{u},F_{u}|W_{v},F_{v},Z^{n})$
$\displaystyle\qquad-nH(U,V|X)+2n\epsilon^{\prime}_{n}$
$\displaystyle\overset{(b)}{\leq}H(V^{n}|Z^{n})+H(W_{u},F_{u}|V^{n},Z^{n})+H(V^{n}|W_{v},F_{v},Z^{n})$
$\displaystyle\qquad-nH(U,V|X)+2n\epsilon^{\prime}_{n}$
$\displaystyle\overset{(c)}{\leq}H(V^{n}|Z^{n})+H(U^{n}|V^{n},Z^{n})-nH(U,V|X)+3n\epsilon^{\prime}_{n}$
$\displaystyle\overset{(d)}{=}n(I(U;X|Z)\\!+\\!3\epsilon^{\prime}_{n})$
$\displaystyle\overset{(e)}{=}\\!n(I(U;X|Z)\\!+\\![I(U;Z|V)\\!-\\!I(U;Y|V)\\!+\\!\epsilon]^{-}\\!+\\!\\!3\epsilon^{\prime}_{n})$
(70)

where $(a)$ and $(b)$ follow because $V^{n}$ determines $(F_{v},W_{v})$, $(c)$
follows because $U^{n}$ determines $(F_{u},W_{u})$ and by (68), $(d)$ follows
because $(V^{n},Z^{n},U^{n})$ are i.i.d. and from the Markov chain $V-U-X-Z$,
and $(e)$ follows by (49), (50), and (69).

_Case 6_ : Assume

$\displaystyle H(V|Z)<$
$\displaystyle\;R_{\text{v}}+\widetilde{R}_{\text{v}},$ (71) $\displaystyle
H(U|Z)<$ $\displaystyle\;R_{\text{u}}+\widetilde{R}_{\text{u}}$ (72)

so that $(F_{v},W_{v},Z^{n})$ can reliably recover $V^{n}$, and
$(F_{u},W_{u},Z^{n})$ can reliably recover $U^{n}$. Using (54), we obtain

$\displaystyle
I(X^{n};W,F|Z^{n})\overset{(a)}{\leq}H(V^{n},U^{n}|Z^{n})-nH(U,V|X)+2n\epsilon^{\prime}_{n}$
$\displaystyle\overset{(b)}{=}n(I(U;X|Z)+2\epsilon^{\prime}_{n})$
$\displaystyle\overset{(c)}{=}\\!n(I(U;X|Z)\\!+\\![I(U;Z|V)\\!-\\!I(U;Y|V)\\!+\\!\epsilon]^{-}\\!+\\!\\!2\epsilon^{\prime}_{n})$
(73)

where $(a)$ follows because $U^{n}$ determines $(F_{u},W_{u})$ and $V^{n}$
determines $(F_{v},W_{v})$, $(b)$ follows because $(V^{n},U^{n},Z^{n})$ are
i.i.d. and from the Markov chain $V-U-X-Z$, and $(c)$ follows by (49), (50),
and (72).

Secrecy Leakage (to the Eavesdropper): Consider the secrecy leakage. We have

$\displaystyle
I(\widetilde{X}^{n},Y^{n};W,F|Z^{n})\overset{(a)}{=}H(W,F|Z^{n})-H(W,F|\widetilde{X}^{n})$
$\displaystyle\;\overset{(b)}{\leq}H(W,F|Z^{n})-H(W_{u},F_{u},V^{n}|\widetilde{X}^{n})+n\epsilon^{\prime}_{n}$
$\displaystyle\;\overset{(c)}{\leq}H(W,F|Z^{n})-nH(U,V|\widetilde{X})+2n\epsilon^{\prime}_{n}$
(74)

where $(a)$ follows from the Markov chain
$(W,F)-\widetilde{X}^{n}-(Y^{n},Z^{n})$, $(b)$ follows since
$(W_{v},F_{v},\widetilde{X}^{n})$ can reliably recover $V^{n}$ due to the
Markov chain $V^{n}-\widetilde{X}^{n}-Y^{n}$ and (43), and $(c)$ follows by
(44) since $(W_{u},F_{u},V^{n},\widetilde{X}^{n})$ can reliably recover
$U^{n}$ due to the inequality $H(U|V,Y)\geq H(U|V,\widetilde{X})$ that can be
proved similarly as in (55), and because $(U^{n},V^{n},\widetilde{X}^{n})$ are
i.i.d.

Similar to the analysis of the privacy leakage to the eavesdropper, we need to
analyze the same six decodability cases to consider whether
$(F_{v},W_{v},Z^{n})$ can recover $V^{n}$ and whether
$(F_{u},W_{u},V^{n},Z^{n})$ or $(F_{u},W_{u},Z^{n})$ can recover $U^{n}$. One
can show that all steps applied in Cases 1-6 for the privacy leakage to the
eavesdropper follow also for the Cases 1-6 for the secrecy leakage by
replacing $X$ with $\widetilde{X}$. We; therefore, list the results for Cases
1-6 as follows.

Case 1: We obtain for (56) and (57) that

$\displaystyle I(\widetilde{X}^{n},Y^{n};W,F|Z^{n})$
$\displaystyle\\!\leq\\!n(I(U;\widetilde{X}|Z)\\!+\\![I(U;Z|V)\\!-\\!I(U;Y|V)\\!+\\!\epsilon]^{-}\\!\\!+\\!2\epsilon^{\prime}_{n}).$
(75)

Case 2: We obtain for (59) and (60) that

$\displaystyle I(\widetilde{X}^{n},Y^{n};W,F|Z^{n})$
$\displaystyle\\!\leq\\!n(I(U;\widetilde{X}|Z)\\!+\\![I(U;Z|V)\\!-\\!I(U;Y|V)\\!+\\!\epsilon]^{-}\\!\\!+\\!2\epsilon^{\prime}_{n}).$
(76)

Case 3: We obtain for (62) and (63) that

$\displaystyle I(\widetilde{X}^{n},Y^{n};W,F|Z^{n})$
$\displaystyle\\!\leq\\!n(I(U;\widetilde{X}|Z)\\!+\\![I(U;Z|V)\\!-\\!I(U;Y|V)\\!+\\!\epsilon]^{-}\\!+\\!\\!2\epsilon^{\prime}_{n}).$
(77)

Case 4: We obtain for (65) and (66) that

$\displaystyle I(\widetilde{X}^{n},Y^{n};W,F|Z^{n})$
$\displaystyle\\!\leq\\!n(I(U;\widetilde{X}|Z)\\!+\\![I(U;Z|V)\\!-\\!I(U;Y|V)\\!+\\!\epsilon]^{-}\\!+\\!\\!2\epsilon^{\prime}_{n}).$
(78)

Case 5: We obtain for (68) and (69) that

$\displaystyle I(\widetilde{X}^{n},Y^{n};W,F|Z^{n})$
$\displaystyle\\!\leq\\!\\!n(I(U;\widetilde{X}|Z)\\!+\\![I(U;Z|V)\\!-\\!I(U;Y|V)\\!+\\!\epsilon]^{-}\\!+\\!\\!3\epsilon^{\prime}_{n}).$
(79)

Case 6: We obtain for (71) and (72) that

$\displaystyle I(\widetilde{X}^{n},Y^{n};W,F|Z^{n})$
$\displaystyle\\!\leq\\!\\!n(I(U;\widetilde{X}|Z)\\!+\\![I(U;Z|V)\\!-\\!I(U;Y|V)\\!+\\!\epsilon]^{-}\\!+\\!\\!2\epsilon^{\prime}_{n}).$
(80)

Now assume that the public indices $F$ are generated uniformly at random. The
encoder $\mathsf{Enc}(\cdot)$ generates $(V^{n},U^{n})$ according to
$P_{V^{n}U^{n}|\widetilde{X}^{n}F_{\text{v}}F_{\text{u}}}$ obtained from the
binning scheme above to compute the bins $W_{\text{v}}$ from $V^{n}$ and
$W_{\text{u}}$ from $U^{n}$, respectively. This procedure induces a joint
probability distribution that is almost equal to $P_{VU\widetilde{X}XYZ}$
fixed above [42, Section 1.6]. We remark that the privacy and secrecy leakage
metrics considered above are expectations over all possible realizations
$F=f$. Thus, applying the selection lemma [44, Lemma 2.2] to each decodability
case separately, these results prove the achievability for Theorem 1 by
choosing an $\epsilon>0$ such that $\epsilon\rightarrow 0$ when
$n\rightarrow\infty$. ∎

###  V-B Converse Proof of Theorem 1

###### Proof:

Suppose for some $\delta_{n}\\!>\\!0$ and $n\geq 1$, there exists a pair of
encoders and decoders such that (2)-(6) are satisfied for some tuple
$(R_{\text{s}},R_{\text{w}},R_{\ell,{\text{Dec}}},R_{\ell,{\text{Eve}}})$.

Let $V_{i}\triangleq(W,Y^{n}_{i+1},Z^{i-1})$ and
$U_{i}\triangleq(W,X^{i-1},Y^{n}_{i+1},Z^{i-1})$, which satisfy the Markov
chain $V_{i}-U_{i}-\widetilde{X}_{i}-X_{i}-(Y_{i},Z_{i})$ for all $i\in[1:n]$
by definition of the source statistics.

Admissibility of $\mathbf{U}$: Define
$\epsilon_{n}\\!=\\!\delta_{n}|\mathcal{\widetilde{X}}||\mathcal{Y}|\\!+\\!H_{b}(\delta_{n})/n$,
where $H_{b}(\delta)=-\delta\log\delta-(1-\delta)\log(1-\delta)$ is the binary
entropy function, so that $\epsilon_{n}\\!\rightarrow\\!0$ if
$\delta_{n}\\!\rightarrow\\!0$. Using (2) and Fano’s inequality, we obtain

$\displaystyle n\epsilon_{n}\geq
H(f^{n}|\widehat{f^{n}})\overset{(a)}{=}H(f^{n}|\widebar{f}^{n})\overset{(b)}{=}\sum_{i=1}^{n}H(f_{i}|\widebar{f}_{i})$
$\displaystyle\;\geq\sum_{i=1}^{n}H(f_{i}|\widebar{f}^{n})\overset{(c)}{\geq}\sum_{i=1}^{n}H(f_{i}|W,Y^{n})$
$\displaystyle\;\geq\sum_{i=1}^{n}H(f_{i}|W,Y^{n},X^{i-1},Z^{i-1})$
$\displaystyle\;\overset{(d)}{=}\sum_{i=1}^{n}H(f_{i}|W,Y^{n}_{i+1},X^{i-1},Z^{i-1},Y_{i})$
$\displaystyle\;\overset{(e)}{=}\sum_{i=1}^{n}H(f_{i}|U_{i},Y_{i})$ (81)

where $(a)$ follows from [30, Lemma 2] so that when $n\rightarrow\infty$,
there exists an i.i.d. random variable $\widebar{f}^{n}$ such that
$H(f^{n}|\widehat{f^{n}})=H(f^{n}|\widebar{f}^{n})$ and
$\widehat{f^{n}}-\widebar{f}^{n}-(W,Y^{n})$ form a Markov chain, $(b)$ follows
because $(f^{n},\widebar{f}^{n})$ are i.i.d., $(c)$ follows from the Markov
chain $f^{n}-(W,Y^{n})-\widebar{f}^{n}$ and permits randomized decoding, $(d)$
follows from the Markov chain for all $i\in[1:n]$

$\displaystyle Y^{i-1}-(X^{i-1},Z^{i-1},W,Y_{i},Y_{i+1}^{n})-f_{i}$ (82)

and $(e)$ follows from the definition of $U_{i}$.

Storage (Public Message) Rate: We have

$\displaystyle
n(R_{\text{w}}+\delta_{n})\overset{(a)}{\geq}\log|\mathcal{W}|\geq
H(W|Y^{n})-H(W|\widetilde{X}^{n},Y^{n})$
$\displaystyle=I(\widetilde{X}^{n};W|Y^{n})=H(\widetilde{X}^{n}|Y^{n})-H(\widetilde{X}^{n}|W,Y^{n})$
$\displaystyle=H(\widetilde{X}^{n}|Y^{n})-\sum_{i=1}^{n}H(\widetilde{X}_{i}|\widetilde{X}^{i-1},W,Y^{n})$
$\displaystyle\overset{(b)}{=}H(\widetilde{X}^{n}|Y^{n})-\sum_{i=1}^{n}H(\widetilde{X}_{i}|\widetilde{X}^{i-1},W,Y_{i+1}^{n},Y_{i})$
$\displaystyle\overset{(c)}{\geq}H(\widetilde{X}^{n}|Y^{n})-\sum_{i=1}^{n}H(\widetilde{X}_{i}|X^{i-1},Z^{i-1},W,Y_{i+1}^{n},Y_{i})$
$\displaystyle\overset{(d)}{=}nH(\widetilde{X}|Y)-\sum_{i=1}^{n}H(\widetilde{X}|U_{i},Y_{i})=\sum_{i=1}^{n}I(U_{i};\widetilde{X}_{i}|Y_{i})$
(83)

where $(a)$ follows by (4), $(b)$ follows from the Markov chain for all
$i\in[1:n]$

$\displaystyle
Y^{i-1}-(\widetilde{X}^{i-1},W,Y_{i+1}^{n},Y_{i})-\widetilde{X}_{i}$ (84)

$(c)$ follows from the data processing inequality applied to the Markov chain
for all $i\in[1:n]$

$\displaystyle(X^{i-1},Z^{i-1})-(\widetilde{X}^{i-1},W,Y_{i+1}^{n},Y_{i})-\widetilde{X}_{i}$
(85)

and $(d)$ follows from the definition of $U_{i}$.

Privacy Leakage to the Decoder: We obtain

$\displaystyle
n(R_{\ell,\text{Dec}}+\delta_{n})\overset{(a)}{\geq}H(W|Y^{n})-H(W|X^{n})$
$\displaystyle\;=\sum_{i=1}^{n}\Big{[}I(W;X_{i}|X^{i-1})-I(W;Y_{i}|Y_{i+1}^{n})\Big{]}$
$\displaystyle\;\overset{(b)}{=}\sum_{i=1}^{n}\Big{[}I(W;X_{i}|X^{i-1},Y_{i+1}^{n})-I(W;Y_{i}|Y_{i+1}^{n},X^{i-1})\Big{]}$
$\displaystyle\;\overset{(c)}{=}\sum_{i=1}^{n}\Big{[}I(W;X_{i}|X^{i-1},Z^{i-1},Y_{i+1}^{n})$
$\displaystyle\qquad\qquad-I(W;Y_{i}|Y_{i+1}^{n},X^{i-1},Z^{i-1})\Big{]}$
$\displaystyle\;\overset{(d)}{=}\sum_{i=1}^{n}\Big{[}I(W,X^{i-1},Z^{i-1},Y_{i+1}^{n};X_{i})$
$\displaystyle\qquad\qquad-I(W,Y_{i+1}^{n},X^{i-1},Z^{i-1};Y_{i})\Big{]}$
$\displaystyle\;\overset{(e)}{=}\sum_{i=1}^{n}\Big{[}I(U_{i};X_{i})-I(U_{i};Y_{i})\Big{]}\overset{(f)}{=}\sum_{i=1}^{n}I(U_{i};X_{i}|Y_{i})$
(86)

where $(a)$ follows by (5) and from the Markov chain $W-X^{n}-Y^{n}$, $(b)$
follows from Csiszár’s sum identity [45], $(c)$ follows from the Markov chains

$\displaystyle Z^{i-1}-(X^{i-1},Y_{i+1}^{n})-(X_{i},W)$ (87) $\displaystyle
Z^{i-1}-(X^{i-1},Y_{i+1}^{n})-(Y_{i},W)$ (88)

$(d)$ follows because $X^{n}$ is i.i.d. and the measurement channels are
memoryless, $(e)$ follows from the definition of $U_{i}$, and $(f)$ follows
from the Markov chain $U_{i}-X_{i}-Y_{i}$ for all $i\in[1:n]$.

Privacy Leakage to the Eavesdropper: We obtain

$\displaystyle n(R_{\ell,\text{Eve}}+\delta_{n})$
$\displaystyle\overset{(a)}{\geq}[H(W|Z^{n})-H(W|Y^{n})]+[H(W|Y^{n})-H(W|X^{n})]$
$\displaystyle=\sum_{i=1}^{n}\Big{[}I(W;Y_{i}|Y_{i+1}^{n})-I(W;Z_{i}|Z^{i-1})\Big{]}$
$\displaystyle\qquad+\sum_{i=1}^{n}\Big{[}I(W;X_{i}|X^{i-1})-I(W;Y_{i}|Y_{i+1}^{n})\Big{]}$
$\displaystyle\overset{(b)}{=}\sum_{i=1}^{n}\Big{[}I(W;Y_{i}|Y_{i+1}^{n},Z^{i-1})-I(W;Z_{i}|Z^{i-1},Y_{i+1}^{n})\Big{]}$
$\displaystyle\qquad+\sum_{i=1}^{n}\Big{[}I(W;X_{i}|X^{i-1},Y_{i+1}^{n})\\!-\\!I(W;Y_{i}|Y_{i+1}^{n},X^{i-1})\Big{]}$
$\displaystyle\overset{(c)}{=}\sum_{i=1}^{n}\Big{[}I(W;Y_{i}|Y_{i+1}^{n},Z^{i-1})-I(W;Z_{i}|Z^{i-1},Y_{i+1}^{n})\Big{]}$
$\displaystyle\qquad+\sum_{i=1}^{n}\Bigg{[}I(W;X_{i}|X^{i-1},Y_{i+1}^{n},Z^{i-1})$
$\displaystyle\qquad\qquad\qquad-\\!I(W;Y_{i}|Y_{i+1}^{n},X^{i-1},Z^{i-1})\Bigg{]}$
$\displaystyle\overset{(d)}{=}\sum_{i=1}^{n}\Big{[}I(W,Y_{i+1}^{n},Z^{i-1};Y_{i})\\!-\\!I(W,Z^{i-1},Y_{i+1}^{n};Z_{i})\Big{]}$
$\displaystyle\qquad+\sum_{i=1}^{n}\Bigg{[}I(W,X^{i-1},Y_{i+1}^{n},Z^{i-1};X_{i})$
$\displaystyle\qquad\qquad\qquad-I(W,Y_{i+1}^{n},X^{i-1},Z^{i-1};Y_{i})\Bigg{]}$
$\displaystyle\overset{(e)}{=}\sum_{i=1}^{n}\Big{[}I(V_{i};Y_{i})\\!-\\!I(V_{i};Z_{i})\\!+\\!I(U_{i},V_{i};X_{i})\\!-\\!I(U_{i},V_{i};Y_{i})\Big{]}$
$\displaystyle=\sum_{i=1}^{n}\Bigg{[}-I(U_{i},V_{i};Z_{i})+I(U_{i},V_{i};X_{i})$
$\displaystyle\qquad\qquad\qquad+\left(I(U_{i};Z_{i}|V_{i})-I(U_{i};Y_{i}|V_{i})\right)\Bigg{]}$
$\displaystyle\overset{(f)}{\geq}\\!\sum_{i=1}^{n}\Big{[}I(U_{i};X_{i}|Z_{i})\\!+\\![I(U_{i};Z_{i}|V_{i})\\!-\\!I(U_{i};Y_{i}|V_{i})]^{-}\Big{]}$
(89)

where $(a)$ follows by (6) and from the Markov chain $W-X^{n}-Z^{n}$, $(b)$
follows from Csiszár’s sum identity, $(c)$ follows from the Markov chains in
(87) and (88), $(d)$ follows because $X^{n}$ is i.i.d. and the measurement
channels are memoryless, $(e)$ follows from the definitions of $V_{i}$ and
$U_{i}$, and $(f)$ follows from the Markov chain $V_{i}-U_{i}-X_{i}-Z_{i}$ for
all $i\in[1:n]$.

Secrecy Leakage (to the Eavesdropper): We have

$\displaystyle n(R_{\text{s}}+\delta_{n})$
$\displaystyle\overset{(a)}{\geq}\\![H(W|Z^{n})\\!-\\!H(W|Y^{n})]\\!+\\![H(W|Y^{n})\\!-\\!H(W|\widetilde{X}^{n},Y^{n})]$
$\displaystyle\overset{(b)}{=}\sum_{i=1}^{n}\Big{[}I(W;Y_{i}|Y_{i+1}^{n})-I(W;Z_{i}|Z^{i-1})\Big{]}$
$\displaystyle\qquad+\Big{[}nH(\widetilde{X}|Y)-\sum_{i=1}^{n}H(\widetilde{X}_{i}|\widetilde{X}^{i-1},W,Y^{n})\Big{]}$
$\displaystyle\overset{(c)}{=}\sum_{i=1}^{n}\Big{[}I(W;Y_{i}|Y_{i+1}^{n},Z^{i-1})-I(W;Z_{i}|Z^{i-1},Y_{i+1}^{n})\Big{]}$
$\displaystyle\qquad+\Big{[}nH(\widetilde{X}|Y)-\sum_{i=1}^{n}H(\widetilde{X}_{i}|\widetilde{X}^{i-1},W,Y_{i+1}^{n},Y_{i})\Big{]}$
$\displaystyle\overset{(d)}{\geq}\sum_{i=1}^{n}\Big{[}I(W,Y_{i+1}^{n},Z^{i-1};Y_{i})-I(W,Z^{i-1},Y_{i+1}^{n};Z_{i})\Big{]}$
$\displaystyle\qquad+\Big{[}nH(\widetilde{X}|Y)-\sum_{i=1}^{n}H(\widetilde{X}_{i}|X^{i-1},Z^{i-1},W,Y_{i+1}^{n},Y_{i})\Big{]}$
$\displaystyle\overset{(e)}{=}\sum_{i=1}^{n}\Big{[}I(V_{i};Y_{i})-I(V_{i};Z_{i})+I(U_{i},V_{i};\widetilde{X}_{i}|Y_{i})\Big{]}$
$\displaystyle\overset{(f)}{=}\sum_{i=1}^{n}\Big{[}I(V_{i};Y_{i})\\!-\\!I(V_{i};Z_{i})\\!+\\!I(U_{i},V_{i};\widetilde{X}_{i})\\!-\\!I(U_{i},V_{i};Y_{i})\Big{]}$
$\displaystyle=\sum_{i=1}^{n}\Bigg{[}-\\!I(U_{i},V_{i};Z_{i})\\!+\\!I(U_{i},V_{i};\widetilde{X}_{i})$
$\displaystyle\qquad\qquad\qquad+(I(U_{i};Z_{i}|V_{i})\\!-\\!I(U_{i};Y_{i}|V_{i}))\Bigg{]}$
$\displaystyle\overset{(g)}{\geq}\sum_{i=1}^{n}\Big{[}I(U_{i};\widetilde{X}_{i}|Z_{i})\\!+\\![I(U_{i};Z_{i}|V_{i})\\!-\\!I(U_{i};Y_{i}|V_{i})]^{-}\Big{]}$
(90)

where $(a)$ follows by (3), $(b)$ follows because $(\widetilde{X}^{n},Y^{n})$
are i.i.d., $(c)$ follows from Csiszár’s sum identity and the Markov chain in
(84), $(d)$ follows because $X^{n}$ is i.i.d. and the measurement channels are
memoryless, and from the data processing inequality applied to the Markov
chain in (85), $(e)$ follows from the definitions of $V_{i}$ and $U_{i}$,
$(f)$ follows from the Markov chain $(U_{i},V_{i})-\widetilde{X}_{i}-Y_{i}$
for all $i\in[1:n]$, and $(g)$ follows from the Markov chain
$V_{i}-U_{i}-\widetilde{X}_{i}-Z_{i}$ for all $i\in[1:n]$.

Introduce a uniformly distributed time-sharing random variable $\displaystyle
Q\\!\sim\\!\text{Unif}[1\\!:\\!n]$ independent of other random variables.
Define $X\\!=\\!X_{Q}$, $\displaystyle\widetilde{X}\\!=\\!\widetilde{X}_{Q}$,
$\displaystyle Y\\!=\\!Y_{Q}$, $\displaystyle Z\\!=\\!Z_{Q}$, $V\\!=\\!V_{Q}$,
$U\\!=\\!(U_{Q},\\!Q)$, and $f=f_{Q}$ so that
$\displaystyle(Q,V)\\!-U-\widetilde{X}-X-(Y,Z)$ form a Markov chain. The
converse proof of Theorem 1 follows by letting $\delta_{n}\rightarrow 0$.

Cardinality Bounds: We use the support lemma [45, Lemma 15.4]. One can
preserve $P_{\widetilde{X}}$ by using $|\mathcal{\widetilde{X}}|-1$ real-
valued continuous functions. We have to preserve two expressions for the two
cases such that $I(U;Z|V,Q\\!=\\!q)\\!>\\!I(U;Y|V,Q=q)$ and $I(U;Z|V,Q=q)\leq
I(U;Y|V,Q=q)$ for all $q\in\mathcal{Q}$, so one can limit the cardinality
$|\mathcal{Q}|$ of $Q$ to $|\mathcal{Q}|\leq 2$. Furthermore, we have to
preserve five more expressions, i.e., $H(\widetilde{X}|U,V,Z)$,
$H(\widetilde{X}|U,V,Y)$, $H(X|U,V,Y)$, $H(X|U,V,Z)$, and
$(I(U;Z|V)-I(U;Y|V))$. Thus, one can limit the cardinality $|\mathcal{V}|$ of
$V$ to $|\mathcal{V}|\leq|\mathcal{\widetilde{X}}|+4$. Similarly, in addition
to the $|\mathcal{\widetilde{X}}|-1$ real-valued continuous functions, one
should preserve the same five expressions for the auxiliary random variable
$U$. To satisfy the Markov condition $(Q,V)-U-\widetilde{X}-X-(Y,Z)$, one can
limit the cardinality $|\mathcal{U}|$ of $U$ to
$|\mathcal{U}|\leq{(|\mathcal{\widetilde{X}}|+4)}^{2}$. ∎

##  VI Proof of Theorem 3

###  VI-A Achievability (Inner Bound) Proof of Theorem 3

The achievability proof follows by using the OSRB method, as described below.

###### Proof:

Similar to Section V-A, fix $P_{U_{j}|\widetilde{X}_{j}}$ and
$P_{V_{j}|U_{j}}$ such that $U_{j}$ is admissible for the function
$f_{j}(\widetilde{X}_{j},Y_{j})$ for all $j\in[1:J]$ and let
$(V_{[1:J]}^{n},U_{[1:J]}^{n},\widetilde{X}_{[1:J]}^{n},X^{n},Y_{[1:J]}^{n},Z_{[1:J]}^{n})$
be i.i.d. according to (29). We remark that since all $n$-letter random
variables are i.i.d., $U_{j}^{n}$ is also admissible for all $j\in[1:J]$.

Assign two random bin indices $(F_{\text{v},j},W_{\text{v},j})$ to each
$v_{j}^{n}$, and assume $F_{\text{v},j}\in[1:2^{n\widetilde{R}_{\text{v},j}}]$
and $W_{\text{v},j}\in[1:2^{nR_{\text{v},j}}]$ for all $j\in[1:J]$. Similarly,
for all $j\in[1:J]$ assign two indices $(F_{\text{u},j},W_{\text{u},j})$ to
each $u_{j}^{n}$, where $F_{\text{u},j}\in[1:2^{n\widetilde{R}_{\text{u},j}}]$
and $W_{\text{u},j}\in[1:2^{nR_{\text{u},j}}]$. The public message is
$W_{j}=(W_{\text{v},j},W_{\text{u},j})$ and indices
$F_{j}=(F_{\text{v},j},F_{\text{u},j})$ represent the public choice of
encoder-decoder pairs for all $j\in[1:J]$.

For all $j\in[1:J]$, using a Slepian-Wolf (SW) decoder, one can reliably
estimate $V_{j}^{n}$ from $(F_{\text{v},j},W_{\text{v},j},Y_{j}^{n})$ if we
have

$\displaystyle\widetilde{R}_{\text{v},j}+R_{\text{v},j}>H(V_{j}|Y_{j})$ (91)

and one can reliably estimate $U_{j}^{n}$ from
$(F_{\text{u},j},W_{\text{u},j},Y_{j}^{n},V_{j}^{n})$ by using a SW decoder if
we have

$\displaystyle\widetilde{R}_{\text{u},j}+R_{\text{u},j}>H(U_{j}|V_{j},Y_{j}).$
(92)

Thus, applying the union bound, we can show that the reliability constraint in
(8) is satisfied if (91) and (92) are satisfied for all $j\in[1:J]$.

The public index $F_{\text{v},j}$ is almost independent of
$\widetilde{X}_{j}^{n}$, so it is almost independent of
$(V^{n}_{[1:J]\setminus\\{j\\}},U^{n}_{[1:J]\setminus\\{j\\}},\widetilde{X}_{[1:J]}^{n},X^{n},Y_{[1:J]}^{n},Z_{[1:J]}^{n})$,
if we have

$\displaystyle\widetilde{R}_{\text{v},j}<H(V_{j}|\widetilde{X}_{j}),\qquad\qquad\forall
j\in[1:J].$ (93)

The public index $F_{\text{u},j}$ is almost independent of
$(V_{j}^{n},\widetilde{X}_{j}^{n})$, so it is almost independent of
$(V^{n}_{[1:J]},U^{n}_{[1:J]\setminus\\{j\\}},\widetilde{X}_{[1:J]}^{n},X^{n},Y_{[1:J]}^{n},Z_{[1:J]}^{n})$,
if we have

$\displaystyle\widetilde{R}_{\text{u},j}<H(U_{j}|V_{j},\widetilde{X}_{j}),\qquad\qquad\forall
j\in[1:J].$ (94)

To satisfy the constraints (91)-(94), similar to Section V, we fix the rates
to

$\displaystyle\widetilde{R}_{\text{v},j}\\!=\\!H(V_{j}|\widetilde{X}_{j})\\!-\\!\epsilon,$
$\displaystyle\;\;\forall j\in[1:J]$ (95) $\displaystyle
R_{\text{v},j}\\!=\\!I(V_{j};\widetilde{X}_{j})\\!-\\!I(V_{j};Y_{j})\\!+\\!2\epsilon,$
$\displaystyle\;\;\forall j\in[1:J]$ (96)
$\displaystyle\widetilde{R}_{\text{u},j}\\!=\\!H(U_{j}|V_{j},\widetilde{X}_{j})\\!-\\!\epsilon,$
$\displaystyle\;\;\forall j\in[1:J]$ (97) $\displaystyle
R_{\text{u},j}\\!=\\!I(U_{j};\widetilde{X}_{j}|V_{j})\\!-\\!I(U_{j};Y_{j}|V_{j})\\!+\\!2\epsilon,$
$\displaystyle\;\;\forall j\in[1:J]$ (98)

for any $\epsilon>0$.

Storage (Public Message) Rate: (95)-(98) result in a storage (public message)
rate $R_{\text{w},j}$ of

$\displaystyle
R_{\text{w},j}=R_{\text{v},j}+R_{\text{u},j}=I(V_{j},U_{j};\widetilde{X}_{j})-I(V_{j},U_{j};Y_{j})+4\epsilon$
$\displaystyle\overset{(a)}{=}I(U_{j};\widetilde{X}_{j}|Y_{j})+4\epsilon,\qquad\qquad\qquad\qquad\forall
j\in[1:J]$ (99)

where $(a)$ follows because $V_{j}-U_{j}-\widetilde{X}_{j}-Y_{j}$ form a
Markov chain for all $j\in[1:J]$.

Privacy Leakage to the Decoder: Consider the privacy leakage to the decoder.
We have

$\displaystyle I(X^{n};W_{j},F_{j}|Y_{j}^{n})$
$\displaystyle\qquad\overset{(a)}{\leq}nI(U_{j};X|Y_{j})+2\epsilon_{n},\qquad\qquad\quad\forall
j\in[1\\!:\\!J]$ (100)

where $(a)$ follows for some $\epsilon_{n}>0$ with $\epsilon_{n}\rightarrow 0$
when $n\rightarrow\infty$ by applying the steps in (52).

Privacy Leakage to the Eavesdropper: Suppose an additional virtual joint
encoder assigns $4J$ indices
$(F_{v,[1:J]},W_{v,[1:J]},F_{u,[1:J]},W_{u,[1:J]})$ to each realization tuple
$(v_{1}^{n},v_{2}^{n},\dots,v^{n}_{J},u_{1}^{n},u_{2}^{n},\dots,u^{n}_{J})\in\mathcal{V}_{1}\times\mathcal{V}_{2}\times\ldots\times\mathcal{V}_{J}\times\mathcal{U}_{1}\times\mathcal{U}_{2}\times\ldots\times\mathcal{U}_{J}$
such that

$\displaystyle\sum_{j=1}^{J}(\widetilde{R}_{\text{v},j}+R_{\text{v},j})>H(V_{[1:J]}|Y_{[1:J]}),$
(101)
$\displaystyle\sum_{j=1}^{J}(\widetilde{R}_{\text{u},j}+R_{\text{u},j})>H(U_{[1:J]}|V_{[1:J]},Y_{[1:J]}).$
(102)

Thus, $(W_{v,[1:J]},F_{v,[1:J]},Y^{n}_{[1:J]})$ can reliably recover
$V^{n}_{[1:J]}$ and $(V^{n}_{[1:J]},W_{u,[1:J]},F_{u,[1:J]},Y^{n}_{[1:J]})$
can reliably recover $U^{n}_{[1:J]}$. Therefore, we have for the total storage
rate that

$\displaystyle\sum_{j=1}^{J}R_{\text{w},j}=\sum_{j=1}^{J}(R_{\text{v},j}+R_{\text{u},j})$
$\displaystyle\qquad\overset{(a)}{\geq}I(U_{[1:J]},V_{[1:J]};\widetilde{X}_{[1:J]})-I(U_{[1:J]},V_{[1:J]};Y_{[1:J]})$
$\displaystyle\qquad\overset{(b)}{=}I(U_{[1:J]};\widetilde{X}_{[1:J]}|Y_{[1:J]})$
(103)

where $(a)$ follows by (101) and (102), and because (93) and (94) ensure that
$(F_{v,[1:J]},F_{u,[1:J]})$ are almost mutually independent of
$\widetilde{X}^{n}_{[1:J]}$ since
$\sum_{j=1}^{J}(\widetilde{R}_{v,j}+\widetilde{R}_{u,j})<H(U_{[1:J]},V_{[1:J]}|\widetilde{X}_{[1:J]})$
such that equality is achieved when $n\rightarrow\infty$ and $(b)$ follows
from the Markov chain $V_{[1:J]}-U_{[1:J]}-\widetilde{X}_{[1:J]}-Y_{[1:J]}$.

Consider the privacy leakage to the eavesdropper. We have

$\displaystyle I(X^{n};W_{[1:J]},F_{[1:J]}|Z_{[1:J]}^{n})$
$\displaystyle\overset{(a)}{=}H(W_{[1:J]},F_{[1:J]}|Z_{[1:J]}^{n})-H(W_{[1:J]},F_{[1:J]}|X^{n})$
$\displaystyle\overset{(b)}{=}H(W_{[1:J]},F_{[1:J]}|Z_{[1:J]}^{n})-nH(U_{[1:J]},V_{[1:J]}|X)$
$\displaystyle\quad+\sum_{j=1}^{J}\Big{[}H(V^{n}_{j}|V^{n}_{[1:j-1]},W_{[1:J]},F_{[1:J]},X^{n})$
$\displaystyle\qquad\qquad\quad+H(U^{n}_{j}|U^{n}_{[1:j-1]},V^{n}_{[1:J]},W_{[1:J]},F_{[1:J]},X^{n})\Big{]}$
$\displaystyle\overset{(c)}{\leq}\\!H(W_{[1:J]},F_{[1:J]}|Z_{[1:J]}^{n})$
$\displaystyle\qquad-nH(U_{[1:J]},V_{[1:J]}|X)+2Jn\epsilon_{n}^{\prime}$ (104)

where $(a)$ follows from the Markov chain
$Z_{[1:J]}^{n}-X^{n}-(W_{[1:J]},F_{[1:J]})$, $(b)$ follows since $U_{j}^{n}$
determines $(W_{u,j},F_{u,j})$ and $V_{j}^{n}$ determines $(W_{v,j},F_{v,j})$
for all $j\in[1:J]$, and $(U^{n}_{[1:J]},V^{n}_{[1:J]},X^{n})$ are i.i.d., and
$(c)$ follows for some $\epsilon_{n}^{\prime}>0$ such that
$\epsilon^{\prime}_{n}\rightarrow 0$ when $n\rightarrow\infty$ because
$(F_{v,j},W_{v,j}X^{n})$ can reliably recover $V_{j}^{n}$ due to the Markov
chain $V_{j}^{n}-X^{n}-Y_{j}^{n}$ and (91), and because
$(W_{u,j},F_{u,j},V_{j}^{n},X^{n})$ can reliably recover $U_{j}^{n}$ due to
the inequality $H(U_{j}|V_{j},Y_{j})\geq H(U_{j}|V_{j},X)$, proved in (55),
for all $j\in[1:J]$.

We consider the six decodability cases considered in Section V-A by replacing
$[(R_{v}+\widetilde{R}_{v}),(R_{u}+\widetilde{R}_{u})]$ with
$\Big{[}\Big{(}\sum_{j=1}^{J}(R_{v,j}+\widetilde{R}_{v,j})\Big{)},\Big{(}\sum_{j=1}^{J}(R_{u,j}+\widetilde{R}_{u,j})\Big{)}\Big{]}$,
respectively, and $[H(V|Z),H(U|V,Z),H(U|Z)]$ with
$[H(V_{[1:J]}|Z_{[1:J]}),H(U_{[1:J]}|V_{[1:J]},Z_{[1:J]}),H(U_{[1:J]}|Z_{[1:J]})]$,
respectively. Using these replacements, applying the steps in (58),(61), (64),
(67), (70), and (73) in combination with (104), and by choosing trivial rates
that satisfy (101) and (102), one can show that

$\displaystyle I(X^{n};W_{[1:J]},F_{[1:J]}|Z_{[1:J]}^{n})$ $\displaystyle\leq
n[I(U_{[1:J]};Z_{[1:J]}|V_{[1:J]})\\!-\\!I(U_{[1:J]};Y_{[1:J]}|V_{[1:J]})\\!+\\!\epsilon]^{-}$
$\displaystyle\qquad+n(I(U_{[1:J]};X|Z_{[1:J]})+3J\epsilon^{\prime}_{n}).$
(105)

Secrecy Leakage (to the Eavesdropper): Consider the secrecy leakage. We have

$\displaystyle
I(\widetilde{X}_{[1:J]}^{n},Y_{[1:J]}^{n};W_{[1:J]},F_{[1:J]}|Z_{[1:J]}^{n})$
$\displaystyle\\!\overset{(a)}{=}H(W_{[1:J]},F_{[1:J]}|Z_{[1:J]}^{n})-H(W_{[1:J]},F_{[1:J]}|\widetilde{X}_{[1:J]}^{n})$
$\displaystyle\\!\overset{(b)}{\leq}\\!H(W_{[1:J]},F_{[1:J]}|Z_{[1:J]}^{n})$
$\displaystyle\qquad-H(U^{n}_{[1:J]},V^{n}_{[1:J]}|\widetilde{X}^{n}_{[1:J]})\\!+\\!2Jn\epsilon^{\prime}_{n}$
(106)

where $(a)$ follows from the Markov chain
$(W_{[1:J]},F_{[1:J]})-\widetilde{X}_{[1:J]}^{n}-(Y_{[1:J]}^{n},Z_{[1:J]}^{n})$,
$(b)$ follows for some $\epsilon_{n}^{\prime}>0$ such that
$\epsilon_{n}^{\prime}\rightarrow 0$ when $n\rightarrow\infty$ because
$U^{n}_{j}$ determines $(W_{u,j},F_{u,j})$ and $V^{n}_{j}$ determines
$(W_{v,j},F_{v,j})$, and $(W_{v,j},F_{v,j},\widetilde{X}_{j}^{n})$ can
reliably recover $V_{j}^{n}$ due to the Markov chain
$V_{j}^{n}-\widetilde{X}_{j}^{n}-Y_{j}^{n}$ and (91), and similarly
$(W_{u,j},F_{u,j},V_{j}^{n},\widetilde{X}_{j}^{n})$ can reliably recover
$U_{j}^{n}$ because $H(U_{j}|V_{j},Y_{j})\geq
H(U_{j}|V_{j},\widetilde{X}_{j})$, which can be proved as in (55).

By using the same joint virtual encoder used for the privacy-leakage to the
eavesdropper analysis above and replacing $X$ by $\widetilde{X}_{[1:J]}$ in
the analyses of (105), we obtain from (106) that

$\displaystyle
I(\widetilde{X}_{[1:J]}^{n},Y_{[1:J]}^{n};W_{[1:J]},F_{[1:J]}|Z_{[1:J]}^{n})$
$\displaystyle\\!\leq
n[I(U_{[1:J]};Z_{[1:J]}|V_{[1:J]})\\!-\\!I(U_{[1:J]};Y_{[1:J]}|V_{[1:J]})\\!+\\!\epsilon]^{-}\\!$
$\displaystyle\qquad+n(I(U_{[1:J]};\widetilde{X}_{[1:J]}|Z_{[1:J]})+\\!\\!3J\epsilon^{\prime}_{n}).$
(107)

Suppose the public indices $F_{[1:J]}$ are generated uniformly at random. The
encoder $\mathsf{Enc}_{j}(\cdot)$ generates $(V_{j}^{n},U_{j}^{n})$ according
to $P_{V_{j}^{n}U_{j}^{n}|\widetilde{X}_{j}^{n}F_{\text{v},j}F_{\text{u},j}}$
obtained from the binning scheme above to compute the bins $W_{\text{v},j}$
from $V_{j}^{n}$ and $W_{\text{u},j}$ from $U^{n}_{j}$, respectively, for all
$j\in[1:J]$. This procedure induces a joint probability distribution that is
almost equal to
$P_{V_{[1:J]}U_{[1:J]}\widetilde{X}_{[1:J]}XY_{[1:J]}Z_{[1:J]}}$ fixed above
[42, Section 1.6]. We remark that the privacy and secrecy leakage metrics
considered above are expectations over all possible realizations
$F_{[1:J]}=f_{[1:J]}$. Thus, applying the selection lemma to each decodability
case separately, these results prove the achievability for the rate tuples
given in Theorem 3 by choosing an $\epsilon>0$ such that $\epsilon\rightarrow
0$ when $n\rightarrow\infty$. ∎

###  VI-B Converse (Outer Bound) Proof of Theorem 3

###### Proof:

Suppose for some $\delta_{n}\\!>\\!0$ and $n\geq 1$, there exists a pair of
encoders and decoders such that (8)-(12) are satisfied for some tuple
$(R_{\text{s}},R_{\text{w},[1:J]},R_{\ell,{\text{Dec}},[1:J]},R_{\ell,{\text{Eve}}})$
.

Let $V_{i,j}\triangleq(W_{j},Y^{n}_{i+1,j},Z_{j}^{i-1})$ and
$U_{i,j}\triangleq(W_{j},X^{i-1},Y^{n}_{i+1,j},Z_{j}^{i-1})$, which satisfy
the Markov chain $V_{i,j}-U_{i,j}-\widetilde{X}_{i,j}-X_{i}-(Y_{i,j},Z_{i,j})$
for all $i\in[1:n]$ and $j\in[1:J]$ by definition of the source statistics.

Admissibility of $\mathbf{U_{j}}$: Define
$\displaystyle\epsilon_{n}\\!=\max_{j\in[1:J]}\\!\Big{(}\delta_{n,j}|\mathcal{\widetilde{X}}_{j}||\mathcal{Y}_{j}|\\!+\\!H_{b}(\delta_{n,j})/n\Big{)}$
so that $\epsilon_{n}\\!\rightarrow\\!0$ if
$\displaystyle\max_{j\in[1:J]}\delta_{n,j}=\delta_{n}\\!\rightarrow\\!0$.
Applying the union bound to (8) and using Fano’s inequality, we obtain

$\displaystyle
n\epsilon_{n}\\!\geq\\!H(f_{j}^{n}|\widehat{f_{j}^{n}})\\!\overset{(a)}{\geq}\\!\sum_{i=1}^{n}\\!\\!H(f_{i,j}|U_{i,j},Y_{i,j}),\;\forall
j\in[1:J]$ (108)

where $(a)$ follows applying the steps in (81) and from the definition of
$U_{i,j}$.

Storage (Public Message) Rate: We have for all $j\in[1:J]$ that

$\displaystyle
n(R_{\text{w},j}\\!+\\!\delta_{n})\\!\overset{(a)}{\geq}\\!\log|\mathcal{W}_{j}|\\!\overset{(b)}{\geq}\\!\sum_{i=1}^{n}I(U_{i,j};\widetilde{X}_{i,j}|Y_{i,j})$
(109)

where $(a)$ follows by (10) and $(b)$ follows by applying the steps in (83)
and from the definition of $U_{i,j}$.

Privacy Leakage to the Decoder: We obtain for all $j\in[1:J]$ that

$\displaystyle
n(R_{\ell,\text{Dec},j}+\delta_{n})\overset{(a)}{\geq}H(W_{j}|Y_{j}^{n})-H(W_{j}|X^{n})$
$\displaystyle\quad\overset{(b)}{\geq}\sum_{i=1}^{n}I(U_{i,j};X_{i}|Y_{i,j})$
(110)

where $(a)$ follows by (11) and from the Markov chain $W_{j}-X^{n}-Y_{j}^{n}$
and $(b)$ follows by applying the steps in (86) and from the definition of
$U_{i,j}$.

Sum-Storage Rate: We have for all $j\in[1:J]$ that

$\displaystyle
n\sum_{j=1}^{J}(R_{\text{w},j}\\!+\\!\delta_{n})\\!\overset{(a)}{\geq}\log\Bigg{|}\prod_{j=1}^{J}|\mathcal{W}_{j}|\Bigg{|}$
$\displaystyle\geq\\!H(W_{[1:J]}|Y^{n}_{[1:J]})-H(W_{[1:J]}|\widetilde{X}^{n}_{[1:J]},Y^{n}_{[1:J]})$
$\displaystyle=H(\widetilde{X}^{n}_{[1:J]}|Y^{n}_{[1:J]})-\sum_{i=1}^{n}H(\widetilde{X}_{i,[1:J]}|\widetilde{X}^{i-1}_{[1:J]},Y^{n}_{[1:J]},W_{[1:J]})$
$\displaystyle\overset{(b)}{=}H(\widetilde{X}^{n}_{[1:J]}|Y^{n}_{[1:J]})$
$\displaystyle\qquad-\sum_{i=1}^{n}H(\widetilde{X}_{i,[1:J]}|\widetilde{X}^{i-1}_{[1:J]},Y^{n}_{i+1,[1:J]},Y_{i,[1:J]},W_{[1:J]})$
$\displaystyle\overset{(c)}{\geq}H(\widetilde{X}^{n}_{[1:J]}|Y^{n}_{[1:J]})$
$\displaystyle\qquad-\sum_{i=1}^{n}H(\widetilde{X}_{i,[1:J]}|X^{i-1}_{[1:J]},Z^{i-1}_{[1:J]},Y^{n}_{i+1,[1:J]},Y_{i,[1:J]},W_{[1:J]})$
$\displaystyle\overset{(d)}{=}\sum_{i=1}^{n}I(U_{i,[1:J]};\widetilde{X}_{i,[1:J]}|Y_{i,[1:J]})$
(111)

where $(a)$ follows by (10), $(b)$ follows from the Markov chain for all
$i\in[1:n]$

$\displaystyle
Y_{[1:J]}^{i-1}-(\widetilde{X}_{[1:J]}^{i-1},W_{[1:J]},Y_{i,[1:J]}^{n})-\widetilde{X}_{i,[1:J]}$
(112)

$(c)$ follows from applying the data processing inequality to the Markov chain
for all $i\in[1:n]$

$\displaystyle(X^{i-1},Z_{[1:J]}^{i-1})-(\widetilde{X}_{[1:J]}^{i-1},W_{[1:J]},Y_{i,[1:J]}^{n})-\widetilde{X}_{i,[1:J]}$
(113)

and $(d)$ follows because $(\widetilde{X}^{n}_{[1:J]},Y^{n}_{[1:J]})$ are
i.i.d. and from the definition of $U_{i,j}$ for all $j\in[1:J]$.

Privacy Leakage to the Eavesdropper: We obtain

$\displaystyle n(R_{\ell,\text{Eve}}+\delta_{n})$
$\displaystyle\overset{(a)}{\geq}[H(W_{[1:J]}|Z_{[1:J]}^{n})-H(W_{[1:J]}|Y_{[1:J]}^{n})]$
$\displaystyle\qquad+[H(W_{[1:J]}|Y_{[1:J]}^{n})-H(W_{[1:J]}|X^{n})]$
$\displaystyle\overset{(b)}{=}\sum_{i=1}^{n}\Big{[}I(W_{[1:J]};Y_{i,[1:J]}|Y_{i+1,[1:J]}^{n},Z_{[1:J]}^{i-1})$
$\displaystyle\qquad\qquad-I(W_{[1:J]};Z_{i,[1:J}]|Z_{[1:J]}^{i-1},Y_{i+1,[1:J]}^{n})\Big{]}$
$\displaystyle\qquad+\sum_{i=1}^{n}\Big{[}I(W_{[1:J]};X_{i}|X^{i-1},Y_{i+1,[1:J]}^{n})$
$\displaystyle\qquad\qquad\quad\;-\\!I(W_{[1:J]};Y_{i,[1:J]}|Y_{i+1,[1:J]}^{n},X^{i-1})\Big{]}$
$\displaystyle\overset{(c)}{=}\sum_{i=1}^{n}\Big{[}I(W_{[1:J]};Y_{i,[1:J]}|Y_{i+1,[1:J]}^{n},Z_{[1:J]}^{i-1})$
$\displaystyle\qquad\qquad-I(W_{[1:J]};Z_{i,[1:J}]|Z_{[1:J]}^{i-1},Y_{i+1,[1:J]}^{n})\Big{]}$
$\displaystyle\qquad+\sum_{i=1}^{n}\Big{[}I(W_{[1:J]};X_{i}|X^{i-1},Y_{i+1,[1:J]}^{n},Z^{i-1}_{[1:J]})$
$\displaystyle\qquad\qquad\quad\;-\\!I(W_{[1:J]};Y_{i,[1:J]}|Y_{i+1,[1:J]}^{n},X^{i-1},Z^{i-1}_{[1:J]})\Big{]}$
$\displaystyle\overset{(d)}{=}\sum_{i=1}^{n}\Big{[}I(W_{[1:J]},Y_{i+1,[1:J]}^{n},Z^{i-1}_{[1:J]};Y_{i,[1:J]})$
$\displaystyle\qquad\qquad-\\!I(W_{[1:J]},Z_{[1:J]}^{i-1},Y_{i+1,[1:J]}^{n};Z_{i,[1:J]})\Big{]}$
$\displaystyle\qquad+\sum_{i=1}^{n}\Big{[}I(W_{[1:J]},X^{i-1},Y_{i+1,[1:J]}^{n},Z_{[1:J]}^{i-1};X_{i})$
$\displaystyle\qquad\qquad\quad\;-I(W_{[1:J]},Y_{i+1,[1:J]}^{n},X^{i-1},Z_{[1:J]}^{i-1};Y_{i,[1:J]})\Big{]}$
$\displaystyle\overset{(e)}{=}\sum_{i=1}^{n}\Big{[}I(V_{i,[1:J]};Y_{i,[1:J]})-I(V_{i,[1:J]};Z_{i,[1:J]})$
$\displaystyle\qquad\qquad\\!+\\!I(U_{i,[1:J]},V_{i,[1:J]};X_{i})\\!-\\!I(U_{i,[1:J]},V_{i,[1:J]};Y_{i,[1:J]})\Big{]}$
$\displaystyle\\!=\\!\sum_{i=1}^{n}\Bigg{[}\\!-\\!I(U_{i,[1:J]},V_{i,[1:J]};Z_{i,[1:J]})\\!+\\!I(U_{i,[1:J]},V_{i,[1:J]};X_{i})$
$\displaystyle\qquad\qquad+I(U_{i,[1:J]};Z_{i,[1:J]}|V_{i,[1:J]})$
$\displaystyle\qquad\qquad-I(U_{i,[1:J]};Y_{i,[1:J]}|V_{i,[1:J]})\Bigg{]}$
$\displaystyle\\!\overset{(f)}{\geq}\\!\\!\sum_{i=1}^{n}\\!\Bigg{[}\\!\big{[}\\!I(U_{i,[1:J]};Z_{i,[1:J]}|V_{i,[1:J]})\\!-\\!I(U_{i,[1:J]};Y_{i,[1:J]}|V_{i,[1:J]})\big{]}^{-}$
$\displaystyle\qquad\qquad+I(U_{i,[1:J]};X_{i}|Z_{i,[1:J]})\Bigg{]}$ (114)

where $(a)$ follows by (12) and from the Markov chain
$W_{[1:J]}-X^{n}-Z_{[1:J]}^{n}$, $(b)$ follows from Csiszár’s sum identity,
$(c)$ follows from the Markov chains for all $i\in[1:n]$

$\displaystyle Z_{[1:J]}^{i-1}-(X^{i-1},Y_{i+1,[1:J]}^{n})-(X_{i},W_{[1:J]})$
(115) $\displaystyle
Z_{[1:J]}^{i-1}-(X^{i-1},Y_{i+1,[1:J]}^{n})-(Y_{i,[1:J]},W_{[1:J]})$ (116)

$(d)$ follows because $X^{n}$ is i.i.d. and the measurement channels are
memoryless, $(e)$ follows from the definitions of $V_{i,j}$ and $U_{i,j}$ for
all $j\in[1:J]$, and $(f)$ follows from the Markov chain
$V_{i,[1:J]}-U_{i,[1:J]}-X_{i}-Z_{i,[1:J]}$ for all $i\in[1:n]$.

Secrecy Leakage (to the Eavesdropper): We have

$\displaystyle n(R_{\text{s}}+\delta_{n})$
$\displaystyle\overset{(a)}{\geq}\\![H(W_{[1:J]}|Z_{[1:J]}^{n})\\!-\\!H(W_{[1:J]}|Y_{[1:J]}^{n})]$
$\displaystyle\qquad+\\![H(W_{[1:J]}|Y_{[1:J]}^{n})\\!-\\!H(W_{[1:J]}|\widetilde{X}_{[1:J]}^{n},Y_{[1:J]}^{n})]$
$\displaystyle\overset{(b)}{=}\sum_{i=1}^{n}\Big{[}I(W_{[1:J]};Y_{i,[1:J]}|Y_{i+1,[1:J]}^{n})$
$\displaystyle\qquad\qquad-\\!I(W_{[1:J]};Z_{i,[1:J]}|Z_{[1:J]}^{i-1})\Big{]}$
$\displaystyle\qquad+\Big{[}nH(\widetilde{X}_{[1:J]}|Y_{[1:J]})$
$\displaystyle\qquad\qquad-\\!\sum_{i=1}^{n}H(\widetilde{X}_{i,[1:J]}|\widetilde{X}_{[1:J]}^{i-1},W_{[1:J]},Y_{[1:J]}^{n})\Big{]}$
$\displaystyle\overset{(c)}{=}\sum_{i=1}^{n}\Big{[}I(W_{[1:J]};Y_{i,[1:J]}|Y_{i+1,[1:J]}^{n},Z_{[1:J]}^{i-1})$
$\displaystyle\qquad\qquad-I(W_{[1:J]};Z_{i,[1:J]}|Z_{[1:J]}^{i-1},Y_{i+1,[1:J]}^{n})\Big{]}$
$\displaystyle\qquad+\Big{[}nH(\widetilde{X}_{[1:J]}|Y_{[1:J]})$
$\displaystyle\qquad\qquad-\sum_{i=1}^{n}H(\widetilde{X}_{i,[1:J]}|\widetilde{X}_{[1:J]}^{i-1},W_{[1:J]},Y_{i+1,[1:J]}^{n},Y_{i,[1:J]})\Big{]}$
$\displaystyle\overset{(d)}{\geq}\sum_{i=1}^{n}\Big{[}I(W_{[1:J]},Y_{i+1,[1:J]}^{n},Z_{[1:J]}^{i-1};Y_{i,[1:J]})$
$\displaystyle\qquad\qquad-I(W_{[1:J]},Z_{[1:J]}^{i-1},Y_{i+1,[1:J]}^{n};Z_{i,[1:J]})\Big{]}$
$\displaystyle\qquad+\Big{[}nH(\widetilde{X}_{[1:J]}|Y_{[1:J]})$
$\displaystyle\qquad\quad\\!-\\!\sum_{i=1}^{n}\\!H(\widetilde{X}_{i,[1\\!:J]}|X^{i-1},Z_{[1\\!:J]}^{i-1},W_{[1\\!:J]},Y_{i+1,[1\\!:J]}^{n},Y_{i,[1\\!:J]})\Big{]}$
$\displaystyle\overset{(e)}{=}\sum_{i=1}^{n}\Big{[}I(V_{i,[1:J]};Y_{i,[1:J]})-I(V_{i,[1:J]};Z_{i,[1:J]})$
$\displaystyle\qquad\qquad+I(U_{i,[1:J]},V_{i,[1:J]};\widetilde{X}_{i,[1:J]}|Y_{i,[1:J]})\Big{]}$
$\displaystyle\overset{(f)}{=}\sum_{i=1}^{n}\Big{[}I(V_{i,[1:J]};Y_{i,[1:J]})\\!-\\!I(V_{i,[1:J]};Z_{i,[1:J]})$
$\displaystyle\qquad\qquad+\\!I(U_{i,[1:J]},V_{i,[1:J]};\widetilde{X}_{i,[1:J]})$
$\displaystyle\qquad\qquad-\\!I(U_{i,[1:J]},V_{i,[1:J]};Y_{i,[1:J]})\Big{]}$
$\displaystyle=\sum_{i=1}^{n}\\!\Big{[}\\!-\\!I(U_{i,[1:J]},V_{i,[1:J]};Z_{i,[1:J]})$
$\displaystyle\qquad\qquad+\\!I(U_{i,[1:J]},V_{i,[1:J]};\widetilde{X}_{i,[1:J]})$
$\displaystyle\qquad\qquad+I(U_{i,[1:J]};Z_{i,[1:J]}|V_{i,[1:J]})$
$\displaystyle\qquad\qquad-\\!I(U_{i,[1:J]};Y_{i,[1:J]}|V_{i,[1:J]})\Big{]}$
$\displaystyle\\!\overset{(g)}{\geq}\\!\sum_{i=1}^{n}\\!\Bigg{[}\\![I(U_{i,[1:J]};Z_{i,[1:J]}|V_{i,[1:J}])\\!-\\!I(U_{i,[1:J]};Y_{i,[1:J]}|V_{i,[1:J]})]^{-}\\!$
$\displaystyle\qquad\qquad+I(U_{i,[1:J]};\widetilde{X}_{i,[1:J]}|Z_{i,[1:J]})\Bigg{]}$
(117)

where $(a)$ follows by (9), $(b)$ follows since
$(\widetilde{X}_{[1:J]}^{n},Y_{[1:J]}^{n})$ are i.i.d., $(c)$ follows from
Csiszár’s sum identity and the Markov chain in (112), $(d)$ follows because
$X^{n}$ is i.i.d. and the measurement channels are memoryless, and from the
data processing inequality applied to the Markov chain in (113), $(e)$ follows
from the definitions of $V_{i,[1:J]}$ and $U_{i,[1:J]}$, $(f)$ follows from
the Markov chain
$(U_{i,[1:J]},V_{i,[1:J]})-\widetilde{X}_{i,[1:J]}-Y_{i,[1:J]}$ for all
$i\in[1:n]$, and $(g)$ follows from the Markov chain
$V_{i,[1:J]}-U_{i,[1:J]}-\widetilde{X}_{i,[1:J]}-Z_{i,[1:J]}$ for all
$i\in[1:n]$.

Introduce a uniformly distributed time-sharing random variable $\displaystyle
Q\\!\sim\\!\text{Unif}[1\\!:\\!n]$ independent of other random variables.
Define $X\\!=\\!X_{Q}$,
$\displaystyle\widetilde{X}_{j}\\!=\\!\widetilde{X}_{Q,j}$, $\displaystyle
Y_{j}\\!=\\!Y_{Q,j}$, $\displaystyle Z_{j}\\!=\\!Z_{Q,j}$,
$V_{j}\\!=\\!V_{Q,j}$, $U_{j}\\!=\\!(U_{Q,j},\\!Q)$, and $f_{j}=f_{Q,j}$ so
that $\displaystyle(Q,V_{j})\\!-U_{j}-\widetilde{X}_{j}-X-(Y_{j},Z_{j})$ form
a Markov chain for all $j\in[1:J]$. The converse proof of Theorem 3 follows by
letting $\delta_{n}\rightarrow 0$.

Cardinality Bounds follow by using the support lemma as in Section V-B. ∎

##  VII Conclusion

We derived the secrecy-storage-privacyDec-privacyEve(-distortion) regions for
lossless and lossy single-function computations with a remote source. The
remote source model allows to model multiple sequences observed by a single
terminal as multiple noisy measurements of a hidden source, which allows to
measure the diversity gains. The equivocation measure common in the literature
was replaced with a mutual information metric, which resulted in simpler
notation and easier interpretations. A new privacy metric was considered to
bound the information leakage to a fusion center about the remote source
sequence. Bounds for the storage and privacy leakage to the eavesdropper rates
were shown to be different, unlike in the previous models. Inner and outer
bounds for multiple asynchronous function computations within the same network
were given to illustrate the effects of joint constraints for all terminals
involved in any function computation. These bounds differ only in the Markov
chain conditions imposed. We evaluated the rate region for a single-function
computation problem by solving an information bottleneck problem for binary
input symmetric output channels. In future work, we will consider multi-
function computations with multiple transmitting terminals for each function
computation and derive the rate regions for two-function computations with two
transmitting terminals if a set of symmetry conditions are satisfied.

## References

  * [1] A. C. Yao, “Protocols for secure computations,” in _IEEE Symp. Foundations Comp. Sci._ , Chicago, IL, Nov. 1982, pp. 160–164.
  * [2] ——, “How to generate and exchange secrets,” in _IEEE Symp. Foundations Comp. Sci._ , Toronto, ON, Canada, Oct. 1986, pp. 162–167.
  * [3] R. Mijumbi, J. Serrat, J.-L. Gorricho, N. Bouten, F. De Turck, and R. Boutaba, “Network function virtualization: State-of-the-art and research challenges,” _IEEE Commun. Surveys Tuts._ , vol. 18, no. 1, pp. 236–262, Firstquarter 2016.
  * [4] A. Orlitsky and J. R. Roche, “Coding for computing,” _IEEE Trans. Inf. Theory_ , vol. 47, no. 3, pp. 903–917, Mar. 2001.
  * [5] D. Slepian and J. Wolf, “Noiseless coding of correlated information sources,” _IEEE Trans. Inf. Theory_ , vol. 19, no. 4, pp. 471–480, July 1973.
  * [6] A. D. Wyner and J. Ziv, “The rate-distortion function for source coding with side information at the decoder,” _IEEE Trans. Inf. Theory_ , vol. 22, no. 1, pp. 1–10, Jan. 1976.
  * [7] O. Günlü and R. F. Schaefer, “An optimality summary: Secret key agreement with physical unclonable functions,” _Entropy_ , vol. 23, no. 1, Jan. 2021.
  * [8] I. Csiszár and P. Narayan, “Common randomness and secret key generation with a helper,” _IEEE Trans. Inf. Theory_ , vol. 46, no. 2, pp. 344–366, Mar. 2000.
  * [9] O. Günlü, O. İşcan, V. Sidorenko, and G. Kramer, “Code constructions for physical unclonable functions and biometric secrecy systems,” _IEEE Trans. Inf. Forensics Security_ , vol. 14, no. 11, pp. 2848–2858, Nov. 2019.
  * [10] J. Ren, B. D. Boyle, G. Ku, S. Weber, and J. M. Walsh, “Overhead performance tradeoffs - A resource allocation perspective,” _IEEE Trans. Inf. Theory_ , vol. 62, no. 6, pp. 3243–3269, June 2016.
  * [11] M. Bloch, O. Günlü, A. Yener, F. Oggier, H. V. Poor, L. Sankar, and R. F. Schaefer, “An overview of information-theoretic security and privacy: Metrics, limits and applications,” _IEEE J. Sel. Areas Inf. Theory_ , vol. 2, no. 1, pp. 5–22, Mar. 2021.
  * [12] N. Ma and P. Ishwar, “Some results on distributed source coding for interactive function computation,” _IEEE Trans. Inf. Theory_ , vol. 57, no. 9, pp. 6180–6195, Aug. 2011.
  * [13] M. Sefidgaran and A. Tchamkerten, “Computing a function of correlated sources: A rate region,” in _IEEE Int. Symp. Inf. Theory_ , St. Petersburg, Russia, July-Aug. 2011, pp. 1856–1860.
  * [14] B. Nazer and M. Gastpar, “Computation over multiple-access channels,” _IEEE Trans. Inf. Theory_ , vol. 53, no. 10, pp. 3498–3516, Sep. 2007.
  * [15] H. Kowshik and P. R. Kumar, “Optimal function computation in directed and undirected graphs,” _IEEE Trans. Inf. Theory_ , vol. 58, no. 6, pp. 3407–3418, Feb. 2012.
  * [16] S. Kannan and P. Viswanath, “Multi-session function computation and multicasting in undirected graphs,” _IEEE J. Sel. Areas Commun._ , vol. 31, no. 4, pp. 702–713, Mar. 2013.
  * [17] H. Tyagi, P. Narayan, and P. Gupta, “When is a function securely computable?” _IEEE Trans. Inf. Theory_ , vol. 57, no. 10, pp. 6337–6350, Oct. 2011.
  * [18] H. Tyagi and S. Watanabe, “A bound for multiparty secret key agreement and implications for a problem of secure computing,” in _Int. Conf. Theory Appl. Crypt. Techn._ , Copenhagen, Denmark, May 2014, pp. 369–386.
  * [19] ——, “Converses for secret key agreement and secure computing,” _IEEE Trans. Inf. Theory_ , vol. 61, no. 9, pp. 4809–4827, July 2015.
  * [20] V. Prabhakaran and K. Ramchandran, “On secure distributed source coding,” in _IEEE Inf. Theory Workshop_ , Lake Tahoe, CA, Sep. 2007, pp. 442–447.
  * [21] M. Goldenbaum, H. Boche, and H. V. Poor, “On secure computation over the binary modulo-2 adder multiple-access wiretap channel,” in _IEEE Inf. Theory Workshop_ , Cambridge, U.K., Sep. 2016, pp. 21–25.
  * [22] D. Gunduz, E. Erkip, and H. V. Poor, “Secure lossless compression with side information,” in _IEEE Inf. Theory Workshop_ , Porto, Portugal, May 2008, pp. 169–173.
  * [23] G. R. Kurri and V. M. Prabhakaran, “Secure computation to hide functions of inputs,” in _IEEE Int. Symp. Inf. Theory_ , Los Angeles, CA, June 2020, pp. 972–977.
  * [24] H. Tyagi, “Distributed function computation with confidentiality,” _IEEE J. Sel. Areas Commun._ , vol. 31, no. 4, pp. 691–701, Apr. 2013.
  * [25] W. Tu and L. Lai, “On function computation with privacy and secrecy constraints,” _IEEE Trans. Inf. Theory_ , vol. 65, no. 10, pp. 6716–6733, Oct. 2019.
  * [26] O. Günlü, “Key agreement with physical unclonable functions and biometric identifiers,” Ph.D. dissertation, TU Munich, Germany, Nov. 2018, published by Dr.-Hut Verlag in Feb. 2019.
  * [27] O. Günlü and G. Kramer, “Privacy, secrecy, and storage with multiple noisy measurements of identifiers,” _IEEE Trans. Inf. Forensics Security_ , vol. 13, no. 11, pp. 2872–2883, Nov. 2018.
  * [28] T. M. Cover and J. A. Thomas, _Elements of Information Theory_ , 2nd ed. Hoboken, NJ: John Wiley & Sons, 2012.
  * [29] O. Günlü, R. F. Schaefer, and G. Kramer, “Private authentication with physical identifiers through broadcast channel measurements,” in _IEEE Inf. Theory Workshop_ , Visby, Sweden, Aug. 2019, pp. 1–5.
  * [30] O. Günlü, R. F. Schaefer, and H. V. Poor, “Biometric and physical identifiers with correlated noise for controllable private authentication,” July 2020, [Online]. Available: arxiv.org/abs/2001.00847.
  * [31] Y. Wang, S. Rane, S. C. Draper, and P. Ishwar, “A theoretical analysis of authentication, privacy, and reusability across secure biometric systems,” _IEEE Trans. Inf. Forensics Security_ , vol. 7, no. 6, pp. 1825–1840, July 2012.
  * [32] O. Günlü, K. Kittichokechai, R. F. Schaefer, and G. Caire, “Controllable identifier measurements for private authentication with secret keys,” _IEEE Trans. Inf. Forensics Security_ , vol. 13, no. 8, pp. 1945–1959, Aug. 2018.
  * [33] O. Günlü, “Multi-entity and multi-enrollment key agreement with correlated noise,” _IEEE Trans. Inf. Forensics Security_ , vol. 16, pp. 1190–1202, 2021.
  * [34] A. E. Gamal and Y.-H. Kim, _Network Information Theory_. Cambridge, U.K.: Cambridge University Press, 2011.
  * [35] N. Tishby, F. C. Pereira, and W. Bialek, “The information bottleneck method,” in _Allerton Conf. Comm., Control, Comp._ , Monticello, IL, Sep. 1999, pp. 368–377.
  * [36] H. Witsenhausen and A. Wyner, “A conditional entropy bound for a pair of discrete random variables,” _IEEE Trans. Inf. Theory_ , vol. 21, no. 5, pp. 493–501, Sep. 1975.
  * [37] R. G. Gallager, _Low-Density Parity-Check Codes_. Cambridge, MA: M.I.T. Press, 1963.
  * [38] O. Günlü, G. Kramer, and M. Skórski, “Privacy and secrecy with multiple measurements of physical and biometric identifiers,” in _IEEE Int. Conf. Commun. Netw. Security_ , Florence, Italy, Sep. 2015, pp. 89–94.
  * [39] N. Chayat and S. Shamai, “Extension of an entropy property for binary input memoryless symmetric channels,” _IEEE Trans. Inf. Theory_ , vol. 35, no. 5, pp. 1077–1079, Sep. 1989.
  * [40] M. H. Yassaee, M. R. Aref, and A. Gohari, “Achievability proof via output statistics of random binning,” _IEEE Trans. Inf. Theory_ , vol. 60, no. 11, pp. 6760–6786, Nov. 2014.
  * [41] J. M. Renes and R. Renner, “Noisy channel coding via privacy amplification and information reconciliation,” _IEEE Trans. Inf. Theory_ , vol. 57, no. 11, pp. 7377–7385, Nov. 2011.
  * [42] M. Bloch, _Lecture Notes in Information-Theoretic Security_. Atlanta, GA: Georgia Inst. Technol., July 2018.
  * [43] M. H. Yassaee, M. R. Aref, and A. Gohari, “Achievability proof via output statistics of random binning,” _IEEE Trans. Inf. Theory_ , vol. 60, no. 11, pp. 6760–6786, Nov. 2014.
  * [44] M. Bloch and J. Barros, _Physical-layer Security_. Cambridge, U.K.: Cambridge University Press, 2011.
  * [45] I. Csiszár and J. Körner, _Information Theory: Coding Theorems for Discrete Memoryless Systems_ , 2nd ed. Cambridge, U.K.: Cambridge University Press, 2011\.