# Analysis on Matrix GSW-FHE and Optimizing Bootstrapping

Authors: Xiufeng Zhao; Hefeng Mao; Shuai Liu; Weitao Song; Bo Zhang
Journal: Security and Communication Networks
 (2018)

---

## Abstract

With the rapid development of multimedia technologies, the multimedia 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. In this paper, we analyse circular security of matrix GSW-FHE scheme. We derive a sufficient condition of circular security for matrix GSW-FHE scheme. It allows us to choose a good secret key via “reject sample” technique and furthermore obtain circular secure matrix GSW-FHE scheme. We also give an extended version of matrix GSW-FHE by defining deterministic asymmetric encryption algorithm and propose hybrid homomorphic plaintext slot-wise switching method, which significantly reduces computation and storage complexity of bootstrapping key generation, thus optimizing the bootstrapping procedure.


---

## Body

## 1. Introduction

With the rapid development of multimedia technologies, for example, high-efficiency video coding (HEVC) is becoming popular due to its excellent coding performance [1]; the multimedia data storage and outsource computation are delegated to the untrusted cloud server, which has led to a series of challenging security and privacy threats. To tackle the security and privacy issues in cloud computing and storage, a lot of researches have been performed, such as fully homomorphic encryption [2, 3], attribute-based encryption, searchable encryption [4], and ciphertext retrieval scheme [5, 6]. The concept of homomorphic encryption is proposed by Rivest et al. [7], and Gentry [2, 3] proposed the first fully homomorphic encryption (FHE) scheme based on ideal lattice. FHE allows us to evaluate any function over ciphertext and obtain the function over corresponding plaintext by decryption. Fully homomorphic encryption can be used to protect the privacy of cloud data and solve the trust problem of untrusted third party. So the fully homomorphic encryption has a broad application prospect in the cloud computation and the big data field. There are many fully homomorphic encryption schemes based NP-hard problems, such as ideal lattice [2, 3], LWE [8, 9], RLWE [10], LWR [11], and so forth.The difficulty of constructing fully homomorphic encryption scheme is reducing the noise in the ciphertext. The noise increases rapidly during ciphertext evaluations and eventually reaches a threshold beyond which we can no longer decrypt the resulting ciphertext correctly. Therefore, the somewhat homomorphic encryption scheme is constructed, which can homomorphically evaluates arithmetic circuits of limited depth. To get pure fully homomorphic encryption scheme, Gentry proposed bootstrapping technique. The bootstrapping technique is currently the only way to get pure fully homomorphic encryption from somewhat homomorphic encryption. Its main idea is refreshing ciphertext by homomorphic decryption and getting fresh ciphertext and realizing the purpose of reducing ciphertext noise. The critical process of bootstrapping technique is encrypting the pieces of secret key, and the corresponding ciphertexts are viewed as public evaluation key. Thus, the homomorphic encryption scheme must enjoy circular security.Unfortunately, all known FHE schemes are supposed to be circular secure except [10, 12]. If fully homomorphic encryption scheme satisfies circular security, it is not necessary to generate as many public evaluation keys as the depth of evaluation circuit. But being circular secure is not a naive security attribute, so it is necessary to analyse circular security for concrete fully homomorphic encryption scheme. Meanwhile, bootstrapping is used to refresh ciphertext, and the procedure is implemented frequently to get pure fully homomorphic encryption. Therefore, how to improve the bootstrapping efficiency is worth intensive studying.Our Results. We analyse circular security of matrix GSW-FHE scheme [13]. From formal definition of circular security, we derive a sufficient condition of circular security for matrix GSW-FHE scheme. That is, the matrix GSW-FHE scheme satisfies circular security with some function, if the equations about secret key have solution over Z
q. Therefore, we can choose a good secret key via “reject sample” technique and furthermore obtain circular secure matrix GSW-FHE scheme.We also give an extended version of matrix GSW-FHE by defining deterministic asymmetric encryption algorithm. To simplify the homomorphic equality test procedure, we propose hybrid homomorphic plaintext slot-wise switching method using symmetric encryption and deterministic public encryption algorithms, which significantly reduces computational cost of bootstrapping key generation, thus optimizing the bootstrapping procedure of work [13].We may implement a trade-off between computation and storage complexity of bootstrapping. We delete part of the bootstrapping keys and compute them online when running Rounding procedure. In view of that, their computation involves only matrix additions; this cuts down the size of the large public bootstrapping key by a third, paying matrix additions with negligible computation complex.Related Works. Encryption scheme achieves circular security, if it remains secure and even the secret key is encrypted under corresponding public key. In other words, circular secure encryption scheme resists key-dependent message (KDM) attack.In the last few years, circular secure encryption schemes have been studied extensively [14–17]. Boneh et al. constructed a circular secure public key encryption scheme based on the DDH assumption without random oracle [16]. Based on Regev’s LWE-based encryption scheme [18], Applebaum et al. constructed efficient cryptosystems enjoying circular secure [17]. Brakerski and Vaikuntanathan [10] proposed circular secure homomorphic encryption scheme based on the ring-LWE assumption. The main idea in the work of [10, 17] is generating a valid ciphertext that decrypts to a message related to secret key. Because the entries of secret key are not in the message space, they introduced “noise flooding technique” and “rerandom technique” to “fit” the entries into the message space.Brakerski and Vaikuntanathan presented a fully homomorphic encryption scheme based on the LWE assumption using relinearization technique [8]. The relinearization process allows doing one multiplication without increasing the size of the ciphertext and obtaining an encryption of the product under a new secret key. Posting a “chain” of L secret keys allows performing up to L levels of multiplications without blowing up to the ciphertext size. Yang et al. consider that if the relinearization satisfies circular security, the “chain” of L secret keys may be back down to only one secret key, and they proposed a circular secure relinearization by defining a new assumption [12].EuroCrypt 2013, Gentry, Sahai, and Waters proposed a new fully homomorphic encryption scheme based on theapproximate eigenvector method, which is called GSW-FHE [19]. In the GSW-FHE scheme, homomorphic addition and multiplication are just matrix addition and multiplication. But GSW scheme operates one bit every running encryption algorithm. PKC 2015, Hiromasa et al. constructed a variant of GSW scheme called matrix GSW-FHE, which encrypts matrices and supports homomorphic matrix addition and multiplication. And they optimized the bootstrapping procedure of Alperin-Sheriff and Peikert [20] using the matrix GSW-FHE scheme [13]. To achieve homomorphic matrix operation, the pubic key of matrix GSW-FHE scheme includes the ciphertexts that encrypt partial information of the secret key, so the matrix GSW-FHE scheme resorts to circular security assumption, but formal circular security proof was not given, and it remains an open problem.There are other works to optimize the bootstrapping procedure. Ducas et al. [21] proposed FHEW scheme, which accelerates bootstrapping via embedding the cyclic group Z
q into the group of roots of unity: i
→
X
i, where i is a primitive q-th root of unity. Wang and Tang [22] proposed an integer bootstrapping scheme by introducing new methods to evaluate integer polynomials with GSW-FHE, and they extended the method to packing by encrypting the integers diagonally in a matrix, as the matrix GSW-FHE proposed by Hiromasa et al. [13]. Similarly, their scheme resorts to circular security assumption.On the other hand, packing technique is used to evaluate efficiently a large number of ciphertexts, and it allows us to apply single-instruction-multiple-data (SIMD) homomorphic operations to all encrypted data [23, 24]. The bootstrapping procedure [13, 20] is optimized by embedding Z
q into symmetric group S
q, the multiplication group of q
×
q permutation matrix, and homomorphic permuting SIMD ciphertexts. The mathematic preliminary of SIMD technique is Chinese Remainder Theorem (CRT). The plaintext space can be split into many small spaces via the CRT. If the plaintext modulus q is a composite that factors into distinct powers q
=
r
1
…
r
t, then the ring R
q can be mapped via the CRT to direct product of ring R
r
i’s.Organization. In Section 2, we describe some preliminaries on the formal definition of homomorphic encryption and circular security and the isomorphic from additive group Z
q to a group of cyclic permutations. In Section 3, we review the matrix GSW-FHE scheme and define a new deterministic asymmetric encryption algorithm. We give the analysis on circular security of matrix GSW-FHE scheme in Section 4. In Section 5, we propose hybrid plaintext slot switching method and optimize the bootstrapping procedure. We give conclusions in Section 6.


