# Generalized Bootstrapping Technique Based on Block Equality Test Algorithm

Authors: Xiufeng Zhao; Ailan Wang
Journal: Security and Communication Networks
 (2018)

---

## Abstract

With the rapid development of cloud computation and big data, the data storage and outsource computation are delegated to the untrusted cloud, which has led to a series of challenging security and privacy threats. Fully homomorphic encryption can be used to protect the privacy of cloud data and solve the trust problem of third party. The key problem of achieving fully homomorphic encryption is how to reduce the increasing noise during the ciphertext evaluation. Bootstrapping procedure can refresh ciphertext with large error, such that the resulting ciphertext has potentially smaller error and allows being continuous homomorphic evaluation. In this paper, we investigated the bootstrapping procedure used to construct fully homomorphic encryption scheme. We proposed a new concept of block homomorphic equality test algorithm and gave an instance based on the FH-SIMD scheme. Furthermore, based on the block homomorphic equality test algorithm, we proposed a faster bootstrapping procedure with smaller bootstrapping keys. Both theory analysis and experiment simulation validate high performance of our bootstrapping algorithm.


---

## Body

## 1. Introduction

Rapidly developing cloud storage and computation platform allow user delegate data outsource to the cloud server. Cloud computing has the characteristics of data concentration, resource sharing, highly interconnecting, fully opening, etc. It breaks the information island of traditional IT field; meanwhile, it brings even more serious security problems. To protect the privacy of data and the confidential of business secret, it is necessary to encrypting the upload data. However, it is difficult to process ciphertext for traditional encryption algorithm, and this promoted the improvement and development of fully homomorphic encryption (FHE). The prominent advantage of the fully homomorphic encryption is that it can solve ciphertext evaluation problem.In 2009, Gentry [1, 2] constructed the first fully homomorphic encryption scheme using ideal lattice, which supports arbitrary depth circuit evaluation. Since then many fully homomorphic encryption schemes have appeared involving new mathematical concepts and NP hard problems and improving efficiency, such as FHE from LWE [3], Ring LWE [4], Integer [5], and LWR [6].In PKC 2010, Smart and Vercauteren [7] proposed a variant of Gentry’s scheme with relatively small key and ciphertext sizes. Packing messages allows us to apply single-instruction-multiple data (SIMD) homomorphic operations to many encrypted messages. Smart and Vercautren [8] showed that applying the Chinese reminder theorem (CRT) to number fields partitions the message space of Gentry’s FHE scheme into a vector of plaintext slots, resulting in a substantial speed-up, the scheme denoted as FH-SIMD. In the work, they explained that the SIMD operations could be utilized to perform many higher level operations, such as performing AES encryption homomorphically and searching an encrypted database on a remote untrusted server.Gentry, Sahai and Waters [9] constructed a simple homomorphic encryption scheme from learning with errors in Crypto 2013, called GSW scheme. In this work, they proposed a new technique for building FHE scheme via the approximate eigenvector method. The homomorphic addition and multiplication In GSW scheme are just matrix addition and multiplication, which makes GSW scheme both asymptotically faster and easier to understand. Otherwise, GSW scheme operates single bit once encryption and it is required to take heavy cost for evaluating a large number of ciphertexts.Bootstrapping technique is a central technique on fully homomorphic encryption (FHE), which converts “somewhat homomorphic” encryption (SHE) scheme into a fully homomorphic one. That is, bootstrapping procedure homomorphically evaluating the SHE scheme’s decryption function on a ciphertext that cannot support any further homomorphic operations, and produces a new one that encrypts the same message and can handle more homomorphic operations.Bootstrapping procedure is computationally very expensive, and it is becomes the main bottleneck of fully homomorphic encryption practicability. Therefore, there are lots of works try to improve its efficiency. Gentry, Halevi, and Smart [9] proposed a simpler approach that bypasses the homomorphic modular-reduction bottleneck by working with a modulus very close to a power of two. In Crypto 2013, Alperin-Sheriff and Peikert [10] gave entirely algebraic algorithm for bootstrapping in quasilinear time. They gave a method for homomorphically evaluating a class of structured linear transformation using “ring-switching” procedure, resulting in evaluating the decryption function efficiently.Recently, Alperin-Sheriff and Peikert [11] proposed generalized bootstrapping technique using GSW scheme. The homomorphic decryption of FHE scheme from LWE concludes inner production and rounding operation, and homomorphic equation text algorithm is the key subprocedure of the rounding operation. Embedding the additive group Z
q into the symmetric group of q
×
q permutation matrices is another technique used in the work [11].In Eurocrypt 2015, Ducas and Micciancio [12] gave an efficient bootstrapping technique by encoding the cyclic group Z
q into the group of roots unity: i
⟼
X
i, where i is primitive q
-
t
h root of unity. This allows implementing a bootstrapping procedure similar to the work of Alperin-Sheriff and Peikert [11], but where each cyclic group element is encoded by a single ciphertext, rather than a vector of ciphertext, this efficiently reduces the size of bootstrapping key.In AsiaCrypt2016, Chillotti et al. constructed an efficient bootstrapping fully homomorphic encryption scheme, called TFHE [13]. Its time of running bootstrapping is less than 0.1 second. In AsiaCrypt2017, Chillotti et al. [14] optimized the multiple addends of work [13], and made the bootstrapping time reduced 13 milliseconds. 2018, Zhou et al. [15] optimized the serial addends to parallel addends, and the speed of single bootstrapping gate is faster that of work [14]. TFHE scheme and the optimized version both are single bit bootstrapping procedure [13–15]. Although a lot of effort is being spent on improving bootstrapping, the efficient and effective method has yet to be developed. And how to construct efficient multibit bootstrapping procedure is worth further study.Our Results. In this paper we investigate the homomorphic equality test algorithm in bootstrapping procedure and proposed the concept of block homomorphic equality test algorithm B_Eq? and give an instance based on the FH-SIMD scheme. Furthermore, we proposed a faster bootstrapping procedure based on the block homomorphic equality test algorithm. Both theory analysis and experiment simulation validate the higher performance of our bootstrapping algorithm than that of Alperin-Sheriff and Peikert’s work [11].Organization. In Section 2, we describe some preliminaries on the field and homomorphism, and the concept of generalized bootstrapping technique. In Section 3, we proposed block homomorphic equality test algorithm B_Eq? and give a faster bootstrapping procedure based on B_Eq? algorithm. In Section 4, we give theory analysis and experiment simulation. We give conclusions in Section 5.


