2022年哥德尔奖颁给后量子密码方案
光子盒研究院出品
5月21日，国际计算机协会(ACM)算法与计算理论兴趣组(SIGACT)宣布，2022年哥德尔奖授予Craig Gentry、Zvika Brakerski和Vinod Vaikuntanathan，表彰其对密码学做出的变革性贡献。
哥德尔奖是理论计算机领域最负盛名的奖项。其名称是为了纪念逻辑学与计算机科学的先驱库尔特·哥德尔(Kurt Gödel)。哥德尔奖的获奖论文必须在理论计算机领域具有开创性重大贡献；同时须在获奖前14年内在学术期刊上正式发表。
2022年哥德尔奖授予以下两篇论文：
https://ieeexplore.ieee.org/document/6108154
https://dl.acm.org/doi/10.1145/2090236.2090262
上述论文通过构造高效的全同态加密(FHE)方案对密码学做出了变革性的贡献。
简单地说，支持对密文进行任意计算的密码系统称为全同态加密(FHE)。从定义上讲：
如果满足f(A)+f(B)=f(A+B)，我们将这种加密函数叫做加法同态；
如果满足f(A)×f(B)=f(A×B)，我们将这种加密函数叫做乘法同态。
如果一个加密函数f只满足加法同态，就只能进行加减法运算；
如果一个加密函数f只满足乘法同态，就只能进行乘除法运算;
如果一个加密函数同时满足加法同态和乘法同态，称为全同态加密。
在FHE方案中，数据加密与标准加密方案并没有区别。此外，FHE提供了对加密数据进行计算并生成加密结果的能力，而不需要解密或任何密钥。这种能力使我们能够安全地将昂贵的计算外包给不可信的服务器，并在多个实体之间安全地执行协作计算。
1978年，Rivest、Adleman和Dertouzos在工作中提出了全同态加密概念（称为“隐私同态”）。然而，在接下来的三十年中，构建一个能够对加密数据进行任意计算的FHE方案仍然是一个悬而未决的问题。第一个满足加法和乘法同态的同态加密方法直到2009年才由Craig Gentry提出。
2009年，Craig Gentry基于理想格的假设构造了第一个FHE方案。格(lattice)是一种数学结构，由被称为“格”的点组成的高维几何结构，随着维数的增加而越来越难解决。基于格的算法是目前用于开发抵抗量子计算攻击的后量子密码的主要候选方案。
这一开创性的贡献在效率和安全保障的性质方面都有很大的希望，但也有一些局限性。
2011年，Brakerski、Vaikuntanathan基于格的加密假设提出了一个新的FHE方案，该假设称为容错学习(LWE)。LWE的提出者Oded Regev获得了2018的哥德尔奖。由于LWE问题尚无有效的量子求解算法，因此基于LWE假设的加密方案被认为是抗量子的。
2012年，Brakerski、Gentry、Vaikuntanathan正式提出BGV FHE方案。该方案是一个分级方案，并且基于比2009年Gentry更好的格假设。通常，我们将BGV方案称为第二代FHE方案。
2013年，Gentry又与Sahai、Waters共同提出了第三代FHE方案——GSW方案。GSW方案仍然基于LWE格密码假设(但稍好)，并使用自举法使其成为真正的FHE方案(能够评估任意大小的函数F)。
哥德尔奖委员会表示，这些论文对理论和应用研究都产生了巨大的影响，从高级密码原语的构建，到FHE的实现，以及后量子加密候选的设计。
根据光子盒发布的《后量子密码——未来安全的风暴热点》报告，后量子密码(PQC)将逐步向全同态加密等更高级应用演变。“传统加密算法只能保护数据在存储和传输过程中的静态安全性。数据加密后，对密文能做的唯一有效操作是解密。同态加密允许在没有解密密钥的情况下对密文进行有意义的计算操作，最终输出加密的计算结果，整个计算过程不泄露原始数据和计算结果的任何有效信息。随着PQC技术不断发展，同态加密这种更高级的密码学应用有望逐步实现。”
获奖者简介：
Craig Gentry
今年5月，Craig Gentry成为TripleBlind首席技术官，TripleBlind是一家隐私增强计算解决方案提供商。Gentry从事密码学研究已有20多年，因为构造了第一个全同态加密系统荣获麦克阿瑟奖，并成为国际密码学研究协会会士。
在加入TripleBlind之前，Gentry是Algorand Foundation、IBM Research和DoCoMo USA Labs的研究科学家。他拥有博士学位。斯坦福大学计算机科学学士学位，哈佛法学院法学博士和杜克大学数学学士学位。
Zvika Brakerski
以色列魏茨曼科学研究所计算机科学和应用数学系副教授。目前主要从事密码学和量子计算方面的工作。特拉维夫大学工程学院和计算机科学学院双理学学士学位，特拉维夫大学工程学院的理学硕士学位，魏茨曼科学研究所博士学位(2011)。然后在斯坦福大学计算机科学系做了两年博士后研究员。
Vinod Vaikuntanathan
密码学家，麻省理工学院电子工程和计算机科学系(MITEECS)教授，Duality Technologies联合创始人。他是大多数现代全同态加密系统和许多其他基于格的(后量子安全)密码原语的共同发明人。印度理工学院理学学士学位，麻省理工学院硕士和博士学位。
2022年哥德尔奖名单：
https://sigact.org/prizes/g%C3%B6del/citation2022.html