最著名的加密算法（2022年哥德尔奖出炉）

编辑：桃子 拉燕

【新智元导读】今天，ACM官方公布了2022年哥德尔奖的得主，以表彰3位加密学大佬对全同态加密系统做出的杰出贡献。

2022哥德尔奖公布了！

ACM算法与计算理论兴趣组(SIGACT)宣布，2022年哥德尔奖授予Craig Gentry，Zvika Brakerski以及Vinod Vaikuntanathan，表彰其对密码学做出的革命性贡献。

加密大神Craig Gentry获奖

Craig Gentry

Craig Gentry是一位美国计算机科学家，目前在由 Silvio Micali 创立的区块链创业公司Algorand Foundation担任研究员。

因在密码学方面的杰出工作，Gentry为人所知，特别是在同态加密。

1993年，在杜克大学学习期间，他成为普特南研究员。2009年，他的博士论文A Fully Homomorphic Encryption Scheme赢得了美国计算机协会同态加密博士论文奖。

2010年，他因同样的作品获得了美国计算机协会的葛丽斯·莫瑞·霍普奖。2014年，他赢得了麦克阿瑟奖（MacArthur Fellowship）。他还是IBM托马斯J. 华生实验室的研究科学家。

Zvika Brakerski

Zvika Brakerski是魏茨曼科学研究所（Weizmann Institute of Science）计算机科学与应用数学系副教授。

他的研究兴趣在于计算机科学基础，目前主要研究密码学和量子计算。

2011年，在导师Shafi Goldwasser的建议下，Brakerski在魏茨曼科学研究所里完成了博士学位。然后在斯坦福大学计算机科学系担任了两年的西蒙斯博士后研究员。

他曾在2002年获特拉维夫大学工程学院硕士学位。在此之前，在2001年，他获得了特拉维夫大学工程学院和计算机科学学院联合理学学士学位。

Vinod Vaikuntanathan

要说Vinod Vaikuntanathan这个人，不光名字不一般，履历更不一般。

他是麻省理工学院计算机科学系Steven and Renee Finn职业发展助理教授。他的主要研究方向是密码学理论与实践。

他致力于研究「基于格」的密码学（格子密码），使用整数格构建高级密码原语。同时，还包括研究如何让密码抵抗泄露，开发抵抗对抗性信息泄漏的算法等等。

最近，Vinod主要在研究对加密数据进行计算的理论和实践，构建强大的密码对象，如全同态加密和函数加密等等。

Vinod在麻省理工学院获得博士学位，并获得了2009年George M. Sprowls奖，以表彰他在计算机科学领域的最佳麻省理工学院博士论文。

同时，他还是2008年IBM Josef Raviv博士后奖学金、2013年Alfred P. Sloan研究奖学金、2014年微软教师奖学金和2014年NSF业奖的获得者。

全同态加密是啥？

2022年哥德尔奖励给以下两篇论文：

https://sigact.org/prizes/gödel/citation2022.html

这两篇论文通过高效的全同态加密（Fully Homomorphic Encryption/FHE）方案对密码学做出了革命性的贡献。

在FHE方案中，数据按照标准加密方案进行安全加密。

此外，FHE还提供了计算加密数据和生成加密结果的能力，而不需要解密或任何密钥。

这种能力解锁了大量的应用程序，让我们可以安全地将昂贵的计算外包给不可信的服务器，并安全地在多个实体之间执行协作计算。

论文1:

论文2:

简单来说，个人隐私能得到保护，离不开同态加密这一形式。

最传统的加密体系的构建往往都需奥一个KEY（密钥）。

通过这个密钥，就可以把明文信息加密成密文。在另一端通过密钥再把密文变回原来的样子。

如果没有这个Key的话，其他的人很难知道我们到底传递了什么信息。

同态加密体系有不同的分类，大致上被分成4类：部分同态、近似同态、有限级数全同态与完全同态。

要说全同态加密这一概念的提出，早在上世纪70年代末就已经出现了。

在1978年，密码学界的几位大牛Rivest、 Adleman和Dertouzos在论文On Data Banks and Privacy Homomorphisms中第一次提出了全同态加密的概念 (称为隐私同态)。

然而，在接下来的三十年里，构建一个可以对加密数据进行任意计算的FHE方案仍然是一个悬而未决的问题。

在以上获奖论文之前，Craig Gentry曾在2009年提出了一个FHE的结构。Gentry在2009年提出来的全同态系统，我们往往称之为第一代全同态加密系统。

由此可见，全同态加密这一概念已经被提出了很久了。

这些论文对理论和应用研究都产生了巨大的影响，从高级密码原语的构造，到 FHE 的实现，以及后量子加密候选方案的设计。

一路看来，全同态体系的大门被Gentry大神敲开已经过去了11年了。现在业界对于FHE的研究百花齐放，不少人都在不同的角度和应用需求上在研究全同态系统。

哥德尔奖

提起哥德尔奖，含金量可不是一般的高。

该奖项是由欧洲理论计算机学会（EATCS）和美国计算机学会基础理论专业组织（ACM SIGACT）在1993年联合设立的。

该奖项颁发给理论计算机领域最杰出的学术论文。其名字的由来是逻辑学与计算机科学先驱——Kurt Gödel（库尔特·哥德尔）。

说起哥德尔，不光人长得帅，才华更是不一般。

有人评价，哥德尔是和亚里士多德一样的伟大的逻辑学家之一。他曾在给计算机之父冯·诺依曼的一封信中，首次提到十分著名的P vs. NP问题。

想要获得哥德尔奖可不是件容易的事。

获奖论文必须在理论计算机领域具有开创性重大贡献，并且该论文必须在14年内在学术期刊上正式发表过。

再满足了上述要求之后，还要通过由6名评审组成的评选委员会的评审。而评委会的成员同样需要通过EATCS和ACM SIGACT的提名。

这样，才能确定出最终的获奖者。

而最终的颁奖典礼一般在当年的理论计算机会议STOC或是ICALP上一同举办。

参考资料：

https://zh.m.wikipedia.org/zh-hans/哥德尔奖

https://twitter.com/sigact/status/1528031898429030400?s=21&t=6mwK9uV7g6b4kESEGeqdIg

https://stevenyue.medium.com/fully-homomorphic-encryption-part-one-a-gentle-intro-94c3c3850568

https://zvikab.bitbucket.io/

,