## 2. Preliminaries

### 2.1. Field and Homomorphism

LetF
(
x
)
∈
F
2
x be a monic polynomial of degree N, which decomposed to exactly l distinct irreducible factors as follows:(1)
F
x
=
∑
i
=
1
l
F
i
x
,where every polynomial F
i
(
x
) has degree D
=
N
/
l.LettingA denote the algebra A
≔
F
2
[
x
]
/
(
F
), we can get the natural homomorphism via Chinese Remainder Theorem (CRT):(2)
A
≅
F
2
x
F
1
⊗
⋯
⊗
F
2
x
F
l
≅
F
2
D
⊗
⋯
⊗
F
2
D
.Forn
∣
D, the finite field K
n
≔
F
2
n is a subfield of F
2
D. Let F
2
x
/
K
n
x denote a fixed canonical representation of K
n, where K
n
x
∈
F
2
[
x
] is some irreducible polynomial of degree n
. Let ψ be a fixed root of K
n
x in the algebraic closure of F
2. Since K
n is contained in each of L
i
≔
F
2
x
/
F
i, there is a homomorphic embedding as follows:(3)
Ψ
n
,
i
:
K
n
→
L
i
α
ψ
↦
α
σ
n
,
i
θ
i
,where σ
n
,
i
(
θ
i
) is a root of K
n
x in algebra L
i, that is,(4)
K
n
σ
n
,
i
x
≡
0
m
o
d
F
i
x
.According to CRT and the above homomorphic embedding, we can obtain a homomorphic embedding ofK
n
l into the algebra A which defined as follows:(5)
Γ
n
,
l
:
K
n
l
→
A
k
1
ψ
,
…
,
k
l
ψ
↦
∑
i
=
1
l
k
i
σ
n
,
i
x
·
H
i
x
·
G
i
x
.where the polynomials H
i
(
x
) and G
i
(
x
) is obtained by CRT and computed as follows:(6)
H
i
x
←
F
x
F
i
x
,
G
i
x
←
H
i
x
-
1
m
o
d
F
i
x
.From the above definition of Γ
n
,
l, we can see that Γ
n
,
l maps a vector of l binary polynomials k
1
ψ
,
…
,
k
l
ψ each of degree less than n, into a single polynomial a
(
x
) of degree less than N. The map Γ
n
,
l defines an isomorphism between K
n
l and Γ
n
,
l
K
n
l, so the inverse map Γ
n
,
l
-
1 is well defined from Γ
n
,
l
(
K
n
l
) to K
n
l. We can represent Γ
n
,
l
-
1 as follows:(7)
Γ
n
,
l
-
1
:
Γ
n
,
l
K
n
l
⊆
A
→
K
n
l
a
x
↦
a
x
m
o
d
F
1
x
,
…
,
a
x
m
o
d
F
l
x
.There are two methods to compute elements in K
n
l: one method is computes component wise on vectors of l elements in K
n; the other concludes three process, firstly, mapping all the inputs to the algebra A by Γ
n
,
l; secondly, performing computations in algebra A; finally, mapping the results back to K
n
l by Γ
n
,
l
-
1. Furthermore, the fully homomorphic encryption scheme FH-SIMD performs one evaluation forl elements in K
n using the algebra A.


### 2.2. Generalized Bootstrapping Technique

Gentry firstly proposed bootstrapping technique, which may transform a somewhat homomorphic encryption scheme to a fully homomorphic encryption scheme. Subsequently, Jacob Alperin-Sheriff and Chris Peikert [11] proposed generalized bootstrapping technique. The generalized bootstrapping technique involves two encryption schemes, outer encryption scheme and inner encryption scheme. It performs decryption procedure of inner encryption scheme using outer encryption scheme, resulting in reducing error in ciphertext. The generalized bootstrapping technique allows that the outer encryption is different from the inner one, realizing that we can design corresponding outer encryption scheme for the concretely inner encryption scheme, such that it effectively performs the decryption circuit of inner encryption scheme. Therefore, the generalized bootstrapping is more efficient than the ordinary one.


### 2.3. The Decryption of FHE from LWE

The decryption of all fully homomorphic schemes based on LWE involved computing inner production and rounding, that is, input secret keys
∈
Z
q
d and binary ciphertext c
∈
0,1
d; the decryption algorithm is written as(8)
D
e
c
s
,
c
=
s
,
c
2
∈
0,1
,where the modular rounding function ·
2: Z
q
→
{
0,1
} indicates whether its arguments is “far from” or “close to” 0 (modulo q), and the modulusq and the dimensiond can both be made as small as quasi-linear O
~
(
λ
) in the security parameter via dimension-modulus reduction [3], while still providing provable 2
λ security under conventional lattice assumption. The inner product s
,
c is just summing the elements of vector s selectively, that is,(9)
s
,
c
=
∑
c
j
=
1
s
j
.Supposing that s
,
c
=
v, the algorithm rounding can be interpreted by iteration as(10)
v
2
=
∑
x
∈
Z
q
s
.
t
.
x
2
=
1
x
=
v
,where [
x
=
v
] denotes the equality test algorithm, when x is equality to v, [
x
=
v
] outputs 1; otherwise, [
x
=
v
] outputs 0.Now, we give the decryption algorithm of FHE based LWE in the ciphertext state. During the bootstrapping procedure, the ciphertext of secrets
∈
Z
q
d is written by s
-
=
s
1
-
,
…
,
s
d
- as bootstrapping public key. The inner product in the ciphertext state is denoted as v
-
=
s
-
,
c
=
∑
c
j
=
1
s
-
j. And the rounding algorithm in the ciphertext state is denoted as(11)
v
-
2
=
⊞
x
∈
Z
q
s
.
t
.
x
2
=
1
x
=
v
-
,where “⊞” denotes the homomorphic addition on the ciphertext space and [
x
=
v
]
- indicates the homomorphic equality test algorithm; it outputs the ciphertext of 1 if and only if x
=
v; otherwise it outputs the ciphertext of 0. We let 1
- denote the ciphertext of 1 and 0
- denote the ciphertext of 0.


