算法作为量子计算时代的密码学标准

数学家经常在默默无闻中辛勤工作，这可能是因为除了拥有相同子专业的数学家之外，很少有人了解他们的工作。即使算法具有实际应用，例如帮助驾驶员看到眼睛无法辨别的接近汽车，汽车制造商(或其软件开发商)也获得了赞誉。

对于密码学家来说尤其如此，他们是无名英雄，他们的算法在人们使用互联网时保证他们的通信和数据安全——技术被称为公钥密码学。

但有时，纯数学会影响现实世界。这发生在今年夏天，当时美国国家标准与技术研究院选择了四种加密算法作为即将到来的量子计算机时代的公钥安全标准，这将使当前的加密系统迅速过时。

四种选定算法中的三种依赖于布朗大学数学家团队领导的工作：教授杰弗里霍夫斯坦、约瑟夫西尔弗曼和吉尔皮弗(他也是布朗大学的研究副总裁)。

NIST 认可的Falcon 算法以及 Falcon 所基于的公钥密码系统 NTRU的故事始于 90 年代中期，当时量子计算仍处于科幻小说领域。当时，霍夫斯坦的目标是开发一种算法来简化和加速传统密码算法的工作方式。1996 年，他与 Silverman 和 Pipher(也与 Hoffstein 结婚)共同创立了 NTRU Cryptosystems Inc.，并将其推向市场。Hoffstein 说 NTRU 的历史是一个“令人毛骨悚然的传奇”，但该公司最终成功，在高通找到了合适的买家。Hoffstein 与其他九位密码学家共同设计的 Falcon，以及 NIST 选择的其他三种算法中的两种，都是建立在原始 NTRU 框架之上的。

从他在麻省理工学院攻读博士学位之前到他在剑桥大学、罗切斯特大学和布朗大学高级研究所担任的每个职位，霍夫斯坦一直是“一个数字人”：“我从来没有想过不要成为一名数学家，”他说。“我向自己保证，我会继续做数学，直到它不再有趣为止。不幸的是，它仍然很有趣!”

在 NIST 入选之后，霍夫斯坦描述了他从数论家到应用数学家的转变，并解决了一个迫在眉睫的至关重要的全球问题。

问：什么是公钥加密?

当你连接到亚马逊进行购买时，你怎么知道你真的连接到亚马逊，而不是一个看起来与亚马逊一模一样的假网站?那么，当你发送你的信用卡信息时，如何发送而不怕被截取和窃取呢?第一个问题由所谓的数字签名解决;二是通过公钥加密解决。在 NIST 的标准化算法中，一种用于公钥加密，另外三种，包括 Falcon，用于数字签名。

这些问题的根源是一种非常特殊类型的纯数学问题。如果你有一条信息，它们很难解决(想想：宇宙结束的时间)，如果你有一条额外的秘密信息，它们很容易解决(需要几微秒)。奇妙的是，只有沟通的一方——亚马逊，在这种情况下——需要拥有秘密信息。

问：量子计算机带来的安全挑战是什么?

如果没有足够强大的量子计算机，解决加密问题的时间是漫长的。使用强大的量子计算机，解决问题的时间可以缩短到几小时或更短。更可怕的是，如果有人拥有一台强大的量子计算机，整个互联网的安全将彻底崩溃。美国国家安全局和大公司都在押注，五年内很有可能建造出强大到足以破坏互联网的量子计算机。

问：您在 90 年代初到中期提出了 NTRU 解决方案，远远早于任何考虑潜在量子计算机的密码学需求的人。你当时的想法是什么?

我发现公钥密码学的三种主要方法非常笨拙且不美观。举个例子，最著名的方法是 RSA，它涉及到取数百位数长的数字，然后将它们提高到数百位数长的幂，然后除以另一个数百位数长的数，然后最后拿走剩下的。这种计算在计算机上很容易实现，但如果你有一个小型、轻量级的处理器，比如 1996 年的手机，这种计算就不太实用了。RSA 也很慢——好吧，毫秒，但这仍然算得很慢。

我们的梦想是找到一种比 RSA 快几个数量级并且可以在低功耗设备上运行的公钥加密方法。我们做到了!实现它的人能够以比 RSA 快 200 到 300 倍的速度运行它。这不是我一个人做的——我痴迷地思考了一年半的问题，但直到我加入了乔·西尔弗曼和吉尔·皮弗，我的布朗同事和 NTRU 的联合创始人.

问：NTRU 代表什么?

我们从来没有说过——人们只是认为我们的意思是技术性的，并使用了他们的想象力!但它代表“Number Theorists R Us”。这激怒了吉尔，因为她是一名谐波分析师，而不是数论家，但她最终原谅了我。

问：您将您的初创公司 NTRU Cryptosystems 描述为有大约五次“濒临”的经历。你面临哪些挑战?

该领域的看门人大多是为公司和计算机科学部门工作的密码学家。让任何新算法被认真对待是非常困难的，如果你不在密码学俱乐部，这尤其困难。在我们的案例中，我们敲响了警钟有两个原因。一方面，我们是局外人，我们将代数数论的额外结构添加到格中，以提高效率。

每当你这样做时，都会有一个严重的风险是你不小心引入了弱点。是的，更有效地做某事真是太好了。但是您是否在此过程中失去了一些重要的安全保障?人们对这种额外的结构深表怀疑是完全可以理解的，它引入了乘法和加法的能力。在人们开始接受没有添加任何弱点之前，花了 10 年的严格审查。

问：这不仅仅是一个学术练习。NTRU 是一家必须与投资者和潜在客户合作的公司。早些时候，NTRU 在密码学中一些家喻户晓的人写的论文中受到了不公正的攻击(后来他们承认了他们的错误)。NTRU是如何幸存下来的?

事实证明，他们的论文在很大程度上被忽略了，但我们的论文非常有趣，以至于每个人都投身其中。他们试图攻击和摧毁它，它得到了极大的关注。你能想象到的每一个表面都被攻城锤所困扰。密码学界对侵犯他们地盘的数学家非常抵触。如果我们不是布朗大学的著名数学家，我们就无法在这场争论中幸存下来。最后，这种关注可能对我们有所帮助。

问：作为数学家——外人，这个世界——有什么优势吗?

我最自豪的事情不一定是特定算法最终进入 NIST 的最后四个选择，尽管三种基于格的算法中的每一种都使用我们的环结构(乘法功能)。他们都使用我们介绍的数学，因为经过超过 25 年的审查，没有因为添加该结构而出现任何弱点。来自代数数论的数学以前不是密码学的一部分。这是我为我的其他生活所做的一部分，我觉得特别高兴的是，我们能够把这个完全抽象的、显然毫无用处的理论事物找到一个实际应用。这样一来，现在这一代密码学家都得懂代数理论，挺好玩的。

问：嫁给另一个数学家是什么感觉?

嫁给一个了解成为一名数学家的感觉的人是宇宙中最幸福的事情。在数学中，你有 99.9% 的时间花费数小时、数周、数月和数年的时间去思考一些毫无结果的事情。很多时候，你认为你有一个绝妙的想法，但它无济于事。嫁给一个了解这种感觉的人真是太好了，即使我们并不总是了解对方在做什么的细节。