同态加密算法BGV的优化
基础知识
单位根与分圆多项式
有一个域\(F\),元素\(\omega \in F\)如果满足\(\omega^m \equiv 1\),那么w是m次单位根，如果找不到一个比\(m\)更小的数\(m’\)，使得\(\omega^{m'} \equiv 1\)是F中最小次数的根，那么\(\omega\)称为m次单位原根。
如果\(\omega\)是m次原单位根，那么有如下两条性质
- 性质1：对于唯一的一个\(j \in \mathbb{Z}_m\)每一个m次单位根都能被写为\(\omega^j\)，这是因为\(\omega^{jm} \equiv 1\)，所以也是m次单位根。
- 性质2：对于唯一的一个\(j \in \mathbb{Z}^*_m\)，每一个m次单位原根都能被写为\(\omega^j\)。这是因为\(\omega^j\)是m次单位根，其次找不到比m还小的值使得\(\omega^{jm} \equiv 1\)成立（假设d|m，那么\(\omega^{d} \neq 1\)从而\(\omega^{jd} \neq 1\)，因为j和d互素，jd必不可能是m的倍数）。
假设\(\omega = e^{2\pi i/m}\)是复数域的m次根，定义分圆多项式： \[ \Phi_m(X):=\prod\limits_{j\in\mathbb{Z}_m^*}(X-\omega^j)\in\mathbb{C}[X]. \] 有如下性质:
- 分圆多项式有多项式次数\(\phi(m)\)，j的个数是与m互素的个数
- \(\Phi_m(X)\in\mathbb{Z}[X]\)
- 分圆多项式在有理数域上不可约
- \(X^m-1=\prod\limits_{d|m}\Phi_d(X)\)以及他的变式\(\Phi_m(X)=\dfrac{X^m-1}{\prod\limits_{d\mid m}\Phi_d(X)}\)。显然，如果m是个素数p，那么\(\Phi_{p}(x)=\frac{x^{p}-1}{x-1}=\sum^{p-1}_{i=0}{x^i}\)
规范嵌入和无穷范数
基本思想：定义\(\mathcal{A}:=\mathbb{Z}[X]/(\Phi_m(X))\)，\(\omega\)是一个m次单位原根，有一个多项式\(a=[f(X)\text{mod}\Phi_m(X)]\in\mathcal{A}\)，我们可以清晰的定义\(\boldsymbol{a}(\omega^j):=f(\omega^j)\)，而不用在乎\(f(X)\)的具体取值(因为模了一个分圆多项式)。
- 规范嵌入：多项式\(a\in\mathcal{A}\)的规范嵌入是一个向量
\[ \operatorname{cannon}(\boldsymbol a):=\Big(\boldsymbol a(\omega^j)\Big)_{j\in\mathbb Z_m^*}. \]
- 无穷范数：使用常见的无穷范数作为多项式\(a \in \mathcal{A}\)的大小（size），取规范嵌入后向量元素的最大值即可
\[ \quad\|\boldsymbol a\|:=\|\mathrm{cannon}(\boldsymbol a)\|_\infty = \max\{|\boldsymbol a(\omega^j)|:j\in\mathbb Z^*_m\}, \]
编码——拉格朗日插值
目前的困境：BGV的明文为一个\(N-1\)次多项式m(x)，我们如何把\(N\)个数值\((a_0,a_1,\dots,a_{N-1})\)编码进一个明文多项式\(m_1(x)\)，另外N个数值\((b_0,b_1,\dots,b_{N-1})\)编码进多项式\(m_2(x)\)。使得当明文多项式做多项式乘法后\(m(x) = m_1(x)*m_2(x)\)，解码\(m(x)\)得到的是对应数值的点乘形式\((a_0*b_0,a_1*b_1,\dots,a_{N-1}*b_{N-1})\)
先介绍一下拉格朗日插值：
假设我们有一些已知点 \((x_i, y_i)\)，我们想要找到一个函数 \(f(x)\)，它在这些点上与 \(y_i\) 相等，同时在这些点之间光滑连续。拉格朗日插值的想法是使用一个多项式来近似这个函数，多项式的系数可以通过在这些点上求解一系列的线性方程来获得。
下面是一个使用拉格朗日插值计算多项式的示例。假设我们有三个点 \((0, 1)\)，\((1, 2)\) 和 \((2, 3)\)。我们可以使用一个二次多项式来近似这些点，形式为 \(f(x) = a + bx + cx^2\)。我们可以通过求解以下三个方程来确定多项式的系数： \[ \begin{matrix}f(0)=a+0b+0c=1\\ f(1)=a+1b+1c=2\\ f(2)=a+2b+4c=3\end{matrix} \]
通过求解这些方程，我们可以得到多项式的系数 \(a = 1\)，\(b = 1\) 和 \(c = -\frac{1}{2}\)。因此，我们的多项式为 \(f(x) = 1 + x - \frac{1}{2}x^2\)。
现在，我们可以将上述思想扩展到任意数量的点。具体来说，我们要使用一个 \(n-1\) 次多项式来拟合 \(n\) 个已知点。设 \((x_i, y_i)\) 是这些已知点中的第 \(i\) 个点，我们的多项式可以写成以下形式： \[ f(x)=\sum_{i=1}^ny_iL_i(x)\quad\text{} \]
其中 \(L_i(x)\) 是拉格朗日基函数，定义为： \[ L_i(x)=\prod_{j=1,j\neq i}^n\frac{x-x_j}{x_i-x_j} \]
这个基函数的作用是将多项式 \(f(x)\) 在 \(x_i\) 处变为 \(y_i\)，同时在其他点处为零。因此，我们可以将多项式表示为所有基函数的线性组合。
解决方案：
假设多项式是在模\(q\)意义下进行的，我们预计算出一个\(N\)次原根\(\omega\)满足\(\omega^N \equiv 1 \mod{q}\)，我们选取N个点 \[ (\omega^0,a_0),(\omega^1,a_1),\dots,(\omega^{N-1},a_{N-1}) \] 使用拉格朗日插值确定一个多项式\(m_1(x)\)，同理对另外N个点 \[ (\omega^0,b_0),(\omega^1,b_1),\dots,(\omega^{N-1},b_{N-1}) \] 确定另一个多项式\(m_2(x)\)，这样多项式乘法\(m(x) = m_1(x)*m_2(x)\)后，代入N个横坐标值\((\omega^0,\dots,\omega^{N-1})\)之后得到的纵坐标即为对应位数的点乘\((a_0*b_0,a_1*b_1,\dots,a_{N-1}*b_{N-1})\)
注意：
- 为什么要选取\(N\)次原根\(\omega\) ?因为有良好的性质，即\((\omega^0,\dots,\omega^{N-1})\)在模q意义下每个数都各不相同（如果相同那么\(\omega\)不是\(N\)次原根）
- 如何找\(N\)次原根\(\omega\) ?首先找到一个模q的原根g，然后使用快速幂运算去计算\(g^{(q-1)/N}\)即可得到\(\omega\)