清华团队要赶在量子计算机正式应用前,提前布局芯片!中国大陆首篇后量子密码芯片顶会论文出炉

科学
清华团队要赶在量子计算机正式应用前,提前布局芯片!中国大陆首篇后量子密码芯片顶会论文出炉
麻省理工科技评论 2020-10-02

2020-10-02

该论文介绍了一种低计算复杂度数论变换与逆变换方法,并提出一种实现后量子密码算法的硬件架构。
科学
该论文介绍了一种低计算复杂度数论变换与逆变换方法,并提出一种实现后量子密码算法的硬件架构。

近日,在第 22 届密码硬件与嵌入式系统会议(CHES 2020)上,清华大学魏少军、刘雷波教授团队作了题为 “《采用低复杂度快速数论变换和逆变换技术在 FPGA 上高效实现 NewHope-NIST 算法的硬件架构》(Highly Efficient Architecture of NewHope-NIST on FPGA using Low-Complexity NTT/INTT)” 的论文报告。

清华团队要赶在量子计算机正式应用前,提前布局芯片

图 | 论文一作张能同学在作报告(来源:受访者)

CHES 成立至今已有 22 年,由国际密码学研究协会(IACR)主办,据刘雷波介绍,这篇论文是中国大陆首次以第一作者身份在该会议上发表的后量子密码芯片方向文章。

报告人张能是论文第一作者,目前正在清华大学微电子所攻读博士学位,论文通讯作者是清华大学微电子与纳电子学系/微电子学研究所教授刘雷波,主要合作者还有杨博翰、陈晨、尹首一。

DeepTech 就该论文和刘雷波进行了深入交流。他表示,该论文介绍了一种低计算复杂度数论变换与逆变换方法,并提出一种实现后量子密码算法的硬件架构。

当前,公钥密码已经广为使用,无论去线下银行、还是在网上银行办业务,都要证明个人身份以避免被人冒用,访问电商网站或使用手机支付时,其数据也需加密。

除民用用途之外,公钥密码算法在海陆空通信方面也有着特定用途,设备间的通信都需要数据加密和身份验证。比如,对面过来一架飞机,远处看到一艘船,往往需要判断对方到底是友是敌,这时也需要用公钥密码算法来保护传输数据。

随着量子计算能力的提高,目前已经从数学上证明,经典公钥密码算法肯定会被量子计算机所攻破。当前,整个互联网系统安全和网络安全,都会用到密码技术,而目前最不可被取代的正是公钥密码模块。

公钥密码算法一旦被量子计算机攻破,整个互联网将“轰然倒塌”,那时我们将没法去银行,也没法用电,甚至没法坐飞机和高铁。整个互联网系统会因为失去安全而瘫痪,各种网络攻击事件将不断出现。

可以说,全人类都面临着量子攻击的风险。因此,学术界正在研究能替换经典公钥密码算法的算法,即后量子密码算法,以有效应对量子计算机技术进步带来的严峻挑战。

能有效抵御量子计算机攻击的密码算法,统称为后量子密码 (Post-Quantum Cryptography) 或抗量子攻击密码 (Quantum-Resistant Cryptography)。后量子 ,主要是指针对量子计算机时代的安全威胁,所发展出的密码算法体系。

后量子密码算法分五大类:第一类是基于格的,第二类是基于编码的,第三类是基于多变量的,第四类是基于哈希的,第五类是基于超奇异同源的。

其中,第一类基于格的后量子密码算法由于其计算的相对高效性和通用性,成为最主流的候选算法种类。

后量子密码算法的设计是一个数学问题,数学家们已经证明它是可以抵御量子计算攻击的算法,但算法如何被应用到电子设备和系统中去,仍需进一步研究。

算法的最终载体是芯片,魏少军、刘雷波团队在本次研究中,把后量子密码算法高效地实现在 FPGA 芯片上。之所以开展这样的研究工作,是因为如果要做到用能抵御量子计算机攻击的后量子密码算法来替代经典公钥密码算法、以及实现广泛应用,就必须研究后量子密码算法如何在芯片上进行高效实现的方法。

业界的一些产业巨头已经在后量子密码算法的应用方面进行了一些探索。谷歌于 2016 年在其实验版浏览器中实现了后量子密钥交换算法 NewHope,虽然可以证明其对量子攻击防护的一定有效性,但其执行效率限制了其进一步推广应用。

微软研究院已推出后量子密码算法 Picnic 算法和后量子 VPN 算法,亚马逊公司目前也在其 AWS 密钥管理系统中的传输层安全(Transport layer security, TLS)网络加密协议中提供后量子密钥交换支持。

后量子密码算法的应用难题在于,一方面需从数学上证明它能够抵御量子攻击中的 Shor 和 Grover 算法;另一方面,需证明后量子密码算法能否在芯片上运行。

