# Privacy in Cloud Computing
through Immersion-based Coding

Haleh Hayati, Nathan van de Wouw, Carlos Murguia The research leading to these
results has received funding from the European Union’s Horizon Europe
programme under grant agreement No 101069748 – SELFY project. Haleh Hayati and
Nathan van de Wouw are with the Department of Mechanical Engineering, Dynamics
and Control Group, Eindhoven University of Technology, The Netherlands.
(Emails<EMAIL_ADDRESS><EMAIL_ADDRESS>Carlos Murguia is with the
Department of Mechanical Engineering, Dynamics and Control Group, Eindhoven
University of Technology, The Netherlands, and with the School of Electrical
Engineering and Robotics, Queensland University of Technology, Brisbane,
Australia. (Emails<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Cloud computing enables users to process and store data remotely on high-
performance computers and servers by sharing data over the Internet. However,
transferring data to clouds causes unavoidable privacy concerns. Here, we
present a synthesis framework to design coding mechanisms that allow sharing
and processing data in a privacy-preserving manner without sacrificing data
utility and algorithmic performance. We consider the setup where the user aims
to run an algorithm in the cloud using private data. The cloud then returns
some data utility back to the user (utility refers to the service that the
algorithm provides, e.g., classification, prediction, AI models, etc.). To
avoid privacy concerns, the proposed scheme provides tools to co-design: 1)
coding mechanisms to distort the original data and guarantee a prescribed
differential privacy level; 2) an equivalent-but-different algorithm (referred
here to as the target algorithm) that runs on distorted data and produces
distorted utility; and 3) a decoding function that extracts the true utility
from the distorted one with a negligible error. Then, instead of sharing the
original data and algorithm with the cloud, only the distorted data and target
algorithm are disclosed, thereby avoiding privacy concerns. The proposed
scheme is built on the synergy of differential privacy and system immersion
tools from control theory. The key underlying idea is to design a higher-
dimensional target algorithm that embeds all trajectories of the original
algorithm and works on randomly encoded data to produce randomly encoded
utility. We show that the proposed scheme can be designed to offer any level
of differential privacy without degrading the algorithm’s utility. We present
two use cases to illustrate the performance of the developed tools: privacy in
optimization/learning algorithms and a nonlinear networked control system.

##  I Introduction

Scientific and technological advancements in today’s hyper-connected world
have resulted in a massive amount of user data being collected and processed
by hundreds of companies over public networks and servers. Companies use this
data to provide personalized services and targeted advertising. However, this
technology has come at the cost of an alarming loss of privacy in society.
Depending on their resources, adversaries can infer sensitive (private)
information about users from public data available on the internet and/or
unsecured networks/servers. A motivating example of this privacy loss is the
potential use of data from smart electrical meters by criminals, advertising
agencies, and governments for monitoring the presence and activities of
occupants [1, 2]. Other examples are privacy loss caused by information
sharing in distributed control systems and cloud computing [3]; the use of
travel data for traffic estimation in intelligent transportation systems [4];
and data collection and sharing by the Internet-of-Things (IoT) [5]. These,
and many more, privacy challenges have drawn the interests of researchers from
different fields (e.g., information theory, computer science, and control
engineering) to the broad research subject of privacy and security in data-
sharing and cloud computing, see [6, 7, 8, 9, 10, 11, 12].
In recent years, various privacy-preserving schemes have been proposed to
address privacy concerns in data-sharing and cloud computing. Most of them
rely on perturbation techniques (inject randomness to distort data) or
cryptographic tools (encrypt data/algorithms before disclosure), see [13].
Perturbation-based techniques use information-theoretic privacy metrics [14,
15, 16, 17] and/or differential privacy [7, 18]. In these techniques, random
vectors drawn from known probability distributions are injected into sensitive
data before sharing it with the cloud. Although these methods effectively
reduce the amount of private data that can be inferred, the induced distortion
is never removed, which inevitably leads to performance degradation of the
utility when used to run algorithms in the cloud.
In standard cryptographic methods, data is encrypted before sharing and then
decrypted in the cloud before processing, see [19]. This technique is suitable
for making eavesdropping attacks over communication networks difficult.
However, it is still vulnerable to insider attacks in the cloud (as they have
the decryption key). Alternatively, Homomorphic Encryption (HE) methods do not
require data to be decrypted before processing. They allow computations over
plain data by performing appropriate computations on the encrypted data [20,
21]. However, standard HE methods (e.g., Paillier and ElGamal encryption [22])
work over finite rings of integers, which implies that the original algorithm
must be reformulated to also work on rings of integers [23]. This
reformulation, although effective when possible, is hard to accomplish for
general algorithms. In the literature, it has only been successfully performed
on small classes of algorithms (mainly algorithms with linear transitions and
a fairly small number of variables). Even when the reformulation is possible,
mapping algorithms working on the reals to operate on finite rings leads to
performance degradation and large computational overhead [24].
In summary, although current solutions improve privacy of data and algorithms,
they often do it at the expense of data utility and algorithm performance
degradation. Balancing these tradeoffs is a key challenge when implementing
privacy solutions for cloud computing. Hence, novel privacy-preserving schemes
must be designed to provide strict privacy guarantees with a fair
computational cost and without compromising the application performance and
utility.
The aim of this work is to devise synthesis tools that allow designing coding
mechanisms that protect private information and allow the implementation of
remote _dynamic algorithms_ – algorithms that perform iterations and have
memory. We propose a coding scheme built on the synergy of random coding and
_system immersion_ tools [25] from control theory. The key idea is to treat
the original algorithm as a dynamical system that we seek to _immerse_ into a
higher-dimensional system (the so-called target algorithm), i.e., trajectories
of the target algorithm must embed all trajectories of the original (up to a
random (left-)invertible transformation). The target algorithm must be
designed such that: 1) trajectories of the original algorithm are
immersed/embedded in its trajectories; and 2) it operates on randomly encoded
higher-dimensional data to produce randomly encoded utility. We formulate the
coding mechanism at the user side as a random change of coordinates that maps
original private data to a higher-dimensional space. Such coding enforces that
the target algorithm produces an encoded higher-dimensional version of the
utility of the original algorithm. The encoded utility is decoded at the user
side using a left-inverse of the encoding map. This is basically a
_homomorphic encryption scheme that operates over the reals_ instead of finite
rings of integers (as in the standard case). Working over the reals provides
much more freedom to redesign algorithms to work on encoded/encrypted data,
which translates to our scheme being able to tackle a larger class of
(nonlinear and high-dimensional) dynamic algorithms.
Another difference compared to HE schemes is the privacy guarantee. While
standard HE schemes provide hard security guarantees, the scheme we propose
gives arbitrarily strong probabilistic guarantees (in terms of differential
privacy). We show that our scheme provides the same utility as the original
algorithm (i.e., when no coding is employed to protect against data
inference), (practically) reveals no information about private data, can be
applied to large-scale algorithms (hundreds of thousands of algorithm
variables, as commonly occurs in deep-learning and large-scale simulations),
is computationally efficient, and offers any desired level of differential
privacy without degrading the algorithm utility (because the induced
distortion is removed at the user side).
Summarizing, the main contribution of the paper is a prescriptive synthesis
framework (i.e., it uses the original undistorted algorithm as the basis) that
allows joint design of coding schemes to randomize data before disclosure and
new (target) algorithms that work on encoded data, does not lead to
performance degradation, and provides any desired level of differential
privacy. We have explored using preliminary versions of these ideas for
privacy in Federated Learning, see [26], [27], and in remote anomaly
detection, see [28]. Here, we generalize these results to a large class of
dynamic algorithms (modeled as a set of difference/differential parameter-
varying equations that take user data and produce utility) and show the
performance of the proposed tools on two use cases – privacy in
optimization/learning algorithms and nonlinear networked control systems.
The remainder of this paper is organized as follows. In Section II, we
formulate the problem of designing the immersion-based coding for privacy of
dynamical algorithms. In Section III, we construct a prescriptive solution
design to the proposed problem using random affine maps. In Section IV, we
prove that the proposed solution can provide any desired level of differential
privacy. In Section V, we provide a synthesis procedure to summarize the
operation methodology for the proposed mechanism. In Section VI, the
performance of the immersion-based coding is shown for two use cases of
privacy in optimization/learning algorithms and nonlinear networked control
systems. Conclusions are drawn in Section VII.

_Notation_ : The symbol ${\mathds{R}}$ stands for the real numbers, and
${\mathds{R}}^{+}$ denotes the set of positive real numbers. The symbol
${\mathds{N}}$ stands for the set of natural numbers, and ${\mathds{N}}_{0}$
denotes the set of naturals with zero. For $x\in{\mathds{R}}^{n}$, the
Euclidian norm is denoted by $||x||$, $||x||^{2}=x^{\top}x$, where ⊤ denotes
transposition, and the $l^{1}$ norm as $\|x\|_{1}=\sum_{i=1}^{N}|x^{i}|$,
$x=(x^{1},\ldots,x^{N})^{\top}$. The $n\times n$ identity matrix is denoted by
$I_{n}$ or simply $I$ if $n$ is clear from the context. Similarly, $n\times m$
matrices composed of only ones and only zeros are denoted by
$\mathbf{1}_{n\times m}$ and $\mathbf{0}_{n\times m}$, respectively, or simply
$\mathbf{1}$ and $\mathbf{0}$ when their dimensions are clear. The notation
$x\sim\mathcal{N}[\mu^{x},\Sigma^{x}]$ means $x\in{\mathds{R}}^{n}$ is a
normally distributed random vector with mean $E[x]=\mu^{x}\in{\mathds{R}}^{n}$
and covariance matrix
$E[(x-\mu^{x})(x-\mu^{x})^{\top}]=\Sigma^{x}\in{\mathds{R}}^{n\times n}$,
where $E[a]$ denotes the expected value of the random vector $a$. The notation
$y\sim\operatorname{Laplace}(\mu^{y},\Sigma^{y})$ stands for Laplace random
vector $y\in{\mathds{R}}^{m}$ with mean $E(y)=\mu^{y}$ and scale parameter
$\frac{1}{2}E[(y-\mu^{y})(y-\mu^{y})^{\top}]=\Sigma^{y}\in{\mathds{R}}^{m\times
m}$. The left inverse of matrix $X$ is denoted by $X^{L}$ where $X^{L}X=I$.

##  II Problem Formulation

The setting that we consider is the following. The user aims to run an
algorithm remotely (in the cloud) using her/his local data $y_{k}$ to produce
some data utility $u_{k}$ (what the algorithm returns), see Fig. 1(a).
However, the user does not want to share the original data $y_{k}$ as it
contains sensitive private information that could be inferred. The goal of our
proposed privacy-preserving scheme is to devise an encoding mechanism to mask
the original data _and the algorithm to be run in the cloud_ so that inference
of sensitive information from the encoded disclosed data is as hard as
possible (in a probabilistic Differential-Privacy (DP) sense) _without
degrading the performance of the encoded algorithm_ (so a homomorphic
probabilistic scheme).
As the original algorithm running in the cloud, we consider discrete-time
dynamic algorithms of the form:

