与ntt在晶体中的实现相关

Question

最近，我开始实施基本骨架水晶凯伯。现在我被困在NTT，在那里我无法理解如何给值(旋转因子，必须转换成NTT形式的实际数据)，.I指的是来自python实现的ntthelper.py和高密度脂蛋白实现 .Here中的参数ntt，我无法弄清楚zetas(旋转因子值)和k值是如何相互关联的。我们能否将ntthelper.py中的齐塔值用作高密度脂蛋白实现中的旋转因子值？

Answer 1

虽然你的问题没有答案，但有一些关于DFT/FFT/NTT的背景知识。如果您很好地理解了这些，就可以编写自己的实现，而不需要太多的麻烦。

DFT/FFT

在具有统一的\mathbb{F} (例如\mathbb{C})的域\mathbb{F}[x]/(x^n-1)\cong\prod_{i=0}^{n-1}\mathbb{F}[x]/(x-\zeta^i)\cong\mathbb{F}^n (\text{as rings!}), 中，我们有一个同构D5--基本上是中国剩余定理(这里\zeta是单位的原始n第四根)。这个同构是由f(x)\mapsto(f(1),f(\zeta),\ldots,f(\zeta^{n-1})) (左到右)对单位\zeta (例如\zeta=e^{2\pi i/n})的一些本原根的求值(从左到右)给出的。从右到左，我们对(z_0,\ldots,z_{n-1})\mapsto f \text{ s.t. } f(\zeta^i)=z_i. 进行插值，这种同构在\mathbb{F}上是线性的，由矩阵(\zeta^{ij})_{i,j=0}^{n-1}= \left( \begin{array}{ccccc} 1&1&1&\cdots&1\\ 1&\zeta&\zeta^2&\cdots&\zeta^{n-1}\\ \vdots&\vdots&\vdots&\cdots&\vdots\\ 1&\zeta^{n-1}&\zeta^{2(n-1)}&\cdots&\zeta^{(n-1)(n-1)} \end{array} \right) \frac{1}{n}\left(\zeta^{-ji}\right)_{i,j=0}^{n-1}= \frac{1}{n}\left( \begin{array}{ccccc} 1&1&1&\cdots&1\\ 1&\zeta^{-1}&\zeta^{-2}&\cdots&\zeta^{-(n-1)}\\ \vdots&\vdots&\vdots&\cdots&\vdots\\ 1&\zeta^{-(n-1)}&\zeta^{-2(n-1)}&\cdots&\zeta^{-(n-1)(n-1)} \end{array} \right) 给出，它是快速计算D13的一对算法。口味是DIT (时间抽取，或Tukey)和DIF (频率抽取，或绅士-Sande)。您可以认为这些是上述矩阵的很好的因式分解，或者是矩阵乘法的递归实现。

NTT

NTT是其它一些基域上的DFT，例如有n根的有限域，例如\mathbb{F}_{8380417}有512的统一根(因为有限阶q的乘法群是q-1阶的循环，也正是x^{q-1}-1=0和8380417-1=2^{13}\cdot3\cdot11\cdot31的解)。

NTT在Kyber

中

大多数格型方案都是在\mathbb{F}[x]/(x^n+1)中工作的，n的幂为2。这并没有改变所有的事情；基本上用\zeta^{2i+1}代替了\zeta^i。

为了允许在Kyber (q=3329)中使用较小的模，我们最终得到了一个域，它没有512_th的单位根，而是有256_th的单位根，因此中国剩余定理看起来又像由求值/插值给出的\mathbb{F}_{3329}[x]/(x^{256}+1)\cong\prod_{i=0}^{255}\mathbb{F}_{3329}[x]/(x^2-\zeta^{2i+1}), 。换句话说，系数f(x)=\sum_{i=0}^{255}f_ix^i给出的多项式D36被转换成一个列表\hat{f}=(\hat{f}_{2i}+x\hat{f}_{2i+1})_{i=0}^{127}. ，从而缩短了一个长篇，这样的评估很快就可以归结为做两个长度128个FFT。

Kyber的最后一个复杂之处是在NTT中统一/索引的根的排序，即\hat{f}=(\hat{f}_{2\mathsf{br}(i)}+x\hat{f}_{2\mathsf{br}(i)+1})_{i=0}^{127} ，其中\mathsf{br}(i)是整数0\leq i<127的7位反转，例如112_{10}=1110000_2\xrightarrow{\mathsf{br}}0000111_2=7_{10}. ，原因是DIT/DIF自然地逆转了索引的位顺序，而实现者忽略了(Un)做这件事的额外工作(或者如果您阅读规范的话，就会忽略一些关于AVX指令的工作)。

习题

• 制定/验证DFT。
• 显示x^n+1和x^{2n}-1的DFT是如何相关的。
• 计算DIT/DIF递归。
• 演示如何实现两个长度为128 DFT的Kyber NTT。