#  Comparison of encrypted control approaches and tutorial on dynamic systems
using LWE-based homomorphic encryption

Junsoo Kim  Dongwoo Kim  Yongsoo Song  Hyungbo Shim  Henrik Sandberg  Karl H.
Johansson  Department of Electrical and Information Engineering, Seoul
National University of Science and Technology, Seoul, Korea  Western Digital
Research, Milpitas, California, USA  Department of Computer Science and
Engineering, Seoul National University, Seoul, Korea  ASRI, Department of
Electrical and Computer Engineering, Seoul National University, Seoul, Korea
School of Electrical Engineering and Computer Science and Digital Futures, KTH
Royal Institute of Technology, Stockholm, Sweden

###### Abstract

Encrypted control has been introduced to protect controller data by encryption
at the stage of computation and communication, by performing the computation
directly on encrypted data. In this article, we first review and categorize
recent relevant studies on encrypted control. Approaches based on homomorphic
encryption, multi-party computation, and secret sharing are introduced,
compared, and then discussed with respect to computational complexity,
communication load, enabled operations, security, and research directions. We
proceed to discuss a current challenge in the application of homomorphic
encryption to dynamic systems, where arithmetic operations other than integer
addition and multiplication are limited. We also introduce a homomorphic
cryptosystem called “GSW-LWE” and discuss its benefits that allow for
recursive multiplication of encrypted dynamic systems, without use of
computationally expensive bootstrapping techniques.

###### keywords:

Encrypted control, homomorphic encryption, bootstrapping, multi-party
computation, secret sharing, dynamic system over encrypted data, Learning With
Errors

##  1 Introduction

Networked control has enabled significant developments in numerous industrial
fields, while it has also led to urgent issues related to cyber-security [1,
2]. The more control systems have been connected to networks, the more
possibilities for cyber-attacks have been discovered. Given the inherent
cyber-physical nature of these systems, such attacks risk also the safe
operation of the connected physical systems. Many incidents have been reported
in recent years, including the StuxNet worm [3], false data injection to power
grids [4], and a security breach in water sewage system [5].

Studies in security of control systems are distinguished from those in fault
detection and isolation in the sense that the considered attacks are
malicious, not random faults, and may be elaborately designed to avoid
detection [6]. A negligible probability of detection of a complex fault may be
acceptable in safety studies, but in security such cases can be the point
where the attacker deceives the detector. For example, zero-dynamics attacks
[7] exploiting system models, replay attacks [8] exploiting signals, and
covert attacks [9] exploiting both models and signals, have been reported. A
common point in these attacks is that the more the attacker learns of the
target system, the more effective and theoretically undetectable attacks can
be designed. An extreme case is the covert attack presented in [9]; if an
adversary can compromise both the input and output communication using all the
information of model and signals, then it can decouple the closed-loop of the
plant and the controller, and manipulate the plant arbitrarily. This is while
the controller (with any anomaly detector) cannot distinguish whether the
received signals are compromised, or not (see Figure 1).

Figure 1: A possible scenario [9] when all the information of system model and
control signals is used for cyber-attacks.

From the motivation that data stored or being transmitted in networks may be
used for advanced attack generation, the notion of encrypted control has been
introduced [10, 11, 12, 13], which aims for security enhancement by protecting
all data in networked controllers by encryption. Conventional encryption has
been used in data transmission, as illustrated in Figure 2), but computing
devices in the network layer have been regarded as one of the most vulnerable
parts. Since cryptosystems allowing arithmetic operations was invented [14],
more developed schemes [15, 16, 17] have been applied to control as in [11,
12, 13]. The concept of “control operation over encrypted data,” as
illustrated in Figure 2, is therefore a promising direction for improving
cyber-security.

4

Figure 2: (a) Data protection by conventional encryption. (b) Configuration of
encrypted control.

Benefits of the solution in Figure 2 are that all data can be kept secure even
when computation is performed, without decryption, and the secret key for
decryption is not shared. Unauthorized parties, or possible network intruders,
cannot learn any information through eavesdropping as long as they do not have
the secret key, because encrypted signals cannot be distinguished from
uniformly generated random signals. Furthermore, a typical type of
cryptosystem used for encrypted operation, called homomorphic encryption, is
known to be more beneficial than other security mechanisms. For example,
compared to methods based on differential privacy [18, 19], it does not
sacrifice precision of the encrypted messages, regardless of the increase of
the security level. Also, many homomorphic encryption schemes are based on
discrete lattice problems, such as [20, 21], and consider a stronger
adversarial model than other schemes, such as chaotic cryptology techniques
[22, 23].

Nonetheless, the more operational abilities in recent cryptosystems are
generally accompanied by increased costs in terms of computation or
communication resource use. From an engineering point of view, application of
cryptosystems to control thus should consider the following aspects for
design.

  * 1.

Type of controller, required operations, and available resources.
Cryptosystems that allow arithmetic operations or guarantee a higher level of
security usually require more data storage for encrypted data. The
computational effort or communication overhead taken for each use of the
arithmetic function may cost much more than usual operation over un-encrypted
messages. Possibly, only one type of arithmetic function is supported, or only
a limited number of function evaluations may be allowed. Thus, the design of
encrypted control systems should consider the required type of operations and
their complexity; the available amount of computation and communication
resources; the time use for each arithmetic computation; whether the system is
static or dynamic; the available amount of data storage; and if there are
multiple units cooperating in the computation or there is only a single unit.

  * 2.

Security model (adversarial model). The design should include an adversarial
model, which determines from what attacks the system is protected. The
adversary of interest can be an unauthorized party in the network, or an
external hacker intruding the network. The adversary may aim for learning
certain information by eavesdropping the communication lines or networked
devices; or for manipulating or forging a portion of data with a certain
objective in mind. Depending on the number of units and the structure of the
design, the security objective can be to protect the data from external
parties only, or to conceal it from participating units who may be curious
about other participants’ private information.

Considering the above aspects, the designer of an encrypted control system
chooses an appropriate cryptosystem, which may be computationally fast with
only limited arithmetic support, may have much more operation abilities with
requirement of large amounts of resources, or can be suitable for centralized
or distributed computation schemes, respectively. Usually, there are trade-
offs between the cryptosystems, in terms of use of resources, level of
security, or enabled encrypted operations. Relevant research efforts try to
overcome this trade-off; by re-constructing a computation system which
exploits only a limited type of operation, by developing a novel cryptosystem
that is more appropriate for a certain application, or by proposing a protocol
that guarantees an improved level of security. In short, the efforts try to
improve the security or computational efficiency, while not losing operational
abilities.

Contribution and organization: This article provides both a general review of
the field of encrypted control and a comprehensive introduction of the
specific topic of dynamic system design based on homomorphic encryption. In
Section 2, we discuss main approaches for encrypted control, which are based
on homomorphic encryption, multi-party computation, or secret sharing,
respectively. These cryptosystems, as tools for encrypted control, are briefly
introduced, and the approaches and their application to control are compared.
Trade-offs between computation speed, operation ability, and security are also
discussed. In Section 3, we focus on the homomorphic encryption based approach
and introduce recent methods for linear dynamic systems. A tutorial on a
Learning With Errors (LWE) based homomorphic encryption scheme is first
provided, and we discuss its benefit in terms of recursive multiplication.
Then, we review a method that implements linear systems by exploiting only the
addition and multiplication abilities of cryptosystem. Finally, Section 4
concludes the paper.

Notation: Let ${\mathbb{N}}$, ${\mathbb{Z}}$, and ${\mathbb{R}}$ denote the
set of natural numbers, integers, and real numbers, respectively. The
(component-wise) floor and round functions are denoted by
$\lfloor\cdot\rfloor$ and $\lceil\cdot\rfloor$, respectively. For
$m\in{\mathbb{N}}$ and $n\in{\mathbb{N}}$, we let $0_{m\times
n}\in{\mathbb{R}}^{m\times n}$ be the zero matrix, and
$I_{n}\in{\mathbb{R}}^{n\times n}$ be the identity matrix. The set of integers
modulo $q\in{\mathbb{N}}$ is denoted by ${\mathbb{Z}}_{q}$, and the
(component-wise) modulo operation is defined by $v\mod q:=v-\lfloor v/q\rfloor
q$ for $v\in{\mathbb{Z}}^{m}$. We make use of “biased” modulo operation
defined as

$v\mod(q,v_{0}):=v-\left\lfloor\frac{v-v_{0}}{q}\right\rfloor q$ (1)

for $v\in{\mathbb{Z}}^{m}$ and $v_{0}\in{\mathbb{R}}^{m}$, so that each
component of the outcome is greater than or equal to that of $v_{0}$, and less
than that of $v_{0}+q$. We define
$\mathrm{col}\\{v_{i}\\}_{i=1}^{n}=[v_{1}^{\top},\cdots,v_{n}^{\top}]^{\top}$
for column vectors $\\{v_{i}\\}_{i=1}^{n}$ (or scalars), and the (induced)
infinity norm of a vector or a matrix is denoted as $\|\cdot\|$.

##  2 Encrypted control approaches

This section categorizes the relevant works into four categories according to
the underlying cryptographic primitives; homomorphic encryption, fully
homomorphic encryption, secret sharing, and multi-party computation, together
with a brief introduction to each primitive and approach. Then, we provide
discussions and comparisons between them.

###  2.1 Homomorphic encryption based control

We begin with a brief introduction on homomorphic encryption. Let a
cryptosystem be denoted by
$({\mathbb{Z}}_{q},{\mathcal{C}},\mathsf{Enc},\mathsf{Dec})$, where the set
${\mathbb{Z}}_{q}=\\{0,1,\ldots,q-1\\}$, $q\in{\mathbb{N}}$, is the plaintext
(un-encrypted message) space, ${\mathcal{C}}$ is the ciphertext (encrypted)
space, $\mathsf{Enc}:{\mathbb{Z}}_{q}\rightarrow{\mathcal{C}}$ and
$\mathsf{Dec}:{\mathcal{C}}\rightarrow{\mathbb{Z}}_{q}$ are the encryption and
decryption algorithms, respectively. We omit the argument of encryption and
decryption keys, for simplicity.

Homomorphic properties of cryptosystems imply that the encryption and
decryption algorithms are “homomorphisms,” which preserve algebraic structure
with respect to a certain arithmetic function. Let us assume that the
cryptosystem $({\mathbb{Z}}_{q},{\mathcal{C}},\mathsf{Enc},\mathsf{Dec})$ is
additively homomorphic, which means that the algorithms $\mathsf{Enc}$ and
$\mathsf{Dec}$ are homomorphic with respect to the addition operation; there
exists a binary function
$\ast:{\mathcal{C}}\times{\mathcal{C}}\rightarrow{\mathcal{C}}$ over
ciphertexts such that

$\mathsf{Dec}(\mathbf{c}_{1}\ast\mathbf{c}_{2})=\mathsf{Dec}(\mathbf{c}_{1})+\mathsf{Dec}(\mathbf{c}_{2})\mod
q,\qquad\forall\mathbf{c}_{1}\in{\mathcal{C}},~{}\forall\mathbf{c}_{2}\in{\mathcal{C}},$

which implies that

$\mathbf{c}=\mathsf{Enc}(x_{1})\ast\mathsf{Enc}(x_{2})\quad\implies\quad\mathsf{Dec}(\mathbf{c})=x_{1}+x_{2}\mod
q,\quad\forall x_{1}\in{\mathbb{Z}}_{q},~{}\forall x_{2}\in{\mathbb{Z}}_{q}.$
(2)

It means that whenever we decrypt the outcome of the operation $\ast$ over
ciphertexts, we obtain the same addition outcome over plaintexts, so it
enables to perform the addition directly over encrypted messages, without
decryption.

The ability of addition is a basic property, but by exploiting it,
multiplication by (un-encrypted) constant numbers can also be performed. Given
a natural number $k\in{\mathbb{N}}$, we define

$k\cdot\mathbf{c}:=\smash[b]{\overbrace{\mathbf{c}\ast\cdots\ast\mathbf{c}}^{\text{$k$
times}}}.$

And, we extend the definition for an integer $k\in{\mathbb{Z}}$, by

$k\cdot\mathbf{c}:=(k\\!\\!\\!\mod(q,1))\cdot\mathbf{c},$

where the operation $\mathrm{mod}(q,1)$ defined from (1) ensures that
$k~{}\mathrm{mod}(q,1)\geq 1$. Then, it follows that

$\displaystyle\begin{split}\mathsf{Dec}(k\cdot\mathbf{c})&=(k\\!\\!\\!\mod(q,1))\cdot\mathsf{Dec}(\mathbf{c})\mod
q\\\ &=k\cdot\mathsf{Dec}(\mathbf{c})\mod q\end{split}$

holds for all $k\in{\mathbb{Z}}$ and $\mathbf{c}\in{\mathcal{C}}$, because
$k~{}\mathrm{mod}(q,1)=k+dq$ with some $d\in{\mathbb{Z}}$.

It enables multiplication by integer matrices as well; for an integer matrix
$K=[k_{ij}]\in{\mathbb{Z}}^{m\times n}$ and a set
$\mathbf{x}=\\{\mathsf{Enc}(x_{i})\\}_{i=1}^{n}$ of encrypted messages of
$x_{i}\in{\mathbb{Z}}_{q}$, $i=1,\ldots,n$, we define

$K\cdot\mathbf{x}=\begin{bmatrix}k_{11}&k_{12}&\cdots&k_{1n}\\\
k_{21}&k_{22}&\cdots&k_{2n}\\\ \vdots&\vdots&\ddots&\vdots\\\
k_{m1}&k_{m2}&\cdots&k_{mn}\end{bmatrix}\cdot\begin{bmatrix}\mathsf{Enc}(x_{1})\\\
\mathsf{Enc}(x_{2})\\\ \vdots\\\
\mathsf{Enc}(x_{n})\end{bmatrix}:=\begin{bmatrix}(k_{11}\cdot\mathsf{Enc}(x_{1}))\ast(k_{12}\cdot\mathsf{Enc}(x_{2}))\ast\cdots\ast(k_{1n}\cdot\mathsf{Enc}(x_{n}))\\\
(k_{21}\cdot\mathsf{Enc}(x_{1}))\ast(k_{22}\cdot\mathsf{Enc}(x_{2}))\ast\cdots\ast(k_{2n}\cdot\mathsf{Enc}(x_{n}))\\\
\vdots\\\
(k_{m1}\cdot\mathsf{Enc}(x_{1}))\ast(k_{m2}\cdot\mathsf{Enc}(x_{2}))\ast\cdots\ast(k_{mn}\cdot\mathsf{Enc}(x_{n}))\end{bmatrix},$
(3)

which is simply a component-wise constant multiplication and consecutive
additions over encrypted data. Then, it can also be easily verified that
$\mathsf{Dec}(K\cdot\mathbf{x})=K\cdot[x_{1},x_{2},\ldots,x_{n}]^{\top}\mod
q$, for all $K\in{\mathbb{Z}}^{m\times n}$ and $x\in{\mathbb{Z}}_{q}^{n}$.

Thanks to the property of allowing computation over ciphertexts without the
secret key nor decryption, the computation can be assigned to an operation
unit who is honest to do the computation correctly while being curious about
the transmitted data, or to a networked unit which can be possibly accessed by
unauthorized third parties. In addition to the described homomorphic
properties, there are also encryption schemes [17, 24, 25, 26, 27, 28] which
enable to compute both the addition and a limited number of multiplication on
encrypted data. Those schemes are sometimes called somewhat or leveled
homomorphic encryption to be distinguished from (partially) homomorphic
encryptions allowing addition only, but we denote both of them, simply, as
homomorphic encryption.

The application of homomorphic encryption for control has been introduced in
[11, 12, 13]. Since homomorphic cryptosystems support addition and/or
multiplication, most controllers based on homomorphic encryption considers
linear operation (matrix multiplication) or polynomial functions (represented
with small number of additions and multiplications) only; see Figure 3 for an
example case of linear controllers based on homomorphic encryption. It has
also been used for implementing model predictive control [29], data-driven
control [30], and reinforcement learning based control [31], where the
computation circuits are represented with linear functions or low degree
polynomials.

4

Figure 3:  (a) Homomorphic encryption based controllers for static feedback.
(b) Dynamic encrypted controller implementation using additional transmission
lines for the state.

Operation unit and attack model: The model of the controller is usually
considered as a single operation unit who performs the computation over
encrypted data without accessing the secret key. It is often specified as a
networked controller under possible eavesdropping attack (which tries to learn
private control data) or considered as a cloud-based controller performing the
computation on behalf of the controller designer, which should not learn any
private information through the computation. In short, adversaries of
homomorphic encryption based controllers can be both external eavesdroppers
and the controller itself, and cryptosystem parameters are determined for a
desirable level of security.

Challenges: A main issue is that encrypted implementation may be limited to
only addition or multiplication over integers. Even for homomorphic encryption
allowing both addition and multiplication, many of them allow evaluating a
limited number of multiplications only. As a consequence, implementation of
dynamic systems that iteratively compute and update the state has been
considered as a challenge, and representing diverse nonlinear systems using
only addition and multiplication is currently an open problem.

Even for linear systems, dynamic systems implemented over encrypted data may
be incapable of operating for an infinite time horizon. This is because, based
on homomorphic encryption only, multiplication by non-integer numbers can be
performed only a finite number of times, so that the dynamic operation that
multiplies the state by non-integer numbers cannot be continued for an
infinite time horizon (see the example described in (32)). Figure 3 describes
a method for dynamic controllers considered in initial studies, which uses
additional transmission lines for the state; assuming that the encrypted state
of the controller can be transmitted to the device having the decryption key,
the state can be decrypted and re-encrypted and transmitted back to the
controller. However, the limitation is that the system cannot continue the
operation without the presence of the decryption key, and the re-encryption
requires additional use of communication lines which may be proportional to
the dimension of the signal. Further discussions and related methods can be
found in Section 3.2.

###  2.2 Fully homomorphic encryption based methods

As introduced, homomorphic encryption supporting a finite number of operations
has limitations on its applicability. The first fully homomorphic encryption,
with which one can perform arbitrary computation without limitation, has been
presented in [32]. Then, the main concern has been reducing the computational
cost, and follow-up works have been proposed toward their practical use [17,
27, 28, 33, 34], with several library implementations. The crucial improvement
from the previous homomorphic encryption (with limitations) is the
introduction of “bootstrapping” procedure111Conceptually, it can be understood
as an encrypted evaluation of the decryption operation on the ciphertext,
resulting in a new ciphertext having the same message. [33, 35] which
refreshes (without a secret key) a ciphertext into a new one with which one
can continue the computation. Many encryption schemes referred to in the
previous section can be fully homomorphic, by adding the bootstrapping
procedure.

Figure 4:  Multiple encrypted linear controllers with switching function.

Thanks to the bootstrapping, any operation circuits in digital computers can
be implemented and run over encrypted data for an infinite time horizon, since
any logical functions with Boolean variables can be represented using addition
and multiplication. Nonetheless, the computational complexity of bootstrapping
has been a critical issue, and its requirement on the computation resource
currently hinders it from being used in practice.

