© 2024 Journal of Northwestern Polytechnical University. All rights reserved.

随着大数据、云计算等技术的发展与应用, 数据隐私保护问题成为目前隐私计算领域研究的重点问题。同态加密方案可以直接对加密数据进行操作, 达到与对明文进行同样操作的结果, 可以有效完成隐私计算任务需求, 已成为目前的研究热点。

2017年, Cheon等[1]首次提出了可以支持浮点数运算的层次同态加密方案CKKS17, 该方案基于单指令多数据操作(single instruction multiple data, SIMD), 可以高效地进行算术运算。因此, 该方案应用价值较高, 已经应用于全基因组关联分析[2]、聚类分析[3]以及神经网络[4]等领域。

但CKKS17方案为层次同态加密方案, 其仅能支持有限次同态加法和同态乘法运算。可以进行任意次同态加法和同态乘法运算的加密方案被称为全同态加密方案, 需要使用自举技术才能将层次同态加密方案转换为全同态加密方案。Cheon等[5]为CKKS17设计了近似同态加密的自举方案, 从而实现全同态加密方案。该方案的4个主要步骤是模数提升、槽转换到系数、模函数和系数转换到槽数。模数提升是将位于小模数q上的密文c_t提升到大模数Q上, 其中Q≫q, s_k, m分别表示密文c_t的私钥和明文, 即〈c_t, s_k〉mod q, 那么就有〈c_t, s_k〉mod Q=qI+m, I是一个整数。槽转换到系数和系数转换到槽数是2个线性转换过程。模函数为(qI+m)mod q=m, 但CKKS方案只支持同态加法和同态乘法, 因此无法直接计算非多项式函数的模函数, 而需要将其转换成三角函数q/2π·sin (2π(qI+m)/q), 再利用泰勒展开公式计算三角函数。

但自举技术的运算耗时过大, 不利于结合现实应用。为提高近似同态加密方案的自举效率, 本文提出一种基于余数系统的小间隔插值拟合自举方法, 通过在多个小间隔内对模函数进行近似拟合完成自举过程中模运算近似拟合, 并通过余数系统提高方案的模乘运算和模逆运算计算速度, 最终使模运算计算耗时降为目前最新公布的近似同态加密库HEAAN[6]的8%。

1 相关工作

CHK+18a方案[5]利用等价无穷小性质, 当x→0时, x与sinx为等价无穷小, 并通过模函数曲线发现, 可以通过[〈c_t, s_k〉]_q≈q/2π·sin(2π/q·〈c_t, s_k〉)来对模函数进行近似计算。同时在计算的过程中, CHK+18a方案使用欧拉公式e^ix=cosx+isinx以及幂运算e^i·2θ=(e^i·θ)²对三角函数的计算进行简化处理, 最终通过泰勒展开多项式进行计算, 从而完成了模运算, 最终实现了自举技术。但该方案在使用泰勒展开多项式对模函数进行近似计算过程中, 为保证精度要求, 所需多项式的次数过高, 从而导致方案计算效率下降。

针对于此, CCS19方案[7]使用切比雪夫插值方法取代泰勒展开方法, 并通过优化Paterson-Stockmeyer算法来快速计算密文上的切比雪夫插值, 将每个明文槽的自举时间提高2个数量级, 即从1 s减少至0.01 s, 但计算效率依然过低。HK20方案[8]通过考虑密文尺寸和密文模尺寸之间的比例对计算正弦函数过程进行优化, 并最终用余弦函数替代正弦函数, 最终使得方案的标量乘法运算量下降到CCS19方案的50%, 然而该方案得到的近似多项式系数过大, 从而导致计算结果精度较差, 无法满足实际应用中的高精度需求。JKA+21方案[9]通过结合GPU对近似同态加密的运行效率进行了极大提升, 该方案发现GPU并行化难点在于高主存带宽需求, 利用内存中心化方法进行处理, JKA+21方案单个同态乘法操作与此前GPU实现相比加速了7.02倍, 在GPU上每比特自举平均用时0.423 μs, 相较于此前单线程CPU加速了257倍。CN22方案[10]使用正弦级数替代CHK+18a方案中的正弦函数, 大幅度提升了方案的计算精度, 自举精度最高可以达到100多位。但由于存在从正弦级数{sin(kx)}到正弦函数{sin^k(x)}幂次的线性变换, 与先前文献中的sinx相比, 其计算效率基本不变。