## 2. Preliminaries

We denote the set of integers byZ. Let G be some group and let P be some probability distribution, and then we use a
←
U
G to denote that a is chosen from G uniformly at random and use b
←
R
P to denote that b is chosen along P.The vector is denoted by bold lowercase letter, for example,x, and the i-th element of a vector x is denoted by x
i. The inner product between two vectors is denoted by x
,
y. Matrices are written by using bold capital letters, for example, X, and the i-th column vector of a matrix is denoted by x
i. The n
×
n identity matrix is denoted by I
n.


### 2.1. Homomorphic Encryption

LetMand C be the message and ciphertext space. A homomorphic encryption scheme consists of four algorithms K
e
y
G
e
n
,
E
n
c
,
D
e
c
,
E
v
a
l.(i)
K
e
y
G
e
n
(
1
λ
): input security parameter λ and output a public encryption key p
k, a secret decryption key s
k, and a public evaluation key e
v
k.
(ii)
E
n
c
p
k
(
m
): input public key p
k and plaintext m
∈
M and output ciphertext c
∈
C.
(iii)
D
e
c
s
k
(
c
): input secret key s
k and ciphertext c and output the message encrypted in the ciphertext c.
(iv)
E
v
a
l
e
v
k
(
f
,
c
1
,
c
2
,
…
,
c
l
): input the evaluation key e
v
k, function f, and ciphertexts c
1
,
c
2
,
…
,
c
l and output a ciphertext c
f
∈
C that is obtained by applying the function f
:
M
l
→
M to c
1
,
c
2
,
…
,
c
l.


### 2.2. EmbeddingZ
q into Symmetric Group

According to Cayley’s Theorem, the additive groupZ
q is isomorphic to a group of cyclic permutations G, where x
∈
Z
q corresponds to a cyclic permutation that can be represented by an indicator vector with 1 in the x
+
1-th position. The permutation matrix can be obtained from the cyclic rotation of the indicator vector. The addition in Z
q leads to the composition of the permutations; the rounding function x
2
:
Z
q
→
{
0,1
} can be computed by summing the entries of the indicator vector corresponding to those in Z
q that round 1.By CRT,Z
q is isomorphic to the direct product Z
r
1
×
…
×
Z
r
t, where q
≔
∏
i
=
1
t
r
i, and r
i are small and powers of distinct primes. Similarly, Z
q embeds into symmetric group S
=
S
r
1
×
S
r
2
×
…
×
S
r
t.


## 2.1. Homomorphic Encryption

LetMand C be the message and ciphertext space. A homomorphic encryption scheme consists of four algorithms K
e
y
G
e
n
,
E
n
c
,
D
e
c
,
E
v
a
l.(i)
K
e
y
G
e
n
(
1
λ
): input security parameter λ and output a public encryption key p
k, a secret decryption key s
k, and a public evaluation key e
v
k.
(ii)
E
n
c
p
k
(
m
): input public key p
k and plaintext m
∈
M and output ciphertext c
∈
C.
(iii)
D
e
c
s
k
(
c
): input secret key s
k and ciphertext c and output the message encrypted in the ciphertext c.
(iv)
E
v
a
l
e
v
k
(
f
,
c
1
,
c
2
,
…
,
c
l
): input the evaluation key e
v
k, function f, and ciphertexts c
1
,
c
2
,
…
,
c
l and output a ciphertext c
f
∈
C that is obtained by applying the function f
:
M
l
→
M to c
1
,
c
2
,
…
,
c
l.


## 2.2. EmbeddingZ
q into Symmetric Group

According to Cayley’s Theorem, the additive groupZ
q is isomorphic to a group of cyclic permutations G, where x
∈
Z
q corresponds to a cyclic permutation that can be represented by an indicator vector with 1 in the x
+
1-th position. The permutation matrix can be obtained from the cyclic rotation of the indicator vector. The addition in Z
q leads to the composition of the permutations; the rounding function x
2
:
Z
q
→
{
0,1
} can be computed by summing the entries of the indicator vector corresponding to those in Z
q that round 1.By CRT,Z
q is isomorphic to the direct product Z
r
1
×
…
×
Z
r
t, where q
≔
∏
i
=
1
t
r
i, and r
i are small and powers of distinct primes. Similarly, Z
q embeds into symmetric group S
=
S
r
1
×
S
r
2
×
…
×
S
r
t.


## 3. Matrix GSW-FHE

### 3.1. Review Matrix GSW-FHE Scheme