### 2.4. Generalized Bootstrapping Procedure of FHE from LWE

Assume that the binary ciphertext to be bootstrapped isc
∈
0,1
d, the secret key is s
∈
Z
q
d, and the dimension d and the module q are enough small (q
,
d
=
Q
~
λ). The decryption function of FHE scheme from LWE is D
e
c
s
c
=
s
,
c
2
∈
{
0,1
}. We also supposed that the outer encryption scheme is FH-SIMD, that is, FHE scheme which supports SIMD operation. The generalized bootstrapping technique concludes two algorithms:BootGen algorithm andBootstrap algorithm [11].(i)
BootGen
(
s
∈
Z
q
d
,
p
k
): input secret key vector s
∈
Z
q
d, and the public key of FH-SIMD encryption; output the bootstrapping public key b
k, that is, encrypt the secret key vector s via FH-SIMD scheme and resulting the ciphertext as the bootstrapping public key b
k.
(ii)
Bootstrap
b
k
,
c
=
0,1
d: input the bootstrapping pubic key b
k and the ciphertext vector c
=
0,1
d, output a new ciphertext c
′ of original encryption scheme based LWE, and the result of decrypting c
′ using secret key s
∈
Z
q
d is same as the one decrypting c using secret key s
∈
Z
q
d, but c
′ with less error.


## 2.1. Field and Homomorphism

LetF
(
x
)
∈
F
2
x be a monic polynomial of degree N, which decomposed to exactly l distinct irreducible factors as follows:(1)
F
x
=
∑
i
=
1
l
F
i
x
,where every polynomial F
i
(
x
) has degree D
=
N
/
l.LettingA denote the algebra A
≔
F
2
[
x
]
/
(
F
), we can get the natural homomorphism via Chinese Remainder Theorem (CRT):(2)
A
≅
F
2
x
F
1
⊗
⋯
⊗
F
2
x
F
l
≅
F
2
D
⊗
⋯
⊗
F
2
D
.Forn
∣
D, the finite field K
n
≔
F
2
n is a subfield of F
2
D. Let F
2
x
/
K
n
x denote a fixed canonical representation of K
n, where K
n
x
∈
F
2
[
x
] is some irreducible polynomial of degree n
. Let ψ be a fixed root of K
n
x in the algebraic closure of F
2. Since K
n is contained in each of L
i
≔
F
2
x
/
F
i, there is a homomorphic embedding as follows:(3)
Ψ
n
,
i
:
K
n
→
L
i
α
ψ
↦
α
σ
n
,
i
θ
i
,where σ
n
,
i
(
θ
i
) is a root of K
n
x in algebra L
i, that is,(4)
K
n
σ
n
,
i
x
≡
0
m
o
d
F
i
x
.According to CRT and the above homomorphic embedding, we can obtain a homomorphic embedding ofK
n
l into the algebra A which defined as follows:(5)
Γ
n
,
l
:
K
n
l
→
A
k
1
ψ
,
…
,
k
l
ψ
↦
∑
i
=
1
l
k
i
σ
n
,
i
x
·
H
i
x
·
G
i
x
.where the polynomials H
i
(
x
) and G
i
(
x
) is obtained by CRT and computed as follows:(6)
H
i
x
←
F
x
F
i
x
,
G
i
x
←
H
i
x
-
1
m
o
d
F
i
x
.From the above definition of Γ
n
,
l, we can see that Γ
n
,
l maps a vector of l binary polynomials k
1
ψ
,
…
,
k
l
ψ each of degree less than n, into a single polynomial a
(
x
) of degree less than N. The map Γ
n
,
l defines an isomorphism between K
n
l and Γ
n
,
l
K
n
l, so the inverse map Γ
n
,
l
-
1 is well defined from Γ
n
,
l
(
K
n
l
) to K
n
l. We can represent Γ
n
,
l
-
1 as follows:(7)
Γ
n
,
l
-
1
:
Γ
n
,
l
K
n
l
⊆
A
→
K
n
l
a
x
↦
a
x
m
o
d
F
1
x
,
…
,
a
x
m
o
d
F
l
x
.There are two methods to compute elements in K
n
l: one method is computes component wise on vectors of l elements in K
n; the other concludes three process, firstly, mapping all the inputs to the algebra A by Γ
n
,
l; secondly, performing computations in algebra A; finally, mapping the results back to K
n
l by Γ
n
,
l
-
1. Furthermore, the fully homomorphic encryption scheme FH-SIMD performs one evaluation forl elements in K
n using the algebra A.


## 2.2. Generalized Bootstrapping Technique

Gentry firstly proposed bootstrapping technique, which may transform a somewhat homomorphic encryption scheme to a fully homomorphic encryption scheme. Subsequently, Jacob Alperin-Sheriff and Chris Peikert [11] proposed generalized bootstrapping technique. The generalized bootstrapping technique involves two encryption schemes, outer encryption scheme and inner encryption scheme. It performs decryption procedure of inner encryption scheme using outer encryption scheme, resulting in reducing error in ciphertext. The generalized bootstrapping technique allows that the outer encryption is different from the inner one, realizing that we can design corresponding outer encryption scheme for the concretely inner encryption scheme, such that it effectively performs the decryption circuit of inner encryption scheme. Therefore, the generalized bootstrapping is more efficient than the ordinary one.


## 2.3. The Decryption of FHE from LWE