$\Sigma=\left\\{\begin{array}[]{l}\begin{aligned}
\zeta_{k+1}&=f\left(\zeta_{k},y_{k},w_{k}\right),\\\
u_{k}&=g\left(\zeta_{k},y_{k},w_{k}\right),\end{aligned}\end{array}\right.$
(1)

with time-index $k\in{\mathds{N}}_{0}$, algorithm input data
$y_{k}\in\mathbb{R}^{n_{y}}$ (the user data), generated data utility
$u_{k}\in\mathbb{R}^{n_{u}}$, algorithm internal variables
$\zeta_{k}\in\mathbb{R}^{n_{\zeta}}$, unknown disturbance (or reference
signal) $w_{k}\in\mathbb{R}^{n_{w}}$, and functions
$f:\mathbb{R}^{n_{\zeta}}\times\mathbb{R}^{n_{y}}\times\mathbb{R}^{n_{w}}\rightarrow\mathbb{R}^{n_{\zeta}}$
and
$g:\mathbb{R}^{n_{\zeta}}\times\mathbb{R}^{n_{y}}\times\mathbb{R}^{n_{w}}\rightarrow\mathbb{R}^{n_{u}}$.
This algorithm description covers a large class of algorithms that have memory
and recursively converge to some value of interest – e.g., algorithms for
learning, searching, simulation, control, and estimation.
To prevent adversaries from eavesdropping on the network or in the cloud
itself to access private data, we propose a privacy-preserving coding scheme
to distort data before transmission. Let the user distort the original data
before disclosure through some encoding map
$\pi_{1}:\mathbb{R}^{n_{y}}\rightarrow\mathbb{R}^{{\tilde{n}_{y}}}$,
$\tilde{y}_{k}=\pi_{1}(y_{k})$, and send the distorted $\tilde{y}_{k}$ to the
cloud to run the algorithm. In general, running the original algorithm
$\Sigma$ on the distorted data $\tilde{y}_{k}$ will not yield the same utility
$u_{k}$ that would be obtained if it was run using $y_{k}$. That is, privacy-
preserving methods that do not account for (remove) the distortion induced by
the encoding map $\pi_{1}(\cdot)$ lead to performance degradation. This is
precisely the problem with perturbation-based techniques for privacy
preservation (like with standard, non-homomorphic DP tools).
To tackle these challenges, the scheme, proposed here, seeks to design a new
dynamic algorithm $\tilde{\Sigma}$ (referred hereafter to as the target
algorithm) that runs on encoded data $\tilde{y}_{k}$, operates over the reals,
and returns an encoded utility, $\tilde{u}_{k}$, that can be used to extract
the true utility $u_{k}$ at the user side without distortion, i.e., a
homomorphic encryption scheme that operates over the reals. Letting the
encoding map and target algorithm work over the reals (as opposed to standard
HE schemes that operate over finite rings of integers) provides much more
freedom to design $\pi_{1}(\cdot)$ and $\tilde{\Sigma}$, which will allow
tackling a larger class of (nonlinear and high-dimensional) dynamic
algorithms.
We seek to design $\pi_{1}(\cdot)$ such that
$\tilde{y}_{k}=\pi_{1}(y_{k})\in\mathbb{R}^{\tilde{n}_{y}}$ is of higher
dimension than $y_{k}\in\mathbb{R}^{n_{y}}$, i.e., $\tilde{n}_{y}>n_{y}$. We
impose this condition to create redundancy in both the encoding map and target
algorithm. Redundancy will allow us to inject randomness that can be traced
through the algorithm, removed at the user side, and used to enforce an
arbitrary level of differential privacy. Consider the higher-dimensional
target algorithm:

$\tilde{\Sigma}=\left\\{\begin{array}[]{l}\begin{aligned}
\tilde{\zeta}_{k+1}&=\tilde{f}(\tilde{\zeta}_{k},\tilde{y}_{k},w_{k}),\\\
\tilde{u}_{k}&=\tilde{g}(\tilde{\zeta}_{k},\tilde{y}_{k},w_{k}),\end{aligned}\end{array}\right.$
(2)

with distorted user data $\tilde{y}_{k}\in\mathbb{R}^{\tilde{n}_{y}}$,
$\tilde{n}_{y}>n_{y}$, distorted data utility
$\tilde{u}_{k}\in\mathbb{R}^{\tilde{n}_{u}}$, $\tilde{n}_{u}>n_{u}$, generated
by the algorithm, algorithm internal variables
$\tilde{\zeta}_{k}\in\mathbb{R}^{\tilde{n}_{\zeta}}$,
$\tilde{n}_{\zeta}>n_{\zeta}$, and functions
$\tilde{f}:\mathbb{R}^{\tilde{n}_{\zeta}}\times\mathbb{R}^{\tilde{n}_{y}}\times\mathbb{R}^{n_{w}}\rightarrow\mathbb{R}^{\tilde{n}_{\zeta}}$
and
$\tilde{g}:\mathbb{R}^{\tilde{n}_{\zeta}}\times\mathbb{R}^{\tilde{n}_{y}}\times\mathbb{R}^{n_{w}}\rightarrow\mathbb{R}^{\tilde{n}_{u}}$.
Our goal is to design the encoding map $\pi_{1}(\cdot)$ and the functions
$\tilde{f}(\cdot)$ and $\tilde{g}(\cdot)$ such that $\tilde{\Sigma}$ can work
on the encoded data $\tilde{y}_{k}=\pi_{1}(y_{k})$ to produce encoded utility
$\tilde{u}_{k}$ that can be used to extract $u_{k}$.
At a system-theoretic level, what we seek to accomplish is to embed
trajectories $(\zeta_{k},u_{k})$ of the original algorithm $\Sigma$ (in
response to the user data $y_{k}$) into trajectories
$(\tilde{\zeta}_{k},\tilde{u}_{k})$ of the target algorithm (in response to
the encoded user data $\tilde{y}_{k}$). That is, we aim to design
$\pi_{1}(\cdot)$ and $\tilde{\Sigma}$ so that there exists a bijection between
trajectories of both algorithms (referred here to as the _immersion map_), and
thus, having a trajectory of the target algorithm uniquely determines a
trajectory of the original one through the immersion map. The latter hints at
the possibility of running the target algorithm in the cloud (instead of the
original) on encoded data $\tilde{y}_{k}$, and using its trajectories
$(\tilde{\zeta}_{k},\tilde{u}_{k})$ to extract ${u}_{k}$. So a fundamental
question is how do we design $\pi_{1}(\cdot)$ and $\tilde{\Sigma}$ to
accomplish this bijection?
In system and control theory, this type of embedding between systems
trajectories is referred to as _system immersion_ and has been used for
nonlinear adaptive control [25, 29] and output regulation [30, 31]. However,
using system immersion tools in the context of privacy in cloud computing has
been largely unexplored in the literature. In what follows, we discuss the
necessary mathematical machinery and provide sufficient conditions to
simultaneously design the encoding map $\pi_{1}(\cdot)$ and the target
algorithm $\tilde{\Sigma}$ to accomplish immersion and utility extraction
using ideas from system immersion. This will culminate in a problem
description on immersion-based coding for privacy at the end of this section.

###  II-A Immersion-based Coding

Consider the original and target algorithms, $\Sigma$ and $\tilde{\Sigma}$, in
(1) and (2), respectively. We say that $\Sigma$ is immersed in
$\tilde{\Sigma}$ if $\tilde{n}_{\zeta}>{n}_{\zeta}$ and there exists a
function
$\pi_{2}:\mathbb{R}^{n_{\zeta}}\rightarrow\mathbb{R}^{\tilde{n}_{\zeta}}$ that
satisfies $\tilde{\zeta}_{k}=\pi_{2}(\zeta_{k})$ for all $\zeta_{k}$ and
$\tilde{\zeta}_{k}$ generated by $\Sigma$ and $\tilde{\Sigma}$, respectively.
That is, any trajectory of $\tilde{\Sigma}$ is a trajectory of $\Sigma$
through the mapping $\pi_{2}(\cdot)$, and $\pi_{2}(\cdot)$ is an immersion
because the dimension of its image is ${\tilde{n}_{\zeta}}>{{n}_{\zeta}}$. We
refer to this map $\pi_{2}(\cdot)$ as the _immersion map_.

(a)

(b)

Figure 1: The schematic diagram of a networked dynamical algorithm (a) without
privacy and (b) with immersion-based coding for privacy.

To guarantee that $\Sigma$ is immersed in $\tilde{\Sigma}$ (in the sense
introduced above), we need to impose conditions on the functions shaping the
algorithms, their initial conditions, and the encoding and immersion maps,
$(f,g,\zeta_{0},\pi_{1},\pi_{2},\tilde{f},\tilde{g},\tilde{\zeta}_{0})$. In
particular, we require to design
$(\pi_{1},\pi_{2},\tilde{f},\tilde{\zeta}_{0})$ such that
$\tilde{\zeta}_{k}=\pi_{2}(\zeta_{k})$ for all $k$ and
$(\zeta_{k},\tilde{\zeta}_{k})\in\mathbb{R}^{{n}_{\zeta}}\times\mathbb{R}^{\tilde{n}_{\zeta}}$,
i.e., the manifold $\tilde{\zeta}_{k}=\pi_{2}(\zeta_{k})$ must be forward
invariant under the algorithms in (1) and (2). Define the off-the-manifold
error $e_{k}:=\tilde{\zeta}_{k}-\pi_{2}(\zeta_{k})$. The manifold
$\tilde{\zeta}_{k}=\pi_{2}(\zeta_{k})$ is forward invariant if and only if the
origin of the error dynamics:

$\displaystyle{e}_{k+1}=\tilde{\zeta}_{k+1}-\pi_{2}(\zeta_{k+1})$ (3)
$\displaystyle=\tilde{f}(e_{k}+\pi_{2}(\zeta_{k}),\pi_{1}(y_{k}),w_{k})-\pi_{2}(f({\zeta}_{k},{y_{k}},w_{k})),$

is a fixed point, i.e., $e_{k}=\mathbf{0}$ implies $e_{k+1}=\mathbf{0}$ for
all $k\in{\mathds{N}}_{0}$ [32]. Substituting $e_{k}=\mathbf{0}$ and
$e_{k+1}=\mathbf{0}$ in (LABEL:errordynamic) leads to

$\tilde{f}(\pi_{2}(\zeta_{k}),\pi_{1}(y_{k}),w_{k})-\pi_{2}(f({\zeta}_{k},{y}_{k},w_{k}))=\mathbf{0}.$
(4)

Therefore, $\tilde{\zeta}_{k}=\pi_{2}(\zeta_{k})$ is satisfied for all $k$ if:
(1) the initial condition of (2), $\tilde{\zeta}_{0}$, satisfies
$\tilde{\zeta}_{0}=\pi_{2}({\zeta}_{0})$, which leads to $e_{0}=\mathbf{0}$
(start on the manifold); and (2) the dynamics of both algorithms match under
the immersion and encoding maps, i.e., (4) is satisfied (invariance condition
on the manifold). We refer to these two conditions as the _immersion
conditions_.
Immersion Conditions:

$\left\\{\begin{aligned}
&\tilde{f}(\pi_{2}(\zeta_{k}),\pi_{1}(y_{k}),w_{k})=\pi_{2}(f({\zeta}_{k},{y}_{k},w_{k})),\text{
(invariance)}\\\ &\tilde{\zeta}_{0}=\pi_{2}({\zeta}_{0}).\text{ (start on the
manifold)}\end{aligned}\right.\vspace{-2.5mm}$ (5)

So far, we have derived sufficient conditions (5) for trajectories of the
original algorithm to be immersed into trajectories of the target algorithm in
terms of $(f,\tilde{f},{\zeta}_{0},{\tilde{\zeta}}_{0},\pi_{1},\pi_{2})$.
Next, we derive conditions on the utility maps $(g,\tilde{g})$ so that, given
the distorted utility $\tilde{u}_{k}$, the true utility $u_{k}$ can be
extracted at the user side. That is, we need conditions under which there
exists a _left-invertible mapping_
$\pi_{3}:\mathbb{R}^{n_{u}}\rightarrow\mathbb{R}^{\tilde{n}_{u}}$ satisfying
$\tilde{u}_{k}=\pi_{3}(u_{k})$ for all $k$, which leads to
$u_{k}=\pi_{3}^{L}(\tilde{u}_{k})$ for some left-inverse function
$\pi_{3}^{L}(\cdot)$ of $\pi_{3}(\cdot)$, i.e.,
$\pi_{3}^{L}\circ\pi_{3}(s)=s$. By substituting the expressions of $u_{k}$ and
$\tilde{u}_{k}$, in (1)-(2), and the coding and immersion maps,
$\tilde{y}_{k}=\pi_{1}(y_{k})$ and $\tilde{\zeta}_{k}=\pi_{2}(\zeta_{k})$, we
have that $\tilde{u}_{k}=\pi_{3}(u_{k})$ implies

$\pi_{3}({g}({\zeta}_{k},{y}_{k},w_{k}))=\tilde{g}(\pi_{2}(\zeta_{k}),\pi_{1}(y_{k}),w_{k})).$
(6)

Therefore, to be able to extract $u_{k}$ from $\tilde{u}_{k}$, we need to
design $(\tilde{g},\pi_{1},\pi_{2})$ so that (6) is satisfied for given
$g(\cdot)$, all $\zeta_{k}$, $y_{k}$, and $w_{k}$, and some left-invertible
mapping $\pi_{3}(\cdot)$.

We now have all the ingredients to pose the problem we seek to address.

######  Problem 1.

_(Immersion-based Coding for Privacy)_ For given $(f,g,\zeta_{0})$ of the
original algorithm (1), design an encoding map $\pi_{1}(\cdot)$, immersion map
$\pi_{2}(\cdot)$, and $(\tilde{f},\tilde{g},\tilde{\zeta}_{0})$ of the target
algorithm (2) so that: (a) the immersion conditions (5) hold; and (b) there
exists a left-invertible function $\pi_{3}(\cdot)$ satisfying (6).

The flowchart of the original algorithm and the target algorithm are shown in
Fig. 1.

######  Remark 1.

Note that solutions to Problem 1 characterize a class of encoding maps and
target algorithms for which we can design homomorphic encryption schemes (a
prescriptive design, i.e., for given $(f,g,\zeta_{0})$) that operate over the
reals. However, this class is infinite-dimensional (over a function space). It
leads to an underdetermined algebraic problem with an infinite dimensional
solution space. To address this aspect of the problem, we impose structure on
the maps we seek to design. We restrict to random affine maps composed of
linear coordinate transformations and additive random processes. In what
follows, we prove that this class of maps is sufficient to guarantee an
arbitrary level of differential privacy.

##  III Affine Solution to Problem 1

In this section, we construct a prescriptive solution to Problem 1 using
random affine maps. Let the user data encoding map $\pi_{1}(\cdot)$, the
immersion map $\pi_{2}(\cdot)$, and the utility map $\pi_{3}(\cdot)$ be affine
functions of the form:

$\left\\{\begin{aligned}
\tilde{y}_{k}&=\pi_{1}(y_{k}):=\Pi_{1}y_{k}+b^{1}_{k},\\\\[-1.42262pt]
\tilde{\zeta}_{k}&=\pi_{2}(\zeta_{k}):=\Pi_{2}\zeta_{k},\\\\[-1.42262pt]
\tilde{u}_{k}&=\pi_{3}(u_{k}):=\Pi_{3}u_{k}+b^{3}_{k},\end{aligned}\right.$
(7)

for matrices $\Pi_{1}\in\mathbb{R}^{\tilde{n}_{y}\times n_{y}}$,
$\Pi_{2}\in\mathbb{R}^{\tilde{n}_{\zeta}\times n_{\zeta}}$, and
$\Pi_{3}\in\mathbb{R}^{\tilde{n}_{u}\times n_{u}}$ to be designed, with
$\tilde{n}_{y}>n_{y}$, $\tilde{n}_{u}>n_{u}$, $\tilde{n}_{\zeta}>n_{\zeta}$,
and some i.i.d. multivariate random processes
$b^{1}_{k}\in\mathbb{R}^{\tilde{n}_{y}}$ and
$b^{3}_{k}\in\mathbb{R}^{\tilde{n}_{u}}$. Therefore, for these maps, the
immersion conditions (5) amounts to $\tilde{\zeta}_{0}=\Pi_{2}\zeta_{0}$ and

$\displaystyle\tilde{f}\left(\Pi_{2}\zeta_{k},\Pi_{1}y_{k}+b^{1}_{k},w_{k}\right)=\Pi_{2}f\left({\zeta}_{k},{y}_{k},w_{k}\right).$
(8)

Let the function $\tilde{f}(\cdot)$ be of the form:

$\tilde{f}\left(\tilde{\zeta}_{k},\tilde{y}_{k},w_{k}\right)=M_{3}f\left(M_{2}\tilde{\zeta}_{k},M_{1}\tilde{y}_{k},w_{k}\right),$
(9)

for some matrices $M_{1}\in\mathbb{R}^{n_{y}\times\tilde{n}_{y}}$,
$M_{2}\in\mathbb{R}^{n_{\zeta}\times\tilde{n}_{\zeta}}$, and
$M_{3}\in\mathbb{R}^{\tilde{n}_{\zeta}\times n_{\zeta}}$ to be designed.
Hence, the immersion condition (8) takes the form:

$M_{3}f\left(M_{2}\tilde{\zeta}_{k},M_{1}\tilde{y}_{k},w_{k}\right)=\Pi_{2}f\left({\zeta}_{k},{y}_{k},w_{k}\right).$
(10)

Note that the choice of $\tilde{f}$ in (9) provides a prescriptive design in
terms of the original algorithm function $f(\cdot)$. That is, we exploit the
knowledge of the original algorithm and build the target algorithm on top of
it in an algebraic manner.
To satisfy (10), we must enforce
$M_{1}\left(\Pi_{1}y_{k}+b^{1}_{k}\right)=y_{k}$,
$M_{2}\Pi_{2}{\zeta}_{k}={\zeta}_{k}$, and $M_{3}=\Pi_{2}$, which implies that
$M_{1}\Pi_{1}=I$, $M_{2}\Pi_{2}=I$, and $M_{1}b^{1}_{k}=\mathbf{0}$ (i.e.,
$b^{1}_{k}\in\text{ker}[M_{1}]$). From this brief analysis, we can draw the
following conclusions: 1) $\Pi_{1}$ and $\Pi_{2}$ _must be of full column
rank_ (i.e., $\text{rank}[\Pi_{1}]=n_{y}$ and
$\text{rank}[\Pi_{2}]=n_{\zeta}$); 2) $M_{1}$ and $M_{2}$ are left inverses of
$\Pi_{1}$ and $\Pi_{2}$, i.e. $M_{1}=\Pi^{L}_{1}$ and $M_{2}=\Pi^{L}_{2}$
(which always exists given the rank of $\Pi_{1}$ and $\Pi_{2}$); 3)
$b^{1}_{k}\in\text{ker}[\Pi^{L}_{1}]$ (this kernel is always nontrivial
because $\Pi_{1}$ is full column rank by construction); and 4)
$M_{3}=\Pi_{2}$. Combining all these facts, the final form of
$\tilde{f}(\cdot)$ in (2) is given by

