CRYSTALS-Kyber 后量子密钥封装机制中的噪声分布与错误纠正

字数 2232 2025-12-08 07:39:32

CRYSTALS-Kyber 后量子密钥封装机制中的噪声分布与错误纠正

题目描述：
在CRYSTALS-Kyber后量子密钥封装机制中，为确保安全性，其加密过程会在密文中引入特定的小范围噪声（采样自中心二项分布）。同时，为了在解密时能够正确恢复共享密钥，必须通过一个“压缩”和“解压缩”过程来容忍并纠正这些噪声引入的错误。请详细解释Kyber中使用的中心二项分布η₁、η₂的定义与采样方法，并逐步阐述压缩（Compress）与解压缩（Decompress）函数的数学原理、参数选择及其如何保证解密的正确性。

解题过程：

步骤1：理解Kyber的LWE问题基础与噪声角色
Kyber基于带错误的模学习（Module-LWE）问题。在加密过程中，一个关键步骤是为向量 e、e₁、e₂ 以及标量 v 添加小噪声。这些噪声从“中心二项分布”中采样，其值很小，确保了解密时即使存在误差，也能通过四舍五入正确恢复消息比特。噪声的大小直接影响安全性（太小不安全，太大会增加解密错误率）。Kyber定义了两个噪声参数：η₁ 用于密钥生成和加密中的部分噪声向量，η₂ 用于加密中的另一个噪声向量和标量。

步骤2：中心二项分布的定义与采样
Kyber使用的不是连续高斯分布，而是易于常数时间实现、离散的中心二项分布 B_η。其定义如下：

采样 (a₁, ..., a_η, b₁, ..., b_η)，其中每个 aᵢ, bᵢ 是独立的均匀随机比特（0或1）。
输出值 = (a₁ + ... + a_η) - (b₁ + ... + b_η)。
因此，输出范围是 [-η, η] 之间的整数，且分布对称，均值为0。例如，η=2时，可能的输出为 -2, -1, 0, 1, 2，概率分别为 1/16, 4/16, 6/16, 4/16, 1/16。在Kyber-512/768/1024中，η₁ 和 η₂ 通常取值2（如Kyber-512）或其他小整数。

步骤3：压缩与解压缩的数学原理
在Kyber中，密钥封装的目标是让双方协商出一个比特串（如256位），用作对称密钥。加密时，消息比特（0或1）被编码为模 q 的整数 0 或 ⌈q/2⌋（即 q/2 四舍五入）。解密时，会得到一个带噪声的近似值，需要通过“压缩”传输部分信息，并在解密端“解压缩”和四舍五近来恢复。

给定模数 q（Kyber中 q=3329）和一个压缩参数 d（d bits），定义两个函数：

压缩函数 Compress_q(x, d)：将模 q 的整数 x 映射到 d 比特。

\[ \text{Compress}_q(x, d) = \lfloor (2^d / q) \cdot x \rceil \mod 2^d \]

这里 ⌊·⌉ 表示四舍五入到最近整数。输出是一个 0 到 2^d -1 的整数，只需 d 比特存储/传输。