The decryption of all fully homomorphic schemes based on LWE involved computing inner production and rounding, that is, input secret keys
∈
Z
q
d and binary ciphertext c
∈
0,1
d; the decryption algorithm is written as(8)
D
e
c
s
,
c
=
s
,
c
2
∈
0,1
,where the modular rounding function ·
2: Z
q
→
{
0,1
} indicates whether its arguments is “far from” or “close to” 0 (modulo q), and the modulusq and the dimensiond can both be made as small as quasi-linear O
~
(
λ
) in the security parameter via dimension-modulus reduction [3], while still providing provable 2
λ security under conventional lattice assumption. The inner product s
,
c is just summing the elements of vector s selectively, that is,(9)
s
,
c
=
∑
c
j
=
1
s
j
.Supposing that s
,
c
=
v, the algorithm rounding can be interpreted by iteration as(10)
v
2
=
∑
x
∈
Z
q
s
.
t
.
x
2
=
1
x
=
v
,where [
x
=
v
] denotes the equality test algorithm, when x is equality to v, [
x
=
v
] outputs 1; otherwise, [
x
=
v
] outputs 0.Now, we give the decryption algorithm of FHE based LWE in the ciphertext state. During the bootstrapping procedure, the ciphertext of secrets
∈
Z
q
d is written by s
-
=
s
1
-
,
…
,
s
d
- as bootstrapping public key. The inner product in the ciphertext state is denoted as v
-
=
s
-
,
c
=
∑
c
j
=
1
s
-
j. And the rounding algorithm in the ciphertext state is denoted as(11)
v
-
2
=
⊞
x
∈
Z
q
s
.
t
.
x
2
=
1
x
=
v
-
,where “⊞” denotes the homomorphic addition on the ciphertext space and [
x
=
v
]
- indicates the homomorphic equality test algorithm; it outputs the ciphertext of 1 if and only if x
=
v; otherwise it outputs the ciphertext of 0. We let 1
- denote the ciphertext of 1 and 0
- denote the ciphertext of 0.


## 2.4. Generalized Bootstrapping Procedure of FHE from LWE

Assume that the binary ciphertext to be bootstrapped isc
∈
0,1
d, the secret key is s
∈
Z
q
d, and the dimension d and the module q are enough small (q
,
d
=
Q
~
λ). The decryption function of FHE scheme from LWE is D
e
c
s
c
=
s
,
c
2
∈
{
0,1
}. We also supposed that the outer encryption scheme is FH-SIMD, that is, FHE scheme which supports SIMD operation. The generalized bootstrapping technique concludes two algorithms:BootGen algorithm andBootstrap algorithm [11].(i)
BootGen
(
s
∈
Z
q
d
,
p
k
): input secret key vector s
∈
Z
q
d, and the public key of FH-SIMD encryption; output the bootstrapping public key b
k, that is, encrypt the secret key vector s via FH-SIMD scheme and resulting the ciphertext as the bootstrapping public key b
k.
(ii)
Bootstrap
b
k
,
c
=
0,1
d: input the bootstrapping pubic key b
k and the ciphertext vector c
=
0,1
d, output a new ciphertext c
′ of original encryption scheme based LWE, and the result of decrypting c
′ using secret key s
∈
Z
q
d is same as the one decrypting c using secret key s
∈
Z
q
d, but c
′ with less error.


## 3. Faster Bootstrapping Based on FH-SIMD

### 3.1. Main Ideas

Jacob Alperin-Sheriff and Chris Peikert proposed the generalized bootstrapping method based on the GSW scheme. Homomorphic equality test is a key component of the generalized bootstrapping algorithm, that is, for the fixedv
∈
Z
q, under the ciphertext state, travels every x
∈
Z
q which satisfies x
2
=
1, and decide that whether v
=
x or not, see Figure 1.Figure 1
Homomorphic equality test.We intend to proposed block homomorphic equality test algorithm, that is, it travels a blockx
1
,
x
2
,
…
,
x
l, x
i
∈
Z
q which satisfies x
2
=
1, and decide that whether this batch of x
1
,
x
2
,
…
,
x
l exits a x
i such that v
=
x
i holds, see Figure 2.Figure 2
Block homomorphic equality test.Resort to the FH-SIMD homomorphic encryption scheme [7], we will give a block homomorphic equality test algorithm B_Eq?, and then propose an efficient generalized bootstrapping algorithm. The bootstrapping key is an encryption of each coordinate of the secret key s
∈
Z
q
d, and consists of d FH-SIMD ciphertexts. To bootstrapping c
∈
0,1
d, the inner product s
,
c
∈
Z
q is computed homomorphically as a subset-sum using addition method, and the rounding function is computed using block homomorphic equality test algorithm and addition method.


### 3.2. Block Homomorphic Equality Test Algorithm