方案CHK+18b[11]将余数系统与近似同态加密相结合提升方案的模乘、模逆运算效率, 但CHK+18b没有提供余数系统下的自举方案。BMTH21[12]方案是第一个余数系统下的自举方案, 通过采用优化密钥交换技术和矩阵向量乘法对方案效率进行提升。LLL+21[13]提出了一种求模函数和三角函数的minimax近似多项式的快速算法——改进的多区间雷米兹(Remez)算法, 减少了自举过程中的误差, 精度比HK20方案提高了5.4~10.2比特, 但该方案的计算时间是BMTH21方案的20倍左右。本文为基于余数系统的近似加密同态方案提出一种小间隔插值拟合自举方法。对于模函数(qI+m)modq=m, I∈(-K, K), 且I为整数, 结合模函数的周期性, 可以将其分割成2K小区间, 在每个小区间内使用拉格朗日插值法得到高精度的小次数拟合多项式, 2K小区间对应2K个拟合多项式。使用同态加密比较算法算出密文所处的区间, 在小区间内进行模函数计算。与CHK+18a、HK20等相比较, 该方法可大幅度提高自举方案的计算效率和计算精度, 满足了隐私计算、机器学习等领域的应用需求。

2 符号定义

本文使用加粗小写字母表示向量, 如a, a_i表示向量a的第i个元素, 无特殊说明下标从0开始, 对数的底数为2。Z代表整数, R代表实数, Q代表有理数, 代表环, Z⁺代表正整数, Zⁿ代表整数上的n维向量, Z_qⁿ代表模q整数上的n维向量, Z^n×m代表整数上n行m列的矩阵, 代表模为q的剩余环。对于实数分别表示对r进行向下取整、近似取整和向上取整。对于长度为n的向量v, ‖v‖₀表示0范数, 为向量v中非零元素的个数; ‖v‖₁表示一范数, 表示向量v中所有元素绝对值之和, 即‖v‖₁=|x₀|+|x₁|+|x₂|+…+|x_n-1|; ‖v‖₂表示二范数, 表示向量v中所有元素平方和的开方, 即‖v‖₂=; ‖v‖_∞表示无穷范数, 表示向量中所有元素绝对值的最大值, 即‖v‖_∞=max(|x₀|, |x₁, x₂|, …, |x_n-1|)。x←D表示从分布D中随机采样得到样本x, U代表均匀分布, DG(σ²)表示Z^N上的方差为σ²的离散高斯分布; 规定均匀分布HWT(h)产生一个汉明权重为h、长度为N的向量{±1}^N; 规定对于给定的概率ρ, 分布ZO(ρ)以ρ/2的概率取+1或-1, 以1-ρ的概率取0, 其中0≤ρ≤1, x_B表示最大值上限为B的随机分布。使用〈a, b〉表示2个向量的内积。复合函数f[g(x)]记作g(x)f(x), 函数f(x)的导数记作f′(x)。

λ为安全参数。通过安全参数λ对参数P进行选择，记作P=P(λ)。

3 基于余数系统的小间隔插值拟合自举方法

本文将余数系统与近似同态加密结合来提高运算效率, 并通过采用小间隔插值拟合方法对自举过程中的模运算进行优化。

3.1 基于余数系统的小区间插值拟合自举算法

基于余数系统的小间隔插值算法包含余数系统下的小区间插值算法、余数系统下的区间判断算法和余数系统下的新鲜密文计算方法。

3.1.1 基于余数系统的小间隔插值算法

使用正弦函数S(t)=q/2πsin(2π/q·t)对模函数F(t)=[t]_q进行近似计算时, 对周期为q的S(t), 可以将S(t)分割为2K+1个小区间, 分别为[-q/2, -Kq, q/2-Kq], (-q/2-(K-1)q, q/2-(K-1)q], …, (-3q/2, -q/2], (-q/2, q/2], (q/2, 3q/2], …, (-q/2+Kq, q/2+Kq]在每个小区间内对S(t)进行拉格朗日插值拟合。

