安全密码学的存在取决于一个最古老的问题--计算复杂度。

前沿

1868 年，数学家查尔斯·道奇森（更为人所知的是刘易斯·卡罗尔）宣称一种称为维吉尼亚密码的加密方案是“牢不可破的”。他没有证据，但他的信念有令人信服的理由，因为三个多世纪以来，数学家一直试图破解密码，但没有成功。

只有一个小问题：事实上，一位名叫弗里德里希·卡西斯基的德国步兵军官在五年前就在一本当时几乎没有引起注意的书中打破了它。

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

五年前，密码学家朝这个方向迈出了一大步。他们表明，如果您可以访问单一成分，则可以创建可证明安全的密码：“单向函数”，该函数易于执行但难以逆转。从那时起，研究人员设计了一系列候选单向函数，从基于乘法的简单运算到更复杂的几何或对数过程。

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

几个世纪以来，数学家一直试图证明欧拉的流体方程可以产生荒谬的答案。一种新的机器学习方法让研究人员押注“爆炸式增长”即将来临。

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

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

密码学家长期以来一直想知道是否有一种不那么特别的方法。“是否存在一些问题，只有一个主问题，告诉我们密码学是否可行？” 通问。

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

康奈尔科技大学和康奈尔大学的密码学家 Rafael Pass 帮助找到了一个问题，该问题可以揭示单向函数以及现代密码学是否真的存在。

休·戈登

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

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

该论文促使密码学家和复杂性理论家更紧密地合作，激发了将他们的方法联合起来的一系列活动。麻省理工学院计算机科学家Ryan Williams说：“多个研究小组正在努力追查事情的真相。”

利用复杂度

通常，一个难题是一个障碍。但是在密码学中，你可以将它部署到你的对手身上，这是一个福音。1976 年，Whitfield Diffie和Martin Hellman写了一篇开创性的论文，他们认为单向函数的特殊复杂度正是密码学家需要满足新兴计算机时代的需求。“我们今天站在密码学革命的边缘，”他们写道。

Martin Hellman（中）和 Whitfield Diffie（右）在 1977 年与 Ralph Merkle 的合影中显示，他们写了一篇开创性的论文，将单向函数与密码学联系起来。

Chuck Painter / 斯坦福新闻社

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

要了解单向函数的工作原理，假设有人要求您将两个大素数相乘，例如 6,547 和 7,079。得出 46,346,213 的答案可能需要一些工作，但这是非常可行的。但是，如果有人将数字 46,346,213 递给您并询问其质因数，您可能会不知所措。事实上，对于素因数都很大的数字，没有有效的方法（我们知道）来找到这些因数。这使得乘法成为单向函数的一个有希望的候选者：只要你从足够大的素数开始，这个过程似乎很容易做到，但很难撤销。但我们不确定情况是否如此。有人可以在任何时候找到一种快速分解数字的方法。

密码学家已经从不同的数学领域收集了各种潜在的单向函数，但没有一个函数比另一个函数具有更高的要求。比如说，如果明天将乘法作为单向函数推翻，那将不会说明其他候选单向函数的有效性。密码学家长期以来一直在询问是否存在一些典型的单向函数——如果被破坏，它将把所有其他候选人都拉下来。

1985 年，波士顿大学的计算机科学家列昂尼德·莱文 ( Leonid Levin ) 正式回答了这个问题，展示了一个“通用”的单向函数，如果有的话，它肯定是一个单向函数。但罗格斯大学的计算机科学家Eric Allender说，他的构造“非常人工” 。“除了得到这样的结果之外，任何人都不会出于任何原因研究它。”

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

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

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

什么是随机的？

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

Yanyi Liu 与 Pass 合作，有意义地将单向函数和 Kolmogorov 复杂性联系起来。

谢长治

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

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

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

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

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

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

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

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

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

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

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

相反，如果计算近似的时界 Kolmogorov 复杂度对于许多字符串来说太难有效地求解，那么 Liu 和 Pass 表明必须存在真正的单向函数。如果是这样的话，他们的论文甚至提供了一种具体的制作方法。Ishai 说，他们在论文中描述的单向函数过于复杂，无法在实际应用中使用，但在密码学中，实际构造通常很快就会出现理论突破。他说，刘和帕斯的单向功能的不切实际“不是一个基本的限制”。

Andrey Kolmogorov 提出了一种测量随机性的方法，该方法基于描述一串数字的生成的难易程度。

亚历山大·马卡罗夫/RIA Novosti

如果它们的函数可以实用，则应优先使用基于乘法和其他数学运算的候选单向函数。因为如果有什么是单向函数，那么这个函数就是。“如果我们能打破这样的计划，那么所有其他计划也可以被打破，”帕斯说。

更丰富的理论

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

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

“如果你认为这个 [Kolmogorov 复杂性] 问题很困难……那么你就相信单向函数，”威廉姆斯说。并且“如果你完全相信加密，那么你必须相信这个版本的有时间限制的 Kolmogorov 复杂性一定很难。”

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

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