$\tilde{f}\big{(}\tilde{\zeta}_{k},\tilde{y}_{k},w_{k}\big{)}=\Pi_{2}f\big{(}\Pi^{L}_{2}\tilde{\zeta}_{k},\Pi^{L}_{1}\tilde{y}_{k},w_{k}\big{)}.$
(11)

At every $k$, vector $b^{1}_{k}$ is designed to satisfy
$\Pi_{1}^{L}b^{1}_{k}=\mathbf{0}$ and used to distort the coding map
$\pi_{1}(\cdot)$ in (7). The role of $b^{1}_{k}$ is to randomize the data so
that we can guarantee differential privacy. The idea is that because the user
knows that $b^{1}_{k}$ draws realizations from the kernel of $\Pi_{1}^{L}$,
the distortion induced by it can be removed at the user side (following the
same reasoning as standard HE, but operating over the reals and proving a DP
guarantee). To enforce that $b^{1}_{k}\in\text{ker}[\Pi_{1}^{L}]$, without
loss of generality, we let it be of the form $b^{1}_{k}=N_{1}s_{k}$ for some
matrix $N_{1}\in\mathbb{R}^{\tilde{n}_{y}\times(\tilde{n}_{y}-n_{y})}$
expanding the kernel of $\Pi_{1}^{L}$ (i.e., $\Pi_{1}^{L}N_{1}=\mathbf{0}$)
and an arbitrary i.i.d. process $s_{k}\in\mathbb{R}^{(\tilde{n}_{y}-n_{y})}$.
This structure for $b^{1}_{k}$ always satisfies
$\Pi_{1}^{L}b^{1}_{k}=\Pi_{1}^{L}N_{1}s_{k}=\mathbf{0}$, for $s_{k}$ with
arbitrary probability distribution.
Up to this point, we have designed $(\tilde{f},\pi_{1},\pi_{2})$ to satisfy
the immersion conditions (5) for the affine maps in (7). Next, we seek to
design the utility map $\tilde{g}(\cdot)$ to satisfy the encoding introduced
in (7) ($\tilde{u}_{k}=\Pi_{3}u_{k}+b^{3}_{k}$) and so that there exists a
decoding function that extracts the true utility $u_{k}$ from the encoded
$\tilde{u}_{k}$ (i.e., left-invertibility of $\pi_{3}(\cdot)$). To design
$\tilde{g}(\cdot)$, similarly to what we did for $\tilde{f}(\cdot)$ above (we
skip detailed steps for the sake of readability), we match the utility
condition in (6) with the proposed affine maps in (7) which yields:

$\tilde{g}(\tilde{\zeta}_{k},\tilde{y}_{k},w_{k}):=\Pi_{3}{g}(\Pi_{2}^{L}\tilde{\zeta}_{k},\Pi_{1}^{L}\tilde{y}_{k},w_{k})+\Pi_{4}\tilde{y}_{k},$
(12)

for full rank $\Pi_{3}\in\mathbb{R}^{\tilde{n}_{u}\times n_{u}}$ and
$\Pi_{4}\in\mathbb{R}^{\tilde{n}_{u}\times\tilde{n}_{y}}$ to be designed. From
this expression of $\tilde{g}(\cdot)$, it follows that
$b_{k}^{3}:=\Pi_{4}\tilde{y}_{k}$ and $\tilde{u}_{k}$ is an affine function of
$u_{k}$ given by

$\tilde{u}_{k}=\Pi_{3}u_{k}+\Pi_{4}\tilde{y}_{k}.$ (13)

The encoded data $\tilde{y}_{k}$ is used in $\tilde{g}(\cdot)$ to inject
randomness into $\tilde{u}_{k}$. Finally, we design the extracting function
$\pi_{3}^{L}(\cdot)$ satisfying the left invertibility condition,
$\pi_{3}^{L}\circ\pi_{3}(s)=s$. Given (13), the latter condition is written as

$\displaystyle\pi_{3}^{L}\left(\Pi_{3}u_{k}+\Pi_{4}\tilde{y}_{k}\right)=u_{k},$
(14)

which trivially leads to

$\pi_{3}^{L}\left(\tilde{u}_{k},\tilde{y}_{k}\right):=\Pi_{3}^{L}\left(\tilde{u}_{k}-\Pi_{4}\tilde{y}_{k}\right).$
(15)

Matrix $\Pi_{3}^{L}$ always exists due to the rank of $\Pi_{3}$.

We can now state the proposed solution to Problem 1.

######  Proposition 1.

_(Solution to Problem 1)_ For given full rank matrices
$\Pi_{1}\in\mathbb{R}^{\tilde{n}_{y}\times n_{y}}$,
$\Pi_{2}\in\mathbb{R}^{\tilde{n}_{\zeta}\times n_{\zeta}}$,
$\Pi_{3}\in\mathbb{R}^{\tilde{n}_{u}\times n_{u}}$, and
$\Pi_{4}\in\mathbb{R}^{\tilde{n}_{u}\times\tilde{n}_{y}}$, matrix
$N_{1}\in\mathbb{R}^{\tilde{n}_{y}\times(\tilde{n}_{y}-n_{y})}$ expanding the
kernel of $\Pi_{1}^{L}$ _(_ i.e., $\Pi_{1}^{L}N_{1}=\mathbf{0}$_)_ , and
random process $s_{k}\in\mathbb{R}^{(\tilde{n}_{y}-n_{y})}$, the encoding map:

$\tilde{y}_{k}=\Pi_{1}y_{k}+N_{1}s_{k},\vspace{-1mm}$ (16)

target algorithm:

