获得图灵奖的密码学家的工作及其影响.pdf

年 月计 算 机 应 用 文 摘第 卷 第 期获得图灵奖的密码学家的工作及其影响黄 海（广东第二师范学院计算机学院，广州）摘 要 图灵奖是当今计算机界最引人注目的奖项之一 旨在表彰在计算机领域取得卓越贡献的科学工作者 自其设立以来 密码学在其中占据重要地位 已有十多位密码学家获此殊荣 文章将对密码学领域的这些获奖者进行介绍并分析他们工作之间的相互关系 关键词 图灵奖 密码学 相互关系中图法分类号 文献标识码 引言 年 月 日，美国计算机协会（）将 年度的“图灵奖”（）颁发给斯坦福大学的 和，以表彰他们在公钥密码体制方面开创性的工作。他们的论文 于 年 发 表 在 期刊上，由此引发了全球公钥密码研究的热潮。此外，结合网络技术，这些研究将改变人们的生产和生活方式。至今，共有六组密码学家荣获图灵奖，包括 和 （年），（年），（年），、（年），和 （年），和（年）。其中，后五组密码学家是因其在密码学领域的研究而获奖。凭借非确定性自动机理论与 合作获得了 年的图灵奖，同时他还以素数检测和 密码在密码学界享有声誉。本文将介绍这些密码学家的主要获奖成就，特别是分析他们之间的联系与区别。和 的工作 密码学的起源可以追溯到古埃及法老时代。他们通过有意改变文字形式来隐藏信息，以突显其尊贵地位。早期的战争无疑是促进密码技术发展的主要驱动力。在第一次和第二次世界大战中，出于战争需求，涌现出大量的密码技术。这些技术需求间接地催生了自动化、快速实现密码技术的机器，为计算机技术的起步奠定了基础。世纪 年代中期，公司的 博士提出了数据加密标准（），其并被美国定为联邦数据加密标准，被广泛应用于加密领域。在所有这些密码学工作中，保密通信的前提是通信双方必须事先商定密钥。然而，麻省理工学院的 和 意识到这种方式的不便之处，提出了一种新的思路：通信双方只需通过一个类似于电话号码的公开信息就能够实现保密通信。公开密钥的概念由此而来。和 是享有国际声誉的密码技术与安全技术专家。在工作期间，与密码学大师 相识，并了解了 结构。和 在论文中提出了一种协商密钥的方法，其与传统的加密方法不同。尽管密钥是密码技术成功的核心要素，但这篇具有深远影响的论文开辟了公开密钥密码研究的新方向。的工作 和 的思想实现方法如下：通过两个整数相乘可以快速计算，但分解因子没有有效的快速方法。同在麻省理工学院工作的，三人提出了一个简单的方案，即公开一个大整数 和一个整数，发送方将消息 经过 计算得出密文，接收方使用保密的 进行 运算以还原出消息。这里要求 是两个大素数的乘积，一旦 分解，就可以通过公开的 和 计算出。他们相信因子分解是十分困难的，而事实也证实了这一点，从而引发对因子分解的研究。尽管存在多项研究，但有效的因子分解方法仍未出现。在这里必须提及背包密码体制。早期，背包密码体制与 体 制 齐 名，由 美 国 的 和 提出。背包密码利用一个相对容易求解的背包问题将其转化为一个难解的问题，并将其作为公开密钥。通过对报文使用难解的背包问题进行加密，因为背包问题属于 问题，所以即使拥有公开密钥也难以破解密文。只有合法的接收方可以使用私钥进行解密。然而，背包密码很快被攻破，出现的多种变体也都被成功攻破。和 的工作 年，和 提出了“零知识证明”（）的概念。这一概念指的是，在不向验证者提供有用信息的情况下，证明者能够使验证者相信某个判断是正确的。零知识证明实际上是一个涉及双方或多方的协议，即通过一系列步骤，证明者向验证者证明并使其相信自己知道或拥有某一消息。然而，证明的过程并不会向验证者透露有关被证明消息的任何信息。在密码学领域，零知识证明得到了广泛的应用，尤其在认证协议、数字签名等方面。随后的研究学者设计了许多优秀的算法，有效地解决了许多难解问题。博士曾在 教授的指导下于 年 获 得 加 利 福 尼 亚 大 学 伯 克 利 分 校（）的博士学位，随后在 年加入了麻省理工学院。是 的同事，两人从研究生时期开始就一直保持合作。在一次构思如何通过电话进行安全的扑克牌游戏时，他们设计了一个方案：将单个比特数据进行加 密，并 确 保 其 安 全 性。从 那 时 起，和 开始验证他们的设计能够扩展到更多更复杂的问题，比如通信协议和在线交易。由于在密码学和复杂理论领域作出的创新性工作，和 不仅在 年获得了图灵奖，还在后来被选为美国工程院院士。的工作 主要研究计算复杂性理论以及求解问题时忽略机器的具体差异时所需的计算资源：基本去处的次数和占用空间的办法，以及节省资源。将这一理论应用于“密码学”和程序正确性验证。年 月，他和合作者 在西雅图召开的 届 计 算 理 论 专 题 研 讨 会 上，首 次 提 出 了 的概念，并综合利用密码学、概率算法和概率交互证明等手段解决了程序正确性验证的难题。主要研究计算复杂性理论，这一理论主要关注在忽略计算机具体差异时解决问题所需的计算资源，如基本操作的次数和占用空间的方式，以及资源的节省。他将这一理论应用于密码学和程序正 确 性 验 证 领 域。年 月，他 与 合 作 者 在西雅图举办的第 届 计算理论专题研讨会上首次提出了 的概念，并综合应用了密码学、概率算法和概率交互证明等方法成功解决了程序正确性验证这一难题。在计算复杂性理论方面的研究受到了以色列学者 的启发。当时，在麻省理工学院举办了讲座，激发了 的兴趣。因此决定以此为研究方向，最终完成了他的博士论文与机器无关的递归函数复杂性理论。这篇论文不仅在计算复杂性分析方面提出了一些新的观点，还在复杂性类的归纳上展现了更高的抽象度，使他成为计算复杂性理论的主要奠基人之一。此前，已有四位科学家因其在计算复杂性理论领域的贡献而获得图灵奖，他们分别是 （年）、（年）、（年）、（年）。在图灵奖的历史上，这个领域获奖科学家最多，从中可以看出计算复杂性作为计算机科学中的基础分支，具有突出的地位和重要性。（姚期智）的工作 姚期智在计算机学科方面的贡献主要集中在计算理论领域。尽管最初学习物理学，并获得哈佛大学的物理学博士学位，但是在加州大学从事研究期间意识到计算机学科对未来社会具有巨大影响力，认识到这是一门重要且具有巨大发展潜力的新兴学科。于是，他放弃了八年的物理学研究，转向投身计算机科学领域。两年后，他成功获得伊利诺伊大学的计算计 算 机 应 用 文 摘 年第 期机博士学位。接下来的几年里，姚期智发表了近百篇具有影响力的学术论文，几乎涵盖计算复杂性的各个方面。比如，他证明了著名的 发生器产生的随机数实际上是伪随机的。他提出了“随机性和难度”以及“计算熵”（）等重要概念，极大地推动了密码学的发展。此外，姚期智还是研究网络通信复杂性理论的国际先驱，早在 年就提出了量子通信复杂性，为量子计算机的理论基础做出了基本贡献。同时，他为通信领域建立了关键的模型，并提出了一整套分析方法，使通信复杂性成为该领域一个重要的研究分支，并将他的研究成果应用于许多相关领域。姚期智由于在伪随机数生成、密码学和通信复杂度等领域所取得的卓越成就，荣获了 年度图灵奖，成为目前唯一一位获得该殊荣的亚裔计算机科学家。和 的工作 和 是师兄弟关系，他们在 世纪 年代中期分别在著名的逻辑学家和计算机专家阿隆索邱奇（）门下学习。在有限自动机及其判定问题的研究中，两人紧密的合作为非确定性有限状态自动机的理论奠定了基础。主要致力于计算理论领域，是计算复杂性理论的先驱者。而 则主要专注于将逻辑学应用于计算机科学中。年，研究中心为 和 提供了一份暑期工作，工作内容并没有具体要求，允许他们从事自己感兴趣的任何研究。于是，和 联手开始了有限状态自动机（，）的研究。在此过程中，他们定义了一种新型、称为“非确定性”的有限状态自动机（，）。这种机器在读取一定输入后会有一个可以选择的“菜单”以进入可能的新状态，使得给定的输入计算不再是单一的，每个选择代表一种可能的计算路径。和 将图灵的有限状态自动机从确定性扩展到非确定性，极大地推动了有限状态自动机理论的发展。尽管非确定性有限状态自动机在能力上并不比确定性有限状态自动机更强，但它能简化机器描述并加快问题求解速度。后来的实践证明，在机器翻译、文献检索和字处理程序等应用中非确定性有限状态自动机都发挥了重要作用。年，和 共同发表了题为有限自动机与其判定性问题的论文，其中提出了非确定性自动机的概念。这一概念被证明是计算理论研究中的重要创新。由于他们的贡献，和 荣获了 年度图灵奖。此外，六组密码学家（图灵奖获得者）之间存在许多关联。他们的主要工作和关系可以通过图 进行表示。图 图灵奖获得者密码学家的关系图 结束语图灵于 年发表的论文奠定了计算机科学的理论基础，他在其中提出的计算模型被称为“图灵机”。尽管计算模型只是该论文脚注中附带提到的，但它成为了后来计算机科学发展的关键。在二战期间，图灵通过破译德军的 密码，获得了德军的活动情报，特别是在大西洋潜艇战中的行动。这使得他荣获战后的光荣勋章，被授予“”（），这是对非战斗人员极高的荣誉。图灵奖自 年创立以来已有 个年度，总体上侧重于计算机科学理论和软件领域。在相对较少的从业人员中，密码学领域有六组科学家获得了这一殊荣，这突显了密码技术工作的重要价值。这也是对那些在密码学领域从事工作的人以及图灵本人的出色贡献的一种美好纪念。参考文献：吴鹤龄，崔林 图灵奖 计算机发展史的缩影，北京：高等教育出版社，刘瑞挺图灵奖首位华裔得主：姚期智教授计算机教育，（）：（），（）：，：，：作者简介：黄海（），博士，讲师，研究方向：算法设计与分析、网络安全。年第 期 计 算 机 应 用 文 摘