In this section, we describe our block homomorphic equality test algorithm, called B_Eq?.Input: ciphertexv
-
∈
Z
q and plaintext block x
1
,
…
,
x
l
∈
Z
q
l.Output: if there exits ax
i
∈
x
1
,
x
2
,
…
,
x
l such that v
=
x
i holds, then the block homomophic equality test algorithm outputs 1
-; otherwise it outputs 0
-.We assume thatv
- and all x
i are n bits in length, and thus can be encoded as an element of the finite filed K
n
=
F
2
n, where n
=
log
⁡
q. The concrete procedure is described as follows:(
1
) For x
1
,
…
,
x
l
∈
Z
q
l, where every x
i satisfies x
i
2
=
1, embed each coordinate x
i
∈
Z
q as an element of F
2
n. Our aim is to pack x
1
,
…
,
x
l into single element X
∈
K
n, so we compute X
=
Γ
n
,
l
x
1
,
…
,
x
l. Then compute the trivial encryption of X in the algebraA using FH-SIMD scheme. It is worth noting that we encrypt X without random, such that saving computational cost. That is,(12)
X
-
=
F
H
-
S
I
M
D
.
E
n
c
r
y
p
t
Γ
n
,
l
x
1
,
…
,
x
l
,
p
k
.Then compute(13)
V
-
=
Γ
n
,
l
v
-
,
…
,
v
-
.(
2
) Sum the ciphertext V
- and X
-, and denote the sum as c
(
1
), that is,(14)
c
1
=
V
-
⊞
X
-
.(
3
) Homomorphically raised c
(
1
) to the power 2
n
-
1, that is,(15)
c
2
=
c
1
2
n
-
1
.And compute(16)
Γ
n
,
l
-
1
c
2
=
v
-
⊞
x
1
-
2
n
-
1
,
…
,
v
-
⊞
x
l
-
2
n
-
1
.According to the homomorphism of encryption scheme FH-SIMD, the2
n
-
1 power of ciphertext is corresponding to the 2
n
-
1 power of plaintext. Of course, the ciphertext is homomorphically raised to the power 2
n
-
1, via performing 2n applications of multiplication. Since the plaintext corresponding to v
-
⊞
x
-
i is an element of finite field F
2
n and its max multiplicative order is 2
n
-
1, then the plaintext corresponding to v
-
⊞
x
-
i
2
n
-
1 is either 0 or 1. Therefore, v
-
⊞
x
i
-
2
n
-
1 is a ciphertext of encrypting 1 (nonzero element) or a ciphertext of encrypting 0 (zero element). When v
-
⊞
x
-
i is an encryption of 0, this means that v
=
x
i holds; when v
-
⊞
x
-
i is an encryption of 1, this means that v
=
x
i does nit hold.(
4
) Compute(17)
c
3
=
c
2
⊞
F
H
-
S
I
M
D
.
E
n
c
r
y
p
t
Γ
n
,
l
1
,
…
,
1
,
p
k
,
Γ
n
,
l
-
1
c
3
=
v
-
⊞
x
1
-
2
n
-
1
⊞
1
-
,
…
,
v
-
⊞
x
l
-
2
n
-
1
⊞
1
-
.We can see that as long as the equationx
i
=
v holds, thei-th component of c
(
3
) is 0
-
⊞
1
-
=
1
-; otherwise, the i-th component of c
(
3
) is 1
-
⊞
1
-
=
0
-. Therefore, if there exits a x
i
∈
x
1
,
x
2
,
…
,
x
l such that v
=
x
i holds, then v
-
⊞
x
-
i
2
n
-
1
⊞
1
-
=
1
-, and all other v
-
⊞
x
-
j
2
n
-
1
⊞
1
-
=
0
-, for all j
≠
i. It follows that c
(
3
)
=
1
-. That is, if there exits a x
i
∈
x
1
,
x
2
,
…
,
x
l such that v
=
x
i holds, the block homomophic equality test algorithm outputs 1
-; otherwise it outputs 0
-.From the above steps, we finish the block homomorphic equality test; then we can homomorphic computev
2, that is, v
-
2
≔
c
(
3
).


### 3.3. Faster Bootstrapping Technique

In this section, we construct faster bootstrapping procedure from the block homomorphic equality test algorithm B_Eq?. The bootstrapping procedure consists of two algorithms: BootKeyGen and Bootstrap. The procedure is used to refresh ciphertexts of all known standard LWE-based FHE. We get the input ciphertextc
∈
0,1
d for Bootstrap, and it is from the dimension-modulus reduction and bit-decomposition of the ciphertext to be bootstrapped. Let s
∈
Z
q
d be the secret key that corresponding to the ciphertext c
.BootGen
(
s
∈
Z
q
d
,
p
k
): input the secret key s
∈
Z
q
d for the ciphertext to be refreshed and the public keypk of FH-SIMD scheme. Without loss of generality, for every j
∈
[
d
], encode each coordinate s
j
∈
Z
q to the element of finite field F
2
n. Then encrypt its ciphertext under FH-SIMD scheme, and generate the bootstrapping key:(18)
s
-
j
=
F
H
-
S
I
M
D
.
E
n
c
r
y
p
t
s
j
,
p
k
.Output the bootstrapping public keyb
k
=
s
1
-
,
…
,
s
d
-. The bootstrapping key consists of d FH-SIMD ciphertexts.Bootstrap
b
k
,
c
∈
0,1
d: input the binary ciphertext c
∈
0,1
d, and perform the following two phases:(i)
Inner Product Homomorphically compute inner product v
- using the bootstrapping public key b
k. It is known that(19)
v
≜
s
,
c
=
∑
j
:
c
j
=
1
s
j
∈
Z
q
.
It follows that(20)
v
-
≜
s
-
,
c
=
⊞
j
:
c
j
=
1
s
-
j
.
(ii)
Round For every x
i
∈
Z
q which satisfies x
i
2
=
1, arrange in order of size, and divide them into blocks of l items, and let us suppose they are distinct from one another, and there are altogether k blocks:(21)
x
1
,
…
,
x
l
,
x
l
+
1
,
…
,
x
2
l
,
…
,
x
k
-
1
l
+
1
,
…
,
x
k
l
.
For every blockx
j
l
+
1
,
…
,
x
(
j
+
1
)
l
,
j
=
0,1
,
…
,
k
-
1, run block homomorphic equality test algorithm in parallel,(22)
c
j
=
B
_
E
q
?
v
-
,
x
j
l
+
1
,
…
,
x
j
+
1
l
.
Then compute(23)
C
=
⊞
j
:
1
≤
j
≤
k
c
j
.We can see thatc
j is either 1
- or 0
-, and then C is the encryption of v
2, C is also either 1
- or 0
-, and it refreshed ciphertext with smaller error. Note that the output C is a FH-SIMD ciphertext encrypted under p
k. If desired, we can convert this ciphertext back to one for the original LWE FHE cryptosystem. We can also perform key-switch from s
k back to the original secret keys.


## 3.1. Main Ideas

Jacob Alperin-Sheriff and Chris Peikert proposed the generalized bootstrapping method based on the GSW scheme. Homomorphic equality test is a key component of the generalized bootstrapping algorithm, that is, for the fixedv
∈
Z
q, under the ciphertext state, travels every x
∈
Z
q which satisfies x
2
=
1, and decide that whether v
=
x or not, see Figure 1.Figure 1
Homomorphic equality test.We intend to proposed block homomorphic equality test algorithm, that is, it travels a blockx
1
,
x
2
,
…
,
x
l, x
i
∈
Z
q which satisfies x
2
=
1, and decide that whether this batch of x
1
,
x
2
,
…
,
x
l exits a x
i such that v
=
x
i holds, see Figure 2.Figure 2
Block homomorphic equality test.Resort to the FH-SIMD homomorphic encryption scheme [7], we will give a block homomorphic equality test algorithm B_Eq?, and then propose an efficient generalized bootstrapping algorithm. The bootstrapping key is an encryption of each coordinate of the secret key s
∈
Z
q
d, and consists of d FH-SIMD ciphertexts. To bootstrapping c
∈
0,1
d, the inner product s
,
c
∈
Z
q is computed homomorphically as a subset-sum using addition method, and the rounding function is computed using block homomorphic equality test algorithm and addition method.


