作为一名密码学家，人们经常问我有关密码学的问题。有时，当问题确实很好时，它们会变成博客文章与世界其他地方分享。今天的问题是“什么是加密原语？”但事实证明，这个太难了。相反，这篇文章将涵盖：

• 为什么这么难定义？

• 如此模糊的术语有何用处？

• 您能否提供一 (1) 个示例来说明如何在“空间和时间”中使用它？

为什么很难？其他解释该术语的尝试列出了一堆原语。提供大量示例通常是好的，但除非您已经知道它们如何在更复杂的系统中使用，否则很难看出是什么让它们变得“原始”。维基百科采用自上而下的方法来定义它们：

加密原语是成熟的低级加密算法，经常用于构建计算机安全系统的加密协议。 -加密原语 - 维基百科

所以现在问题已经成为焦点。加密原语是一种低级构建块，通常依赖于非常高级的“月球数学”。密码学家以某种方式解决了这个矛盾，然后这个术语就变得有用了。

我接触“加密原语”这个术语的次数越多，我对真正理解它的含义就越没有信心。是我个人这么认为，还是这个词没有通用的定义？或者这个术语是否具有我所缺少的上下文敏感性？- StackExchange 上最相关的帖子

由于缺乏“加密原语”的真正定义，我将全力以赴地进行这个类比（所以我真的希望它能够实现）。

家具就像一个密码系统。 “原始材料”是内六角扳手、销钉、L 型支架、木胶、金属支架、实木、胶合板、工程木材等。 - 引用我自己的强调

如果我必须对密码原语和密码系统（或家具和组件）之间的区别给出明确的答案，那么原语的设计并不是“内部”完成的。密码系统设计者对此不抱任何功劳。他们认为以一种新颖的方式将原语组合在一起以创建更复杂的系统。刨花板可能是别人设计的，但书架是家具公司设计的。同样，Space and Time 正在构建Proof of SQL™，但我们使用现有的库来构建多项式承诺等组件。

这并不是说创建加密原语不是一项创造性或困难的任务。恰恰相反。一个好的原语将在其开发人员无法预测的上下文中被反复使用。你知道，有点像螺丝刀（实际上需要大量的工程设计）。但是，一旦您获得了现代工程的奇迹，您就可以建造更宏伟的东西，例如电视柜。

与“工具”或“积木”相比，我更喜欢家具的比喻，因为它还让我们在概念上又进行了一次非常有用的跳跃。在解释加密协议时，对它们实际功能的解释常常与它们如何实现的方式纠缠在一起。实际上，它们是两个独立的轴，可以根据它们进行分组，但它们通常是根据功能而不是构造来分组的。但是，根据原语对协议进行分类使我们能够做出广泛的陈述，例如“基于对称密钥原语的协议通常更快，并且似乎是后量子安全的”，而无需指定我们是在谈论加密、多方计算还是密码学有担保的投票计划。这有点像说“平板包装家具运输成本更便宜，但不太坚固”，但没有具体说明您是在谈论桌子还是椅子。

关于研究报告的结构，有一个笑话是这样的：“第一部分是给所有人的，第二部分是给专家的，最后一部分是给演讲者的。”我们已经进入了第二部分。如果您以前编写过程序，那么它会更有意义。

富有表现力的编程语言或查询语言将具有数据类型。因此，为了证明有关这些程序的任何内容，我们需要一种方法来在我们的证明系统中表示这些数据类型。正如我在之前的博客文章中提到的，这意味着我们将其转化为数学。

我们需要什么样的数据类型？嗯，大多数都可以分解为标量类型，这是一种牢不可破的原子（例如，布尔值、整数类型，可能是字符，具体取决于语言）和复合类型（如元组和数组），它们是构建起来的来自更简单的类型。处理标量数据类型相当简单；我们只是将它们编码为数字。1