The bootstrapping was first used for linear dynamic systems in [12]. The
latency time for bootstrapping may be larger than the sampling period, but as
described in Figure 4, multiple identical controllers are designed and the
time for bootstrapping is scheduled in a different way, so that the same
output can be generated all the time even when some of them are performing
bootstrapping. Many homomorphic encryption based works [30, 31, 36, 37]
mentioned in the previous section also claim that introduction of
bootstrapping enables the encrypted systems to update the state without
interacting with an entity holding the secret key.

Operation unit and attack model: Since fully homomorphic encryption is simply
a homomorphic encryption with further evaluation capabilities, the operation
model considered is the same as the case of homomorphic encryption without use
of bootstrapping. It also considers a single operation unit who should not
learn any information from the computation, while all the control data are
kept encrypted so that it is protected from external parties as well. A
difference in practice is that it should be able to use a large amount of
computational or memory resources, for bootstrapping.

Challenges: Main challenge of fully homomorphic encryptions is to reduce the
computational cost for bootstrapping. A couple of issues regarding control
operation can be listed; first, operations consisting of addition,
multiplication, and bootstrapping, may not be efficient for non-polynomial
functions, such as, comparison, if-else conditionals, or transcendental
functions, for which lots of arithmetic operations may be required for the
representation and result in impractical evaluation cost. A countermeasure
would be to represent the given operation circuit to an “arithmetic-friendly
form,” so that the evaluation cost can be reduced. And, since bootstrapping
constitutes a major cost in fully homomorphic encryption based schemes while
it has been essentially used, a momentous challenge will be to reduce the
number of uses of bootstrapping.

###  2.3 Secret sharing based schemes

Now, we describe another computation protocol based on secret sharing, where
private data are distributed in the form of “shares” to two or more parties so
that an individual party cannot get any information about the data. Still,
each party can perform appropriate computation on its share and generate the
outcome from which the owner of the data can reconstruct the computation
outcome; in other words, there is a homomorphic property on the shares, so
that the computation of control signals can be offloaded to outsourced
operation units, without disclosing any information on the input and output.

The most basic secret sharing with two computing parties, supporting
additions, is described as follows. Let $m\in{\mathbb{Z}}_{q}$ be a message
that should be kept securely. A share for the first party is generated as
$c_{1}:=m+r\bmod q$, where $r\in{\mathbb{Z}}_{q}$ is a random number sampled
from the uniform distribution over the set ${\mathbb{Z}}_{q}$. And, the share
for the other party is given by $c_{2}:=-r\bmod q$, so that
$m=c_{1}+c_{2}\bmod q$. By doing so, the distribution of each share on each
party follows the uniform distribution over the set ${\mathbb{Z}}_{q}$, which
means that referring to only one share does not give any information about the
message $m$. We note that a new random number must be sampled whenever a
message is split to shares. See Figure 5 for an example with
${\mathbb{Z}}_{q}={\mathbb{Z}}_{5}=\\{0,1,2,3,4\\}$ and $m=3$.

Figure 5:  A basic example of secret sharing.

The method itself is quite simple, but this scheme as a cryptosystem is
homomorphic with respect to addition and integer multiplication; let two
messages $m\in{\mathbb{Z}}_{q}$ and $m^{\prime}\in{\mathbb{Z}}_{q}$ be split
into two shares, as $m=c_{1}+c_{2}\\!\\!\mod q$ and
$m^{\prime}=c_{1}^{\prime}+c_{2}^{\prime}\\!\\!\mod q$, respectively. And, let
the first shares $c_{1}\in{\mathbb{Z}}_{q}$ and
$c_{1}^{\prime}\in{\mathbb{Z}}_{q}$ be kept by the first operation unit and
let the other shares $c_{1}^{\prime}\in{\mathbb{Z}}_{q}$ and
$c_{2}^{\prime}\in{\mathbb{Z}}_{q}$ be kept by the second operation unit.
Then, the addition operation ($m+m^{\prime}\\!\\!\mod q$) can be performed by
the operation units in parallel, as

$\displaystyle\text{Operation unit 1}:\qquad c_{1}^{\sf add}$
$\displaystyle=c_{1}+c_{1}^{\prime}\mod q$ $\displaystyle\text{Operation unit
2}:\qquad c_{2}^{\sf add}$ $\displaystyle=c_{2}+c_{2}^{\prime}\mod q$

where the operation units cannot learn any information of $m$, $m^{\prime}$,
or $m+m^{\prime}\\!\\!\mod q$. When the outcomes $c_{1}^{\sf add}$ and
$c_{2}^{\sf add}$ as shares are collected from both the units, then the
plaintext outcome can be restored, because $(m+m^{\prime}\\!\\!\mod
q)=(c_{1}^{\sf add}+c_{2}^{\sf add}\\!\\!\mod q)$. And, for a vector
$\vec{m}\in{\mathbb{Z}}_{q}^{n}$ of $n$-messages split as
$\vec{m}=\vec{c}_{1}+\vec{c}_{2}~{}\mathrm{mod}\,q$ by generating $n$-random
numbers in ${\mathbb{Z}}_{q}$, multiplication by (un-encrypted) integer
matrices can also be done by the operation units in parallel; for a matrix
$K\in{\mathbb{Z}}^{m\times n}$, let the operation units compute

$\displaystyle\text{Operation unit 1}:\qquad c_{1}^{\sf mult}$
$\displaystyle=K\cdot\vec{c}_{1}\mod q$ $\displaystyle\text{Operation unit
2}:\qquad c_{2}^{\sf mult}$ $\displaystyle=K\cdot\vec{c}_{2}\mod q.$

Then, it is easy to check that $(K\cdot\vec{m}\\!\\!\mod q)=(c_{1}^{\sf
mult}+c_{2}^{\sf mult}\\!\\!\mod q)$. For general schemes, one may refer to
Shamir’s secret sharing [38], and many extended results and methods can be
found in literature [39, 40, 41].

Figure 6:  Configuration of encrypted controller based on secret sharing with
two operation units.

We have seen that secret sharing enables offloading linear operations without
disclosing information, given that the computing parties do not collude with
others. Contrary to homomorphic encryptions demanding a relatively large
amount of storage and computational resources on the operation device, secret
sharing based methods can be a good alternative for applications where
computational resources are limited but multiple operation units are
available. For example, it is proposed in [42] that the use of secret sharing
for encrypted control can reduce the time consumption significantly, per each
unit of operation (compared to homomorphic encryption). Figure 6 describes a
linear controller based on secret sharing; the sensor measurement $y(t)$ is
distributed, as shares $y_{1}(t)$ and $y_{2}(t)$, to two controllers, and each
controller performs the linear operation and sends the outcome to the
actuator, respectively.

4

Figure 7: (a) Conventional distributed protocol. (b) Distributed protocol
based on secret sharing.

Secret sharing has also been employed for dealing with privacy problems in
distributed computation protocols, where multiple participants collaboratively
evaluate a common function of interest. For example, average consensus can be
considered as in Figure 7, where the participants compute the average of the
individual values by communicating with their neighbors. In terms of privacy,
the goal is to perform the computation while each individual value is not
disclosed to other parties. Methods based on differential privacy have been
frequently employed as in [43, 44], where a trade-off between privacy and
performance is inevitable, depending on the size of injected noises. Then, the
secret sharing has been introduced for distributed systems; for example,
Figure 7 describes a method proposed in [45] for privacy-preserving average
consensus. By splitting each individual value to two shares, transmitting only
one of them to the neighbors directly, and reflecting the other share to the
protocol “indirectly,” the distributed protocol can yield the same outcome
without sacrificing the privacy of each individual value. An advantage
compared to differential privacy is that there is no performance penalty for
keeping the data private.

Operation unit and attack model: Secret sharing based control systems
introduce multiple operation units which perform the computation on the
distributed shares in parallel, and thus they consider an adversarial model
compromising some portion of the units. Specifically, “$(t,N)$-threshold
scheme” denotes that an adversary needs to get $t$-shares out of the
$N$-shares (distributed to the units) to recover the message. For instance,
the example described in Figure 5 can be seen as (2,2)-threshold secret
sharing.

Challenges: Whereas secret sharing allows for efficient computation between
the shares of messages, the issue of possible collusion between the units that
reveals the value of the message is a main issue in this framework.
Furthermore, additional potential risk in practice would be that, if there is
an external party (not participating in the computation) who succeeds in
collecting the operation units’ information, then the private data can also be
exposed. Another challenge is that, analogous to methods solely based on
homomorphic encryption, general nonlinear functions over secret shares may be
hard to implement and currently they are limited. There is a trade-off between
further operation abilities on the shares and sacrifice of the security, so
that it can be studied and improved in the future; to perform operations other
than addition, interactions between the computing units or relaxation of the
security model is required. For example, in [46], computation of polynomials
of degree $N$ results in a $(2,N)$-threshold secret sharing, where the private
message is revealed if any two of the shares are collected.

There are several works exploiting secret sharing to enhance the privacy of
control systems, where many of them also employ homomorphic encryption or
other cryptographic schemes, together with use of communication between the
operation units. We refer to them as “multi-party computation” based schemes,
which will be discussed in the next subsection. In general, secret sharing is
often regarded as a sort of multi-party computation scheme, as it also
utilizes multiple parties for the computation. Nonetheless, for the sake of
detailed comparison and discussion in Section 2.5, we distinguish the secret
sharing algorithms from the multi-party computation; secret sharing desirably
does not utilize communication between the parties during the computation,
whereas for the multi-party computation, the parties essentially communicate
with other parties and collaborate for each unit of computation.

###  2.4 Multi-party computation based control

Finally, we introduce approaches based on multi-party computation. The
terminology multi-party computation is usually used broadly and often includes
the homomorphic encryption and secret sharing based methods discussed in the
previous subsections. Nonetheless, by “multi-party computation,” throughout
the article, we mean a narrower framework employing homomorphic encryption,
secret sharing, and/or other cryptographic primitives, where the parties
cooperate for each unit of computation, by several interactions and
communications between them.

4

Figure 8: (a) Configuration of two-party computation. (b) Encrypted
multiplication based on two-party computation.

The scheme is to let multiple participants collaboratively evaluate a
function, where the inputs are given from the participants, but the privacy of
each input should be kept. That is, each participant’s input should be used
for the joint computation, but it should not be learned by any other
participant.222The goal can be defined formally with a simulation paradigm
which comprises broader security guarantees such as detecting malicious
behaviors with data privacy (we refer to [47]). In this article, we rather
focus on the data privacy aspects. See Figure 8 describing a configuration of
two-party computation as a basic case; the two units jointly compute the value
of $f(a,b)$ while the arguments $a$ and $b$ are not informed by the other
unit.

Figure 8 shows a basic example of encrypted multiplication by two-party
computation. Let Unit 2 have two encrypted numbers, Unit 1 have the decryption
key, and let the encryption $\mathsf{Enc}$ be additively homomorphic but not
multiplicatively homomorphic. That is, Unit 2 can perform encrypted addition
using the function $\ast$ as in (2), but it cannot do the multiplication for
the two encrypted messages $\mathsf{Enc}(x_{1})$ and $\mathsf{Enc}(x_{2})$
directly, by itself. Then, the objective is to let Unit 2 obtain the
multiplication outcome of two messages as encrypted, with help of Unit 1,
while Unit 1 should not learn the values of $x_{1}$ and $x_{2}$, and Unit 2
should not obtain Unit 1’s decryption key.

Figure 9:  A basic method for two-party encrypted multiplication.

Then, Figure 9 shows how the two-party computation for encrypted
multiplication is performed. Essentially, Unit 2 will send the two messages to
Unit 1, and Unit 1 will do the multiplication after decrypting the received
ciphertexts. Unit 1 should not know the message values, so Unit 2 generates
two random numbers $r_{1}$ and $r_{2}$ and add to $\mathbf{x}_{1}$ and
$\mathbf{x}_{2}$ using the additively homomorphic property, and then transmit
the “masked” messages. Then, even though Unit 1 decrypts the messages, it
cannot learn anything from the values $(x_{1}+r_{1}\\!\\!\mod q)$ and
$(x_{2}+r_{2}\\!\\!\mod q)$. Nevertheless, now Unit 1 can multiply the
decrypted messages, encrypt the outcome again, and send it back to Unit 2.
Finally, the transmitted ciphertext $\mathbf{z}$ contains the message as
$(x_{1}+r_{1})(x_{2}+r_{2})\\!\\!\mod q$, and since Unit 2 has the information
of $r_{1}$, $r_{2}$, $\mathsf{Enc}(x_{1})$, and $\mathsf{Enc}(x_{2})$, it can
cancel out the terms $r_{1}x_{2}$, $r_{2}x_{1}$, and $r_{1}r_{2}$, over
encrypted data. As a consequence, Unit 2 obtains the outcome whose decryption
is equal to $x_{1}\times x_{2}\\!\\!\mod q$. It is also clear that Unit 2 does
not learn any additional information because it only computes over encrypted
messages during the process.

We have seen that two-party computation enables encrypted multiplication,
despite that the ability of multiplication is not given from the homomorphic
cryptosystem. In general, a main advantage of multi-party computation is that
it can allow various functions other than addition and multiplication while
exploiting additively homomorphic encryption only, by use of multiple parties
and communication between them. Many results have contributed for enabling
various functions [48, 49, 50, 51, 52], such as division by integers,
inversion of encrypted matrices, and comparison or maximum operations. It is
also notable that usually multi-party computation does not make use of
bootstrapping of fully homomorphic encryption so that the required amount of
computational resources is not exhaustively large, but it rather exploits
communication resources several times for each unit of arithmetic function.

Meanwhile, similarly to the framework of secret sharing, a crucial assumption
on multi-party computation is that the parties do not collude with each other.
For example, supposing that Units 1 and 2 in the algorithm in Fig. 9 are
“outsourced computers” performing the encrypted computation on client’s
private data $x_{1}$ and $x_{2}$, the information will be exposed once the
units collude and Unit 1 decrypts Unit 2’s encrypted data.

A basic configuration of the two-party computation based control scheme is
described in Figure 10. It considers two collaborative operation units
consisting of an “encrypted controller” who stores encrypted control data and
performs arithmetic supported from the employed homomorphic encryption, and a
“computation assistant” who helps advanced operations that cannot be done with
the homomorphic property of cryptosystem solely, by use of two-party
computation techniques. In case the computation assistant is supposed to have
the decryption key of the cryptosystem, the actuator can take the role,
assuming that the communication between the actuator and the encrypted
controller can be bi-directional (for this case, the structure of system
becomes similar with that of Figure 3, where additional communication is used
for “re-encrypting” the state).

Figure 10:  Configuration of encrypted controller based on two-party
computation.

Multi-party computation based control employs multiple operation units, which
are often regarded as “out-sourced” computers, who performs the computation on
behalf of the controller designer. Thanks to its utility enabling further
advanced arithmetic functions, it has been applied to nonlinear controllers
which need more than addition and multiplication for operating. For example,
it has been used for encrypted implementations of “implicit” model predictive
controllers where projection operation is needed for constrained optimizations
[53, 54], or extended Kalman filters where matrix inversions and comparison
operations are required [55].

Attack model: Since more than one parties are involved, the adversarial model
for multi-party computation framework is similar to that of secret sharing. It
can be described similarly according to the number of parties that the
adversary is required to compromise to recover the underlying messages.
Usually, the security model also considers the behavior that the adversary can
carry on; “honest-but-curious” model assumes that the adversary follows the
protocol correctly (but tries to infer useful information from the
observation) whereas “malicious” model assumes that the adversary may not
follow the protocol correctly and perform an arbitrary behavior (for this
case, the protocol aims to enable other participants to detect such
behaviors).

Challenges: Compared to fully homomorphic encryption (which achieves a similar
functionality), multi-party computation methods in general require much less
computational resources but exploit more communication costs for each unit of
arithmetic functions. Interestingly, similarly to (fully) homomorphic
encryption, evaluating non-arithmetic functions such as division,
transcendental functions, and conditional expressions may require much more
communications (and computations) than arithmetic functions. While there are
many specialized multi-party protocols for evaluating a unit of function, it
often requires combining them together to design an encrypted system. We also
remark that constructing a system based on multi-party computation protocol
usually involves more complex security analysis and proofs, even in the same
honest-but curious model, than that based on (fully) homomorphic encryption,
due to the presence of multiple parties and interactions between them where
the adversary tries to compromise.

###  2.5 Discussion and comparison

Finally, Table 1 puts all the discussed approaches and their features
together, and compares them with each other, where general trade-offs between
the encrypted control approaches are found. To this end, for simplicity, let
us abbreviate homomorphic encryption as “HE,” fully homomorphic encryption as
“FHE,” and secret sharing as “SS,” in this subsection. Multi-party computation
protocols, utilizing homomorphic encryption, are particularly denoted by “MPC-
HE,” so that they are distinguished from secret sharing.

Table 1: Trade-offs between cryptographic tools (compared to HE). | $\begin{matrix}\textsf{HE}\end{matrix}$ | $\begin{matrix}\textsf{FHE}\end{matrix}$ | SS | MPC-HE
---|---|---|---|---
feature | - | computation-intensive | $\begin{matrix}\textsf{\color[rgb]{0,0.5,0}operation without}\\\ \textsf{\color[rgb]{0,0.5,0}homomorphic encryption}\end{matrix}$ | communication-intensive
operation unit | single | single | multiple | multiple
strengths | - | $\begin{matrix}\textsf{\color[rgb]{0,0.5,0}no limitation}\\\ \textsf{\color[rgb]{0,0.5,0}on operations}\end{matrix}$ | computationally efficient | $\begin{matrix}\textsf{\color[rgb]{0,0.5,0}advanced operations}\\\ \textsf{\color[rgb]{0,0.5,0}without bootstrapping}\end{matrix}$
weaknesses | $\begin{matrix}\textsf{limitation on}\\\ \textsf{operations}\end{matrix}$ | $\begin{matrix}\textsf{\color[rgb]{1,0,0}high computational}\\\ \textsf{\color[rgb]{1,0,0}complexity}\end{matrix}$ | $\begin{matrix}\textsf{limitation on operations,}\\\ \textsf{\color[rgb]{1,.5,0}collusion issues}\end{matrix}$ | $\begin{matrix}\textsf{\color[rgb]{1,0,0}communication delay,}\\\ \textsf{\color[rgb]{1,.5,0}collusion issues}\end{matrix}$

One natural observation is that “the more resources are utilized, then the
more operation abilities (over encrypted data) the scheme obtains”. Comparing
HE and FHE, it can be seen that FHE utilizes much more computational
resources, but it guarantees that any sort of operation circuit can be
implemented. Comparing HE and MPC-HE, on the other hand, it can be understood
that additional use of communication resources for MPC-HE schemes mitigates
the limited operation issue of HE; e.g., the ability of HE is limited to
addition and multiplication over integers, but MPC-HE can implement many more
advanced functions.

Another aspect in comparison is that “use of multiple operation units” brings
improvement of computational efficiency, but it also brings possible security
issues together. Comparing HE and MPC-HE again, MPC-HE takes advantage of
multiple parties so that it obtains more operation abilities, and comparing HE
and SS, SS also introduces multiple operation units so that it improves
computational efficiency in the sense that it keeps the ability of linear
operation still amenable, despite that it does not use homomorphic encryption.
However, a main opportunity cost for utilizing multiple operation units is
possible security issues; it should be guaranteed that the participating units
never collude with the others, and it might also be vulnerable to
eavesdropping from external adversaries.

