自学内容网 自学内容网

近似的同态比较:简单多项式的迭代计算

参考文献:

  1. [Gold64] Goldschmidt R E. Applications of division by convergence[D]. Massachusetts Institute of Technology, 1964.
  2. [CKKLL19] Cheon J H, Kim D, Kim D, et al. Numerical method for comparison on homomorphically encrypted numbers[C]//International Conference on the Theory and Application of Cryptology and Information Security. Cham: Springer International Publishing, 2019: 415-445.
  3. [CKK20] Cheon J H, Kim D, Kim D. Efficient homomorphic comparison methods with optimal complexity[C]//Advances in Cryptology–ASIACRYPT 2020: 26th International Conference on the Theory and Application of Cryptology and Information Security, Daejeon, South Korea, December 7–11, 2020, Proceedings, Part II 26. Springer International Publishing, 2020: 221-256.
  4. [LLNK21] Lee E, Lee J W, No J S, et al. Minimax approximation of sign function by composite polynomial for homomorphic comparison[J]. IEEE Transactions on Dependable and Secure Computing, 2021, 19(6): 3711-3727.
  5. [LLKN22] Lee E, Lee J W, Kim Y S, et al. Optimization of homomorphic comparison algorithm on rns-ckks scheme[J]. IEEE Access, 2022, 10: 26163-26176.


CKKS 方案只能计算多项式,但是符号函数是阶跃的,难以表示为简单多项式。如果采取完全的插值,随着精度提高,多项式的度数将会是指数级。[CKK20] 提出可以通过迭代一个或两个简单多项式,来快速逼近符号函数,它达到了渐进最优。[LLNK21] 使用若干个 minimax approximate polynomials 的组合来逼近符号函数,用动态规划算法确定它们,实际效率更好。[LLKN22] 继续改进,但提升并不算大。

New Comparison Algorithm

Idea