与标量数据类型相比，复合数据类型是一种在某些地方有东西的东西。关于复合数据类型的问题是您想要查看它们的内部。我们将重点关注一个非常简单的、类似列表的一维数组示例。如果你有一个名为 `𝙲𝚞𝚜𝚝𝚘𝚖𝚎𝚛𝚜` 的数组，那么你想要用它做的最基本的事情就是对其进行索引。您调用“𝙲𝚞𝚜𝚝𝚘𝚖𝚎𝚛𝚜[𝚒]`，您将获得列表中的第 i个客户（当然是零索引）。

我们可以通过插值多项式来做到这一点。基本上，对于任何数组 `𝙰`，我们可以构造一个多项式ã(x)，这样将x代入i就可以得到条目 `𝙰[𝚒]`。2

数据结构和算法经常一起教授，因为它们协同工作。当有有效的算法来处理数据结构时，它们会更有用。我们刚刚描述了一种以我们的证明语言可以推理的方式表示通用复合数据类型的方法。但我们注意到，要查看数组中的一个特定位置，需要计算多项式，而这似乎不可扩展。我们可以使用什么样的算法呢？

答案是Lund、Fortnow、Karloff 和 Nisan 的和校验协议。自 20 世纪 90 年代以来，它一直是交互式证明的主要内容。这可能看起来有点做作，但它所做的是让证明者说服验证者超立方体 H 上的多变量多项式g的总和 = {0, 1} m（这都是由 0 和 1 组成的有序m元组） ）是，无论该值是什么。我们称之为y。

在我们尝试澄清一些技术定义之前，让我们先了解它的实际用途。第一步是检查动漫猫数学推特以获得一些见解。

（另外，请注意：sum-check 中的总和超过零和一，但如果我们将其读取为二进制，则范围只是 0 到 2 m -1。）因此，结合我们在数据结构速成课程中学到的知识对于证明系统和这条有用的推文，我们得到总和检查为我们提供了一种可证明地迭代数组的方法，但它在迭代过程中我们可以做的事情非常有限。因此，我们设计 Proof-of-SQL™️ 的任务是将其他更复杂的运算转化为求和。

这就是为什么和检查协议的定义令人困惑、做作且有点倒退的原因。当尝试应用该协议时，您不会问“我关心什么多项式？”或者“这里的超立方体有什么特别之处？”。真正的技术挑战是选择或构造多项式以使该求和有意义。经过注释，sum-check 证明的语句看起来更像是这样：

以下是如何使用它的一个示例。许多（所有？）语言都有映射功能，您可以在其中获取类似列表的东西（或其中几个）和一个函数，然后映射会将该函数应用于列表的每个元素并返回结果列表。

如果该函数（称为f）是一个多项式，并且多元多项式*a(x 1 , x 2 , … x m )表示一个数组，则组合f(a(x 1 , x 2 , … x m ))*也是一个多项式。事实上，将一个点代入该多项式就可以得到该点的地图结果！

由于我们还可以将结果数组表示为多项式，因此证明者可以运行求和检查来说服验证者他们计算出正确的结果。如果我们设置正确，只有当*r(x 1 , x 2 , … x m )实际上是将映射应用于a(x 1 , x 2 , … x m )*的结果时，我们才能使多项式为零。那么总和应该加上一堆零，整个结果就是零。

（好吧，对于一些随机权重和其他东西需要多加注意，但我保证，这几乎是我们在 SQL™ 证明中实际使用的东西。）

感谢您阅读本文。这非常深入地探讨了细节，所以我想缩小范围并涵盖主要内容。希望读完本文后，您可以参加下一次区块链/加密货币会议，并与密码学研究人员进行闲聊。您可以说，“嘿，您听说过 Space and Time 的 SQL™ 证明吗？它就像 SNARK，但它们的主要加密原语是和检查。”密码学家会说：“哦，这很聪明。这样证明者就可以避免进行 FFT。”然后你会抬起头，微笑，并交换一个会意的眼神，就像两个木匠欣赏做得很好的燕尾榫接头（并且知道一旦木胶干燥，它甚至不需要钉子或螺丝）。您会意识到，了解加密原语的超级技术和精确定义并不重要。重要的是知道你交了一个朋友。

‍

[1] 具体来说，一切都会变成 𝔽 p的元素，这是一种奇特的说法，表示一切都是整数 mod p，其中p是素数。

[2] 这促使我们选择继续研究 𝔽 p。通过选择p为素数，我们得到了一个非常有用的属性，这正是我们从实数中所期望的：除了零之外的所有值都有乘法逆元。这最终会产生深远的影响，例如 𝔽 p上插值多项式的存在。不幸的是，大多数关于多项式插值的可用文献（这里有一个资源）都涉及实数或有时是复数，但由于注意到了很好的属性（用数学术语来说，𝔽 p是一个域），很多理论都经过了必要的修改。经必要修改。