Figure 11: Comparison of encrypted control approaches and future research
directions.

A similar observation can be made in a different way. Let Figure 11 compare
the four approaches, in terms of speed (operation amount per unit of time),
ability (enabled operations over encrypted data), and security (mainly
considers issues of collusion and external eavesdropping). In terms of
“speed,” SS may be a good option if the system can be implemented using
multiple computers. Regarding “ability,” if the encrypted controller design
includes complicated nonlinear functions, either FHE based method or MPC-HE
based protocol can be considered, with intensive use of computational or
communication resources, respectively. And, for applications in which use of
multiple operation units is not allowed because of security matters, use of HE
or FHE would be appropriate. In short, each encrypted control application
should consider its required sort of operations, available resources, and
appropriate security model, for choosing its approach.

Lastly, Figure 11 also considers future research directions for the
approaches, which would be to deal with and improve on their respective
weaknesses. HE based schemes would aim for overcoming the constraint of
limited operation, and proposing practical bootstrapping techniques would be
of main interest for FHE based methods. For the sake of control application,
SS and MPC-HE based schemes should resolve possible security issues due to
collusion or external eavesdropping. At the same time, developing nonlinear
functions using SS and reducing the communication overhead with MPC-HE would
be of challenges, respectively.

##  3 Introduction to linear dynamic systems using LWE-based homomorphic
encryption

So far we have discussed broad approaches on encrypted control and current
challenges. To handle those issues, new problems that have not been considered
in the control community are often formulated. In this section, let us be more
focused on the approach based on homomorphic encryption only, and introduce a
specific problem and current solutions, on implementation of dynamic systems
over encrypted data.

Implementing an encrypted controller is to convert a “given” controller over
plaintext (described in Figure 2) to a system over ciphertext (as Figure 2).
Let a linear dynamic controller has been designed and given as

$\displaystyle\begin{split}x(t+1)&=Fx(t)+Gy(t)\\\ u(t)&=Hx(t)+Jy(t)\\\
x(0)&=x_{0}\end{split}$ (4)

where $x(t)\in{\mathbb{R}}^{\ell}$ is the state,
$y(t)\in{\mathbb{R}}^{\mathsf{p}}$ is the sensor measurement transmitted from
the plant (input of the controller), $u(t)\in{\mathbb{R}}^{\mathsf{m}}$ is the
actuation input fed back to the plant (output of the controller), and the
matrices $\\{F,G,H,J\\}$ and the initial state $x_{0}\in{\mathbb{R}}^{\ell}$
are given as controller parameters. Throughout the paper, we assume that the
trajectories of the signals $\\{x(t),y(t),u(t)\\}_{t=0}^{\infty}$ are bounded.

Then, the implementation of the controller (4) over encrypted data can be
divided into two steps.

  1. 1.

Conversion of given controller to operate over integers. As discussed in
Section 2.1, most homomorphic cryptosystems allow no more than addition and
multiplication over encrypted integers, unless bootstrapping (of fully
homomorphic encryption) is used. Thus, the given system (4) with the
parameters $\\{F,G,H,J,x_{0}\\}$, which are generally non-integers, should be
converted to operate over integers using addition and multiplication only. The
input-output relation (performance) of the re-constructed controller should be
equivalent to the given controller.

  2. 2.

Choice of homomorphic cryptosystem and application to dynamic operation. The
employed cryptosystem should be appropriate to the dynamic operation of the
controller. If the implemented controller is to perform recursive
multiplication by an encrypted parameter for each time iteration (just as in
(4)), the cryptosystem should be homomorphic with respect to such recursive
operation. To that end, it can be expected that the encryption should be
homomorphic with respect to both addition and multiplication, and it should
allow recursive multiplication as encrypted, for an unlimited number of times.

Let us begin with the second issue in the next subsection. We introduce a
Learning With Errors (LWE) based encryption called “GSW-LWE” proposed in [34],
which can be understood as a combination of “Gentry-Sahai-Waters (GSW)”
encryption scheme [56] and a basic LWE-based encryption [57]. Detailed
explanations on the encryption scheme and algorithms will be followed by a
discussion on its benefits to dynamic operation.

###  3.1 An LWE-based cryptosystem for encrypted recursive multiplication

We first introduce a basic version of LWE-based cryptosystem.

####  3.1.1 Encryption method, security, and additively homomorphic property
[20, 57]

Let the set ${\mathbb{Z}}_{q}=\\{0,1,\ldots,q-1\\}$, $q\in{\mathbb{N}}$, be
the space of messages for encryption. We have seen in Section 2.3 and Figure 5
that “adding a random number $r\in{\mathbb{Z}}_{q}$ and taking modulo
operation by $q$” is an easy way to conceal a message $m\in{\mathbb{Z}}_{q}$.
Though it is quite simple, it may be impractical in the sense that the
information of the number $r\in{\mathbb{Z}}_{q}$ is required for restoring the
message, which is newly sampled whenever a message is encrypted.

To be a cryptosystem using the same “key” for each encryption, LWE based
schemes generate “random-like” numbers from a fixed portion of data, called an
encryption key; let a row vector
$\mathsf{sk}=[\mathsf{sk}_{1},\mathsf{sk}_{2},\ldots,\mathsf{sk}_{n}]\in{\mathbb{Z}}^{n}$,
$n\in{\mathbb{N}}$, be chosen, which we will call the encryption key or the
secret key. Then, the idea of LWE-based schemes is that the number
$c\in{\mathbb{Z}}_{q}$, generated as

$\displaystyle\begin{split}c&=\begin{bmatrix}\mathsf{sk}_{1}&\mathsf{sk}_{2}&\cdots&\mathsf{sk}_{n}\end{bmatrix}\cdot\begin{bmatrix}a_{1}\\\
a_{2}\\\ \vdots\\\ a_{n}\end{bmatrix}+e\mod q\\\ &=\mathsf{sk}\cdot a+e\mod
q,\end{split}$ (5)

looks “almost uniformly random” in the space ${\mathbb{Z}}_{q}$, where the
components of $a=[a_{1},a_{2},\ldots,a_{n}]^{\top}$ are random numbers in
${\mathbb{Z}}_{q}$ (i.e., sampled from the uniform distribution over
${\mathbb{Z}}_{q}$), and $e\in{\mathbb{Z}}$ is a “small error” sampled from
$N(0,\sigma)$, which denotes the zero-mean discrete Gaussian distribution with
standard deviation $\sigma>0$.

The claim that the method (5) generates “almost random” numbers is in fact
exactly what the Learning With Errors (LWE) problem considers. Let a
“sufficient” amount of samples $\\{c_{i}\\}_{i=1}^{N}$ in ${\mathbb{Z}}_{q}$
be generated using the key $\mathsf{sk}\in{\mathbb{Z}}^{n}$, as

$\displaystyle\begin{split}c_{1}&=\mathsf{sk}\cdot\vec{a}_{1}+e_{1}\mod q\\\
c_{2}&=\mathsf{sk}\cdot\vec{a}_{2}+e_{2}\mod q\\\ &~{}\vdots\\\
c_{N}&=\mathsf{sk}\cdot\vec{a}_{N}+e_{N}\mod q,\end{split}$ (6)

where the components of $a_{i}\in{\mathbb{Z}}_{q}^{n}$ are uniformly sampled
from ${\mathbb{Z}}_{q}$ and $e_{i}\in{\mathbb{Z}}$ is sampled from the
distribution $N(0,\sigma)$, for each $i=1,\ldots N$. Then, given the
information of $\\{c_{i}\\}_{i=1}^{N}$ and $\\{\vec{a}_{i}\\}_{i=1}^{N}$, the
LWE problem is to find out if the data $\\{c_{i}\\}_{i=1}^{N}$ are generated
through the process (6), or are just uniformly generated random numbers. If
this problem is hard to solve, it implies that the information of the secret
key $\mathsf{sk}$ is “secure” from unauthorized parties receiving or
eavesdropping $\\{\vec{a}_{i}\\}_{i=1}^{N}$ and $\\{c_{i}\\}_{i=1}^{N}$ only.
And, another version of LWE problem is to solve the equation (6) and find the
value of the key $\mathsf{sk}$, from given data of $\\{c_{i}\\}_{i=1}^{N}$ and
$\\{\vec{a}_{i}\\}_{i=1}^{N}$.

Note that the equation (6) is defined over the space ${\mathbb{Z}}_{q}$ with
modulo operation, so that the problem is different from the simple least
square problem over real numbers. It has been known that the LWE-problems are
hard; for example, it has been proven in [20] that the latter version of
problem is hard as “worst-case lattice problems,” and it has also been known
as “post-quantum cryptography” [58].

The level of “hardness” is determined by the parameters; the dimension $n$ for
the key $\mathsf{sk}\in{\mathbb{Z}}^{n}$ and the vector
$a\in{\mathbb{Z}}_{q}^{n}$, the modulus $q$, and the standard deviation
$\sigma$ for the error distribution $N(0,\sigma)$. For example, in [57], it
has been suggested to choose the parameters to satisfy

$n\log
q\geq\frac{\lambda+110}{7.2}\cdot\left(\log\left(\frac{\sqrt{2\pi}\sigma}{q}\right)\right)^{2},$
(7)

in order for “$\lambda$-bit security,” which means more than
$2^{\lambda}$-times of iterations of a certain computation are required to
solve the LWE problem. Typically, to ensure a higher level of security, a
larger dimension $n$ is chosen for the key $\mathsf{sk}\in{\mathbb{Z}}^{n}$.

Then, thanks to the security guaranteed from the LWE problems, we may define
an encrypted algorithm with the key333Usually, the components of $\mathsf{sk}$
are generated by sampling from the distribution $N(0,\sigma)$, the same
distribution for the errors. $\mathsf{sk}\in{\mathbb{Z}}^{n}$, as

$\text{for}~{}m\in{\mathbb{Z}}_{q},\quad\mathsf{Enc}(m):=\begin{bmatrix}m+\mathsf{sk}\cdot
a+e\\\ a\end{bmatrix}\mod
q\quad\in{\mathbb{Z}}_{q}^{\mathfrak{n}},\qquad\mathfrak{n}:=n+1,$ (8)

where the components of the column vector $a\in{\mathbb{Z}}_{q}^{n}$ are
uniformly sampled from ${\mathbb{Z}}_{q}$ and the error $e\in{\mathbb{Z}}$ is
sampled from $N(0,\sigma)$ analogous to (5). We omit the argument of the key
$\mathsf{sk}$ from all the cryptosystem algorithms, for simplicity. Note that,
the encryption outcome becomes an $(\mathfrak{n}=n+1)$-dimensional vector
consisting of elements in ${\mathbb{Z}}_{q}$; as LWE problems suppose that the
vector $a$ be public, so that it can be treated as a part of encrypted message
(it will be used for decryption, to restore the message). It can be understood
that every encrypted message consists of “message part,” “random-like part,”
and “error part,” as

$\mathsf{Enc}(m)=\begin{bmatrix}m\\\ 0_{n\times
1}\end{bmatrix}+\begin{bmatrix}\mathsf{sk}\cdot a\\\
a\end{bmatrix}+\begin{bmatrix}e\\\ 0_{n\times 1}\end{bmatrix}\mod q,$ (9)

where the information of the message is contained in the first component.

As the encryption is to add a random-like number $\mathsf{sk}\cdot a$ to the
message together with an error, it can be decrypted by simply canceling out
the same number $\mathsf{sk}\cdot a$; let the decryption for a ciphertext
$\mathbf{c}\in{\mathbb{Z}}_{q}^{\mathfrak{n}}$ be defined as

$\mathsf{Dec}(\mathbf{c}):=\begin{bmatrix}1&-\mathsf{sk}\end{bmatrix}\cdot\mathbf{c}\mod
q\quad\in{\mathbb{Z}}_{q},$ (10)

considering that the “random-like term” $[\mathsf{sk}\cdot a,a^{\top}]^{\top}$
in (9) as a column vector will be canceled out whenever the secret key
$[1,-\mathsf{sk}]$ is multiplied from the left, regardless of the random part
$a$. Indeed, it is obvious that

$\mathsf{Dec}(\mathsf{Enc}(m))=m+e\mod q$ (11)

holds, when the ciphertext $c$ is simply a newly encrypted message. The
cryptosystem being described is “symmetric” as a basic case, where the same
key $\mathsf{sk}$ is used for both the encryption and decryption. For a
public-key LWE-based cryptosystem in which encryption is possible without
knowledge of the key $\mathsf{sk}$, interested readers may refer to [57].

It can be seen in (11) that the error $e$, “injected” during encryption
because of security, may perturb the decryption outcome not equal to the
original message. To negate the effect of errors, a scale factor can be used
for the messages; let us neglect the probability that a sample from the
distribution $N(0,\sigma)$ is larger than a particular multiple $n_{0}\sigma$
of $\sigma$, $n_{0}\in{\mathbb{N}}$, and assume that every error $e$ sampled
from $N(0,\sigma)$ is such that $|e|\leq n_{0}\sigma$. Then, by modifying the
encryption as

$\mathsf{Enc}_{\mathsf{L}}(m):=\mathsf{Enc}(\mathsf{L}m~{}~{}\mathrm{mod}~{}q),$
(12)

with some scale factor $\mathsf{L}\in{\mathbb{N}}$ such that
$\mathsf{L}/2>n_{0}\sigma$, the message can be restored without error as

$\mathsf{Dec}(\mathsf{Enc}_{\mathsf{L}}(m))=\mathsf{L}m+e\mod
q\quad\implies\quad\left\lceil\frac{\mathsf{L}m+e\mod
q}{\mathsf{L}}\right\rfloor=m,$ (13)

as long as $0<m<(q/\mathsf{L})-(1/2)$ so that $0\leq\mathsf{L}m+e<q$.

As one of the simplest versions of LWE based schemes, it can be easily seen
that the encryption $\mathsf{Enc}$ is homomorphic with respect to addition.
Let the addition of two encrypted messages be defined simply by the component-
wise modular addition as

$\mathbf{c}_{1}\in{\mathbb{Z}}_{q}^{\mathfrak{n}},~{}~{}\mathbf{c}_{2}\in{\mathbb{Z}}_{q}^{\mathfrak{n}}\qquad\mapsto\qquad\mathbf{c}_{1}+\mathbf{c}_{2}\mod
q\quad\in{\mathbb{Z}}_{q}^{\mathfrak{n}}.$

Then, since the decryption $\mathsf{Dec}$ is nothing but multiplying a row
vector, by the distributive law, it is obvious that

$\displaystyle\begin{split}\mathsf{Dec}(\mathbf{c}_{1}+\mathbf{c}_{2}\mod
q)&=\begin{bmatrix}1&-\mathsf{sk}\end{bmatrix}\cdot(\mathbf{c}_{1}+\mathbf{c}_{2})\mod
q\\\ &=\mathsf{Dec}(\mathbf{c}_{1})+\mathsf{Dec}(\mathbf{c}_{2})\mod
q\end{split}$ (14)

holds for every ciphertexts $\mathbf{c}_{1}\in{\mathbb{Z}}_{q}^{\mathfrak{n}}$
and $\mathbf{c}_{2}\in{\mathbb{Z}}_{q}^{\mathfrak{n}}$. It means that the
modular addition for the messages in ${\mathbb{Z}}_{q}$ can be performed as
encrypted, by the same (component-wise) modular addition over the ciphertext
space ${\mathbb{Z}}_{q}^{\mathfrak{n}}$, because the decryption of the
computation outcome matches to the addition of the plaintext messages
$\mathsf{Dec}(\mathbf{c}_{1})$ and $\mathsf{Dec}(\mathbf{c}_{2})$.

Multiplication of a ciphertext
$\mathbf{c}_{1}\in{\mathbb{Z}}_{q}^{\mathfrak{n}}$ by an un-encrypted integer
$k\in{\mathbb{Z}}$ can be done analogously, as

$k\in{\mathbb{Z}},~{}~{}\mathbf{c}_{1}\in{\mathbb{Z}}_{q}^{\mathfrak{n}}\qquad\mapsto\qquad
k\cdot\mathbf{c}_{1}\mod q\quad\in{\mathbb{Z}}_{q}^{\mathfrak{n}},$ (15)

which is simply the component-wise modular multiplication by the constant $k$.
It is also clear that

$\displaystyle\begin{split}\mathsf{Dec}(k\cdot\mathbf{c}_{1}\mod
q)&=\begin{bmatrix}1&-\mathsf{sk}\end{bmatrix}\cdot(k\cdot\mathbf{c}_{1})\mod
q\\\ &=k\cdot\mathsf{Dec}(\mathbf{c}_{1})\mod q,\end{split}$ (16)

so the decryption outcome of integer multiplication for encrypted messages
matches to that over plaintexts.

In general, LWE-based cryptosystems are also multiplicatively homomorphic,
which means they allow multiplication by an encrypted number to ciphertexts as
well as by the un-encrypted integer multiplication as in (15). Nonetheless, in
fact, there is no “trivial way” of performing multiplication of a ciphertext
$\mathbf{c}_{1}\in{\mathbb{Z}}_{q}^{\mathfrak{n}}$ to another ciphertext
$\mathbf{c}_{2}\in{\mathbb{Z}}_{q}^{\mathfrak{n}}$, since the component-wise
multiplication over ${\mathbb{Z}}_{q}^{\mathfrak{n}}$ would not work (i.e.,
decryption outcome of component-wise multiplication would not match with
multiplication between the messages), and it seems there is no other
“intuitive way” of multiplying two vectors in
${\mathbb{Z}}_{q}^{\mathfrak{n}}$ yielding the same form in
${\mathbb{Z}}_{q}^{\mathfrak{n}}$. In this regard, a separate encryption
method as well as an encrypted multiplication method proposed in [56] and [34]
is introduced in the next subsection.

####  3.1.2 Gentry-Sahai-Waters (GSW) scheme and encrypted recursive
multiplication [56, 34]

An idea for multiplication by an encrypted message is to consider a separate
encryption method whose outcome is a matrix in
${\mathbb{Z}}_{q}^{\mathfrak{n}\times\mathfrak{n}}$, so that it can be
multiplied to the ciphertexts of column vectors in
${\mathbb{Z}}_{q}^{\mathfrak{n}}$ from the left naturally; consider a
“multiplier” $k\in{\mathbb{Z}}_{q}$ encrypted as

$k\in{\mathbb{Z}}_{q}\qquad\mapsto\qquad\mathbf{C}=k\cdot
I_{\mathfrak{n}}+\begin{bmatrix}\mathsf{sk}\cdot a_{1}&\mathsf{sk}\cdot
a_{2}&\cdots&\mathsf{sk}\cdot a_{\mathfrak{n}}\\\
a_{1}&a_{2}&\cdots&a_{\mathfrak{n}}\end{bmatrix}+\begin{bmatrix}e_{1}&e_{2}&\cdots&e_{\mathfrak{n}}\\\
0_{n\times 1}&0_{n\times 1}&\cdots&0_{n\times 1}\end{bmatrix}\mod
q\quad\in{\mathbb{Z}}_{q}^{\mathfrak{n}\times\mathfrak{n}}$ (17)

where $a_{i}\in{\mathbb{Z}}_{q}^{n}$ is a uniformly random vector and $e_{i}$
is an error sampled from $N(0,\sigma)$ for each $i=1,\ldots\mathfrak{n}$,
respectively. The massage part $k\cdot I_{\mathfrak{n}}$ in (17) is added by a
matrix consisting of “random-like” vectors plus errors analogous to (9), so
obviously it is also an LWE-based encryption.

