关于Kyber中差异分布的几个问题

Question

我有两个基本问题有关的特殊分布的|x'-x \text{ mod}^{\pm} \, q| \leq B_q := \left\lceil \frac{q}{2^{d+1}} \right\rfloor在凯伯。第一个问题是关于论文，第二个问题是关于规范中的一个部分。我是作为一个问题来问这个问题的，因为我认为它在主题上很适合。

1. In 纸 on页面4，它写着：

• 不幸的是，没有人解释为什么会出现这种情况。我已经为选定的参数绘制了一次分布图，并且会同意这一点，但这更像是一个基于经验的论点。但是，这是否也有正式的理由，例如，通过计算？

1. In 规格说明 on页面21上面写着：

• 不幸的是，我在这里忽略了一个人是如何得出结论的，那就是差别是3或4。我只能用我写的脚本来解释这一点。我感兴趣的是，是否可以用计算器更正式地显示这一点。
• 在这一点上，我还感兴趣的是，如何得出这样的结论，即每个系数在\left\{-1,0,1\right\}、\left\{-1,0,1,2\right\}或\left\{-2,-1,0,1\right\}上都是均匀分布的。
• My猜测：我认为这与B_q有关，在本例中，根据参数d = 10和q = 3326，以及B_q = 2。由于|x'-x \text{ mod}^{\pm} \, q| \leq B_q := 2和x'是3或4，所以我们可以计算出压缩输入和解压缩输出之间的差异，从而得到\left\{-1,0,1,2\right\}，这取决于定义“差异”的方式，我们也可以得到\left\{-2,-1,0,1\right\}。另一个集合\left\{-1,0,1\right\}发生在B_q = 1 (包含在case |x'-x \text{ mod}^{\pm} \, q| \leq B_q := 2中)的情况下。如果有人能吐露我的猜测，那就太好了。

编辑：在回应@kodlu的评论时，以下是mod^\pm \, q的定义，如本文所定义的：

Answer 1

我喜欢考虑压缩和解压函数，它操作于范围[0,1) (包装)中分母的分子，其分母是2^d或q。压缩函数将分母为q的分子映射到分母为2^d的最近分数的分子，解压缩函数将分母为2^d的分子映射到分母为q的最近分数的分子。注意，因为2^d压缩是满射的，而解压是内射的。

在具有分母2^d的每一对分数之间，都有带有分母q的[q/2^d]或[q/2^d]+1分数(更准确地说，有第一类的q\mod{2^d}对和第二类的2^d-q\mod{2^d} )。同样，通过取分母2^d的每一对分数之间的中间点，我们将包装区间[0,1)划分为2^d子区间，其中压缩函数在子区间上是常数。同样，在每个子区间中分母q的分数的数目不是[q/2^d]就是[q/2^d]+1。现在请注意，对整数[q/2^d]和[q/2^d]+1要么是2B_q和2B_q+1，要么是2B_q-1和2B_q。

对于具有分母q的2B_q+1分数，我们有一个中心分数，它最接近于子区间中间有分母2^d的分数。这个中心分数的分子固定在\mathrm{decompress}(\mathrm{compress}(x))下，对应于x'-x=0。在子区间中中心分数左侧有分母q的每个D32分数都对应于x'-x值-B_q,-B_q+1,\ldots -1，同样，具有分母q的B_q分数对应于x'-x值1,2,\ldots, B_q。请注意，这种情况对应于所有x'-x值的完全一致性。

在有分母q的2B_q-1分数的情况下，我们又有一个中心分数，它与分母2^d在子区间中间的分数最接近。这个中心分数的分子固定在\mathrm{decompress}(\mathrm{compress}(x))下，对应于x'-x=0。在子区间中中心分数左侧有分母q的每个D46分数都对应于x'-x值-B_q+1,-B_q+2,\ldots -1，同样，具有分母q的B_q分数对应于x'-x值1,2,\ldots, B_q-1。请注意，这种情况对应于不包括x'-x值的\pm B_q值的一致性。

如果存在带分母q的D56分数，则在子区间中有一个与分母2^d最接近的中心‘’分数，但不平衡意味着左有B_q-1分数，右边有B_q分数，反之亦然。前者对应于不包括x'-x值的-B_q值的均匀性，后者对应于不包括B_q的x'-x值的均匀性。

在所有情况下，x'-x值都是一致的，不包括x'-x；在2B_q-1和2B_q的情况下，对于一些大小为B_q的整数，我们有一个较小的权重。并不是所有的情况都可以落入2B_q+1，因为q\mod 2^d\neq 0。这解释了问题1中的说法。

对于问题2，请注意，在Kyber q=3329中，B_q=2，[q/2^d]=3和我们有带[q/2^d]=3分式的q\mod 2^d=257子区间和带分母q的[q/2^d]+1=4分数的767子区间。包含3个分数的子区间是2B_q-1情况，正如我们所期望的那样，我们对值\{-B_q+1,\ldots,B_q-1\}=\{-1,0,1\}有相同的表示。包含4个分数的子区间是2B_q情况，可以是向左(在这种情况下我们看到-值\{-B_q,\ldots, B_q-1\}=\{-2,-1,0,1\})，也可以是向右(在这种情况下，我们看到-值\{-B_q+1,\ldots, B_q\}=\{-1,0,1,2\} )。这就解释了问题2背后的说法。