$\tilde{\Sigma}=\left\\{\begin{array}[]{l}\begin{aligned}
\tilde{\zeta}_{k+1}&=\Pi_{2}f(\Pi_{2}^{L}\tilde{\zeta}_{k},\Pi_{1}^{L}\tilde{y}_{k},w_{k}),\\\
\tilde{u}_{k}&=\Pi_{3}{g}(\Pi_{2}^{L}\tilde{\zeta}_{k},\Pi_{1}^{L}\tilde{y}_{k},w_{k})+\Pi_{4}\tilde{y}_{k},\end{aligned}\end{array}\right.$
(17)

and inverse function:

$\pi_{3}^{L}\left(\tilde{u}_{k},\tilde{y}_{k}\right)=\Pi_{3}^{L}\left(\tilde{u}_{k}-\Pi_{4}\tilde{y}_{k}\right),$
(18)

provide a solution to Problem 1.

_Proof_ : Proposition 1 follows from the discussion provided in the solution
section above, Section III. $\blacksquare$

######  Remark 2.

In Proposition 1, we present the first part of the design of the proposed
immersion-based coding mechanism for privacy. Note that the proposed scheme is
independent of the nature of the user data $y_{k}$ and utility $u_{k}$, and
does not require any assumption on the original algorithm. These features make
the proposed scheme suitable to enforce privacy for a large class of linear
and nonlinear high-dimensional algorithms.

######  Remark 3.

This manuscript primarily focuses on immersion-based coding for privacy of
discrete-time algorithms operating in the cloud. It is noteworthy that it can
be proved that the application of the proposed coding and target algorithm in
Proposition 1 can be extended for privacy of continuous-time systems. This
extension highlights the wider application of the immersion-based coding,
providing a solution for cloud-based privacy covering discrete and continuous-
time algorithms.

###  III-A Algorithms with Different Time-Scales

The class of algorithms considered in (1), and the results that followed,
operates on a single time scale. That is, the algorithm reacts to the received
$y_{k}$, iterates once according to $f(\cdot)$ and $g(\cdot)$, and sends the
utility $u_{k}$ back to the user. This is repeated sequentially between the
user and the cloud. Algorithms that fit this class are, e.g., control,
monitoring, and federated learning schemes. Note, however, that there are many
algorithms that operate on a different time scale from that of the user. That
is, there are algorithms that receive the user data $y_{k}$ at time $k$,
iterate locally multiple times in the cloud (say for $t=1,\ldots,T$), and only
after a number of local iterations ($T$), the data utility $u_{k}$ is sent
back to the user. Algorithms that fit this class are, for instance, general
learning algorithms where it is often the case that the complete data set is
uploaded to the cloud, the training is done there by running gradient-like
steps multiple times, and only when the cost function has decreased to an
acceptable level, the final trained model is sent back to the user.
For the sake of completeness, we concisely provide the corresponding coding
result for algorithms with different time scales. Consider discrete-time
dynamic algorithms of the form:

$\Sigma=\left\\{\begin{array}[]{l}\begin{aligned}
\zeta_{t+1}&=f\left(\zeta_{t},y_{k},w_{t}\right),\hskip
2.84526ptt=0,\ldots,T-1,\\\ u_{k}&=g\left(\zeta_{T},y_{k},w_{T}\right),\\\
\end{aligned}\end{array}\right.$ (19)

with _global_ time-index $k\in{\mathds{N}}_{0}$, _local_ time-index
$t\in{\mathds{N}}_{0}$, user data $y_{k}\in\mathbb{R}^{n_{y}}$, data utility
$u_{k}\in\mathbb{R}^{n_{u}}$, algorithm internal variables
$\zeta_{t}\in\mathbb{R}^{n_{\zeta}}$, unknown disturbance (or reference
signal) $w_{t}\in\mathbb{R}^{n_{w}}$, and functions $(f,g)$ of appropriate
dimensions.
Further, consider the corresponding higher-dimensional target algorithm:

$\tilde{\Sigma}=\left\\{\begin{array}[]{l}\begin{aligned}
\tilde{\zeta}_{t+1}&=\tilde{f}(\tilde{\zeta}_{t},\tilde{y}_{k},w_{t}),\hskip
2.84526ptt=0,\ldots,T-1,\\\
\tilde{u}_{k}&=\tilde{g}(\tilde{\zeta}_{T},\tilde{y}_{k},w_{T}),\end{aligned}\end{array}\right.$
(20)

with distorted user data $\tilde{y}_{k}\in\mathbb{R}^{\tilde{n}_{y}}$,
$\tilde{n}_{y}>n_{y}$, distorted data utility
$\tilde{u}_{k}\in\mathbb{R}^{\tilde{n}_{u}}$, $\tilde{n}_{u}>n_{u}$, algorithm
variables $\tilde{\zeta}_{t}\in\mathbb{R}^{\tilde{n}_{\zeta}}$,
$\tilde{n}_{\zeta}>n_{\zeta}$, and functions $(\tilde{f},\tilde{g})$ of
appropriate dimensions.
Following the reasoning described in the above section, for algorithm (19) and
corresponding target algorithm (20), we let the user data encoding map, the
immersion map, and the utility map be affine functions of the form:

$\left\\{\begin{aligned}
\tilde{y}_{k}&=\Pi_{1}y_{k}+N_{1}s_{k},\\\\[-1.42262pt]
\tilde{\zeta}_{t}&=\Pi_{2}\zeta_{t},\\\\[-1.42262pt]
\tilde{u}_{k}&=\Pi_{3}u_{k}+\Pi_{4}\tilde{y}_{k},\end{aligned}\right.$ (21)

for some full rank matrices $(\Pi_{1},\Pi_{2},\Pi_{3},\Pi_{4},N_{1})$ of
appropriate dimensions. We can now state the problem we seek to address for
(19)-(21).

######  Problem 2.

_(Privacy-Preserving Coding, Two Time Scales)_ For given $(f,g,\zeta_{0})$ of
the original algorithm (19), design an encoding matrix $\Pi_{1}$, random
process $s_{k}$, and immersion matrix $\Pi_{2}$ in (21), and
$(\tilde{f},\tilde{g},\tilde{\zeta}_{0})$ of the target algorithm (20) so
that: (a) $\tilde{\zeta}_{t}=\Pi_{2}\zeta_{t}$ is forward invariant (the
immersion condition); and (b) there exists a left-invertible matrix $\Pi_{3}$
and full rank matrix $\Pi_{4}$ satisfying
$\tilde{u}_{k}=\Pi_{3}u_{k}+\Pi_{4}\tilde{y}_{k}$.

Problem 2 is an analogue to Problem 1 for systems with two time scales.
Following the lines of the solution to Problem 1, we provide a solution to
Problem 2 in the following corollary of Proposition 1.

######  Corollary 1.

_(Solution to Problem 2)_ For given full rank matrices
$(\Pi_{1},\Pi_{2},\Pi_{3},\Pi_{4})$ of appropriate dimensions, matrix $N_{1}$
expanding the kernel of $\Pi_{1}^{L}$, and random process $s_{k}$, the
encoding map:

$\tilde{y}_{k}=\Pi_{1}y_{k}+N_{1}s_{k},\vspace{-1mm}$ (22)

target algorithm:

$\left\\{\begin{array}[]{l}\begin{aligned}
\tilde{\zeta}_{t+1}&=\Pi_{2}f(\Pi_{2}^{L}\tilde{\zeta}_{t},\Pi_{1}^{L}\tilde{y}_{k},w_{t}),\hskip
2.84526ptt=0,\ldots,T-1,\\\
\tilde{u}_{k}&=\Pi_{3}{g}(\Pi_{2}^{L}\tilde{\zeta}_{T},\Pi_{1}^{L}\tilde{y}_{k},w_{T})+\Pi_{4}\tilde{y}_{k},\end{aligned}\end{array}\right.$
(23)

and inverse input map:

${u}_{k}=\Pi_{3}^{L}\left(\tilde{u}_{k}-\Pi_{4}\tilde{y}_{k}\right),$ (24)

provide a solution to Problem 2.

_Proof_ : The proof of Corollary 1 follows the same lines as the proof of
Proposition 1. Only the time scales of the encoded signals change. The proof
is omitted here for the sake of brevity.
So far, we have presented the proposed immersion-based coding for two classes
of discrete-time algorithms built around stochastic affine maps. Note that the
only constraint on these maps is that they are full-rank. In the next section,
we state sufficient conditions for the proposed privacy scheme to guarantee a
prescribed level of differential privacy.

##  IV Privacy Guarantees

The private element that we consider in the proposed scheme is privacy of the
user data and utility. Even though we encode the original algorithm (which
effectively makes inference of it from the encoded disclosed target algorithm
hard to accomplish), the algorithm itself is not considered private. The
algorithm is encoded to make it work on encoded user data $\tilde{y}_{k}$ to
produce encoded utility $\tilde{u}_{k}$. Hence, in what follows we focus on
how to enforce differential privacy of $(y_{k},u_{k})$ by properly selecting
the random process $s_{k}$ and the encoding matrices in the affine maps of
user data $\tilde{y}_{k}=\Pi_{1}y_{k}+N_{1}s_{k}$ and utility
$\tilde{u}_{k}=\Pi_{3}u_{k}+\Pi_{4}\tilde{y}_{k}$.
A privacy-level analysis of random affine maps of the form (7) has been
discussed in the literature, see [33] (cryptanalysis) and [34] (DP). However,
the guarantees they show are for square and invertible encoding matrices. In
our scheme, we cannot directly apply those results as our encoding matrices
($\Pi_{1}$ and $\Pi_{3}$) are rectangular (tall matrices). We need rectangular
matrices to be able to exploit their kernels to remove the injected distortion
at the user side. A complication with this architecture is that the covariance
matrix of $N_{1}s_{k}$ (which is part of the user data encoding mechanism) is
degenerate regardless of the probability distribution of $s_{k}$. The latter
prevents us from using off-the-shelf tools to design the affine maps to
guarantee differential privacy.
In what follows, we provide a tailored solution to guarantee DP for the class
of mechanisms that we consider. In particular, we prove that the proposed
scheme, with full-column rank encoding matrices, can provide any desired level
of differential privacy without reducing the accuracy and performance of the
original algorithm.

###  IV-A Differential Privacy

In the context of databases, $(\epsilon,\delta)$-Differential Privacy (DP)
[18] was introduced as a probabilistic framework to quantify privacy of
probabilistic maps. The constant $\epsilon\geq 0$ quantifies how similar
(different) are outputs of a mechanism on _adjacent_ datasets, say
$(\mathcal{D}$ and $\mathcal{D}^{\prime})$, and $\delta$ is a constant shift
used when the ratio of the probabilities of $\mathcal{D}$ and
$\mathcal{D}^{\prime}$ under the mechanism cannot be bounded by $e^{\epsilon}$
(see Definition 2 below). With an arbitrarily given $\delta$, a mechanism with
a smaller $\epsilon$ makes _adjacent_ data less distinguishable and hence more
private.

######  Definition 1.

[Adjacency] Let $\mathcal{X}$ denote the space of all possible datasets. We
say that $\mathcal{D}\in\mathcal{X}$ and $\mathcal{D}^{\prime}\in\mathcal{X}$
are adjacent if they differ on a single element.

######  Definition 2.

[$(\epsilon,\delta)$-Differential Privacy [35]] The random mechanism
$\mathcal{M}:\mathcal{X}\rightarrow\mathcal{R}$ with domain $\mathcal{X}$ and
range $\mathcal{R}$ is said to provide $(\epsilon,\delta)$-differential
privacy, if for any two adjacent datasets
$\mathcal{D},\mathcal{D}^{\prime}\in\mathcal{X}$ and for all measurable sets
$\mathcal{S}\subseteq\mathcal{R}$_:_

$\operatorname{Pr}(\mathcal{M}(\mathcal{D})\in\mathcal{S})\leq
e^{\epsilon}\operatorname{Pr}\left(\mathcal{M}\left(\mathcal{D}^{\prime}\right)\in\mathcal{S}\right)+\delta.$
(25)

If $\delta=0$, $\mathcal{M}$ is said to satisfy $\epsilon$-differential
privacy. From Definition 2, we have that a mechanism provides DP if its
probability distribution satisfies (25) for some $\epsilon$ and $\delta$.
Then, if we seek to design the mechanism to guarantee DP, we need to shape its
probability distribution. This is usually done by injecting noise into the
data we seek to encode. The noise statistics must be designed in terms of the
sensitivity of the data to be encoded. Sensitivity refers to the maximum
change of the data due to the difference in a single element of the dataset.

######  Definition 3 (Sensitivity).

_:_ Given two adjacent datasets
$\mathcal{D},\mathcal{D}^{\prime}\in\mathcal{X}$, and a query function
$q:\mathcal{X}\rightarrow\mathcal{R}$ (a deterministic function of datasets).
The sensitivity of $q(\cdot)$ is formulated as

$\Delta^{q}_{1}=\sup_{\mathcal{D},\mathcal{D}^{\prime}}\left\|q\right(\mathcal{D}\left)-q\left(\mathcal{D}^{\prime}\right)\right\|_{1}.$
(26)

A differential privacy mechanism $\mathcal{M}$ based on the sensitivity (26)
needs to be designed so that the differential privacy condition (25) holds.

###  IV-B Immersion-based Coding Differential Privacy Guarantee

We formulate the problem of designing the variables of the privacy mechanisms
in (16) and (17) (or (22) and (23) for the two time scales algorithm) that, at
every time-step, guarantee differential privacy of the user and utility data
$(y_{k},u_{k})$ from the disclosed distorted data in the cloud,
$(\tilde{y}_{k},\tilde{u}_{k})$. We seek to design matrices $\Pi_{1}$,
$\Pi_{3}$, and $\Pi_{4}$, and random process $s_{k}$ such that $\tilde{y}_{k}$
and $\tilde{u}_{k}$ are $\epsilon^{y}$ and $\epsilon^{u}$-differentially
private, respectively.

######  Problem 3.

_(Element-Wise Differential Privacy)_ Given the desired privacy levels
$\epsilon^{y}$ and $\epsilon^{u}$, design the variables of privacy mechanisms
in (16) and (17) (or (22) and (23) for the two time scales algorithm) such
that at time $k$, each element of $\tilde{y}_{k}$ and $\tilde{u}_{k}$,
$\tilde{y}^{i}_{k}$ and $\tilde{u}^{j}_{k}$, $i\in\\{1,...,\tilde{n}_{y}\\}$
and $j\in\\{1,...,\tilde{n}_{u}\\}$, are $\epsilon^{y}$ and
$\epsilon^{u}$-differentially private, respectively, for any measurable
$\mathcal{S}_{y},\mathcal{S}_{u}\subset\mathbb{R}$, i.e.,

$\left\\{\begin{aligned}
\mathbb{P}(\tilde{y}^{i}_{k}(y_{k})\in\mathcal{S}_{y})&\leq
e^{\epsilon^{y}}\mathbb{P}(\tilde{y}^{i}_{k}(y^{\prime}_{k})\in\mathcal{S}_{y}),\\\\[2.84526pt]
\mathbb{P}(\tilde{u}^{j}_{k}(u_{k})\in\mathcal{S}_{u})&\leq
e^{\epsilon^{u}}\mathbb{P}(\tilde{u}^{j}_{k}(u^{\prime}_{k})\in\mathcal{S}_{u}),\\\\[2.84526pt]
&\text{for adjacent}\left(y_{k},y^{\prime}_{k}\right)\text{ and
}\left(u_{k},u^{\prime}_{k}\right).\end{aligned}\right.$ (27)

### Solution to Problem 3

As it is standard in DP literature, we let the stochastic process $s_{k}$
follow a multivariate i.i.d. Laplace distribution with mean
$E[s_{k}]=:\mu\in{\mathds{R}}^{\tilde{n}_{y}-n_{y}}$ and covariance matrix
$E[(s_{k}-\mu)(s_{k}-\mu)^{\top}]=:\sigma I_{(\tilde{n}_{y}-n_{y})}$, for some
$\sigma>0$, i.e., $s_{k}\sim\operatorname{Laplace}(\mu,\sigma
I_{(\tilde{n}_{y}-n_{y})})$.
We start with the privacy guarantee for $\tilde{y}_{k}$. According to
Definition 3, given adjacent user data $y_{k},y^{\prime}_{k}\in\mathcal{Y}$,
where $\mathcal{Y}$ denotes the space of all user data sets, the sensitivity
of $y_{k}$ is as follows:

$\Delta_{1}^{y}=\sup_{y_{k},y^{\prime}_{k}\in\mathcal{Y}}\left\|y_{k}-y^{\prime}_{k}\right\|_{1}.$
(28)

Because $s_{k}\sim\operatorname{Laplace}(\mu,\sigma I)$, and given the privacy
encoding mechanisms (16) or (22), each element of $\tilde{y}_{k}$ also follows
a Laplace distribution:

$\displaystyle\tilde{y}_{k}^{i}\sim\operatorname{Laplace}\left(N_{1}^{i}\mu+\Pi_{1}^{i}y_{k},||N_{1}^{i}||_{2}\sigma\right),$
(29)

where $N_{1}^{i}$ and $\Pi_{1}^{i}$ are the $i$-th rows of matrices $N_{1}$
and $\Pi_{1}$, respectively. It follows that

$\displaystyle\mathbb{P}\left(\tilde{y}^{i}_{k}(y_{k})\in\mathcal{S}_{y}\right)=\left(\tfrac{1}{2\left\|N_{1}^{i}\right\|_{2}\sigma}\right)\int_{\mathcal{S}_{y}}e^{\frac{-\left\|p-\Pi_{1}^{i}y_{k}-N_{1}^{i}\mu\right\|_{1}}{\left\|N_{1}^{i}\right\|_{2}\sigma}}dp$
(30)
$\displaystyle\stackrel{{\scriptstyle(\mathrm{a})}}{{\leq}}e^{\frac{\left\|\Pi_{1}^{i}\left({y}_{k}-y^{\prime}_{k}\right)\right\|_{1}}{\left\|N_{1}^{i}\right\|_{2}\sigma}}\left(\tfrac{1}{2\left\|N_{1}^{i}\right\|_{2}\sigma}\right)\int_{\mathcal{S}_{y}}e^{\frac{-\left\|p-\Pi_{1}^{i}y^{\prime}_{k}-N_{1}^{i}\mu\right\|_{1}}{\left\|N_{1}^{i}\right\|_{2}\sigma}}dp$
$\displaystyle=e^{\frac{\left\|\Pi_{1}^{i}\left({y}_{k}-y^{\prime}_{k}\right)\right\|_{1}}{\left\|N_{1}^{i}\right\|_{2}\sigma}}\mathbb{P}\left(\tilde{y}^{i}_{k}(y_{k}^{\prime})\in\mathcal{S}_{y}\right),$

where (a) follows from the following triangle inequality

$\displaystyle-\left\|p-\Pi_{1}^{i}{y}_{k}-N_{1}^{i}\mu\right\|_{1}\leq-\left\|p-\Pi_{1}^{i}y^{i\prime}_{k}-N_{1}^{i}\mu\right\|_{1}$
(31) $\displaystyle\hskip
128.0374pt+\left\|\Pi_{1}^{i}\left({y}_{k}-y^{i\prime}_{k}\right)\right\|_{1}.$

Due to the sensitivity relation (28), we have

$\left\|\Pi_{1}^{i}\left({y}_{k}-y^{\prime}_{k}\right)\right\|_{1}\leq\left\|\Pi_{1}^{i}\right\|_{1}\Delta_{1}^{y}.$
(32)

Hence, inequality (30) implies

$\mathbb{P}\left(\tilde{y}^{i}_{k}(y_{k})\in\mathcal{S}_{y}\right)\leq
e^{\frac{\left\|\Pi_{1}^{i}\right\|_{1}\Delta_{1}^{y}}{\left\|N_{1}^{i}\right\|_{2}\sigma}}\mathbb{P}\left(\tilde{y}^{i}_{k}(y_{k}^{\prime})\in\mathcal{S}_{y}\right).$
(33)

Therefore, $\epsilon^{y}$-differential privacy of $y^{i}_{k}$ given
$\tilde{y}_{k}$, for all $i\in\\{1,...,\tilde{n}_{y}\\}$, is guaranteed for
$\Pi_{1}$, $N_{1}$, and $\sigma$ satisfying

$\frac{||\Pi_{1}^{i}||_{1}\Delta_{1}^{y}}{||N_{1}^{i}||_{2}\sigma}\leq{\epsilon^{y}}.$
(34)

Following the same reasoning, it can be shown that $u^{j}_{k}$ is
$\epsilon^{u}$-differentially private for given $\tilde{u}_{k}$ and all
$j\in\\{1,...,\tilde{n}_{u}\\}$, if $\Pi_{3}$, $\Pi_{4}$, $N_{1}$, and
$\sigma$ satisfy

$\frac{||\Pi_{3}^{j}||_{1}\Delta_{1}^{u}}{||\Pi_{4}N_{1}^{j}||_{2}\sigma}\leq{\epsilon^{u}},$
(35)

where $\Pi_{3}^{j}$ is the $j$-th row of matrix $\Pi_{3}$,

$\Delta_{1}^{u}=\sup_{u_{k},u^{\prime}_{k}\in\mathcal{U}}\left\|u_{k}-u^{\prime}_{k}\right\|_{1},$
(36)

and $\mathcal{U}$ denoting the utility space.
Hence, according to the differential privacy conditions, (34) and (35), to
increase the privacy guarantees (by decreasing $\epsilon^{y}$ and
$\epsilon^{u}$), we need to design $\Pi_{1}$ and $\Pi_{3}$ as small as
possible while selecting $\sigma$ (the covariance of $s_{k}$) and $\Pi_{4}$ as
large as possible. From (16), (17), (22), and (23), it is apparent that by
choosing small $\Pi_{1}$ and $\Pi_{3}$, and large $\sigma$ and $\Pi_{4}$,
$\tilde{y}_{k}$ and $\tilde{u}_{k}$ are close to $N_{1}s_{k}$ and
$\Pi_{4}N_{1}s_{k}$, respectively, and (practically) independent from
${y}_{k}$ and ${u}_{k}$. Note that $\left\|N_{1}^{i}\right\|_{2}$,
$i\in\\{1,\dots,\tilde{n}_{y}\\}$, must be nonzero, i.e., we need to design
$N_{1}$ without zero rows. The latter is not a technical constraint as, for a
given $N_{1}$ with nonzero rows, $\Pi_{1}$ can be obtained by solving the
equation $\Pi_{1}^{L}N_{1}=\mathbf{0}$ and computing the right inverse of
$\Pi_{1}^{L}$.

###  IV-C Perfect Security

A perfectly secure cryptosystem is a secure system against adversaries with
unlimited computing resources and time, see [36]. In [37], Shannon proves that
a necessary condition for an encryption method to be perfectly secure is that
the uncertainty of the secret key is larger than or equal to the uncertainty
of the plaintext, see [38]. He proposes a one-time pad encryption scheme in
which the key is randomly selected and never used again. The one-time pad
gives unbounded entropy of the key space, i.e., infinite key space, which
provides perfect security. Perfect secrecy is lost when the key is not random
or if it is reused. This perfect security idea can be used to assess the
performance of our proposed coding mechanism. Given the fact that in the
proposed mechanism, (7), the encoding keys, $(\Pi_{1},s_{k})$ and
$(\Pi_{3},\Pi_{4}N_{1}s_{k})$, are random, change in every iteration, and
provide an infinite-dimensional key space (the support of $s_{k}$), can be
considered perfectly secure.
Perfect secrecy of the proposed coding mechanisms can also be concluded from
the differential privacy point of view. In [39], the authors define perfect
secrecy in terms of DP. They state that a mechanism
$\mathcal{M}:\mathcal{X}\rightarrow\mathcal{R}$, with domain $\mathcal{X}$ and
range $\mathcal{R}$ is perfectly secret if

$\frac{\operatorname{Pr}(M(\mathcal{D})\in\mathcal{S})}{\operatorname{Pr}\left(M\left(\mathcal{D}^{\prime}\right)\in\mathcal{S}\right)}=1=e^{0},$
(37)

for any two adjacent $\mathcal{D},\mathcal{D}^{\prime}\in\mathcal{X}$ and for
all measurable sets $\mathcal{S}\subseteq\mathcal{R}$. Then, the output of the
mechanism reveals no information about private data. Comparing the definition
of perfect secrecy in (37) and the definition of differential privacy
(Definition 2), we can conclude that a differentially private mechanism is
perfectly secret if $(\epsilon,\delta)$ equal zero.
The relation between design variables of the proposed encoding mechanism and
its differential privacy guarantees is shown in (34) and (35). Therefore, to
have perfect secrecy, we need $(\epsilon^{y},\epsilon^{u})=\mathbf{0}$. While
this can not be achieved, $(\epsilon^{y},\epsilon^{u})$ can be made
arbitrarily small by selecting small $\Pi_{1}$ and $\Pi_{2}$ and large
$\sigma$ and $\Pi_{4}$.

##  V General Guidelines for Implementation

In what follows, we provide a synthesis procedure to summarize the design
steps and operation methodology for the proposed mechanism.

Synthesis and Operation Procedure:

  * $\bullet$

Randomly select ”small” full rank matrices $(\Pi_{1},\Pi_{2},\Pi_{3})$, and
”large” full rank matrix $\Pi_{4}$ of appropriate dimensions (see Proposition
1).

  * $\bullet$

Compute base $N_{1}$ of the kernel of $\Pi_{1}^{L}$.

  * $\bullet$

Fix the distribution of the random process $s_{k}$ in (16).

  * $\bullet$

At every time step $k\in{\mathds{N}}_{0}$, encode $y_{k}$ according to (16) at
the user side and send $\tilde{y}_{k}$ to the cloud.

  * $\bullet$

Have the cloud run the target algorithm in (17) using the received encoded
$\tilde{y}_{k}$.

  * $\bullet$

The cloud sends $\tilde{u}_{k}$ back to the user.

  * $\bullet$

The user decodes the encoded utility signal using the inverse function in
(18).

##  VI Case Studies

In this section, we show the performance of the immersion-based coding
algorithm on two use cases – privacy in optimization/learning algorithms and
privacy in a nonlinear networked control system.

###  VI-A Immersion-based Coding for Privacy in Optimization/Learning
algorithms

Machine learning (ML) has been successfully used in a wide variety of
applications for multiple fields and industries. However, gathering extensive
amounts of training data poses a challenge for ML systems. Commonly, increased
data leads to improved ML model performance, necessitating the need for large
datasets often sourced from various origins. Nonetheless, the process of
gathering and using such data, along with developing ML models, presents
significant privacy risks due to the potential exposure of private
information.
In recent years, various privacy-preserving schemes have been implemented to
address the privacy leakage in ML. Most of them rely on cryptography-based
techniques such as Secure Multiparty Computation (SMC) [40] and Homomorphic
Encryption (HE) [41], and perturbation-based techniques such as Differential
Privacy (DP) [42]. Although current solutions improve privacy of ML
algorithms, they often do this at the expense of model performance and system
efficiency.
In this paper, we propose a privacy-preserving machine learning framework
through the immersion-based coding algorithm. The main idea is to treat the
optimization algorithm employed in the standard ML process as a dynamical
system that we seek to immerse into a higher-dimensional system. We have
explored the use of preliminary version of the ideas on this paper for privacy
in federated learning with Stochastic Gradient Descent (SGD) as the
optimization algorithm [26]. In this work, we generalize these results and
implement immersion-based coding to encode all types of gradient descent
optimization algorithms and employ the encoded optimizers to train machine-
learning models.

####  VI-A1 Learning Model Parameters using Gradient Descent

Learning the parameters of a machine learning model is a nonlinear
optimization problem. The algorithms that are used to solve these problems are
typically variants of gradient descent [43]. Simply put, gradient descent
starts at a random point (set of parameters for the model), then, at each
step, computes the gradient of the nonlinear function being optimized, called
the loss function, and updates the parameters so as to decrease the gradient.
This process continues until the algorithm converges to a local optimum.
Hence, the optimal model parameters vector is obtained by
$w^{*}=\arg\min_{w}l\left({w},\mathcal{D}\right)$, with database $\mathcal{D}$
of size $n_{D}$, model parameters vector $w$, and loss function
$l\left({w},\mathcal{D}\right)$.
In gradient descent optimization algorithms, the model parameters are updated
following $T$ iterations of the optimizers that can generally be modeled as
follows:

$\text{Optimizer}\left\\{\begin{aligned}
&w_{{t+1}}={w}_{t}-p({w}_{t},\mathcal{D}),\\\\[2.84526pt]
&t=0,1,\cdots,T-1,\\\\[2.84526pt] &w^{*}=w_{T},\end{aligned}\right.$ (38)

where $w_{{t}}\in\mathbb{R}^{n_{w}}$ denotes the model parameters vector at
the $t$-th epoch of the optimization algorithm, $T$ is the total number of
epochs, and $p(\cdot,\cdot)$ is a gradient-based function that can be defined
for each gradient descent optimizer, separately.
Stochastic Gradient Descent (SGD) is one of the most common gradient descent
optimization techniques in machine learning [43]. For SGD, function
$p(\cdot,\cdot)$ can be written as follows:

$p({w}_{t},\mathcal{D}):=\eta\nabla{l}({w}_{t},\mathcal{Y}_{t}),$ (39)

where $\eta>0$ is learning rate, $\nabla{l}(\cdot,\cdot)$ is the gradient of
loss function ${l}(\cdot,\cdot)$, and $\mathcal{Y}_{t}$ is a mini-batch of
database (a subset of database $\mathcal{D}$) for t-th epoch. Another well-
known gradient descent optimizer in ML is the Adam optimization algorithm
[43]. Adam is an extended version of stochastic gradient descent implemented
in various ML applications. Function $p(\cdot,\cdot)$ can be modeled for Adam
optimizer as follows:

$\text{(Adam)}\left\\{\begin{aligned}
&m_{t+1}=\beta_{1}m_{t}+\left(1-\beta_{1}\right)\nabla
l\left(w_{t},\mathcal{Y}_{t}\right),\\\
&v_{t+1}=\beta_{2}v_{t}+\left(1-\beta_{2}\right)\left(\nabla
l\left(w_{t},\mathcal{Y}_{t}\right)\right)^{2},\\\
&p({w}_{t},\mathcal{D})=\frac{\frac{\alpha}{1-\beta_{1}^{t}}m_{t+1}}{\sqrt{\frac{v_{t+1}}{1-\beta_{2}^{t}}}+\epsilon},\end{aligned}\right.$
(40)

where $m_{{t}}\in\mathbb{R}^{n_{w}}$, and $v_{{t}}\in\mathbb{R}^{n_{w}}$
denote the aggregate of gradients and the sum of the square of past gradients,
respectively, in the $t$-th epoch of the Adam algorithm, $\alpha>0$ is the
step size, $\beta_{1},\beta_{2}\in[0,1)$ are exponential decay rates for the
moment estimates, $\epsilon>0$ is a small constant to avoid division by zero,
and $\mathcal{Y}_{t}$ is a mini-batch of database (a subset of database
$\mathcal{D}$) for t-th epoch.

####  VI-A2 Immersion-based Coding for Privacy-Preserving Gradient Descent
Optimizers

In this section, we encode the gradient descent optimization algorithm given
in (38), following the same technique that we discussed in Corollary 1, which
is the immersion-based coding for remote dynamical algorithms with different
time scales. The encoded optimization algorithm can be employed to provide
privacy for the database and model in machine learning algorithms.
In this application, the optimizer in (38) is the original dynamical system
$\Sigma$ in (19) that we want to immerse to provide privacy. We consider a
setting where the user who owns the database uploads the complete database
$\mathcal{D}$ to the cloud, where the training process is executed by running
the gradient-based optimizer (38). The optimizer iterates $T$ times in the
cloud to converge to a local optimum. Subsequently, the optimal model
parameters vector $w^{*}$ is sent back to the user. Since the user and cloud
send the database and optimal model, which play the role of input and utility
of the algorithm, only once, the number of user iterations is $K=1$, and the
number of local iterations is $T$. Functions $f(\cdot)$ and $g(\cdot)$ in (19)
can be modeled as
$w_{t+1}=f(w_{t},\mathcal{D}):={w}_{t}-p({w}_{t},\mathcal{D})$ and
$w^{*}=g(w_{T}):=w_{T}$ in this case. The model parameters $w_{t}$, database
$\mathcal{D}$, and the optimal model parameters vector $w^{*}$ can be
considered as the internal variables $\zeta_{t}$, input $y$, and utility $u$
of the original algorithm $\Sigma$ in (19).
To implement the user data encoding map in (21) for user database
$\mathcal{D}$, we assume that the user distorts each data of the database
$\mathcal{D}$, $y_{i}\in\mathbb{R}^{{n}_{y}}$, with $i=\\{1,2,...,n_{D}\\}$,
before sending it to the cloud, as follows:

$\tilde{y}_{i}=\pi_{1}\left(y_{i}\right)=\Pi_{1}y_{i}+N_{1}s_{i},\forall
y_{i}\in\mathcal{D},$ (41)

for full column rank matrix $\Pi_{1}\in\mathbb{R}^{\tilde{n}_{y}\times
n_{y}}$, $N_{1}\in\mathbb{R}^{\tilde{n}_{y}\times(\tilde{n}_{y}-{n}_{y})}$
expanding the kernel of $\Pi_{1}^{L}$, random vectors
$s_{i}\in\mathbb{R}^{(\tilde{n}_{y}-{n}_{y})}$, and distorted data
$\tilde{y}_{i}\in\mathbb{R}^{\tilde{n}_{y}}$ with $i=\\{1,2,...,n_{D}\\}$.
Then, user sends the distorted database $\tilde{\mathcal{D}}$, which includes
all distorted data $\tilde{y}_{i}$, $i\in\\{1,...,n_{D}\\}$, to the cloud.
We use the distortion and immersion maps and target dynamical algorithm in
Corollary 1 to immerse the model parameters and optimization algorithm as
follows.

The immersion and utility encoding maps are given by:

$\left\\{\begin{array}[]{l}\tilde{w}_{t}=\Pi_{2}{w}_{t},\\\
\tilde{w}^{*}=\Pi_{3}{w}^{*}+\Pi_{4}\tilde{y}_{0},\end{array}\right.$ (42)

the target gradient descent optimizer is given by:

$(\text{Target
Optimizer})\left\\{\begin{array}[]{l}\tilde{w}_{{t+1}}=\tilde{f}(\tilde{w}_{t},\tilde{\mathcal{D}})\\\
\,\,\,\,\,\,\,\,\,\,\,\,\,:=\tilde{w}_{t}-\Pi_{2}p\left(\Pi_{2}^{L}\tilde{w}_{t},\Pi_{1}^{L}\tilde{\mathcal{D}}\right),\\\
t=0,1,\cdots,T-1,\\\
\tilde{w}^{*}=\tilde{g}(\tilde{w}_{T},\tilde{\mathcal{D}}):=\Pi_{3}{\Pi}_{2}^{L}\tilde{w}_{T}+\Pi_{4}\tilde{y}_{0},\end{array}\right.$
(43)

and the inverse function:

$\pi_{3}^{L}(\tilde{w}^{*},\tilde{\mathcal{D}})=\Pi_{3}^{L}(\tilde{w}^{*}-\Pi_{4}\tilde{y}_{0}),$
(44)

with full rank matrices $\Pi_{2}\in\mathbb{R}^{\tilde{n}_{w}\times{n}_{w}}$,
$\Pi_{3}\in\mathbb{R}^{\tilde{n}_{w}\times n_{w}}$, and
$\Pi_{4}\in\mathbb{R}^{\tilde{n}_{w}\times\tilde{n}_{y}}$.

This approach can be employed to encode all kinds of gradient descent
optimization algorithms that are typically used by machine learning
algorithms. We will refer to machine learning algorithms that utilize
immersion-based coding to preserve privacy as System Immersion-based Machine
Learning (SIML).

(a)

(b)

Figure 2: The comparison of one sample of the original MNIST database and its
encoded format.

####  VI-A3 Case Study of Optimization/Learning algorithms

In this section, we implement our proposed SIML scheme for performance
evaluation using a multi-layer perception (MLP) [44] and a real-world machine
learning database. Our investigation involves utilizing two optimization
tools, i.e., Adam and SGD, on the MNIST database [45]. The experimental
details are described as follows:

(a)

(b)

(c)

(d)

Figure 3: The comparison of the accuracy and loss of ML network in each
iteration with and without the proposed encoding mechanism.

  * $\bullet$

Dataset: We test our algorithm on the standard MNIST database for handwritten
digit recognition, containing 60000 training and 10000 testing instances of
28× 28 size gray-level images, which are flattened to the vectors of dimension
784.

  * $\bullet$

Model: The MLP model is a feed-forward deep neural network with ReLU units and
a softmax layer of 10 classes (corresponding to the ten digits) with two
hidden layers containing 256 hidden units and cross-entropy loss. The MLP
model contains 269,322 parameters.

  * $\bullet$

Optimization tools: As optimization algorithms, the SGD and Adam optimizers
with learning rate 0.001 and $T=50$ epochs are employed to train ML models.

Our implementation uses Keras with a Tensorflow backend.

Based on the database and the MLP model, we have the dimension of input data
$n_{y}=784$ and model parameters vector $n_{w}=269,322$. Then, for the design
of target optimizers and encoding mechanisms, we choose the immersed
dimensions of distorted input and model parameters as $\tilde{n}_{y}=812$ and
$\tilde{n}_{w}=269,579$, respectively. The variables of the encoding
mechanisms (41) and (42), and target optimizer (43) are designed by randomly
selecting small full-rank matrices $\Pi_{1}$-$\Pi_{3}$ and a large full-rank
matrix $\Pi_{4}$ with appropriate dimensions. Then, we compute base $N_{1}$ of
the kernel of $\Pi_{1}^{L}$. The random processes $s_{i}$, for
$i\in\\{1,2,...,n_{D}\\}$, are defined as multivariate Laplace variables with
large means and covariances.
First, in Fig. 2, we show the impact of the proposed coding mechanisms by
comparing one sample of the original MNIST dataset and its encoded format. As
can be seen in this figure, the encoded image closely resembles the random
term in the distorting mechanism, differing significantly from the original
image. Therefore, adversaries can not infer any information from the original
image by accessing the encoded one.
Then, the comparison between training accuracy and loss outcomes of the SIML
and standard ML frameworks is illustrated in Fig. 3. In our implementation,
the SIML framework utilizes target SGD and target Adam optimizers with the
distorted MNIST database, while the traditional ML framework employs original
SGD and Adam optimizers with the original MNIST dataset. It’s evident that the
accuracy and loss metrics under the SIML configuration are similar to those in
the non-privacy setting, indicating that SIML can incorporate cryptographic
methods into ML systems without compromising model accuracy and convergence
rate.

###  VI-B Privacy-aware Networked Control

We illustrate the performance of the immersion-based coding for networked
control systems through a case study of a two-stage chemical reactor with
delayed recycle streams. The authors in [46] propose an adaptive output
feedback controller for this chemical reactor dynamics. We assume the
controller is run in the cloud and aim to run it in a private manner using the
proposed coding scheme. Consider the dynamic model of the reactor (as reported
in [46]):

(a)

(b)

Figure 4: Comparison between the measurement vector $y_{k}$ and the encoded
measurements $\tilde{y}_{k}$.

$\left\\{\begin{array}[]{l}\begin{aligned}
{x}^{1}_{k+1}&=-(\frac{1}{\theta_{1}}+k_{1})x^{1}_{k}+\frac{1-R_{2}}{V_{1}}x^{2}_{k}+\delta_{1}(\vartheta,x_{\tau}),\\\
{x}^{2}_{k+1}&=-(\frac{1}{\theta_{2}}+k_{2})x^{1}_{k}+\frac{R_{1}}{V_{2}}x^{1}_{\tau}+\frac{F_{2}}{V_{2}}u_{k}+\delta_{2}(\vartheta,x_{\tau}),\\\
y_{k}&=x^{1}_{k},\end{aligned}\end{array}\right.$ (45)

with system state $x_{k}=[x^{1}_{k},x^{2}_{k}]$, controller $u_{k}$, and
measurement $y_{k}$, delayed time index $\tau=k-d_{k}$ with unknown time-
varying delay $d_{k}$, parameters $\theta_{1}=\theta_{2}=2$,
$k_{1}=k_{2}=0.3$, $R_{1}=R_{2}=0.5$, $V_{1}=V_{2}=0.5$, $F_{2}=0.5$, and
nonlinear functions with unknown parameters $\vartheta_{i}$, $i=1,2,3$, as
follows:

$\left\\{\begin{array}[]{l}\begin{aligned}
\delta_{1}&=\vartheta_{1}\sin(k)(x^{1}_{\tau})^{2},\\\
\delta_{2}&=\vartheta_{2}\sin(k)(x^{1}_{\tau})^{3}+\vartheta_{3}x^{2}_{k}.\end{aligned}\end{array}\right.$
(46)

We use the following adaptive output feedback controller (see [46] for
details) in order to achieve global adaptive stabilization of system (45):

$\left\\{\begin{array}[]{l}\begin{aligned}
{\hat{z}}_{k+1}&=-r_{k}\left(\hat{z}_{k}+r_{k}y_{k}+l_{k}\rho_{k}y_{k}\right)-r_{k}{\hat{z}}_{k}-r_{k}^{2}y_{k}\\\
&-\max\\{r_{k}\Delta_{k}-r_{k}^{2},\rho_{k}y_{k}^{2}+\zeta_{k}^{2}\\}y_{k},\\\
{r}_{k+1}&=\max\\{r_{k}\Delta_{k}-r_{k}^{2},\rho_{k}y_{k}^{2}+\zeta_{k}^{2}\\},\\\
{l}_{k+1}&=\rho_{k}y_{k}^{2},\\\
u_{k}&=-r_{k}\left(\hat{z}_{k}+r_{k}y_{k}+l_{k}\rho_{k}y_{k}\right),\end{aligned}\end{array}\right.$
(47)

where $\hat{z}_{0}=0$, $r_{0}=l_{0}=1$, and

$\left\\{\begin{array}[]{l}\begin{aligned}
\rho_{k}&=\left(0.1+y_{k}^{2}\right)^{2}+1.01,\\\
\zeta_{k}&=r_{k}^{-\frac{1}{2}}\left(\hat{z}_{k}+r_{k}y_{k}+l_{k}\rho_{k}y_{k}\right),\\\
\Delta_{k}&=2\left(2l_{k}^{2}+l_{k}^{4}\left(1.02+0.2y_{k}^{2}+y_{k}^{4}\right)\right)(1.0404\\\
&+1.224y_{k}^{2}+10.56y_{k}^{4}+6y_{k}^{6}+25y_{k}^{8})\\\
&+4y_{k}^{4}\left(1.02+0.2y_{k}^{2}+y_{k}^{4}\right)^{4}.\end{aligned}\end{array}\right.$
(48)

We consider the setting where the controller (47), (48) is run in the cloud.
We employ the proposed immersion-based coding in Proposition 1 to enable a
secure networked control system. The controller (47) can be reformulated in a
compact form as follows.

$\mathcal{C}:\left\\{\begin{array}[]{l}\begin{aligned}
{x}^{c}_{k+1}&=f_{c}\left(x^{c}_{k},y_{k}\right),\\\
u_{k}&=g_{c}\left(x^{c}_{k},y_{k}\right),\end{aligned}\end{array}\right.$ (49)

where $x^{c}_{k}:=[\hat{z}_{k},r_{k},l_{k}]^{T}$ denotes the controller state
vector, and $f_{c}(\cdot)$ and $g_{c}(\cdot)$ are nonlinear functions that can
be defined based on (47). Therefore, controller $\mathcal{C}$ can be
considered as dynamical system $\Sigma$ in (1) that we want to immerse to
provide privacy. Accordingly, $x^{c}_{k}$, $y_{k}$, and $u_{k}$ are equivalent
to system internal variables $\zeta_{k}$, input $y_{k}$, and utility $u_{k}$
in system $\Sigma$. Hence, using the solution in Proposition 1, the encoding
maps for the controller $u_{k}$ and measurement $y_{k}$, the immersion map of
the controller state $x^{c}_{k}$, and the target dynamical controller
$\tilde{\mathcal{C}}$ can be designed as follows.
The encoding and immersion maps are given by:

$\left\\{\begin{array}[]{l}\begin{aligned}
\tilde{y}_{k}&=\Pi_{1}y_{k}+N_{1}s_{k},\\\
\tilde{x}^{c}_{k}&=\Pi_{2}x^{c}_{k},\\\
\tilde{u}_{k}&=\Pi_{3}u_{k}+\Pi_{4}\tilde{y}_{k},\end{aligned}\end{array}\right.$
(50)

the target controller is given by:

$\tilde{\mathcal{C}}=\left\\{\begin{array}[]{l}\begin{aligned}
{\tilde{x}}^{c}_{k+1}&=\tilde{f}_{c}\left({\tilde{x}}^{c}_{k},\tilde{y}_{k}\right)=\Pi_{2}f_{c}\left(\Pi_{2}^{L}{\tilde{x}}^{c}_{k},\Pi_{1}^{L}\tilde{y}_{k}\right),\\\
\tilde{u}_{k}&=\tilde{g}_{c}\left({\tilde{x}}^{c}_{k},\tilde{y}_{k}\right)\\\
&=\Pi_{3}{g}_{c}\left(\Pi_{2}^{L}{\tilde{x}}^{c}_{k},\Pi_{1}^{L}\tilde{y}_{k}\right)+\Pi_{4}\tilde{y}_{k},\end{aligned}\end{array}\right.$
(51)

and the inverse function:

$\pi_{3}^{L}\left(\tilde{u}_{k},\tilde{y}_{k}\right):=\Pi_{3}^{L}\left(\tilde{u}_{k}-\Pi_{4}\tilde{y}_{k}\right),$
(52)

with _full rank matrices_ $\Pi_{1}\in\mathbb{R}^{\tilde{n}_{y}\times n_{y}}$,
$\Pi_{2}\in\mathbb{R}^{\tilde{n}_{x_{c}}\times n_{x_{c}}}$,
$\Pi_{3}\in\mathbb{R}^{\tilde{n}_{u}\times n_{u}}$,
$\Pi_{4}\in\mathbb{R}^{\tilde{n}_{u}\times\tilde{n}_{y}}$, matrix
$N_{1}\in\mathbb{R}^{\tilde{n}_{y}\times(\tilde{n}_{y}-n_{y})}$ expanding the
kernel of $\Pi_{1}^{L}$, and a random vector
$s^{1}(t)\in\mathbb{R}^{(\tilde{n}_{y}-n_{y})}$.
The dimensions of vectors in the original controller (47) are $n_{x_{c}}=3$
and $n_{y}=n_{u}=1$. For the design of the target controller, we consider
immersed dimensions $\tilde{n}_{x_{c}}=4$ and $\tilde{n}_{y}=\tilde{n}_{u}=3$.
Also, for the design of mappings’ matrices, we randomly select small full-rank
matrices $\Pi_{1}$-$\Pi_{3}$ and a large full-rank matrix $\Pi_{4}$ based on
the designed dimensions. Then, we compute base $N_{1}$ of the kernel of
$\Pi_{1}^{L}$. The random process $s_{k}$ is defined as a multivariate Laplace
variable with a large mean and covariance.
For implementing the dynamic model of the reactor given in (45) and (46), we
consider time-varying delay $d_{k}=0.5(3+\sin(k))$, initial states
$x^{1}_{0}=-0.5$, $x^{2}_{0}=2$, and unknown parameters
$\vartheta_{1}=\vartheta_{2}=1$, $\vartheta_{3}=-1$.
First, in Fig. 4, we show the effect of the proposed coding mechanisms, where
we contrast actual and encoded measurement data. As illustrated in this
figure, when $\Pi_{1}$ is very small and $s_{k}$ is large according to (50),
the encoded measurement $\tilde{y}_{k}$ closely resembles the random
component, differing significantly from the actual measurement $y_{k}$.
Moreover, the dimension of the measurement vector $y_{k}$ expands from one to
three in the encoded form $\tilde{y}_{k}$. Therefore, adversaries can not even
access the true dimension of the measurement vector. A similar outcome is
observed when comparing the actual and encoded control actions $u_{k}$ and
$\tilde{u}_{k}$.

Figure 5: Comparison between the control action $u_{k}$ and the decoded
control action $\hat{u}_{k}$.

In Fig. 5, the original control action $u_{k}$ and the decoded control action
at the user side $\hat{u}_{k}$ are compared. As can be seen, the decoded
control action is almost identical to the original control action, and the
error (due to matrix products) between the original and decoded control
action, which is shown in Fig. 6, is negligible. Hence, we can conclude that
the proposed immersion-based coding can integrate a cryptographic method in
the networked control systems without sacrificing the performance of the
controller, and there is no need to hold a trade-off between privacy and
control performance.
Therefore, although encoded private signals $\tilde{y}_{k}$ and
$\tilde{u}_{k}$ are different from original signals $y_{k}$ and $u_{k}$, the
decoded controller at the user’s side, $\hat{u}_{k}$, is same as $u_{k}$.
Consequently, the proposed privacy-preserving networked control system shows
equivalent control performance to the standard controller.

Figure 6: The error between the control action $u_{k}$ and the decoded control
action $\hat{u}_{k}$.

Fig. 7 compares the states of the closed-loop system using the original
control action $u_{k}$, $x_{k}^{1}$ and $x_{k}^{2}$, and the states of the
closed-loop system using the decoded control action $\hat{u}_{k}$,
$\hat{x}_{k}^{1}$ and $\hat{x}_{k}^{2}$. It can be clearly observed from Fig.
7 that the states of the system with and without the immersion-based coding
are almost identical, and asymptotic stabilization has been achieved in both
cases with a good robustness against the time-varying delay.

Figure 7: Comparison between closed-loop system states using the original
control action $u_{k}$, $x_{k}^{1}$ and $x_{k}^{2}$, and closed-loop system
states using the decoded control action $\hat{u}_{k}$, $\hat{x}_{k}^{1}$ and
$\hat{x}_{k}^{2}$.

##  VII Conclusion

In this paper, we have developed a privacy-preserving framework for the
implementation of remote dynamical algorithms in the cloud. It is built on the
synergy of random coding and system immersion tools from control theory to
protect private information. We have devised a synthesis procedure to design
the dynamics of a coding scheme for privacy and a higher-dimensional system
called target algorithm such that trajectories of the standard dynamical
algorithm are immersed/embedded in its trajectories, and it operates on
randomly encoded higher-dimensional data. Random coding was formulated at the
user side as a random change of coordinates that maps original private data to
a higher-dimensional space. Such coding enforces that the target algorithm
produces an encoded higher-dimensional version of the utility of the original
algorithm that can be decoded on the user side.

The proposed immersion-based coding scheme provides the same utility as the
original algorithm (i.e., when no coding is employed to protect against data
inference), (practically) reveals no information about private data, can be
applied to large-scale algorithms, is computationally efficient, and offers
any desired level of differential privacy without degrading the algorithm
utility.

## References

  * [1] S. R. Rajagopalan, L. Sankar, S. Mohajer, and H. V. Poor, “Smart meter privacy: A utility-privacy framework,” in _Proceedings of the IEEE International Conference on Smart Grid Communications (SmartGridComm)_ , 2011, pp. 190–195.
  * [2] O. Tan, D. Gündüz, and H. V. Poor, “Increasing smart meter privacy through energy harvesting and storage devices,” _IEEE Journal on Selected Areas in Communications_ , vol. 31, pp. 1331–1341, 2013.
  * [3] Z. Huang, Y. Wang, S. Mitra, and G. E. Dullerud, “On the cost of differential privacy in distributed control systems,” in _Proceedings of the 3rd International Conference on High Confidence Networked Systems_ , 2014, pp. 105–114.
  * [4] and M. Gruteser, , and A. Alrabady, “Enhancing security and privacy in traffic-monitoring systems,” _IEEE Pervasive Computing_ , vol. 5, pp. 38–46, 2006.
  * [5] R. H. Weber, “Internet of things - new security and privacy challenges,” _Computer Law and Security Review_ , vol. 26, pp. 23–30, 2010.
  * [6] Z. Xiao and Y. Xiao, “Security and privacy in cloud computing,” _IEEE communications surveys & tutorials_, vol. 15, no. 2, pp. 843–859, 2012.
  * [7] J. L. Ny and G. J. Pappas, “Differentially private filtering,” _IEEE Transactions on Automatic Control_ , vol. 59, pp. 341–354, 2014.
  * [8] R. M. Ferrari and A. M. Teixeira, _Safety, Security and Privacy for Cyber-Physical Systems_. Springer, 2021.
  * [9] T. Tanaka, M. Skoglund, H. Sandberg, and K. H. Johansson, “Directed information as privacy measure in cloud-based control,” _arXiv preprint arXiv:1705.02802_ , 2017.
  * [10] C. Murguia, I. Shames, F. Farokhi, and D. Nešić, “On privacy of quantized sensor measurements through additive noise,” in _Proceedings of the 57th IEEE Conference on Decision and Control (CDC)_ , 2018.
  * [11] N. Wang, W. Zhou, J. Wang, Y. Guo, J. Fu, and J. Liu, “Secure and efficient similarity retrieval in cloud computing based on homomorphic encryption,” _IEEE Transactions on Information Forensics and Security_ , 2024.
  * [12] M. S. Prakash and N. Monshizadeh, “Privacy-preserving cloud computation of algebraic riccati equations,” _IEEE Control Systems Letters_ , 2024.
  * [13] F. Farokhi, _Privacy in Dynamical Systems_. Springer, 2020.
  * [14] F. Farokhi and H. Sandberg, “Optimal privacy-preserving policy using constrained additive noise to minimize the fisher information,” in _Proceedings of the IEEE 56th Annual Conference on Decision and Control (CDC)_ , 2017.
  * [15] C. Murguia, I. Shames, F. Farokhi, D. Nešić, and H. V. Poor, “On privacy of dynamical systems: An optimal probabilistic mapping approach,” _IEEE Transactions on Information Forensics and Security_ , 2021.
  * [16] H. Hayati, C. Murguia, and N. Van De Wouw, “Finite horizon privacy of stochastic dynamical systems: A synthesis framework for gaussian mechanisms,” in _2021 60th IEEE Conference on Decision and Control (CDC)_. IEEE, 2021, pp. 5607–5613.
  * [17] H. Hayati, N. van de Wouw, and C. Murguia, “Infinite horizon privacy in networked control systems: Utility/privacy tradeoffs and design tools,” in _2023 62nd IEEE Conference on Decision and Control (CDC)_ , 2023, pp. 1847–1852.
  * [18] C. Dwork, “Differential privacy: A survey of results,” in _Theory and Applications of Models of Computation_. Berlin, Heidelberg: Springer Berlin Heidelberg, 2008, pp. 1–19.
  * [19] J. Wan, A. Lopez, and M. A. A. Faruque, “Physical layer key generation: Securing wireless communication in automotive cyber-physical systems,” _ACM Transactions on Cyber-Physical Systems_ , vol. 3, no. 2, pp. 1–26, 2018.
  * [20] Y. Shoukry, K. Gatsis, A. Alanwar, G. J. Pappas, S. A. Seshia, M. Srivastava, and P. Tabuada, “Privacy-aware quadratic optimization using partially homomorphic encryption,” in _Proceedings of the IEEE 55th Conference on Decision and Control (CDC)_ , 2016, pp. 5053–5058.
  * [21] B. Joshi, B. Joshi, A. Mishra, V. Arya, A. K. Gupta, and D. Peraković, “A comparative study of privacy-preserving homomorphic encryption techniques in cloud computing,” _International Journal of Cloud Applications and Computing (IJCAC)_ , vol. 12, no. 1, pp. 1–11, 2022.
  * [22] P. Paillier, “Public-key cryptosystems based on composite degree residuosity classes,” in _International conference on the theory and applications of cryptographic techniques_. Springer, 1999, pp. 223–238.
  * [23] C. Murguia, F. Farokhi, and I. Shames, “Secure and private implementation of dynamic controllers using semihomomorphic encryption,” _IEEE Transactions on Automatic Control_ , vol. 65, no. 9, pp. 3950–3957, 2020.
  * [24] J. Kim, D. Kim, Y. Song, H. Shim, H. Sandberg, and K. H. Johansson, “Comparison of encrypted control approaches and tutorial on dynamic systems using lwe-based homomorphic encryption,” _arXiv preprint arXiv:2210.05560_ , 2022.
  * [25] A. Astolfi and R. Ortega, “Immersion and invariance: A new tool for stabilization and adaptive control of nonlinear systems,” _IEEE Transactions on Automatic control_ , vol. 48, no. 4, pp. 590–606, 2003.
  * [26] H. Hayati, C. Murguia, and N. van de Wouw, “Privacy-preserving federated learning via system immersion and random matrix encryption,” in _2022 IEEE 61st Conference on Decision and Control (CDC)_. IEEE, 2022, pp. 6776–6781.
  * [27] H. Hayati, S. Heijmans, L. Persoon, C. Murguia, and N. van de Wouw, “Mo-0304 privacy-preserving federated learning for radiotherapy applications,” _Radiotherapy and Oncology_ , vol. 182, pp. S238–S240, 2023.
  * [28] H. Hayati, N. van de Wouw, and C. Murguia, “Immersion and invariance-based coding for privacy in remote anomaly detection,” _IFAC-PapersOnLine_ , vol. 56, no. 2, pp. 11 191–11 196, 2023.
  * [29] A. Astolfi, D. Karagiannis, and R. Ortega, _Nonlinear and adaptive control with applications_. Springer, 2008, vol. 187.
  * [30] A. Isidori and C. Byrnes, “Output regulation of nonlinear systems,” _IEEE Transactions on Automatic control_ , vol. 35, no. 2, pp. 131–140, 1990.
  * [31] F. Delli Priscoli, C. Byrnes, and A. Isidori, “Output regulation of uncertain nonlinear systems,” 1997.
  * [32] M. W. Hirsch, S. Smale, and R. L. Devaney, _Differential equations, dynamical systems, and an introduction to chaos_. Academic press, 2012.
  * [33] N. Schlüter, P. Binfet, and M. S. Darup, “Cryptanalysis of random affine transformations for encrypted control,” _arXiv preprint arXiv:2304.06582_ , 2023.
  * [34] J. Upadhyay, “Random projections, graph sparsification, and differential privacy,” in _International Conference on the Theory and Application of Cryptology and Information Security_. Springer, 2013, pp. 276–295.
  * [35] C. Dwork and A. Roth, “The algorithmic foundations of differential privacy,” _Foundations and Trends in Theoretical Computer Science_ , vol. 9, pp. 211–407, 2014.
  * [36] W. Diffie and M. E. Hellman, “New directions in cryptography,” in _Secure communications and asymmetric cryptosystems_. Routledge, 2019, pp. 143–180.
  * [37] C. E. Shannon, “Communication theory of secrecy systems,” _The Bell system technical journal_ , vol. 28, no. 4, pp. 656–715, 1949.
  * [38] C. Wang and S. Ju, “Book cipher with infinite key space,” in _2008 International Symposium on Information Science and Engineering_ , vol. 1. IEEE, 2008, pp. 456–459.
  * [39] C. Dwork, F. McSherry, K. Nissim, and A. Smith, “Differential privacy—a primer for the perplexed,”,” _Joint UNECE/Eurostat work session on statistical data confidentiality_ , vol. 11, 2011.
  * [40] B. Knott, S. Venkataraman, A. Hannun, S. Sengupta, M. Ibrahim, and L. van der Maaten, “Crypten: Secure multi-party computation meets machine learning,” _Advances in Neural Information Processing Systems_ , vol. 34, pp. 4961–4973, 2021.
  * [41] Y. Aono, T. Hayashi, L. Wang, S. Moriai _et al._ , “Privacy-preserving deep learning via additively homomorphic encryption,” _IEEE Transactions on Information Forensics and Security_ , vol. 13, no. 5, pp. 1333–1345, 2017.
  * [42] K. Wei, J. Li, M. Ding, C. Ma, H. H. Yang, F. Farokhi, S. Jin, T. Q. Quek, and H. V. Poor, “Federated learning with differential privacy: Algorithms and performance analysis,” _IEEE Transactions on Information Forensics and Security_ , vol. 15, pp. 3454–3469, 2020.
  * [43] S. Ruder, “An overview of gradient descent optimization algorithms,” _arXiv preprint arXiv:1609.04747_ , 2016.
  * [44] J. Tang, C. Deng, and G.-B. Huang, “Extreme learning machine for multilayer perceptron,” _IEEE transactions on neural networks and learning systems_ , vol. 27, no. 4, pp. 809–821, 2015.
  * [45] Y. LeCun, L. Bottou, Y. Bengio, and P. Haffner, “Gradient-based learning applied to document recognition,” _Proceedings of the IEEE_ , vol. 86, no. 11, pp. 2278–2324, 1998.
  * [46] X. Jia, X. Chen, S. Xu, B. Zhang, and Z. Zhang, “Adaptive output feedback control of nonlinear time-delay systems with application to chemical reactor systems,” _IEEE Transactions on Industrial Electronics_ , vol. 64, no. 6, pp. 4792–4799, 2017.