基于误差学习（LWE）问题的公钥加密方案
字数 2893 2025-12-09 03:46:23

基于误差学习（LWE）问题的公钥加密方案

你好！我将为你讲解一个在后量子密码学中非常重要的公钥加密方案，它基于Learning With Errors (LWE) 问题。这个方案是许多现代后量子密码系统（如 Kyber）的理论基石。我会从问题背景开始，循序渐进地解释其数学原理、密钥生成、加密和解密的每一步。

第一步：背景与问题定义

在我们开始前，需要理解核心困难问题：误差学习 (LWE) 问题。

  • 场景类比：想象你有一个秘密的线性方程组。攻击者（黑客）可以向你提交任意一个“查询”向量，你会返回一个“近似”的答案，但这个答案带有一点小的、随机的“误差”或“噪音”。LWE问题断言：即使攻击者获得了大量这样的“带噪声的答案”，他也极难反推出你最初的秘密方程。这个问题的计算困难性是公认的，即使在量子计算机面前也是如此。

  • 数学定义：给定一个公开的随机矩阵 A (大小为 m x n，元素来自整数环 Z_q)，和一个向量 b = A * s + e。其中：

    • s 是秘密向量 (n x 1)。
    • e 是一个小的随机误差向量 (m x 1)。
    • 所有运算在模 q 下进行。
    • LWE假设指出：从 (A, b) 对中找出秘密 s 是计算困难的。

我们的加密方案将基于这个假设来构建。

第二步：方案概述

一个基础的 LWE 公钥加密方案包含三个算法：密钥生成(KeyGen)、加密(Encrypt) 和 解密(Decrypt)。

  1. 公共参数：选择一个大整数 q 作为模数 (例如 2^13=8192)，一个较小的整数 p (例如 2, 4)。明文消息 m 来自一个更小的集合 (例如，{0, 1} 或 {0, 1, 2, 3})。我们还需要一个离散高斯分布或均匀的小整数分布来生成误差 e。

第三步：密钥生成 (KeyGen)

这一步产生一对公钥和私钥。

  • 私钥 (sk)：随机选择一个“小”的秘密向量 s。其每个分量通常从 {-1, 0, 1} 这样的集合中均匀随机选取，或者从一个“窄”的分布中取样。s 必须保密。
  • 公钥 (pk)：
    1. 随机均匀地生成一个公开矩阵 A (大小为 n x n，来自 Z_q)。
    2. 随机生成一个小的误差向量 e (大小为 n x 1，其分量来自误差分布)。
    3. 计算向量 b = A * s + e (所有运算在模 q 下进行)。
    • 公钥就是 (A, b) 对。

直观理解：公钥 (A, b) 看起来就像一个 LWE 样本。知道私钥 s 的人，可以验证 b 大约等于 A*s (因为 e 很小)。而不知道 s 的攻击者，面对 (A, b) 就像面对一个困难的 LWE 问题实例。

第四步：加密 (Encrypt)

假设我们想加密一个消息比特 m (为简化，设 m ∈ {0, 1})。发送者使用接收者的公钥 (A, b) 进行加密。

  1. 引入随机性：随机选择一个“小”的 n 维向量 r，其分量也从 {0, 1} 中均匀选取。这个 r 是每次加密的临时秘密。
  2. 计算密文的第一部分 (u)：计算 u = A^T * r (结果模 q)。这是一个 n 维向量。注意，这里用了 A 的转置 A^T，目的是使维度匹配，使得 u 与私钥 s 可以做点乘。
  3. 计算密文的第二部分 (v)：
    • 首先计算一个“临时密钥”：b^T * r。这标量。
    • 然后将消息编码到密文中。为了抗噪声，我们通常将消息放大。设 Δ = floor(q/2)，那么编码后的消息为 m * Δ (例如，m=1 时编码为 q/2 附近的数)。
    • 最后，我们需要添加一个新的、小的加密误差 e1, e2。完整公式为：
      v = b^T * r + e2 + m * Δ (结果模 q)。这是一个标量。
  4. 输出密文：密文由两部分组成：C = (u, v)。

直观理解：加密过程实际上是在用公钥 (A, b) 构造两个新的、关联的LWE样本。向量 u 像一个“公共部分”，标量 v 包含了用“临时密钥”（近似为 b^T * r）掩盖后的消息。

第五步：解密 (Decrypt)