Then, it can be checked if the multiplication outcome of

$\mathbf{C}\in{\mathbb{Z}}_{q}^{\mathfrak{n}\times\mathfrak{n}},~{}~{}\mathbf{c}\in{\mathbb{Z}}_{q}^{\mathfrak{n}}\qquad\mapsto\qquad\mathbf{C}\cdot\mathbf{c}\mod
q\quad\in{\mathbb{Z}}_{q}^{\mathfrak{n}}$ (18)

(multiplication of the matrix
$\mathbf{C}\in{\mathbb{Z}}_{q}^{\mathfrak{n}\times\mathfrak{n}}$ from (17) to
a ciphertext vector $\mathbf{c}\in{\mathbb{Z}}_{q}^{\mathfrak{n}}$) has the
message parts multiplied with each other; let us decrypt the outcome (18) by
multiplying $[1,-\mathsf{sk}]$ from the left (just as in (10)), which yields

$\displaystyle\mathsf{Dec}(\mathbf{C}\cdot\mathbf{c}\mod q)$
$\displaystyle\quad=\begin{bmatrix}1&-\mathsf{sk}\end{bmatrix}\cdot\left(k\cdot
I_{\mathfrak{n}}+\begin{bmatrix}\mathsf{sk}\cdot a_{1}&\cdots&\mathsf{sk}\cdot
a_{\mathfrak{n}}\\\
a_{1}&\cdots&a_{\mathfrak{n}}\end{bmatrix}+\begin{bmatrix}e_{1}&\cdots&e_{\mathfrak{n}}\\\
0_{n\times 1}&\cdots&0_{n\times 1}\end{bmatrix}\right)\cdot\mathbf{c}\mod q$
$\displaystyle\quad=\begin{bmatrix}1&-\mathsf{sk}\end{bmatrix}\cdot\left(k\cdot
I_{\mathfrak{n}}+\begin{bmatrix}e_{1}&\cdots&e_{\mathfrak{n}}\\\ 0_{n\times
1}&\cdots&0_{n\times 1}\end{bmatrix}\right)\cdot\mathbf{c}\mod q$
$\displaystyle\quad=k\cdot\mathsf{Dec}(\mathbf{c})+\begin{bmatrix}e_{1}&\cdots&e_{\mathfrak{n}}\end{bmatrix}\cdot\mathbf{c}\mod
q.$

It can be seen that the encryption is homomorphic with respect to the
multiplication, in the sense that the decryption outcome has the message
$\mathsf{Dec}(\mathbf{c})$ multiplied by $k$. However, it can be found that
the injected errors $[e_{1},\ldots e_{\mathfrak{n}}]$, whose components were
smaller than $n_{0}\sigma$, have been multiplied by the ciphertext
$\mathbf{c}\in{\mathbb{Z}}_{q}^{\mathfrak{n}}$ consisting of large numbers.
Then, the size of the error “grows” too large and it will even dominate the
message part, so that the computation result will not be correct at all. Thus,
the described method cannot be applied as it is, so modified as follows.

Considering that the problem of the method (18) was due to the large size of
the “multiplicand” $\mathbf{c}\in{\mathbb{Z}}_{q}^{\mathfrak{n}}$ amplifying
the errors, the method in [56] called “Gentry-Sahai-Waters (GSW)” scheme
suggests that the multiplication be done in a different manner, to reduce the
size of the multiplicand; consider multiplication of a vector
$\mathsf{x}\in{\mathbb{Z}}_{q}^{\mathfrak{n}}$ by $k\in{\mathbb{Z}}_{q}$,
represented as

$k\cdot\mathsf{x}=k\cdot\left(\sum_{i=0}^{d-1}\nu^{i}\cdot\mathsf{x}_{i}\right)=k\cdot\begin{bmatrix}I_{\mathfrak{n}}&\nu\cdot
I_{\mathfrak{n}}&\cdots&\nu^{d-1}\cdot
I_{\mathfrak{n}}\end{bmatrix}\cdot\begin{bmatrix}\mathsf{x}_{0}\\\
\mathsf{x}_{1}\\\ \vdots\\\ \mathsf{x}_{d-1}\end{bmatrix},$ (19)

where $\nu\in{\mathbb{N}}$ is a base chosen such that $\nu^{d-1}<q\leq\nu^{d}$
with some $d\in{\mathbb{N}}$, so that the vector
$\mathsf{x}\in{\mathbb{Z}}_{q}^{\mathfrak{n}}$ is represented by “$\nu$-ary
numeral system” as $\mathsf{x}=\sum_{i=0}^{d-1}\nu^{i}\cdot\mathsf{x}_{i}$
with some vectors $\\{\mathsf{x}_{i}\\}_{i=0}^{d-1}$ of non-negative integers
such that $\|\mathsf{x}_{i}\|<\nu$, $\forall i$. Then, by defining

$G:=\begin{bmatrix}I_{\mathfrak{n}}&\nu\cdot
I_{\mathfrak{n}}&\cdots&\nu^{d-1}\cdot
I_{\mathfrak{n}}\end{bmatrix}\qquad\text{and}\qquad
D(\mathsf{x}):=\begin{bmatrix}\mathsf{x}_{0}\\\ \mathsf{x}_{1}\\\ \vdots\\\
\mathsf{x}_{d-1}\end{bmatrix},$

and rewriting (19) as

$k\cdot\mathsf{x}=(k\cdot G)\cdot D(\mathsf{x}),$

one can have the size of the multiplicand reduced as $\|D(\mathsf{x})\|<\nu$,
thanks to the “decomposition” function $D$. For example, consider the equation
$77=7\times 11$ re-written as

$77=\left(7\times\begin{bmatrix}2^{0}&2^{1}&2^{2}&2^{3}\end{bmatrix}\right)\times\begin{bmatrix}1\\\
1\\\ 0\\\ 1\end{bmatrix}$

with $d=4$, $\nu=2$. It can be seen that the norm of the multiplicand (which
was $11$) is reduced.

From this observation, the GSW scheme slightly modifies the encryption
algorithm (17), as

$\mathsf{Enc}^{\prime}(k):=k\cdot G+\begin{bmatrix}\mathsf{sk}\cdot
a_{1}&\mathsf{sk}\cdot a_{2}&\cdots&\mathsf{sk}\cdot a_{d\mathfrak{n}}\\\
a_{1}&a_{2}&\cdots&a_{d\mathfrak{n}}\end{bmatrix}+\begin{bmatrix}e_{1}&e_{2}&\cdots&e_{d\mathfrak{n}}\\\
0_{n\times 1}&0_{n\times 1}&\cdots&0_{n\times 1}\end{bmatrix}\mod
q\quad\in{\mathbb{Z}}_{q}^{\mathfrak{n}\times d\mathfrak{n}},$

by substituting $I_{\mathfrak{n}}$ in (17) by the matrix $G$ and increasing
the column dimension $d$-times. Now, let the multiplication of a ciphertext
$\mathbf{c}\in{\mathbb{Z}}_{q}^{\mathfrak{n}}$ by an encrypted message
$\mathsf{Enc}^{\prime}(k)$, be performed as

$\mathsf{Enc}^{\prime}(k)\in{\mathbb{Z}}_{q}^{\mathfrak{n}\times
d\mathfrak{n}},~{}~{}\mathbf{c}\in{\mathbb{Z}}_{q}^{\mathfrak{n}}\qquad\mapsto\qquad\mathsf{Enc}^{\prime}(k)\cdot
D(\mathbf{c})\mod q\in{\mathbb{Z}}_{q}^{\mathfrak{n}},$ (20)

which enlarges the dimension of $\mathbf{c}$ by the decomposition first and
then multiply to the encrypted multiplier. Then, let us decrypt the outcome
and check the multiplicatively homomorphic property and the growth of the
error again, as

$\displaystyle\mathsf{Dec}(\mathsf{Enc}^{\prime}(k)\cdot D(\mathbf{c})\mod q)$
$\displaystyle\quad=\begin{bmatrix}1&-\mathsf{sk}\end{bmatrix}\cdot\left(k\cdot
G+\begin{bmatrix}\mathsf{sk}\cdot a_{1}&\cdots&\mathsf{sk}\cdot
a_{d\mathfrak{n}}\\\
a_{1}&\cdots&a_{d\mathfrak{n}}\end{bmatrix}+\begin{bmatrix}e_{1}&\cdots&e_{d\mathfrak{n}}\\\
0_{n\times 1}&\cdots&0_{n\times 1}\end{bmatrix}\right)\cdot D(\mathbf{c})\mod
q$
$\displaystyle\quad=\begin{bmatrix}1&-\mathsf{sk}\end{bmatrix}\cdot\left(k\cdot
G+\begin{bmatrix}e_{1}&\cdots&e_{d\mathfrak{n}}\\\ 0_{n\times
1}&\cdots&0_{n\times 1}\end{bmatrix}\right)\cdot D(\mathbf{c})\mod q$
$\displaystyle\quad=\begin{bmatrix}1&-\mathsf{sk}\end{bmatrix}\cdot
k\cdot\mathbf{c}+\begin{bmatrix}e_{1}&\cdots&e_{d\mathfrak{n}}\end{bmatrix}\cdot
D(\mathbf{c})\mod q$
$\displaystyle\quad=k\cdot\mathsf{Dec}(\mathbf{c})+\begin{bmatrix}e_{1}&\cdots&e_{d\mathfrak{n}}\end{bmatrix}\cdot
D(\mathbf{c})\mod q.$

It turns out that, thanks to the size of the multiplicand
$\mathbf{c}\in{\mathbb{Z}}_{q}^{\mathfrak{n}}$ reduced by the decomposition
$D$ as $\|D(\mathbf{c})\|<\nu$, the effect of the error becomes bounded by a
constant proportional to the parameter $\nu$ (recall that the base $\nu$ can
be chosen such that $\nu\ll q$). Putting all together, the homomorphic
properties of the described cryptosystem is listed as the following
proposition.

###### Proposition 1

The following holds.

  1. 1.

For every $m\in{\mathbb{Z}}_{q}$, it satisfies
$\mathsf{Dec}(\mathsf{Enc}(m))=m+e\mod q$, with some $e\in{\mathbb{Z}}$ such
that $|e|\leq n_{0}\sigma$.

  2. 2.

For any ciphertexts $\mathbf{c}_{1}\in{\mathbb{Z}}_{q}^{\mathfrak{n}}$ and
$\mathbf{c}_{2}\in{\mathbb{Z}}_{q}^{\mathfrak{n}}$, they satisfy
$\mathsf{Dec}(\mathbf{c}_{1}+\mathbf{c}_{2}\mod
q)=\mathsf{Dec}(\mathbf{c}_{1})+\mathsf{Dec}(\mathbf{c}_{2})\mod q$.

  3. 3.

For any $k\in{\mathbb{Z}}$ and $\mathbf{c}\in{\mathbb{Z}}_{q}^{\mathfrak{n}}$,
they satisfy $\mathsf{Dec}(k\cdot\mathbf{c}\mod
q)=k\cdot\mathsf{Dec}(\mathbf{c})\mod q$.

  4. 4.

For any $k\in{\mathbb{Z}}_{q}$ and
$\mathbf{c}\in{\mathbb{Z}}_{q}^{\mathfrak{n}}$, they satisfy
$\mathsf{Dec}(\mathsf{Enc}^{\prime}(k)\cdot D(\mathbf{c})\mod
q)=k\cdot\mathsf{Dec}(\mathbf{c})+e\mod q$, with some $e\in{\mathbb{Z}}$ such
that $|e|\leq\Delta_{\mathsf{Mult}}:=d\mathfrak{n}\cdot n_{0}\sigma\cdot\nu$.

$\square$

The homomorphic properties directly extended to matrix-vector multiplication
over encrypted data, by considering component-wise encryption and operations;
let us abuse the notation and the algorithms $\mathsf{Enc}$ and $\mathsf{Dec}$
be also applied to vector of messages component-wisely, as

$\mathsf{Enc}\left(\vec{m}\right):=\begin{bmatrix}\mathsf{Enc}(m_{1})\\\
\mathsf{Enc}(m_{2})\\\ \vdots\\\
\mathsf{Enc}(m_{l})\end{bmatrix}\in{\mathbb{Z}}_{q}^{l\mathfrak{n}},$ (21a)
for $\vec{m}=\mathrm{col}\\{m_{i}\\}_{i=1}^{l}\in{\mathbb{Z}}_{q}^{l}$, and
$\mathsf{Dec}(\vec{\mathbf{c}}):=\begin{bmatrix}\mathsf{Dec}(\mathbf{c}_{1})\\\
\mathsf{Dec}(\mathbf{c}_{2})\\\ \vdots\\\
\mathsf{Dec}(\mathbf{c}_{l})\end{bmatrix}\in{\mathbb{Z}}_{q}^{l},$ (21b) for
$\vec{\mathbf{c}}=\mathrm{col}\\{\mathbf{c}_{i}\\}_{i=1}^{l}\in{\mathbb{Z}}_{q}^{l\mathfrak{n}}$,
$\mathbf{c}_{i}\in{\mathbb{Z}}_{q}^{\mathfrak{n}}$, $i=1,\ldots,l$. And, let
matrices consisting of elements in ${\mathbb{Z}}_{q}$ be encrypted using the
encryption $\mathsf{Enc}^{\prime}$ component-wisely, as
$\mathsf{Enc}^{\prime}(\mathsf{F})=\begin{bmatrix}\mathsf{Enc}^{\prime}(\mathsf{F}_{11})&\mathsf{Enc}^{\prime}(\mathsf{F}_{12})&\cdots&\mathsf{Enc}^{\prime}(\mathsf{F}_{1l_{2}})\\\
\mathsf{Enc}^{\prime}(\mathsf{F}_{21})&\mathsf{Enc}^{\prime}(\mathsf{F}_{22})&\cdots&\mathsf{Enc}^{\prime}(\mathsf{F}_{2l_{2}})\\\
\vdots&\vdots&\ddots&\vdots\\\
\mathsf{Enc}^{\prime}(\mathsf{F}_{l_{1}1})&\mathsf{Enc}^{\prime}(\mathsf{F}_{l_{1}2})&\cdots&\mathsf{Enc}^{\prime}(\mathsf{F}_{l_{1}l_{2}})\end{bmatrix}\in{\mathbb{Z}}_{q}^{(l_{1}\mathfrak{n})\times(dl_{2}\mathfrak{n})}$
(21c) for $\mathsf{F}=[\mathsf{F}_{ij}]\in{\mathbb{Z}}_{q}^{l_{1}\times
l_{2}}$, and let the multiplication of a vector of encrypted messages by an
encrypted matrix be considered as
$\mathsf{Enc}^{\prime}(\mathsf{F})\in{\mathbb{Z}}_{q}^{(l_{1}\mathfrak{n})\times(dl_{2}\mathfrak{n})},~{}~{}\vec{\mathbf{c}}\in{\mathbb{Z}}_{q}^{l_{2}\mathfrak{n}}\quad\mapsto\quad\mathsf{Enc}^{\prime}(\mathsf{F})\cdot
D(\vec{\mathbf{c}})\mod q,$ (21d) where we also let the decomposition $D$ be
applied to a vector of encrypted messages component-wisely as
$D(\vec{\mathbf{c}}):=\mathrm{col}\\{D(\mathbf{c}_{i})\\}_{i=1}^{l_{2}}\in{\mathbb{Z}}_{q}^{l_{2}d\mathfrak{n}}$.
Then, it is easy to verify that the following proposition holds.

###### Proposition 2

For any matrix $\mathsf{F}\in{\mathbb{Z}}_{q}^{l_{1}\times l_{2}}$ and a
ciphertext of encrypted messages
$\vec{\mathbf{c}}\in{\mathbb{Z}}_{q}^{l_{2}\mathfrak{n}}$, they satisfy444Note
that $\Delta_{\mathsf{Mult}}$ is defined from Proposition 1.4.

$\mathsf{Dec}(\mathsf{Enc}^{\prime}(\mathsf{F})\cdot D(\vec{\mathbf{c}})\mod
q)=\mathsf{F}\cdot\mathsf{Dec}(\vec{\mathbf{c}})+\vec{e}\mod q,$ (22)

with some $\vec{e}\in{\mathbb{Z}}^{l_{1}}$ such that $\|\vec{e}\|\leq
l_{2}\Delta_{\mathsf{Mult}}$. $\square$

Note that the multiplication of an “LWE type” ciphertext by a “GSW type”
encrypted matrix yields an “LWE type” ciphertext. The encryption method of
$\mathsf{Enc}^{\prime}$ has been introduced in [56] where multiplication
between GSW type ciphertexts has been presented, and the multiplication of an
LWE type ciphertext by a GSW type ciphertext has been considered in [34].

Now, we further discuss homomorphic property with respect to “recursive”
operation. Let us compare the following two types of homomorphic properties:

$\displaystyle\text{Property
1}:\quad\mathsf{Dec}(\mathsf{Enc}(\mathsf{x}_{1})\ast\mathsf{Enc}(\mathsf{x}_{2}))=\mathsf{x}_{1}\cdot\mathsf{x}_{2}\mod
q,\qquad\forall\mathsf{x}_{1}\in{\mathbb{Z}}_{q},~{}\mathsf{x}_{2}\in{\mathbb{Z}}_{q}\quad(\text{plaintexts})$
$\displaystyle\text{Property
2}:\quad\mathsf{Dec}(\mathbf{c}_{1}\ast\mathbf{c}_{2})=\mathsf{Dec}(\mathbf{c}_{1})\cdot\mathsf{Dec}(\mathbf{c}_{2})\mod
q,\qquad\forall\mathbf{c}_{1}\in{\mathbb{Z}}_{q}^{\mathfrak{n}},~{}\mathbf{c}_{2}\in{\mathbb{Z}}_{q}^{\mathfrak{n}}\quad(\text{ciphertexts})$

where $\ast$ denotes a certain operation over encrypted data that matches to
the multiplication over plaintexts. Each of the properties implies an ability
of multiplication over encrypted data, but it can be observed that Property
$2$ implies Property $1$, but Property $1$ does not imply Property $2$
conversely, in general; this is because Property $1$ can be applied to “newly”
encrypted messages only, whereas Property $2$ can be applied to any
ciphertexts. For example, for a ciphertext
$\mathbf{c}\in{\mathbb{Z}}_{q}^{\mathfrak{n}}$ which is a computation outcome
as
$\mathbf{c}=\mathsf{Enc}(\mathsf{x}_{1})\ast\mathsf{Enc}(\mathsf{x}_{2})\\!\\!\mod
q$ with some $\mathsf{x}_{1}\in{\mathbb{Z}}_{q}$ and
$\mathsf{x}_{2}\in{\mathbb{Z}}_{q}$, it is clear that the property of
multiplication is applicable to $\mathbf{c}$ if the cryptosystem satisfies
Property $2$, whereas the multiplication may not be applicable to $\mathbf{c}$
even if the cryptosystem satisfies Property $1$, because there is no guarantee
that there exists a message $\mathsf{x}^{\prime}\in{\mathbb{Z}}_{q}$ such that
$\mathbf{c}=\mathsf{Enc}(\mathsf{x}^{\prime})$.

