展开菜单
首页 精品内容 本月促销 装机必备 Windows PDF教程 macOS软件 IOS软件 Android AI 专题
全部分类

当前位置:

首页 > 业界资讯 > 格密码的量子危机?一文带你解析格密码学术风波

格密码的量子危机?一文带你解析格密码学术风波

区块链的量子安全威胁以及应对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 算法的影响,上述公钥密码在使用上的安全性无法得到有效保障。在考虑专用密码破译量子计算机大规模应用所需时间的同时,还需考虑存储在区块链上的数据需要保存多长时间以及现有区块链系统升级到量子安全级别的时间。如果后两者相加的时间和大于前者,那么区块链上的数据就会受到量子计算带来的严重安全威胁。

    考虑到量子计算飞速发展带来的算力不断提升的现状,目前可以有效应对安全风险的主要有两种技术途径:

    1. 不借助物理设备的基于新型数学难题的后量子密码[5]技术路线;

    2. 借助专用物理设备的基于物理原理的量子密码[6]技术路线。

    综合考虑落地实施验证等多种因素,为确保区块链长期演进下的安全性保证,在兼容现有密码安全的前提下,可考虑通过后量子密码迁移将区块链提前部署升级到量子安全级别。理想情况下,将现有区块链使用的公钥密码算法升级为量子安全的后量子密码算法,应尽可能满足以下特点:

    • 密钥小且签名短:区块链上的每笔交易都会包含签名信息,而验证任意一笔交易的公钥也存储在链上。若密钥以及签名尺寸过大,都将大大加剧区块链的存储成本以及通信开销;

    • 计算效率高:区块链运行时每一时间段可处理的交易数量很大程度上与算法的运行时间有关,特别是签名验签算法。算法更快的计算效率可以更好地支持高性能的区块链应用。

     

    后量子密码发展现状

    后量子密码,一句话概括就是能够抵抗量子计算机对现有密码算法攻击的第一代密码算法:

    • 面向公钥密码体系;

    • 依赖新型数学问题;

    • 不需要专用设备支持;

    • 经典计算以及量子计算条件下安全;

    目前主流的构造技术路线有五种,如下图所示,从左到右分别是格、编码、多变量、哈希以及同源:

    格密码的量子危机?一文带你解析格密码学术风波

    1. 格:基于格上的困难问题。

    2. 编码:基于解码的困难性。

    3. 多变量:基于有限域上多元二次多项式组的难解性。

    4. 哈希:基于哈希函数的抗碰撞性。

    5. 同源:基于超奇异椭圆曲线的伪随机游走。

    新一代密码算法然会涉及到标准密码体系的建立。关于后量子密码标准最值得关注的则是:美国国家标准技术研究所(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 共同撰写。

    本站声明:本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系bd@zhengruan.com
    作者最新文章
    业界资讯
    相关文章 更多
    精品专题 更多
    装机必备

    正软商城装机必备专区,精选办公、浏览器、安全防护、影音播放、压缩解压、设计创作和系统工具等电脑常用正版软件,帮助用户快速完成新电脑软件配置。

    Windows

    正软商城Windows软件专区,汇集适用于Windows电脑的办公、设计、安全防护、影音播放、开发工具和系统优化软件,提供软件介绍、系统要求、正版授权及购买下载服务。

    PDF教程

    正软商城PDF教程频道提供PDF编辑、转换、合并、拆分、压缩及格式处理方法,同时介绍常用PDF软件和工具的使用技巧。

    macOS软件

    正软商城macOS软件专区,精选适用于Mac电脑的办公、设计、影音、效率、开发和系统工具,提供软件功能介绍、macOS兼容版本、正版授权及购买下载服务。

    IOS软件

    正软商城iOS软件专区,精选适用于iPhone和iPad的办公、学习、影音、设计、效率及AI应用,提供功能介绍、适用设备、系统要求和正版获取方式等信息。

    AI

    正软商城AI软件专区,汇集AI写作、AI绘画、AI视频、AI办公、AI编程、AI翻译、智能客服和数据分析等人工智能工具,提供功能介绍、适用平台、收费方式及正版购买信息。

    Mac软件 更多
    讯飞智作 网页版
    讯飞智作 网页版

    讯飞智作是一款基于语音合成技术、虚拟人驱动技术与数字人形象声音构建能力的 AI 数字人音视频创作平台。

    火山引擎 网页版
    火山引擎 网页版

    火山引擎是字节跳动旗下企业级云与AI服务平台。聚焦大模型核心能力,依托字节自研豆包多模态大模型,凭借火山方舟一站式平台,提供模型精调、推理部署、智能应用搭建等全链路服务,结合高性能AI算力,助力各行业快速落地大模型数字化与智能化应用。

    Aperty macOS版
    Aperty macOS版

    Aperty 是 Skylum 推出的 AI 人像修图软件,支持自然肤质修饰、瑕疵处理、面部与身体调整、预设及批量同步。

    立刻MV 网页版
    立刻MV 网页版

    立刻MV 面向音乐人、内容创作者和品牌团队,帮助用户低成本完成歌曲 MV、歌词视频、AI 分镜、图生视频与最终合成。

    蛙蛙写作 网页版
    蛙蛙写作 网页版

    蛙蛙写作 AI 创作工具,覆盖小说、剧本、文案,一键生成文稿,打通文字转视频全流程,高效解决创作难题。

    超级简历WonderCV 网页版
    超级简历WonderCV 网页版

    超级简历WonderCV是面向应届生和AI小白的智能求职平台,覆盖简历、面试与职业规划。

    音述AI 网页版
    音述AI 网页版

    音述AI,是一个以“用声音述说故事”为核心的 AI 音乐创作与声音分享社区。

    AionClaw macOS版
    AionClaw macOS版

    AionClaw 是可在桌面端运行的任务型 AI 助手,通过数字专家与技能市场组合办公、创作、数据和开发能力。

    Loomy macOS版
    Loomy macOS版

    Loomy 是科大讯飞推出的桌面 AI 助手,可通过对话、任务与工作目录协助处理办公、内容创作和资料整理。

    AirBuddy 3 macOS版
    AirBuddy 3 macOS版

    AirBuddy 3 是面向 macOS 的蓝牙外设增强工具,可集中查看 AirPods、Beats 与苹果设备电量,提供快速连接、播放控制、电量提醒、桌面小组件和多台 Mac 外设接力等功能。

    AirServer macOS版
    AirServer macOS版

    AirServer macOS版可把 Mac 转换为无线投屏接收端,通过 AirPlay 或 Google Cast 接收手机、平板和电脑画面,并支持多设备同时连接、高清镜像及会话录制,适合家庭娱乐、课堂教学、会议演示和应用展示。

    AnyDesk macOS版
    AnyDesk macOS版

    AnyDesk macOS版是一款适用于远程办公、设备维护和客户支持的远程桌面工具,可连接并操作异地计算机,支持文件传输、无人值守访问、会话权限控制及跨平台协作。

    WINDOWS 更多
    讯飞智作 网页版
    讯飞智作 网页版

    讯飞智作是一款基于语音合成技术、虚拟人驱动技术与数字人形象声音构建能力的 AI 数字人音视频创作平台。

    火山引擎 网页版
    火山引擎 网页版

    火山引擎是字节跳动旗下企业级云与AI服务平台。聚焦大模型核心能力,依托字节自研豆包多模态大模型,凭借火山方舟一站式平台,提供模型精调、推理部署、智能应用搭建等全链路服务,结合高性能AI算力,助力各行业快速落地大模型数字化与智能化应用。

    PixTV 网页版
    PixTV 网页版

    PixTV 是一款在浏览器中使用的 AI 视觉内容创作平台,提供图片、视频、音频、文字生成、AI 分镜、局部重绘、提示词反推和无限画布等工具,适合短剧、漫剧、广告及社交媒体内容制作。

    讯飞绘文 网页版
    讯飞绘文 网页版

    讯飞绘文网页版是科大讯飞推出的AI图文创作与内容运营工具,覆盖热点选题、文章生成、稿件校对、智能配图、排版发布和数据复盘等环节,适合自媒体创作者及内容团队在线使用。

    Maya(Autodesk Maya) Windows版
    Maya(Autodesk Maya) Windows版

    Autodesk Maya 是面向影视、电视、动画和游戏行业的专业三维制作软件,集多边形与 NURBS 建模、角色绑定、关键帧和动作捕捉动画、Bifrost 特效模拟、材质开发及 Arnold 渲染于一体,

    Aperty Windows版
    Aperty Windows版

    Aperty 是 Skylum 推出的 AI 人像修图软件,支持自然肤质修饰、瑕疵处理、面部与身体调整、预设及批量同步。

    立刻MV 网页版
    立刻MV 网页版

    立刻MV 面向音乐人、内容创作者和品牌团队,帮助用户低成本完成歌曲 MV、歌词视频、AI 分镜、图生视频与最终合成。

    蛙蛙写作 网页版
    蛙蛙写作 网页版

    蛙蛙写作 AI 创作工具,覆盖小说、剧本、文案,一键生成文稿,打通文字转视频全流程,高效解决创作难题。

    超级简历WonderCV 网页版
    超级简历WonderCV 网页版

    超级简历WonderCV是面向应届生和AI小白的智能求职平台,覆盖简历、面试与职业规划。

    音述AI 网页版
    音述AI 网页版

    音述AI,是一个以“用声音述说故事”为核心的 AI 音乐创作与声音分享社区。

    AionClaw Windows版
    AionClaw Windows版

    AionClaw 是可在桌面端运行的任务型 AI 助手,通过数字专家与技能市场组合办公、创作、数据和开发能力。

    Loomy Windows版
    Loomy Windows版

    Loomy 是科大讯飞推出的桌面 AI 助手,可通过对话、任务与工作目录协助处理办公、内容创作和资料整理。