对于上述2K+1个小区间内的函数, 使用拉格朗日插值方法对函数进行多项式拟合。仍然选取函数值趋近于x轴附近的曲线进行拟合, 用x_left表示插值左端点, x_right表示插值右端点。

由正弦函数周期性可知, 区间[x_left, x_right]一定包含在某一个完整的区间(-q/2+iq, q/2+iq]中, 其中i∈Z∩[-2K, 2K]。

对于函数y=f(x)在区间[x_left, x_right]上的n+1个节点x_i, i=0, 1, …, n, x₀＜x₁＜…＜x_n, 有函数值y_i=f(x_i), 按照 形式计算计算拉格朗日插值基函数, 同时选择满足f(x)-的最小n值作为拉格朗日插值多项式的次数n_ploy。

在进行拉格朗日插值过程中, 拉格朗日插值多项式的次数为n_ploy时需要选取n_ploy+1个插值点, 记第i个区间的n_ploy+1个插值点分别为x_{i, 0}, x_{i, 1}, …, x_{i, nploy-1}, x_{i, nploy}。规定选择区间左右端点作为插值点, 则x_{i, 0}=x_left, x_{i, nploy}=x_right。

对于函数y=f(x)=S(t)=q/2π·sin2π/q·t, 计算2个端点x_{i, 0}和x_{i, nploy}处的函数值, 分别为y_{xi, 0}=f(x_{i, 0})和y_{xi, nploy}=f(x_{i, nploy})。按照y值等间距选取插值点x_{i, j}, j=0, 1, …, n_ploy, y值间隔Δy=(y_{xi, nploy}-y_{xi, 0})/n_ploy, 则y_{xi, j}=y_{xi, 0}+j×Δy。通过y=f(x)的反函数x=f^-1(y)计算出n_ploy-1个插值点: x_{i, j}=f^-1(y_{xi, j}), j=1, 2, …, n_ploy-1。

将上述n_ploy+1个插值点(x_{i, j}, y_{xi, j})进行拉格朗日插值拟合, 得到多项式函数L(x)=a₀+a₁x+a₂x²+…+a_nployx^n_ploy。

对于区间2K+1个小插值区间做如上操作, 得到包含2K+1个插值多项式的拉格朗日插值多项式族, 这2K+1个插值多项式构成了对原始函数S(t)=q/2π·sin2π/q·t选定小区间内的近似拟合。

3.1.2 基于余数系统的区间判断算法

用E_ncpk(μ)表示使用公钥pk对明文μ加密后的结果。插值区间左端点密文值向量为(E_ncpk(x_{0, 0}), E_ncpk(x_{1, 0}), …, E_ncpk(x_{2K, 0})), 插值区间右端点密文值向量为(E_ncpk(x_{0, u}), E_ncpk(x_{1, u}), …, E_ncpk(x_{2K, u}))。为避免比较运算过程中密文值恰好等于左右端点值而使比较结果为1/2, 而非期待的0或1, 将左端点由-q/2+iq移到-q/2+iq-q/2=(i-1)q, 右端点由q/2+iq移动到q/2+iq+q/2=(i+1)q。此时端点区间为[(i-1)q, (i+1)q), 每一个端点区间长度由q增长为2q, 而实际函数所在区间仍为[-q/2+iq, q/2+iq)。此时再进行c_t与比较区间左端点或右端点的计算, 就不会出现插值绝对值过小问题。

端点区间长度由q增长为2q, 计算后插值的取值范围也从(0, q)增长到了(0, 2q), 需要对插值结果乘1/2进行归一化操作保证结果的准确性。

则可以计算得到实际使用的插值区间左端点密文值向量为

实际使用的插值区间右端点密文值向量为

比较函数C_mpn(a, b)的复合多项式次数选择为2n+1, 当2n+1=15时, 基于余数系统的同态加密方案多项式计算流程如算法1所示。

算法1 E_valPoly(x, 2n+1, a₁, …, a_2n+1)

输入: 一次项x, 多项式次数2n+1以及多项式系数a_2i+1, 0≤i≤n