Keeping this observation in mind, let us revisit the property (22) that we
obtained. In the left hand side where the encrypted multiplication is
performed, the argument of left multiplier considers GSW type ciphertext
$\mathsf{Enc}^{\prime}(\mathsf{F})$ as newly encrypted message only, but the
argument of the right multiplicand considers any LWE type ciphertext,
regardless if is a newly encrypted message or it was used for certain
encrypted operations. Since the outcome of the multiplication is also an LWE
type ciphertext, the property (22) implies that the encrypted multiplication
is applicable to LWE type ciphertexts recursively, unlimited number of times.
Meanwhile, since an error $\vec{e}$ is added to the encrypted message whenever
the multiplication is performed, it is notable that the “growth of error” can
be accumulated under recursive operation. In the next subsection, when the LWE
based cryptosystem is applied to dynamic control operations, it will be seen
that the growth of error accumulated in LWE type ciphertexts under recursive
operation can be “controlled” under stability.

The effect of error can be reduced by using a scale factor for the LWE type
encryption, as seen in (13); for instance, let the property (22) be rewritten
with respect to the encryption (12), as

$\mathsf{Dec}(\mathsf{Enc}^{\prime}(\mathsf{F})\cdot
D(\mathsf{Enc}_{\mathsf{L}}(\mathsf{x}))\mod
q)=\mathsf{F}(\mathsf{L}\cdot\mathsf{x}+\vec{e}_{1})+\vec{e}_{2}\mod q,$

where $\mathsf{x}\in{\mathbb{Z}}_{q}^{l_{2}}$, the error
$\vec{e}_{1}\in{\mathbb{Z}}_{q}^{l_{2}}$ from the encryption
$\mathsf{Enc}_{\mathsf{L}}$ is such that $\|\vec{e}_{1}\|\leq n_{0}\sigma$,
and the error $\vec{e}_{2}\in{\mathbb{Z}}_{q}^{l_{1}}$ from the multiplication
is such that $\|\vec{e}_{2}\|\leq l_{2}\Delta_{\mathsf{Mult}}$. Then, by
choosing the parameter $\mathsf{L}$ considering the size of grown error such
that $\mathsf{L}/2>\|\mathsf{F}\|\cdot
n_{0}\sigma+l_{2}\Delta_{\mathsf{Mult}}$, the expected outcome
$\mathsf{F}\cdot\mathsf{x}$ can be obtained without the error, as

$\left\lceil\frac{\mathsf{F}\cdot(\mathsf{L}\mathsf{x}+\vec{e}_{1})+\vec{e}_{2}\mod
q}{\mathsf{L}}\right\rfloor=\mathsf{F}\cdot\mathsf{x},$ (23)

as long as all the components of $\mathsf{F}\cdot\mathsf{x}$ is less than
$(q/\mathsf{L})-(1/2)$ and greater than $0$ so that the modulo operation in
(23) does nothing about the argument value. Note that the scale factor
$\mathsf{L}$ is used for the LWE type encryption only and not used for GSW
type encryption, so that the scaled LWE type messages are not multiplied with
another scale factor through the multiplication by GSW type encrypted
messages.

As a result of the enabled recursive multiplication, a class of dynamic
systems, which can be implemented to run over encrypted data exploiting the
homomorphic properties, is specified. Consider a system defined over the space
${\mathbb{Z}}_{q}$ written as

$\displaystyle\begin{split}\mathsf{z}(t+1)&=\mathsf{F}\cdot\mathsf{z}(t)+\mathsf{G}\cdot\mathsf{y}(t)\mod
q\\\
\mathsf{u}(t)&=\mathsf{H}\cdot\mathsf{z}(t)+\mathsf{J}\cdot\mathsf{y}(t)\mod
q\\\ \mathsf{z}(0)&=\mathsf{z}_{0}\in{\mathbb{Z}}_{q}^{\ell},\end{split}$ (24)

where $\mathsf{z}(t)\in{\mathbb{Z}}_{q}^{\ell}$ is the state with the initial
value $\mathsf{z}_{0}$, $\mathsf{y}(t)\in{\mathbb{Z}}_{q}^{\mathsf{p}}$ is the
input, $\mathsf{u}(t)\in{\mathbb{Z}}_{q}^{\mathsf{m}}$ is the output, and
$\\{\mathsf{F},\mathsf{G},\mathsf{H},\mathsf{J}\\}$ are matrices consisting of
elements in ${\mathbb{Z}}_{q}$. Then, an implication of Proposition 2 is that
the dynamic operation of (24) can be performed over encrypted data, as

$\displaystyle\begin{split}\mathbf{z}(t+1)&=\mathbf{F}\cdot
D(\mathbf{z}(t))+\mathbf{G}\cdot D(\mathsf{Enc}(\mathsf{y}(t)))\mod q\\\
\mathbf{u}(t)&=\mathbf{H}\cdot D(\mathbf{z}(t))+\mathbf{J}\cdot
D(\mathsf{Enc}(\mathsf{y}(t)))\mod q\\\
\mathbf{z}(0)&=\mathsf{Enc}(\mathsf{z}_{0}),\end{split}$ (25)

where $\mathbf{z}(t)\in{\mathbb{Z}}_{q}^{\ell\mathfrak{n}}$ is the state with
the initial value $\mathsf{Enc}(\mathsf{z}_{0})$,
$\mathsf{Enc}(\mathsf{y}(t))\in{\mathbb{Z}}_{q}^{\mathsf{p}\mathfrak{n}}$ is
the input, $\mathbf{u}(t)\in{\mathbb{Z}}_{q}^{\mathsf{m}\mathfrak{n}}$ is the
output, and $\\{\mathbf{F},\mathbf{G},\mathbf{H},\mathbf{J}\\}$ are the
encryptions of the matrices from (24), as

$\mathbf{F}=\mathsf{Enc}^{\prime}(\mathsf{F}),\quad\mathbf{G}=\mathsf{Enc}^{\prime}(\mathsf{G}),\quad\mathbf{H}=\mathsf{Enc}^{\prime}(\mathsf{H}),\quad\mathbf{J}=\mathsf{Enc}^{\prime}(\mathsf{J}).$

As the configuration of an encrypted system described in Figure 2, it stores
the encrypted parameters
$\\{\mathbf{F},\mathbf{G},\mathbf{H},\mathbf{J},\mathbf{z}_{0}\\}$, receives
the input $\mathsf{y}(t)$ as an LWE type newly encrypted signal, and computes
the next state $\mathbf{z}(t+1)$ and the output $\mathbf{u}(t)$, respectively,
using the GSW-LWE matrix multiplication and the addition between LWE type
ciphertexts. The performance of the system (25) can be analyzed, by decrypting
the signals $\mathbf{z}(t)$ and $\mathbf{u}(t)$ and comparing to that of the
un-encrypted model (24), as the following proposition.

###### Proposition 3

Consider the messages
$\tilde{\mathsf{z}}(t):=\mathsf{Dec}(\mathbf{z}(t))\in{\mathbb{Z}}_{q}^{\ell}$
and
$\tilde{\mathsf{u}}(t):=\mathsf{Dec}(\mathbf{u}(t))\in{\mathbb{Z}}_{q}^{\mathsf{m}}$
of the encrypted trajectories of (25). They obey

$\displaystyle\begin{split}\tilde{\mathsf{z}}(t+1)&=\mathsf{F}\cdot\tilde{\mathsf{z}}(t)+\mathsf{G}\cdot(\mathsf{y}(t)+\Delta_{\mathsf{y}}(t))+\Delta_{\mathsf{z}}(t)\mod
q\\\
\tilde{\mathsf{u}}(t)&=\mathsf{H}\cdot\tilde{\mathsf{z}}(t)+\mathsf{J}\cdot(\mathsf{y}(t)+\Delta_{\mathsf{y}}(t))+\Delta_{\mathsf{u}}(t)\mod
q\\\ \tilde{\mathsf{z}}(0)&=\mathsf{z}_{0}+\Delta_{0}\mod q,\end{split}$ (26)

with some $\Delta_{\mathsf{y}}(t)\in{\mathbb{Z}}^{\mathsf{p}}$,
$\Delta_{\mathsf{z}}(t)\in{\mathbb{Z}}^{\ell}$,
$\Delta_{\mathsf{u}}(t)\in{\mathbb{Z}}^{\mathsf{m}}$, and
$\Delta_{0}\in{\mathbb{Z}}^{\ell}$ such that

$\|\Delta_{\mathsf{y}}(t)\|\leq
n_{0}\sigma,\qquad\|\Delta_{\mathsf{z}}(t)\|\leq(\ell+\mathsf{p})\Delta_{\mathsf{Mult}},\qquad\|\Delta_{\mathsf{u}}(t)\|\leq(\ell+\mathsf{p})\Delta_{\mathsf{Mult}},\qquad\|\Delta_{0}\|\leq
n_{0}\sigma,$ (27)

respectively. $\square$

Proof: By Propositions 2 and 1.1, it is obvious that

$\begin{bmatrix}\tilde{\mathsf{z}}(t+1)\\\
\tilde{\mathsf{u}}(t)\end{bmatrix}=\mathsf{Dec}\left(\begin{bmatrix}\mathbf{z}(t+1)\\\
\mathbf{u}(t)\end{bmatrix}\right)=\mathsf{Dec}\left(\begin{bmatrix}\mathbf{F}&\mathbf{G}\\\
\mathbf{H}&\mathbf{J}\end{bmatrix}\cdot D\left(\begin{bmatrix}\mathbf{z}(t)\\\
\mathsf{Enc}(\mathsf{y}(t))\end{bmatrix}\right)\right)=\begin{bmatrix}\mathsf{F}&\mathsf{G}\\\
\mathsf{H}&\mathsf{J}\end{bmatrix}\cdot\begin{bmatrix}\tilde{\mathsf{z}}(t)\\\
\mathsf{y}(t)+\Delta_{\mathsf{y}}(t)\end{bmatrix}+\begin{bmatrix}\Delta_{\mathsf{z}}(t)\\\
\Delta_{\mathsf{u}}(t)\end{bmatrix}\mod q$

and
$\mathsf{Dec}(\mathbf{z}(0))=\mathsf{Dec}(\mathsf{Enc}(\mathsf{z}_{0}))=\mathsf{z}_{0}+\Delta_{0}$
hold, with some
$\\{\Delta_{\mathsf{y}}(t),\Delta_{\mathsf{z}}(t),\Delta_{\mathsf{u}}(t),\Delta_{0}\\}$
satisfying (27). $\blacksquare$

Proposition 3 shows that the performance of the encrypted system (25) is
equivalent to the system (26), which has the same parameters
$\\{\mathsf{F},\mathsf{G},\mathsf{H},\mathsf{J},\mathsf{z}_{0}\\}$ with that
of (24). It is found that the effect of the errors is denoted by
$\\{\Delta_{\mathsf{z}}(t),\Delta_{\mathsf{u}}(t),\Delta_{0}\\}$, which can be
seen as disturbances or perturbations bounded as (27).

In order to have the error effect relatively small, the encryption
$\mathsf{Enc}_{\mathsf{L}}$ with the scale factor $\mathsf{L}$ can be used for
the input $\mathsf{y}(t)$ and the state $\mathsf{z}(t)$, as

$\displaystyle\begin{split}\mathbf{z}(t+1)&=\mathbf{F}\cdot
D(\mathbf{z}(t))+\mathbf{G}\cdot
D(\mathsf{Enc}_{\mathsf{L}}(\mathsf{y}(t)))\mod q\\\
\mathbf{u}(t)&=\mathbf{H}\cdot D(\mathbf{z}(t))+\mathbf{J}\cdot
D(\mathsf{Enc}_{\mathsf{L}}(\mathsf{y}(t)))\mod q\\\
\mathbf{z}(0)&=\mathsf{Enc}_{\mathsf{L}}(\mathsf{z}_{0}).\end{split}$ (28)

In the following corollary, it can be observed that only the messages in the
dynamics are scaled by the factor $\mathsf{L}$, while the bound for the errors
remains the same.

###### Corollary 1

The messages $\tilde{\mathsf{z}}(t)=\mathsf{Dec}(\mathbf{z}(t))$ and
$\tilde{\mathsf{u}}(t)=\mathsf{Dec}(\mathbf{u}(t))$ of the system (28) obey

$\displaystyle\begin{split}\tilde{\mathsf{z}}(t+1)&=\mathsf{F}\cdot\tilde{\mathsf{z}}(t)+\mathsf{G}\cdot(\mathsf{L}\cdot\mathsf{y}(t)+\Delta_{\mathsf{y}}(t))+\Delta_{\mathsf{z}}(t)\mod
q\\\
\tilde{\mathsf{u}}(t)&=\mathsf{H}\cdot\tilde{\mathsf{z}}(t)+\mathsf{J}\cdot(\mathsf{L}\cdot\mathsf{y}(t)+\Delta_{\mathsf{y}}(t))+\Delta_{\mathsf{u}}(t)\mod
q\\\ \tilde{\mathsf{z}}(0)&=\mathsf{L}\cdot\mathsf{z}_{0}+\Delta_{0}\mod
q,\end{split}$ (29)

where the errors $\Delta_{\mathsf{y}}(t)\in{\mathbb{Z}}^{\mathsf{p}}$,
$\Delta_{\mathsf{z}}(t)\in{\mathbb{Z}}^{\ell}$,
$\Delta_{\mathsf{u}}(t)\in{\mathbb{Z}}^{\mathsf{m}}$, and
$\Delta_{0}\in{\mathbb{Z}}^{\ell}$ satisfy (27). $\square$

We defer the discussion about the error effect in the closed-loop system of
the plant and the encrypted controller to the next subsection. It will be seen
that if the closed-loop system is stable with respect to “perturbations,” then
the effect of the errors can be made arbitrarily small by an appropriate
choice of the parameter $\mathsf{L}$.

In the remaining, we discuss the strengths and weaknesses of the GSW-LWE
encryption scheme. Compared to other LWE-based cryptosystems, an opportunity
cost of using the GSW scheme is that it may require a large amount of storage;
for example, if the parameters $(q,\sigma_{0},d)$ are chosen as
$(q,\sigma_{0},d)=(2^{48},10,3)$ and the desired bit-security level is
$\lambda={80}$, then the estimation (7) suggest that the dimension $n$ should
be chosen larger than $n=7.16\times 10^{2}$. It means that a scalar message
encrypted by GSW scheme turns into ($d\mathfrak{n}^{2}\approx 1.54\times
10^{6}$)-dimensional $48$-bit numbers. Instead, besides the abilities of
addition, multiplication, and recursive operation, another benefit of GSW-LWE
scheme is that its implementation is simple and easy; in contrast to the
cryptosystems requiring the modulus $q$ chosen as a large odd number, there is
no such restriction on the choice of the modulus $q$ with the GSW-LWE scheme.
Then, once choosing the modulus $q$ and the base $\nu$ chosen as powers of
$2$, it can be found that the encrypted addition and multiplication, and the
algorithms $\mathsf{Enc}$ and $\mathsf{Dec}$ can be implemented with simple
modular matrix multiplication, where the operations such as $(\cdot\mod q)$ or
$D(\cdot)$ can be easily performed using binary bit operations.

An example of computation times consumed for each encrypted operation is shown
in Table 2. In spite of a conservative choice of parameters to ensure the
security, the operations $\mathsf{Enc}$, $\mathsf{Dec}$, and the
multiplication turn out to be relatively fast. The encryption
$\mathsf{Enc}^{\prime}$ takes a relatively long time, but considering that it
will be used for encrypting the control parameters, it can be performed off-
line, while the controller is initialized. The component-wise encryption and
operation described in (21) would require a multiple of operation times as
many as the size of the dimension, but a “packing method” [59] for the GSW-LWE
scheme that encrypts a vector or a matrix into a “single ciphertext” can be
used for reducing the computation time in practice.

Table 2: Computation times for GSW-LWE algorithms for a scalar variable, tested with MATLAB using an Intel i5 processor with $16\mathrm{GB}$ RAM. $(\mathfrak{n},q,d)$ | $(50,2^{48},3)$ | $(1000,2^{48},3)$
---|---|---
$\mathsf{Enc}/\mathsf{Dec}$ | $0.2\mathrm{ms}$ | $2.6\mathrm{ms}$
$\mathsf{Enc}^{\prime}$ | $15\mathrm{ms}$ | $120\mathrm{ms}$
GSW-LWE multiplication | $0.7\mathrm{ms}$ | $19.9\mathrm{ms}$

###  3.2 Conversion of linear controllers to operate over ${\mathbb{Z}}_{q}$

The previous section showed that the dynamic operation of (24) can be
implemented as (25) with all the parameters and the signals encrypted with the
GSW-LWE scheme. Thus, the remaining task for the encrypted dynamic control
implementation is to convert the “given” dynamic controller (4) over
${\mathbb{R}}$ (which is supposed to be designed in advance) to a system of
the form (24) so that it can operate over the space ${\mathbb{Z}}_{q}$ based
on the modular arithmetic.

Let the system (24) be rewritten as

$\displaystyle\begin{split}\mathsf{z}(t+1)&=\mathsf{F}\cdot\mathsf{z}(t)+\mathsf{G}\cdot
Q(y(t))\mod q\\\ \mathsf{u}(t)&=\mathsf{H}\cdot\mathsf{z}(t)+\mathsf{J}\cdot
Q(y(t))\mod q\\\
\mathsf{z}(0)&=\mathsf{z}_{0}\in{\mathbb{Z}}_{q}^{\ell},\end{split}$ (30)

where $Q:{\mathbb{R}}^{\mathsf{p}}\rightarrow{\mathbb{Z}}_{q}^{\mathsf{p}}$ is
a quantization function so that the input $y(t)\in{\mathbb{R}}^{\mathsf{p}}$
of the given controller (4) can be regarded as the input of the system (30) as
well. Now, given the controller (4), the problem of interest is to design the
parameters $\\{\mathsf{F},\mathsf{G},\mathsf{H},\mathsf{J},\mathsf{z}_{0}\\}$
of (30), so that the performance of the system (30) over ${\mathbb{Z}}_{q}$ is
“practically equivalent” to that of the controller (4) over ${\mathbb{R}}$.
The problem is more specifically stated, as follows.

###### Problem 1

Given the parameters $\\{F,G,H,J,x_{0}\\}$ of the system (4) consisting of
real numbers together with a positive number $\epsilon>0$, find parameters
$\\{\mathsf{F},\mathsf{G},\mathsf{H},\mathsf{J},\mathsf{z}_{0}\\}$ of integers
and a function $Q$ for the system (30), and find a function
$g:{\mathbb{Z}}_{q}^{\mathsf{m}}\rightarrow{\mathbb{R}}^{\mathsf{m}}$, such
that $\|u(t)-g(\mathsf{u}(t))\|\leq\epsilon$ for all $t\geq 0$. $\square$

It is desirable that, as in Figure 2, only the encrypted signal of the plant
output $y(t)$ is received at the controller, and only the encrypted output of
$u(t)$ is transmitted back to the plant. Nonetheless, from the rationale that
the output of the system is supposed to be decrypted at the actuator, an
additional assumption can be considered that the decrypted signal of $u(t)$
can be re-encrypted and transmitted back to the controller again; let the
system (30) be replaced with the following form

