一个关乎密码学存在性的主问题

原文：https://www.quantamagazine.org/researchers-identify-master-problem-underlying-all-cryptography-20220406/

翻译：Kurt Pan

1868 年，数学家Charles Dodgson（更为人所知的名字是Lewis Carroll）宣称一种称为维吉尼亚密码的加密方案是“牢不可破的”。他没有给出证明，但他的这种信念也有令人信服的理由：三个多世纪以来，数学家一直试图破解该密码，但并没有成功。

但事实上，一位名叫Friedrich Kasiski的德国步兵军官在五年前就在一本当时几乎没有引起注意的书中攻破了维吉尼亚密码。

只要人们还在发送秘密信息，密码学家就一直在玩这种猫鼠游戏，创造和破解一个又一个的密码。“几千年来，人们一直试图弄清楚，我们能打破这个循环吗？”康奈尔大学的密码学家Rafael Pass说。

半个世纪前，密码学家朝这个方向迈出了一大步。他们表明，如果你可以调用一个东西，你就可以创建可证明安全的密码。这个东西就是单向函数，一种易于正向运行但难以逆转的函数。从那时起，研究人员设计了一系列候选的单向函数，从基于乘法的简单运算到基于更复杂的几何或对数过程。

今天，用于传输信用卡号和数字签名等任务的互联网协议依赖于这些单向函数。“现实世界中使用的大多数密码都是基于单向函数的”，以色列Technion 的密码学家Yuval Ishai说。

但这一进步并没有结束猫鼠游戏，而是更加突出了其焦点问题的尖锐。现在，密码学家不必担心加密方案的各个方面的安全性，而只需关注其核心函数即可。但是目前使用的所有函数都没有被明确证明是单向函数——我们甚至不确定是否存在真正的单向函数。密码学家已经证明了，如果真正的单向函数不存在，那么安全的密码学是不可能的。

在没有证明的情况下，密码学家只能寄希望于在攻击中幸存下来的那些函数真的是安全的。研究人员没有统一的方法来研究这些函数的安全性，因为每个函数都“来自不同的领域，来自不同的专家”，Ishai 说。

密码学家长期以来一直想知道，是否有一种不那么特殊的方法。“是否存在某个问题，这唯一的一个主问题，来告诉我们密码学究竟是否可行？” Pass问道。

现在，他和康奈尔大学研究生Yanyi Liu已经证明，答案是肯定的。他们证明了，真正的单向函数的存在性取决于计算复杂性理论中的一个最古老也最核心的问题之一。这个问题被称为 Kolmogorov 复杂度，它涉及区分随机字符串和包含某些信息的字符串的困难性。

https://arxiv.org/abs/2009.11514

Liu 和 Pass 证明了，如果某个版本的 Kolmogorov 复杂度在特定意义上难以计算，那么真正的单向函数确实存在，并且有一种明确的方法来构造。相反，如果这个版本的 Kolmogorov 复杂度很容易计算，那么单向函数就不存在。 “这个问题在人们引入单向函数之前就出现了，结果证明实际上它完全表征了单向函数”，Pass说。

这一发现表明，密码学家不必四处寻找候选的单向函数了，而是可以将精力集中在理解 Kolmogorov 复杂度上。“一切都取决于这个问题了，”Ishai说，该证明是“密码学基础理论上的突破性工作”。

这篇论文促使密码学家和复杂性理论专家更紧密地合作，激发了一系列将他们两个领域的方法结合起来的行动。麻省理工学院计算机科学家Ryan Williams说：“多个研究组正在努力弄清楚事情的真相。”

1利用困难性

通常来说，一个困难问题会是一个障碍。但是在密码学中，当你可以部署这个困难问题用以抵御你的对手时，这就成了一个福音。1976 年，Whitfield Diffie和Martin Hellman写了一篇开创性的论文，他们认为单向函数的特殊困难性正是密码学家需要的可以满足新兴计算机时代的需求的东西。“我们今天站在密码学革命的边缘，”他们写道。

https://ee.stanford.edu/~hellman/publications/24.pdf

在接下来的几十年里，研究人员想出了如何利用单向函数构建各种各样的密码学工具，包括私钥加密、数字签名、伪随机数生成器和零知识证明（一个人可以说服另一个人相信一个陈述是真实的而同时不透露证明）。Pass说，Diffie和Hellman的论文“几乎就像一个预言”。他说，从单向函数这一单一构建块开始，密码学家设法构建了“这些超级复杂美丽的造物”。

