基于小步大步法（BSGS）的同态加密多项式求值
摘要
本文介绍如何使用小步大步（Baby-Step-Giant-Step，BSGS）加速同态加密的多项式求值，尽量减少密文和密文乘法的次数。
公式
假设我们需要求多项式 p ( x ) = a 0 + a 1 x + a 2 x 2 + ⋯ + a n x n p(x)=a_0+a_1x+a_2x^2+\cdots+a_nx^n p(x)=a0+a1x+a2x2+⋯+anxn 在某一点 x x x 的值。
如果直接计算，需要计算
x
1
,
x
2
,
⋯
,
x
n
x^1,x^2,\cdots,x^n
x1,x2,⋯,xn，需要
n
n
n次密文乘法。
即使使用Horner法则计算：
p
(
x
)
=
(
⋯
(
(
a
n
x
+
a
n
−
1
)
x
+
a
n
−
2
)
x
+
⋯
)
x
+
a
0
p(x)=(\cdots((a_nx+a_{n-1})x+a_{n-2})x+\cdots)x+a_0
p(x)=(⋯((anx+an−1)x+an−2)x+⋯)x+a0
也需要
n
n
n次的密文乘法。
在同态加密中， a i a_i ai与密文 x x x的代价是远远小于两个密文相乘的。
令
k
1
=
k
2
,
k
1
k
2
=
n
+
1
k_1=k_2,k_1k_2=n+1
k1=k2,k1k2=n+1，那么可以将
p
(
x
)
p(x)
p(x)重新写为：
p
(
x
)
=
∑
j
=
0
k
2
−
1
(
∑
i
=
0
k
1
−
1
a
i
+
j
k
1
x
i
)
x
j
k
1
p(x)=\sum_{j=0}^{k_2-1}(\sum_{i=0}^{k_1-1}a_{i+jk_1}x^i)x^{jk_1}
p(x)=∑j=0k2−1(∑i=0k1−1ai+jk1xi)xjk1.
因此，我们需要计算 x 1 , x 2 , ⋯ , x k 1 − 1 x^1,x^2,\cdots,x^{k_1-1} x1,x2,⋯,xk1−1和 x k 1 , x 2 k 1 , ⋯ , x ( k 2 − 1 ) k 1 x^{k_1},x^{2k_1},\cdots,x^{(k_2-1)k_1} xk1,x2k1,⋯,x(k2−1)k1.
令 k 1 = k 2 k_1=k_2 k1=k2，那么需要计算 2 n + 1 2\sqrt{n+1} 2n+1。
然后根据公式计算，在每一次外部的乘法都会需要一次密文乘以密文，因此一共需要 3 n + 1 3\sqrt{n+1} 3n+1次密文乘法。
然后，我们还可以继续利用Horner法则进行优化：
p
(
x
)
=
(
⋯
(
(
a
(
k
2
−
1
)
k
1
x
k
1
−
1
+
a
(
k
2
−
1
)
k
1
−
1
x
k
1
−
2
+
⋯
+
a
(
k
2
−
1
)
k
1
−
k
1
)
x
k
1
+
a
(
k
2
−
2
)
k
1
−
1
x
k
1
−
1
+
⋯
+
a
(
k
2
−
2
)
k
1
−
k
1
)
x
k
1
+
⋯
)
x
k
1
+
a
k
1
−
1
x
k
1
−
1
+
⋯
+
a
0
p(x)=(\cdots((a_{(k_2-1)k_1}x^{k_1-1}+a_{(k_2-1)k_1-1}x^{k_1-2}+\cdots+a_{(k_2-1)k_1-k_1})x^{k_1}+a_{(k_2-2)k_1-1}x^{k_1-1}+\cdots+a_{(k_2-2)k_1-k_1})x^{k_1}+\cdots)x^{k_1}+a_{k_1-1}x^{k_1-1}+\cdots+a_0
p(x)=(⋯((a(k2−1)k1xk1−1+a(k2−1)k1−1xk1−2+⋯+a(k2−1)k1−k1)xk1+a(k2−2)k1−1xk1−1+⋯+a(k2−2)k1−k1)xk1+⋯)xk1+ak1−1xk1−1+⋯+a0.
这样就避免 x 2 k 1 , ⋯ , x ( k 2 − 1 ) k 1 x^{2k_1},\cdots,x^{(k_2-1)k_1} x2k1,⋯,x(k2−1)k1.的额外计算。
参考文献
[1] Paterson, Michael S., and Larry J. Stockmeyer. “On the number of nonscalar multiplications necessary to evaluate polynomials.” SIAM Journal on Computing 2.1 (1973): 60-66.