介绍
1994 年，计算机科学家 Peter Shor 发现 如果发明了量子计算机，它们将摧毁大部分用于保护在线共享信息的基础设施。 这种可怕的可能性让研究人员争先恐后地制定新的“后量子”加密方案，以尽可能多地保存信息，以免落入量子黑客之手。
今年早些时候，美国国家标准技术研究院 发现 四名决赛选手在寻找后量子密码学标准。 其中三个使用“格子密码学”——一种受格子启发的方案，格子是空间中点的规则排列。
格密码学和其他后量子可能性在关键方面与当前标准不同。 但它们都依赖于数学上的不对称性。 许多当前密码系统的安全性基于乘法和因式分解：任何计算机都可以快速将两个数字相乘，但可能需要几个世纪才能将密码学上的大数字分解为其主要组成部分。 这种不对称性使得秘密易于编码但难以解码。
Shor 在他 1994 年的算法中揭示的是，因式分解的一个怪癖使它容易受到量子计算机的攻击。 “这是量子计算机可以做的一件非常具体、特别的事情，”他说 凯瑟琳斯坦奇，科罗拉多大学博尔德分校的数学家。 因此，在 Shor 之后，密码学家有了一份新工作：找到一组新颖的数学运算，这些运算很容易做到但几乎不可能撤消。
格密码学是迄今为止最成功的尝试之一。 最初于 1990 年代开发，它依赖于逆向工程点和的难度。
下面是描述格密码学的一种方式：想象你的朋友有一个格，它只是平面上规则重复图案中的一串点。 您的朋友希望您说出其中的 10 个要点。 但他很难，他不会画整个格子。 相反，他只列出了两点——第一点 x- 值 101 和 y-值为 19，另一个坐标为 [235, 44]。
幸运的是，很容易在格子上找到新的点，因为当你在一个格子上加减任意两个点时，你会在同一个格子中得到第三个点。 所以你所要做的就是把你朋友给你的分数相加，或者将它们乘以整数然后相加，或者两者的某种组合。 以八种不同的方式进行此操作，您将能够回答朋友的问题。
但你的朋友仍然不满意。 他给你同样的两个起点，然后问你点[2, 1]是否在同一个格子上。 要正确回答这个问题，您必须找到 [101, 19] 和 [235, 44] 的组合，从而产生 [2, 1]。 这个问题比第一个问题要难得多，你可能最终只能通过猜测和检查来得到答案。* 这种不对称性正是格密码学的基础。
如果您真的想使用格密码术来共享信息，您将执行以下操作。 想象一下，一位朋友（一位更好的朋友！）想要向您发送一条安全消息。 您从数字的方形网格开始。 假设它有两行两列，看起来像这样：
现在你想出了一个只有你知道的私人“密钥”。 在此示例中，假设您的私钥只是两个秘密数字：3 和 -2。 将第一列中的数字乘以 3，将第二列中的数字乘以 -2。 将每行中的结果相加以获得包含两个条目的第三列。
将新列粘贴到网格的末尾。 这个新的三列网格是您的公钥。 免费分享！
（现实世界的场景会稍微复杂一些。为了防止黑客解码您的私钥，您必须在最后一列中添加一些随机噪声。但是为了简单起见，我们将忽略这一步。 )
现在您的朋友将使用公钥向您发送消息。 她想到了自己的两个秘密数字：2 和 0。她将第一行的数字乘以 2，将第二行的数字乘以 0。然后她将每一列的结果相加得到第三行。
她现在将新行附加到网格底部并将其发回给您。 （同样，在真实系统中，她需要为她的行添加一些噪音。）
现在您将阅读该消息。 为此，您检查朋友的最后一行是否正确。 将您自己的私钥应用于她行的前两个条目。 结果应与最后一个条目匹配。
您的朋友也可以选择向您发送最后一列数字错误的行。 她知道这个数字不符合你的计算。
如果您的朋友发送了一行最后一个数字正确的行，您会将其解释为 0。如果她发送了一行数字不正确的行，您会将其解释为 1。因此，该行编码为单个位：0 或 1。
请注意，外部攻击者无法访问您的私钥或您朋友的私钥。 没有这些，攻击者将不知道最终数字是否正确。
实际上，您希望发送的消息长度超过一位。 因此，想要接收 100 位消息的人将生成 100 个新列，而不是一个。 然后消息的发件人将创建一个新行，修改最后 100 个条目以将每个条目编码为 0 或 1。
如果真正实施格密码术，它将有无数的细微差别在这个场景中没有涉及。 例如，如果您希望消息真正安全，不被窥探，则矩阵需要具有难以想象的条目数量，这使得整个事情变得如此笨拙以至于不值得使用。 为了解决这个问题，研究人员使用具有有用对称性的矩阵来减少参数数量。 除此之外，还有一整套调整可以应用于问题本身、错误合并的方式等等。
当然，总有可能有人会发现格密码学的致命缺陷，就像 Shor 对因式分解所做的那样。 无法保证特定的加密方案在面对任何可能的攻击时都能正常工作。 密码学在被破解之前一直有效。 事实上，今年夏天早些时候 一个有前途的后量子密码学方案被破解 使用的不是量子计算机，而是普通的笔记本电脑。 对 Stange 来说，整个项目产生了一个令人不安的悖论：“我发现密码学如此惊人的一点是，我们为人类建立了这个基础设施，坚信我们作为人类的能力是有限的，”她说。 “太落后了。”
*：如果您好奇的话，答案是 7 × [101, 19] – 3 × [235, 44] = [2, 1]。 [回到文章]