输出: 多项式计算结果

1:x²=x*x

2:S_um+=a₁*x

3:x=R_S(x)

4:x³=x*x², x⁴=x²*x²

5:S_um+=a₃*x³

6:x=R_S(x)

7: x⁵=x^x*x⁴, x⁷=x³*x⁴, x⁸=x⁴*x⁴

8:S_um+=a₅*x⁵+a₇*x⁷

9:x=R_S(x), x³=R_S(x³)

10:x⁹=x*x⁸, x¹¹=x³*x⁸, x¹³=x⁵*x⁸, x¹⁵=x⁷*x⁸

11:S_um+=a₉*x⁹+a₁₁*x¹¹+a₁₃*x¹³+a₁₅*x¹⁵

12:return S_um

可以看到, 在步骤4、步骤7和步骤10的计算过程中, 每一步骤各个计算均独立, 故而可以对每一步骤的计算进行并行化处理。同时可以看到, 步骤5和6、步骤8和9间是独立的, 同样可以并行化处理进行计算。

规定归一化向量T=(Kq, (K-1)q, …, 2q, q, 1, q, 2q, …, (K-1)q, Kq), ε表示插值小区间长度, 即ε=x_right-x_left。将待自举密文c_t分别与(1)和(2)式中插值区间左端点密文值和插值区间右端点密文值进行比较。计算c_t与 G中各元素的比较值:

式中，0≤i≤2K。v_i表示待自举密文c_t与G_i之间的明文大小关系, D_ecsk(c_t)>D_ecsk(G_i)时, v_i=E_ncpk(1), 否则v_i=E_ncpk(0)。同样地, 计算c_t与E中各元素的比较值

式中，0≤i≤2K。w_i表示待自举密文c_t与E_i之间的明文大小关系, D_ecsk(c_t)＜D_ecsk(E_i)时, w_i=E_ncpk(1), 否则w_i=E_ncpk(0)。

计算区间判断算法的结果

若c_mpresi=E_ncpk(1), 则代表待自举密文属于第i个区间; 若c_mpresi=E_ncpk(0), 则代表待自举密文不属于第i个区间。

3.1.3 基于余数系统的新鲜密文计算

将待自举密文c_t分别代入插值多项式L_i(x), i=0, 1, …, 2K, 得到插值结果向量L_res=(L₀(c_t), L₁(c_t), …, L_2K(c_t))。

对于较小的模q, 将其替换为新的模Q, 满足Q≫q, 并且满足

计算自举后的新鲜密文

3.2 模乘模逆运算实现

同态加密方案在实现过程中模乘模逆运算占据了大量的运算时间。余数系统可以高效地将大数运算转化为多个互相独立的小数进行等效运算, 可以为基于近似同态加密方案的实现提供良好效率支持。但因在使用余数系统进行运算过程中, 需要尽可能地避免进行除法运算, 这就使得在余数系统下进行取模操作变得困难。可以使用蒙哥马利模乘算法来实现余数系统中的除法运算。

蒙哥马利模乘算法可以不使用除法运算就实现模约减运算。需要将模乘算法改进成余数系统下的蒙哥马利模乘算法。对于基A =(a₁, a₂, …, a_i, …, a_l)和基B =(b₁, b₂, …, b_i, …, b_l), 有运算元素X和Y, [X]_A∪B和[Y]_A∪B为X和Y在基A和基B下的表示, x_k和y_k为X和Y在基A和基B下的第k个元素。|-N_i^-1|=(-N_i^-1)mod a_i为N_i在模a_i下的模逆, |-H_j^-1|=(-H_j^-1)mod b_j为H_j在模b_j下的模逆。N为大素数X和Y的模数, X, Y＜2N, 为蒙哥马利模乘因子。余数系统下的蒙哥马利模乘运算的具体步骤见算法2。

算法2 RNSMonModMult(X, Y, N)

输入: [X]_A∪B, [Y]_A∪B和N

输出: r=XYH^-1mod N

1:for(i=1;i≤l; ++i)

2: w_i=(x_i×y_i) mod a_i

3: z_i=(w_i×|-N_i^-1|_ai) mod a_i

