564 Journal of Cryptologic Research 密码学报 Vol.4, No.6, Dec. 2017
格以 Gentry 方案为蓝图的 FHE 构造; 基于 LWE 假设, 利用密钥交换等技术来实现 FHE 的构造; 基于
LWE 假设, 利用近似特征向量构造的 FHE 方案; 以及基于 NTRU, 利用密钥交换等技术来实现 FHE 的
构造. 经典全同态加密方案的构造方法和继承关系如图1所示.
..
Gentry-FHE
[13]
.
DGHV10
[14]
.
CMNT11
[21]
.
CNT12
[22]
.
CCK+13
[23]
.
CLP14
[35]
.
NK15
[36]
.
BBL17
[37]
.
SV10
[18]
.
SS10
[19]
.
GH11a
[28]
.
GH11b
[27]
.
LMSV11
[38]
.
GHS12a
[29]
.
GHS12b
[30]
.
BV11a
[16]
.
BV11b
[15]
.
BGV12
[17]
.
Bra12
[39]
.
AP13:
[40]
.
BV14:
[41]
.
AP14,HS14:
[42, 43]
.
DM15,HS15:
[44, 45]
.
GSW13
[32]
.
AP14
[42]
.
BL14
[46]
.
HAO15
[47]
.
CM15
[48]
.
MW16
[49]
.
BP16
[50]
.
PS16
[51]
.
LTV12
[52]
.
BLLN13
[53]
.
BLN14
[54]
.
LLN14
[55]
.
CO17
[56]
.
第一代
.
第二代
.
第三代
.
整数
.
理想格
.
(ring)-LWE
.
特征向量
.
NTRU
图 1 全同态加密发展概况
Figure 1 Brief history of fully homomorphic encryption
如图1所示, 第 1 列是基于整数上 AGCD 假设的部分 FHE 经典方案, 第 2–4 列则分别是基于格上
LWE 假设的第一、二、三代部分经典的 FHE 方案, 第 5 列则是基于 NTRU 格的部分 FHE 经典方案.
下文着重总结基于格上 LWE 假设的 FHE 方案.
2.1 基于格基的全同态加密研究现状
2.1.1 基于理想格的 (第一代) 全同态加密研究
Gentry 的 FHE 体制的设计是基于理想格 (ideal lattice) 上的有界编码问题 (bounded distance
decoding problem, BDDP) 和稀疏子集和问题 (sparse subset sum problem, SSSP), 其构造过程分为两
步: 首先, 设计一个具备有限次密文运算的同态加法和同态乘法的近似同态 (somewhat homomorphic
encryption, SWHE) 加密体制, 其运算能力是借助于格上的噪声向量实现. 随着密文运算次数的增加, 噪
声逐步增大, 当其超出某一阀值时, 就会出现解密错误. 为此, 引入 “Bootstrapping” 程序, 利用重加密的
方法对密文进行更新, 以此控制噪声膨胀, 保证解密正确性, 从而实现任意次的密文同态运算. 尽管该方法
可以实现全同态加密所希望的任意次密文运算, 但 Bootstrapping 的过程需将私钥加密后作为公共参数予
以公开. 因此, 利用 Bootstrapping 实现的全同态加密体制无法抵抗选择密文攻击 (CCA), 只能达到选择
明文攻击 (CPA) 安全. 随后, 文献 [28, 29] 则分别对 Bootstrapping 程序进行改进, 利用主理想格的代数
结构取代 Gentry
[13]
的理想格, 目的是减少私钥尺寸, 提高解密算法的计算效率, 但缺陷是将私钥由 n 维
向量约减到 1 维向量上, 从而增加了方案遭受 Key Recovery 攻击的概率. 此外, Smart 和 Vercauteren
在 Gentry 方案
[13]
的基础上, 提出具有相对小的密钥和密文尺寸的 FHE 方案
[18]
, 在效率上有所提高.
而 Stehlé 和 Steinfel 利用 “可忽略概率解密错误” 这一弱化条件, 对 Gentry 方案
[13]
进行优化, 提出了
较快速的 FHE 方案
[19]
, 允许降低比特计算复杂度. 但由于 SSSP 假设研究尚不成熟且安全性不充分,
为了使 FHE 方案不再依赖于 SSSP 假设, Brakerski 和 Vaikuntanathan
[15, 16]
等人于 2011 年提出基于