In this section, we review the matrix GSW-FHE scheme. Letλ be the security parameter. The matrix GSW-FHE scheme is parameterized by an integer lattice dimension n, an integer modulus q, and a distribution χ over Z which is assumed to be sub-Gaussian; all of the parameters depend on λ. Let l
≔
log
⁡
q, m
≔
O
n
+
r
log
⁡
q, and N
≔
n
+
r
·
l. Let r be the amount of bits to be encrypted, which defines the message space 0,1
r
×
r. The ciphertext space is Z
q
(
n
+
r
)
×
N. The scheme uses the rounding function ·
2 where, for any x
∈
Z
q, x
2 outputs 1 if x is close to q
/
4 and 0 otherwise. Recall that g
T
=
1,2
,
…
,
2
l
-
1 and G
=
g
T
⨂
I
n
+
r.(i)
KeyGen1
λ
,
r: Sample a uniformly random matrix ←
U
Z
q
n
×
m, secret key matrix S
′
←
R
χ
r
×
n, and noise matrix E
←
R
χ
r
×
m. Let S
≔
I
r
∣
∣
-
S
′ and B
≔
S
′
A
+
E
A
∈
Z
q
(
n
+
r
)
×
m. Let M
(
i
,
j
)
∈
0,1
r
×
r
(
i
,
j
=
1,2
,
…
,
r
) be the matrix with 1 in the i
,
j
-
t
h position and 0 in the others. For all i
,
j
=
1,2
,
…
,
r, first sample R
(
i
,
j
)
←
U
0,1
m
×
N, and set(1)
P
i
,
j
≔
B
R
i
,
j
+
M
i
,
j
S
0
G
∈
Z
q
n
+
r
×
N
Output public keyp
k
≔
P
i
,
j
i
,
j
∈
[
r
]
,
B and secret key s
k
≔
S.
(ii)
S
e
c
E
n
c
s
k
M
∈
0,1
r
×
r: Sample random matrixes A
′
←
U
0,1
n
×
N and E
′
←
R
χ
r
×
N, parse S
=
I
r
∣
∣
-
S
′, and output the ciphertext(2)
C
≔
S
′
A
′
+
E
′
A
′
+
M
S
0
G
q
∈
Z
q
n
+
r
×
N
.
(iii)
P
u
b
E
n
c
s
k
p
k
,
M
∈
0,1
r
×
r: Sample a random matrix R
←
U
0,1
m
×
N, and output the ciphertext(3)
C
≔
B
R
+
∑
i
,
j
∈
r
:
M
i
,
j
=
1
P
i
,
j
∈
Z
q
n
+
r
×
N
,
whereM
[
i
,
j
] is the i
,
j
-
t
h element of M.
(iv)
D
e
c
s
k
(
s
k
,
C
): Output the matrix M
=
s
i
,
c
j
l
-
1
2
i
,
j
∈
[
r
], where s
i
T is the i
t
h row of S.


### 3.2. Deterministic Asymmetric Encryption

We define a new deterministic asymmetric encryption algorithm in the matrix GSW-FHE scheme as follows:(i)
D
e
t
e
P
u
b
E
n
c
p
k
M
∈
0,1
r
×
r: input p
k and M
∈
0,1
r
×
r and output the ciphertext(4)
C
≔
∑
i
,
j
∈
r
:
M
i
,
j
=
1
P
i
,
j
∈
Z
q
n
+
r
×
N
,whereM
[
i
,
j
] is the i
,
j
-
t
h element of M. The DetePubEnc algorithm has lower computational cost than S
e
c
E
n
c algorithm and P
u
b
E
n
c algorithm, and it only involves matrix addition, whereas the S
e
c
E
n
c algorithm and P
u
b
E
n
c algorithm involve both matrix multiplication and matrix addition.


## 3.1. Review Matrix GSW-FHE Scheme

In this section, we review the matrix GSW-FHE scheme. Letλ be the security parameter. The matrix GSW-FHE scheme is parameterized by an integer lattice dimension n, an integer modulus q, and a distribution χ over Z which is assumed to be sub-Gaussian; all of the parameters depend on λ. Let l
≔
log
⁡
q, m
≔
O
n
+
r
log
⁡
q, and N
≔
n
+
r
·
l. Let r be the amount of bits to be encrypted, which defines the message space 0,1
r
×
r. The ciphertext space is Z
q
(
n
+
r
)
×
N. The scheme uses the rounding function ·
2 where, for any x
∈
Z
q, x
2 outputs 1 if x is close to q
/
4 and 0 otherwise. Recall that g
T
=
1,2
,
…
,
2
l
-
1 and G
=
g
T
⨂
I
n
+
r.(i)
KeyGen1
λ
,
r: Sample a uniformly random matrix ←
U
Z
q
n
×
m, secret key matrix S
′
←
R
χ
r
×
n, and noise matrix E
←
R
χ
r
×
m. Let S
≔
I
r
∣
∣
-
S
′ and B
≔
S
′
A
+
E
A
∈
Z
q
(
n
+
r
)
×
m. Let M
(
i
,
j
)
∈
0,1
r
×
r
(
i
,
j
=
1,2
,
…
,
r
) be the matrix with 1 in the i
,
j
-
t
h position and 0 in the others. For all i
,
j
=
1,2
,
…
,
r, first sample R
(
i
,
j
)
←
U
0,1
m
×
N, and set(1)
P
i
,
j
≔
B
R
i
,
j
+
M
i
,
j
S
0
G
∈
Z
q
n
+
r
×
N
Output public keyp
k
≔
P
i
,
j
i
,
j
∈
[
r
]
,
B and secret key s
k
≔
S.
(ii)
S
e
c
E
n
c
s
k
M
∈
0,1
r
×
r: Sample random matrixes A
′
←
U
0,1
n
×
N and E
′
←
R
χ
r
×
N, parse S
=
I
r
∣
∣
-
S
′, and output the ciphertext(2)
C
≔
S
′
A
′
+
E
′
A
′
+
M
S
0
G
q
∈
Z
q
n
+
r
×
N
.
(iii)
P
u
b
E
n
c
s
k
p
k
,
M
∈
0,1
r
×
r: Sample a random matrix R
←
U
0,1
m
×
N, and output the ciphertext(3)
C
≔
B
R
+
∑
i
,
j
∈
r
:
M
i
,
j
=
1
P
i
,
j
∈
Z
q
n
+
r
×
N
,
whereM
[
i
,
j
] is the i
,
j
-
t
h element of M.
(iv)
D
e
c
s
k
(
s
k
,
C
): Output the matrix M
=
s
i
,
c
j
l
-
1
2
i
,
j
∈
[
r
], where s
i
T is the i
t
h row of S.


## 3.2. Deterministic Asymmetric Encryption

We define a new deterministic asymmetric encryption algorithm in the matrix GSW-FHE scheme as follows:(i)
D
e
t
e
P
u
b
E
n
c
p
k
M
∈
0,1
r
×
r: input p
k and M
∈
0,1
r
×
r and output the ciphertext(4)
C
≔
∑
i
,
j
∈
r
:
M
i
,
j
=
1
P
i
,
j
∈
Z
q
n
+
r
×
N
,whereM
[
i
,
j
] is the i
,
j
-
t
h element of M. The DetePubEnc algorithm has lower computational cost than S
e
c
E
n
c algorithm and P
u
b
E
n
c algorithm, and it only involves matrix addition, whereas the S
e
c
E
n
c algorithm and P
u
b
E
n
c algorithm involve both matrix multiplication and matrix addition.


## 4. Analysis on Matrix GSW-FHE

