FHE之NTT（）NWC NTT与PWC NTT

PWC NTT与NWC NTT

NTT在不同多项式环的不同版本

常规有限域上的多项式相乘

Ring：$Z_q [x]$

对于多项式 $\mathbf a∈Z_q [x],\mathbf b∈Z_q [x], \mathbf a=[a_0,a_1, ⋯,a_{(n-1)} ],\mathbf b=[b_0,b_1, ⋯,b_{(n-1)} ]$

若 $\mathbf c∈Z_q [x], \mathbf c=\mathbf a∙\mathbf b$, 那么

$$\operatorname{INTT}_{2 N}\left(\operatorname{NTT}_{2 N}(\text { zeropadding }(\boldsymbol{a})) \odot \operatorname{NTT}_{2 N}(\text { zeropadding }(\boldsymbol{b}))\right) \tag{1}$$

多项式环一：Positive Wrapped Convolution

Ring：$\frac{Z_q [x]}{x^n-1}$

对于多项式 $\mathbf{a}∈(Z_q [x])⁄((x^n-1)),\mathbf{b}∈(Z_q [x])⁄((x^n-1)), \mathbf{a}=[a_0,a_1, ⋯,a_{(n-1)} ],\mathbf{b}=[b_0,b_1, ⋯,b_{(n-1)} ]$

若 $\mathbf c∈\frac{Z_q [x]}{x^n-1}$, $\mathbf c=\mathbf a∙\mathbf b$, 那么

$$\boldsymbol{c}=\operatorname{INTT}_{N}\left(\operatorname{NTT}_{N}(\boldsymbol{a}) \odot \operatorname{NTT}_{N}(\boldsymbol{b})\right) \tag{2}$$

多项式环二：Negative Wrapped Convolution

Ring：$\frac{Z_q [x]}{x^n+1}$

对于多项式 $\mathbf a∈(Z_q [x])⁄((x^n+1)),\mathbf b∈(Z_q [x])⁄((x^n+1)), \mathbf a=[a_0,a_1, ⋯,a_(n-1) ],\mathbf b=[b_0,b_1, ⋯,b_(n-1) ]$

若 $\mathbf c∈\frac{Z_q [x]}{x^n+1}$, $\mathbf c=\mathbf a∙\mathbf b$, 那么令 $\gamma_{2N}=\omega_{N}^{\frac{1}{2}}=g^{\frac{q-1}{2N}}$

$$\overline{\boldsymbol{c}}=\operatorname{INTT}\left(\operatorname{NTT}(\overline{\boldsymbol{a}}) \odot \operatorname{NTT}_{N}(\overline{\boldsymbol{b}})\right) 。 \tag{3}$$

$$\overline{\mathbf a}=[γ_{2N}^0,γ_{2N}^1,⋯,γ_{2N}^{N-1}]⊙\mathbf a,\\\overline{\mathbf b}=[γ_{2N}^0,γ_{2N}^1,⋯,γ_{2N}^{N-1}]⊙\mathbf b\\\overline{\mathbf c}=[γ_{2N}^0,γ_{2N}^1,⋯,γ_{2N}^{N-1}]⊙\mathbf c$$

分析

传统NTT计算多项式，多项式取自$Z_q[x]$，可以表示为：

$$\operatorname{INTT}_{2 N}\left(\operatorname{NTT}_{2 N}(\text { zeropadding }(\boldsymbol{a})) \odot \operatorname{NTT}_{2 N}(\text { zeropadding }(\boldsymbol{b}))\right) \tag{1}$$

其中符号 $\odot$ 表示逐点乘法，函数 $zeropadding (\boldsymbol{a})$ 将向量$\boldsymbol{a}$的长度从$N$扩展到$2 N$，末尾用零填充。可以看到，这种方式需要执行$2N$的NTT，十分浪费资源。

我们其实可以让多项式取自$\mathbb{Z}_{q}[x] /(x^N-1)$，当$N$大于多项式的最高次数时，约化多项式$x^N-1$这一步并不需要进行。但此时我们可以使用正向循环卷积(Positive Wrapped Convolution,PWC)高效地执行 $\mathbb{Z}_{q}[x] /(x^N-1)$ 上的乘法，这只需要3个$N$点的NTT/INTT，而不需要像$(1)$那样将NTT/INTT的大小加倍。