如果无法在上芯片运行、或者运行非常慢,那就无法投入实际应用。例如,当访问网络时,需要很长时间才能算出结果,那就没有任何意义。因此,后量子密码算法需同时满足在数学和芯片层面均可行。

目前,全球尚未就后量子密码算法形成统一的标准。美国国家标准与技术研究院(National Institute of Standards and Technology,下称 NIST)正在开展后量子密码算法的标准化工作,目前已经推进到第三轮。

对于征集到的每个候选算法,NIST 及密码领域的研究人员都会对其进行安全评估、数学评估、以及实现性能评估(包括软件实现和硬件实现)。最终通过评估的算法,将会成为 NIST 的推荐标准。

除 NIST 以外,欧盟的欧洲电信标准化协会、美国 IEEE 和中国的相关机构也在征集算法。但 NIST 的后量子标准化是影响力最大,同时进展最快的,其从第一轮征集到的 69 个候选算法,到目前第三轮仅剩下 15 个算法,预计至 2021 年底还会淘汰大半,仅选出不到五个算法,直到最后沉淀出的算法成为 NIST 推荐的国际标准。

由于后量子密码算法要抵抗未来的量子攻击和当前的经典计算攻击,因此需考虑未来数年计算机的发展。更重要的是,后量子密码算法的布局一定要先于量子计算机进入应用。

同时,公钥密码的应用广泛,不计其数的软硬件主体和企业都在使用公钥密码,替换它们将是一个超大系统工程,需提前三至五年布局。

算法站得住,芯片也需要站得住

刘雷波表示,后量子密码算法能否用起来,至少取决于两个因素:第一,算法站得住,即算法本身能否抵御后量子攻击和经典性攻击;第二,芯片站得住,有了算法还得有物质载体来高效运行和快速执行这些算法。

刘雷波的专业背景是微纳电子学与数字集成电路设计,其研究工作主要是针对算法中的计算、存储等瓶颈问题进行改进,进一步实现算法和硬件的协同设计,并最终完成相应的芯片实现。

当前后量子密码算法尚未站住。美国 NIST 第三轮候选算法中,还包括不同种类的 7 个算法需要进行进一步的安全、计算效率及硬件性能评估。

后量子密码芯片设计的现状是在低开销、高性能等设计目标驱动下,完成相应算法的计算架构设计,并在 FPGA(Field Programmable Gate Array)平台上完成功能验证和性能评估。

FPGA 实现的优点在于可以在避免高昂芯片流片成本的前提下,完成特定芯片的功能验证和应用评估。在产业需求成熟及算法最终收敛时,可以实现相应芯片的快速产业化。

那么,是否能直接采用现有芯片(如 CPU、FPGA 及 DSP 等)实现后量子密码算法呢?现有芯片在执行后量子算法时效率非常低,远不能满足应用需求。因此,只有针对后量子密码算法完成领域定制的专用芯片,才能最大化地满足应用需求。

在很多特定场合中,如物联网终端需要面积特别小、功耗特别低的芯片。此时就更需要专门为算法去定制专用芯片,从而实现高性能、低开销和低功耗的设计目标。

比同类研究平均速度快 2.5 倍左右

在算法的硬件设计过程中,仍然需要在算法及计算架构层面,解决一系列的硬件问题,如怎样存储中间数据、怎么有效降低计算复杂度、怎样降低功耗等。

为解决上述问题,魏少军、刘雷波团队提出一种低计算复杂度的快速数论转换与逆变换方法,并首先在算法的软件实现 (C 语言)上进行改进并显著降低了算法的运算量,该方法的好处是独立于特定的芯片架构设计,具有普适的通用性。

基于该方法,高效执行的硬件架构可以进一步挖掘和发挥方法的有效性。研究团队设计了一款后量子密码硬件架构,进一步降低了基于格的后量子密码算法计算复杂度的同时,显著减少了硬件资源开销。

刘雷波坦言,由于目前尚无国际标准,因此厂商不愿投资芯片流片,不过业界对后量子密码算法的标准化工作保持着持续关注。

几年前,阿里云已有在云计算上部署后量子密码算法的意向,虽然距最终部署仍有一段距离,但已有企业开始重点关注这个方向并开始有所布局。

按照国际惯例,在后量子密码算法标准出台后的一年之内,芯片可完成研发并进行部署。现在,该团队正从两方面着手,一方面是跟国际顶尖算法团队开展合作。在算法开发及评估阶段就参与到算法硬件实现性能评估工作中,并致力于共同发现与解决芯片实现过程中的瓶颈问题。

另一方面,该团队跟国家密码管理局保持着密切联系,国家密码管理局也在征集后量子密码算法,且就此和中国科学院信息工程技术研究所开展合作。届时,该团队也将负责对此过程中后量子密码算法的硬件评估.