要了解单向函数的工作原理，假设有人要求你将两个大素数相乘，例如 6547 和 7079。要得出答案 46346213 可能确实需要一些工作，但这是非常可行的。但是，如果有人将数字 46346213 递给你并询问其素因数是多少，你就可能会不知所措了。事实上，对于素因子都很大的数，没有已知的有效的算法来找到这些因子。这使得乘法成为单向函数的一个有希望的候选者：只要你从足够大的素数开始，这个乘法过程似乎很容易正向去做，但很难反过来做。但我们不确定情况是否真的如此，完全可能在某个时候某个人就找到了一种快速分解数字的方法。

密码学家已经从不同的数学领域收集了各种潜在的单向函数，但没有哪一个函数比另一个函数具有更高的断言。比如说，如果明天乘法作为单向函数这一论断被推翻了，这个事实也不会对其他候选单向函数的有效性产生任何影响。密码学家长期以来一直在问，是否存在某个典型的单向函数——如果其被证伪，将把所有其他候选单向函数都拉下来。

1985 年，波士顿大学的计算机科学家Leonid Levin正式回答了这个问题，展示了一个“通用”单向函数，如果任何其他东西是单向函数的话，这个函数保证是一个单向函数。但Rutgers大学的计算机科学家Eric Allende说，他的构造“非常刻意” ，“除了为了得到这样的结果之外，任何人都不会出于任何原因去研究它。”

https://dl.acm.org/doi/10.1145/22145.22185

密码学家真正追求的是一种源于某种自然问题的通用单向函数——其可以对单向函数是否存在这一问题提供真正的洞见。长期以来，研究人员其实一直都在考虑一个特殊的问题：Kolmogorov 复杂度，这是一种起源于 1960 年代的随机性度量。但它与单向函数的联系是微妙且难以捉摸的。

2004 年，作为一名研究生，Pass开始着迷于这种联系。多年来，他一直在玩弄这个问题，但没有取得多大进展。但他确信那里是有些什么东西的，而且过去五年中关于 Kolmogorov 复杂度的爆发性活动进展更是提高了他的兴趣。

Pass试图说服几名研究生与他一起探讨这个问题，但当时没有人愿意承担这个可能会徒劳无功的项目。之后 Yanyi Liu 开始在康奈尔读研究生。“Yanyi无所畏惧，”Pass在一封电子邮件中写道。他们一起跳了进去。

2什么是随机？

从本质上讲，随机性的概念很难确定。有一个呆伯特漫画，其中一位办公室导游向呆伯特展示了会计部门的“随机数发生器”——结果证明这是一个不断重复数字 9 的怪物。“你确定那是随机的吗？” 呆伯特问道。“这就是带随机性的问题，”他的向导回答，“你永远无法确定。”

如果有人向你展示数字字符串 99999999999999999999 和 03729563829603547134 并说它们是都是随机选择的，你是不能完全揭穿这种说法的：当你随机选择数字时，这两个字符串具有相同的概率被生成。然而，第二个字符串确实感觉要更随机。

“当我们说‘那件事是随机的’时，我们认为我们知道我们的意思，”Allender说。“但直到定义了 Kolmogorov 复杂度的概念，它才被证明是具有数学意义的定义。”

为了理解随机数字串的概念，Andrey Kolmogorov 在 1960 年代决定不再关注生成字符串的过程，而是关注它的描述难易程度。字符串 99999999999999999999 可以简明扼要地描述为“20 个 9”，但字符串 03729563829603547134 可能没有比字符串本身更短的描述。

Kolmogorov 将字符串的复杂度定义为产生字符串作为输出的最短程序的长度。如果我们正在处理比如说一千位字符串，有些程序很短，例如“打印一千个 9”或“打印数字 ”或“使用以下公式打印 的前一千位...... 。” 另外的一些字符串就不可能简洁地描述，并且没有比写出整个字符串并告诉计算机打印它的程序更短的程序。其他的字符串的程序的长度落在二者中间的某个地方。

Kolmogorov 复杂度很快成为计算机科学的核心概念之一。这个概念是如此基础，以至于它在 1960 年代被多次独立发现。这是“一个深层次的问题，不仅仅是关乎随机性和数学，而且关乎一般科学，”Pass说。

Kolmogorov 复杂度只有一个缺点：它是不可计算的，没有程序可以计算每个可能字符串的复杂度。我们知道这一点是因为如果有这样的程序，最终会产生矛盾。

要看到这一点，假设我们有一个程序可以计算任意字符串的 Kolmogorov 复杂度，将此程序称为 。现在，让我们搜索最短的数字串 - 称之为 - 它的 Kolmogorov 复杂度是 长度的两倍。具体来说，我们可以想象 有 100 万个字符，所以我们正在寻找的是 Kolmogorov 复杂度为 200 万的字符串 （意味着输出 的最短程序有 200 万个字符）。