4:z_i=Conv(z_i)

5:for(j=0;j≤l; ++j)

6: w_j=(x_j×y_j) mod b_j

7: f_j=(w_j+z_j×N_j) mod b_j

8: r_j=(f_j×|-H_i^-1|_bj) mod b_j

9:r_i=Conv(r_i)

10:return(r_i, r_j)

可以通过费马小定理在素域上完成模逆运算的高效实现。算法3为使用费马小定理进行模逆运算。

算法3 FermModInv(g)

输入: 非零元素g

输出: 模逆元素g^-1

1:c=g^q-2

2:return c

相较于使用费马小定理来实现模逆运算, 在普遍情况下, 扩展欧几里得算法实现模逆运算更为高效。但扩展欧几里得算法需要比较运算以及模运算, 这些运算在基于近似计算的同态加密方案中是较难计算的, 实现复杂耗时高。因此在实际计算模逆运算时, 使用费马小定理来实现模逆运算是基于近似同态加密方案中更为高效实际的计算方法。

4 噪声与安全性分析

4.1 噪声分析

对于第l层的加密后的密文c_t, 其对应明文为m, 重缩放算法返回一个第l-1层的密文, 且该密文对应明文为q_l^-1·m, 并且满足q_l^-1·m≈q^-1·m。这一约等于过程相当于引入了新的计算误差。现对基于余数系统的近似同态加密方案噪声进行分析。

记ζ=e^-πi/N, K=Q[X]/(X^N+1)上的正规嵌入映射定义为a(X)→(a(ζ), a(ζ³), …, a(ζ^2N-1)), 其无穷范数被称为正规嵌入范数, ‖a‖_∞^can=‖σ(a)‖_∞。对于解码映射τ和任意a∈K, 有‖a‖_∞^can=‖τ(a)‖_∞。

对于正整数h, 私钥的随机分布χ_key为HWT(h)。噪声的随机分布χ_err为DG(σ²), 其中σ²表示Z^N上的方差。加密密钥的随机分布χ_enc为ZO(ρ)。

a(X)为经过随机采样得到的多项式, a(ζ)为系数向量a的内积, 向量(1, ζ, …, ζ^N-1)的欧拉范数为, 对于a中的每一个系数, 其方差为σ², 随机变量a(ζ)的方差为V_err=σ², 当a随机采样自U(R_q)时, a(ζ)的方差为V_enc=N/2, 当a随机采样自χ_enc时, a(ζ)的方差为V_q=q²N/12, 当a随机采样自χ_key时, a(ζ)的方差为V_key=h。在复平面上看, 因a(ζ)为多个独立同分布随机变量的集合, 可以将其看作高斯随机变量。对于单位根ζ^j的任意计算都有相同的方差, 因此当a中的每一个系数的方差为V时, 可以用作为a的规范嵌入范数的高置信上界。对于2个服从高斯分布的独立随机变量, 其方差分别为V₁和V₂, 则这2个变量的乘积的高置信上界为。

对于基于余数系统的近似同态加密方案, 其加密阶段并没有使用到近似模交换算法, 故而加密过程的噪声上界与原始近似同态加密方案一样, 加密过程的噪声上界为。

同态加法操作也没用使用到近似模交换算法, 故而同态加法过程的噪声上界与原始近似同态加密方案一样, 对于处于同层的密文(c₁, l, v₁, B₁)和(c₂, l, v₂, B₂), 对应明文分别为m₁和m₂, 有同态加法运算c_add=Add(c₁, c₂), 则同态加法后的密文形式为(c_add, l, v₁+v₂, B₁+B₂)。

对于重缩放操作, c_t=(c_t^(j)=(c₀^(j), c₁^(j)))_0≤j≤l∈为第l层的待重缩放密文, c′_t=(c′_t^(j)=(c′₀^(j), c′₁^(j)))_0≤j≤l-1=RS(c_t)为重缩放过程的输出结果, 其中c′_i^(j)=q_l^-1·(c_i^(j)-c_i^(l)), i=0, 1, 0≤j≤l-1。多项式c_i∈R_QL满足[c_i]_Cl=(c_i⁽⁰⁾, …, c_i^(l)), 那么可以计算c′_i=q_l^-1·(c_i-[c_i]_ql)=, 则[c_i]_Cl-1=(c′_i⁽⁰⁾, …, c′_i^(l-1))。因此可以得到[〈c′_t, s_k〉]_Ql-1=q_l^-1·[〈c_t, s_k〉]_Ql+e_RS, 其中e_RS满足‖e‖_∞^can≤B_RS=。