为进一步评估研究成果的先进性,魏少军、刘雷波团队跟麻省理工学院、德国慕尼黑工业大学、比利时鲁汶大学、纽约大学及英国布里斯托大学等团队的相关研究进行了对比,结果表明计算速度上平均快 2.5 倍以上,面积效率提高近 5 倍以上。

清华团队要赶在量子计算机正式应用前,提前布局芯片

图 | 和世界其他高校相关研究的对比

量子攻击迫在眉睫

当前,全球都处于后量子密码算法标准未定、后量子密码芯片架构设计空白的局面。假如某个算法通过 NIST 的完整评估并最终成为国际标准,将是一件能带来巨大学术荣誉和学术影响力的事情。

刘雷波认为,在此情况下我国必须拥有自己的算法标准和相应的后量子密码芯片。这也是本篇论文的重要意义所在,为密码学领域作出学术创新贡献的同时,也能提高中国的学术影响力,更重要的是能解决中国的实际问题。

目前,该团队正在利用其在芯片计算架构方面多年的技术积累和学术成果,为国家的相关算法做性能测试,并为未来的技术推广提前做技术储备。以便在算法标准、测试方法和论证方法最终确定时快速响应,实现具有抗量子攻击能力的后量子公钥密码体系切换。

刘雷波表示,技术不用就等于 0,论文的研究成果也是为了促进国家后量子密码芯片体系的建立,只有这样才能解决产业发展的关键难题,当然这其中需要政府机构、学校和企业的多方联动。

他告诉 DeepTech,量子攻击迫在眉睫,假设量子计算机十年后正式投入使用,即便从现在开始做算法开发、芯片设计及产业培育,时间都未必够用。

团队希望在这方面能够为我国在相关关键技术的突破做出一点贡献。在此过程中,产出了一篇在国际顶级会议 CHES 发表的论文。

虽然本次发布的仅仅是一篇论文,但本质是为实现对量子攻击有效防御的后量子密码芯片技术攻关,最终目的是让中国网络基础设施在技术进步过程当中不至于崩溃。

该团队所做的后量子密码芯片设计,目前国内从事相关研究的高校、机构等不超过五家。四年前立项时,他之所以选择该方向,首先是因为潜在需求大,同时技术难度,国内研究力量不足。国内科研院所和大型央企在后量子密码芯片方面的研究特别少,但是不能等到别人来卡脖子时再做。

而该团队从四年前,就开始着手这方面研究。之所以有这样的前瞻性,是因为该团队不仅专注于密码芯片技术,同时还深入开展通信、人工智能等相关领域的芯片设计及核心计算架构研究。

该团队的学术研究方向选择遵循两大原则:第一是不做主流,但也不偏离主流。当前的中国安全技术主流之一是网络安全和软件安全,这已经有大批人员在做。同样做安全,该团队关注的是芯片安全,即从芯片层面解决问题。这虽然不是主流,但是主流的核心基础。

第二个学术原则是,在学生做课题设计时就要考虑长远。比如,一个直博生大概需要五、六年才能毕业,因此刘雷波在指导博士生进行选题时在考虑学术价值、技术难度的同时,会努力让其研究在毕业后成为业界有竞争力的技术。

除后量子密码芯片之外,刘雷波也开展了其他密码芯片的研究和设计,并已经孵化出两家从事安全相关产业的创业公司。

其中一家注册在无锡的公司沐创集成电路设计有限公司,主要致力于向业界提供支持经典密码算法的芯片及系统服务。在该方面的研究最早可追溯到 2012 年,目前估值达五亿元。

他认为,密码芯片产业化对于工业界来说门槛太高,小公司想的是今年研发,明年就要挣钱;中等企业想的是今年研发,三到四年就要挣钱;大公司想的是今年研发,五到六年左右一定要挣钱。不挣钱就不行,这就是中国产业的现状。

那么,八到十年、十到十五年才能挣钱的技术谁来做?举个例子,现在应用在英特尔可穿戴芯片中的可重构计算技术(Reconfigurable Computing Technology),是其从十几年前就开始研发的。

刘雷波认为,企业今天不创新,明天就会死掉。谷歌等大公司的技术都是十多年前布局的。但在中国,包括华为在内的企业也达不到这一点,因为现在做的技术研发,五六年以后不挣钱企业就会死掉。

而学校主要做关键技术突破,并非以盈利为目的,为的是解决科学问题,因此能在国家项目支持下布局到十年以后。当工业界需要该技术时,公司就能实现盈利。所以,只有产学研结合起来,才能提前布局关键技术。

*清华邓辰辰博士、朱文平博士对本文亦有贡献。

麻省理工科技评论

From Tech to Deeptech