## 3.2. Block Homomorphic Equality Test Algorithm

In this section, we describe our block homomorphic equality test algorithm, called B_Eq?.Input: ciphertexv
-
∈
Z
q and plaintext block x
1
,
…
,
x
l
∈
Z
q
l.Output: if there exits ax
i
∈
x
1
,
x
2
,
…
,
x
l such that v
=
x
i holds, then the block homomophic equality test algorithm outputs 1
-; otherwise it outputs 0
-.We assume thatv
- and all x
i are n bits in length, and thus can be encoded as an element of the finite filed K
n
=
F
2
n, where n
=
log
⁡
q. The concrete procedure is described as follows:(
1
) For x
1
,
…
,
x
l
∈
Z
q
l, where every x
i satisfies x
i
2
=
1, embed each coordinate x
i
∈
Z
q as an element of F
2
n. Our aim is to pack x
1
,
…
,
x
l into single element X
∈
K
n, so we compute X
=
Γ
n
,
l
x
1
,
…
,
x
l. Then compute the trivial encryption of X in the algebraA using FH-SIMD scheme. It is worth noting that we encrypt X without random, such that saving computational cost. That is,(12)
X
-
=
F
H
-
S
I
M
D
.
E
n
c
r
y
p
t
Γ
n
,
l
x
1
,
…
,
x
l
,
p
k
.Then compute(13)
V
-
=
Γ
n
,
l
v
-
,
…
,
v
-
.(
2
) Sum the ciphertext V
- and X
-, and denote the sum as c
(
1
), that is,(14)
c
1
=
V
-
⊞
X
-
.(
3
) Homomorphically raised c
(
1
) to the power 2
n
-
1, that is,(15)
c
2
=
c
1
2
n
-
1
.And compute(16)
Γ
n
,
l
-
1
c
2
=
v
-
⊞
x
1
-
2
n
-
1
,
…
,
v
-
⊞
x
l
-
2
n
-
1
.According to the homomorphism of encryption scheme FH-SIMD, the2
n
-
1 power of ciphertext is corresponding to the 2
n
-
1 power of plaintext. Of course, the ciphertext is homomorphically raised to the power 2
n
-
1, via performing 2n applications of multiplication. Since the plaintext corresponding to v
-
⊞
x
-
i is an element of finite field F
2
n and its max multiplicative order is 2
n
-
1, then the plaintext corresponding to v
-
⊞
x
-
i
2
n
-
1 is either 0 or 1. Therefore, v
-
⊞
x
i
-
2
n
-
1 is a ciphertext of encrypting 1 (nonzero element) or a ciphertext of encrypting 0 (zero element). When v
-
⊞
x
-
i is an encryption of 0, this means that v
=
x
i holds; when v
-
⊞
x
-
i is an encryption of 1, this means that v
=
x
i does nit hold.(
4
) Compute(17)
c
3
=
c
2
⊞
F
H
-
S
I
M
D
.
E
n
c
r
y
p
t
Γ
n
,
l
1
,
…
,
1
,
p
k
,
Γ
n
,
l
-
1
c
3
=
v
-
⊞
x
1
-
2
n
-
1
⊞
1
-
,
…
,
v
-
⊞
x
l
-
2
n
-
1
⊞
1
-
.We can see that as long as the equationx
i
=
v holds, thei-th component of c
(
3
) is 0
-
⊞
1
-
=
1
-; otherwise, the i-th component of c
(
3
) is 1
-
⊞
1
-
=
0
-. Therefore, if there exits a x
i
∈
x
1
,
x
2
,
…
,
x
l such that v
=
x
i holds, then v
-
⊞
x
-
i
2
n
-
1
⊞
1
-
=
1
-, and all other v
-
⊞
x
-
j
2
n
-
1
⊞
1
-
=
0
-, for all j
≠
i. It follows that c
(
3
)
=
1
-. That is, if there exits a x
i
∈
x
1
,
x
2
,
…
,
x
l such that v
=
x
i holds, the block homomophic equality test algorithm outputs 1
-; otherwise it outputs 0
-.From the above steps, we finish the block homomorphic equality test; then we can homomorphic computev
2, that is, v
-
2
≔
c
(
3
).


## 3.3. Faster Bootstrapping Technique

