# An Unbounded Fully Homomorphic Encryption Scheme Based On Ideal Lattices
Chinese Remainder Theorem

Zhiyong Zheng∗, Engineering Research Center of Ministry of Education for
Financial Computing and Digital Engineering, Renmin University of China,
Henan Academy of Sciences, China
Fengxia Liu†, Beijing Advanced Innovation Center for Future Blockchain
and Privacy Computing, Institute of Artificial Intelligence, China,
email<EMAIL_ADDRESS>
Kun Tian‡, Engineering Research Center of Ministry of Education for
Financial Computing and Digital Engineering, Renmin University of China,
China,
email<EMAIL_ADDRESS>
ABSTRACT We propose an unbounded fully homomorphic encryption scheme, i.e. a
scheme that allows one to compute on encrypted data for any desired functions
without needing to decrypt the data or knowing the decryption keys. This is a
rational solution to an old problem proposed by Rivest, Adleman, and Dertouzos
[42] in 1978, and to some new problems appeared in Peikert [38] as open
questions 10 and open questions 11 a few years ago.

Our scheme is completely different from the breakthrough work [21, 22] of
Gentry in 2009. Gentry’s bootstrapping technique constructs a fully
homomorphic encryption (FHE) scheme from a somewhat homomorphic one that is
powerful enough to evaluate its own decryption function. To date, it remains
the only known way of obtaining unbounded FHE. Our construction of unbounded
FHE scheme is straightforward and noise-free that can handle unbounded
homomorphic computation on any refreshed ciphertexts without bootstrapping
transformation technique.

KEYWORDS Fully Homomorphic Encryption, Ideal Lattices, Chinese Remainder
Theorem, General Compact Knapsacks Problem.

##  1 Introduction

In 1978, Rivest, Adleman, and Dertouzos [42] proposed a concept which has come
to be known as fully homomorphic encryption(FHE), at the time they called it a
privacy homomorphism. In brief, we write a cryptosystem by
$\mathcal{P}\stackrel{{\scriptstyle
f}}{{\longrightarrow}}\mathcal{C}\stackrel{{\scriptstyle
f^{-1}}}{{\longrightarrow}}\mathcal{P}$, where $\mathcal{P}$ is the plaintexts
space, and $\mathcal{C}$ is the ciphertexts space, $f$ is the encryption
function depends an public key, and $f^{-1}$ is the decryption function
depends on secret key. Suppose that $\mathcal{P}$ and $\mathcal{C}$ are two
commutative rings, and

$f^{-1}\left(c_{1}+c_{2}\right)=f^{-1}\left(c_{1}\right)+f^{-1}\left(c_{2}\right),\
\
f^{-1}\left(c_{1}c_{2}\right)=f^{-1}\left(c_{1}\right)f^{-1}\left(c_{2}\right),\
\forall c_{1},c_{2}\in\mathcal{C},$

then $f$ is called a fully homomorphic encryption, or FHE. Under a FHE $f$,
for any polynomials $p(x)\in\mathcal{C}[x]$, it is easy to see that

$f^{-1}\left(p(c)\right)=p^{*}\left(f^{-1}(c)\right),\quad\forall
c\in\mathcal{C},$

where $p^{*}(x)\in\mathcal{P}[x]$ is the corresponding polynomial over
$\mathcal{P}$. Since all elementary functions can be approximated by
polynomials, thus we can do any desired computation on ciphertexts without the
decryption of data.

###  1.1 Unbounded FHE Schemes

Fully homomorphic encryption was known to have abundant applications in
cryptography, but for more than three decades no plausibly secure scheme was
known. This changed in 2009 when Gentry [21, 22] proposed a candidate FHE
scheme based on ideal lattices. The candidate FHE scheme means somewhat
homomorphic scheme that supports only a bounded amount of homomorphic
computation on fresh ciphertexts, then, one applies the bootstrapping
transformation to convert the scheme into one that can handle unbounded
homomorphic computation. Gentry’s breakthrough seminal work generated
tremendous excitement, and was quickly followed by many works [7, 8, 9, 10,
12, 17, 18, 23, 24, 25, 26, 43]. Despite significant advances, bootstrapping
is computationally quite expensive, because it involves homomorphically
evaluating the entire decryption function. In addition, bootstrapping for
unbounded FHE requires one to make a “circular security” assumption, i.e, it
is secure to reveal an encryption of the secret key under itself. So far, such
assumptions are poorly understood, and we have little theoretical evidence to
support them, in particular, no worst-case hardness. Because of this, Peikert
[38] put out two open problems relating to unbounded FHE as follows.

  * •

Open Question 10: Is there an unbounded FHE scheme that does not rely on
bootstrapping? Is there a version of bootstrapping that uses a lighter-weight
computation than full decryption?

  * •

Open Question 11: Is there an unbounded FHE scheme that can be proved secure
solely under a worst-case complexity assumption?

###  1.2 The FHE Schemes From LWE Distribution

To date, all known full homomorphic encryption schemes follow the same basic
template from Gentry’s initial work [21]. In a sequence of work, Brakerski and
Vaikuntanathan [9, 10] gave a “second generation” of FHE constructions based
on LWE distribution [40, 41]. In 2013, Gentry, Sahai, and Waters [27] proposed
another interesting LWE-based FHE scheme that have some unique and
advantageous properties. For example, the GSW Scheme can be used to bootstrap
with only a small polynomial-factor growth in the error rate. We describe
these schemes in details here.

  * •

BV FHE Scheme  Let $1<t<q$ be two positive integers such that $(t,q)=1$. In
the BV system, a secret key $s$ is an LWE secret and encrypt a plaintext
$u\in\mathbb{Z}_{t}$ using an LWE sample for modulus $q$. We use the most
significant bit encoding to obtain a ciphertext $c$ by

$\langle c,s\rangle\equiv_{\chi}\lfloor\frac{qu}{t}\rceil(\text{mod}\ q),$

where $\chi$ is a discrete Gauss distribution over $\mathbb{Z}_{q}$, and
$\lfloor x\rceil$ is the rounding of real number $x$ to the nearest integer.
We use secret key $s$ to decrypt the ciphertext $c$ by

$f^{-1}(c)\equiv_{\chi}\lfloor\frac{t}{q}\cdot\langle
c,s\rangle\rceil\left(\text{mod}\ t\right).$

Obviously, one has $f^{-1}(c)=u$ (see [52]). To explain this scheme is a
somewhat FHE scheme, we may use the least significant bit encoding of the
message (The equivalence of two encoding is referred to Appendix A of [4]). In
fact, the ciphertext $c$ satisfies

$\langle s,c\rangle\equiv_{\chi}m\ (\text{mod}\ q),\ \text{and }\
m\in\\{nt+u\mid n\in\mathbb{Z}\\}\cap[-\frac{q}{2},\frac{q}{2}).$

To decrypt $c$, one just compute $\langle s,c\rangle\in\mathbb{Z}_{q}$, lifts
the result to its unique representative $m$ in
$\mathbb{Z}\cap[-\frac{q}{2},\frac{q}{2})$, and the outputs $u\equiv
m(\text{mod}\ t)$. It is easily seen that the homomorphic computation on
ciphertext $c$ induces some noises, which, if too large, will destroy the
plaintext. Therefore, the bootstrapping technique that re-encrypts a
ciphertext and reduces the noise level remains the only known way of building
the unbounded FHE schemes.

  * •

GSW FHE Scheme  The GSW FHE scheme is presented most simply in terms of the
gadget-based trapdoor described in [1, 3, 5, 34, 39]. The heart of GSW scheme
are the following additive and multiplicative homomorphisms for tags and
trapdoors. Let $\bar{A}\in\mathbb{Z}_{q}^{n\times\bar{m}}$ be LWE samples with
secret key $\bar{s}\in\mathbb{Z}_{q}^{n-1}$, and for $i=1,2$, let

$A_{i}=x_{i}G-\bar{A}R_{i},$

where $x_{i}\in\mathbb{Z}_{q}$, $G$ is the block-diagonal gadget matrix of
dimension $n\times nl,$ $R_{i}\in\mathbb{Z}_{q}^{\bar{m}\times n}$ are random
Gauss matrices over $\mathbb{Z}_{q}$, and $\bar{m}=n+nl$ (see p.50 of [38]).
Since $\left(\begin{array}[]{l}R_{i}\\\ I_{n}\end{array}\right)$ is a trapdoor
with tag $x_{i}I_{n}$ for matrix $\left[\bar{A},A_{i}\right],$ it is easy to
verify that

$A_{1}+A_{2}=\left(x_{1}+x_{2}\right)G-\bar{A}\left(R_{1}+R_{2}\right)$

and

$A_{1}G^{-1}\left(A_{2}\right)=x_{1}x_{2}G-\bar{A}\underbrace{\left(R_{1}G^{-1}\left(A_{2}\right)+x_{1}R_{2}\right)}_{R}$

In other words, $\left(\begin{array}[]{c}R_{1}+R_{2}\\\
I_{n}\end{array}\right)$ is a trapdoor with tag
$\left(x_{1}+x_{2}\right)I_{n}$ for matrix $\left[\bar{A},A_{1}+A_{2}\right]$,
and $\left(\begin{array}[]{l}R\\\ I_{n}\end{array}\right)$ is a trapdoor with
tag $x_{1}x_{2}I_{n}$ for matrix
$\left[\bar{A},A_{1}G^{-1}\left(A_{2}\right)\right]$. Even with all of the
above techniques, homomorphic operations always increase the error rate of a
ciphertext, by as much as a polynomial factor per operation. Therefore, the
schemes described here can only homomorghically evaluate circuits of an
a-priori bounded depth.

###  1.3 The FHE Schemes From Ring-LWE

Several constructions based on Ring-LWE are today among the most promising FHE
candidates. There are three most popular FHE schemes from Ring-LWE: (1) TFHE
[15, 16] particularly suitable for combinatorial operations on individual
slots and tolerating large noise and thus, large multiplicative depth; (2)
B/FV [7, 11, 20] allowing to perform large vectorial arithmetic operations as
long as the multiplicative depth of the evaluated circuit remains small; (3)
HEAAN [13, 14]—a mixed encryption scheme shown to be very efficient for
floating-point computations. We introduce these schemes slightly in details as
follows.

  * •

TFHE Scheme TFHE consists of three major encryption/decryption schemes, each
represented by a different plaintext space. First, the scheme TLWE encrypts
messages over the entire torus $\mathbb{T}$ and produces ciphertexts in
$\mathbb{T}^{N+1}$. The other two schemes are:

— TRGSW encrypts elements of the ring $\mathcal{R}_{\mathbb{Z}}$ (integer
polynomials) with bounded $l^{\infty}$-norms (of the corresponding vectors in
$\mathbb{Z}^{N}$ under the natural identification
$\mathcal{R}\simeq\mathbb{Z}^{N}$).

— TRLWE encrypts elements $\mu$ of the $\mathcal{R}_{\mathbb{Z}}$-module
$\mathbb{T}_{\mathcal{R}}$ that can also be viewed as elements of
$\mathbb{T}^{N}$ via the natural bijection
$\mathbb{T}_{\mathcal{R}}\simeq\mathbb{T}^{N}$.

There is an external product $\boxdot_{\alpha}$ depending on a noise parameter
$\alpha$ (see Corollary 3.14 [16]) which yields a FHE module structure on the
schemes TRGSW and TRLWE.

In TFHE, TLWE ciphertexts of a message $\mu\in\mathbb{T}$ have the form
$(a,b=<s,a>+\mu+e)\in\mathbb{T}^{N+1}$ where $s\in\\{0,1\\}^{N}$ is the secret
key, $a\in\mathbb{T}^{N}$ is uniformly random and $e\in\mathbb{T}$ is sampled
according to a noise distribution centered at zero. Similarly, for TRLWE,
ciphertexts of $\mu\in\mathbb{T}_{\mathcal{R}}$ are of the form $(a,b=s\cdot
a+\mu+e)\in\mathbb{T}_{\mathcal{R}}^{2}$ where $s\in\mathcal{B}$,
$a\in\mathbb{T}_{\mathcal{R}}$ is uniformly random and
$e\in\mathbb{T}_{\mathcal{R}}$.

The decryption in TLWE (resp. TRLWE) uses a secret $\kappa$-Lipschitz function
(here, $\kappa>0$ is small and we mean “with respect to the $l^{\infty}$-norm
on the torus”)
$\varphi_{s}:\mathbb{T}^{N}\times\mathbb{T}\rightarrow\mathbb{T}$ (resp.
$\varphi_{s}:\mathbb{T}_{\mathcal{R}}\times\mathbb{T}_{\mathcal{R}}\rightarrow\mathbb{T}_{\mathcal{R}}$)
called phase parametrized by a small (often binary) secret key
$s\in\\{0,1\\}^{N}$ (resp. $s\in\mathcal{B}$) and defined by
$(a,b)\in\mathbb{T}^{N}\times\mathbb{T}\rightarrow b-<s,a>$ (resp.
$(a,b)\rightarrow b-s\cdot a$). The fact that the phase is a
$\kappa$-Lipschitz function for small $\kappa\leqslant N+1$ makes the
decryption tolerant to errors and allows working with approximated numbers.

