密码学基础：环（Ring）上学习错误问题

这是关于密码学的一系列文章中的一部分。如果这是你第一次接触这系列文章，我强烈建议你从 系列的开头 开始。

在我们之前的文章中，我们介绍了另一个供我们研究的结构：环。这些将为一些根本上不同于我们迄今所见的密码学打开一些新的道路。

不过，让我们不要急于求成——在尝试理解任何新的加密技术之前，还有一件事需要做。

没有任何方法在实践中是可用的，除非它是安全的。在此系列的这个阶段，我们完全清楚安全性是通过破解一个方案的难度来衡量的。

例如，解密一条加密消息而不知晓私钥有多难？

为了回答这个问题，我们需要理解假定为困难的相关数学问题。在这个系列中，我们已经见到了一些这样的例子——比如说整数因子分解问题和离散对数问题。

当然，还有更多这样的问题。今天，我们将学习一个全新的问题，它将成为基于环的密码学的基础。

好了，让我们看看我们正在处理什么！

设置准备

环学习错误（Ring Learning With Errors，简称 RLWE）是一个基于多项式的问题。准确地说是一个商多项式环。简要回顾一下，这意味着我们将与某个环一起工作：

这样我们就可以将任何多项式对f(X)进行模约——即模多项式。

我们在 前一篇文章 中详细解释了这一点，所以如果需要，可以去看看！

那么……我们可以对此做什么？

让我们逐步开发我们的理解。给定几个多项式A(X)和S(X)，我们可以计算它们的乘积，如下所示：

在这一点上，环的属性发挥作用：B(X)根据选择的某个多项式f(X)进行模约，确保次数始终是有界的。

这里有一个问题：如果我给你B(X)和A(X)，你认为恢复S(X)的难度有多大？

嗯，这并不难！

事实证明，根据仔细选择的f(X)，环中的每个多项式都可以反转。它的工作原理与有限域中的模逆完全一样：对于每个多项式P(X)，我们可以找到某个P⁻¹(X)，使得：

拥有这个工具使得任务变得相当简单：你只需找到A⁻¹(X)并计算：

好的，这似乎不是一个良好的困难问题的候选者。或者说是？那我们来稍作修改？

转变方向

只需稍微调整一下，我们就可以将这个看似无害且易于解决的表达式转变为更有用的东西。这真的很简单——我们需要做的就是将一些错误或噪声多项式混入其中：

这个错误需要是小的——只要有一点噪声就足够了，正如下文所说的万事皆是如此_。

就这样！这一转折相当特别，因为我们已经习惯了疯狂的事情。

这个看似微不足道的调整隐藏了很多复杂性。让我们稍作思考。

稍微重新组织一下这个表达式：

从这个角度看，很容易看出，给定任何多项式A(X)和B(X)，我们基本上可以选择任何S(X)并计算E(X)。这意味着没有唯一或直接的方法将A(X)与B(X)联系起来。解决方案不再是直接的。

听起来很有希望！

但在我们继续进行一个例子之前，还有一些事情需要谈谈。“学习与错误”中的学习是什么？

学习问题

在这一部分，我们需要再次改变视角。别担心——没有什么奇怪的。这次一切都会很友好。

我不再信任你了。

与其直接使用多项式A(X)和B(X)，不如先来看看它们的评估。所以，我们将为X选择一些值并计算：

这些向量显然是相关的——它们遵循我们之前描述的多项式方程：

顺便提一下，依次乘以a⋅s就是分量乘法。

如往常一样，问题是， 这有什么用 ？随着我们探讨一些应用，这个答案会变得更清晰！耐心点。

现在的问题是：

给定a和b，找到s。

沿着先前讨论的思路，只要e被仔细选择——意味着它是从特定分布中随机抽取的，那么这个问题就非常困难。想象一下类似于正态分布。

之所以难，是因为由于噪声向量e的加入，很难分辨b是一个随机向量还是确实是通过b = a⋅s + e mod q计算出来的_。相应地，在知晓a和b的前提下，确定s也相当困难。当然，只要s和e没有被揭示。

这两种不同的表述被称为 决策问题 和 搜索问题。密码学中的大多数问题都可以写成这两种形式之一——它们是等价的。**

好吧，酷。接下来我们该怎么做？拥有一个困难问题并不有趣，除非我们能用这些新工具构建一些东西！

构建一个例子

我们将基于这篇论文来构建某些内容，这是一项基础性的研究工作。

让我们想象一下我们想要加密一条消息。通常情况下，我们会通过生成密钥来处理此事，并利用它们对消息进行某种操作，接收者随后可以解开这个操作。这正是我们将要做的。

加密

我们的密钥将是一个随机抽样的多项式s(X)_。为简单起见，干脆就记作s。接下来，我们需要一些要加密的消息。为了我们的目的，它将是另一个多项式，记作m。它的系数介于0到某个低于q的整数t之间。

例如，t可以为2，这样系数实际上就形成了一个 二进制序列。**

加密非常简单：我们只需抽样几个多项式a和e，然后计算：

对的，这对(c₀, c₁)构成了密文。这些可以发送给接收者，接收者将尝试在知晓s的情况下恢复消息。因此，这是一个对称加密算法。

解密

接收到消息后，接收者将简单计算：

没错！就是 这么简单。

现在，让我们做一下数学运算，验证一下这是否有效。将c₀和c₁代入就会得到：

如你所见，错误神奇地消失了，因为操作是在t的模下进行的。太棒了！

这是什么魔法？

如果我们比较这两个表达式：

你可能会发现这与我们最初的问题表述之间的相似之处。在没有知晓s的情况下，任何人看到密文都无法将c₀和c₁与随机多项式区分开来。

