1868 年，数学家 Charles Dodgson（更为人熟知的名字叫 Lewis Carroll）宣称一种被称为维吉尼亚密码（Vigenère cipher）的加密方案是“无法破解的”。他没有证据，但有令人信服的理由，因为三个多世纪以来，数学家一直在试图破解该密码，可一直也没有成功。只有一个小问题：事实上，一位名叫 Friedrich Kasiski 的德国步兵军官在五年之前就破解了它，记录此事的书在当时几乎没有引起任何注意。

只要人们还在发送加密信息，密码学家就一直在玩这种猫捉老鼠的游戏——创造密码并破解密码。康奈尔科技学院和康奈尔大学的密码学家 Rafael Pass 表示：“几千年来，人们一直想弄清楚，‘我们可以打破这个循环吗？’”五十年前，密码学家朝着这个方向迈进了一大步。他们证明只要有“单向函数”，你就可以创建被证明是安全的密码。单向函数是一种很容易计算的函数，但很难逆运算。从那时起，研究人员设计出各种候选单向函数，从基于乘法的简单运算到更复杂的几何或对数运算都有。

今天负责传输信用卡号和数字签名等任务的互联网协议依赖于这些函数。以色列海法理工学院的密码学家 Yuval Ishai 表示：“现实世界中使用的绝大多数加密都可以基于单向函数。”但这一进步没有终结这场猫捉老鼠的游戏——只是更加突出了它的焦点。现在密码学家不必担心加密方案各个方面的安全性，只要关注其核心的函数即可。但是目前使用的函数中没有一种被明确证明是单向函数——我们甚至不确定真正的单向函数是否真的存在。密码学家证明，如果它们确实不存在，那么安全加密就是不可能的。

在缺乏证据的情况下，密码学家只能希望能在攻击中幸存下来的函数是安全的。Ishai 表示，研究人员没有统一的方法来研究这些函数的安全性，因为每种函数都“来自不同的领域，来自不同的专家组”。长期以来，密码学家们一直想知道是否有一种不那么特别的方法。Pass 问道：“是否存在着某个问题，只有一个主问题，告诉我们密码学是否可行？”

现在他和康奈尔大学的研究 生Yanyi Liu

。他们

，真正单向函数存在与否取决于计算机科学另一个领域中最古老也最核心的问题之一，这个领域被称为复杂性理论或计算复杂性。这个被称为Kolmogorov 复杂性的问题涉及区分随机数字字符串和包含某些信息的字符串之间的区别有多难。