解压缩函数 Decompress_q(x', d)：将 d 比特的整数 x' 映射回模 q 的一个近似值。

\[ \text{Decompress}_q(x', d) = \lfloor (q / 2^d) \cdot x' \rceil \]

注意：Decompress 的结果不一定等于原始的 x，但会接近 x（误差可控）。

步骤4：压缩/解压缩在Kyber加密解密中的具体应用
假设加密时，我们有一个系数 m ∈ {0, 1}，对应消息比特。编码为 m' = m * ⌈q/2⌋（在模 q 下）。加密过程中，生成一个带噪声的标量 v，然后计算：

\[c = \text{Compress}_q(v, d) \]

这里 d 是参数，例如 d=10（对于Kyber-512）。压缩后的 c 作为密文的一部分发送。

解密时，接收方计算：

\[v' = \text{Decompress}_q(c, d) \]

然后利用私钥和密文的其他部分计算出一个近似值，减去 v' 后得到：

\[w = \text{某个值} - v' \quad (\text{模 } q) \]

理论上，如果没有噪声，w 应等于 m'。但由于噪声，w 会接近 0 或 ⌈q/2⌋。解密时只需判断 w 更接近哪个值：

\[\text{输出消息比特} = 0, \quad \text{如果 } |w|_q < ⌈q/4⌋, \text{ 否则输出 } 1 \]

这里 |·|_q 表示模 q 下的最小绝对值代表（范围在 -q/2 到 q/2）。

步骤5：参数选择与正确性保证
正确性要求：即使有噪声，解密时四舍五入结果必须与原始消息比特一致。这取决于：

噪声的大小（由 η₁, η₂ 控制）。
压缩参数 d：更大的 d 意味着压缩损失更小，但密文更长。d 必须足够大，使得压缩/解压缩引入的误差加上原始噪声，总误差小于 q/4。
模数 q=3329 是固定的，⌈q/2⌋=1664 或 1665（取决于四舍五入），q/4≈832。

在Kyber设计中，通过严格分析中心二项分布噪声的最大可能值、压缩误差上界（最大为 ⌈q / 2^{d+1}⌋），可以证明在所选参数（如 η₁=η₂=2, d=10）下，解密错误率极低（如 2^{-140} 以下）。因此，噪声分布与压缩/解压缩协同工作，在确保安全性的同时，使解密几乎总是正确的。

CRYSTALS-Kyber 后量子密钥封装机制中的噪声分布与错误纠正题目描述：在CRYSTALS-Kyber后量子密钥封装机制中，为确保安全性，其加密过程会在密文中引入特定的小范围噪声（采样自中心二项分布）。同时，为了在解密时能够正确恢复共享密钥，必须通过一个“压缩”和“解压缩”过程来容忍并纠正这些噪声引入的错误。请详细解释Kyber中使用的中心二项分布η₁、η₂的定义与采样方法，并逐步阐述压缩（Compress）与解压缩（Decompress）函数的数学原理、参数选择及其如何保证解密的正确性。解题过程：步骤1：理解Kyber的LWE问题基础与噪声角色 Kyber基于带错误的模学习（Module-LWE）问题。在加密过程中，一个关键步骤是为向量 e 、 e₁ 、 e₂ 以及标量 v 添加小噪声。这些噪声从“中心二项分布”中采样，其值很小，确保了解密时即使存在误差，也能通过四舍五入正确恢复消息比特。噪声的大小直接影响安全性（太小不安全，太大会增加解密错误率）。Kyber定义了两个噪声参数：η₁ 用于密钥生成和加密中的部分噪声向量，η₂ 用于加密中的另一个噪声向量和标量。步骤2：中心二项分布的定义与采样 Kyber使用的不是连续高斯分布，而是易于常数时间实现、离散的中心二项分布 B_ η。其定义如下：采样 (a₁, ..., a_ η, b₁, ..., b_ η)，其中每个 aᵢ, bᵢ 是独立的均匀随机比特（0或1）。输出值 = (a₁ + ... + a_ η) - (b₁ + ... + b_ η)。因此，输出范围是 [ -η, η ] 之间的整数，且分布对称，均值为0。例如，η=2时，可能的输出为 -2, -1, 0, 1, 2，概率分别为 1/16, 4/16, 6/16, 4/16, 1/16。在Kyber-512/768/1024中，η₁ 和 η₂ 通常取值2（如Kyber-512）或其他小整数。步骤3：压缩与解压缩的数学原理在Kyber中，密钥封装的目标是让双方协商出一个比特串（如256位），用作对称密钥。加密时，消息比特（0或1）被编码为模 q 的整数 0 或 ⌈q/2⌋（即 q/2 四舍五入）。解密时，会得到一个带噪声的近似值，需要通过“压缩”传输部分信息，并在解密端“解压缩”和四舍五近来恢复。给定模数 q（Kyber中 q=3329）和一个压缩参数 d（d bits），定义两个函数：压缩函数 Compress_ q(x, d) ：将模 q 的整数 x 映射到 d 比特。 \[ \text{Compress}_ q(x, d) = \lfloor (2^d / q) \cdot x \rceil \mod 2^d \] 这里 ⌊·⌉ 表示四舍五入到最近整数。输出是一个 0 到 2^d -1 的整数，只需 d 比特存储/传输。解压缩函数 Decompress_ q(x', d) ：将 d 比特的整数 x' 映射回模 q 的一个近似值。 \[ \text{Decompress}_ q(x', d) = \lfloor (q / 2^d) \cdot x' \rceil \] 注意：Decompress 的结果不一定等于原始的 x，但会接近 x（误差可控）。步骤4：压缩/解压缩在Kyber加密解密中的具体应用假设加密时，我们有一个系数 m ∈ {0, 1}，对应消息比特。编码为 m' = m * ⌈q/2⌋（在模 q 下）。加密过程中，生成一个带噪声的标量 v ，然后计算： \[ c = \text{Compress}_ q(v, d) \] 这里 d 是参数，例如 d=10（对于Kyber-512）。压缩后的 c 作为密文的一部分发送。解密时，接收方计算： \[ v' = \text{Decompress}_ q(c, d) \] 然后利用私钥和密文的其他部分计算出一个近似值，减去 v' 后得到： \[ w = \text{某个值} - v' \quad (\text{模 } q) \] 理论上，如果没有噪声，w 应等于 m'。但由于噪声，w 会接近 0 或 ⌈q/2⌋。解密时只需判断 w 更接近哪个值： \[ \text{输出消息比特} = 0, \quad \text{如果 } |w|_ q < ⌈q/4⌋, \text{ 否则输出 } 1 \] 这里 |·|_ q 表示模 q 下的最小绝对值代表（范围在 -q/2 到 q/2）。步骤5：参数选择与正确性保证正确性要求：即使有噪声，解密时四舍五入结果必须与原始消息比特一致。这取决于：噪声的大小（由 η₁, η₂ 控制）。压缩参数 d：更大的 d 意味着压缩损失更小，但密文更长。d 必须足够大，使得压缩/解压缩引入的误差加上原始噪声，总误差小于 q/4。模数 q=3329 是固定的，⌈q/2⌋=1664 或 1665（取决于四舍五入），q/4≈832。在Kyber设计中，通过严格分析中心二项分布噪声的最大可能值、压缩误差上界（最大为 ⌈q / 2^{d+1}⌋），可以证明在所选参数（如 η₁=η₂=2, d=10）下，解密错误率极低（如 2^{-140} 以下）。因此，噪声分布与压缩/解压缩协同工作，在确保安全性的同时，使解密几乎总是正确的。