待计算的两个函数,关系为 c o m p ( a , b ) = ( s g n ( a − b ) + 1 ) / 2 comp(a,b)=(sgn(a-b)+1)/2 comp(a,b)=(sgn(ab)+1)/2
s g n ( x ) = { 1 , x > 0 0 , x = 0 − 1 , x < 0 c o m p ( a , b ) = { 1 , a > b 1 / 2 , a = b 0 , a < b \begin{aligned} sgn(x) &= \left\{\begin{aligned} 1, && x>0\\ 0, && x=0\\ -1, && x<0 \end{aligned}\right.\\ comp(a,b) &= \left\{\begin{aligned} 1, && a>b\\ 1/2, && a=b\\ 0, && a<b \end{aligned}\right.\\ \end{aligned} sgn(x)comp(a,b)= 1,0,1,x>0x=0x<0= 1,1/2,0,a>ba=ba<b
在 [CKKLL19] 中指出如下的公式,
c o m p ( a , b ) = lim ⁡ k → ∞ a k a k + b k comp(a,b) = \lim_{k \to \infty} \frac{a^k}{a^k + b^k} comp(a,b)=klimak+bkak
可以使用迭代算法,

  1. 初始化 a 0 = a , b 0 = b a_0=a,b_0=b a0=a,b0=b
  2. 迭代计算 a k + 1 ← a k 2 / ( a k 2 + b k 2 ) a_{k+1} \gets a_k^2/(a_k^2+b_k^2) ak+1ak2/(ak2+bk2) b k + 1 ← a k 2 / ( a k 2 + b k 2 ) b_{k+1} \gets a_k^2/(a_k^2+b_k^2) bk+1ak2/(ak2+bk2)
  3. 输出 a d = a 2 d / ( a 2 d + b 2 d ) ≈ c o m p ( a , b ) a_d=a^{2^d}/(a^{2^d}+b^{2^d}) \approx comp(a,b) ad=a2d/(a2d+b2d)comp(a,b)

然而这种方法需要计算同态除法,同态方案并不自然支持。[CKKLL19] 使用了 Goldschmidt’s division 算法,但效率很低。

[CKK20] 的目标是找到一个好的简单多项式,并且它的迭代过程中不需要计算除法。首先将 [CKKLL19] 的迭代函数修改为 f ( x ) = x 2 / ( x 2 + ( 1 − x 2 ) ) , x ∈ [ 0 , 1 ] f(x)=x^2/(x^2+(1-x^2)), x \in [0,1] f(x)=x2/(x2+(1x2)),x[0,1],容易验证

  1. 它穿过了 ( 0 , 0 ) , ( 0.5 , 0.5 ) , ( 1 , 1 ) (0,0), (0.5, 0.5), (1,1) (0,0),(0.5,0.5),(1,1) 三个点
  2. 它在区间 [ 0 , 0.5 ] [0,0.5] [0,0.5] 上是凸的,在区间 [ 0.5 , 1 ] [0.5,1] [0.5,1] 上是凹的
  3. 随着函数迭代 f ( d ) f^{(d)} f(d),它将逼近区间 [ 0 , 1 ] [0,1] [0,1] 上的阶跃函数

事实上,我们只需要找出类似形状的多项式(不需要多项式分式),依旧可以通过迭代过程逼近这个阶跃函数。迭代过程如图所示:

在这里插入图片描述

Core Properties

任意区间 [ c 1 , c 2 ] [c_1,c_2] [c1,c2] 总是可以缩放平移到 [ − 1 , 1 ] [-1,1] [1,1] 上,因此我们只考虑符号函数 s g n ( x ) , x ∈ [ − 1 , 1 ] sgn(x), x \in [-1,1] sgn(x),x[1,1]

现在,我们确定形状近似 f ( x ) = x 2 / ( x 2 + ( 1 − x 2 ) ) , x ∈ [ 0 , 1 ] f(x)=x^2/(x^2+(1-x^2)), x \in [0,1] f(x)=x2/(x2+(1x2)),x[0,1] 的,用于迭代计算 s g n ( x ) , x ∈ [ − 1 , 1 ] sgn(x), x \in [-1,1] sgn(x),x[1,1] 的多项式应当具备的性质:

  1. 它应当是奇函数,假设它的度数为 2 n + 1 2n+1 2n+1,记为 f n f_n fn
  2. 它应当穿过两个端点 f ( − 1 ) = − 1 , f ( 1 ) = 1 f(-1)=-1, f(1)=1 f(1)=1,f(1)=1,由于原点附近它是阶跃的,因此难以用多项式正确逼近,我们排除对区间 [ − ϵ , ϵ ] [-\epsilon,\epsilon] [ϵ,ϵ] 的逼近
  3. 它应当在区间 [ − 1 , 0 ] [-1,0] [1,0] 上是凸的,在区间 [ 0 , 1 ] [0,1] [0,1] 上是凹的,并且凹凸性越强烈越好,我们设置多项式导数在两个端点上最大化重根

使用数学语言描述,

在这里插入图片描述

事实上,对于固定的参数 n n n,多项式 f n f_n fn 和常数 c n c_n cn 都是固定的,
f n ( x ) = ∑ i = 0 n ( 2 i i ) ⋅ x ( 1 − x 2 ) i 4 i c n = 2 n + 1 4 n ⋅ ( 2 n n ) = Θ ( n ) \begin{aligned} f_n(x) &= \sum_{i=0}^n {2i \choose i} \cdot \frac{x(1-x^2)^i}{4^i}\\ c_n &= \frac{2n+1}{4^n} \cdot {2n \choose n} = \Theta(\sqrt n) \end{aligned} fn(x)cn=i=0n(i2i)4ix(1x2)i=4n2n+1(n2n)=Θ(n )
可以计算出某些多项式,

在这里插入图片描述

它们的形状如图所示:

在这里插入图片描述

我们称多项式 p ( x ) p(x) p(x) 在区间 [ − 1 , 1 ] [-1,1] [1,1] 上满足 ( α , ϵ ) (\alpha,\epsilon) (α,ϵ)-close to 函数 f ( x ) f(x) f(x),假如
∥ p ( x ) − f ( x ) ∥ ∞ ,    [ − 1 , − ϵ ] ∪ [ ϵ , 1 ] ≤ 2 − α \big\| p(x) -f(x) \big\|_{\infty,\,\, [-1,-\epsilon]\cup[\epsilon,1] } \le 2^{-\alpha} p(x)f(x) ,[1,ϵ][ϵ,1]2α
可以证明上述多项式 f n f_n fn 的迭代收敛性质:

在这里插入图片描述

NewComp

根据等式 c o m p ( a , b ) = ( s g n ( a − b ) + 1 ) / 2 comp(a,b)=(sgn(a-b)+1)/2 comp(a,b)=(sgn(ab)+1)/2 和近似式 f n ( d ) ≈ s g n ( n ) f_n^{(d)} \approx sgn(n) fn(d)sgn(n),可以给出如下的近似比较算法,

在这里插入图片描述

实数多项式 f n f_n fn 可以转化为整系数多项式,
h n ( x ) = f n ( 2 x − 1 ) + 1 2 = ∑ i = 0 n ( 2 i i ) ⋅ ( 2 x − 1 ) ( x − x 2 ) i h_n(x) = \frac{f_n(2x-1)+1}{2} = \sum_{i=0}^n {2i \choose i} \cdot (2x-1)(x-x^2)^i hn(x)=2fn(2x1)+1=i=0n(i2i)(2x1)(xx2)i
并且它满足迭代公式 h n ( d ) ( x ) = ( f n ( d ) ( 2 x − 1 ) + 1 ) / 2 h_n^{(d)}(x) = (f_n^{(d)}(2x-1)+1)/2 hn(d)(x)=(fn(d)(2x1)+1)/2,于是 c o m p ( a , b ) ≈ g n ( d ) ( ( a − b + 1 ) / 2 ) comp(a,b) \approx g_n^{(d)}((a-b+1)/2) comp(a,b)gn(d)((ab+1)/2)

采取 Paterson-Stockmeyer 算法,每轮迭代中计算 f n ( x ) f_n(x) fn(x) 需要 C n : = Θ ( n ) C_n:=\Theta(\sqrt n) Cn:=Θ(n ) 次同态乘法, D n : = log ⁡ n + O ( 1 ) D_n:=\log n + O(1) Dn:=logn+O(1) 乘法深度。迭代次数的下界为
d n : = 1 log ⁡ c n log ⁡ ( 1 / ϵ ) + 1 log ⁡ ( n + 1 ) log ⁡ ( α − 1 ) + O ( 1 ) d_n := \frac{1}{\log c_n}\log(1/\epsilon) + \frac{1}{\log(n+1)}\log(\alpha-1) + O(1) dn:=logcn1log(1/ϵ)+log(n+1)1log(α1)+O(1)
我们简记复杂度类 L ( a , b ) : = a log ⁡ ( 1 / ϵ ) + b log ⁡ ( α − 1 ) + O ( 1 ) L(a,b) := a\log(1/\epsilon) + b\log(\alpha-1) + O(1) L(a,b):=alog(1/ϵ)+blog(α1)+O(1),那么 total computation 和 total depth 分别为:
T C n = d n ⋅ C n = L ( Θ ( n ) log ⁡ c n , Θ ( n ) log ⁡ ( n + 1 ) ) T D n = d n ⋅ D n = L ( log ⁡ n + O ( 1 ) log ⁡ c n , log ⁡ n + O ( 1 ) log ⁡ ( n + 1 ) ) \begin{aligned} TC_n &= d_n \cdot C_n = L\left( \frac{\Theta(\sqrt n)}{\log c_n}, \frac{\Theta(\sqrt n)}{\log(n+1)} \right)\\ TD_n &= d_n \cdot D_n = L\left( \frac{\log n + O(1)}{\log c_n}, \frac{\log n + O(1)}{\log(n+1)} \right)\\ \end{aligned} TCnTDn=dnCn=L(logcnΘ(n ),log(n+1)Θ(n ))=dnDn=L(logcnlogn+O(1),log(n+1)logn+O(1))
由于 c n = Θ ( n ) c_n = \Theta(\sqrt n) cn=Θ(n ),因此前者发散到无穷大,后者会接近 L ( 2 , 1 ) L(2,1) L(2,1)(但并不收敛)。计算表明 n = 4 n=4 n=4 的时候 T C 4 TC_4 TC4 是最优的,此时有 T C 4 = Θ ( 1 ) ⋅ log ⁡ ( 1 / ϵ ) + Θ ( 1 ) ) ⋅ log ⁡ ( α − 1 ) + O ( 1 ) TC_4 = \Theta(1)\cdot\log(1/\epsilon) + \Theta(1)) \cdot \log(\alpha-1) + O(1) TC4=Θ(1)log(1/ϵ)+Θ(1))log(α1)+O(1),假如 ϵ = 2 − α \epsilon=2^{-\alpha} ϵ=2α 那么就是 T C 4 = Θ ( α ) TC_4 = \Theta(\alpha) TC4=Θ(α),随近似精度的提升线性增长。

Acceleration

在迭代计算 f n ( d ) f_n^{(d)} fn(d) 的过程中,实际上分为两步。对于 x ≥ ϵ x \ge \epsilon xϵ

  1. 首先计算 f n ( d ϵ ) f_n^{(d_\epsilon)} fn(dϵ),将区间 [ ϵ , 1 ] [\epsilon,1] [ϵ,1] 映射到区间 [ 1 − τ , 1 ] [1-\tau,1] [1τ,1],其中 0 < τ < 1 0<\tau<1 0<τ<1 是某个常数
  2. 继续计算 f n ( d α ) f_n^{(d_\alpha)} fn(dα),将区间 [ 1 − τ , 1 ] [1-\tau,1] [1τ,1] 映射到区间 [ 1 − 2 − α , 1 ] [1-2^{-\alpha},1] [12α,1],它逼近 s g n ( x ) = 1 sgn(x)=1 sgn(x)=1

在第一阶段的迭代过程中,其实不需要 f n f_n fn 的全部性质。[CKK20] 提出可以用另一个斜率更大的函数 g g g 来代替,从而更少的迭代次数 d ϵ d_\epsilon dϵ 就可以达到区间。现在我们确定 g g g 应当具有的性质,

  1. 依旧应当是奇函数
  2. 存在常数 0 < δ < 1 0<\delta<1 0<δ<1,在区间 ( 0 , δ ] (0,\delta] (0,δ]严格递增
  3. 在区间 [ δ , 1 ] [\delta,1] [δ,1] 中总保持映射到区间 [ 1 − τ , 1 ] [1-\tau,1] [1τ,1]

使用数学语言描述,

在这里插入图片描述

对于固定的常数 τ \tau τ,为了使得 ( 0 , δ ] (0,\delta] (0,δ] 内的导数更大(从而迭代次数更少),我们确定多项式 g g g 使得最小化常数 δ 0 \delta_0 δ0,采用迭代算法寻找:

在这里插入图片描述

可以证明这个过程收敛到某个多项式 g n , τ g_{n,\tau} gn,τ,它是导数最大意义下最优的。

[CKK20] 固定 τ = 1 / 4 \tau=1/4 τ=1/4,虽然上述获得的 g n g_n gn 并没有关于 n n n 的简单表达式,但是以精度 2 − 10 2^{-10} 210 近似为

在这里插入图片描述

它们的形状和迭代,如图所示:

在这里插入图片描述

修改后的算法为

在这里插入图片描述

根据 g n g_n gn 的某些启发式性质,可以确定 g n ′ ( 0 ) g_n'(0) gn(0) 的大小和 g n ( x ) g_n(x) gn(x) 逼近 ± 1 \pm1 ±1 的速率(详见 [CKK20]),最后计算出各自的迭代次数 d ϵ d_\epsilon dϵ d α d_\alpha dα 的下界。虽然不同的输入值 x x x 需要的迭代次数也不同,但它是密文状态的,难以用它来动态地确定迭代次数。

在这里插入图片描述

通过和 NewComp 的复杂度做比较,算法 NewCompG 在第一阶段的迭代深度降低了基本一半,因此乘法深度 T D n TD_n TDn 和乘法复杂度 T C n TC_n TCn 都显著降低。

Application to Min/Max

最大值/最小值可以用绝对值来构造,
min ⁡ ( a , b ) = ( a + b ) − ∣ a − b ∣ 2 max ⁡ ( a , b ) = ( a + b ) + ∣ a − b ∣ 2 \begin{aligned} \min(a,b) &= \frac{(a+b) - |a-b|}{2}\\ \max(a,b) &= \frac{(a+b) + |a-b|}{2}\\ \end{aligned} min(a,b)max(a,b)=2(a+b)ab=2(a+b)+ab
而绝对值可以用符号函数来构造,
∣ x ∣ = x ⋅ s g n ( x ) ≈ x ⋅ ( f n ( d α ) ∘ g n ( d ϵ ) ) ( x ) |x| = x \cdot sgn(x) \approx x \cdot (f_n^{(d_\alpha)}\circ g_n^{(d_\epsilon)})(x) x=xsgn(x)x(fn(dα)gn(dϵ))(x)

对应的收敛性:

在这里插入图片描述

Result

[CKK20] 选用了 HEAAN 同态加密库,设置参数 N = 2 17 N=2^{17} N=217 q L ≈ 2 2250 q_L \approx 2^{2250} qL22250。由于 CKKS 是 Level FHE,不同层的复杂度不一样,因此它使用 T D n ⋅ T C n TD_n \cdot TC_n TDnTCn 作为计算复杂度的描述。在设置 ϵ = 2 − α \epsilon = 2^{-\alpha} ϵ=2α 时,依旧是 n = 4 n=4 n=4 最优化,因此选用 f 4 , g 4 f_4,g_4 f4,g4

计算复杂度、乘法深度、性能测试:

在这里插入图片描述


原文地址:https://blog.csdn.net/weixin_44885334/article/details/135462535

免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!