对于同态乘法运算, 2个同层的密文c_t和c′_t, 记层数为l。同态乘法计算先得到的结果为(d₀, d₁, d₂)∈R_Ql³, 满足d₀+d₁·s+d₂·s²≡〈c_t, s_k〉。接着计算=d₂+Q_l·e, 满足‖‖_∞=(1/2)·(l+1)·Q_l。可以假设整数多项式为R_Ql上的l+1个独立的均匀分布随机变量的和, 则的方差为V=(1/2)·(l+1)·(Q_l²·(N/12))。因此, 同态计算密钥evk的前k+l+1个组成元素可以看作是在模数为P·Q_l下对P·s²的加密。最终的输出结果为P··s²≡P·d₂·s²(mod P·Q_l), 因此密文噪声上界为=。通过模约减算法进行模约减后, 返回, 满足。对于误差, 可以将其看作是R_P上的k个独立均匀分布随机变量的和, 所以其方差为k·V_P=k·P²·(N/12)。最后, 通过除以P, 得到模约减噪声k·P·(N/12)。所以, 结果为一个噪声上界为对d₂·s²的的加密结果。

4.2 安全性分析

CKKS一系列加密方案都是基于错误学习问题(LWE问题)设计的同态加密方案, 即其安全性可以归约到LWE困难问题。下面先给出同态加密方案的IND-CPA安全性定义和IND-CPA^D安全性定义, 在此基础上对本文方案的安全性进行分析。

对于公钥加密方案, 语义安全等同于选择明文攻击下的不可区分性(indistinguishability under chosen plaintext attacks, IND-CPA)安全。定义1通过安全性验证方式给出了IND-CPA安全的定义。在安全性验证试验中称同态加密方案拥有者为挑战者, 对同态加密方案进行攻击的行为方为攻击者E_ve。

定义1 IND-CPA安全

E=(K_eyGen, E_nc, D_ec, E_val)为一个同态加密方案。定义安全性验证试验过程expr_b^IND-CPA, 其中b可取0或1, 安全性验证试验过程如下

那么定义IND-CPA安全性验证试验的优势为Adv_IND-CPA=|Pr{expr₀^IND-CPA(1^κ)=1}-Pr{expr₁^IND-CPA (1^κ)=1}|, 则当且仅当Adv_IND-CPA的值关于κ可忽略时, 该同态加密方案为IND-CPA安全的。

同态加密方案因可以进行密文同态运算而不同于其他类型的加密方案。在安全性度量时这一特性也需要被考虑到。Li等[14]发现, 针对基于近似计算的同态加密方案CKKS17, 该方案即便是满足IND-CPA安全下, 仍然无法完全防御被动攻击。对此, Li等提出了带解密预言机的选择明文攻击下的不可区分性(indistinguishability under chosen plaintext attacks with decryption oracles, IND-CPA^D) 安全的概念。

定义2 IND-CPA^D安全

E=(K_eyGen, E_nc, D_ec, E_val)为一个明文空间为M, 密文空间为C的同态加密方案。定义安全性验证试验过程expr_b^IND-CPAD, 其中b可取0或1。用三元组(M×M×C)来表示状态, *代表可以不出现, 也可以出现一次或者多次。在该安全性验证试验中, 攻击者具有记录状态三元组S∈(M×M×C)^*的能力, |S|表示S中状态的个数, S[j]·m₀、S[j]·m₁和S[j]·m_c分别代表S中下标为j的相应元素。攻击者可以使用如下预言机:

加密预言机E_pk(m₀, m₁): 向加密预言机输入明文消息m₀和m₁, 计算c←E_ncpk(m_b), 将状态三元组(m₀, m₁, c)加入到S中, 并返回密文c给攻击者E_ve。