In the KeyGen algorithm of matrix GSW-FHE,M
(
i
,
j
)
S needs to be computed when generating public key P
i
,
j. We observe that (5)
M
i
,
j
S
=
M
i
,
j
I
r
∣
​
∣
-
S
′
=
M
i
,
j
0
-
s
j
1
′
…
-
s
j
n
′
0
,where right matrix is with -
s
j
1
′
,
…
,
-
s
j
n
′ in the i-th row and 0 in other rows. Let M
i
,
j
′
∈
Z
q
n
×
n be an n
×
n matrix, which satisfies the following matrix equation:(6)
I
r
-
S
′
·
M
i
,
j
0
0
M
i
,
j
′
=
M
i
,
j
0
-
s
j
1
′
…
-
s
j
n
′
0
.That is,(7)
-
S
′
·
M
i
,
j
′
=
0
-
s
j
1
′
…
-
s
j
n
′
0
.Viewing the elements of S
′ as the equation parameter and the elements of M
i
,
j
′ as variables, we can get equations from the above matrix equation: (8)
s
′
11
·
m
′
11
+
⋯
+
s
′
1
n
·
m
′
n
1
=
0
s
′
11
·
m
′
12
+
⋯
+
s
′
1
n
·
m
′
n
2
=
0
⋮
s
′
11
·
m
′
1
n
+
⋯
+
s
′
1
n
·
m
′
n
n
=
0
⋮
s
′
i
1
·
m
′
11
+
⋯
+
s
′
i
n
·
m
′
n
1
=
s
′
j
1
s
′
i
1
·
m
′
12
+
⋯
+
s
′
i
n
·
m
′
n
2
=
s
′
j
2
⋮
s
′
i
1
·
m
′
1
n
+
⋯
+
s
′
i
n
·
m
′
n
n
=
s
′
j
n
⋮
s
′
r
1
·
m
′
11
+
⋯
+
s
′
r
n
·
m
′
n
1
=
0
s
′
r
1
·
m
′
12
+
⋯
+
s
′
r
n
·
m
′
n
2
=
0
⋮
s
′
r
1
·
m
′
1
n
+
⋯
+
s
′
r
n
·
m
′
n
n
=
0According to the knowledge of linear algebra, the equations exit nontrivial solution if the rank of coefficient matrix is equal to the rank of the augmented matrix as below.(9)
r
a
n
k
s
′
11
s
′
12
…
s
′
1
n
…
s
′
11
s
′
12
…
s
′
1
n
⋮
s
′
i
1
s
′
i
2
…
s
′
i
n
…
s
′
i
1
s
′
i
2
…
s
′
i
n
⋮
s
′
r
1
s
′
r
2
…
s
′
r
n
…
s
′
r
1
s
′
r
2
…
s
′
r
n
r
n
×
n
=
r
a
n
k
s
′
11
s
′
12
…
s
′
1
n
0
…
s
′
11
s
′
12
…
s
′
1
n
0
⋮
s
′
i
1
s
′
i
2
…
s
′
i
n
s
′
j
1
…
s
′
i
1
s
′
i
2
…
s
′
i
n
s
′
j
n
⋮
s
′
r
1
s
′
r
2
…
s
′
r
n
0
…
s
′
r
1
s
′
r
2
…
s
′
r
n
0
r
n
×
n
+
1
.That is,(10)
r
a
n
k
s
′
11
s
′
12
…
s
′
1
n
⋮
s
′
i
1
s
′
i
2
…
s
′
i
n
⋮
s
′
r
1
s
′
r
2
⋯
s
′
r
n
r
×
n
=
r
a
n
k
s
′
11
s
′
12
…
s
′
1
n
0
⋮
s
′
i
1
s
′
i
2
…
s
′
i
n
s
′
j
1
…
s
′
i
1
s
′
i
2
…
s
′
i
n
s
′
j
n
⋮
s
′
r
1
s
′
r
2
…
s
′
r
n
0
r
+
n
-
1
×
n
+
1
.We denote the solution by M
-
(
i
,
j
), so we have (11)
-
S
′
·
M
-
i
,
j
=
0
-
s
j
1
′
…
-
s
j
n
′
0
=
M
i
,
j
·
-
S
′
.From the above analysis, we can derivate the circular security of the matrix GSW-FHE scheme.Theorem 1 (circular security).
If the equation(12)
-
S
′
·
M
i
,
j
′
=
0
-
s
j
1
′
…
-
s
j
n
′
0exits nontrivial solution M
-
i
,
j over Z
q, then the matrix GSW-FHE scheme is circular secure with function f
M
i
,
j
S.Proof.
Letc
1 be a ciphertext encrypting function f
M
i
,
j
S
=
M
i
,
j
S
0
G
∈
Z
q
(
n
+
r
)
×
N, c
1
=
B
R
+
P
i
,
j, and R
←
U
0,1
m
×
N. Then we have(13)
c
1
=
B
R
+
P
i
,
j
=
B
R
+
B
·
R
i
,
j
+
M
i
,
j
S
0
·
G
=
I
r
-
S
′
·
E
-
A
·
R
+
R
i
,
j
A
·
R
+
R
i
,
j
+
M
i
,
j
S
0
·
G
=
I
r
-
S
′
·
E
-
A
·
R
+
R
i
,
j
A
·
R
+
R
i
,
j
+
M
i
,
j
0
-
s
j
1
′
…
-
s
j
n
′
0
0
·
GFrom (12), we have(14)
c
1
=
I
r
-
S
′
E
-
A
·
R
+
R
i
,
j
+
I
r
-
S
′
·
M
i
,
j
0
0
M
-
i
,
j
G
A
·
R
+
R
i
,
j
=
I
r
-
S
′
E
-
A
·
R
+
R
i
,
j
+
I
r
-
S
′
·
0
0
0
M
-
i
,
j
G
+
I
r
-
S
′
·
M
i
,
j
0
0
0
G
A
·
R
+
R
i
,
j
=
I
r
-
S
′
E
·
R
+
R
i
,
j
-
A
·
R
+
R
i
,
j
+
M
-
i
,
j
·
g
T
⨂
I
n
+
I
r
-
S
′
·
M
i
,
j
0
0
0
G
A
·
R
+
R
i
,
j
=
I
r
-
S
′
E
·
R
+
R
i
,
j
-
A
·
R
+
R
i
,
j
+
M
-
i
,
j
·
g
T
⨂
I
n
A
·
R
+
R
i
,
j
-
M
-
i
,
j
·
g
T
⨂
I
n
+
I
r
-
S
′
·
M
i
,
j
0
0
0
G
M
-
i
,
j
·
g
T
⨂
I
n
=
I
r
-
S
′
E
~
-
A
~
A
~
+
I
r
-
S
′
·
M
i
,
j
0
0
0
G
M
-
i
,
j
·
g
T
⨂
I
n
=
S
′
A
~
+
E
~
A
~
+
M
i
,
j
·
g
T
⨂
I
r
0
0
0
M
-
i
,
j
·
g
T
⨂
I
n
.
E
~
≜
E
·
R
+
R
i
,
j; A
~
≜
A
·
R
+
R
i
,
j
-
M
-
(
i
,
j
)
·
g
T
⨂
I
n; therefore, we derivate that (15)
c
1
=
S
′
A
~
+
E
~
A
~
+
M
i
,
j
·
g
T
⨂
I
r
0
0
0
M
-
i
,
j
·
g
T
⨂
I
n
.As A
~
,
S
′
A
~
+
E
~ is an instance of LWE over Z
q
(
n
+
r
)
×
N, it satisfies uniform distribution over Z
q
(
n
+
r
)
×
N. Furthermore, c
1 obeys uniform distribution over Z
q
(
n
+
r
)
×
N.
On the other hand, suppose thatc
0 is a ciphertext encrypting0; that is,(16)
c
0
=
B
R
′
=
S
′
A
+
E
A
·
R
′
∈
Z
q
n
+
r
×
N
,
R
′
←
U
0,1
m
×
N
.It is also an instance of LWE over Z
q
(
n
+
r
)
×
N and obeys uniform distribution over Z
q
(
n
+
r
)
×
N, too. Therefore, distributions of c
0 and c
1 are computationally indistinguishable, and the advantage of probabilistic polynomial-time adversary A is negligible. So we can conclude that the matrix GSW-FHE is circular secure with function f
M
i
,
j
S.
From Theorem1, we can choose a good secret key that satisfies that (12) has solution via “reject sample” technique and obtain circular secure matrix GSW-FHE scheme.