接收者使用自己的私钥 s 来解密密文 C = (u, v)。

  1. 近似恢复临时密钥：计算 v - s^T * u (所有运算在模 q 下)。
  2. 代入与化简：
    • v = b^T * r + e2 + mΔ
    • b = A * s + e
    • 所以 v = (A * s + e)^T * r + e2 + mΔ = s^T * (A^T * r) + e^T * r + e2 + mΔ
    • 又因为 u = A^T * r
    • 所以 v - s^T * u = (s^T * u + e^T * r + e2 + mΔ) - s^T * u = e^T * r + e2 + mΔ
  3. 处理噪声：结果 e^T * r + e2 + mΔ 中，mΔ 是我们编码后的大消息（接近0或q/2），而 e^T * r + e2 是多个小误差项的组合，总和仍然是一个“相对较小”的噪声。
  4. 解码消息：
    • 计算上面得到的值 (在0到q-1之间)。
    • 观察这个值更靠近 0 还是更靠近 q/2 (即 Δ)。
    • 如果这个值离 0 更近 (即在区间 [0, q/4) 或 [3q/4, q) 内，通过模运算处理环绕)，则解码输出 m' = 0。
    • 如果这个值离 q/2 更近 (即在区间 [q/4, 3q/4) 内)，则解码输出 m' = 1。

核心原理：因为噪声 e^T * r + e2 相对于 q/4 足够小，所以不会将编码后的消息推出其正确的解码区间，从而保证了正确性。

第六步：安全性讨论

  • 安全性基础：该方案的安全性可以归约到LWE问题的困难性。直观上，公钥 (A, b) 是LWE样本，密文 (u, v) 是“重新随机化”后生成的新的LWE样本。如果敌手能破解密文，他就能解决LWE问题。
  • 选择明文攻击(CPA)安全：上述基础方案是CPA安全的。为了达到更强的选择密文攻击(CCA)安全，实际方案（如Kyber）会使用Fujisaki-Okamoto变换等技术进行封装。
  • 误差管理：方案设计的关键是仔细选择误差分布和参数 (q, p)。误差必须足够小以确保正确解密，但又必须足够“大”以提供安全性。

总结一下流程：

  1. 密钥生成：私钥是小的秘密向量 s；公钥是LWE样本 (A, b = A*s + e)。
  2. 加密：用公钥和随机向量 r 生成密文 (u = A^T * r, v = b^T * r + e2 + mΔ)。
  3. 解密：用私钥计算 v - s^T * u，得到 噪声 + mΔ，然后通过看这个值更靠近0还是Δ来解码出消息 m。

这个方案展示了如何将一个抽象的数学难题（LWE）转化为一个实用的、可抵抗量子攻击的公钥加密工具，是理解后量子密码学的重要一步。