使用我们工具箱中的程序 ，计算 很容易（尽管不一定很快）：我们可以编写一个新程序，称为 。程序 本质上是在说，“按顺序遍历所有字符串，使用程序 来计算他们的 Kolmogorov 复杂度，直到找到第一个 Kolmogorov 复杂度为 200 万的字符串。” 我们在构建 时需要使用程序，所以 总共有略多于 100 万个字符。但是这个程序输出的是 ， 的定义为一个字符串，它的最短程序有 200 万个字符。推出矛盾。

但是，如果我们不是寻找输出一个字符串的最短程序，而是寻找输出字符串的最短的合理高效的程序（在这里可以指定“合理”的具体含义），这种矛盾就会消失。毕竟，程序 需要大量的时间来运行，因为它必须检查这么多的字符串。如果我们禁止这么慢的程序，我们就会得到一个称为“时间受限”的 Kolmogorov 复杂度 的概念。这个版本的 Kolmogorov 复杂度是可计算的——我们可以计算每个可能的字符串的时间受限Kolmogorov 复杂度，至少在原则上是这样。在某些方面，它与最初的 Kolmogorov 复杂度概念一样自然。毕竟，Pass说，我们真正关心的是，“你真的能在我们生活在地球上的时候，或者在宇宙还存在的时候产生这个字符串吗？”

由于时间受限的 Kolmogorov 复杂度是可计算的，下一个问题自然是计算的难度如何。而这正是 Liu 和 Pass 证明的是单向函数是否存在的关键的问题。“这是一个可爱的洞察力，”艾伦德说。

更具体地说，假设你将目光投向了一个不那么崇高的目标，不是去计算每个可能字符串的确切时间受限 Kolmogorov 复杂度——假设你满足于近似计算它，并且只针对大多数字符串。如果有一种有效的方法可以做到这一点，Liu 和 Pass 表明，那么真正的单向函数就不存在了。 在这种情况下，我们所有的候选单向函数都将立即变得可破解，不仅在理论上，而且在实践中。“密码学再见！” Pass说。

相反，如果计算近似的时间受限 Kolmogorov 复杂度对于很多字符串来说依然很难有效地求解，那么 Liu 和 Pass 表明真正的单向函数一定存在。 如果是这种情况，他们的论文甚至提供了一种特定的构造方法。Ishai 说，他们在论文中描述的单向函数过于复杂，无法在实际应用中使用，但在密码学中，实际可用的构造通常很快就会在理论突破之后出现。他说，Liu和Pass的单向函数的不实用“不是一个根本的限制”。

如果它们的函数可以实用，则相对于基于乘法和其他数学运算的候选单向函数，应优先使用该单向函数。因为如果有什么东西是单向函数的话，那么该函数一定也是。“如果我们能攻破该方案，那么所有其他方案也可以被攻破，”Pass说。

3更丰富的理论

该论文在密码学和复杂性理论的交汇处引发了一系列新的研究。牛津大学的复杂性理论家Rahul Santhanam表示，虽然这两个学科都在研究计算问题的难度，但它们的思维方式并不相同。他说，密码学发展迅速、务实且乐观，而复杂性理论发展缓慢且保守。 在后一个领域，“有这些长期存在的开放性问题，每十几年都会发生一些事情，”他说。但是“这些问题都非常深刻且困难。”

现在密码学和复杂性理论有了一个共同的目标，而且每个领域都为对方提供了一个全新的视角：密码学家有充分的理由认为存在单向函数，而复杂性理论家也有了不同的充分理由去认为有时间限制的 Kolmogorov 复杂度是困难的。由于新的结果，这两个假设相互支持。

“如果你认为Kolmogorov 复杂度问题很困难……那么你就相信单向函数，”Williams说。并且“如果你完全相信密码学，那么你就不得不相信这个版本的时间限制的 Kolmogorov 复杂度一定很难。”

密码学家现在面临着试图使 Liu 和 Pass 的单向函数更实用的任务。他们还开始探索除了时间受限 Kolmogorov 复杂度之外的任何其他“主问题” 是否也可以决定单向函数或更复杂的密码工具的存在性。与此同时，复杂性理论家开始去深入研究理解 Kolmogorov 复杂度的难易程度。

所有这些都表明，这一发现的真正遗产可能还没有到来。“它是某种东西的种子，可能会发展成更丰富的理论，”Ishai 说。