## 5. Optimizing Bootstrapping

In this section, we describe how to optimize the bootstrapping procedure of [13] by introducing deterministic homomorphic plaintext slot-wise permutation.


### 5.1. Motivation

The decryption of all LWE-based FHE schemes consists of the inner product and rounding: for secret keys
∈
Z
q
d and a binary ciphertext c
∈
0,1
d, the decryption algorithm computes(17)
D
e
c
s
,
c
=
s
,
c
2
∈
0,1
.Note that the inner product itself is just a subset-sum of the Z
q-entries of s indicated by c and uses only the additive group structure of Z
q. Alperin-Sheriff and Peikert [20] proposed an efficient bootstrapping algorithm by embedding Z
q into permutation group S
q. Thus the rounding function is no longer just a sum, and it can be expressed as (18)
x
2
=
∑
v
∈
Z
q
s
.
t
.
v
2
=
1
x
=
v
,where each equality test [
x
=
v
] returns 0 for false and 1 for true. The equality test operation has homomorphic counterpart, called homomorphic equality test. Homomorphic equality test is an important primitive for optimizing bootstrapping procedure, and it has many other applications as mentioned in [25].Forx
,
v
∈
Z
r, they map to the r-by-r permutation matrices of group S
r and are denoted as τ
and
σ, respectively. The Eq? algorithm is described as follows:(i)
E
q
?
C
τ
=
c
i
,
j
τ
,
σ
∈
S
r: given a ciphertext encrypting some permutation τ
∈
S
r and a permutation σ
∈
S
r (in the clear), output a ciphertext c encrypting 1 if τ
=
σ; otherwise, output a ciphertext c encrypting 0:(19)
c
←
⊡
i
∈
r
c
σ
i
,
j
τ
⊡
g
.Note that the permutationσ goes through all permutations in S
r, and it is not masked in the homomorphic equality test E
q
? Algorithm; that is, σ
∈
S
r isin the clear.Letφ
i: Z
q
→
{
0,1
}
r be the isomorphism of an element in Z
q (q
≔
∏
i
=
1
t
r
i) into the cyclic permutation that corresponds to an element in Z
r
i, where r
≜
m
a
x
i
r
i. During homomorphic rounding process of work [13], φ
i
x is encrypted as part of public bootstrapping key and used in the homomorphic equality test algorithm.In fact,x traverses Z
q and does not carry any privacy information. It is not necessary to encrypt π
φ
i
x using SecEnc algorithm, which would increase computation cost. We propose optimizing homomorphic equality test algorithm by defining hybrid homomorphic plaintext slot-wise switching method, which reduces the computation cost of bootstrapping key generation.


### 5.2. Hybrid Homomorphic Plaintext Slot-Wise Switching

Plaintext slot-wise permutation is an important operation in application of packed FHE [23, 24]. It can be achieved by multiplying the encryption of a permutation and its inverse from left and right. We propose hybrid homomorphic plaintext slot switching procedure where the switch key is encrypted by symmetric and asymmetric encryption algorithm. The nice feature of our switching procedure is that part of switch key can be computed by deterministic public encryptions, which makes our procedure more efficient than that of [13].(i)
S
w
i
t
c
h
K
e
y
G
e
n
S
,
σ: Input a secret key matrix S
∈
Z
q
r
×
(
n
+
r
) and a permutation σ; let π
σ
∈
0,1
r
×
r be a matrix corresponding to σ, and compute(20)
W
σ
←
S
e
c
E
n
c
S
π
σ
,
W
σ
-
1
←
S
e
c
E
n
c
S
π
σ
T
.
Output the switch keys
s
k
σ
≔
(
W
σ
,
W
σ
-
1
). The algorithm is the same as the work in [13].
(ii)
S
l
o
t
S
w
i
t
c
h
s
s
k
σ
(
C
): Input a switch key s
s
k
σ and a ciphertext C; output (21)
C
σ
←
W
σ
⨀
C
⨀
W
σ
-
1
⨀
G
,
whereG
∈
Z
q
(
n
+
r
)
×
N is the fixed encryption of I
r with noise zero.
(iii)
D
e
t
e
S
w
i
t
c
h
K
e
y
G
e
n
S
,
σ: Input a secret key matrix S
∈
Z
q
r
×
(
n
+
r
) and a permutation σ, and compute(22)
D
W
σ
←
D
e
t
e
P
u
b
E
n
c
S
π
σ
,
D
W
σ
-
1
←
D
e
t
e
P
u
b
E
n
c
S
π
σ
T
.
Output the deterministic switch keyd
s
s
k
σ
≔
(
D
W
σ
,
D
W
σ
-
1
).
(iv)
D
e
t
e
S
l
o
t
S
w
i
t
c
h
d
s
s
k
σ
(
C
): Input a deterministic switch key d
s
s
k
σ and a ciphertext C; output (23)
C
σ
←
D
W
σ
⨀
C
⨀
D
W
σ
-
1
⨀
G
,
whereG
∈
Z
q
(
n
+
r
)
×
N is the fixed encryption of I
r with noise zero.


### 5.3. Optimized Bootstrapping Procedure