Ciphertexts are either fresh (i.e., generated by directly encrypting a
plaintext) or they are produced by a sequence of homomorphic operations. In
both cases, one views the ciphertext as a random variable depending on the
random coins used to generate $a$ and $e$ as well as all random coins used in
all these homomorphic operations.

Since $\varphi_{s}(a,b)=b-s\cdot a=\mu+e$, the decryption $\mu$ and the noise
parameter $\alpha$ are the mean and the standard deviation of the phase
function $\varphi_{s}(a,b)$, respectively (here, the mean and standard
deviation are computed over the random coins in the encryption algorithm).

  * •

B/FV Scheme In this scheme, the message space is the finite ring
$\mathcal{R}_{p}=\mathbb{Z}_{p}[x]/<x^{N}+1>$ for some integer $p$ (typically
a power of 2 or a prime number). A message $\mu\in\mathcal{R}_{p}$ is
encrypted on a quotient ring $\mathcal{R}_{q}$ (for a larger modulus $q$) as a
ciphertext $(a,b)\in\mathcal{R}_{q}^{2}$ where $a\in\mathcal{R}_{q}$ is chosen
uniformly at random and $b$ is sampled from
$\mathcal{D}_{\mathcal{R}_{q},\sigma,s\cdot a+\frac{p}{q}\mu}$. Here,
$\mathcal{D}_{\mathcal{R}_{q},\sigma,\mu}$ is the discrete Gaussian
distribution over $\mathcal{R}_{q}$ centered at $\mu$ with standard deviation
$\sigma$ (discrete means that the values are integers only). In addition,
$s\in\mathcal{B}$ is the secret key.

Homomorphic addition of two ciphertexts $(a_{1},b_{1})$ and $(a_{2},b_{2})$ is
achieved by component-wise addition. The idea behind the homomorphic
multiplication of two ciphertexts $(a_{1},b_{1})$ and $(a_{2},b_{2})$ is a
technique referred to as relinearization: one first lifts
$(a_{i},b_{i})\in\mathcal{R}_{q}^{2}$ to
$(\tilde{a_{i}},\tilde{b_{i}})\in\mathcal{R}^{2}$ where each coefficient is
lifted to $[-q/2,q/2)$ and then view of $\mu_{i}$ as being expressed as a
linear polynomial on $s$ (i.e., $\mu_{i}\sim\frac{p}{q}(b_{i}+s\cdot a_{i})$).
One then computes the quadratic polynomial corresponding to the product,
namely $\frac{p}{q}(b_{1}+s\cdot a_{1})\cdot\frac{p}{q}(b_{2}+s\cdot a_{2})$,
and uses the relinearization described in [20] to write this product as
$\frac{p}{q}(b+s\cdot a)$ and determine the coefficients
$(a,b)\in\mathcal{R}_{q}$.

The noise amplitude grows by a small factor $O(N)$ on average after each
multiplication, so it is a common practice to perform a modulus-rescaling
step, that divides and rounds each coefficient as well as the modulus $q$ by
the same scalar in order to bring the noise amplitude back to $O(1)$ so that
the subsequent operations continue on smaller ciphertexts.

  * •

HEAAN Scheme In this scheme, the message space is the subset of
$\mathcal{R}_{q}$ containing all elements of norm $\leqslant B$ for some bound
$B$, where the norm of an element $x\in\mathcal{R}_{q}$ is defined as
$||\tilde{x}||_{\infty}$. Here $\tilde{x}\in\mathcal{R}_{\mathbb{R}}$ is the
minimal lift of $x$, i.e., coefficients lifted to $[-q/2,q/2)$. The message is
decrypted up to a constant number of least significant bits which are
considered as noise.

A HEAAN ciphertext is also a Ring-LWE pair $(a,b)\in\mathcal{R}_{q}^{2}$ where
$a\in\mathcal{R}_{q}$ is uniformly random and $b$ is equal to $s\cdot a+\mu$
up to a Gaussian error of small standard deviation. This time, plaintexts and
ciphertexts share the same space, so no rescaling factor $p/q$ is used.
Multiplication of two messages uses the same formula as in B/FV including
relinearization: if both input messages are bounded by $B$ with $O(1)$ noise,
the product is a message bounded by $B^{2}$ with noise $O(B)$, so it is a
common practice at this point to perform a modulusrescaling step that divides
everything by $B$ to bring the noise back to $O(1)$ (see [14]). Unlike B/FV,
this division in the modulus switching scales not only the ciphertext but also
the plaintext by $B$. This can be fixed by adding a (public) tag to the
ciphertext to track the number of divisions by $B$ performed.

Recently, Boura, Gama, Georgieva, and Jetchev [6] proposed a practical hybrid
solution for combining and switching between the above three Ring-LWE-based
FHE scheme. They achieved it by first mapping the different plaintexts spaces
to a common algebra structure and then by applying efficient switching
algorithms. This approach has many practical applications, for example, it
becomes an integral tool for the recent standardization initiatives of
homomorphic schemes and common APIs.

###  1.4 Other Related Works

At Eurocrypt 2010, van Dijk, Gentry, Halevi, and Vaikuntanathan [19] described
a fully homomorphic encryption scheme over the integers (see also [12, 17,
18]). As in Gentry’s scheme, the authors first describe a somewhat homomorphic
scheme supporting a limited number of additions and multiplications over
encrypted bits. Then they apply Gentry’s squash decryption technique to get a
bootstrappable scheme and then Gentry’s ciphertext refresh procedure to get a
full homomorphic scheme. The main appeal of the scheme (compared to the
original Gentry’s scheme) is its conceptual simplicity, namely, all operations
are done over that integers instead of ideal lattices. However the public key
was too large for any practical system. In [17] and [18], the authors reduced
the public key site from $\tilde{\mathcal{O}}\left(\lambda^{10}\right)$ to
$\tilde{\mathcal{O}}\left(\lambda^{7}\right)$ by encrypting with a quadratic
form in the public key elements, instead of a linear form.

It is the latest schemes without using noise reduction techniques (see [28]).
In 2015, Yagisawa proposed a non-associative octonion ring over finite field
fully homomorphic encryption scheme [45]. This scheme cryptographic robustness
is based on the complexity of multivariate algebraic equations with high
degree. In his next paper, he developed some improvements to the scheme [46].
Liu presented a symmetric fully homomorphic encryption scheme based on non-
commutative rings [30]. Liu’s scheme provides arbitrary number of additions
and multiplications, and the correct decryption in contempt of the amount of
noises reduction mechanisms and based on the approximating-GCD complexity.
Noise-free symmetric fully homomorphic encryption scheme was proposed by Li
and Wang [29] that used matrices over non-commutative rings. Needless to say,
those noise-free schemes are not the solutions to problems of FHE scheme,
because of using non-associative and non-commutative rings for the plaintexts
and ciphertexts.

###  1.5 Our contribution

Our contribution on unbounded FHE scheme is straightforward and noise-free,
which is completely different from Gentry’s initial construction. More
precisely, our FHE scheme can handle unbounded homomorphic computation on any
refreshed ciphertexts without bootstrapping transformation. This is an
rational solution to open problems on fully homomorphic encryption.

Our solution comes in three steps. First, we provide a general construction
based on ideal lattices and Chinese Remainder Theorem, which includes three
efficient algorithms for generating secret key, public key and decryption. The
plaintext space is the direct sum of rings $\mathbb{Z}_{t_{i}}$, where $t_{i}$
is the one dimensional modulus of each ideal lattice $I_{i}$ ($1\leqslant
i\leqslant m$). The ciphertexts space $\mathbb{Z}^{n}$ is a commutative ring
with the addition and convolutional product $\otimes$ of vectors, needless to
say, the algebraic structures for homomorphic computation are simplest. The
main ideal is to set up a multiplicative opperation for $\mathbb{Z}^{n}$, such
that $\mathbb{Z}^{n}$ becomes a commutative ring, therefore, one view
$I\subset\mathbb{Z}^{n}$ both as an ideal and as a lattice in
$\mathbb{Z}^{n}$, in particular, $\mathbb{Z}^{n}/I$ becomes a quotient ring.
Working with this ring $(\mathbb{Z}^{n},+,\otimes)$, we can efficiently
utilize Chinese Remainder Theorem for generating of public key. Next, we
provide an efficient computable practical system based on principal ideal
lattices and some basic results from cyclotomic fields [47]. The novelty of
this practical system is to establish a connection between a cryptosystem and
the ancient hard problem in mathematics: how to find a solution of an
algebraic equation with high degree. By the famous Galois theory, there is no
general method to find a solution when the degree of an algebraic equation is
bigger than 5. Finally, we discuss the secure of our scheme based on the
general compact knapsacks problem for arbitrary rings, we show that the
security is solely under the worst-case complexity assumption. This is also a
solution to Open Question 11 of Peikert [38].

The generalization of compact knapsack problem for arbitrary ring may be
described as follows: given $m$ ring elements $a_{1},a_{2},\cdots a_{m}\in R$
and a target value $b\in R$, find coefficients $x_{1},x_{2},\cdots,x_{m}\in
X\subset R$ such that $\sum_{i=1}^{m}a_{i}x_{i}=b$. The computational
complexity of this problem depends on the choice of ring $R$ and the size of
$X$. This problem is known to be solvable in quasi polynomial time when $R$ is
the ring of integers and $X$ is the set of small integers
$\left\\{0,1,\cdots,2^{m-1}\right\\}$ (see [2] and [32]). Micciancio [32]
studied the knapsack problem when $R$ is an appropriately chosen ring of
modulo polynomials and $X$ is the subset of polynomials with small
coefficients, he has shown that the complexity is as hard to solve on the
average as the worst-case instance of approximating the covering radius of any
cyclic lattice within a polynomial factor.

We generalize this result to any ideal lattices, such that our FHE scheme is
as hard to solve on the average as the worst case of approximating the
covering radius of any ideal lattices.

##  2 The General Construction

Let $\mathbb{Z}[x]$ be the ring of integer coefficients polynomials with
variable $x,\ \phi(x)\in\mathbb{Z}[x]$, and
$\phi(x)=x^{n}-\phi_{n-1}x^{n-1}-\cdots-\phi_{1}x-\phi_{0}$ with $\phi_{0}\neq
0$ be a given polynomial, $\langle\phi(x)\rangle$ be the principal ideal
generated by $\phi(x)$ in $\mathbb{Z}[x]$,
$R=\mathbb{Z}[x]/\langle\phi(x)\rangle$ be the quotient ring. Let
$\mathbb{R}^{n}$ be the $n$ dimensional Euclidean space, and
$\mathbb{Z}^{n}\subset\mathbb{R}^{n}$ be all of integer vectors in
$\mathbb{R}^{n}$. We use column notation for vectors in $\mathbb{R}^{n}$.

There is a one to one correspondence between the quotient ring
$\mathbb{Z}[x]/\langle\phi(x)\rangle$ and all the integer vectors
$\mathbb{Z}^{n}$:

$a(x)=a_{0}+a_{1}x\cdots
a_{n-1}x^{n-1}\in\mathbb{Z}[x]/\langle\phi(x)\rangle\stackrel{{\scriptstyle\tau}}{{\longrightarrow}}a=\left(\begin{array}[]{c}a_{0}\\\
a_{1}\\\ \vdots\\\ a_{n-1}\end{array}\right)\in\mathbb{Z}^{n},$ (2.1)

we write $\tau(a(x))=a$, or $\tau^{-1}(a)=a(x)$. Since
$\tau\left(a(x)+b(x)\right)=\tau(a(x))+\tau(b(x)),$ $\tau$ is an isomorphism
of additive groups in fact. To regard $\tau$ as an isomorphism of rings, we
need to define a multiplicative operator in $\mathbb{Z}^{n}$. To do this, let
the rotation matrix $H=H_{\phi}$ be given by

$H=\left(\begin{array}[]{ccc|c}0&\cdots&0&\phi_{0}\\\ \hline\cr&&&\phi_{1}\\\
&I_{n-1}&&\vdots\\\ &&&\phi_{n-1}\\\ \end{array}\right)$

where $I_{n-1}$ is the unit matrix of $n-1$ dimension.

DEFINITION 2.1 For any $\alpha\in\mathbb{R}^{n}$, the ideal matrix generated
by $\alpha$ is defined by

$H^{*}(\alpha)=\left[\alpha,H\alpha,\cdots,H^{n-1}\alpha\right]\in\mathbb{R}^{n\times
n}.$

Some basic properties about ideal matrix may be described as the following
lemma, its proof is referred to Lemma $2.5$ of [49], or Lemma 5.2.4 of [48].