同态运算预言机H_ek(g, J): g为映射关系M^k→M, J为下标序列集合, J=(j₁, j₂, …, j_k)∈ 1, 2, …, |S|}^k。进行与映射关系g对应的同态运算得到密文c←E_valpk(g, S[j₁]·c, S[j₂]·c, …, S[j_k]·c), 并将三元组(g(S[j₁]·m₀, S[j₂]·m₀, …, S[j_k]·m₀), g(S[j₁]·m₁, S[j₂]·m₁, …, S[j_k]·m₁), c)加入到S中。返回密文c给攻击者E_ve。

解密预言机D_sk(j): 对于下标j≤|S|, 判断S[j]·m₀=S[j]·m₁的真伪, 若为真, 返回D_ecsk(S[j]·c)给攻击者E_ve, 若为假, 则返回错误信息给攻击者。

安全性验证试验过程如下

即定义IND-CPA^D安全性验证试验的优势为|Pr{expr₀^IND-CPAD(1^κ)=1}-Pr{expr₁^IND-CPAD(1^κ)=1}|, 则当且仅当Adv_IND-CPA^D的值可以忽略时, 该同态加密方案为IND-CPA^D安全的。

可以观察到, 本文方案的加密过程为: 随机采样得到s←HWT(h)、a←R_qL和e←DG(σ²), 计算b=-as+e(modq_L), 公钥p_k=(b, a), 随机采样得到v←ZO(0.5)以及e₀, e₁←DG(σ²), 对于明文m, 加密后的密文为c=v·pk+(m+e₀, e₁) (modq_L)。加密过程就是LWE问题中向量的构造过程, 因为LWE问题是困难的, 所以方案的安全性受到了保障。

由定义1可知, 对于(s_k, p_k, e_k)←K_eyGen(1^λ), 攻击者E_ve可以获得已经公布的公钥和计算密钥以及安全参数, 那么攻击者可以选定(x₀, x₁)←E_ve(1^κ, p_k, e_k)。对于b∈{0, 1}, 明文x_b经过加密后的结果为c_t, 由判定LWE问题是困难问题可知, 攻击者无法以明显的优势进行判定, 即对于b′←E_ve(c_t), Adv_IND-CPA=|Pr{expr₀^IND-CPA(1^λ)=1}-Pr{expr₁^IND-CPA(1^λ)=1}|=0, 该方案是满足IND-CPA安全的。

但是对于IND-CPA^D安全的安全, 选择加密明文为0, 并且加密后不执行同态运算而是直接解密, 多次重复该操作, 就可以得到关于私钥s_k的线性方程组, 通过高斯消元法即可结束s_k。上述过程即为对近似计算同态加密的被动恢复密钥攻击。所以CKKS17方案无法满足IND-CPA^D安全。对此本文方案在解密过程中先进行随机采样得到e₂←DG(σ²), 对于密文c=(b, a), 解密形式变换为m=b+a·s+e₂(mod q_l), 而非CKKS17方案中的m=b+a·s(mod q_l)。由于近似计算特性, 解密结果中增加噪声不会影响方案正确性, 同时增加噪声后, 解密后的明文符合LWE问题形式, 无法通过高斯消元法直接获得加密方案的私钥, 所以本文方案可以成功防御针对近似计算同态加密方案的被动恢复密钥攻击。根据定义2可知, 该方案满足IND-CPA^D安全要求。

本文方案仅是对自举过程进行优化改进, 自举过程可以看作是同态加法运算和同态乘法运算的组合, 对自举运算的优化并不影响方案的安全性。

5 实验结果和分析

本文实验是基于余数系统的HEAAN库[6]实现的, 运行设备CPU型号为Intel(R) Core(TM) i9-9900K CPU @ 3.60 GHz, 64 GB运行内存, 操作系统为Ubuntu 18.04.4 LTS。

表 1给出了参数集选择, 其中“-”代表了该方案未使用到该参数。表中参数均遵循CKKS推荐参数[15]选择, 可以有效防止格攻击。其中参数log₂N表示一个CKKS密文能打包N/2个明文; log₂p和log₂q表示自举过程模约减过程使用的参数; log₂Q表示模升操作后密文的模大小; r是CHK+18a使用的倍角公式; n表示比较函数中多项式函数f(x)和g(x)的次数, d_f和d_g分别表示多项式函数f(x)和g(x)的迭代次数。