从本质上讲，他们必须解决RLWE问题。而我们已经知道——这真的很难做到！

这里有一个链接，带你见一个更为 简单的加密例子，我们将在其中对单一位进行编码。这个例子是基于一些稍后我们将讨论的内容——但如果你渴望一些更互动的东西或者想稍作休息，不妨去看看！**

之后还会有时间让我们探索更多方法。现在，重要的是暂时搁置这些，而转向一个非常有趣的连接。

格

哇哇哇。什么？

我们刚在谈论多项式，你现在带来了格？格到底是什么？

慢点，哥们。

好吧，你说得对，我们需要一些背景。尽管我们还没有定义什么是格——也没有定义它们与环的关联_——_我可以说许多后量子密码学方法是基于格的问题。因此理解它们是非常重要的。研究它们与RLWE之间的关系也可能帮助我们了解它们的安全性。

这样，我们就准备好一些定义了。

什么是格？

先在二维空间取一个点。然后，像这样画出两个向量：

当然，能用于密码学，这些向量的值需要是整数。

有了这个，我们就开始一个迭代过程。

在每个向量的末尾放一个点。以它们为起点，重复这个过程。哦，还要在所述向量的反方向同样进行。

你最终得到的是一个无限集的均匀分布的点，就像创建一个无限模式。这就是由我们的两个基向量生成的格。

顺便说一下，在处理有限域时，这些格并非无限——它们是在 q 的模下被约化的，就像你预期的那样。**

好的，好的。又玩了个玩具！但我们知道，除非我们能够提出与之相关的困难问题，否则这对密码学没有什么用。

格问题

在上面的图像中的向量很容易在格中识别出一个模式。假如我给你一个不在该格上的随机点——因为模式很简单，找出与我给你的点最近的格点也相当简单：

仅凭视觉分析，我们就能找出最近的点。

我问你一个问题：这总是那么简单吗？

暂停思考。

.

.

.

.

.

.

.

。☕️ 咖啡总是有帮助的。

.

.

.

.

.

.

好吧，那就够多了！

答案是这取决于。这取决于我们选择的基向量，在某些情况下，新出现的模式不会如此简单。像下面这个例子：

无限模式现在就没有这么简单。而找到与红色点最近的格点的方法是开始尝试基向量的组合，直到我们找到一个佳候选。但是……我们如何能够确保我们的候选点是最近的格点？

这个问题被称为最短向量问题，或简称 SVP。且可这一非常困难。一般来说，困难度因两个方面的不同而加大：

• 基向量如何共线——或如何接近平行。
• 定义格的维度数量。

哦，是的，因为我们不局限于二维。我是不是忘记提到这一点了？在数百或甚至千维的情况下使用格并不罕见。

多维 Morty！

我们可以使用任意数量的维度！这让问题变得非常非常困难。

等一下。等一下。我们不是在寻找与RLWE的联系吗？我们不想偏离我们的主要目标。那么这一切是如何连接起来的呢？

RLWE与格

我们开始于多项式，现在我们正在处理向量。这些构造似乎操作在完全不同的世界上——但实际上它们并没有那么远。看看这个：

看到我们做了什么吗？我们只是将多项式的系数表示为一个向量！你会发现加这些向量等同于加上相关的多项式。

通过这种新视角，让我们再次审视RLWE中的原始困难问题_：

想象一下B(X)是一个向量，表示n维空间中的一个点。我们需要找到S(X)，使得A(X).S(X)与B(X)的关系最近。因此，E(X)将是这些多项式之间可能的最小差异——而应用我们之前的等价关系，它就是最短可能的向量。

啊哈！这正变得越来越清晰！通过把噪声多项式想象成一个短向量，至少这两者问题的最终目标似乎是可以互换的！

然而，似乎出现了一个问题：表达式A(X).S(X)与搜索一个格上的点有什么关系？如果我们能将这个悬而未决的问题捆绑在一起，那么我们就将获得这些问题之间的完全联系。

这个问题并不像以前那么直接。这是最后的冲刺——请再稍微忍耐一下！

还记得环理想吗？那些超级抽象且难以定义的东西？我们在这里会需要它们！

多项式A(X)用于定义在我们选择的多项式环中的一个理想。它被定义为：

这是一个双边理想，因为在多项式环中支持可交换性。

我们已经知道如何使用理想计算一个商环。剩下的就是将理想中的每个多项式映射到一个向量上——就在此时，朋友们，我们刚刚找到了自己的格！

这些通常被称为理想格，因为它们源自多项式环的一个理想。

有趣的是，这个格的 基向量 可以通过对 A(X) 进行连续的乘以 X 来计算。在某些特殊情况下（比如使用 旋转多项式 ），基向量最终成为 A(X) 系数的 旋转。**

例如，使用多项式 A(X) = a₀ + a₁X + a₂X² ，并与环 𝔽[X]/(X³ + 1) 一起工作，那么理想格的基由向量 (a₀, a₁, a₂) ， (a₂, a₀, a₁) 和 (a₁, a₂, a₀) 构成。

总结

我认为，这已经足够让人初步了解支撑大多数后量子方法的结构了。

当然，关于RLWE和格的内容还有很多！但我们目前必须满足于这些。

大多数情况下，这个系列的目标并不是详细而全面地涵盖我们所呈现的每个结构或构造——我认为这里最重要的是我们讨论的一般概念和想法。

我们从这篇文章中的主要收获应该是RLWE和SVP问题，以及环和格在实践中的粗略概念。

这将是我们探索一些PQC方法所需的一切——我们现在准备好进入更有趣的内容了！

展示其中一些方法将是下一篇文章的主题。再见！

• 原文链接： medium.com/thecapital/cr...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，在这里修改，还请包涵～