$$\boldsymbol{c}=\operatorname{INTT}_{N}\left(\operatorname{NTT}_{N}(\boldsymbol{a}) \odot \operatorname{NTT}_{N}(\boldsymbol{b})\right) \tag{2}$$

当 $g(x)$ 从 $x^{N}-1$ 更改为另一种特定形式 $x^{N}+1$ 时，可以使用负向循环卷积(Negative Wrapped Convolution, NWC)在 $\mathbb{Z}_{q}[x] /\left\langle x^{N}+1\right\rangle$ 上执行乘法，仍然只需要三个 $N$ 点的NTT/INTT，而无且需像 $\mathbb{Z}_{q}[x] /\left\langle x^{N}-1\right\rangle$ 上的乘法那样显式约化。

注：NWC“无需显式约化”的性质可能与“分圆多项式”有关，这点我暂未研究。

NWC方法要求质数 $q$ 满足 $q \equiv 1(\bmod 2 N)$，从而 $\omega_{N}$ 及其平方根 $\gamma_{2 N}$存在。然而，此方法额外引入了一步旋转，需要在NTT之前预处理，在INTT之后附加后处理，如下所述。令 $\bar{a}_{i}=a_{i} \gamma_{2 N}^{i}$，$\bar{b}_{i}=b_{i} \gamma_{2 N}^{i}$，$\bar{c}_{i}=c_{i} \gamma_{2 N}^{i}$。为了在 $\mathbb{Z}_{q}[x] /\left\langle x^{N}+1\right\rangle$ 上计算 $\boldsymbol{c}=\boldsymbol{a} \cdot \boldsymbol{b}$，进行NWC如下：

$$\overline{\boldsymbol{c}}=\operatorname{INTT}\left(\operatorname{NTT}(\overline{\boldsymbol{a}}) \odot \operatorname{NTT}_{N}(\overline{\boldsymbol{b}})\right) 。 \tag{3}$$

通过这种方式，在缩放向量 $\overline{\boldsymbol{a}}$ 和 $\overline{\boldsymbol{b}}$ 上执行经典的 $N$ 点的NTT，经典的 $N$点的INTT后，得到缩放向量$\bar{c}$，通过计算 $c_{i}=\bar{c}_{i} \gamma_{2 N}^{-i}$ 可以得到最终结果 $c$。因此，NWC方法避免了将NTT/INTT的大小加倍和显式约化，但它要求在NTT之前将系数缩放为 $\gamma_{2 N}^{i}$，在INTT之后将结果缩放为 $\gamma_{2 N}^{-i}$。

比较

我们以$N=8$为例，看看各个版本的NTT的参数有哪些规律

PWC NTT(DIF)

PWC INTT(DIT)

NWC NTT(DIT)

NWC INTT(DIF)

注意

同为NTT，PWC一般采用DIF，NWC一般采用DIT；同为INTT，PWC一般采用DIT，NWC一般采用DIF。

实际上我认为PWC采用DIT还是DIF无所谓，而NWC则必须按以上方法采样，这主要是由于$\gamma$的限制：

• NWC NTT需要对输入预处理：$\bar{a}_{i}=a_{i} \gamma_{2 N}^{i}$，$\bar{b}_{i}=b_{i} \gamma_{2 N}^{i}$，因此只能采用DIT。
• NWC INTT则需要对输出后处理：$\bar{c}_{i}=c_{i} \gamma_{2 N}^{i}$，因此只能采用DIF。

归纳

at the $i$-th stage for $N$-point NTT	PWC NTT(DIF)	NWC NTT(DIT)	PWC INTT(DIT)	NWC INTT(DIF)
num_stages (number of stages)	$logN$	$logN$	$logN$	$logN$
bf_pairs (number of pairs in a group)	$2^{logN-1}$	$2^{logN-1}$	$2^i$	$2^i$
bf_groups (number of groups at a stage)	$2^i$	$2^i$	$2^{logN-1}$	$2^{logN-1}$
the power of $\omega$	同一group内以$2^i$沿pair递增 不同group对应位置相同	同一group内相同 同一stage内第$j$个group的power为$\frac{N}{2}$中$j$的位逆序	同group内以$2^i$沿pair递增 不同group对应位置相同	同一group内相同 同一stage内第$j$个group的power为$\frac{N}{2}$中$j$的位逆序
the power of $\gamma$	~	~	$2^i$	$2^i$
index_stride (the index stride within the pair)	bf_pairs	bf_pairs	bf_pairs	bf_pairs