格密码的量子危机？一文带你解析格密码学术风波
区块链的量子安全威胁以及应对2024年3月10日，以太坊联合创始人VitalikButerin在以太坊研究论坛（ethresear.ch）发布最新文章《Howtohard-forktosavemostuser'sfundsinaquantumemergency》[1]，文中表示：以太坊生态系统面临的量子计算攻击威胁，可以通过恢复性分叉策略和抗量子密码技术来保护用户资金安全。对于区块链来说，量子安全威胁到底是什么？量子计算[2]作为利用量子力学调控量子信息单元进行计算的新型计算模式，在20世纪80年
区块链的量子安全威胁以及应对
2024 年 3 月 10 日，以太坊联合创始人 Vitalik Buterin 在以太坊研究论坛（ethresear.ch）发布最新文章《How to hard-fork to save most user's funds in a quantum emergency》[1]，文中表示：以太坊生态系统面临的量子计算攻击威胁，可以通过恢复性分叉策略和抗量子密码技术来保护用户资金安全。
对于区块链来说，量子安全威胁到底是什么？
量子计算[2]作为利用量子力学调控量子信息单元进行计算的新型计算模式，在 20 世纪 80 年代被提出，在其概念提出后的十年内，量子计算机也只是停留在抽象理论阶段。直到 20 世纪 90 年代中期的两个量子算法：Shor 算法[3]（多项式时间内解决大数分解及离散对数困难问题）和Grover算法[4]（针对非结构化数据的穷举搜索问题提供平方加速）的提出，使得量子计算跳出抽象理论阶段，转而进入到物理载体研发的新阶段，也就是目前所说的量子计算机。下图展示了从 1998 年到 2026 年量子计算机的物理量子比特发展路线图：
量子计算不是万能的，它并非能解决所有计算问题。目前可在模拟（模拟自然界发生的过程，适用于化学与生物工程）、破译（打破大部分传统密码体系，适用于网络安全）、优化（寻找可行选项中的最优解，适用于金融、供应链）等特定领域问题上发挥其计算优越性。
区块链目前得到广泛应用来自于它给不同诉求方间的协作带来新的信任基础，而这种信任基础建立在底层密码学所提供的安全性保障之上：
可信身份与交易确权：基于非对称公私钥对建立用户可信身份，统一管理身份信息。通过数字签名实现数字资产的确权，有效签名的私钥持有者实际拥有资产所有权。
核心共识和运行安全：基于哈希函数、门限签名、可验证随机函数等现代密码技术构建共识机制，保障共识机制使用安全。
隐私保护与安全共享：基于零知识证明、安全多方计算、全同态等富功能密码技术构建隐私保护方案，实现区块链上数据的安全共享。
可控监管与合规应用：集成部署环签名、同态密码方案、隐地址和秘密共享等密码技术，确保区块链交易的安全监管。
这其中涉及到公钥密码的用法可粗略分为：链上交易防篡改使用的数字签名机制，以及节点间通信使用的安全传输协议。受 Shor 算法的影响，上述公钥密码在使用上的安全性无法得到有效保障。在考虑专用密码破译量子计算机大规模应用所需时间的同时，还需考虑存储在区块链上的数据需要保存多长时间以及现有区块链系统升级到量子安全级别的时间。如果后两者相加的时间和大于前者，那么区块链上的数据就会受到量子计算带来的严重安全威胁。
考虑到量子计算飞速发展带来的算力不断提升的现状，目前可以有效应对安全风险的主要有两种技术途径：
不借助物理设备的基于新型数学难题的后量子密码[5]技术路线；
借助专用物理设备的基于物理原理的量子密码[6]技术路线。
综合考虑落地实施验证等多种因素，为确保区块链长期演进下的安全性保证，在兼容现有密码安全的前提下，可考虑通过后量子密码迁移将区块链提前部署升级到量子安全级别。理想情况下，将现有区块链使用的公钥密码算法升级为量子安全的后量子密码算法，应尽可能满足以下特点：
密钥小且签名短：区块链上的每笔交易都会包含签名信息，而验证任意一笔交易的公钥也存储在链上。若密钥以及签名尺寸过大，都将大大加剧区块链的存储成本以及通信开销；
计算效率高：区块链运行时每一时间段可处理的交易数量很大程度上与算法的运行时间有关，特别是签名验签算法。算法更快的计算效率可以更好地支持高性能的区块链应用。
后量子密码发展现状
后量子密码，一句话概括就是能够抵抗量子计算机对现有密码算法攻击的第一代密码算法：
面向公钥密码体系；
依赖新型数学问题；
不需要专用设备支持；
经典计算以及量子计算条件下安全；
目前主流的构造技术路线有五种，如下图所示，从左到右分别是格、编码、多变量、哈希以及同源：
格：基于格上的困难问题。
编码：基于解码的困难性。
多变量：基于有限域上多元二次多项式组的难解性。
哈希：基于哈希函数的抗碰撞性。
同源：基于超奇异椭圆曲线的伪随机游走。
新一代密码算法然会涉及到标准密码体系的建立。关于后量子密码标准最值得关注的则是：美国国家标准技术研究所（NTST）的后量子密码标准化项目[7]，从 2016 年启动到现在已基本进入后量子密码标准化制定的尾声。回顾这接近十年的标准化时间线，NIST 在：
2022 年 7 月 5 日，正式官宣四个后量子密码标准候选算法[8]：
公钥加密/密钥封装：CRYSTALS-KYBER；
数字签名：CRYSTALS-Dilithium、FALCON；SPHINCS+；
这其中，CRYSTALS-KYBER、CRYSTALS-Dilithium、FALCON 均为格密码算法，但三者的安全性基础有所区别，KYBER 基于模格的 MLWE 困难问题，Dilithium 基于模格的 MLWE 和 MSIS 困难问题，FALCON 则基于 NTRU 格的 SIS 困难问题；除此之外，SPHINCS+ 是无状态哈希签名算法。
2023 年 8 月 24 日，已将 CRYSTALS-KYBER、CRYSTALS-Dilithium、SPHINCS+分别形成FIPS203、FIPS 204、FIPS205 标准草案 [9]，FALCON 标准草案也将在 2024 年公布。
不难看出目前 NIST 选择的标准算法大多基于格密码的技术路线。但是 NIST 并没有把鸡蛋放在同一个篮子中，他们也在积极需要除了格构造以外的多种选择：2022 年公布四个标准算法的同时，也宣布启动了第四轮后量子密码标准算评估工作，这一轮则关注于公钥加密/密钥封装算法，入选的算法并没有基于格构造。此外，还发起新一轮数字签名算法的征集，此轮征集独立于第四轮评估独立进行，旨在丰富后量子签名算法组合，所以更关注于算法构造上不同与现有的基于结构格，且算法签名尺寸小、验证速度快的新提案。
除了 NIST 标准外，国际互联网标准化组织 IETF 在 2018 年和 2019 年分别标准化有状态哈希签名算法 XMSS 为 RFC 8391[10]、LMS 为 RFC 8554[11] 且被 NIST 接受。
破解格密码的量子算法
2024 年 4 月 10 日，陈一镭老师在 eprint 上的文章《Quantum Algorithms for Lattice Problems》[12] 引起了学术界的轰动。论文中给出了一种多项式时间求解格上困难问题的量子算法，该算法对很多基于格困难问题的密码方案有着较大冲击，可导致很多算法不再具备抗量子计算机攻击的能力，例如，目前广泛使用的基于 LWE 假设的同态加密算法。论文中算法的正确性暂未可知。
LWE 问题的困难性由 Oded Regev 在论文《On lattices, learning with errors, random linear codes, and cryptography》[13]中给出了严格的论证，具体地说，作者在论文中将 LWE 问题的困难性归约到格上的离散高斯采样问题，而离散高斯采样问题可以很容易归约到 GapSVP, SIVP 等经典问题（当然，每个具体问题都是有其具体参数的，这里忽略），这说明 LWE 问题要比这些经典的格问题还要困难。在 LWE 问题的困难性有了严格的归约后，由于其结构简单，一大批基于 LWE 的密码方案也随之而来，涵盖（同态）加密，签名，密钥交换等基础密码原语，以及基于身份加密，属性加密等高级密码原语等。其中，在业界使用较多的主要集中在全同态加密和上面所提到的 NIST 公布的后量子标准算法（KYBER， Dilithium等）。
总结
该论文公开后，对学术界造成了很大的轰动，引起很多专业人士的讨论。但由于论文的理解难度极大，全世界可能也就不到 5 位学者可以完全理解论文的内容，可能需要 1-2 年的时间才能完全验证论文的正确性。目前一些论坛、公众号、知乎等平台也有很多人发表了一些相关见解，大家都是在分析如果论文中的算法是正确的，会带来哪些影响，至于论文算法的正确性问题，还没人能下定结论。其中，著名密码学家 N. P. Smart 发表了博客文章《Implications of the Proposed Quantum Attack on LWE》[14]，详细介绍了此攻击的影响和一些观点，总结如下：
这篇论文目前尚未经过同行评审，即使被验证是正确的，也要依赖于量子计算机，因此只要量子计算机还未问世，对目前在使用的密码方案均无影响。
按照论文中给出的结果：仍无法攻破此前 NIST 给出的标准化算法 Kyber, Dilithium，但 NIST 可能会重新评估这些算法的参数。
对于常用的 RLWE 同态加密算法，如 BFV/CKKS/BGV，这些算法是在这篇论文的攻击能力之内的。不过，不管从是学术界还是工业界的视角，同态加密技术的“同态性”比其“抗量子性”更具吸引力，很少人会为追求“抗量子性”而使用 RLWE 同态加密算法，就像基于椭圆曲线的密码方案依赖于离散对数困难问题，而求解该问题的量子算法很早就被提出了，但学术界，工业界仍然在研究、使用这些方案。
最新消息：陈老师论文计算存在问题，格密码警报暂时解除。
[1] https://ethresear.ch/t/how-to-hard-fork-to-save-most-users-funds-in-a-quantum-emergency/18901/9
[2] Benioff P. The computer as a physical system: A microscopic quantum mechanical Hamiltonian model of computers as represented by Turing machines[J]. Journal of statistical physics, 1980, 22: 563-591.
[3] Shor P W. Algorithms for quantum computation: discrete logarithms and factoring[C]//Proceedings 35th annual symposium on foundations of computer science. Ieee, 1994: 124-134.
[4] Grover L K. A fast quantum mechanical algorithm for database search[C]//Proceedings of the twenty-eighth annual ACM symposium on Theory of computing. 1996: 212-219.
[5] Bernstein, D.J. (2009). Introduction to post-quantum cryptography. In: Bernstein, D.J., Buchmann, J., Dahmen, E. (eds) Post-Quantum Cryptography. Springer, Berlin, Heidelberg.
[6] Gisin N, Ribordy G, Tittel W, et al. Quantum cryptography[J]. Reviews of modern physics, 2002, 74(1): 145.
[7]https://csrc.nist.gov/Projects/post-quantum-cryptography/post-quantum-cryptography-standardization
[8]https://csrc.nist.gov/News/2022/pqc-candidates-to-be-standardized-and-round-4
[9]https://csrc.nist.gov/News/2023/three-draft-fips-for-post-quantum-cryptography
[10] Huelsing, A., Butin, D., Gazdag, S., Rijneveld, J., and A. Mohaisen, "XMSS: eXtended Merkle Signature Scheme", RFC 8391, DOI 10.17487/RFC8391, May 2018, <https://www.rfc-editor.org/info/rfc8391>.
[11] McGrew, D., Curcio, M., and S. Fluhrer, "Leighton-Micali Hash-Based Signatures", RFC 8554, DOI 10.17487/RFC8554, April 2019, <https://www.rfc-editor.org/info/rfc8554>.
[12] Chen Y. Quantum Algorithms for Lattice Problems[J]. Cryptology ePrint Archive, 2024.
[13] Regev O. On lattices, learning with errors, random linear codes, and cryptography[J]. Journal of the ACM (JACM), 2009, 56(6): 1-40.
[14]https://nigelsmart.github.io/LWE.html
本文由 ZAN Team（X 账号 @zan_team）的 Dongni 和 Jiaxing 共同撰写。
Postman是一套面向API全生命周期的开发与测试平台，可在Mac上发送和调试多种协议请求，管理集合、环境及认证信息，并完成脚本测试、模拟服务、监控、文档发布和团队协作。它适合开发、测试及运维人员使用，提供个人免费方案。
Docker Desktop 是 Docker 官方为 Mac 提供的容器开发环境，集成 Docker Engine、命令行工具、Compose、Build、Kubernetes 与图形化管理界面。
Android Studio 是 Google 面向安卓应用开发提供的官方集成开发环境，基于 IntelliJ IDEA 构建。它整合智能代码编辑、Gradle 构建、界面预览、设备模拟、性能分析、调试测试及 APK 分析等工具。
Xcode 是苹果面向 Mac 提供的官方集成开发环境，将代码编辑、项目构建、SwiftUI 实时预览、设备模拟、自动化测试、断点调试、性能分析和应用分发整合在同一套工作流中，适合开发与维护 iPhone、iPad、Mac、Apple Wa
JetBrains WebStorm 是面向 JavaScript、TypeScript 和现代 Web 技术的专业集成开发环境，可智能理解项目结构，提供代码补全、重构、错误检查、运行调试、测试及 Git 工具。
PhpStorm 是 JetBrains 推出的专业 PHP 集成开发环境，可在 Mac 上完成代码编写、智能检查、重构、调试、测试和数据库管理。它支持主流 PHP 框架、Composer、Git、Docker 与远程解释器。
JetBrains PyCharm 是面向 Python 开发者的集成开发环境，提供智能补全、代码检查、重构、调试、测试、版本控制及虚拟环境管理功能。Mac 版兼容 Intel 与 Apple 芯片，核心功能可免费使用。
IntelliJ IDEA 是 JetBrains 推出的专业集成开发环境，重点服务于 Java、Kotlin 与 JVM 项目开发。软件集成代码补全、静态检查、重构、调试、测试、版本控制及构建工具，并可借助插件扩展语言和框架支持。
Visual Studio Code 是微软提供的免费代码编辑器，支持 macOS，并为 Intel 与 Apple 芯片 Mac 提供适配版本。软件集代码编辑、调试、Git 源代码管理、集成终端和扩展市场于一体。
REAPER是Cockos开发的数字音频工作站，提供多轨音频与MIDI录制、剪辑、处理、混音和母带制作工具。Mac版兼容Intel与Apple芯片，支持AU、VST、VST3、CLAP等插件格式，并提供高度可定制的工作流程。
Adobe Audition 是面向播客、影视后期、音乐制作及内容创作者的专业音频工作站，提供波形精修、多轨录制与混音、频谱编辑、降噪修复、响度匹配和效果处理工具，并可与 Adobe Premiere 协同完成视频声音制作。
Pro Tools 是 Avid 推出的专业数字音频工作站，覆盖多轨录音、无损剪辑、MIDI 编曲、插件处理、自动化混音及声音与画面同步等工作。它拥有 Intro、Artist、Studio 和 Ultimate 等方案。
PixPix 是面向品牌、卖家和内容团队的在线 AI 图片视频创作平台，提供图视频 Agent、无限画布、图片生成、视频生成、自然语言编辑及商品套图、产品精修和带货视频等电商工具。
Postman 是面向 API 全生命周期的开发与协作平台。Windows 桌面版可用于构建和发送 HTTP、GraphQL、gRPC、WebSocket、MQTT 等请求，并提供环境变量、集合、脚本测试、模拟服务、监控、文档及团队工作区等
Docker Desktop 为 Windows 开发者提供集成式容器环境，内置 Docker Engine、命令行工具、Compose、Build 与 Kubernetes 等组件，可在本机完成镜像构建、容器运行、日志查看和资源管理。
Android Studio 是 Google 面向 Android 应用开发提供的官方集成开发环境，以 IntelliJ IDEA 为基础，集成智能代码编辑、Gradle 构建、设备模拟、界面预览、调试测试及性能分析工具，
WebStorm 是 JetBrains 面向 JavaScript、TypeScript 和现代 Web 技术打造的集成开发环境。它提供项目级代码分析、智能补全、安全重构、导航搜索，并集成调试、测试、终端、Git 与常用前端工具，
PhpStorm 是 JetBrains 面向 PHP 与现代 Web 开发打造的专业集成开发环境，提供代码补全、静态检查、重构、调试、测试、数据库、版本控制及前端语言支持。Windows 用户可直接下载安装程序，
PyCharm 是 JetBrains 推出的 Python 集成开发环境，提供智能代码补全、错误检查、重构、调试、测试、Git、终端及 Jupyter Notebook 支持。统一版安装后可体验 30 天 Pro 功能，
JetBrains IntelliJ IDEA 是以 Java、Kotlin 和 JVM 项目为核心的专业集成开发环境，提供智能补全、代码检查、安全重构、调试、测试、版本控制及构建工具集成。统一发行版的核心功能可免费用于商业和非商业项目，
Visual Studio Code 是微软推出的免费代码编辑器，Windows 版集成智能补全、代码导航、调试、终端和版本控制，并可通过扩展添加语言、格式化及远程开发能力。它启动较快、配置灵活，
REAPER 是 Cockos 推出的数字音频工作站，适用于录音、MIDI 编曲、音频编辑、混音、母带制作及声音设计。软件安装包小巧，支持多轨录制、灵活路由、自动化、第三方插件和脚本扩展，并提供完整功能的 60 天免费评估期。
Adobe Audition 是面向播客、影视后期、广播与音乐制作的专业音频工作站，提供波形编辑、多轨混音、频谱分析、录音、降噪修复和效果处理等功能。Windows 版通过 Adobe Creative Cloud 安装和管理，
Pro Tools 是 Avid 推出的专业数字音频工作站，提供多轨录音、音频剪辑、MIDI编曲、插件处理、自动化混音及影视声音制作能力。它适合音乐人、录音师、制作人和音频后期团队使用，并提供免费入门版、订阅方案及永久授权选择。