晶体压缩和解压缩.Kyber

Question

我目前正在研究凯伯文件。关于第2.2节的压缩和解压缩，我有一个问题，但首先我要引述以下的说法：

压缩和减压。我们现在定义一个函数\text{Compress}_q (x, d)，它接受一个元素x ∈ \mathbb{Z}_q，并在\{0,..., 2^d − 1\}中输出一个整数，其中d < \lceil\log_2(q) \rceil。我们进一步定义了一个函数\text{Decompress}_q，因此x' =\text{Decompress}_q(\text{Compress}_q(x,d),d) \quad (1)是一个接近x的元素--更具体地说，是|x'-x \text{ mod}^{\pm} q|\leq B_q := \lceil \frac{q}{2^{d+1}} \rfloor。满足这些要求的函数定义为：\text{Compress}_q(x,d)= \lceil (2^d / q) \cdot x \rfloor \text{ mod}^+ 2^d , \\ \text{Decompress}_q(x,d) = \lceil (q/2^d) \cdot x \rfloor，如果x'是x的函数，就像在Eq中一样。(1)对于随机选取的x\leftarrow \mathbb{Z}_q，x' - x \text{ mod}^\pm q在至多B_q的数量级整数上的分布几乎是一致的。

• 我的第一个问题是关于不等式|x'-x \text{ mod}^{\pm} q|\leq B_q := \lceil \frac{q}{2^{d+1}} \rfloor，如何给出详细的估计？我不太明白你怎么能说这个数量比居中的二项分布B_q要小。
• 我的第二个问题是关于压缩和解压缩函数的定义(来自“满足这些要求的函数.”)。我现在看不出这些函数是如何满足需求的。

Answer 1

首先，请理解这里B_q并不代表中心二项分布，而是表示整数值\lceil\frac q{2^{d+1}}\rfloor。

接下来，可以将压缩和解压缩函数如下所示：

考虑分数x/q，并找到分母2^d最近的分数，假设这是c/2^d，然后是\mathrm{Compress}(x,d)=c\mod^+2^d。

考虑分数x/2^d，并找到分母q最近的分数，假设这是b/q，然后是\mathrm{Decompress}(x,d)=b。

因为q>2^d的每个分数都有分母，c/2^d是区间((2c-1)/2^{d+1},(2c+1)/2^{d+1})的中心，它包含有分母q的\lfloor q/2^d\rfloor或\lceil q/2^d\rceil分数。这些分数的分子(在0,q-1)中没有其他整数)将在压缩下映射到c，而\mathrm{Decompress}(c,d)将映射到分子列表的一半“完全”。最坏的情况是，当我们从x开始时，这是分子列表的极端末端。在这种情况下，压缩然后解压缩将我们映射到分子列表的上方，在分子列表的一半，因此，这最多是远离我们开始的点的\lceil q/2^{d+1}\rfloor。