Our optimized bootstrapping procedure can be used to refresh ciphertexts of all standard LWE-based FHE. Letc
∈
0,1
d be the ciphertext to be bootstrapped, and let s
∈
Z
q
d be a secret key that corresponds to c
. The optimized bootstrapping procedure consists of two algorithms, HybirdBootKeyGen and HybirdBootstrap.(i)
H
y
b
r
i
d
B
o
o
t
K
e
y
G
e
n
p
k
,
s
k
,
s: Input a secret key s
k and public key p
k for our bootstrapping scheme and the secret key s
=
s
1
,
…
,
s
d
∈
Z
q
d for ciphertext to be refreshed; output a bootstrapping key b
k. For every i
∈
[
t
] and j
∈
[
d
], let π
φ
i
(
s
j
) be the permutation corresponding to φ
i
(
s
j
), and generate (24)
τ
i
,
j
←
R
S
e
c
E
n
c
s
k
d
i
a
g
φ
i
s
j
,
s
s
k
i
,
j
←
R
S
w
i
t
c
h
K
e
y
G
e
n
s
k
,
π
φ
i
s
j
,
where, for a vectorx
∈
Z
r, d
i
a
g
(
x
)
∈
Z
r
×
r is the square integer matrix that has x in its diagonal entries and 0 in the others. Then compute the hints used in homomorphic equality test on packed indictor vectors. For every i
∈
[
t
] and x
∈
Z
q such that x
2
=
1, compute(25)
d
s
s
k
φ
i
x
←
D
e
t
e
S
w
i
t
c
h
K
e
y
G
e
n
s
k
,
π
φ
i
x
.
Output the bootstrapping key(26)
b
k
≔
τ
i
,
j
,
s
s
k
i
,
j
,
d
s
s
k
φ
i
x
i
∈
t
,
j
∈
d
,
x
∈
Z
q
:
x
2
=
1
.
(ii)
H
y
b
r
i
d
B
o
o
t
s
t
r
a
p
b
k
(
c
): Input a bootstrapping keybk and a ciphertext c
∈
0,1
d; output the refreshed ciphertext C
∗. All the FHE schemes based on the LWE problem have similar decryption algorithm; that is, the decryption algorithm needs to compute s
,
c
2. There are two phases in the HybridBootstrap algorithm: evaluate the inner product and rounding.
Inner Product: For every i
∈
[
t
], homomorphically compute an encryption of φ
i
s
,
c. Let h
≔
m
i
n
⁡
{
j
∈
d
:
c
j
=
1
}. For i
=
1,2
,
…
,
t, set C
i
∗
≔
τ
i
,
h, and iteratively compute(27)
C
i
∗
←
R
S
l
o
t
S
w
i
t
c
h
s
s
k
i
,
j
C
i
∗
forj
=
h
+
1
,
…
,
d such that c
j
=
1.
Rounding: For each x
∈
Z
q such that x
2
=
1, homomorphically test the equality between x and s
,
c, and sum their results. The refreshed ciphertext is computed as(28)
C
∗
←
⨁
x
∈
Z
q
:
x
2
=
1
⨀
i
∈
t
⁡
D
e
t
e
S
l
o
t
S
w
i
t
c
h
d
s
s
k
φ
i
x
C
i
∗
⨀
P
1,1
.


### 5.4. Correctness Analysis

Lemma 2 (correctness).
Lets
k be the secret key for our scheme. Let c and s be a ciphertext and secret key of LWE-based FHE scheme. Then, for b
k
←
H
y
b
r
i
d
B
o
o
t
K
e
y
G
e
n
p
k
,
s
k
,
s, the refreshed ciphertext C
∗
←
H
y
b
r
i
d
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
} in the first slot.Proof.
Firstly,C
i
∗ is designed to encrypt φ
i
s
,
c
q, and(29)
⨀
i
∈
t
⁡
D
e
t
e
S
l
o
t
S
w
i
t
c
h
d
s
s
k
φ
i
x
C
i
∗
⨀
P
1,1is designed to encrypt 1 in the first slot if and only if x
=
s
,
c
m
o
d
q
. Finally, since the homomorphic sum is taken over every x
∈
Z
q such that x
2
=
1, C
∗ is designed to encrypt 1 if and only if s
,
c
2
=
1.


### 5.5. Security Analysis

If the bootstrapping scheme secret keys
k is generated independently of the secret keys s of FHE scheme from LWE, then Ind-CPA security of the bootstrapping key follows immediately from the security of hybrid homomorphic plaintext slot-wise switching, and the security of hybrid homomorphic plaintext slot-wise switching scheme resorts to the security of matrix GSW-FHE and hence the security of our bootstrapping scheme from LWE assumption.


### 5.6. Performance Analysis

Letq
=
O
~
(
λ
) be the modules of the ciphertext to be refreshed, and q has the form q
≔
∏
i
=
1
t
r
i, where r
i are small and powers of distinct primes. The following lemma allows us to choose a sufficiently large q by letting it be the product of all maximal prime powers r
i bounded by O
(
log
⁡
λ
), and then there exists t
=
O
log
⁡
λ
/
l
o
g
log
⁡
λ, where λ is security parameter.Lemma 3 (see [13, 20]).
For allx
≥
7, the product of all maximal prime powers r
i
≤
x is all at least e
x
p
3
x
/
4.On one hand, ourD
e
t
e
P
u
b
E
n
c algorithm involves matrix additions operation only, whereas SecEnc algorithm involves many matrix multiplication operations. Our bootstrapping key d
s
s
k
φ
i
x is optimized from s
s
k
φ
i
x. Therefore, our optimized bootstrapping key generation has lower computation complexity. The comparison of computational complexity is illustrated in Table 1.Table 1
Comparison of computational complexity.
Bootstrapping key
MM
MA
s
s
k
φ
i
x [13],0
≤
i
≤
t
O
log
⁡
λ
/
log
⁡
log
⁡
λ
O
log
⁡
λ
/
log
⁡
log
⁡
λ
d
s
s
k
φ
i
x
[
o
u
r
s
], 0
≤
i
≤
t
0
O
log
2
⁡
λ
/
log
⁡
log
⁡
λ
Note: MM denotes matrix multiplication operation; MA denotes matrix addition operation.On the other hand, we may implement a trade-off between computation and storage complexity. For everyk
,
l
∈
[
r
], P
k
,
l
=
S
e
c
E
n
c
s
k
(
M
k
,
l
) can be used as public bootstrapping key, delete d
s
s
k
φ
i
x from the bootstrapping key, and compute d
s
s
k
φ
i
x online when running rounding procedure. In view of d
s
s
k
φ
i
x being obtained by DetePubEnc algorithm, its computation involves only matrix additions. Therefore, our optimized bootstrapping drastically cuts down the size of the large public bootstrapping key by a third, paying matrix additions with negligible computation complex. The comparison of storage complexity is illustrated in Table 2.Table 2
Comparison of storage complexity of bootstrapping key.
Work
Bootstrapping key
[13]
τ
i
,
j
,
s
s
k
i
,
j
,
s
s
k
φ
i
x
i
∈
t
,
j
∈
d
,
x
∈
Z
q
:
x
2
=
1
[
o
u
r
s
]-1
τ
i
,
j
,
s
s
k
i
,
j
,
d
s
s
k
φ
i
x
i
∈
t
,
j
∈
d
,
x
∈
Z
q
:
x
2
=
1
[
o
u
r
s
]-2
τ
i
,
j
,
s
s
k
i
,
j
i
∈
t
,
j
∈
d
Note:[
o
u
r
s
]-1 denotes save computation complexity in the cost of the storage complexity; [
o
u
r
s
]-2 denotes save storage complexity in the cost of computation complexity.


## 5.1. Motivation