In this section, we construct faster bootstrapping procedure from the block homomorphic equality test algorithm B_Eq?. The bootstrapping procedure consists of two algorithms: BootKeyGen and Bootstrap. The procedure is used to refresh ciphertexts of all known standard LWE-based FHE. We get the input ciphertextc
∈
0,1
d for Bootstrap, and it is from the dimension-modulus reduction and bit-decomposition of the ciphertext to be bootstrapped. Let s
∈
Z
q
d be the secret key that corresponding to the ciphertext c
.BootGen
(
s
∈
Z
q
d
,
p
k
): input the secret key s
∈
Z
q
d for the ciphertext to be refreshed and the public keypk of FH-SIMD scheme. Without loss of generality, for every j
∈
[
d
], encode each coordinate s
j
∈
Z
q to the element of finite field F
2
n. Then encrypt its ciphertext under FH-SIMD scheme, and generate the bootstrapping key:(18)
s
-
j
=
F
H
-
S
I
M
D
.
E
n
c
r
y
p
t
s
j
,
p
k
.Output the bootstrapping public keyb
k
=
s
1
-
,
…
,
s
d
-. The bootstrapping key consists of d FH-SIMD ciphertexts.Bootstrap
b
k
,
c
∈
0,1
d: input the binary ciphertext c
∈
0,1
d, and perform the following two phases:(i)
Inner Product Homomorphically compute inner product v
- using the bootstrapping public key b
k. It is known that(19)
v
≜
s
,
c
=
∑
j
:
c
j
=
1
s
j
∈
Z
q
.
It follows that(20)
v
-
≜
s
-
,
c
=
⊞
j
:
c
j
=
1
s
-
j
.
(ii)
Round For every x
i
∈
Z
q which satisfies x
i
2
=
1, arrange in order of size, and divide them into blocks of l items, and let us suppose they are distinct from one another, and there are altogether k blocks:(21)
x
1
,
…
,
x
l
,
x
l
+
1
,
…
,
x
2
l
,
…
,
x
k
-
1
l
+
1
,
…
,
x
k
l
.
For every blockx
j
l
+
1
,
…
,
x
(
j
+
1
)
l
,
j
=
0,1
,
…
,
k
-
1, run block homomorphic equality test algorithm in parallel,(22)
c
j
=
B
_
E
q
?
v
-
,
x
j
l
+
1
,
…
,
x
j
+
1
l
.
Then compute(23)
C
=
⊞
j
:
1
≤
j
≤
k
c
j
.We can see thatc
j is either 1
- or 0
-, and then C is the encryption of v
2, C is also either 1
- or 0
-, and it refreshed ciphertext with smaller error. Note that the output C is a FH-SIMD ciphertext encrypted under p
k. If desired, we can convert this ciphertext back to one for the original LWE FHE cryptosystem. We can also perform key-switch from s
k back to the original secret keys.


## 4. Analysis

### 4.1. Correctness Analysis

Lemma 1 (correctness).
Forb
k
←
B
o
o
t
G
e
n
(
s
,
p
k
), the FH-SIMD ciphertext  C
←
B
o
o
t
s
t
r
a
p
(
b
k
,
c
) is designed to encrypt D
e
c
s
c
=
s
,
c
2
∈
{
0,1
}.Proof.
Firstly, the FH-SIMD ciphertexts
-
j is designed to encrypt s
j from (18). Therefore, since φ
:
Z
q
→
F
2
n is homomorphic embedding, the ciphertext v
- as defined as in (20) designed to encrypt(24)
∑
j
:
c
j
=
1
s
j
=
s
,
c
=
v
.
By correctness of block homomorphic equality test algorithm B_Eq?, the homomorphic sumC
=
⊞
j
:
1
≤
j
≤
k
c
j is designed to encrypt 1 if and only if v
=
x
.Finally, since the homomorphic sum is taken over every x
∈
Z
q such that x
2
=
1, it is designed to encrypt 1 if and only if v
2
=
1.


### 4.2. Security Analysis

Lemma 2 (semantic security).
Suppose that the FH-SIMD scheme secret keys
k is generated independently of the secret key s
=
s
1
,
…
,
s
d
∈
Z
q
d of FHE scheme from LWE; then Ind-CPA security of the bootstrapping key follows immediately from the Ind-CPA security of FH-SIMD, hence from SIVP of ideal lattice.Proof.
Forb
k
←
B
o
o
t
G
e
n
(
s
,
p
k
), if there is not an adversary can distinguish the bootstrapping key b
k from a random element in the same space, then the bootstrapping procedure called satisfing semantic security.
In our bootstrapping procedure, fors
=
s
1
,
…
,
s
d
∈
Z
q
d, the bootstrapping key consists of d FH-SIMD ciphertexts; that is, b
k
=
s
1
-
,
…
,
s
d
- is generated via FH-SIMD scheme, where(25)
s
-
j
=
F
H
-
S
I
M
D
.
E
n
c
r
y
p
t
s
j
,
p
k
.
Suppose that there is an adversaryA can distinguish the bootstrapping b
k from random element. Then we can construct an algorithm B by calling the adversary A and break the Ind-CPA security of FH-SIMD scheme and, furthermore, solve the SIVP of ideal lattice.


### 4.3. Performance Analysis

Our block homomorphic equality test algorithm B_Eq? has a cost of(
2
·
E
n
c
+
2
·
C
A
+
2
log
⁡
q
·
C
M
+
2
·
Γ
n
,
l
+
Γ
n
,
l
-
1
) per data block, where C
A denotes add operation of the ciphertext and C
M denotes multiplicative operation of the ciphertext, whereas the homomorphic equality test algorithm Eq? involves q
·
C
A, which is exponential times of B_Eq? algorithm, meaning that the computation of Eq? algorithm is more costly, reference to Table 1.Table 1
Compare of the performance of homomorphic equality test algorithm.
algorithm
Enc
C
A
C
M
Γ
n
,
l
Γ
n
,
l
-
1
Eq? [11]
0
0
O
(
q
)
0
0
B_Eq?
2
2
O
(
log
⁡
q
)
2
1In the work of Alperin-Sheriff and Peikert [11], one inner product evaluation of bootstrapping needs to compute d ciphertexts compose evaluation, and one rounding evaluation of bootstrapping needs to call O
(
q
) Eq? algorithm, and O
(
q
) ciphertext multiplicative operation. Whereas one inner production of our faster bootstrapping needs to compute d ciphertext additions, and one rounding evaluation needs to call k B_Eq? algorithm, where l is the size of block, and k is the number of block, k
=
q
/
l.Suppose that LWE problem has 80 bits security whenq is set to be 2003. Parameters setting as above, and when q is set to be 2003, 2047, 2501, 3001, 4093, and 12899, we give the relation between multiplicative operation quantity and modulus q, as shown in Figure 3. As the modulus q increases, the number of ciphertext multiplicative operation grows swiftly in the AP’s bootstrapping procedure, whereas the number of ciphertext multiplicative operation grows slowly.Figure 3
The relation between the ciphertext multiplicative quantity and the modulusq.On the other hand, for the fixed modulusq andm, we give the relation between multiplicative operation quantity once running our faster bootstrapping procedure based on the block size of block homomorphic equality test algorithm B_Eq?. When m
=
11441, N
=
φ
m
=
10752, and 2
48
m
o
d
11441
=
1, so d
=
48, we set n
=
12, which satisfies n
∣
d. Then we set the size of block as 16,32,64,128,224, that is, the size of block l
=
16,32,64,128,224. Then the number of blocks k
=
3024,1512,768,384,216. We can see from Figure 4, as the block size increases, the ciphertext multiplicative operation drops dramatically.Figure 4
The relation between the ciphertext multiplicative quantity and the block size.


