86 N. LI ET AL.: EFFICIENT FULLY HOMOMORPHIC ENCRYPTION WITH LARGE PLAINTEXT SPACE
can homomorphically extract the MSB (Most Signi-
cant Bit) of the plaintext from the external ciphertext.
By constructing a faster msbExtract process, FHEW
can perform bootstrapping within a second. However,
only if the plaintext space is
Z
2
that the msbExtract
algorithm can homomorphically extract the MSB of the
plaintext.
In LATINCRYPT’2015, Biasse and Ruiz proposed a
new scheme BR15 [26], which introduces homomorphic
member tests and parallelizes the bootstrapping process.
However, BR15 is based on a special cyclotomic polyno-
mial ring, which will aect the performance of FFT/NTT
(Fast Fourier Transformation/Number Theoretic Trans-
form) during bootstrapping. However, comparing to
Helib [20], BR15 increases the number of parallels, which
resultsinnearly100timesimprovementinperformance.
Contributions: The main improvement of our work on the
FHEW scheme lies in two parts. First, we optimize the
decryption algorithm in basic LWE encryption scheme
to msdExtract algorithm, which can homomorphically
extract the most signicant digit of the plaintext, thus
allow the bootstrapping procedure to refresh the encryp-
tions of message modulo an integer t ≥ 2.
Second, we give a detailed process about how to imple-
ment the msdExtract algorithm by employing the homo-
morphic accumulator and present the process of general
bootstrapping via msdExtract algorithm and homomor-
phic accumulator. As operations during the general boot-
strapping is implemented directly on encrypted data, and
the encryption algorithm follows the basic LWE scheme
and external scheme in FHEW, the security of our scheme
is the same as FHEW, and our scheme has wide applica-
tions for large plaintext space such as the protection of
gene data, which can be represented by
Z
4
(four kinds of
bases in DNA: A,T,G,C).
Organization: Therestofthepaperisorganizedasfol-
lows. Some background knowledge is provided in Section
2. In Section 3, we rstly introduce the basic LWE
symmetric encryption scheme, then analyze the opti-
mization of decrypting process from rounding func-
tion to msdExtract function, and give the construction
of the general bootstrapping via a homomorphic accu-
mulator. In Section 4, we analyze the construction and
components in homomorphic accumulator detailedly.
Section 5 analyzes our scheme in aspects of the correct-
ness of the general bootstrapping, scheme’s computation
complexity and security. The conclusion is provided in
Section 6.
2. MATHEMATICAL PRELIMINARIES
This section introduces some symbols, basic concepts,
and denitions used in our scheme. For a list of vec-
tors or matrices a
1
, a
2
, ..., a
l
,weuse(...) for vertical
concatenation, and [...] for horizontal concatenation.
2.1 Distribution
We dene the randomized rounding function ψ :
R →
Z,whichsatisesψ(x + n) = ψ(x) + n for arbitrary
x ∈
R and n ∈ Z.Wheninputx ∈ Z,wehaveψ(x) =
ψ(0) + x as a special case, which means that a certain
noise ψ(0) isaddedtotheinputx.Wedeneψ(x) − x
as the rounding error of ψ(x), and typically the error
distribution ψ(x) − x < q/2t.
We dene that the random variable x ∈
R is a sub-
Gaussian distribution of parameter α, if its moment-
generating function (MGF) satises E[exp(2π tX)] ≤
exp(πα
2
t
2
)αfor all t ∈ R, and then we have Pr{| ≥ t}≤
2exp(−π t
2
/α
2
)
for
t ≥ 0. The concept of sub-Gaussian
distribution can be extended to vector x and matrice X.
For unit vector u,if< u, x > isasub-Gaussiandistribu-
tion, then x is also a sub-Gaussian distribution. For all
theunitvectorsu and v,ifu
t
Xv is a sub-Gaussian dis-
tribution, so is X. From the denition, we can see that
if concatenate multiple variables which are sub-Gaussian
with parameter α, the resulting vectors and matrices are
also sub-Gaussian with parameter α.
2.2 Cyclotomic Ring
For security parameter λ,let
2N
(X) =X
N
+ 1bethe
2N-th cyclotomic polynomial, where N = N(λ) is a
power of 2. Let the cyclotomic ring
R = Z[X]/(X
N
+ 1),
and
R
Q
= R/(QR) denotes the residue ring of R mod-
ulo an integer Q, and then there is an isomorphic map-
ping
R
Q
Z
N
Q
which is dened as f : a →
a,wherea =
a
0
+ a
1
x + ...+ a
N−1
x
N−1
∈ R,
a = (a
0
, a
1
, ..., a
N−1
)
∈
Z
N
.Thenotation· canbeextendedtovectorand
matrix over
R. We dene the Euclidean length of ring
elements as ||a|| = ||
a|| =
i
|a
i
|
2
,andthespectral
norm of a matrix R ∈
R
w×k
of ring elements as s
1
(R) =
sup
x∈R
k
\{0}
||R · x||/||x||.
Given the ring element r ∈
R,wedenethefunction
⇒
·
as
⇒
r
=
⎡
⎢
⎢
⎢
⎣
r
0
r
N−1
... r
1
r
1
r
0
r
2
.
.
.
.
.
.
.
.
.
.
.
.
r
N−1
r
N−2
... r
0
⎤
⎥
⎥
⎥
⎦
∈ Z
N×N
(1)
剩余12页未读，继续阅读
weixin_38647925
- 粉丝: 2
- 资源: 913
我的内容管理
展开
最新资源
- C++多态实现机制详解：虚函数与早期绑定
- Java多线程与异常处理详解
- 校园导游系统：无向图实现最短路径探索
- SQL2005彻底删除指南：避免重装失败
- GTD时间管理法：提升效率与组织生活的关键
- Python进制转换全攻略：从10进制到16进制
- 商丘物流业区位优势探究：发展战略与机遇
- C语言实训：简单计算器程序设计
- Oracle SQL命令大全：用户管理、权限操作与查询
- Struts2配置详解与示例
- C#编程规范与最佳实践
- C语言面试常见问题解析
- 超声波测距技术详解：电路与程序设计
- 反激开关电源设计：UC3844与TL431优化稳压
- Cisco路由器配置全攻略
- SQLServer 2005 CTE递归教程：创建员工层级结构
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
