摘要
本文介绍如何使用小步大步（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.