$\displaystyle\begin{split}\mathsf{z}(t+1)&=\mathsf{F}\cdot\mathsf{z}(t)+\mathsf{G}\cdot
Q(y(t))+\mathsf{R}\cdot Q^{\prime}(\mathsf{u}(t))\mod q\\\
\mathsf{u}(t)&=\mathsf{H}\cdot\mathsf{z}(t)+\mathsf{J}\cdot Q(y(t))\mod q\\\
\mathsf{z}(0)&=\mathsf{z}_{0}\in{\mathbb{Z}}_{q}^{\ell}\end{split}$ (31)

where a (nonlinear) function
$Q^{\prime}:{\mathbb{Z}}_{q}^{\mathsf{m}}\rightarrow{\mathbb{Z}}_{q}^{\mathsf{m}}$
can be applied to the decrypted output before it is re-encrypted. See Figure
12 describing the encrypted implementation of (31). Then, a relaxed problem
assuming the “output re-encryption” can be reformulated as follows.

4

Figure 12: (a) Block diagram of the system (30). (b) Encrypted implementation
of (30) with output re-encryption.

###### Problem 2

Given the parameters $\\{F,G,H,J,x_{0}\\}$ of (4) and $\epsilon>0$, find a set
of parameters
$\\{\mathsf{F},\mathsf{G},\mathsf{H},\mathsf{J},\mathsf{z}_{0},\mathsf{R}\\}$
of integers and functions $\\{Q,Q^{\prime}\\}$ for the system (31) over
${\mathbb{Z}}_{q}$, and a function $g$, such that
$\|g(\mathsf{u}(t))-u(t)\|\leq\epsilon$, $\forall t\geq 0$. $\square$

Regarding the stated problems, we note that simply “scaling up” the parameters
$\\{F,G,H,J,x_{0}\\}$ cannot be a solution. Consider the following example

$\displaystyle\begin{split}{x(t+1)}&={-0.25\times x(t)}+1\\\ u(t)&=x(t)\\\
x(0)&=1\end{split}\qquad\rightarrow\begin{split}u(1)&={0.75},\\\
u(2)&={0.8125},\\\ u(3)&={0.796875},\\\ u(4)&={0.80078125}.\end{split}$ (32a)
To keep the precision of the parameter $0.25$ that is recursively multiplied
with the state $x(t)$, let it be scaled by $100$ and stored as an integer and
the system is represented as
$\displaystyle\begin{split}{\mathsf{z}(t+1)}&={-25\times\mathsf{z}(t)}+100^{t+1}\\\
\mathsf{u}(t)&=\mathsf{z}(t)\\\
\mathsf{z}(0)&=1\end{split}\qquad\rightarrow\begin{split}\mathsf{u}(1)&={75},\\\
\mathsf{u}(2)&={8125},\\\ \mathsf{u}(3)&={796875},\\\
\mathsf{u}(4)&={80078125},\end{split}$ (32b)

so that the output $u(t)$ is recovered as $u(t)=\mathsf{u}(t)/100^{t}$.
However, it can be seen that the size $|\mathsf{u}(t)|$ of the output
increases (exponentially) as time goes by, so that no matter how large the
modulus $q$ is chosen for the underlying space ${\mathbb{Z}}_{q}$ for the
system (30), there will be an overflow and the output will be incorrect, in a
finite time.

In general, a major issue related to the problem is recursive multiplication
of the state matrix consisting of non-integers; the state matrix $F$ of the
given controller in (4), which is recursively multiplied with the state
$x(t)$, should not be kept as $\lceil
F/\mathsf{s}\rfloor\in{\mathbb{Z}}^{\ell\ell\times\ell}$ with a scale factor
$1/\mathsf{s}>1$ to keep the precision of the decimal part. If so, the state
$\mathsf{z}(t)$ of the implemented system will be multiplied by the scaled
matrix $\lceil F/\mathsf{s}\rfloor$ together with the factor $1/\mathsf{s}>1$,
so that the size of $\mathsf{z}(t)$ (equivalently, the number of decimal
places of the state $x(t)$) will increase as time goes by, even if the norm
$\|x(t)\|$ of the state is bounded.

In this regard, from the following subsection, we first convert the state
matrix to integers without use of scaling, and then convert the rest part of
the system to integers. The methods to be introduced are presented in [60],
which will be seen as a solution to Problem 2.

####  3.2.1 Conversion of state matrix to integers

A simple way of changing the parameters of a linear system while keeping the
same input-output relation is the “similarity transformation”. With an
invertible matrix $T\in{\mathbb{Z}}^{\ell\times\ell}$, let the given
controller (4) be transformed as

$\displaystyle\begin{split}z(t+1)&=TFT^{-1}z(t)+TGy(t)\\\
u(t)&=HT^{-1}z(t)+Jy(t)\\\ z(0)&=Tx_{0}\end{split}$ (33)

which has the same input-output relation with the relation $z(t)=Tx(t)$. Then,
to convert the given state matrix $F$ to integers, one may try to find a
transformation matrix $T$ such that the state matrix
$F\in{\mathbb{R}}^{\ell\times\ell}$ consisting of non-integers is turned into
integers; i.e., $TFT^{-1}\in{\mathbb{Z}}^{\ell\times\ell}$.

However, this attempt will not be successful in general, due to the invariant
characteristics of the linear systems. If there exists a transformation $T$
such that $TFT^{-1}\in{\mathbb{Z}}^{\ell\times\ell}$, then it is obvious that
the characteristic polynomial $\det(sI_{\ell}-TFT^{-1})$ of the matrix
$TFT^{-1}$ has the coefficients as integers. Thus, from the invariance that
$\det(sI_{\ell}-TFT^{-1})=\det(sI_{\ell}-F)$ no matter what the transform $T$
is chosen, there does not exist a transformation $T$ such that
$TFT^{-1}\in{\mathbb{Z}}^{\ell\times\ell}$ as long as the given state matrix
$F$ is such that its characteristic polynomial $\det(sI_{\ell}-F)$ does not
have integer coefficients.

Then, considering that the objective of Problem 2 is to convert the given
controller into the form (31) where the output of the system can be treated as
an “auxiliary input” at the same time, we first change the state matrix using
the auxiliary input and then try to transform it to integers; let us observe
that the system (4) can be rewritten as

$\displaystyle\begin{split}x(t+1)&=(F-RH)x(t)+(G-RJ)y(t)+Ru(t)\\\
u(t)&=Hx(t)+Jy(t)\\\ x(0)&=x_{0}\end{split}$ (34)

which has the same relation from the input $y(t)$ to the output $u(t)$,
regardless of the choice of the matrix
$R\in{\mathbb{R}}^{\ell\times\mathsf{m}}$. Now, we consider the similarity
transformation for the system (34), as

$\displaystyle z(t+1)$ $\displaystyle=T(F-RH)T^{-1}z(t)+T(G-RJ)y(t)+TRu(t)$
(35a) $\displaystyle u(t)$ $\displaystyle=HT^{-1}z(t)+Jy(t)$ (35b)
$\displaystyle z(0)$ $\displaystyle=Tx_{0}$ (35c)

and try to find a transformation matrix $T$ such that the “converted” state
matrix consists of integers; that is,

$T(F-RH)T^{-1}\in{\mathbb{Z}}^{\ell\times\ell}.$

In what follows, it is proposed that the system of the form (34) can always be
converted to have the state matrix as integers. First, without loss of
generality, we can assume that the pair $(F,H)$ of the given controller (4) is
observable, i.e.,

$\mathrm{rank}\left(\begin{bmatrix}H\\\ HF\\\ \vdots\\\
HF^{\ell-1}\end{bmatrix}\right)=\ell.$

If it is not, “Kalman observable decomposition” can be considered so that the
pair $(F,H)$ can be reduced to an observable pair; an invertible matrix
$W=[W_{1}^{\top},W_{2}^{\top}]^{\top}\in{\mathbb{R}}^{\ell\times\ell}$ can
always be found such that, with
$z_{1}(t)=W_{1}x(t)\in{\mathbb{R}}^{\ell^{\prime}}$ and
$z_{2}(t)=W_{2}x(t)\in{\mathbb{R}}^{\ell-\ell^{\prime}}$ with some
$\ell^{\prime}\leq\ell$, the controller (4) can be transformed into the form

$\displaystyle z_{1}(t+1)$ $\displaystyle=F_{11}z_{1}(t)+W_{1}Gy(t)$ (36a)
$\displaystyle z_{2}(t+1)$
$\displaystyle=F_{21}z_{1}(t)+F_{22}z_{2}(t)+W_{2}Gy(t)$ (36b) $\displaystyle
u(t)$ $\displaystyle=H_{1}z_{1}(t)+Jy(t)$ (36c)

with

$WFW^{-1}=\begin{bmatrix}F_{11}&0_{\ell^{\prime}\times(\ell-\ell^{\prime})}\\\
F_{21}&F_{22}\end{bmatrix}\quad\text{and}\quad
HW^{-1}=\begin{bmatrix}H_{1}&0_{\mathsf{m}\times(\ell-\ell^{\prime})}\end{bmatrix},$

where the reduced pair $(F_{11},H_{1})$ becomes observable. Then, since the
sub-state $z_{2}(t)$ of the unobservable part does not affect the value of the
output $u(t)$ in (36c), it suffices to reduce the given controller (4) to the
subsystem (36a) with (36c) only, which is observable and has the same input-
output relation.

Now, based on the observability of the pair $(F,H)$, it is proposed that, the
matrices $R$ and $T$ can always be found such that the converted system (35)
has the state matrix as integers; let the matrix $R$ be found such that the
eigenvalues $\\{\lambda_{i}\\}_{i=1}^{\ell}$ of the matrix $F-RH$ are distinct
integers, for example. Then, by choosing the transformation matrix $T$ that
diagonalizes the matrix $F-RH$, we obtain

$T(F-RH)T^{-1}=\begin{bmatrix}\lambda_{1}&0&\cdots&0\\\
0&\lambda_{2}&\cdots&0\\\ \vdots&\vdots&\ddots&\vdots\\\
0&0&\cdots&\lambda_{\ell}\end{bmatrix}\in{\mathbb{Z}}^{\ell\times\ell},$

which is clearly a matrix consisting of integers. As a result, we have the
following lemma.

###### Lemma 1

For any observable pair $F\in{\mathbb{R}}^{\ell\times\ell}$ and
$H\in{\mathbb{R}}^{\mathsf{m}\times\ell}$, there exist matrices
$R\in{\mathbb{R}}^{\ell\times\mathsf{m}}$ and
$T\in{\mathbb{R}}^{\ell\times\ell}$ such that
$T(F-RH)T^{-1}\in{\mathbb{Z}}^{\ell\times\ell}$. $\square$

If the controller (4) is an observable single-output system, the observable
canonical form of the system can be simply used for the conversion. Indeed,
let $H\in{\mathbb{R}}^{1\times\ell}$, and let the transform matrix $T$ be
found such that the pair $(F,H)$ is transformed into the form

$TFT^{-1}=\begin{bmatrix}0&0&\cdots&0&a_{1}\\\ 1&0&\cdots&0&a_{2}\\\
0&1&\cdots&0&a_{3}\\\ \vdots&\vdots&\ddots&\vdots&\vdots\\\
0&0&\cdots&1&a_{\ell}\end{bmatrix}\in{\mathbb{R}}^{\ell\times\ell},\qquad
HT^{-1}=\begin{bmatrix}0&\cdots&0&1\end{bmatrix}\in{\mathbb{R}}^{1\times\ell}.$

Then obviously, any matrix $R\in{\mathbb{R}}^{\ell\times 1}$, given by

$R=T^{-1}\begin{bmatrix}a_{1}-k_{1}\\\ a_{2}-k_{2}\\\ \vdots\\\
a_{\ell}-k_{\ell}\end{bmatrix},\qquad k_{i}\in{\mathbb{Z}},\quad
i=0,\ldots,\ell,$

will yield the converted state matrix as integers, as

$T(F-RH)T^{-1}=\begin{bmatrix}0&0&\cdots&0&k_{1}\\\ 1&0&\cdots&0&k_{2}\\\
0&1&\cdots&0&k_{3}\\\ \vdots&\vdots&\ddots&\vdots&\vdots\\\
0&0&\cdots&1&k_{\ell}\end{bmatrix}\in{\mathbb{Z}}^{\ell\times\ell}.$

####  3.2.2 Conversion to system over ${\mathbb{Z}}$

So far, we have converted the given controller (4) to the form (35), where the
matrices $T$ and $R$ are found such that the state matrix $T(F-RH)T^{-1}$
consists of integers. Now, recalling that the overflow problem described in
the example (32) was due to the state matrix $F$ consisting of non-integers
and due to the recursive multiplication of the state matrix $\lceil
F/\mathsf{s}\rfloor\in{\mathbb{Z}}^{\ell\times\ell}$ scaled by
$1/\mathsf{s}>1$, it can be expected that such problem would not be found
because now the converted system (35) will keep the state matrix
$T(F-RH)T^{-1}$ as integers without a scaling factor (that is,
$1/\mathsf{s}=1$). In this subsection, we show how to implement the system
having the state matrix as integers, to operate over the space ${\mathbb{Z}}$
using addition and multiplication.

The task is to convert all the signals and the parameters of the system (35)
to integers using scale factors, except the state matrix which is already of
integers. Note that, any matrix $G\in{\mathbb{R}}^{\ell\times\mathsf{p}}$ (or
any vector or scalar) can be stored as integers with arbitrary precision, as
$\lceil G/\mathsf{s}\rfloor\in{\mathbb{Z}}^{\ell\times\mathsf{p}}$,
$1/\mathsf{s}>0$, because the error due to rounding can be arbitrary small as
the scale factor $1/\mathsf{s}$ tends to infinity (as $\mathsf{s}$ tends to
zero), as

$\left\|G-\mathsf{s}\left\lceil\frac{G}{\mathsf{s}}\right\rfloor\right\|\leq\frac{\mathsf{p}}{2}\cdot\mathsf{s}.$
(37)

Thus, to keep the performance of the system (35) while scaling up the non-
integer numbers therein, let $1/\mathsf{r}>0$, $1/\mathsf{s}>0$, and
$\mathsf{L}\in{\mathbb{N}}$ be scale factors, and let the factor
$\mathsf{L}/(\mathsf{r}\mathsf{s})$ be multiplied to the both sides of the
equations (35a) and (35c), and the factor
$\mathsf{L}/(\mathsf{r}\mathsf{s}^{2})$ be multiplied to the both sides of the
equation (35b), as

$\displaystyle\begin{split}\frac{\mathsf{L}\cdot
z(t+1)}{\mathsf{r}\mathsf{s}}&=T(F-RH)T^{-1}\cdot\frac{\mathsf{L}\cdot
z(t)}{\mathsf{r}\mathsf{s}}+\frac{T(G-RJ)}{\mathsf{s}}\cdot\frac{\mathsf{L}\cdot
y(t)}{\mathsf{r}}+\frac{TR}{\mathsf{s}}\cdot\frac{\mathsf{L}\cdot
u(t)}{\mathsf{r}}\\\ \frac{\mathsf{L}\cdot
u(t)}{\mathsf{r}\mathsf{s}^{2}}&=\frac{HT^{-1}}{\mathsf{s}}\cdot\frac{\mathsf{L}\cdot
z(t)}{\mathsf{r}\mathsf{s}}+\frac{J}{\mathsf{s}^{2}}\cdot\frac{\mathsf{L}\cdot
y(t)}{\mathsf{r}}\\\ \frac{\mathsf{L}\cdot
z(0)}{\mathsf{r}\mathsf{s}}&=\mathsf{L}\cdot\frac{Tx_{0}}{\mathsf{r}\mathsf{s}}.\end{split}$
(38)

Next, we take the rounding operation to the parameters and signals so that we
consider the following system

$\displaystyle\overline{z}(t+1)$
$\displaystyle=\overline{F}\cdot\overline{z}(t)+\overline{G}\cdot\overline{y}(t)+\overline{R}\cdot\mathsf{L}\cdot\left\lceil\frac{\mathsf{s}^{2}}{\mathsf{L}}\cdot\overline{u}(t)\right\rfloor,$
(39a) $\displaystyle\overline{u}(t)$
$\displaystyle=\overline{H}\cdot\overline{z}(t)+\overline{J}\cdot\overline{y}(t)$
(39b) $\displaystyle\overline{z}(0)$ $\displaystyle=\overline{z}_{0},$

with

$\displaystyle\begin{split}\overline{F}&:=T(F-RH)T^{-1},\quad\overline{G}:=\left\lceil\frac{T(G-RJ)}{\mathsf{s}}\right\rfloor,\quad\overline{R}:=\left\lceil\frac{TR}{\mathsf{s}}\right\rfloor,\\\
\overline{H}&:=\left\lceil\frac{HT^{-1}}{\mathsf{s}}\right\rfloor,\quad\overline{J}:=\left\lceil\frac{J}{\mathsf{s}^{2}}\right\rfloor,\quad\overline{y}(t):=\mathsf{L}\cdot\left\lceil\frac{y(t)}{\mathsf{r}}\right\rfloor,\quad\overline{z}_{0}:=\mathsf{L}\cdot\left\lceil\frac{Tx_{0}}{\mathsf{r}\mathsf{s}}\right\rfloor,\end{split}$
(40)

where the state $\overline{z}(t)\in{\mathbb{Z}}^{\ell}$, the input
$\overline{y}(t)\in{\mathbb{Z}}^{\mathsf{p}}$, and the output
$\overline{u}(t)\in{\mathbb{Z}}^{\mathsf{m}}$ will keep approximate values of
the state $\mathsf{L}\cdot z(t)/(\mathsf{r}\mathsf{s})$, the input
$\mathsf{L}\cdot y(t)/\mathsf{r}$, and the output $\mathsf{L}\cdot
u(t)/(\mathsf{r}\mathsf{s}^{2})$ in (38), respectively. Note that, the
constructed system (39) is defined over integers and operates using only
addition and multiplication, except the operation
$\mathsf{L}\cdot\lceil(\mathsf{s}^{2}/\mathsf{L})\cdot(~{})\rfloor$ which
“divides” the value of $\overline{u}(t)$ by the factor $1/\mathsf{s}^{2}$.

Next, we consider the performance of the system (39). Define
$\tilde{z}(t):=(\mathsf{r}\mathsf{s}/\mathsf{L})\cdot\overline{z}(t)$ and
$\tilde{u}(t):=(\mathsf{r}\mathsf{s}^{2}/\mathsf{L})\cdot\overline{u}(t)$.
Then, the system (39) can be rewritten as

$\displaystyle\begin{split}\tilde{z}(t+1)&=T(F-RH)T^{-1}\tilde{z}(t)+T(G-RJ)y(t)+TR\tilde{u}(t)+e_{z}(t)\\\
\tilde{u}(t)&=HT^{-1}\tilde{z}(t)+Jy(t)+e_{u}(t)\\\
\tilde{z}(0)&=Tx_{0}+e_{z,0}\end{split}$ (41)

where $e_{z}(t)\in{\mathbb{R}}^{\ell}$,
$e_{u}(t)\in{\mathbb{R}}^{\mathsf{m}}$, and $e_{z,0}\in{\mathbb{R}}^{\ell}$
denote the error due to the rounding (quantization), given by