The decryption of all LWE-based FHE schemes consists of the inner product and rounding: for secret keys
∈
Z
q
d and a binary ciphertext c
∈
0,1
d, the decryption algorithm computes(17)
D
e
c
s
,
c
=
s
,
c
2
∈
0,1
.Note that the inner product itself is just a subset-sum of the Z
q-entries of s indicated by c and uses only the additive group structure of Z
q. Alperin-Sheriff and Peikert [20] proposed an efficient bootstrapping algorithm by embedding Z
q into permutation group S
q. Thus the rounding function is no longer just a sum, and it can be expressed as (18)
x
2
=
∑
v
∈
Z
q
s
.
t
.
v
2
=
1
x
=
v
,where each equality test [
x
=
v
] returns 0 for false and 1 for true. The equality test operation has homomorphic counterpart, called homomorphic equality test. Homomorphic equality test is an important primitive for optimizing bootstrapping procedure, and it has many other applications as mentioned in [25].Forx
,
v
∈
Z
r, they map to the r-by-r permutation matrices of group S
r and are denoted as τ
and
σ, respectively. The Eq? algorithm is described as follows:(i)
E
q
?
C
τ
=
c
i
,
j
τ
,
σ
∈
S
r: given a ciphertext encrypting some permutation τ
∈
S
r and a permutation σ
∈
S
r (in the clear), output a ciphertext c encrypting 1 if τ
=
σ; otherwise, output a ciphertext c encrypting 0:(19)
c
←
⊡
i
∈
r
c
σ
i
,
j
τ
⊡
g
.Note that the permutationσ goes through all permutations in S
r, and it is not masked in the homomorphic equality test E
q
? Algorithm; that is, σ
∈
S
r isin the clear.Letφ
i: Z
q
→
{
0,1
}
r be the isomorphism of an element in Z
q (q
≔
∏
i
=
1
t
r
i) into the cyclic permutation that corresponds to an element in Z
r
i, where r
≜
m
a
x
i
r
i. During homomorphic rounding process of work [13], φ
i
x is encrypted as part of public bootstrapping key and used in the homomorphic equality test algorithm.In fact,x traverses Z
q and does not carry any privacy information. It is not necessary to encrypt π
φ
i
x using SecEnc algorithm, which would increase computation cost. We propose optimizing homomorphic equality test algorithm by defining hybrid homomorphic plaintext slot-wise switching method, which reduces the computation cost of bootstrapping key generation.


## 5.2. Hybrid Homomorphic Plaintext Slot-Wise Switching

Plaintext slot-wise permutation is an important operation in application of packed FHE [23, 24]. It can be achieved by multiplying the encryption of a permutation and its inverse from left and right. We propose hybrid homomorphic plaintext slot switching procedure where the switch key is encrypted by symmetric and asymmetric encryption algorithm. The nice feature of our switching procedure is that part of switch key can be computed by deterministic public encryptions, which makes our procedure more efficient than that of [13].(i)
S
w
i
t
c
h
K
e
y
G
e
n
S
,
σ: Input a secret key matrix S
∈
Z
q
r
×
(
n
+
r
) and a permutation σ; let π
σ
∈
0,1
r
×
r be a matrix corresponding to σ, and compute(20)
W
σ
←
S
e
c
E
n
c
S
π
σ
,
W
σ
-
1
←
S
e
c
E
n
c
S
π
σ
T
.
Output the switch keys
s
k
σ
≔
(
W
σ
,
W
σ
-
1
). The algorithm is the same as the work in [13].
(ii)
S
l
o
t
S
w
i
t
c
h
s
s
k
σ
(
C
): Input a switch key s
s
k
σ and a ciphertext C; output (21)
C
σ
←
W
σ
⨀
C
⨀
W
σ
-
1
⨀
G
,
whereG
∈
Z
q
(
n
+
r
)
×
N is the fixed encryption of I
r with noise zero.
(iii)
D
e
t
e
S
w
i
t
c
h
K
e
y
G
e
n
S
,
σ: Input a secret key matrix S
∈
Z
q
r
×
(
n
+
r
) and a permutation σ, and compute(22)
D
W
σ
←
D
e
t
e
P
u
b
E
n
c
S
π
σ
,
D
W
σ
-
1
←
D
e
t
e
P
u
b
E
n
c
S
π
σ
T
.
Output the deterministic switch keyd
s
s
k
σ
≔
(
D
W
σ
,
D
W
σ
-
1
).
(iv)
D
e
t
e
S
l
o
t
S
w
i
t
c
h
d
s
s
k
σ
(
C
): Input a deterministic switch key d
s
s
k
σ and a ciphertext C; output (23)
C
σ
←
D
W
σ
⨀
C
⨀
D
W
σ
-
1
⨀
G
,
whereG
∈
Z
q
(
n
+
r
)
×
N is the fixed encryption of I
r with noise zero.


## 5.3. Optimized Bootstrapping Procedure

Our optimized bootstrapping procedure can be used to refresh ciphertexts of all standard LWE-based FHE. Letc
∈
0,1
d be the ciphertext to be bootstrapped, and let s
∈
Z
q
d be a secret key that corresponds to c
. The optimized bootstrapping procedure consists of two algorithms, HybirdBootKeyGen and HybirdBootstrap.(i)
H
y
b
r
i
d
B
o
o
t
K
e
y
G
e
n
p
k
,
s
k
,
s: Input a secret key s
k and public key p
k for our bootstrapping scheme and the secret key s
=
s
1
,
…
,
s
d
∈
Z
q
d for ciphertext to be refreshed; output a bootstrapping key b
k. For every i
∈
[
t
] and j
∈
[
d
], let π
φ
i
(
s
j
) be the permutation corresponding to φ
i
(
s
j
), and generate (24)
τ
i
,
j
←
R
S
e
c
E
n
c
s
k
d
i
a
g
φ
i
s
j
,
s
s
k
i
,
j
←
R
S
w
i
t
c
h
K
e
y
G
e
n
s
k
,
π
φ
i
s
j
,
where, for a vectorx
∈
Z
r, d
i
a
g
(
x
)
∈
Z
r
×
r is the square integer matrix that has x in its diagonal entries and 0 in the others. Then compute the hints used in homomorphic equality test on packed indictor vectors. For every i
∈
[
t
] and x
∈
Z
q such that x
2
=
1, compute(25)
d
s
s
k
φ
i
x
←
D
e
t
e
S
w
i
t
c
h
K
e
y
G
e
n
s
k
,
π
φ
i
x
.
Output the bootstrapping key(26)
b
k
≔
τ
i
,
j
,
s
s
k
i
,
j
,
d
s
s
k
φ
i
x
i
∈
t
,
j
∈
d
,
x
∈
Z
q
:
x
2
=
1
.
(ii)
H
y
b
r
i
d
B
o
o
t
s
t
r
a
p
b
k
(
c
): Input a bootstrapping keybk and a ciphertext c
∈
0,1
d; output the refreshed ciphertext C
∗. All the FHE schemes based on the LWE problem have similar decryption algorithm; that is, the decryption algorithm needs to compute s
,
c
2. There are two phases in the HybridBootstrap algorithm: evaluate the inner product and rounding.
Inner Product: For every i
∈
[
t
], homomorphically compute an encryption of φ
i
s
,
c. Let h
≔
m
i
n
⁡
{
j
∈
d
:
c
j
=
1
}. For i
=
1,2
,
…
,
t, set C
i
∗
≔
τ
i
,
h, and iteratively compute(27)
C
i
∗
←
R
S
l
o
t
S
w
i
t
c
h
s
s
k
i
,
j
C
i
∗
forj
=
h
+
1
,
…
,
d such that c
j
=
1.
Rounding: For each x
∈
Z
q such that x
2
=
1, homomorphically test the equality between x and s
,
c, and sum their results. The refreshed ciphertext is computed as(28)
C
∗
←
⨁
x
∈
Z
q
:
x
2
=
1
⨀
i
∈
t
⁡
D
e
t
e
S
l
o
t
S
w
i
t
c
h
d
s
s
k
φ
i
x
C
i
∗
⨀
P
1,1
.