基于误差学习（LWE）问题的公钥加密方案 你好！我将为你讲解一个在 后量子密码学 中非常重要的公钥加密方案，它基于 Learning With Errors (LWE) 问题 。这个方案是许多现代后量子密码系统（如 Kyber）的理论基石。我会从问题背景开始，循序渐进地解释其数学原理、密钥生成、加密和解密的每一步。 第一步：背景与问题定义 在我们开始前，需要理解核心困难问题： 误差学习 (LWE) 问题 。 场景类比 ：想象你有一个秘密的线性方程组。攻击者（黑客）可以向你提交任意一个“查询”向量，你会返回一个“近似”的答案，但这个答案带有一点小的、随机的“误差”或“噪音”。LWE问题断言：即使攻击者获得了大量这样的“带噪声的答案”，他也极难反推出你最初的秘密方程。这个问题的计算困难性是公认的，即使在量子计算机面前也是如此。 数学定义 ：给定一个公开的随机矩阵 A (大小为 m x n，元素来自整数环 Z_ q)，和一个向量 b = A * s + e 。其中： s 是秘密向量 (n x 1)。 e 是一个小的随机误差向量 (m x 1)。 所有运算在模 q 下进行。 LWE假设指出：从 (A, b) 对中找出秘密 s 是计算困难的。 我们的加密方案将基于这个假设来构建。 第二步：方案概述 一个基础的 LWE 公钥加密方案包含三个算法： 密钥生成(KeyGen) 、 加密(Encrypt) 和 解密(Decrypt) 。 公共参数 ：选择一个大整数 q 作为模数 (例如 2^13=8192)，一个较小的整数 p (例如 2, 4)。明文消息 m 来自一个更小的集合 (例如，{0, 1} 或 {0, 1, 2, 3})。我们还需要一个离散高斯分布或均匀的小整数分布来生成误差 e。 第三步：密钥生成 (KeyGen) 这一步产生一对公钥和私钥。 私钥 (sk) ：随机选择一个“小”的秘密向量 s 。其每个分量通常从 {-1, 0, 1} 这样的集合中均匀随机选取，或者从一个“窄”的分布中取样。 s 必须保密 。 公钥 (pk) ： 随机均匀地生成一个公开矩阵 A (大小为 n x n，来自 Z_ q)。 随机生成一个小的误差向量 e (大小为 n x 1，其分量来自误差分布)。 计算向量 b = A * s + e (所有运算在模 q 下进行)。 公钥就是 (A, b) 对。 直观理解 ：公钥 (A, b) 看起来就像一个 LWE 样本。知道私钥 s 的人，可以验证 b 大约等于 A* s (因为 e 很小)。而不知道 s 的攻击者，面对 (A, b) 就像面对一个困难的 LWE 问题实例。 第四步：加密 (Encrypt) 假设我们想加密一个消息比特 m (为简化，设 m ∈ {0, 1})。发送者使用接收者的公钥 (A, b) 进行加密。 引入随机性 ：随机选择一个“小”的 n 维向量 r ，其分量也从 {0, 1} 中均匀选取。这个 r 是每次加密的临时秘密。 计算密文的第一部分 (u) ：计算 u = A^T * r (结果模 q)。这是一个 n 维向量。注意，这里用了 A 的转置 A^T，目的是使维度匹配，使得 u 与私钥 s 可以做点乘。 计算密文的第二部分 (v) ： 首先计算一个“临时密钥”： b^T * r 。这标量。 然后将消息编码到密文中。为了抗噪声，我们通常将消息放大。设 Δ = floor(q/2)，那么编码后的消息为 m * Δ (例如，m=1 时编码为 q/2 附近的数)。 最后，我们需要添加一个新的、小的加密误差 e1, e2。完整公式为： v = b^T * r + e2 + m * Δ (结果模 q)。这是一个标量。 输出密文 ：密文由两部分组成： C = (u, v) 。 直观理解 ：加密过程实际上是在用公钥 (A, b) 构造 两个新的、关联的LWE样本 。向量 u 像一个“公共部分”，标量 v 包含了用“临时密钥”（近似为 b^T * r）掩盖后的消息。 第五步：解密 (Decrypt) 接收者使用自己的私钥 s 来解密密文 C = (u, v)。 近似恢复临时密钥 ：计算 v - s^T * u (所有运算在模 q 下)。 代入与化简 ： v = b^T * r + e2 + mΔ b = A * s + e 所以 v = (A * s + e)^T * r + e2 + mΔ = s^T * (A^T * r) + e^T * r + e2 + mΔ 又因为 u = A^T * r 所以 v - s^T * u = (s^T * u + e^T * r + e2 + mΔ) - s^T * u = e^T * r + e2 + mΔ 处理噪声 ：结果 e^T * r + e2 + mΔ 中， mΔ 是我们编码后的大消息（接近0或q/2），而 e^T * r + e2 是多个小误差项的组合，总和仍然是一个“相对较小”的噪声。 解码消息 ： 计算上面得到的值 (在0到q-1之间)。 观察这个值更靠近 0 还是更靠近 q/2 (即 Δ)。 如果这个值离 0 更近 (即在区间 [ 0, q/4) 或 [ 3q/4, q) 内，通过模运算处理环绕)，则解码输出 m' = 0。 如果这个值离 q/2 更近 (即在区间 [ q/4, 3q/4) 内)，则解码输出 m' = 1。 核心原理 ：因为噪声 e^T * r + e2 相对于 q/4 足够小，所以不会将编码后的消息推出其正确的解码区间，从而保证了正确性。 第六步：安全性讨论 安全性基础 ：该方案的安全性可以归约到LWE问题的困难性。直观上，公钥 (A, b) 是LWE样本，密文 (u, v) 是“重新随机化”后生成的新的LWE样本。如果敌手能破解密文，他就能解决LWE问题。 选择明文攻击(CPA)安全 ：上述基础方案是CPA安全的。为了达到更强的 选择密文攻击(CCA)安全 ，实际方案（如Kyber）会使用Fujisaki-Okamoto变换等技术进行封装。 误差管理 ：方案设计的关键是仔细选择误差分布和参数 (q, p)。误差必须足够小以确保正确解密，但又必须足够“大”以提供安全性。 总结一下流程 ： 密钥生成 ：私钥是小的秘密向量 s ；公钥是LWE样本 (A, b = A* s + e) 。 加密 ：用公钥和随机向量 r 生成密文 (u = A^T * r, v = b^T * r + e2 + mΔ) 。 解密 ：用私钥计算 v - s^T * u ，得到 噪声 + mΔ ，然后通过看这个值更靠近0还是Δ来解码出消息 m。 这个方案展示了如何将一个抽象的数学难题（LWE）转化为一个实用的、可抵抗量子攻击的公钥加密工具，是理解后量子密码学的重要一步。