$\displaystyle\begin{split}e_{z}(t)&=\left(T(G-RJ)y(t)-\left(\mathsf{s}\left\lceil\frac{T(G-RJ)}{\mathsf{s}}\right\rfloor\right)\cdot\left(\mathsf{r}\left\lceil\frac{y(t)}{\mathsf{r}}\right\rfloor\right)\right)+\left(TR\tilde{u}(t)-\left(\mathsf{s}\left\lceil\frac{TR}{\mathsf{s}}\right\rfloor\right)\cdot\left(\mathsf{r}\left\lceil\frac{\tilde{u}(t)}{\mathsf{r}}\right\rfloor\right)\right)\\\
e_{u}(t)&=\left(HT^{-1}-\mathsf{s}\left\lceil\frac{HT^{-1}}{\mathsf{s}}\right\rfloor\right)\cdot\tilde{z}(t)+\left(Jy(t)-\left(\mathsf{s}^{2}\left\lceil\frac{J}{\mathsf{s}^{2}}\right\rfloor\right)\cdot\left(\mathsf{r}\left\lceil\frac{y(t)}{\mathsf{r}}\right\rfloor\right)\right)\\\
e_{z,0}&=Tx_{0}-\mathsf{r}\mathsf{s}\left\lceil\frac{Tx_{0}}{\mathsf{r}\mathsf{s}}\right\rfloor.\end{split}$
(42)

We note that the factor $\mathsf{L}$ does not affect the values of
$\\{e_{z}(t),e_{u}(t),e_{z,0}\\}$, so does nothing about the performance of
(41); as an auxiliary scale factor, it will be used in Section 3.3, to deal
with “error growth” of the LWE-based cryptosystem. One may suppose
$\mathsf{L}=1$ in this subsection for simplicity.

Then, the performance of the implemented system (39) can be identified with
the given controller model (4) with presence of perturbation; from (41), it
can be easily verified that the state $\tilde{x}(t):=T^{-1}\tilde{z}(t)$ and
the output $\tilde{u}(t)$ obey

$\displaystyle\begin{split}\tilde{x}(t+1)&=F\tilde{x}(t)+Gy(t)+e_{x}(t)\\\
\tilde{u}(t)&=H\tilde{x}(t)+Jy(t)+e_{u}(t)\\\
\tilde{x}(0)&=x_{0}+e_{0},\end{split}$ (43)

where the errors $e_{x}(t)\in{\mathbb{R}}^{\ell}$ and
$e_{0}\in{\mathbb{R}}^{\ell}$ are given by

$e_{x}(t)=T^{-1}e_{z}(t)+TRe_{u}(t),\qquad e_{0}=T^{-1}e_{z,0}.$ (44)

Compared to the given controller (4) without considering the errors, note that
$\tilde{x}(t)=x(t)$ and $\tilde{u}(t)=u(t)$, $\forall t\geq 0$, if $e_{0}=0$,
$e_{x}(t)=0$, and $e_{u}(t)$, $\forall t\geq 0$. The result is that the
performance of (39) is equivalent to that of (43), with the relation

$\tilde{x}(t)=\frac{\mathsf{r}\mathsf{s}}{\mathsf{L}}\cdot
T^{-1}\overline{z}(t),\qquad\tilde{u}(t)=\frac{\mathsf{r}\mathsf{s}^{2}}{\mathsf{L}}\cdot\overline{u}(t).$
(45)

In what follows, we discuss the effect of the perturbations
$\\{e_{x}(t),e_{u}(t),e_{0}\\}$ on the performance of the systems (39) and
(43). The claim is that, if the sizes of the errors
$\\{e_{x}(t),e_{u}(t),e_{0}\\}$ can be made arbitrarily small by appropriate
choice of the parameters $\\{\mathsf{r},\mathsf{s}\\}$, and if the
trajectories $\tilde{x}(t)$ and $\tilde{u}(t)$ of (43) are “stable” with
respect to the perturbations $\\{e_{x}(t),e_{u}(t),e_{0}\\}$, then the
difference of the trajectories $\tilde{x}(t)$ and $\tilde{u}(t)$ from those of
the “ideal” trajectories $x(t)$ and $u(t)$ can be made arbitrarily small by
the choice of $\\{\mathsf{r},\mathsf{s}\\}$. And, this will ensure that the
performance of the system (39) is “practically equivalent” to the given
controller (4). In this regard, we make the following assumption.

###### Assumption 1

Given the controller (4), the perturbed model (43) satisfies the following:
There exists a function $\delta(\epsilon)>0$ such that for any $\epsilon>0$,
if

$\|e_{0}\|\leq\delta(\epsilon),~{}~{}\|e_{x}(t)\|\leq\delta(\epsilon),~{}~{}\text{and}~{}~{}\|e_{u}(t)\|\leq\delta(\epsilon),~{}~{}\forall
t\geq 0,$ (46)

then $\|\tilde{x}(t)-x(t)\|\leq\epsilon$ and
$\|\tilde{u}(t)-u(t)\|\leq\epsilon$ hold for all $t\geq 0$. $\square$

Obviously, if the given controller (4) itself is stable (i.e., the state
matrix $F$ is Schur stable), then the condition of Assumption 1 is implied.
But, we note that a system, in which the condition of Assumption 1 holds, may
not be stable by itself (the matrix $F$ may not be Schur stable). Typically,
if the system (43) is a part of a closed-loop system, and if it is stable with
respect to the perturbations $\\{e_{x}(t),e_{u}(t),e_{0}\\}$, then the
condition of Assumption 1 will hold. In such cases, rigorously, the input
$y(t)$ of the system may also be affected by the perturbations, but we omit
such arguments for simplicity (See [60, Section II.B]).

Finally, the following lemma states that the performance of the converted
controller (39) operating over integers is guaranteed, provided that the
trajectories of the given controller is stable with respect to the
quantization errors $\\{e_{x}(t),e_{u}(t),e_{0}\\}$. For a more rigorous proof
under a more general setting, see [60, Proposition 6].

###### Lemma 2

For any $\epsilon>0$, under Assumption 1, there exist $\mathsf{r}^{\prime}>0$
and $\mathsf{s}^{\prime}>0$ such that for any
$\mathsf{r}<\mathsf{r}^{\prime}$, $\mathsf{s}<\mathsf{s}^{\prime}$, and
$\mathsf{L}\in{\mathbb{N}}$, the controller (39) implemented over
${\mathbb{Z}}$ guarantees that $\|(\mathsf{r}\mathsf{s}/\mathsf{L})\cdot
T^{-1}\overline{z}(t)-x(t)\|\leq\epsilon$ and
$\|(\mathsf{r}\mathsf{s}^{2}/\mathsf{L})\cdot\overline{u}(t)-u(t)\|\leq\epsilon$
hold, $\forall t\geq 0$. $\square$

Sketch of Proof: Recall the relation (45) between the system (39) and (43),
with the perturbations $\\{e_{x}(t),e_{u}(t),e_{0}\\}$ determined by (42) and
(44). Given $\epsilon>0$ and $\delta(\epsilon)$, we show that
$\mathsf{r}^{\prime}$ and $\mathsf{s}^{\prime}$ can be chosen such that
$\mathsf{r}<\mathsf{r}^{\prime}$ and $\mathsf{s}<\mathsf{s}^{\prime}$ ensure
that (46) holds. Observe that, for any signal
$y(t)\in{\mathbb{R}}^{\mathsf{p}}$ and
$G\in{\mathbb{R}}^{\ell\times\mathsf{p}}$, some constants $\theta_{1}$ and
$\theta_{2}$ can be found such that

$\displaystyle\left\|Gy(t)-\left(\mathsf{s}\left\lceil\frac{G}{\mathsf{s}}\right\rfloor\right)\cdot\left(\mathsf{r}\left\lceil\frac{y(t)}{\mathsf{r}}\right\rfloor\right)\right\|$
$\displaystyle\leq\frac{\|G\|}{2}\cdot\mathsf{r}+\frac{\mathsf{p}}{2}\cdot\|y(t)\|\cdot\mathsf{s}+\frac{\mathsf{p}}{4}\cdot\mathsf{r}\mathsf{s}$
$\displaystyle\leq\theta_{1}\cdot\max\\{\|y(t)\|,\theta_{2}\\}\cdot\max\\{\mathsf{r},\mathsf{s},\mathsf{r}\mathsf{s}\\}.$

Then, from (42) and (44), it can be verified that

$\displaystyle\max\\{\|e_{x}(t)\|,\|e_{u}(t)\|,\|e_{0}\|\\}$
$\displaystyle\leq\theta^{\prime}_{1}\cdot\max\\{\|y(t)\|,\|\tilde{x}(t)\|,\|\tilde{u}(t)\|,\theta^{\prime}_{2}\\}\cdot\max\\{\mathsf{r},\mathsf{s},\mathsf{r}\mathsf{s},\mathsf{s}^{2},\mathsf{r}\mathsf{s}^{2}\\}$
$\displaystyle=:\alpha(\|y(t)\|,\|\tilde{x}(t)\|,\|\tilde{u}(t)\|,\mathsf{r},\mathsf{s})$
(47)

with some constants $\theta_{1}^{\prime}$ and $\theta_{2}^{\prime}$. From the
boundedness of the signals of (4), let
$\max\\{\|y(t)\|,\|x(t)\|,\|u(t)\|\\}\leq M$ with some $M>0$. Then, since
$\mathsf{r}=0$ and $\mathsf{s}=0$ implies $\alpha=0$ in (47), we can choose
$\mathsf{r}^{\prime}>0$ and $\mathsf{s}^{\prime}>0$ such that

$\alpha(M,M+\epsilon,M+\epsilon,\mathsf{r}^{\prime},\mathsf{s}^{\prime})\leq\delta(\epsilon).$

As a consequence, by Assumption 1, it can be proved that any
$\mathsf{r}<\mathsf{r}^{\prime}$ and $\mathsf{s}<\mathsf{s}^{\prime}$ ensure
that

$\|\tilde{x}(t)-x(t)\|\leq\epsilon,\quad\|\tilde{u}(t)-u(t)\|\leq\epsilon,\quad\|\tilde{x}(t)\|\leq
M+\epsilon,\quad\|\tilde{u}(t)\|\leq M+\epsilon,$

for all $t\geq 0$, using mathematical induction. It completes the proof.
$\blacksquare$

####  3.2.3 Conversion to system over ${\mathbb{Z}}_{q}$

All the parameters and the signals of the given controller (4) are now
converted to integers, in the controller (39). Recalling the goal of Problem
2, we map the parameters and signals of (39) to the set
${\mathbb{Z}}_{q}=\\{0,1,\ldots,q-1\\}$ of messages for encryption, and
further convert the system (39) to the form (31), so that it can be directly
encrypted using the result of Proposition 3.

First of all, we note that, given any dynamic system of the form

$\displaystyle\begin{split}\overline{x}(t+1)&=\overline{F}^{\prime}\overline{x}(t)+\overline{G}^{\prime}\overline{y}(t),\\\
\overline{u}^{\prime}(t)&=\overline{H}^{\prime}\overline{x}(t)+\overline{J}^{\prime}\overline{y}(t),\\\
\overline{x}(0)&=\overline{x}_{0},\end{split}$ (48)

where all the signals and parameters are of integers, the conversion to a
system over ${\mathbb{Z}}_{q}$ itself is simple; just by taking the modulo
operation to the parameters, the signals, and the computation outcomes of
(48), it can be converted as

$\displaystyle\begin{split}\mathsf{x}(t+1)&=\mathsf{F}^{\prime}\mathsf{x}(t)+\mathsf{G}^{\prime}\mathsf{y}(t)\mod
q,\\\
\mathsf{u}^{\prime}(t)&=\mathsf{H}^{\prime}\mathsf{x}(t)+\mathsf{J}^{\prime}\mathsf{y}(t)\mod
q,\\\ \mathsf{x}(0)&=\mathsf{x}_{0},\end{split}$ (49)

where

$\displaystyle\begin{split}\mathsf{F}^{\prime}&=\overline{F}^{\prime}\mod
q,\quad\mathsf{G}^{\prime}=\overline{G}^{\prime}\mod
q,\quad\mathsf{H}^{\prime}=\overline{H}^{\prime}\mod
q,\quad\mathsf{J}^{\prime}=\overline{J}^{\prime}\mod q,\\\
\mathsf{y}(t)&=\overline{y}(t)\mod q,\quad\mathsf{x}_{0}=\overline{x}_{0}\mod
q.\end{split}$ (50)

Since the modulo operation is compatible with addition and multiplication, the
conversion (49) ensures that

$\mathsf{u}^{\prime}(t)=\overline{u}^{\prime}(t)\mod q,\quad\forall t\geq 0.$
(51)

Conversely, to recover the output $\overline{u}^{\prime}(t)$ of arbitrary
integers from the “projected” output $\mathsf{u}^{\prime}(t)$ consisting of
elements of ${\mathbb{Z}}_{q}$, the “size” $q$ of the space ${\mathbb{Z}}_{q}$
should be chosen appropriately. A sufficient condition is given in the
following proposition; the original output $\overline{\mathsf{u}}^{\prime}(t)$
can be recovered from $\mathsf{u}^{\prime}(t)$ using the biased modulo
operation defined in (1), if the size of the space ${\mathbb{Z}}_{q}$ “covers”
the range of the output $\overline{u}^{\prime}(t)$.

###### Proposition 4

Consider two systems (48) and (49) with (50). Suppose that the output
$\overline{u}^{\prime}(t)=\mathrm{col}\\{\overline{u}_{i}^{\prime}(t)\\}_{i=1}^{\mathsf{m}^{\prime}}$,
$\mathsf{m}^{\prime}\in{\mathbb{N}}$, of (48) be bounded as

$\overline{u}_{i}^{\min}\leq\overline{u}^{\prime}_{i}(t)\leq\overline{u}_{i}^{\max},\qquad\forall
t\geq 0,\quad\forall i=1,\ldots,\mathsf{m}^{\prime},$ (52)

with some constants
$\\{\overline{u}_{i}^{\min}\\}_{i=1}^{\mathsf{m}^{\prime}}$ and
$\\{\overline{u}_{i}^{\max}\\}_{i=1}^{\mathsf{m}^{\prime}}$. If

$q\geq\overline{u}_{i}^{\max}-\overline{u}_{i}^{\min}+1,\qquad\forall
i=1,\ldots,\mathsf{m}^{\prime},$ (53)

then
$\overline{u}^{\prime}(t)=\mathsf{u}^{\prime}(t)~{}~{}\mathrm{mod}\,(q,\mathrm{col}\\{\overline{u}_{i}^{\min}\\}_{i=1}^{\mathsf{m}^{\prime}})$
holds for all $t\geq 0$. $\square$

Proof: Let the $i$-th component of
$\mathsf{u}^{\prime}(t)~{}~{}\mathrm{mod}\,(q,\mathrm{col}\\{\overline{u}_{i}^{\min}\\}_{i=1}^{\mathsf{m}^{\prime}})$
be denoted by $\overline{u}^{\prime\prime}_{i}(t)$. Note that the operations
$\mathrm{mod}\,q$ and
$\mathrm{mod}\,(q,\mathrm{col}\\{\overline{u}_{i}^{\min}\\}_{i=1}^{\mathsf{m}^{\prime}})$
add some multiples of $q$ to the components only. Then, from (51), it is clear
that $\overline{u}_{i}^{\prime}(t)=\overline{u}_{i}^{\prime\prime}(t)+kq$ with
some $k\in{\mathbb{Z}}$. Now, the definition (1) ensures that
$\overline{u}_{i}^{\min}\leq\overline{u}_{i}^{\prime\prime}(t)<\overline{u}_{i}^{\min}+q$,
and (52) and (53) ensure that
$\overline{u}_{i}^{\min}\leq\overline{u}^{\prime}_{i}(t)<\overline{u}_{i}^{\min}+q$.
Hence, $k=0$ and
$\overline{u}_{i}^{\prime\prime}(t)=\overline{u}_{i}^{\prime}(t)$. It
completes the proof. $\blacksquare$

Based on this observation, we convert the system (39) to the form (31) over
${\mathbb{Z}}_{q}$, and determine the parameters and functions therein, to
find a solution to Problem 2. To determine the modulus $q$ first, we calculate
the range of the output $\overline{u}(t)$ of (39); from the boundedness of the
output $u(t)=\mathrm{col}\\{u_{i}(t)\\}_{i=1}^{\mathsf{m}}$ of (4), let some
constants $\\{u_{i}^{\min}\\}_{i=1}^{\mathsf{m}}$ and
$\\{u_{i}^{\max}\\}_{i=1}^{\mathsf{m}}$ be found such that

$u_{i}^{\min}\leq u_{i}(t)\leq u_{i}^{\max},\qquad\forall
i=1,\ldots,\mathsf{m},\quad\forall t\geq 0.$ (54)

Then, given $\epsilon>0$ from Problem 2, the design of (39) is supposed to
ensure that the output
$\overline{u}(t)=\mathrm{col}\\{\overline{u}_{i}(t)\\}_{i=1}^{\mathsf{m}}$ is
bounded as
$\|(\mathsf{r}\mathsf{s}^{2}/\mathsf{L})\cdot\overline{u}(t)-u(t)\|\leq\epsilon$,
which implies

$\mathsf{L}\cdot\frac{u_{i}^{\min}-\epsilon}{\mathsf{r}\mathsf{s}^{2}}\leq\overline{u}_{i}(t)\leq\mathsf{L}\cdot\frac{u_{i}^{\max}+\epsilon}{\mathsf{r}\mathsf{s}^{2}},\quad\forall
i=1,\ldots,\mathsf{m}.$ (55)

Now, considering the condition (53), we choose the modulus $q$ such that

$q\geq\max_{i=1,\ldots,\mathsf{m}}\left\\{\mathsf{L}\cdot\frac{u_{i}^{\max}-u_{i}^{\min}+2\epsilon}{\mathsf{r}\mathsf{s}^{2}}\right\\}+1.$
(56)

Then, even if the operation $\mathrm{mod}\,q$ is taken to the output
$\overline{u}(t)$, as
$\mathsf{u}^{\prime}(t)=\overline{u}(t)~{}\mathrm{mod}\,q$, the value of
$\overline{u}(t)$ can be recovered from $\mathsf{u}^{\prime}(t)$, as

$\overline{u}(t)=\mathsf{u}^{\prime}(t)\mod\left(q,\mathrm{col}\left\\{\mathsf{L}\cdot\frac{u_{i}^{\min}-\epsilon}{\mathsf{r}\mathsf{s}^{2}}\right\\}_{i=1}^{\mathsf{m}}\right),$

and a real-valued signal approximate to the real output
$u(t)\approx(\mathsf{r}\mathsf{s}^{2}/\mathsf{L})\cdot\overline{u}(t)$ can
also be computed from $\mathsf{u}^{\prime}(t)$, with a function
$g:{\mathbb{Z}}_{q}^{\mathsf{m}}\rightarrow{\mathbb{R}}^{\mathsf{m}}$ defined
as

$g(\mathsf{u}^{\prime}(t)):=\frac{\mathsf{r}\mathsf{s}^{2}}{\mathsf{L}}\cdot\left(\mathsf{u}^{\prime}(t)\mod\left(q,\mathrm{col}\left\\{\mathsf{L}\cdot\frac{u_{i}^{\min}-\epsilon}{\mathsf{r}\mathsf{s}^{2}}\right\\}_{i=1}^{\mathsf{m}}\right)\right).$