## 5.4. Correctness Analysis

Lemma 2 (correctness).
Lets
k be the secret key for our scheme. Let c and s be a ciphertext and secret key of LWE-based FHE scheme. Then, for b
k
←
H
y
b
r
i
d
B
o
o
t
K
e
y
G
e
n
p
k
,
s
k
,
s, the refreshed ciphertext C
∗
←
H
y
b
r
i
d
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
} in the first slot.Proof.
Firstly,C
i
∗ is designed to encrypt φ
i
s
,
c
q, and(29)
⨀
i
∈
t
⁡
D
e
t
e
S
l
o
t
S
w
i
t
c
h
d
s
s
k
φ
i
x
C
i
∗
⨀
P
1,1is designed to encrypt 1 in the first slot if and only if x
=
s
,
c
m
o
d
q
. Finally, since the homomorphic sum is taken over every x
∈
Z
q such that x
2
=
1, C
∗ is designed to encrypt 1 if and only if s
,
c
2
=
1.


## 5.5. Security Analysis

If the bootstrapping scheme secret keys
k is generated independently of the secret keys s of FHE scheme from LWE, then Ind-CPA security of the bootstrapping key follows immediately from the security of hybrid homomorphic plaintext slot-wise switching, and the security of hybrid homomorphic plaintext slot-wise switching scheme resorts to the security of matrix GSW-FHE and hence the security of our bootstrapping scheme from LWE assumption.


## 5.6. Performance Analysis

Letq
=
O
~
(
λ
) be the modules of the ciphertext to be refreshed, and q has the form q
≔
∏
i
=
1
t
r
i, where r
i are small and powers of distinct primes. The following lemma allows us to choose a sufficiently large q by letting it be the product of all maximal prime powers r
i bounded by O
(
log
⁡
λ
), and then there exists t
=
O
log
⁡
λ
/
l
o
g
log
⁡
λ, where λ is security parameter.Lemma 3 (see [13, 20]).
For allx
≥
7, the product of all maximal prime powers r
i
≤
x is all at least e
x
p
3
x
/
4.On one hand, ourD
e
t
e
P
u
b
E
n
c algorithm involves matrix additions operation only, whereas SecEnc algorithm involves many matrix multiplication operations. Our bootstrapping key d
s
s
k
φ
i
x is optimized from s
s
k
φ
i
x. Therefore, our optimized bootstrapping key generation has lower computation complexity. The comparison of computational complexity is illustrated in Table 1.Table 1
Comparison of computational complexity.
Bootstrapping key
MM
MA
s
s
k
φ
i
x [13],0
≤
i
≤
t
O
log
⁡
λ
/
log
⁡
log
⁡
λ
O
log
⁡
λ
/
log
⁡
log
⁡
λ
d
s
s
k
φ
i
x
[
o
u
r
s
], 0
≤
i
≤
t
0
O
log
2
⁡
λ
/
log
⁡
log
⁡
λ
Note: MM denotes matrix multiplication operation; MA denotes matrix addition operation.On the other hand, we may implement a trade-off between computation and storage complexity. For everyk
,
l
∈
[
r
], P
k
,
l
=
S
e
c
E
n
c
s
k
(
M
k
,
l
) can be used as public bootstrapping key, delete d
s
s
k
φ
i
x from the bootstrapping key, and compute d
s
s
k
φ
i
x online when running rounding procedure. In view of d
s
s
k
φ
i
x being obtained by DetePubEnc algorithm, its computation involves only matrix additions. Therefore, our optimized bootstrapping drastically cuts down the size of the large public bootstrapping key by a third, paying matrix additions with negligible computation complex. The comparison of storage complexity is illustrated in Table 2.Table 2
Comparison of storage complexity of bootstrapping key.
Work
Bootstrapping key
[13]
τ
i
,
j
,
s
s
k
i
,
j
,
s
s
k
φ
i
x
i
∈
t
,
j
∈
d
,
x
∈
Z
q
:
x
2
=
1
[
o
u
r
s
]-1
τ
i
,
j
,
s
s
k
i
,
j
,
d
s
s
k
φ
i
x
i
∈
t
,
j
∈
d
,
x
∈
Z
q
:
x
2
=
1
[
o
u
r
s
]-2
τ
i
,
j
,
s
s
k
i
,
j
i
∈
t
,
j
∈
d
Note:[
o
u
r
s
]-1 denotes save computation complexity in the cost of the storage complexity; [
o
u
r
s
]-2 denotes save storage complexity in the cost of computation complexity.


## 6. Conclusions

Matrix GSW-FHE scheme encrypts multibit message and supports complex homomorphic matrix operations and can be used to optimize the bootstrapping procedure. We analyse circular security of matrix GSW-FHE scheme and derive a sufficient condition of circular security for matrix GSW-FHE scheme. That is, if the equations about secret key have solution overZ
q, the matrix GSW-FHE scheme satisfies circular security with function f
M
i
,
j
S. Therefore, we can choose a good secret key that satisfies the sufficient condition via “reject sample” technique and furthermore obtain circular secure matrix GSW-FHE scheme.We also propose hybrid homomorphic plaintext slot-wise switching method by defining deterministic public encryption algorithm in matrix GSW-FHE, which significantly reduces computational complex or space complex of bootstrapping key generation, thus optimizing the bootstrapping procedure of Hiromasa and so forth. Meanwhile, performance analysis validates the effectiveness of the proposed optimized bootstrapping scheme.Some questions remain for further study, such as the probability analysis of our sufficient condition and the sufficient and necessary condition for circular security of the matrix GSW-FHE scheme [26]. And to make a fair comparison with the state-of-the-art bootstrapping schemes such as FHEW [21], WT [22], and so forth, detailed security, parameters, and efficiency experiment analysis remain to be a future work.



---

*Source: 6362010-2018-12-19.xml*