Lemma 2.1 Let $\alpha=\left(\begin{array}[]{c}\alpha_{0}\\\ \alpha_{1}\\\
\vdots\\\ \alpha_{n-1}\end{array}\right)$ and
$\beta=\left(\begin{array}[]{c}\beta_{0}\\\ \beta_{1}\\\ \vdots\\\
\beta_{n-1}\end{array}\right)$ be any two vectors in $\mathbb{R}^{n}$, then
one has

(i) $H^{*}(\alpha)=\alpha_{0}I_{n}+\alpha_{1}H+\cdots+\alpha_{n-1}H^{n-1}$;

(ii) $H^{*}(\alpha)H^{*}(\beta)=H^{*}(\beta)H^{*}(\alpha)$;

(iii) $H^{*}(\alpha)H^{*}(\beta)=H^{*}\left(H^{*}(\alpha)\beta\right)$;

(iv)
$\operatorname{det}\left(H^{*}(\alpha)\right)=\prod\limits_{i=1}^{n}\alpha\left(\omega_{i}\right)$;

where $\alpha(x)=\tau^{-1}(\alpha)$, and
$\omega_{1},\omega_{2},\cdots,\omega_{n}$ are $n$ roots of $\phi(x)$.

By (iv) of Lemma 2.1, $H^{*}(\alpha)$ is an invertible matrix if and only if
$\alpha(x)$ and $\phi(x)$ have no common roots in complex numbers field. Now,
we may define a multiplicative operator in $\mathbb{Z}^{n}$ in terms of the
ideal matrix.

DEFINITION 2.2 Let $\alpha,\beta\in\mathbb{Z}^{n}$ be two integer vectors, we
define the convolutional product $\alpha\otimes\beta$ by

$\alpha\otimes\beta=H^{*}(\alpha)\beta.$

Obviously, under the convolutional product $\alpha\otimes\beta$,
$\mathbb{Z}^{n}$ becomes a commutative ring with the unit element
$e=\left(\begin{array}[]{c}1\\\ 0\\\ \vdots\\\
0\end{array}\right)\in\mathbb{Z}^{n}$, since
$\alpha\otimes\beta=\beta\otimes\alpha$ and

$\alpha\otimes e=e\otimes\alpha=\alpha,\ \ \ \forall\alpha\in\mathbb{Z}^{n}.$

Sometimes, we write this ring by
$\left(\mathbb{Z}^{n},+,\otimes\right)=\mathbb{Z}^{n}$.

Lemma 2.2 The correspondence $\tau$ given by (2.1) is a ring isomorphism
between $\mathbb{Z}^{n}/\langle\phi(x)\rangle$ and $\mathbb{Z}^{n}$, namely,
we have

$\mathbb{Z}[x]/\langle\phi(x)\rangle\cong\left(\mathbb{Z}^{n},+,\otimes\right).$

###### Proof.

By Lemma 2.4 of [49] or Lemma 5.2.5 of [48], it is easy to see that

$\displaystyle\tau\left(\alpha(x)+\beta(x)\right)=\alpha+\beta=\tau(\alpha(x))+\tau(\beta(x)),$
$\displaystyle\tau(\alpha(x)\beta(x))=\alpha\otimes\beta=\tau(\alpha(x))\otimes\tau(\beta(x)).$

The conclusion follows immediately.

∎

According to the definition of ideal lattices [31, 32, 37, 38, 50, 51], an
ideal lattice $I\subset\mathbb{Z}^{n}$, just is an ideal of
$(\mathbb{Z}^{n},+,\otimes)$, we view $I\subset\mathbb{Z}^{n}$ both as an
ideal of $\mathbb{Z}^{n}$ and as a lattice in $\mathbb{Z}^{n}$, in particular,
$\mathbb{Z}^{n}/I$ is a quotient ring.

A lattice $I\subset\mathbb{R}^{n}$ is a discrete additive group of
$\mathbb{R}^{n}$ [36, 37, 44], we write $I=\mathcal{L}(B)$ as usual, where
$B=[\beta_{1},\beta_{2},\cdots,\beta_{n}]\in\mathbb{R}^{n\times n}$ is the
generated matrix or a basis of $I$. All lattices we discuss here are the full
rank lattice, it means that det$(B)\neq 0$. If $I\subset\mathbb{Z}^{n}$, then
$I$ is called an integer lattice. The Hermite Normal Form base $B$ [33, 47]
for an integer lattice is an upper triangular matrix $B=(b_{ij})_{n\times
n}\in\mathbb{Z}^{n\times n}$ satisfying $b_{ii}\geqslant 1(1\leqslant
i\leqslant n)$ and

$b_{ij}=0,\ \text{if}\ 0\leqslant j<i\leqslant n,\ \text{and}\ \ 0\leqslant
b_{ij}<b_{ii},\ \text{if}\ 0\leqslant i<j\leqslant n.$

It is known that there is an unique HNF basis for an integer lattice and its
Gram-Schmidt orthogonal basis is a diagonal matrix, more precisely, if
$B=[\beta_{1},\beta_{2},\cdots,\beta_{n}]$ is the HNF basis of an integer
lattice, $B^{*}=[\beta_{1}^{*},\beta_{2}^{*},\cdots,\beta_{n}^{*}]$ is the
corresponding orthogonal basis obtained by Gram-Schmidt orthogonal method,
then $B^{*}=\text{diag}\\{b_{11},b_{22},\cdots,b_{nn}\\}$ is a diagonal matrix
(see Lemma 7.26 of [47]).

DEFINITION 2.3 $b_{11}$ is called the one dimensional modulus of an ideal
lattice $I=\mathcal{L}(\beta_{1},\beta_{2},\cdots,\beta_{n})$, and denoted by
$t(I)=b_{11}$.

Let $I\subset(\mathbb{Z}^{n},+,\otimes)$ be an ideal lattice, to obtain a set
of representative elements for the quotient ring $\mathbb{Z}^{n}/I$, we use
the notation of orthogonal parallelepiped due to Micciancio [33]. The
following lemma is referred to Lemma 7.45 and (7.131) of [47], or §4.1 of
[33], and a proof will be appeared in Lemma 2.6 below.

Lemma 2.3 Suppose that $I=\mathcal{L}(B)$ is an full rank ideal of
$\mathbb{Z}^{n}$, $B$ is the HNF basis of $I$, and
$B^{*}=\text{diag}\\{b_{11},b_{22},\cdots,b_{nn}\\}$ is the corresponding
orthogonal basis, then a set of representative elements of the quotient ring
$\mathbb{Z}^{n}/I$ is

$\mathcal{F}(I)=\Bigg{\\{}x=\begin{pmatrix}x_{1}\\\ x_{2}\\\ \vdots\\\
x_{n}\end{pmatrix}\in\mathbb{Z}^{n}\ |\ 0\leqslant x_{i}<b_{ii},\ 1\leqslant
i\leqslant n\Bigg{\\}},$

and $\mathcal{F}(I)$ is called the orthogonal parallelepiped of $I$.

Next, we turn to discuss the ideal lattices and the ring
$(\mathbb{Z}^{n},+,\otimes)$. Let $\alpha\in\mathbb{Z}^{n}$ be a given vector,
the principal ideal lattice $<\alpha>$ is a principal ideal generated by
$\alpha$ in $\mathbb{Z}^{n}$. It is easily verified that

$<\alpha>=\Big{\\{}\alpha\otimes x\ |\
x\in\mathbb{Z}^{n}\Big{\\}}=\mathcal{L}(H^{*}(\alpha)).$

Thus, the generated matrix of a principle ideal lattice $<\alpha>$ just is the
ideal matrix generated by $\alpha$.

The operations among the ideal lattices in $(\mathbb{Z}^{n},+,\otimes)$ are
defined as usual, in particular, the addition and multiplication for two
ideals, $I$ and $J$ are defined by

$I+J=\Big{\\{}\alpha+\beta\ |\ \alpha\in I,\ \beta\in J\Big{\\}},$
$IJ=\Big{\\{}\sum\limits_{i<\infty}\alpha_{i}\otimes\beta_{i}\ |\
\alpha_{i}\in I,\ \beta_{i}\in J\Big{\\}},$

and

$I\cap J=\Big{\\{}\gamma\ |\ \gamma\in I,\ \text{and}\ \gamma\in J\Big{\\}}.$

Since $I+J$, $IJ$ and $I\cap J$ are also the ideals of $\mathbb{Z}^{n}$,
therefore, all of them are ideal lattices.

DEFINITION 2.4 Let $I\subset\mathbb{Z}^{n}$, $J\subset\mathbb{Z}^{n}$ be two
ideal lattices. If $I+J=\mathbb{Z}^{n}$, we call $I$ and $J$ to be relatively
prime, and denoted by $(I,J)=1$.

It is easy to see that two ideal lattices $I$ and $J$ are relatively prime, if
and only if there are $\alpha\in I$ and $\beta\in J$ such that
$\alpha+\beta=e$, where $e$ is the unit element of
$(\mathbb{Z}^{n},+,\otimes)$.

To construct a FHE scheme, we utilize the Chinese Remainder Theorem in the
ring $(\mathbb{Z}^{n},+,\otimes)$, of which is a well-known theorem in Number
Theory.

THEOREM 1(Chinese Remainder Theorem) Let $I_{1},I_{2},\cdots,I_{m}$ be
pairwise relatively prime ideal lattices in $\mathbb{Z}^{n}$, and
$\alpha_{1},\alpha_{2},\cdots,\alpha_{m}\in\mathbb{Z}^{n}$ be $m$ target
vectors in $\mathbb{Z}^{n}$, then there exists a common solution of the
following congruences:

$x\equiv\alpha_{i}\ (\text{mod}\ I_{i}),\ 1\leqslant i\leqslant m,$

and the solution of $x\in\mathbb{Z}^{n}$ is unique modulo ideal lattice
$I_{1}\cap I_{2}\cdots\cap I_{m}$.

For arbitrary pairwise relatively prime lattices $I_{1},I_{2},\cdots,I_{m}$,
it is known that

$I_{1}\cap I_{2}\cdots\cap I_{m}=I_{1}I_{2}\cdots I_{m}.$

By the above Chinese Remainder Theorem, one has the following consequence
immediately.

Corollary 2.1 Suppose that $I_{1},I_{2},\cdots,I_{m}$ are pairwise relatively
prime ideal lattices in $\mathbb{Z}^{n}$, then we have the following ring
isomorphism

$\mathbb{Z}^{n}/I_{1}I_{2}\cdots I_{m}\cong\mathbb{Z}^{n}/I_{1}\ \bigoplus\
\mathbb{Z}^{n}/I_{2}\ \bigoplus\ \cdots\ \bigoplus\ \mathbb{Z}^{n}/I_{m}.$
(2.2)

The right-hand side of (2.2) is the direct sum of $m$ quotient ring
$\mathbb{Z}^{n}/I_{i}\ (1\leqslant i\leqslant m)$, and the addition and
multiplication of $\mathop{\bigoplus}\limits_{i=1}^{m}\mathbb{Z}^{n}/I_{i}$
are given by

$(a_{1},a_{2},\cdots,a_{m})+(b_{1},b_{2},\cdots,b_{m})=(a_{1}+b_{1},a_{2}+b_{2},\cdots,a_{m}+b_{m})$

and

$(a_{1},a_{2},\cdots,a_{m})\otimes(b_{1},b_{2},\cdots,b_{m})=(a_{1}\otimes
b_{1},a_{2}\otimes b_{2},\cdots,a_{m}\otimes b_{m}).$

###### Proof.

Since $I_{1},I_{2},\dots,I_{m}$ are pairwise prime, by Theorem 1, there are
$m$ vectors $A_{i}$ ($1\leqslant i\leqslant m$) in $\mathbb{Z}^{n}$ such that

$A_{i}\equiv e\ (\text{mod}\ I_{i}),\ \text{and}\ A_{i}\equiv 0\ (\text{mod}\
I_{j}),\ \text{if}\ j\neq i.$

For any
$\alpha=(\alpha_{1},\alpha_{2},\dots,\alpha_{m})\in\mathbb{Z}^{n}/I_{1}\
\bigoplus\ \mathbb{Z}^{n}/I_{2}\ \bigoplus\ \cdots\ \bigoplus\
\mathbb{Z}^{n}/I_{m}$, by Theorem 1 again, there is a unique solution
$x\in\mathbb{Z}^{n}/I_{1}I_{2}\cdots I_{m}$ such that