Finally, we convert the system (39) to a system over ${\mathbb{Z}}_{q}$, by
simply taking the modulo operation, as

$\displaystyle\mathsf{z}(t+1)$
$\displaystyle=\mathsf{F}\cdot\mathsf{z}(t)+\mathsf{G}\cdot\mathsf{y}(t)+\mathsf{R}\cdot
Q^{\prime}(\mathsf{u}(t))\mod q$ (57a) $\displaystyle\mathsf{u}(t)$
$\displaystyle=\mathsf{H}\cdot\mathsf{z}(t)+\mathsf{J}\cdot\mathsf{y}(t)\mod
q$ (57b) $\displaystyle\mathsf{z}(0)$ $\displaystyle=\mathsf{z}_{0}$

with

$\displaystyle\begin{split}\mathsf{F}&=\overline{F}\mod
q,\quad\mathsf{G}=\overline{G}\mod q,\quad\mathsf{R}=\overline{R}\mod
q,\quad\mathsf{y}(t)=\overline{y}(t)\mod q,\\\ \mathsf{H}&=\overline{H}\mod
q,\quad\mathsf{J}=\overline{J}\mod q,\quad\mathsf{z}_{0}=\overline{z}_{0}\mod
q,\end{split}$ (58)

where the term
$\mathsf{L}\cdot\lceil(\mathsf{s}^{2}/\mathsf{L})\cdot\overline{u}(t)\rfloor$
in (39) is replaced with the term $Q^{\prime}(\mathsf{u}(t))$, with a function
$Q^{\prime}:{\mathbb{Z}}_{q}^{\mathsf{m}}\rightarrow{\mathbb{Z}}_{q}^{\mathsf{m}}$
defined as

$Q^{\prime}(\mathsf{u}(t)):=\mathsf{L}\cdot\left\lceil\frac{\mathsf{s}^{2}}{\mathsf{L}}\cdot\left(\mathsf{u}(t)\mod\left(q,\mathrm{col}\left\\{\mathsf{L}\cdot\frac{u_{i}^{\min}-\epsilon}{\mathsf{r}\mathsf{s}^{2}}\right\\}_{i=1}^{\mathsf{m}}\right)\right)\right\rfloor\mod
q.$ (59)

Note that, since the operation
$\mathsf{L}\cdot\lceil(\mathsf{s}^{2}/\mathsf{L})\cdot\overline{u}(t)\rfloor$
for $\overline{u}(t)$ is not compatible with the modulo operation, in (59),
the value of $\overline{u}(t)$ is first computed from $\mathsf{u}(t)$, and
then the operation is applied. And, note that, with

$\mathsf{y}(t)=Q(y(t)):=\mathsf{L}\cdot\left\lceil\frac{y(t)}{\mathsf{r}}\right\rfloor~{}~{}\mathrm{mod}~{}q,$

the constructed system (57) takes the same form that Problem 2 considers.

As the end result of Section 3.2, and as a solution to Problem 2, the
following theorem shows that the performance of the implemented system (57),
which operates based on modular arithmetic over the space ${\mathbb{Z}}_{q}$,
can be arbitrarily close to that of the given system (4), by increasing the
scale factors $1/\mathsf{r}$ and $1/\mathsf{s}$, regardless of the factor
$\mathsf{L}$.

###### Theorem 1

Given any controller (4) and $\epsilon>0$, under Assumption 1, there exist
$\mathsf{r}^{\prime}>0$ and $\mathsf{s}^{\prime}>0$ such that for any
$\mathsf{r}<\mathsf{r}^{\prime}$, $\mathsf{s}<\mathsf{s}^{\prime}$, and
$\mathsf{L}\in{\mathbb{N}}$, the controller (57) implemented over
${\mathbb{Z}}_{q}$ with (56) guarantees
$\|g(\mathsf{u}(t))-u(t)\|\leq\epsilon$, $\forall t\geq 0$.

Proof: Consider the system (39) over ${\mathbb{Z}}$ as an auxiliary system.
Thanks to Lemma 2, we choose $\mathsf{r}^{\prime}$ and $\mathsf{s}^{\prime}$
such that any $\mathsf{r}<\mathsf{r}^{\prime}$ and
$\mathsf{s}<\mathsf{s}^{\prime}$ ensure that
$\|(\mathsf{r}\mathsf{s}^{2}/\mathsf{L})\cdot\overline{u}(t)-u(t)\|\leq\epsilon$,
$\forall t\geq 0$. By the boundedness of the output $u(t)$ as (54) with the
constants $\\{u_{i}^{\min},u_{i}^{\max}\\}_{i=1}^{\mathsf{m}}$, it follows
that (55) holds. Now, it is enough to show that

$\overline{u}(t)=\left(\mathsf{u}(t)\mod\left(q,\mathrm{col}\left\\{\mathsf{L}\cdot\frac{u_{i}^{\min}-\epsilon}{\mathsf{r}\mathsf{s}^{2}}\right\\}_{i=1}^{\mathsf{m}}\right)\right)$
(60)

for all $t\geq 0$. Note that
$\mathsf{y}(t)=\overline{y}(t)~{}\mathrm{mod}\,q$, $\forall t\geq 0$, and
$\mathsf{z}_{0}=\overline{z}_{0}~{}\mathrm{mod}\,q$, so, from (39b) and (57b),
it follows that $\mathsf{u}(0)=\overline{u}(0)~{}\mod\,q$. Now, suppose that
$\mathsf{u}(\tau)=\overline{u}(\tau)~{}\mod\,q$ for some $\tau\geq 0$. Then,
the condition (56) ensures that (60) holds for $t=\tau$, which can be proved
analogously to the proof of Proposition 4. This is followed by
$Q^{\prime}(\mathsf{u}(\tau))=\mathsf{L}\cdot\lceil(\mathsf{s}^{2}/\mathsf{L})\cdot(\overline{u}(\tau))\rfloor$,
so that it can be easily verified that
$\mathsf{z}(\tau+1)=\overline{z}(\tau+1)~{}\mathrm{mod}\,q$, by comparing
(39a) and (57a). And, from (39b) and (57b), it is followed by
$\mathsf{u}(\tau+1)=\overline{u}(\tau+1)~{}\mod\,q$. Hence, the proof is
completed. $\blacksquare$

The result of Theorem 1 can be summarized as follows. First of all, from the
example in (32), it has been observed that linear systems having the state
matrix as non-integers cannot continue the encrypted operation for an infinite
time horizon, because of the limitation of homomorphic encryption. Then, based
on the assumption that the encrypted controller can receive a re-encrypted
signal of its output, Lemma 1 has converted the state matrix to integers in
(35), while keeping the same relation from the input $y(t)$ to the output
$u(t)$. Next, the quantization parameters $\mathsf{r}$ and $\mathsf{s}$ have
been introduced for the rest controller matrices and signals. And, Lemma 2 and
Theorem 1 showed that linear systems having the state matrix as integers can
be converted to operate over ${\mathbb{Z}}_{q}$, based on modular addition and
multiplication, so that they can be implemented over encrypted data. The
performance is guaranteed and its error can be made arbitrarily small, as long
as the modulus $q$ for the space ${\mathbb{Z}}_{q}$ is chosen as (56), so that
it covers the range of the output.

A follow-up result proposing a solution to Problem 1 can be found in [61],
where the parameters $\\{\mathsf{F},\mathsf{G},\mathsf{H},\mathsf{J}\\}$ are
found as time-varying matrices consisting of integers.

###  3.3 Encrypted dynamic system and controlled error growth

Finally, we combine the GSW-LWE cryptosystem (described in Section 3.1) to the
implemented controller (57) over ${\mathbb{Z}}_{q}$ (constructed in Section
3.2), and discuss the result.

Thanks to Proposition 3 and Theorem 1, the result is straightforward; let the
matrices of the controller (57) be encrypted using the GSW encryption
$\mathsf{Enc}^{\prime}:{\mathbb{Z}}_{q}\rightarrow{\mathbb{Z}}_{q}^{\mathfrak{n}\times
d\mathfrak{n}}$ component-wisely, as

$\displaystyle\mathbf{F}:=\mathsf{Enc}^{\prime}(\mathsf{F}),\quad\mathbf{G}:=\mathsf{Enc}^{\prime}(\mathsf{G}),\quad\mathbf{R}:=\mathsf{Enc}^{\prime}(\mathsf{R}),\quad\mathbf{H}:=\mathsf{Enc}^{\prime}(\mathsf{H}),\quad\mathbf{J}:=\mathsf{Enc}^{\prime}(\mathsf{J}),$

and let the initial value $\mathsf{z}_{0}\in{\mathbb{Z}}_{q}^{\ell}$ of the
controller state and the controller input $y(t)\in{\mathbb{R}}^{\mathsf{p}}$
be quantized using the function
$Q:{\mathbb{R}}^{\mathsf{p}}\rightarrow{\mathbb{Z}}_{q}^{\mathsf{p}}$ and
encrypted using the LWE-based encryption
$\mathsf{Enc}:{\mathbb{Z}}_{q}\rightarrow{\mathbb{Z}}_{q}^{\mathfrak{n}}$,
component-wisely, as

$\mathbf{z}_{0}:=\mathsf{Enc}(\mathsf{z}_{0}),\qquad\mathbf{y}(t):=\mathsf{Enc}(Q(y(t))).$

Then, the encrypted controller is constructed as

$\displaystyle\begin{split}\mathbf{z}(t+1)&=\mathbf{F}\cdot
D(\mathbf{z}(t))+\mathbf{G}\cdot D(\mathbf{y}(t))+\mathbf{R}\cdot
D(\mathbf{u}^{\prime}(t))\mod q\\\ \mathbf{u}(t)&=\mathbf{H}\cdot
D(\mathbf{z}(t))+\mathbf{J}\cdot D(\mathbf{y}(t))\mod q\\\
\mathbf{z}(0)&=\mathbf{z}_{0}\end{split}$ (61)

where $\mathbf{z}(t)\in{\mathbb{Z}}_{q}^{\ell\mathfrak{n}}$ and
$\mathbf{u}(t)\in{\mathbb{Z}}_{q}^{\mathsf{m}\mathfrak{n}}$ are the encrypted
state and output, respectively, and
$\mathbf{u}^{\prime}(t)\in{\mathbb{Z}}_{q}^{\mathsf{m}\mathfrak{n}}$ is the
re-encrypted signal of the output $\mathbf{u}(t)$ with the function
$Q^{\prime}:{\mathbb{Z}}_{q}^{\mathsf{m}}\rightarrow{\mathbb{Z}}_{q}^{\mathsf{m}}$,
defined as

$\mathbf{u}^{\prime}(t):=\mathsf{Enc}(Q^{\prime}(\mathsf{Dec}(\mathbf{u}(t)))).$
(62)

Note that the operation of the encrypted controller (61) coincides with the
description of Figure 12.

From now on, we discuss the effect of the “injected errors” of the
cryptosystem, which has been seen in Proposition 3. Recall that, in Corollary
1, the factor $\mathsf{L}$ has been used for scaling up the messages, in order
to reduce the effect of the errors. For this purpose, in fact, all the signals
of the systems (39) and (57) have already been “scaled up by $\mathsf{L}$,
although it did nothing about the performance in the previous subsection.

Let us consider the performance of the controller (61); let the decryption
$\mathsf{Dec}$ be taken to both sides of (61). Analogously to Proposition 3,
the decrypted state
$\tilde{\mathsf{z}}(t):=\mathsf{Dec}(\mathbf{z}(t))\in{\mathbb{Z}}_{q}^{\ell}$
and the decrypted output $\tilde{\mathsf{u}}(t):=\mathsf{Dec}(\mathbf{u}(t))$
will obey

$\displaystyle\begin{split}\tilde{\mathsf{z}}(t+1)&=\mathsf{F}\cdot\tilde{\mathsf{z}}(t)+\mathsf{G}\cdot(Q(y(t))+\Delta_{\mathsf{y}}(t))+\mathsf{R}\cdot(Q^{\prime}(\tilde{\mathsf{u}}(t))+\Delta_{\mathsf{u}^{\prime}}(t))+\Delta_{\mathsf{z}}(t)\mod
q\\\
\tilde{\mathsf{u}}(t)&=\mathsf{H}\cdot\tilde{\mathsf{z}}(t)+\mathsf{J}(Q(y(t))+\Delta_{\mathsf{y}}(t))+\Delta_{\mathsf{u}}(t)\mod
q\\\ \tilde{\mathsf{z}}(0)&=\mathsf{z}_{0}+\Delta_{0}\mod q\end{split}$ (63)

with some $\Delta_{\mathsf{y}}(t)\in{\mathbb{Z}}^{\mathsf{p}}$,
$\Delta_{\mathsf{u}^{\prime}}(t)\in{\mathbb{Z}}^{\mathsf{m}}$,
$\Delta_{\mathsf{z}}(t)\in{\mathbb{Z}}^{\ell}$,
$\Delta_{\mathsf{u}}(t)\in{\mathbb{Z}}^{\mathsf{m}}$, and
$\Delta_{0}\in{\mathbb{Z}}^{\mathsf{m}}$ such that

$\|\Delta_{\mathsf{y}}(t)\|\leq
n_{0}\sigma,\qquad\|\Delta_{\mathsf{u}^{\prime}}(t)\|\leq
n_{0}\sigma,\qquad\|\Delta_{\mathsf{z}}(t)\|\leq(\ell+\mathsf{p})\Delta_{\mathsf{Mult}},\qquad\|\Delta_{\mathsf{u}}(t)\|\leq(\ell+\mathsf{p})\Delta_{\mathsf{Mult}},\qquad\|\Delta_{0}\|\leq
n_{0}\sigma.$

To make use of the results of Theorem 1 and Lemma 2, we consider an auxiliary
system defined over ${\mathbb{Z}}$, as

$\displaystyle\begin{split}\overline{z}(t+1)&=\overline{F}\cdot\overline{z}(t)+\overline{G}\cdot(\overline{y}(t))+\Delta_{\mathsf{y}}(t))+\overline{R}\cdot\left(\mathsf{L}\cdot\left\lceil\frac{\mathsf{s}^{2}}{\mathsf{L}}\cdot\overline{u}(t)\right\rfloor+\Delta_{\mathsf{u}^{\prime}}(t)\right)+\Delta_{\mathsf{z}}(t)\\\
\overline{u}(t)&=\overline{H}\cdot\overline{z}(t)+\mathsf{J}(\overline{y}(t)+\Delta_{\mathsf{y}}(t))+\Delta_{\mathsf{u}}(t)\\\
\overline{z}(0)&=\overline{z}_{0}+\Delta_{0}.\end{split}$ (64)

Then, analogously to Lemma 2, it can be verified that the state $\tilde{x}(t)$
and the output $\tilde{u}(t)$ defined as (45) will obey

$\displaystyle\begin{split}\tilde{x}(t+1)&=F\tilde{x}(t)+Gy(t)+e_{x}^{\prime}(t)\\\
\tilde{u}(t)&=H\tilde{x}(t)+Jy(t)+e_{u}^{\prime}(t)\\\
\tilde{x}(0)&=e_{0}^{\prime}\end{split}$ (65)

where the errors $\\{e_{x}^{\prime}(t),e_{u}^{\prime}(t),e_{0}^{\prime}\\}$
are determined as

$\displaystyle e_{x}^{\prime}(t)$
$\displaystyle=e_{x}(t)+\Delta_{x}^{\mathsf{L}}(t):=e_{x}(t)+\frac{\mathsf{r}\mathsf{s}\cdot
T^{-1}\cdot(\overline{G}\Delta_{\mathsf{y}}(t)+\overline{R}\Delta_{\mathsf{u}^{\prime}}(t)+\Delta_{z}(t))}{\mathsf{L}}+\frac{\mathsf{r}\mathsf{s}^{2}\cdot
TR(\overline{J}\Delta_{\mathsf{y}}(t)+\Delta_{\mathsf{u}}(t))}{\mathsf{L}}$
$\displaystyle e_{u}^{\prime}(t)$
$\displaystyle=e_{u}(t)+\Delta_{u}^{\mathsf{L}}(t):=e_{u}(t)+\frac{\mathsf{r}\mathsf{s}^{2}\cdot(\overline{J}\Delta_{\mathsf{y}}(t)+\Delta_{\mathsf{u}}(t))}{\mathsf{L}}$
$\displaystyle e_{0}^{\prime}$
$\displaystyle=e_{0}+\Delta_{0}^{\mathsf{L}}:=e_{0}+\frac{\mathsf{r}\mathsf{s}\cdot
T^{-1}\cdot\Delta_{0}}{\mathsf{L}},$

where $\\{e_{x}(t),e_{u}(t),e_{0}\\}$ are the same quantization errors defined
in (42) and (44). Note that
$\\{\Delta_{x}^{\mathsf{L}}(t),\Delta_{u}^{\mathsf{L}}(t),\Delta_{0}^{\mathsf{L}}\\}$
are bounded as

$\displaystyle\max\\{\|\Delta_{x}^{\mathsf{L}}(t)\|,\|\Delta_{u}^{\mathsf{L}}(t)\|,\|\Delta_{0}^{\mathsf{L}}\|\\}$
$\displaystyle\leq\frac{\mathsf{r}}{\mathsf{L}}\cdot\max\\{\|T^{-1}\|,\|TR\|,1\\}\cdot((\max\\{\|G\|+\|R\|,\|J\|\\}+1)n_{0}\sigma+(\ell+\mathsf{p})\Delta_{\mathsf{Mult}})$
$\displaystyle=:\beta(\mathsf{r},\mathsf{L})$

Now, in the following theorem, we prove that the performance of the controller
(61) is the same with that of (65), where the errors
$\\{e_{x}^{\prime}(t),e_{u}^{\prime}(t),e_{0}^{\prime}\\}$ consist of the
errors $\\{e_{x}(t),e_{u}(t),e_{0}\\}$ due to quantization, and the rest due
to error injection of the cryptosystem. Since only the signals are scaled by
$\mathsf{L}\in{\mathbb{N}}$ before encryption and the injected errors are not,
it can be understood that the effect of the cryptosystem errors can be made
arbitrarily small, by increasing the factor $\mathsf{L}$.

###### Theorem 2

Given any controller (4) and $\epsilon>0$, under Assumption 1, there exist
$\mathsf{r}^{\prime}>0$, $\mathsf{s}^{\prime}>0$, and
$\mathsf{L}^{\prime}\in{\mathbb{N}}$ such that for any
$\mathsf{r}<\mathsf{r}^{\prime}$, $\mathsf{s}<\mathsf{s}^{\prime}$, and
$\mathsf{L}>\mathsf{L}^{\prime}$, the encrypted controller (61) with (56)
ensures $\|g(\mathsf{Dec}(\mathbf{u}(t)))-u(t)\|\leq\epsilon$, $\forall t\geq
0$.

Sketch of Proof: The proof is analogous to the proof of Theorem 1. Given
$\delta(\epsilon)>0$ from Assumption 1, analogously to Lemma 2 with (47), we
can choose $\mathsf{r}^{\prime}$, $\mathsf{s}^{\prime}$, and
$\mathsf{L}^{\prime}$ such that