CKKS密文支持SIMD, 一个密文打包了N/2个明文数据, 因此, 本文的对比实验中主要采取了耗时和平均耗时2个对比标准来进行自举方案对比, 耗时表示的是对N/2个明文数据进行自举计算所需的整体时间, 而平均耗时表示对每一个明文数据进行自举计算所需的时间。下面将本文提出的优化方案与CHK+18a方案[5]、HEAAN库[6]以及方案[16]进行对比。参数集Ⅰ~Ⅳ为CHK+18a方案中设定的参数, HEAAN库同样按照CHK+18a方案中的参数选择进行设定, 参数集Ⅴ~Ⅷ为应用小间隔差值拟合算法[16]计算时所需参数, 本文基于余数系统的小间隔差值拟合算法所使用的参数集是Ⅸ~Ⅻ。

CHK+18a、HEAAN、文献[16]方案和本文方案的自举耗时对比记录在表 2, 其中Q₁表示自举后密文模的大小; l_left表示自举后还剩下的乘法次数; 图 1展示了HEAAN库, 文献[16]方案和余数系统下的小间隔差值拟合方案自举实验。

Ⅰ, Ⅴ和Ⅸ这3组参数集有着相同的精度设置和基本相同的模大小, 在这3组参数集下, 本文提出的余数系统下小间隔差值拟合自举方案运行耗时仅为1 743 ms, 平均到每一槽计算时间仅需0.027 ms, 是CHK18+a的1/20, 约为HEAAN 2.1版本和文献[16]方案的1/5;在更大的参数设置下, 即参数集Ⅳ, Ⅷ和Ⅻ, 本文提出的余数系统下的小间隔差值拟合自举方案的运行耗时和平均耗时是CHK+18a方案的1/37, 约为HEAAN 2.1版本的1/6, 约为文献[16]方案运行耗时的1/6。在各组参数集对比下, 本文自举方案比其他3个方案耗时少, 并且在更大的参数集设置下, 本文方案优势更加明显。

结合图 1中的曲线变化, 当自举精度从12比特上升到16比特时, HEEAN1.2和文献[16]方案的耗时有大幅度上升, 而基于余数系统的小间隔差值拟合自举方法运行时间虽有上升, 但上升比例不大。分析其原因, 当计算精度提升时, 选取的模数变大, 密文位数也随着变多, 导致运算量增大, 计算耗时上升。余数系统能将大整数拆分为多个小整数进行运算, 这样就避免了大整数乘法因位数上升而导致的运算效率下降这一问题。从实验数据中也可以得到相同的结论, HEEAN1.2和文献[16]方案在精度上升时, 运算耗时有显著的上升, 但通过本文方案将大数转化为多个小整数后, 精度上升时的运算耗时上升不明显。因此, 本文方案能够在合理的耗时下满足高精度的自举计算需求。

图1 平均耗时对比

6 结论

针对基于小间隔插值拟合的近似同态加密自举方法, 本文继续探索优化, 将其余数系统相结合, 提出了一种基于余数系统的小间隔插值拟合自举方法。余数系统可以提高密码方案中模乘运算和模逆运算的计算速度, 但应用在近似计算同态加密方案中会遇到模基选择问题。本文根据近似计算同态加密方案的特性选择了更适合的高效模乘运算和模逆运算的实现算法。最终在16比特精度, N=2¹⁶时, 平均到每一槽的分时计算时间仅需0.027 ms, 相较于原始方案计算效率有显著提升。

在研究过程中发现, 当设定较大N值时, 近似计算同态加密方案所产生的密钥尺寸和密文尺寸较大, 对内存的占用极为明显。这就导致了实验过程中对实验设备硬件要求较高, 影响了方案的实用性, 对此可以进一步探讨近似同态加密过程中的密文压缩技术, 通过压缩手段来降低密文尺寸, 进而提高方案的实用性。

References

All Tables

All Figures

	图1 平均耗时对比
In the text