## 4.1. Correctness Analysis

Lemma 1 (correctness).
Forb
k
←
B
o
o
t
G
e
n
(
s
,
p
k
), the FH-SIMD ciphertext  C
←
B
o
o
t
s
t
r
a
p
(
b
k
,
c
) is designed to encrypt D
e
c
s
c
=
s
,
c
2
∈
{
0,1
}.Proof.
Firstly, the FH-SIMD ciphertexts
-
j is designed to encrypt s
j from (18). Therefore, since φ
:
Z
q
→
F
2
n is homomorphic embedding, the ciphertext v
- as defined as in (20) designed to encrypt(24)
∑
j
:
c
j
=
1
s
j
=
s
,
c
=
v
.
By correctness of block homomorphic equality test algorithm B_Eq?, the homomorphic sumC
=
⊞
j
:
1
≤
j
≤
k
c
j is designed to encrypt 1 if and only if v
=
x
.Finally, since the homomorphic sum is taken over every x
∈
Z
q such that x
2
=
1, it is designed to encrypt 1 if and only if v
2
=
1.


## 4.2. Security Analysis

Lemma 2 (semantic security).
Suppose that the FH-SIMD scheme secret keys
k is generated independently of the secret key s
=
s
1
,
…
,
s
d
∈
Z
q
d of FHE scheme from LWE; then Ind-CPA security of the bootstrapping key follows immediately from the Ind-CPA security of FH-SIMD, hence from SIVP of ideal lattice.Proof.
Forb
k
←
B
o
o
t
G
e
n
(
s
,
p
k
), if there is not an adversary can distinguish the bootstrapping key b
k from a random element in the same space, then the bootstrapping procedure called satisfing semantic security.
In our bootstrapping procedure, fors
=
s
1
,
…
,
s
d
∈
Z
q
d, the bootstrapping key consists of d FH-SIMD ciphertexts; that is, b
k
=
s
1
-
,
…
,
s
d
- is generated via FH-SIMD scheme, where(25)
s
-
j
=
F
H
-
S
I
M
D
.
E
n
c
r
y
p
t
s
j
,
p
k
.
Suppose that there is an adversaryA can distinguish the bootstrapping b
k from random element. Then we can construct an algorithm B by calling the adversary A and break the Ind-CPA security of FH-SIMD scheme and, furthermore, solve the SIVP of ideal lattice.


## 4.3. Performance Analysis

Our block homomorphic equality test algorithm B_Eq? has a cost of(
2
·
E
n
c
+
2
·
C
A
+
2
log
⁡
q
·
C
M
+
2
·
Γ
n
,
l
+
Γ
n
,
l
-
1
) per data block, where C
A denotes add operation of the ciphertext and C
M denotes multiplicative operation of the ciphertext, whereas the homomorphic equality test algorithm Eq? involves q
·
C
A, which is exponential times of B_Eq? algorithm, meaning that the computation of Eq? algorithm is more costly, reference to Table 1.Table 1
Compare of the performance of homomorphic equality test algorithm.
algorithm
Enc
C
A
C
M
Γ
n
,
l
Γ
n
,
l
-
1
Eq? [11]
0
0
O
(
q
)
0
0
B_Eq?
2
2
O
(
log
⁡
q
)
2
1In the work of Alperin-Sheriff and Peikert [11], one inner product evaluation of bootstrapping needs to compute d ciphertexts compose evaluation, and one rounding evaluation of bootstrapping needs to call O
(
q
) Eq? algorithm, and O
(
q
) ciphertext multiplicative operation. Whereas one inner production of our faster bootstrapping needs to compute d ciphertext additions, and one rounding evaluation needs to call k B_Eq? algorithm, where l is the size of block, and k is the number of block, k
=
q
/
l.Suppose that LWE problem has 80 bits security whenq is set to be 2003. Parameters setting as above, and when q is set to be 2003, 2047, 2501, 3001, 4093, and 12899, we give the relation between multiplicative operation quantity and modulus q, as shown in Figure 3. As the modulus q increases, the number of ciphertext multiplicative operation grows swiftly in the AP’s bootstrapping procedure, whereas the number of ciphertext multiplicative operation grows slowly.Figure 3
The relation between the ciphertext multiplicative quantity and the modulusq.On the other hand, for the fixed modulusq andm, we give the relation between multiplicative operation quantity once running our faster bootstrapping procedure based on the block size of block homomorphic equality test algorithm B_Eq?. When m
=
11441, N
=
φ
m
=
10752, and 2
48
m
o
d
11441
=
1, so d
=
48, we set n
=
12, which satisfies n
∣
d. Then we set the size of block as 16,32,64,128,224, that is, the size of block l
=
16,32,64,128,224. Then the number of blocks k
=
3024,1512,768,384,216. We can see from Figure 4, as the block size increases, the ciphertext multiplicative operation drops dramatically.Figure 4
The relation between the ciphertext multiplicative quantity and the block size.


## 5. Conclusions

Fully homomorphic encryption scheme allows evaluating encrypted data, without decrypting the corresponding ciphertext. In fully homomorphic encryption scheme, the ciphertext has a noise that grows at each homomorphic evaluation. When the noise reaches a threshold, then the ciphertext cannot be decrypted correctly. The number of homomorphic operations can be made asymptotically large using bootstrapping technique.In this paper, we further investigated the bootstrapping procedure. We proposed the concept of block homomorphic equality test algorithm and give an instance based on the FH-SIMD scheme. Furthermore, we give a faster bootstrapping procedure based on the block homomorphic equality test algorithm. Both theory analysis and experiment simulation validate the higher performance of our bootstrapping than that of the work [11].



---

*Source: 9325082-2018-12-24.xml*