$\left\\{\begin{array}[]{c}x\equiv\alpha_{1}\ (\text{mod}\ I_{1})\\\ \vdots\\\
x\equiv\alpha_{m}\ (\text{mod}\ I_{m})\end{array}\right.$

We define $f(\alpha)=x$, which is the ring isomorphism from
$\mathbb{Z}^{n}/I_{1}\ \bigoplus\ \mathbb{Z}^{n}/I_{2}\ \bigoplus$ $\cdots\
\bigoplus\ \mathbb{Z}^{n}/I_{m}$ to $\mathbb{Z}^{n}/I_{1}I_{2}\cdots I_{m}$ as
we desired. Using $A_{1},A_{2},\dots,A_{m}$, one may clearly write down $f$ by

$f(\alpha)=f((\alpha_{1},\alpha_{2},\dots,\alpha_{m}))=\alpha_{1}\otimes
A_{1}+\cdots+\alpha_{m}\otimes A_{m}.$

Let $\beta=(\beta_{1},\beta_{2},\dots,\beta_{m})$ be another element of
$\mathop{\bigoplus}\limits_{i=1}^{m}\mathbb{Z}^{n}/I_{i}$, it is easy to see
that

$f(\alpha+\beta)=f((\alpha_{1}+\beta_{1},\alpha_{2}+\beta_{2},\dots,\alpha_{m}+\beta_{m}))\
$ $\qquad\qquad\qquad\qquad\qquad\ =\alpha_{1}\otimes
A_{1}+\cdots+\alpha_{m}\otimes A_{m}+\beta_{1}\otimes
A_{1}+\cdots+\beta_{m}\otimes A_{m}$ $=f(\alpha)+f(\beta).\qquad\qquad\qquad$

To verify $f(\alpha\otimes\beta)=f(\alpha)\otimes f(\beta)$, since

$f(\alpha)\equiv\alpha_{i}\ (\text{mod}\ I_{i}),\ \text{and}\
f(\beta)\equiv\beta_{i}\ (\text{mod}\ I_{i}),\ 1\leqslant i\leqslant m.$

It follows that

$f(\alpha)\otimes f(\beta)\equiv\alpha_{i}\otimes\beta_{i}\ (\text{mod}\
I_{i}),\ 1\leqslant i\leqslant m.$

By the definition of $f$, we have

$\displaystyle f(\alpha\otimes\beta)$
$\displaystyle=f((\alpha_{1}\otimes\beta_{1},\alpha_{2}\otimes\beta_{2},\dots,\alpha_{m}\otimes\beta_{m}))$
$\displaystyle=f(\alpha)\otimes f(\beta).$

This proves that $f$ is a ring isomorphism. ∎

We extend the inverse isomorphism $f^{-1}$ to the whole space $\mathbb{Z}^{n}$
by $f^{*}=f\circ\pi:$

$f^{*}:\mathbb{Z}^{n}\stackrel{{\scriptstyle\pi}}{{\longrightarrow}}\mathbb{Z}^{n}/I_{1}I_{2}\dots
I_{m}\stackrel{{\scriptstyle
f^{-1}}}{{\longrightarrow}}\mathop{\bigoplus}\limits_{i=1}^{m}\mathbb{Z}^{n}/I_{i},$

where $\pi$ is the natural homomorphism from $\mathbb{Z}^{n}$ to its quotient
ring $\mathbb{Z}^{n}/I_{1}I_{2}\dots I_{m}$. It is easy to see that $f^{*}$ is
a homomorphism from $\mathbb{Z}^{n}$ to
$\mathop{\bigoplus}\limits_{i=1}^{m}\mathbb{Z}^{n}/I_{i}$, and

$f^{*}(f(u))=f^{-1}(f(u))=u,\ \forall
u\in\mathop{\bigoplus}\limits_{i=1}^{m}\mathbb{Z}^{n}/I_{i},$ (2.3)

$f^{*}$ will play the role of decryption in our scheme, and always write down
$f^{*}$ by $f^{-1}$ in the following discussion.

Since $\mathbb{Z}$ is a ring, we wish to embed this ring into
$(\mathbb{Z}^{n},+,\otimes)$. To do this, we define an embedding mapping from
$\mathbb{Z}$ to $\mathbb{Z}^{n}$ by

$\forall a\in\mathbb{Z},\ a\rightarrow\overline{a}=\begin{pmatrix}a\\\ 0\\\
\vdots\\\ 0\end{pmatrix}\in\mathbb{Z}^{n}.$ (2.4)

Lemma 2.4 Under the embedding mapping $a\rightarrow\overline{a}$, $\mathbb{Z}$
becomes a subring of $(\mathbb{Z}^{n},+,\otimes)$, namely, for any
$a\in\mathbb{Z}$, $b\in\mathbb{Z}$, one has
$\overline{a+b}=\overline{a}+\overline{b}$ and
$\overline{ab}=\overline{a}\otimes\overline{b}$.

###### Proof.

By (2.4), we have

$\overline{a+b}=\begin{pmatrix}a+b\\\ 0\\\ \vdots\\\
0\end{pmatrix}=\begin{pmatrix}a\\\ 0\\\ \vdots\\\
0\end{pmatrix}+\begin{pmatrix}b\\\ 0\\\ \vdots\\\
0\end{pmatrix}=\overline{a}+\overline{b}$

and

$\overline{a}\otimes\overline{b}=\begin{pmatrix}ab\\\ 0\\\ \vdots\\\
0\end{pmatrix}=\overline{a\cdot b},$

the lemma follows at once. ∎

Lemma 2.5 Let $I\subset\mathbb{Z}^{n}$ be an ideal lattice, and $t=t(I)$ be
its one dimensional modulus given by DEFINATION 2.3. Then, for any
$a,b\in\mathbb{Z}$, we have

$a\equiv b\ (\text{mod}\ t)\Longleftrightarrow\overline{a}\equiv\overline{b}\
(\text{mod}\ I).$

###### Proof.

By assumption, $I$ is a full rank lattice and its HNF basis may be written by

$B=\begin{pmatrix}b_{11}&*&*&*\\\ &b_{22}&*&*\\\ &0&\ddots&*\\\
&&&b_{nn}\end{pmatrix}.$

If $\overline{a}\equiv\overline{b}\ (\text{mod}\ I)$, then there is a vector
$x=\begin{pmatrix}x_{1}\\\ \vdots\\\ x_{n}\end{pmatrix}\in\mathbb{Z}^{n}$ such
that

$\overline{a}-\overline{b}=Bx=\begin{pmatrix}a-b\\\ 0\\\ \vdots\\\
0\end{pmatrix}.$

Since $b_{nn}x_{n}=0$, and $b_{nn}\geqslant 1$, we have $x_{n}=0$, similarly,
since $b_{n-1,n-1}x_{n-1}+b_{n-1,n}x_{n}=0$, it follows that $x_{n-1}=0$.
Therefore, we have $x_{n}=x_{n-1}=\cdots=x_{2}=0$, and
$a-b=x_{1}b_{11}=x_{1}t\Rightarrow a\equiv b\ (\text{mod}\ t)$. Conversely, if
$a\equiv b\ (\text{mod}\ t)$, then $a-b=qt$, and

$\overline{a}-\overline{b}=B\begin{pmatrix}q\\\ 0\\\ \vdots\\\
0\end{pmatrix}\in I\Longrightarrow\overline{a}\equiv\overline{b}\ (\text{mod}\
I).$

The assertion is true. ∎

For arbitrary given pairwise relatively prime ideal lattices
$I_{1},I_{2},\cdots,I_{m}$, one uses the Chinese Remainder Theorem to generate
the public key $A_{1},A_{2},\cdots,A_{m}$, where $A_{i}\in\mathbb{Z}^{n}\
(1\leqslant i\leqslant m)$ such that

$A_{i}\equiv e\ (\text{mod}\ I_{i}),\ \text{and}\ A_{i}\equiv 0\ (\text{mod}\
I_{j}),\ \text{if}\ j\neq i,$ (2.5)

where $e=\begin{pmatrix}1\\\ 0\\\ \vdots\\\ 0\end{pmatrix}\in\mathbb{Z}^{n}$
is the unit element of $(\mathbb{Z}^{n},+,\otimes)$.

Now, we describe a scheme for unbounded fully homomorphic encryption as
follows.

Algorithm 1: The General Unbounded FHE Scheme
---
$\bullet$ Secret Key: One selects $m$ pairwise relatively prime ideal lattices
$I_{1},I_{2},\cdots,I_{m}$ in
$\mathbb{Z}^{n}$ as the decryption key.
$\bullet$ Public Key: Let $t_{i}=t(I_{i})$ be the one dimensional modulus of
$I_{i}\ (1\leqslant i\leqslant m)$. The
plaintexts space is the direct sum of ring
$\mathcal{P}=\mathop{\bigoplus}\limits_{i=1}^{m}\mathbb{Z}_{t_{i}}$, the
addition and
multiplication in $\mathcal{P}$ are given by
$\hskip
79.6678pt(a_{1},a_{2},\cdots,a_{m})+(b_{1},b_{2},\cdots,b_{m})=(a_{1}+b_{1},a_{2}+b_{2},\cdots,a_{m}+b_{m}),$
$\hskip
99.58464pt(a_{1},a_{2},\cdots,a_{m})\cdot(b_{1},b_{2},\cdots,b_{m})=(a_{1}b_{1},a_{2}b_{2},\cdots,a_{m}b_{m}).$
The public key for encryption is
$\\{A_{1},A_{2},\cdots,A_{m}\\}\subset\mathbb{Z}^{n}$, and each $A_{i}$
is given by (2.5).
$\bullet$ Encryption: For any plaintext
$u=(u_{1},u_{2},\cdots,u_{m})\in\mathcal{P}=\mathop{\bigoplus}\limits_{i=1}^{m}\mathbb{Z}_{t_{i}}$,
the encryption
function $f$ is given by
$\hskip 119.50148ptc=f(u)=\overline{u_{1}}\otimes
A_{1}+\overline{u_{2}}\otimes A_{2}+\cdots+\overline{u_{m}}\otimes
A_{m},\qquad\quad\ (2.6)$
where $\overline{u_{i}}$ is the embedding of $u_{i}$.
$\bullet$ Decryption: For any ciphertext $c\in\mathbb{Z}^{n}$, we use the
secret key $I_{1},I_{2},\cdots,I_{m}$ to decrypt
$c$. Since for every $i$, $1\leqslant i\leqslant m$, we have
$c\equiv\overline{u_{i}}\ (\text{mod}\ I_{i})$, and $c$ mod $I_{i}$ is
a unique vector in the orthogonal parallelepiped $\mathcal{F}(I_{i})$ of
$I_{i}$, thus one has
$c$ mod $I_{i}=\overline{u_{i}}$, and by (2.3), we have
$\hskip 150.79968ptf^{-1}(c)=(u_{1},u_{2},\cdots,u_{m})=u.$

To verify the homomorphic addition and multiplication for the above scheme, by
Lemma 2.4, $\mathbb{Z}$ is a subring of $(\mathbb{Z}^{n},+,\otimes)$. By Lemma
2.5, we can embed the direct sum
$\mathop{\bigoplus}\limits_{i=1}^{m}\mathbb{Z}_{t_{i}}$ into
$\mathop{\bigoplus}\limits_{i=1}^{m}\mathbb{Z}^{n}/I_{i}$, so that
$\mathop{\bigoplus}\limits_{i=1}^{m}\mathbb{Z}_{t_{i}}$ also is a subring of
$\mathop{\bigoplus}\limits_{i=1}^{m}\mathbb{Z}^{n}/I_{i}$. Therefore, the
property of fully homomorphism directly follows by $f^{*}$ (or $f^{-1}$) a
ring homomorphism:

$\mathop{\bigoplus}\limits_{i=1}^{m}\mathbb{Z}_{t_{i}}\hookrightarrow\mathop{\bigoplus}\limits_{i=1}^{m}\mathbb{Z}^{n}/I_{i}\stackrel{{\scriptstyle
f}}{{\longrightarrow}}\mathbb{Z}^{n}/I_{1}I_{2}\dots
I_{m}\stackrel{{\scriptstyle f^{*}}}{{\longleftarrow}}\mathbb{Z}^{n}.$

More precisely, let $c_{1}=f(u)$, and $c_{2}=f(v)$ be arbitrary two
ciphertexts, where
$u=(u_{1},u_{2},\cdots,u_{m})\in\mathop{\bigoplus}\limits_{i=1}^{m}\mathbb{Z}_{t_{i}}$,
and
$v=(v_{1},v_{2},\cdots,v_{m})\in\mathop{\bigoplus}\limits_{i=1}^{m}\mathbb{Z}_{t_{i}}$,
we note that for all $i$, $1\leqslant i\leqslant m$,

$c_{1}+c_{2}\equiv\overline{u_{i}}+\overline{v_{i}}\ (\text{mod}\ I_{i}),\
\text{and}\ c_{1}\otimes c_{2}\equiv\overline{u_{i}}\otimes\overline{v_{i}}\
(\text{mod}\ I_{i}).$

By Lemma 2.4, it follows that

$c_{1}+c_{2}\equiv\overline{u_{i}+v_{i}}\ (\text{mod}\ I_{i}),\ \text{and}\
c_{1}\otimes c_{2}\equiv\overline{u_{i}v_{i}}\ (\text{mod}\ I_{i}).$

Therefore, by Lemma 2.5, we have

$f^{-1}(c_{1}+c_{2})=(u_{1}+v_{1},u_{2}+v_{2},\cdots,u_{m}+v_{m})$
$\qquad\qquad\qquad\ \ =(u_{1},u_{2},\cdots,u_{m})+(v_{1},v_{2},\cdots,v_{m})$
$\ =f^{-1}(c_{1})+f^{-1}(c_{2}),$

and

$f^{-1}(c_{1}\otimes
c_{2})=(u_{1}v_{1},u_{2}v_{2},\cdots,u_{m}v_{m})\qquad\qquad$
$\qquad\qquad\quad=(u_{1},u_{2},\cdots,u_{m})(v_{1},v_{2},\cdots,v_{m})$
$=f^{-1}(c_{1})\cdot f^{-1}(c_{2}).\ \ $

This is an unbounded fully homomorphic encryption as we desirable.

How to decrypt the ciphertext $c\in\mathbb{Z}^{n}$ using the secret key
$I_{1},I_{2},\dots,I_{m}$ in our algorithm for the general unbounded FHE
scheme? Here we give a lemma to show that there is only one vector
$\overline{u_{i}}\in\mathbb{Z}^{n}$ in the orthogonal parallelepiped
$\mathcal{F}(I_{i})$ of $I_{i}$ such that $c\equiv\overline{u_{i}}\
(\text{mod}\ I_{i})$, and give an algorithm to calculate $\overline{u_{i}}$ in
detail.

Lemma 2.6 Given an ideal lattice $I$, for any vector $c\in\mathbb{Z}^{n}$,
there is only one vector $w\in\mathcal{F}(I)$ such that $c\equiv w\
(\text{mod}\ I)$.

###### Proof.

Assume $B=[\beta_{1},\beta_{2},\dots,\beta_{n}]$ is the HNF basis of $I$, and
$B^{*}=[\beta_{1}^{*},\beta_{2}^{*},\dots,\beta_{n}^{*}]$ is the corresponding
orthogonal basis of $B$. Write $c$ as the linear combination of
$[\beta_{1}^{*},\beta_{2}^{*},\dots,\beta_{n}^{*}]$, i.e.

$c=\sum\limits_{i=1}^{n}c_{i}\beta_{i}^{*},\
c_{i}=\frac{<c,\beta_{i}^{*}>}{<\beta_{i}^{*},\beta_{i}^{*}>}.$

Let
$w=\sum\limits_{i=1}^{n}c_{i}\beta_{i}^{*}-\sum\limits_{i=1}^{n}k_{i}\beta_{i}$,
$k_{1},k_{2},\dots,k_{n}\in\mathbb{Z}$, then
$c-w=\sum\limits_{i=1}^{n}k_{i}\beta_{i}\in I$. Next, we prove that there is
only one group of integers $k_{1},k_{2},\dots,k_{n}$ such that
$w\in\mathcal{F}(I)$, i.e.

$w_{i}=\frac{<w,\beta_{i}^{*}>}{<\beta_{i}^{*},\beta_{i}^{*}>}\in[0,1),\
\forall 1\leqslant i\leqslant n.$

Firstly, we determine the value of $k_{n}$. Since

$w_{n}=\frac{<w,\beta_{n}^{*}>}{<\beta_{n}^{*},\beta_{n}^{*}>}=c_{n}-k_{n}\frac{<\beta_{n},\beta_{n}^{*}>}{<\beta_{n}^{*},\beta_{n}^{*}>}=c_{n}-k_{n},$

therefore, when $k_{n}=[c_{n}]$, here $[x]$ means the largest integer no more
than real number $x$, we have $w_{n}\in[0,1)$. Secondly, we determine
$k_{n-1}$. Note that

$w_{n-1}=\frac{<w,\beta_{n-1}^{*}>}{<\beta_{n-1}^{*},\beta_{n-1}^{*}>}=c_{n-1}-k_{n-1}-k_{n}\frac{<\beta_{n},\beta_{n-1}^{*}>}{<\beta_{n-1}^{*},\beta_{n-1}^{*}>},$

so there is only one integer

$k_{n-1}=\left[c_{n-1}-[c_{n}]\frac{<\beta_{n},\beta_{n-1}^{*}>}{<\beta_{n-1}^{*},\beta_{n-1}^{*}>}\right]$

such that $w_{n-1}\in[0,1)$. Similarly, we could determine any $k_{i}$,
$\forall 1\leqslant i\leqslant n-1$,

$w_{i}=\frac{<w,\beta_{i}^{*}>}{<\beta_{i}^{*},\beta_{i}^{*}>}=c_{i}-k_{i}-\frac{<\sum\limits_{j=i+1}^{n}k_{j}\beta_{j},\beta_{i}^{*}>}{<\beta_{i}^{*},\beta_{i}^{*}>},$

hence, there is only one integer

$k_{i}=\bigg{[}c_{i}-\frac{<\sum\limits_{j=i+1}^{n}k_{j}\beta_{j},\beta_{i}^{*}>}{<\beta_{i}^{*},\beta_{i}^{*}>}\bigg{]}$

such that $w_{i}\in[0,1)$, $\forall 1\leqslant i\leqslant n-1$. Above all,
there is only one vector
$w=\sum\limits_{i=1}^{n}c_{i}\beta_{i}^{*}-\sum\limits_{i=1}^{n}k_{i}\beta_{i}\in\mathcal{F}(I)$
such that $c\equiv w\ (\text{mod}\ I)$. ∎

Based on Lemma 2.6, we give an algorithm for the decryption of our general FHE
scheme.

Algorithm 2: Decryption Algorithm for FHE Scheme

$\bullet$ For any ciphertext $c\in\mathbb{Z}^{n}$, given a full rank ideal
lattice $I_{i}$ with HNF basis $B=$
$[\beta_{1},\beta_{2},\dots,\beta_{n}]$ and the corresponding orthogonal basis
$B^{*}=[\beta_{1}^{*},\beta_{2}^{*},\dots,\beta_{n}^{*}]$, we
can find only one vector
$\overline{u_{i}}=c-\sum\limits_{i=1}^{n}k_{i}\beta_{i}\in\mathcal{F}(I)$ such
that $c\equiv\overline{u_{i}}\ (\text{mod}\ I_{i})$, where

$k_{n}=\left[\frac{<c,\beta_{n}^{*}>}{<\beta_{n}^{*},\beta_{n}^{*}>}\right],\
k_{i}=\bigg{[}\frac{<c,\beta_{i}^{*}>}{<\beta_{i}^{*},\beta_{i}^{*}>}-\frac{<\sum\limits_{j=i+1}^{n}k_{j}\beta_{j},\beta_{i}^{*}>}{<\beta_{i}^{*},\beta_{i}^{*}>}\bigg{]},\
i=n-1,n-2,\dots,1.$

To create an efficient algorithm for generating secret key of the above
unbounded FHE scheme, we assume that $\phi(x)$ is an irreducible polynomial,
so that the principal ideal $<\phi(x)>$ is a prime ideal in $\mathbb{Z}[x]$,
and the quotient ring $\mathbb{Z}[x]/<\phi(x)>$ is a domain, equivalently,
$(\mathbb{Z}^{n},+,\otimes)$ becomes a domain. Under this assumption, we see
that arbitrary many pairwise relatively prime ideals in $\mathbb{Z}^{n}$
almost come in automatically, we describe the process as follows.

Algorithm 3: Generating Algorithm for Secret Key

$\bullet$ First step. Randomly select an non-zero vector
$\alpha\in\mathbb{Z}^{n}$ as input, and the output
is the following relatively prime two ideal $I_{1}$ and $I_{2}$, where

$I_{1}=<\alpha>,\ \text{and}\ I_{2}=<e-\alpha>.$

$\bullet$ Second step. Randomly select two non-zero vectors $\alpha_{1}\in
I_{1}$ and $\alpha_{2}\in I_{2}$ as
input, and the output is the following ideal $I_{3}$, where

$I_{3}=<e-\alpha_{1}\otimes\alpha_{2}>.$

It is easy to see that $I_{1},I_{2},I_{3}$ are pairwise relatively prime
ideals.

$\bullet$ Last step. Suppose that $m-1$ pairwise relatively prime ideals
$I_{1},I_{2},\dots,I_{m-1}$ are
selected, then one randomly finds $\alpha_{1}\in I_{1}$, $\alpha_{2}\in
I_{2}$, $\dots$, $\alpha_{m-1}\in I_{m-1}$,
$\alpha_{i}\neq 0$, and the output ideal $I_{m}$ given by

$I_{m}=<e-\alpha_{1}\otimes\alpha_{2}\otimes\cdots\otimes\alpha_{m-1}>.$

Obviously, $I_{1},I_{2},\dots,I_{m}$ are pairwise relatively prime ideals in
$\mathbb{Z}^{n}$.

To construct an efficient algorithm for finding public key, we first show that

Lemma 2.7 Suppose that $I_{1},I_{2},\dots,I_{m}$ are pairwise relatively
ideals in $\mathbb{Z}^{n}$, and each $I_{i}$ is a principal ideal generated by
$\alpha_{i}$, namely, $I_{i}=<\alpha_{i}>$. Let

$d_{i}=\mathop{\otimes}\limits_{j=1,j\neq i}^{m}\alpha_{j},\ 1\leqslant
i\leqslant m.$

Then for every $d_{i}$, there is a vector $\mathcal{D}_{i}\in\mathbb{Z}^{n}$
such that

$d_{i}\otimes\mathcal{D}_{i}\equiv e\ (\text{mod}\ I_{i}),\ 1\leqslant
i\leqslant m.$

###### Proof.

Since $I_{1},I_{2},\dots,I_{m}$ are pairwise relatively prime by assumption,
we have

$(I_{i},I_{1}I_{2}\cdots I_{i-1}I_{i+1}\cdots I_{m})=1,\ 1\leqslant i\leqslant
m.$

In other words, we have $(I_{i},<d_{i}>)=1$, or

$<\alpha_{i}>+<d_{i}>=\mathbb{Z}^{n}.$

Therefore, there is a vector $\mathcal{D}_{i}\in\mathbb{Z}^{n}$ such that
$d_{i}\otimes\mathcal{D}_{i}\equiv e\ (\text{mod}\ I_{i})$, and we have Lemma
2.7 immediately. ∎

How to find the vector $\mathcal{D}_{i}$ defined by Lemma 2.7? We introduce a
polynomial algorithm to obtain $\mathcal{D}_{i}$ ($1\leqslant i\leqslant m$),
and generate the public key $\\{A_{1},A_{2},\dots,A_{m}\\}$ by taking
$A_{i}=d_{i}\otimes\mathcal{D}_{i}$ ($1\leqslant i\leqslant m$).

Algorithm 4: Generating Algorithm for Public Key

$\bullet$ Let $I_{i}=<\alpha_{i}>$ $(1\leqslant i\leqslant m)$ be pairwise
relatively prime, and

$d_{i}(x)=\mathop{\prod}\limits_{j=1,j\neq i}^{m}\tau^{-1}(\alpha_{i}),\
1\leqslant i\leqslant m,$

where the secret key $I_{i}=<\alpha_{i}>$ ($1\leqslant i\leqslant m$), and
$\tau^{-1}$ is the inverse mapping of
$\tau$ given by (2.1).
Since $d_{i}(x)$ and $\tau^{-1}(\alpha_{i})$ are relatively prime polynomial
in quotient ring
$\mathbb{Z}[x]/<\phi(x)>$, it follows that

$<d_{i}(x)>+<\tau^{-1}(\alpha_{i})>=\mathbb{Z}[x]/<\phi(x)>.$

Therefore, there is a polynomial $\mathcal{D}_{i}(x)$ such that

$d_{i}(x)\mathcal{D}_{i}(x)\equiv 1\ (\text{mod}\ \tau^{-1}(\alpha_{i})).$

We put $\mathcal{D}_{i}=\tau(\mathcal{D}_{i}(x))$, and
$A_{i}=d_{i}\otimes\mathcal{D}_{i}$, $1\leqslant i\leqslant m$.

To discuss the security of this scheme, we observe that all risks come from
the encryption algorithm (2.6), we describe this risk as a generalized compact
knapsack problem over the ring $(\mathbb{Z}^{n},+,\otimes)$ as follows:

$\sum\limits_{i=1}^{m}a_{i}\otimes x_{i}=u,\quad|x_{i}|\leqslant\beta,$ (2.7)

where $a_{1},a_{2},\cdots,a_{m}$ are given $m$ vectors in $\mathbb{Z}^{n}$,
$u\in\mathbb{Z}^{n}$ is a target vector, and $\beta=\max\limits_{1\leqslant
i\leqslant m}t_{i}$. We will show that the security next section.

On the other hands, for any $a\in\mathbb{Z}$, we see that
$H^{*}(\overline{a})=aI_{n}$. Therefore, this problem may transfer to the
standard Ring-SIS problem: suppose that
$A=[A_{1},A_{2},\cdots,A_{m}]\in\mathbb{Z}^{n\times m}$, where $A_{i}$ is the
public key given by (2.5), $u\in\mathbb{Z}^{n}$ is a target vector, find
$x=\begin{pmatrix}x_{1}\\\ \vdots\\\ x_{n}\end{pmatrix}\in\mathbb{Z}^{n}$ such
that $Ax=u$, and $0<|x|\leqslant\beta$. Let $q$ be a sufficiently large
positive integer, this problem can be changed to an inhomogeneous version of
the SIS problem, which is to find a short integer solution to $Ax\equiv u\
(\text{mod}\ q)$. It is not hard to show that the homogeneous and
inhomogeneous problem are essentially equivalent for typical parameters.

According to Ajtai’s seminal work [2, 3], the hardness of the SIS problem
relative to the worst-case lattice problem. More precisely, for any
$m=\text{poly}(n)$, any $\beta>0$, and any sufficiently large
$q\geqslant\beta\cdot\text{poly}(n)$, solving $\text{SIS}_{n,q,\beta,m}$ with
non-negligible probability is at least as hard as solving the decisional
approximate shortest vector problem $\text{GapSVP}_{\gamma}$ for some
$\gamma=\beta\cdot\text{poly}(n)$ (also see [35] and Theorem 4.1.2 of [38]).
Therefore, the secure of our FHE scheme is solely under a worst-case
complexity assumption, this is a reasonable solution to Open Question 11 of
[38].

##  3 The Generalized Compact Knapsack Problem Over $\mathbb{Z}^{n}$

In this section, we discuss the secure of our scheme based on the general
compact knapsack problem over the ring $(\mathbb{Z}^{n},+,\otimes)$. In [32],
Micciancio has proved that if we can solve the knapsack problem over
$\mathbb{Z}_{q}^{n}$ for some sufficiently large positive integer number $q$,
then there is a probabilistic polynomial algorithm solving the covering radius
problem for any $n$ dimensional full rank cyclic lattice. First we generalize
Micciancio’s result to arbitrary ideal lattices based on our precious work
[51], and then solving the knapsack problem from $\mathbb{Z}_{q}^{n}$ to
$(\mathbb{Z}^{n},+,\otimes)$. We give an entire proof for the reason of
completeness, although the method we present here is quite similar to
Micciancio’s original proof.

DEFINITION 3.1 Let $L$ be a full rank lattice, $\gamma(n)$ is a parameter of
$n$, $\gamma(n)\geqslant 1$, $\text{CDP}_{\gamma}$ problem is to find an $r$
such that

$\rho(L)\leqslant r\leqslant\gamma(n)\rho(L),$

where $\rho(L)=\max\limits_{x\in\mathbb{R}^{n}}\text{dist}(x,L)$ and
$\text{dist}(x,L)=\min\limits_{\alpha\in L}|x-\alpha|$.

DEFINITION 3.2 Let $L$ be a full rank lattice,
$S=\\{s_{1},s_{2},\cdots,s_{n}\\}\subset L$ be $n$ linearly independent
lattice vectors. $S^{*}=\\{s_{1}^{*},s_{2}^{*},\cdots,s_{n}^{*}\\}$ is the
orthogonal basis corresponding to $S$ by the Gram-Schmidt method. We define

$\sigma(S)=\Big{(}\sum\limits_{i=1}^{n}|s_{i}^{*}|^{2}\Big{)}^{\frac{1}{2}}.$

Here we give our main result to show that the generalized knapsack problem
over $\mathbb{Z}^{n}$ is at least as hard as the covering radius problem for
any $n$ dimensional full rank ideal lattice.

THEOREM 2 Let $m=O(\log n)$, $k=\tilde{O}(\text{log}n)$,
$\phi_{\max}=\max\\{|\phi_{0}|,|\phi_{1}|,\dots,|\phi_{n-1}|\\}$,
$M=\sqrt{2+2\phi_{\max}^{2}}$, $W=\frac{M^{n}-1}{M-1}$, $\gamma\geqslant
16mkn^{3}W$, if we can solve the knapsack problem (2.7), then there is a
positive probabilistic polynomial algorithm solving the covering radius
problem $\text{CDP}_{\gamma}$ for any $n$ dimensional full rank ideal lattice
$L$.

Remark: In the original work of Micciancio [32], the parameter $\gamma$ is
bigger than $16mkn^{3}$, we require $\gamma\geqslant 16mkn^{3}W$, where $W$ is
given by $\frac{M^{n}-1}{M-1}$. The main difference is to estimate the length
of convolutional product $\alpha\otimes\beta$ for any two vectors $\alpha$ and
$\beta$. It is clearly that
$|\alpha\otimes\beta|\leqslant\sqrt{n}|\alpha||\beta|$ in the case of
circulant lattice, but it is non-trivial in the case of ideal lattices.

Lemma 3.1 For any $\alpha,\beta\in\mathbb{Z}^{n}$, we have

$|\alpha\otimes\beta|\leqslant W|\alpha|\cdot|\beta|,$

where $W$ is defined in Theorem 2.

###### Proof.

We first prove $|H\alpha|\leqslant M|\alpha|$. Let
$\alpha=(\alpha_{0},\alpha_{1},\dots,\alpha_{n-1})^{T}$, then

$\displaystyle|H\alpha|^{2}$
$\displaystyle=\phi_{0}^{2}\alpha_{0}^{2}+(\alpha_{0}+\phi_{1}\alpha_{1})^{2}+\cdots+(\alpha_{n-2}+\phi_{n-1}\alpha_{n-1})^{2}$
$\displaystyle\leqslant\phi_{0}^{2}\alpha_{0}^{2}+2(\alpha_{0}^{2}+\phi_{1}^{2}\alpha_{1}^{2})+\cdots+2(\alpha_{n-2}^{2}+\phi_{n-1}^{2}\alpha_{n-1}^{2})$
$\displaystyle\leqslant
2(\alpha_{0}^{2}+\cdots+\alpha_{n-2}^{2})+2\phi_{\max}^{2}(\alpha_{0}^{2}+\alpha_{1}^{2}+\cdots+\alpha_{n-1}^{2})$
$\displaystyle\leqslant(2+2\phi_{\max}^{2})|\alpha|^{2}.$

So $|H\alpha|\leqslant M|\alpha|$. Similarly,

$|H^{2}\alpha|\leqslant M|H\alpha|\leqslant M^{2}|\alpha|.$

In the same way, we can get $|H^{k}\alpha|\leqslant M^{k}|\alpha|$, $\forall
1\leqslant k\leqslant n-1$. Let
$\beta=(\beta_{0},\beta_{1},\dots,\beta_{n-1})^{T}$, it follows that

$\displaystyle|\alpha\otimes\beta|$
$\displaystyle=|H^{*}(\alpha)\beta|=|\beta_{0}\alpha+\beta_{1}H\alpha+\cdots+\beta_{n-1}H^{n-1}\alpha|$
$\displaystyle\leqslant\sum\limits_{i=0}^{n-1}|\beta_{i}H^{i}\alpha|\leqslant\sum\limits_{i=0}^{n-1}M^{i}|\alpha||\beta|=\frac{M^{n}-1}{M-1}|\alpha|\cdot|\beta|.$

We complete this proof. ∎

Let $L=\mathcal{L}(B)\subset\mathbb{R}^{n}$ be a full rank ideal lattice,
$q\geqslant 4mkn^{2}W^{2}$,
$\\{e_{0},e_{1},\cdots,e_{n-1}\\}\subset\mathbb{Z}_{q}^{n}$ is a standard
orthogonal basis, $S=\\{s_{1},s_{2},\cdots,s_{n}\\}\subset L$ is a set of $n$
linearly independent vectors. We define the parameter

$\mu=\left(\frac{4nq}{\gamma}+\frac{W}{2}\right)\sigma(S).$ (3.1)

According to Lemma 1.6 in Chapter 3 in [48], there is a lattice vector $c\in
L$ such that $|c-\mu e_{0}|\leqslant\frac{1}{2}\sigma(S)$, let
$B^{\prime}=q(H^{*}(c))^{-1}B$. It follows that the lattice
$\mathcal{L}(B^{\prime})$ generated by $B^{\prime}$ satisfies
$q\mathbb{Z}^{n}\subset\mathcal{L}(B^{\prime})$ according to Lemma 2.1 in
Chapter 3 in [48]. Therefore, $q\mathbb{Z}^{n}$ is an additive subgroup in
$\mathcal{L}(B^{\prime})$. Randomly choose $mk$ elements
$x_{ij}^{{}^{\prime}}\ (1\leqslant i\leqslant m,1\leqslant j\leqslant k)$ in
the quotient group $G=\mathcal{L}(B^{\prime})/q\mathbb{Z}^{n}$, the integral
vectors $w_{ij}^{{}^{\prime}}$ of $x_{ij}^{{}^{\prime}}$ is defined by

$w_{ij}^{{}^{\prime}}=\lfloor x_{ij}^{{}^{\prime}}\rceil\in\mathbb{Z}^{n},\
1\leqslant i\leqslant m,\ 1\leqslant j\leqslant k.$

Let

$a_{ij}\equiv w_{ij}^{{}^{\prime}}\ (\text{mod}\ q),\ \
a_{i}\equiv\sum\limits_{j=1}^{k}w_{ij}^{{}^{\prime}}\ (\text{mod}\ q),$

Assume $A=(a_{1},a_{2},\cdots,a_{m})\in\mathbb{Z}_{q}^{n\times m}$. Since the
knapsack problem (2.7) is solvable on $\mathbb{Z}^{n}$, it could also be
solved on $\mathbb{Z}_{q}^{n}$. Let
$y=(y_{1},y_{2},\cdots,y_{m})\in\mathbb{Z}_{q}^{n\times m}$ and
$\hat{y}=(\hat{y}_{1},\hat{y}_{2},\cdots,\hat{y}_{m})\in\mathbb{Z}_{q}^{n\times
m}$ be two different integer matrices such that
$\sum\limits_{i=1}^{m}a_{i}\otimes(y_{i}-\hat{y}_{i})=0,\
|y_{i}|\leqslant\sqrt{n},\ |\hat{y}_{i}|\leqslant\sqrt{n},\forall 1\leqslant
i\leqslant m$. We define

$x_{ij}=\frac{1}{q}H^{*}(c)x_{ij}^{{}^{\prime}},w_{ij}=\frac{1}{q}H^{*}(c)w_{ij}^{{}^{\prime}},1\leqslant
i\leqslant m,1\leqslant j\leqslant k,$

and

$s^{\prime}=\sum\limits_{i=1}^{m}\sum\limits_{j=1}^{k}(x_{ij}-w_{ij})\otimes(y_{i}-\hat{y}_{i}).$
(3.2)

Then $x_{ij}$ is a lattice vector in the given ideal lattice
$L=\mathcal{L}(B)$ ($1\leqslant i\leqslant m,1\leqslant j\leqslant k$), and
$s^{\prime}$ is also a lattice vector in $L=\mathcal{L}(B)$ based on Lemma 2.2
in Chapter 3 in [48].

The next lemma gives an estimation of the length of $s^{\prime}$, which has
some differences from the proof of Micciancio’s.

Lemma 3.2 Let $S=\left\\{s_{1},s_{2},\cdots,s_{n}\right\\}\subset L$ be a set
of $n$ linearly independent vectors in the full rank ideal lattice $L$. Denote
$|S|=\max\limits_{1\leqslant i\leqslant n}|s_{i}|$, $s^{\prime}$ is the
lattice vector defined in (3.2), then

$|s^{\prime}|\leqslant\frac{1}{2}|S|.$

###### Proof.

This proof is similar to that of Lemma 2.3 in Chapter 3 in [48] except some
computations about the parameters. We prove
$|s^{\prime}|\leqslant\frac{1}{2\sqrt{n}}\sigma(S)$ first. Based on the
definition of $s^{\prime}$ in (3.2),

$|s^{\prime}|\leqslant\sum\limits_{i=1}^{m}\sum\limits_{j=1}^{k}\big{|}(x_{ij}-w_{ij})\otimes(y_{i}-\hat{y}_{i})\big{|}.$
(3.3)
$x_{ij}-w_{ij}=\frac{1}{q}H^{*}(c)(x_{ij}^{{}^{\prime}}-w_{ij}^{{}^{\prime}})=\frac{1}{q}c\otimes(x_{ij}^{{}^{\prime}}-w_{ij}^{{}^{\prime}}).$

Let $\alpha=c-\mu e_{0}$, where $\mu$ is defined in (3.1). Then
$|\alpha|\leqslant\frac{1}{2}\sigma(S)$, and

$x_{ij}-w_{ij}=\frac{1}{q}(\alpha+\mu
e_{0})\otimes(x_{ij}^{{}^{\prime}}-w_{ij}^{{}^{\prime}})=\frac{1}{q}H^{*}(\alpha+\mu
e_{0})(x_{ij}^{{}^{\prime}}-w_{ij}^{{}^{\prime}})$ $\ \ =\frac{1}{q}\mu
H^{*}(e_{0})(x_{ij}^{{}^{\prime}}-w_{ij}^{{}^{\prime}})+\frac{1}{q}H^{*}(\alpha)(x_{ij}^{{}^{\prime}}-w_{ij}^{{}^{\prime}})\quad$
$\
=\frac{\mu}{q}(x_{ij}^{{}^{\prime}}-w_{ij}^{{}^{\prime}})+\frac{1}{q}H^{*}(\alpha)(x_{ij}^{{}^{\prime}}-w_{ij}^{{}^{\prime}}).\qquad\qquad$

Since $w_{ij}^{{}^{\prime}}=\lfloor
x_{ij}^{{}^{\prime}}\rceil\in\mathbb{Z}^{n}$, we have

$|x_{ij}^{{}^{\prime}}-w_{ij}^{{}^{\prime}}|\leqslant\frac{1}{2}\sqrt{n},$

combine with Lemma 3.1, we get

$|x_{ij}-w_{ij}|\leqslant\frac{\mu}{q}|x_{ij}^{{}^{\prime}}-w_{ij}^{{}^{\prime}}|+\frac{1}{q}|\alpha\otimes(x_{ij}^{{}^{\prime}}-w_{ij}^{{}^{\prime}})|$
$\qquad\qquad\leqslant\frac{\mu}{q}\cdot\frac{1}{2}\sqrt{n}+\frac{1}{q}\cdot
W\cdot\frac{1}{2}\sigma(S)\cdot\frac{\sqrt{n}}{2}$ $\qquad\qquad\qquad\ \
=\frac{\sqrt{n}}{2q}\left(\frac{4nq}{\gamma}+\frac{W}{2}\right)\sigma(S)+\frac{\sqrt{n}W}{4q}\sigma(S)$
$\qquad\ \
=\sigma(S)\left(\frac{2n^{\frac{3}{2}}}{\gamma}+\frac{\sqrt{n}W}{2q}\right)\qquad\
$ $\qquad\qquad\qquad\
\leqslant\sigma(S)\left(\frac{1}{8}\cdot\frac{1}{mkn^{\frac{3}{2}}W}+\frac{1}{8}\cdot\frac{1}{mkn^{\frac{3}{2}}W}\right)$
$\ \ \ =\sigma(S)\frac{1}{4mkn^{\frac{3}{2}}W}.\qquad\quad\ \ $

Based on (3.3), we know

$|s^{\prime}|\leqslant
mkW\max\limits_{i,j}|x_{ij}-w_{ij}|\cdot\max\limits_{i}|y_{i}-\hat{y}_{i}|$ $\
\ \leqslant mkW\cdot\frac{\sigma(S)}{4mkn^{\frac{3}{2}}W}\cdot
2\sqrt{n}=\frac{\sigma(S)}{2\sqrt{n}}.\ $

Since

$\sigma(S)\leqslant\left(\sum\limits_{i=1}^{n}|s_{i}|^{2}\right)^{\frac{1}{2}}\leqslant\sqrt{n}|S|,$

We can get

$|s^{\prime}|\leqslant\frac{\sigma(S)}{2\sqrt{n}}\leqslant\frac{\sqrt{n}|S|}{2\sqrt{n}}=\frac{1}{2}|S|.$

So we complete the proof of Lemma 3.2.

∎

Based on the above lemmas, Theorem 2 follows directly from Micciancio’s method
[32]. From Theorem 2, we can see that the general compact knapsack problem
over $\mathbb{Z}^{n}$ is at least as hard as the covering radius problem
$\text{CDP}_{\gamma}$ of any ideal lattice. Therefore, the security of our
unbounded FHE scheme is solely under the worst-case complexity assumption, as
a result, it is a reasonable solution to Open Question 11 of [38].

##  4 A Practical System

As an example, we introduce a practical system for FHE using some basic
results about the cyclotomic field [44]. Suppose that $p$ is an odd prime
number and $Q\left(\xi_{p}\right)$ is the cyclotomic field, where
$\xi_{p}=e^{\frac{2\pi i}{p}}$ is a primitive $p$-th root of unit. Let

$\mathbb{Z}\left[\xi_{p}\right]=\left\\{\sum_{i=0}^{p-1}a_{i}\xi_{p}^{i}\mid
a_{i}\in\mathbb{Z}\right\\}.$

It is known that $\mathbb{Z}\left[\xi_{p}\right]$ is the ring of algebraic
integers of field $Q(\xi_{p})$. Therefore $\mathbb{Z}\left[\xi_{p}\right]$ is
a Dedekind domain (so we have unique factorization into prime ideals, etc. see
Proposition $1.2$ of [44]).

To construct an commutative ring for $\mathbb{Z}^{n}$, we select
$\phi(x)=x^{p-1}+x^{p-2}+\cdots+x+1\in\mathbb{Z}[x]$. Obviously, $\phi(x)$ is
the minimal polynomial of $\xi_{p}.$ Let $n=p-1$, then we obtain a ring
$\left(\mathbb{Z}^{n},+,\otimes\right)$ in terms of $\phi(x)$ and the rotation
matrix $H_{\phi}$, it is easy to see that (see (3.2) of [49])

$\left(\mathbb{Z}^{n},+,\otimes\right)\cong\mathbb{Z}[x]/\langle\phi(x)\rangle\cong\mathbb{Z}\left[\xi_{p}\right].$

Thus, $\mathbb{Z}^{n}$ becomes a Dedekind domain.

For any integer $q\in\mathbb{Z}$, we define an integer vector
$\alpha_{q}\in\mathbb{Z}^{n}$ by

$\alpha_{q}=\left(\begin{array}[]{l}q\\\ 0\\\ \vdots\\\ 0\\\
1\end{array}\right)\in\mathbb{Z}^{n}.$

The principal ideal $\left\langle\alpha_{q}\right\rangle$ generated by
$\alpha_{q}$ is denoted by

$I_{q}=\left\langle\alpha_{q}\right\rangle=\mathcal{L}\left(H^{*}(\alpha_{q})\right).$

Lemma 4.1 If $q_{1}$ and $q_{2}$ are two different prime numbers, then
$I_{q_{1}}$ and $I_{q_{2}}$ are relatively prime ideal lattices in
$\mathbb{Z}^{n}$.

###### Proof.

Suppose that $q$ is a prime number. Since
$\left(\mathbb{Z}^{n},+,\otimes\right)\cong\mathbb{Z}[x]/\langle\phi(x)\rangle,$
we see the polynomial
$\tau^{-1}\left(\alpha_{q}\right)=\alpha_{q}(x)=x^{n-1}+q\in\mathbb{Z}[x]$,
which is the type polynomial of Eisenstein, thus it is an irreducible
polynomial over $\mathbb{Z}[x]$. Regarding $\alpha_{q}(x)$ as the polynomial
of $\mathbb{Z}[x]/\langle\phi(x)\rangle$, clearly, it is also an irreducible
polynomial in $\mathbb{Z}[x]/\langle\phi(x)\rangle$. By assumption, $q_{1}$
and $q_{2}$ are different prime numbers, we show that the principal ideals
$\left\langle\alpha_{q_{1}}(x)\right\rangle$, and
$\left\langle\alpha_{q_{2}}(x)\right\rangle$ are relatively prime ideals in
$\mathbb{Z}[x]/\langle\phi(x)\rangle$. Since
$\mathbb{Z}[x]/\langle\phi(x)\rangle$ is a Dedekind domain, if
$\left\langle\alpha_{q_{1}}(x)\right\rangle$ and
$\left\langle\alpha_{q_{2}}(x)\right\rangle$ are not relatively prime, then,
there exists a prime ideal $P$ in $\mathbb{Z}[x]/\langle\phi(x)\rangle$ such
that

$\left\langle\alpha_{q_{1}}(x)\right\rangle\subset P,\ \text{ and }\
\left\langle\alpha_{q_{2}}(x)\right\rangle\subset P.$

It follows for any positive integer $k\geq 1$ that

$\left<\alpha^{k}_{q_{1}}(x)\right>\subset P^{k},\ \text{ and }\
\left\langle\alpha^{k}_{q_{2}}(x)\right\rangle\subset P^{k}.$

It is known that three exists a positive integer $k\geqslant 1$, such that
$P^{k}=\langle d(x)\rangle$ is a principal ideal, we thus have

$\left\langle\alpha^{k}_{q_{1}}(x)\right\rangle\subset\langle d(x)\rangle,\
\text{ and }\ \left\langle\alpha^{k}_{q_{2}}(x)\right\rangle\subset\langle
d(x)\rangle.$

In other words, we have $d(x)\mid\alpha^{k}_{q_{1}}(x)$, and
$d(x)\mid\alpha^{k}_{q_{2}}(x)$. However, this is impossible, since
$\alpha_{q_{1}}(x)$ and $\alpha_{q_{2}}(x)$ are two irreducible polynomials in
$\mathbb{Z}[x]/\langle\phi(x)\rangle$, and
$\alpha_{q_{1}}(x)\neq\alpha_{q_{2}}(x)$.

This proves that $\left\langle\alpha_{q_{1}}(x)\right\rangle$ and
$\left\langle\alpha_{q_{2}}(x)\right\rangle$ are relatively prime ideals in
$\mathbb{Z}[x]/\langle\phi(x)\rangle$. Equivalently, $I_{q_{1}}$ and
$I_{q_{2}}$ are two relatively prime ideal lattices in $\mathbb{Z}^{n}.$ ∎

Lemma 4.2 The one dimensional modulus of the principal ideal $I_{q}$ is

$t_{q}=t(I_{q})=q^{n}-q^{n-1}+\cdots-q+1.$

###### Proof.

It is not hard to compute that
$\text{det}(H^{*}(\alpha_{q}))=q^{n}-q^{n-1}+\cdots-q+1.$ Since the polynomial
$x^{n}-x^{n-1}+\cdots-x+1$ is an irreducible polynomial over $\mathbb{Z}$, we
have the assertion of lemma immediately. ∎

According to Lemma 4.1 and Lemma 4.2, we obtain a generating algorithm for the
secret key as follows:

Algorithm 5: Generating Algorithm for Secret Key
---
$\bullet$ Randomly select $m$ different prime numbers $q_{1}$, $q_{2}$,
$\cdots,$ $q_{m}$ such that $q_{i}\neq p$. The principle
ideal lattices
$I_{q_{i}}=\langle\alpha_{q_{i}}\rangle,\ \ 1\leq i\leq m$
are the secret key, and the corresponding one dimensional modulus $t_{q_{i}}$
given by
$t_{q_{i}}=t(I_{q_{i}})=q_{i}^{n}-q_{i}^{n-1}+\cdots-q_{i}+1.$ (4.1)

To get an attainable algorithm for public key, we define $m$ vectors
$d_{i}(1\leq i\leq m)$ by

$d_{i}=\alpha_{q_{1}}\otimes\alpha_{q_{2}}\otimes\cdots\otimes\alpha_{q_{i-1}}\otimes\alpha_{q_{i+1}}\otimes\cdots\otimes\alpha_{q_{m}}\\\
=\otimes_{\begin{subarray}{c}j=1\\\ j\neq
i\end{subarray}}^{m}\alpha_{q_{j}},\quad 1\leq i\leq m.$

Lemma 4.3 For every vector $d_{i}(1\leq i\leq m)$, there is a vector
$\mathcal{D}_{i}\in\mathbb{Z}^{n}$ such that

$d_{i}\otimes\mathcal{D}_{i}\equiv e\left(\text{mod}\ I_{q_{i}}\right),$

where $e=\left(\begin{array}[]{l}1\\\ 0\\\ \vdots\\\ 0\end{array}\right)$ is
the unit element of rimg $\left(\mathbb{Z}^{n},+,\otimes\right)$.

###### Proof.

By lemma 4.1, $I_{q_{1}},I_{q_{2}},\cdots,I_{q_{m}}$ are pairwise relatively
prime ideals, hence we have
$\left(I_{q_{i}},I_{q_{1}}I_{q_{2}}\cdot I_{q_{i-1}}I_{q_{i+1}}\cdot
I_{q_{m}}\right)=1$. In other words, we have
$\left(\left\langle\alpha_{q_{i}}\right\rangle,\left\langle
d_{i}\right\rangle\right)=1$, or

$\left\langle\alpha_{q_{i}}\right\rangle+\left\langle
d_{i}\right\rangle=\mathbb{Z}^{n}.$

Therefore, there is a vector $\mathcal{D}_{i}\in\mathbb{Z}^{n}$ such that
$\mathcal{D}_{i}\otimes d_{i}\equiv e(\text{mod}\ I_{q_{i}})$. we have Lemma
$4.3$.

∎

We propose a polynomial algorithm to find the vector $\mathcal{D}_{i}$
appeared in Lemma 4.3, and then put $A_{i}=d_{i}\otimes\mathcal{D}_{i}$
getting the public key $A_{1},A_{2},\cdots,A_{m}$. The polynomial algorithm
for finding vector $\mathcal{D}_{i}$ like follows.

Algorithm 6: Generating Algorithm for Public Key
---
$\bullet$ Let
$d_{i}(x)=\prod_{\begin{subarray}{c}j=1\\\ j\neq
i\end{subarray}}^{m}\left(x^{n-1}+q_{j}\right),1\leq i\leq m.$
Since polynomial $x^{n-1}+q_{i}$ and $x^{n-1}+q_{j}(j\neq i)$ are relatively
prime in $\mathbb{Z}[x]/\langle\phi(x)\rangle$,
it follows that $\left(x^{n-1}+q_{i},d_{i}(x)\right)=1$. Therefore, there is a
polynomial $\mathcal{D}_{i}(x)$ such that
$d_{i}(x)\mathcal{D}_{i}(x)\equiv 1\left(\text{mod}\ (x^{n-1}+q_{i})\right).$
We obtain $\mathcal{D}_{i}=\tau\left(\mathcal{D}_{i}(x)\right)$ under the
mapping $\tau$ given in section 2.

Now, we describe an attainable algorithm for our FHE Scheme based on
cyclotomic field as follows.

Algorithm 7: The Attainable Algorithm for Unbounded FHE Scheme
---
$\bullet$ Secret key:  Let $q_{1},q_{2},\cdots,q_{m}$ be $m$ different prime
numbers such that $q_{i}\neq p$. The $m$
pairwise relatively prime principal ideal lattices
$I_{q_{1}},I_{q_{2}},\cdots,I_{q_{m}}$ are
the secret keys for decryption.
$\bullet$ Public key:  Let $A_{i}=d_{i}\otimes\mathcal{D}_{i}\left(1\leqslant
i\leqslant m\right)$, then $A_{1},A_{2},\cdots,A_{m}$ are the public key for
encryption. The plaintext space is
$\mathcal{P}=\mathbb{Z}_{t_{1}}\bigoplus\mathbb{Z}_{t_{2}}\bigoplus\cdots\bigoplus\mathbb{Z}_{t_{m}},$
where $t_{i}$ is the one dimensional modulus of $I_{q_{i}}$ given by (4.1).
$\bullet$ Encryption:  For any plaintext
$u=\left(u_{1},u_{2},\cdots,u_{m}\right)\in\mathop{\bigoplus}\limits_{i=1}^{m}\mathbb{Z}_{t_{i}}$,
then
$c=f(u)=\bar{u}_{1}\otimes A_{1}+\bar{u}_{2}\otimes
A_{2}+\cdots+\bar{u}_{m}\otimes A_{m},$
where $\bar{u}_{i}$ is the embedding of $u_{i}$ into $\mathbb{Z}^{n}$.
$\bullet$ Decryption:  For given ciphertext $c\in\mathbb{Z}^{n}$, there is an
unique vector $\bar{u}_{i}$ in the orthogonal
parallelepiped $\mathcal{F}\left(I_{q_{i}}\right)$, such that
$c\equiv\bar{u}_{i}(\text{mod}\ I_{q_{i}})$, $1\leq i\leq m$. Thus, one has
$f^{-1}(c)=\left(u_{1},u_{2},\cdots,u_{m}\right)=u.$

The property of FHE follows immediately from the general construction. We
mainly discuss the security of this practical system for FHE. Obviously, an
additional risk comes from the messages of one dimensional modulus
$t_{i}\left(1\leq i\leq m\right)$. It is equivalent to find a solution of the
algebraic equation with high degree of

$x^{n}-x^{n-1}+\cdots-x+1=t$

for given target value $t\in\mathbb{Z}$. This is an ancient hard problem in
mathematics, there is no general method to find the solution according to the
famous Galois theory. Therefore, we conclude that there are no special risks
coming from the one dimensional modulus $t_{i}$ of $I_{q_{i}}$.

##  5 Conclusions

In this work, we construct the first unbounded fully homomorphic encryption
scheme without using bootstrapping transformation technique. It remains a
problem to construct a probabilistic algorithm for generating secret key and
public key, so that the security of our scheme solely depends upon short
integer solution problem (SIS), or R-SIS. To our best knowledge, there is no a
cryptosystem directly connect with SIS or R-SIS. On the other hands, the fully
homomorphic signature is the dual question of the fully homomorphic
encryption, we will develop a scheme for fully homomorphic signature in the
following works.

Acknowledgements This work was prepared during our visiting to Henan Academy
of Sciences, the authors appreciate professor Tianze Wang and professor
Jingluo Huang for invitation and hosting.

## References

  * [1] S. Agrawal, D. Boneh and X. Boyen. Efficient lattice (H)IBE in the standard model. In EUROCRYPT, 553-572, 2010.
  * [2] M. Ajtai. Generating hard instances of lattice problems. Quaderni di Matematica, 13:1-32, 2004. Preliminary version in STOC 1996.
  * [3] M. Ajtai. Generating hard instances of the short basis problem. In ICALP, 1-9, 1999.
  * [4] J. Alperin-Sheriff and C. Peikert. Practical bootstrapping in quasilinear time. In CRYPTO, 1-20, 2013.
  * [5] J. Alwen and C. Peikert. Generating shorter bases for hard random lattices. Theory of Computing Systems, 48(3):535-553, April 2011. Preliminary version in STACS 2009.
  * [6] C. Boura, N. Gama, M. Georgieva and D. Jetchev. CHIMERA: Combining ring-LWE-based fully homomorphic encryption schemes. J. Math. Cryptol., 316-338, 2020.
  * [7] Z. Brakerski. Fully homomorphic encryption without modulus switching from classical GapSVP. In CRYPTO, 868-886, 2012.
  * [8] Z. Brakerski, C. Gentry and V. Vaikuntanathan. (Leveled) fully homomorphic encryption without bootstrapping. TOCT, 6(3):13, 2014. Preliminary version in ITCS 2012.
  * [9] Z. Brakerski and V. Vaikuntanathan. Fully homomorphic encryption from ring-LWE and security for key dependent messages. In CRYPTO, 505-524, 2011.
  * [10] Z. Brakerski and V. Vaikuntanathan. Efficient fully homomorphic encryption from (standard) LWE. SIAM J. Comput., 43(2):831-871, 2014. Preliminary version in FOCS 2011.
  * [11] H. Chen, K. Laine and R. Player. Simple encrypted arithmetic library-SEAL v2.1. In Financial Cryptography and Data Security-FC 2017, 3-18, 2017.
  * [12] J. H. Cheon, J.-S. Coron, J. Kim, M. S. Lee, T. Lepoint, M. Tibouchi and A. Yun. Batch fully homomorphic encryption over the integers. In EUROCRYPT, 315-335, 2013.
  * [13] J. H. Cheon, K. Han, A. Kim, M. Kim and Y. Song. Bootstrapping for approximate homomorphic encryption. In EUROCRYPT, 360-384, 2018.
  * [14] J. H. Cheon, A. Kim, M. Kim and Y. S. Song. Homomorphic encryption for arithmetic of approximate numbers. In ASIACRYPT, 409-437, 2017.
  * [15] I. Chillotti, N. Gama, M. Georgieva and M. Izabachene. Faster fully homomorphic encryption: Bootstrapping in less than 0.1 seconds. In ASIACRYPT, 3-33, 2016.
  * [16] I. Chillotti, N. Gama, M. Georgieva and M. Izabachene. TFHE: Fast fully homomorphic encryption over the torus. IACR Cryptology ePrint Archive, 2018.
  * [17] J.-S. Coron, A. Mandal, D. Naccache and M. Tibouchi. Fully homomorphic encryption over the integers with shorter public keys. In CRYPTO, 487-504, 2011.
  * [18] J.-S. Coron, D. Naccache and M. Tibouchi. Public key compression and modulus switching for fully homomorphic encryption over the integers. In EUROCRYPT, 446-464, 2012.
  * [19] M. van Dijk, C. Gentry, S. Halevi and V. Vaikuntanathan. Fully homomorphic encryption over the integers. In EUROCRYPT, 24-43, 2010.
  * [20] J. Fan and F. Vercauteren. Somewhat practical fully homomorphic encryption. IACR Cryptology ePrint Archive, 2012.
  * [21] C. Gentry. A fully homomorphic encryption scheme. Ph.D. thesis, Stanford University, 2009.
  * [22] C. Gentry. Fully homomorphic encryption using ideal lattices. In STOC, 169-178, 2009.
  * [23] C. Gentry. Computing arbitrary functions of encrypted data. Commun. ACM, 53(3):97-105, 2010.
  * [24] C. Gentry. Toward basing fully homomorphic encryption on worst-case hardness. In CRYPTO, 116-137, 2010.
  * [25] C. Gentry, S. Halevi, C. Peikert and N. P. Smart. Field switching in BGV-style homomorphic encryption. Journal of Computer Security, 21(5):663-684, 2013. Preliminary version in SCN 2012.
  * [26] C. Gentry, S. Halevi and N. P. Smart. Fully homomorphic encryption with polylog overhead. In EUROCRYPT, 465-482, 2012.
  * [27] C. Gentry, A. Sahai and B. Waters. Homomorphic encryption from learning with errors: Conceptually-simpler, asymptotically-faster, attribute-based. In CRYPTO, 75-92, 2013.
  * [28] K.G. Kogos, K.S. Filippova and A.V. Epishkina. Fully homomorphic encryption schemes: the state of the art. In EIConRus, 463-466, 2017.
  * [29] J. Li and L. Wang. Noise-free symmetric fully homomorphic encryption based on non-commutative rings. In IACR Cryptology ePrint Archive, 2015.
  * [30] D. Liu. Practical fully homomorphic encryption without noise reduction. In IACR Cryptology ePrint Archive, 2015.
  * [31] V. Lyubashevsky, C. Peikert and O. Regev. On ideal lattices and learning with errors over rings. In EUROCRYPT, 1-23, 2010.
  * [32] D. Micciancio. Generalized compact knapsacks, cyclic lattices, and efficient one-way functions from worst-case complexity assumptions. In SFCS, 356-365, 2002.
  * [33] D. Micciancio. Improving lattice based cryptosystems using the Hermite normal form. In CaLC, 126-145, 2001.
  * [34] D. Micciancio and C. Peikert. Trapdoors for lattices: Simpler, tighter, faster, smaller. In EUROCRYPT, 700-718, 2012.
  * [35] D. Micciancio and C. Peikert. Hardness of SIS and LWE with small parameters. In CRYPTO, 21-39, 2013.
  * [36] D. Micciancio and O. Regev. Worst-case to average-case reductions based on Gaussian measures. SIAM J. Comput., 37(1):267-302, 2007. Preliminary version in FOCS 2004.
  * [37] D. Micciancio and O. Regev. Lattice-based cryptography. In Post Quantum Cryptography, 147-191. Springer, 2009.
  * [38] C. Peikert. A decade of lattice cryptography. Foundations and trends in theoretical computer science, 1-90, 2016.
  * [39] C. Peikert and B. Waters. Lossy trapdoor functions and their applications. SIAM J. Comput., 40(6):1803-1844, 2011. Preliminary version in STOC 2008.
  * [40] O. Regev. On lattices, learning with errors, random linear codes, and cryptography. J. ACM, 56(6):1-40, 2009. Preliminary version in STOC 2005.
  * [41] O. Regev. The learning with errors problem. In IEEE Conference on Computational Complexity, 191-204, 2010.
  * [42] R. L. Rivest, L. Adleman and M. L. Dertouzos. On data banks and privacy homomorphisms. Foundations of secure computation, 4(11):169-180, 1978.
  * [43] N. P. Smart and F. Vercauteren. Fully homomorphic SIMD operations. Designs, Codes and Cryptography, 71(1):57-81, 2014. Preliminary version in ePrint Report 2011/133.
  * [44] L. C. Washington. Graduate texts in mathematics—Introduction to cyclotomic fields. Springer-Verlag, New York Heidelberg Berlin, 1980.
  * [45] M. Yagisawa. Fully homomorphic encryption without bootstrapping. In IACR Cryptology ePrint Archive, 2015.
  * [46] M. Yagisawa. Fully homomorphic encryption on octonion ring. In IACR Cryptology ePrint Archive, 2015.
  * [47] Z. Zheng. Modern cryptography volume 1—A classical introduction to informational and mathematical principle. Springer, 2022.
  * [48] Z. Zheng, K. Tian and F. Liu. Modern cryptography volume 2—A classical introduction to informational and mathematical principle. Springer, 2022.
  * [49] Z. Zheng, F. Liu and M. Chen. On the high dimensional RSA algorithm—A public key cryptosystem based on lattice and algebraic number theory. IJLRET, 8(9):1-16, 2022.
  * [50] Z. Zheng, F. Liu, W. Huang, J. Xu and K. Tian. A generalization of NTRUEncrypt—Cryptosystem based on ideal lattice. Journal of Information Security, 165-180, 2022.
  * [51] Z. Zheng, F. Liu, Y. Lu and K. Tian. Cyclic lattices, ideal lattices and bounds for the smoothing parameter. Journal of Information Security, 272-293, 2022.
  * [52] Z. Zheng and K. Tian. On the LWE cryptosystem with more general disturbance. Journal of Information Security, 127-139, 2022.