这是一篇关于后量子公钥加密系统的文章，主要内容总结如下：

• 介绍：

  • 传统公钥加密系统如 RSA 等已广泛使用，现在因量子计算机威胁正逐渐被新的系统取代。
  • 作者阅读了六种“后量子”公钥系统的规格，打算传达对其的“外行理解”。
  • 强调所介绍系统仅为示例，不是真正的加密系统，不要用于实际。

• 一个玩具加密系统：

  • 参数：选择质数 p 和正整数 n，用于定义系统的向量和矩阵维度。
  • 公私钥生成：私钥为两个小向量 a0 和 a1，公共向量 A = a0 + Ta1，其中 T 是随机矩阵。
  • 难以逆推的原因：攻击者易找到满足 u + Tv = A 的向量对，但这些向量通常不是小向量，难以找到真正的私钥向量。
  • 加密：Bob 生成自己的私钥向量 b0 和 b1，计算公共向量 B = b0 + T^Tb1，将其与加密消息 c = m + b1·A 一起发送给 Alice，其中 m 为单比特消息。
  • 解密：Alice 计算 d = c - B·a1，通过一系列向量运算和抵消，恢复出 m 加上一些“噪声”，由于 Bob 选择的消息有限，Alice 能猜出原消息。
  • 解密可能失败：加密和解密过程会添加噪声，可能导致 Alice 猜错消息，但这种情况很少见。
  • Bob 可作弊：Bob 不按规则发送特定值，可部分提取 Alice 的私钥，通过规定 Bob 随机生成私钥的方式并让 Alice 可检查可防御此攻击。

• 一些类似的真实系统：

  • a0 + Ta1 类型：

    • FrodoKEM：使用 n×8 的矩阵，消息为 8×8 矩阵，模 2 的幂。
    • ML-KEM：使用简单列向量，矩阵和向量维度小，元素为大多项式。
    • HQC：向量元素为模 2 的单比特，通过错误纠正码恢复消息。

  • 使用 a0a1⁻¹的变体：

    • BIKE：Bob 的交换为加法，加密为乘法，消息为两个小值，基于错误纠正码。
    • NTRU Prime：在不同代数结构中工作，加密确定性，无解密失败问题。
  • 其他细节差异：公共矩阵由 Bob 从种子重新生成、噪声有不同等级、加密时添加额外噪声、密文可能有损压缩等。

• 与众不同的经典 McEliece：

  • 基于纠错码，错误纠正码本身是私钥，公共密钥是生成矩阵，解密不会失败，但公共密钥巨大。
• 参考文献：列出了作者阅读的六种“后量子”加密系统。