An Unbounded Fully Homomorphic Encryption Scheme Based on Ideal Lattices and Chinese Remainder Theorem ()
1. Introduction
In 1978, Rivest, Adleman, and Dertouzos [1] 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
, where
is the plaintexts space, and
is the ciphertexts space, f is the encryption function depends on public keys, and
is the decryption function depends on secret keys. Suppose that
and
are two commutative rings, and
then f is called a fully homomorphic encryption, or FHE. Under a FHE f, for any polynomials
, it is easy to see that
where
is the corresponding polynomial over
. Since all elementary functions can be approximated by polynomials, 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 [3] [4] proposed a candidate FHE scheme based on ideal lattices. The candidate FHE scheme means a 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 [5] - [16] . 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 [2] 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 [3] . In a sequence of work, Brakerski and Vaikuntanathan [7] [8] gave a “second generation” of FHE constructions based on LWE distribution [17] [18] . In 2013, Gentry, Sahai, and Waters [19] proposed another interesting LWE-based FHE scheme that has 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 detail here.
· BV FHE Scheme Let
be two positive integers such that
. In the BV system, a secret key s is an LWE secret and encrypts a plaintext
using an LWE sample for modulus q. We use the most significant bit encoding to obtain a ciphertext c by
where
is a discrete Gauss distribution over
, and is the rounding of a real number x to the nearest integer. We use secret key s to decrypt the ciphertext c by
Obviously, one has
(see [20] ). To explain this scheme is a somewhat FHE scheme, we may use the least significant bit encoding of the message (The equivalence of two encodings is referred to in Appendix A of [21] ). In fact, the ciphertext c satisfies
To decrypt c, one just compute
, lifts the result to its unique representative m in
, and the outputs
. 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 [22] [23] [24] [25] [26] . The heart of the GSW scheme is the following additive and multiplicative homomorphisms for tags and trapdoors. Let
be LWE samples with a secret key
, and for
, let
where
, G is the block-diagonal gadget matrix of dimension
,
are random Gauss matrices over
, and
(see p.50 of [2] ). Since
is a trapdoor with a tag
for matrix
, it is easy to verify that
and
In other words,
is a trapdoor with a tag
for matrix
, and
is a trapdoor with a tag
for matrix
. 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 [27] [28] particularly suitable for combinatorial operations on individual slots and tolerating large noise and thus, large multiplicative depth; (2) B/FV [5] [29] [30] allowing to perform large vectorial arithmetic operations as long as the multiplicative depth of the evaluated circuit remains small; (3) HEAAN [31] [32] —a mixed encryption scheme shown to be very efficient for floating-point computations. We introduce these schemes slightly in detail 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
and produces ciphertexts in
. The other two schemes are:
TRGSW encrypts elements of the ring
(integer polynomials) with bounded
-norms (of the corresponding vectors in
under the natural identification
).
TRLWE encrypts elements
of the
-module
that can also be viewed as elements of
via the natural bijection
.
There is an external product
depending on a noise parameter
(see Corollary 3.14 [28] ) which yields a FHE module structure on the schemes TRGSW and TRLWE.
In TFHE, TLWE ciphertexts of a message
have the form
where
is the secret key,
is uniformly random and
is sampled according to a noise distribution centered at zero. Similarly, for TRLWE, ciphertexts of
are of the form
where
,
is uniformly random and
.
The decryption in TLWE (resp. TRLWE) uses a secret
-Lipschitz function (here,
is small and we mean “with respect to the
-norm on the torus”)
(resp.
) called phase parametrized by a small (often binary) secret key
(resp.
) and defined by
(resp.
). The fact that the phrase is a
-Lipschitz function for small
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
, the decryption
and the noise parameter
are the mean and the standard deviation of the phase function
, 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
for some integer p (typically a power of 2 or a prime number). A message
is encrypted on a quotient ring
(for a larger modulus q) as a ciphertext
where
is chosen uniformly at random and b is sampled from
. Here,
is the discrete Gaussian distribution over
centered at
with standard deviation
(discrete means that the values are integers only). In addition,
is the secret key.
Homomorphic addition of two ciphertexts
and
is achieved by component-wise addition. The idea behind the homomorphic multiplication of two ciphertexts
and
is a technique referred to as relinearization: one first lifts
to
where each coefficient is lifted to
and then views of
as being expressed as a linear polynomial on s (i.e.,
). One then computes the quadratic polynomial corresponding to the product, namely
, and uses the relinearization described in [30] to write this product as
and determine the coefficients
.
The noise amplitude grows by a small factor
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
so that the subsequent operations continue on smaller ciphertexts.
· HEAAN Scheme In this scheme, the message space is the subset of
containing all elements of norm
for some bound B, where the norm of an element
is defined as
. Here
is the minimal lift of x, i.e., coefficients lifted to
. The message is decrypted up to a constant number of the least significant bits which are considered as noise.
A HEAAN ciphertext is also a Ring-LWE pair
where
is uniformly random and b is equal to
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
noise, the product is a message bounded by B2 with noise
, 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
(see [32] ). 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 [33] proposed a practical hybrid solution for combining and switching between the above three Ring-LWE-based FHE schemes. They achieved it by first mapping the different plaintext 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 [34] described a fully homomorphic encryption scheme over the integers (see also [9] [10] [11] ). 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 those integers instead of ideal lattices. However, the public key was too large for any practical system. In [10] and [11] , the authors reduced the public key site
from
to
by encrypting with a quadratic form in the public key elements, instead of a linear form.
It is the latest scheme, without using noise reduction techniques (see [35] ). In 2015, Yagisawa proposed a non-associative octonion ring over a finite field fully homomorphic encryption scheme [36] . This scheme’s 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 [37] . Liu presented a symmetric fully homomorphic encryption scheme based on non-commutative rings [38] . Liu’s scheme provides an arbitrary number of additions and multiplications, and the correct decryption in contempt of the amount of noise reduction mechanisms and based on the approximating-GCD complexity. Noise-free symmetric fully homomorphic encryption scheme was proposed by Li and Wang [39] that used matrices over non-commutative rings. Needless to say, those noise-free schemes are not the solutions to problems of the FHE scheme, because of using non-associative and non-commutative rings for the plaintexts and ciphertexts.
1.5. Our Contribution
Our contribution to the unbounded FHE scheme is straightforward, 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 a rational solution to open problems on fully homomorphic encryption.
Our solution comes in three steps. First, we provide a general noise-free construction based on ideal lattices and the 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
, where
is the one-dimensional modulus of each ideal lattice
(
). The ciphertext space
is a commutative ring with the addition and convolutional product
of vectors, needless to say, the algebraic structures for homomorphic computation are simplest. The main ideal is to set up a multiplicative operation for
, such that
becomes a commutative ring, therefore, one views
both as an ideal and as a lattice in
, in particular,
becomes a quotient ring. Working with the ring
, we can efficiently utilize the Chinese Remainder Theorem for generating of public key. Next, we provide a probabilistic algorithm for public keys, so that the encryption algorithms are secure against indistinguishable under chosen-plaintext attacks, namely, our scheme is IND-CPA secure. Finally, we discuss the IND-CCA security 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 [2] . In the last section of this paper, we provide a practical system based on some basic results from cyclotomic fields [40] . 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 to an algebraic equation with a 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.
The generalization of compact knapsack problem for arbitrary ring may be described as follows: given m ring elements
and a target value
, find coefficients
such that
. 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
(see [41] and [42] ). Micciancio [42] 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 without Disturbance
Let
be the ring of integer coefficients polynomials with variable x,
, and
with
be a given polynomial,
be the principal ideal generated by
in
,
be the quotient ring. Let
be the n dimensional Euclidean space, and
be all of integer vectors in
. We use column notation for vectors in
.
There is a one to one correspondence between the quotient ring
and all the integer vectors
:
(2.1)
we write
, or
. Since
,
is an isomorphism of additive groups in fact. To regard
as an isomorphism of rings, we need to define a multiplicative operator in
. To do this, let the rotation matrix
be given by
where
is the unit matrix of
dimension.
DEFINITION 2.1 For any
, the ideal matrix generated by
is defined by
Some basic properties about ideal matrix may be described as the following lemma, its proof is referred to Lemma 2.5 of [43] , or Lemma 5.2.4 of [44] .
Lemma 2.1 Let
and
be any two vectors in
, then one has
(i)
;
(ii)
;
(iii)
;
(iv)
;
where
is the determinant of
,
, and
are n roots of
.
By (iv) of Lemma 2.1,
is an invertible matrix if and only if
and
have no common roots in complex numbers field. Now, we may define a multiplicative operator in
in terms of the ideal matrix.
DEFINITION 2.2 Let
be two integer vectors, we define the convolutional product
by
Obviously, under the convolutional product
,
becomes a commutative ring with the unit element
, since
and
Sometimes, we write this ring by
.
Lemma 2.2 The correspondence
given by (2.1) is a ring isomorphism between
and
, namely, we have
Proof. By Lemma 2.4 of [43] or Lemma 5.2.5 of [44] , it is easy to see that
The conclusion follows immediately.
According to the definition of ideal lattices [2] [42] [45] [46] [47] [48] , an ideal lattice
, just is an ideal of
, we view
both as an ideal of
and as a lattice in
, in particular,
is a quotient ring.
A lattice
is a discrete additive group of
[46] [49] [50] , we write
as usual, where
is the generated matrix or a basis of I. All lattices we discuss here are the full rank lattice, it means that
. If
, then I is called an integer lattice. The Hermite Normal Form base B [40] [51] for an integer lattice is an upper triangular matrix
satisfying
(
) and
It is known that there is a unique HNF basis for an integer lattice and its Gram-Schmidt orthogonal basis is a diagonal matrix, more precisely, if
is the HNF basis of an integer lattice,
is the corresponding orthogonal basis obtained by Gram-Schmidt orthogonal method, then
is a diagonal matrix (see Lemma 7.26 of [40] ).
DEFINITION 2.3
is called the one dimensional modulus of an ideal lattice
, and denoted by
.
Let
be an ideal lattice, to obtain a set of representative elements for the quotient ring
, we use the notation of orthogonal parallelepiped due to Micciancio [51] . The following lemma is referred to as Lemma 7.45 and (7.131) of [40] , or §4.1 of [51] , and a proof will be appeared in Lemma 2.6 below.
Lemma 2.3 Suppose that
is a full rank ideal of
, B is the HNF basis of I, and
is the corresponding orthogonal basis, then a set of representative elements of the quotient ring
is
and
is called the orthogonal parallelepiped of I.
Next, we turn to discuss the ideal lattices and the ring
. Let
be a given vector, the principal ideal lattice
is a principal ideal generated by
in
. It is easily verified that
Thus, the generated matrix of a principle ideal lattice
just is the ideal matrix generated by
.
The operations among the ideal lattices in
are defined as usual, in particular, the addition and multiplication for two ideals, I and J are defined by
and
Since
,
and
are also the ideals of
, therefore, all of them are ideal lattices.
DEFINITION 2.4 Let
,
be two ideal lattices. If
, we call I and J to be relatively prime, and denoted by
.
It is easy to see that two ideal lattices I and J are relatively prime, if and only if there are
and
such that
, where e is the unit element of
.
To construct a FHE scheme, we utilize the Chinese Remainder Theorem in the ring
, which is a well-known theorem in Number Theory.
THEOREM 1 (Chinese Remainder Theorem) Let
be pairwise relatively prime ideal lattices in
, and
be m target vectors in
, then there exists a common solution of the following congruences:
and the solution of
is a unique modulo-ideal lattice
.
For arbitrary pairwise relatively prime lattices
, it is known that
By the above Chinese Remainder Theorem, one has the following consequence immediately.
Corollary 2.1 Suppose that
are pairwise relatively prime ideal lattices in
, then we have the following ring isomorphism
(2.2)
The right-hand side of (2.2) is the direct sum of m quotient ring
(
), and the addition and multiplication of
are given by
and
Proof. Since
are pairwise prime, by Theorem 1, there are m vectors
(
) in
such that
For any
, by Theorem 1 again, there is a unique solution
such that
We define
, which is the ring isomorphism from
to
as we desired. Using
, one may clearly write down f by
Let
be another element of
, it is easy to see that
To verify
, since
It follows that
By the definition of f, we have
This proves that f is a ring isomorphism.
We extend the inverse isomorphism
to the whole space
by
:
where
is the natural homomorphism from
to its quotient ring
. It is easy to see that
is a homomorphism from
to
, and
(2.3)
will play the role of decryption in our scheme, and always write down
by
in the following discussion.
Since
is a ring, we wish to embed this ring into
. To do this, we define an embedding mapping from
to
by
(2.4)
Lemma 2.4 Under the embedding mapping
,
becomes a subring of
, namely, for any
,
, one has
and
.
Proof. By (2.4), we have
and
the lemma follows at once.
Lemma 2.5 Let
be an ideal lattice, and
be its one dimensional modulus given by DEFINATION 2.3. Then, for any
, we have
Proof. By assumption, I is a full rank lattice and its HNF basis may be written by
If
, then there is a vector
such that
Since
, and
, we have
, similarly, since
, it follows that
. Therefore, we have
, and
. Conversely, if
, then
, and
The assertion is true.
For arbitrary given pairwise relatively prime ideal lattices
, one uses the Chinese Remainder Theorem to generate the public key
, where
such that
(2.5)
where
is the unit element of
.
Now, we describe a scheme for unbounded fully homomorphic encryption as follows.
To verify the homomorphic addition and multiplication for the above scheme, by Lemma 2.4,
is a subring of
. By Lemma 2.5, we can embed the direct sum
into
, so that
also is a subring of
. Therefore, the property of fully homomorphism directly follows by
(or
) a ring homomorphism:
↪
More precisely, let
, and
be arbitrary two ciphertexts, where
, and
, we note that for all i,
,
By Lemma 2.4, it follows that
Therefore, by Lemma 2.5, we have
and
This is an unbounded fully homomorphic encryption as we desired.
How to decrypt the ciphertext
using the secret key
in our algorithm for the general unbounded FHE scheme? Here we give a lemma to show that there is only one vector
in the orthogonal parallelepiped
of
such that
, and give an algorithm to calculate
in detail.
Lemma 2.6 Given an ideal lattice I, for any vector
, there is only one vector
such that
.
Proof. Assume
is the HNF basis of I, and
is the corresponding orthogonal basis of B. Write c as the linear combination of
, i.e.
Let
,
, then
. Next, we prove that there is only one group of integers
such that
, i.e.
Firstly, we determine the value of
. Since
therefore, when
, here
means the largest integer no more than real number x, we have
. Secondly, we determine
. Note that
so there is only one integer
such that
. Similarly, we could determine any
,
,
hence, there is only one integer
such that
,
. Above all, there is only one vector
such that
.
Based on Lemma 2.6, we give an algorithm for the decryption of our general FHE scheme.
To create an efficient algorithm for generating the secret key of the above unbounded FHE scheme, we assume that
is an irreducible polynomial, so that the principal ideal
is a prime ideal in
, and the quotient ring
is a domain, equivalently,
becomes a domain. Under this assumption, we see that arbitrary many pairwise relatively prime ideals in
almost come in automatically, we describe the process as follows.
To construct an efficient algorithm for finding public key, we first show that
Lemma 2.7 Suppose that
are pairwise relatively ideals in
, and each
is a principal ideal generated by
, namely,
. Let
Then for every
, there is a vector
such that
Proof. Since
are pairwise relatively prime by assumption, we have
In other words, we have
, or
Therefore, there is a vector
such that
, and we have Lemma 2.7 immediately.
How to find the vector
defined by Lemma 2.7? We introduce a polynomial algorithm to obtain
(
), and generate the public key
by taking
(
).
3. A Probabilistic Algorithm for Encryption
In our general construction for unbounded FHE, the encryption formula (2.6) is deterministic, so it is not IND-CPA secure, i.e. it is not secure against indistinguishable under chosen-plaintexts attack. To improve the encryption algorithm, we require to add some noises to the generating algorithm for public keys.
Let
be an arbitrary multiple discrete probability distributions over
, where
be any discrete distribution over
. Let
and
, so that
are the samples drawn from the distribution
. By Theorem 1, we have m vectors
in
such that
(3.1)
where e is the unit element of
and
is the embedding of
given by (2.4). According to the probabilistic distribution
, we generate the public keys
with noises by
(3.2)
where
given by (2.5), and
given by (3.1). Therefore, the encryption algorithm (2.6) in our general construction (see algorithm 1) becomes the following formula for any
,
(3.3)
Lemma 3.1 For arbitrary samples
drawn from the distribution
, we have (
)
Proof. By (2.5), for every
we have
, and
when
, it follows that
The dramatic effect of the above lemma is that the probabilistic encryption function
shares the same decryption formula (see Algorithm 2) with the deterministic encryption algorithm f given by (2.6). In other words, there are no noises occurred in the decryption procedure, although the encryption algorithms with disturbance. It explains why we may obtain an unbounded FHE scheme without Gentry’s bootstrapping transformation technique.
Next, we discuss how to randomly find the public keys
according to the probabilistic distribution
, the following lemma tells us how to obtain the error term
.
Lemma 3.2 Let
, and
be given by Algorithm 4, then we have
(3.4)
where
is the embedding of
.
Proof. Since
, and
for
, it follows that
We have the lemma immediately.
Now, we give the final algorithm for the unbounded FHE scheme as follows.
Because of the decryption procedure without noises, and the homomorphic computation on ciphertexts, we claim that the above Algorithm 5 is the unbounded FHE scheme as we desired.
Remark Since the probabilistic distribution
is arbitrary, an alternative method to add noises to public key
may be described as follows: Randomly find m vectors
in
, and put
(3.6)
and then let
. Thus, we obtain the public key
with noises, which guarantees the encryption formula (2.6) is not deterministic.
To discuss the security of this scheme, we observe that all risks come from the encryption algorithm (3.5). This algorithm contains some noises for public keys and guarantees the scheme could resist CPA attack. We describe the other risk as a generalized compact knapsack problem over the ring
as follows:
(3.7)
where
are given m vectors in
,
is a target vector, and
. Next section, we will show that the security of our scheme is solely under a worst-case complexity assumption, this is also a solution to open question 11 of [2] .
4. The Generalized Compact Knapsack Problem over
In this section, we discuss the security of our scheme based on the general compact knapsack problem over the ring
. In [42] , Micciancio has proved that if we can solve the knapsack problem over
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 [48] , and then solving the knapsack problem from
to
. 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 4.1 Let L be a full rank lattice,
is a parameter of n,
,
problem is to find an r such that
where
and
.
DEFINITION 4.2 Let L be a full rank lattice,
be n linearly independent lattice vectors.
is the orthogonal basis corresponding to S by the Gram-Schmidt method. We define
Here we give our main result to show that the generalized knapsack problem over
is at least as hard as the covering radius problem for any n dimensional full rank ideal lattice.
THEOREM 2 Let
,
,
,
,
,
, if we can solve the knapsack problem (3.7), then there is a positive probabilistic polynomial algorithm solving the covering radius problem
for any n dimensional full rank ideal lattice L.
Remark In the original work of Micciancio [42] , the parameter
is bigger than
, we require
, where W is given by
. The maindifference is to estimate the length of convolutional product
for any two vectors
and
. It is clearly that
in the case of circulant lattice, but it is non-trivial in the case of ideal lattices.
Lemma 4.1 For any
, we have
where W is defined in Theorem 2.
Proof. We first prove
. Let
, then
So
. Similarly,
In the same way, we can get
,
. Let
, it follows that
We complete this proof.
Let
be a full rank ideal lattice,
,
is a standard orthogonal basis,
is a set of n linearly independent vectors. We define the parameter
(4.1)
According to Lemma 1.6 in Chapter 3 in [44] , there is a lattice vector
such that
, let
. It follows that the lattice
generated by
satisfies
according to Lemma 2.1 in Chapter 3 in [44] . Therefore,
is an additive subgroup in
. Randomly choose mk elements
in the quotient group
, the integral vectors
of
is defined by
Let
Assume
. Since the knapsack problem (3.7) is solvable on
, it could also be solved on
. Let
and
be two different integer matrices such that
,
,
,
. We define
and
(4.2)
Then
is a lattice vector in the given ideal lattice
(
,
), and
is also a lattice vector in
based on Lemma 2.2 in Chapter 3 in [44] .
The next lemma gives an estimation of the length of
, which has some differences from the proof of Micciancio’s.
Lemma 4.2 Let
be a set of n linearly independent vectors in the full rank ideal lattice L. Denote
,
is the lattice vector defined in (4.2), then
Proof. This proof is similar to that of Lemma 2.3 in Chapter 3 in [44] except some computations about the parameters. We prove
first. Basedon the definition of
in (4.2),
(4.3)
Let
, where
is defined in (4.1). Then
, and
Since, we have
combine with Lemma 4.1, we get
Based on (4.3), we know
Since
We can get
So we complete the proof of Lemma 4.2.
Based on the above lemmas, Theorem 2 follows directly from Micciancio’s method [42] . From Theorem 2, we can see that the general compact knapsack problem over
is at least as hard as the covering radius problem
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 [2] .
5. A Practical System
As an example, we introduce a practical system for FHE using some basic results about the cyclotomic field [50] . Suppose that p is an odd prime number and
is the cyclotomic field, where
is a primitive p-th root of the unit.
Let
It is known that
is the ring of algebraic integers of field
. Therefore
is a Dedekind domain (so we have unique factorization into prime ideals, etc. see Proposition 1.2 of [50] ).
To construct a commutative ring for
, we select
. Obviously,
is the minimal polynomial of
. Let
, then we obtain a ring
in terms of
and the rotation matrix
, it is easy to see that (see (3.2) of [43] )
Thus,
becomes a Dedekind domain.
For any integer
, we define an integer vector
by
The principal ideal
generated by
is denoted by
Lemma 5.1 If
and
are two different prime numbers, then
and
are relatively prime ideal lattices in
.
Proof. Suppose that q is a prime number. Since
, we see the polynomial
, which is the type polynomial of Eisenstein, thus it is an irreducible polynomial over
. Regarding
as the polynomial of
, clearly, it is also an irreducible polynomial in
. By assumption,
and
are different prime numbers, we show that the principal ideals
, and
are relatively prime ideals in
. Since
is a Dedekind domain, if
and
are not relatively prime, then, there exists a prime ideal P in
such that
It follows for any positive integer
that
It is known that three exists a positive integer
, such that
is a principal ideal, we thus have
In other words, we have
, and
. However, this is impossible, since
and
are two irreducible polynomials in
, and
.
This proves that
and
are relatively prime ideals in
. Equivalently,
and
are two relatively prime ideal lattices in
.
Lemma 5.2 The one dimensional modulus of the principal ideal
is
Proof. It is not hard to compute that
. Since the polynomial
is an irreducible polynomial over
, we have the assertion of lemma immediately.
According to Lemma 5.1 and Lemma 5.2, we obtain a generating algorithm for the secret key as follows:
To get an attainable algorithm for public key, we define m vectors
by
Lemma 5.3 For every vector
, there is a vector
such that
where
is the unit element of rimg
.
Proof. By lemma 5.1,
are pairwise relatively prime ideals, hence we have
. In other words, we have
, or
Therefore, there is a vector
such that
. We have Lemma 5.3.
We propose a polynomial algorithm to find the vector
appeared in Lemma 5.3, and then put
getting the public key
. The polynomial algorithm for finding vector
like follows.
Now, we describe an attainable algorithm for our FHE Scheme based on cyclotomic field as follows.
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
. It is equivalent to find a solution to the algebraic equation with a high degree of
For a given target value
. 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
of
.
6. Conclusions
In this work, we construct the first unbounded fully homomorphic encryption scheme without the bootstrapping transformation technique. In the encryption algorithm (3.5), we see that
for any
. Therefore, the problem of security may transfer to the standard Ring-SIS problem: suppose that
, where
is given by (3.2),
is a target vector, find
such that
, and
. Let q be a sufficiently large positive integer, if one can show that every column
of
is uniformly random vectors in
, then this problem can be changed to an inhomogeneous version of the SIS problem, which is to find a short integer solution to
. It is not hard to show that the homogeneous and inhomogeneous problems are essentially equivalent to typical parameters.
According to Ajtai’s seminal work [23] [41] , the hardness of the SIS problem is relative to the worst-case lattice problem. More precisely, for any
, any
, and any sufficiently large
, solving
with non-negligible probability is at least as hard as solving the decisional approximate shortest vector problem
for some
(also see [52] and Theorem 4.1.2 of [2] ). Perhaps, we may find another proof that the security of our FHE scheme is solely under a worst-case complexity assumption.
On the other hand, the fully homomorphic signature is the dual question of the fully homomorphic encryption, we will develop a scheme for a fully homomorphic signature in another article.
Acknowledgements
This work was prepared during our visit to Henan Academy of Sciences, the authors appreciate Professor Tianze Wang and Professor Jingluo Huang for their invitation and hosting. This work was supported by the Fundamental Research Funds for the Central Universities, and the Research Funds of Renmin University of China (No. 2020030254).