The world needs codes quantum computers can’t break 世界需要不会被量子计算机破解的密码

type

status

date

The world needs codes quantum computers can’t break 世界需要不会被量子计算机破解的密码

Aug 21st 2024

QUANTUM COMPUTERS, which exploit strange properties of the subatomic realm to crunch numbers in powerful new ways, do not actually work yet. But if and when they do start working, they will be able to break the cryptographic algorithms that currently protect online communications, financial transactions, medical records and corporate secrets.

量子计算机开创了在亚原子领域这一陌生领域进行高效计算的一种高效新方式，但是实际上它们还未投入使用。但是如果他们投入使用后，它们将有能力破译当前所有用于保护在线通信的加密算法。（包括金融交易、医疗纪录、公司机密。） quantum n. 量子 realm n. 领域 transaction n. 交易；业务

Today’s algorithms generally rely on the fact that conventional computers struggle to factorise very large numbers. Finding the factors of the big numbers used by the RSA-2048 algorithm, for example, often used as a benchmark for progress in the field, has eluded generations of classical computers. But experts believe a quantum computer could emerge within a decade or two capable of cracking it in a day. That is already making cryptographers nervous. Sensitive data illicitly obtained today could be held on ice for years, until a sufficiently powerful code-breaker is built.

当今的算法通常以这样一个事实为基础：传统的计算机很难分解非常大的数。例如，找到 RSA-2048 算法中所使用的大数的因子一直以来作为这个领域发展的一个基准点，难倒了一代又一代的传统计算机。但是，专家相信在未来的十年到二十年间将会出现一台量子计算机可以在一天内解出它，这已经造成了加密者的焦虑。今天非法获取到的敏感数据将会被保留多年直到出现一种足够强大的解密工具被构建出来。 generally adv. 通常地；一般地 struggle to + v. 表示某人或某物努力去做某事 factorise adj. 因数的；阶乘的；阶乘｜ v. 因式分解 benchmark n. 基准点 elude v. 躲避；把（某人）难倒 within a decade or two capable of 在十年到二十年间 crack n. 裂缝；裂纹｜ v. 打击；使崩溃 illicit adj. 非法的 be held on ice 将某物保留或搁置一段时间

New algorithms are therefore needed. And because switching over to them will take years, the transition to post-quantum cryptography (PQC) needs to begin as soon as possible. The National Institute of Standards and Technology (NIST), America’s standards agency, has now fired the starting gun for this transition. On August 13th NIST announced that three algorithms had been approved as official standards for PQC. Two are based on lattice problems, a type of mathematical puzzle challenging for quantum and classical computers alike. The third, which is based on the hash functions used in data analysis, avoids having too many eggs in a single basket.

所以新的加密算法是被需要的。并且由于现有算法替换成它们需要一些时间，所以需要尽可能快地开始将加密算法替换为后量子加密算法这一进程。美国的权威机构国家标准与技术研究院开启了这个转换的第一枪。在八月13日，美国国家标准与技术研究院宣告三个官方权威的后量子加密算法已经出现。其中有两个算法基于格问题（一种数学难题，困扰着经典及量子计算机）。另外一个算法基于一个曾用于数据分析的哈希函数，避免将太多鸡蛋放在同一个篮子里。

Chart: The Economist 不方便分布分布分布分布分布分布分布分布分布分布分布分布分布分布分布分布分布分布分布分布分布分布分布分布分布分布分布分布分布分布分布分布分布分布分布分布分布分布分布分布分布分布分布分布分布分布分布分布分布c n j n j d n c j d n c j d n c j d n c j d n c j d n c j d n j c n d。行行行行行行

The announcement marks an important step in a continuing process. NIST began looking for quantum-safe algorithms in 2016, when it launched a competition for codes that future quantum computers would be unable to crack. Dozens of algorithms were submitted, mathematicians and cryptographers did their best to pick holes in them, and many fell by the wayside. Eventually, in July 2022, NIST announced a shortlist of four algorithms that were candidates for standardisation. Three of them were based on lattice problems. The fourth involved hash functions.

这则宣告标志着继续这一进程的重要一步。美国国家标准与技术研究院于2016年开始探索量子安全算法，并且发起了一项竞赛，目的是寻找未来的量子计算机无法破解的代码。数量众多的算法被参赛者所提交，数学家和密码学家竭尽全力挑出其中的漏洞，许多算法被淘汰了。终于，在2022年七月，美国国家标准与技术研究院公布了最后候选名单——有四个算法成为标准化的候选。其中有三个基于格问题，另外一个涉及哈希函数。 Dozens of 字面意思是“几十个”，但在实际使用中，通常只是用来强调数量的多。 pick holes 挑毛病 wayside n. 路边 shortlist n. 最后候选人名单｜ v. 把…列入最后候选人名单 standardisation n. 标准化

NIST also said it would continue to evaluate four backup algorithms, some of which might be adopted as standards in future. That is because nobody can ever be sure how secure an algorithm really is; there is always a risk somebody might discover a clever way to crack it. NIST consequently chose backup algorithms that did not rely on lattices. One of these, called SIKE, is based on the mathematics of isogeny-based elliptic curves. Elliptic curves are already used in some cryptographic systems today, but are not considered quantum-safe. Isogeny-based elliptic curves, it was thought, would be.

美国国家标准与技术研究院声称将会继续迭代优化四个备用算法，它们中的一些将会在未来被采纳而作为标准。因为没有人能确定一种算法有多安全。总是存在可能有人发现一种巧妙的方法来破解它的风险。美国国家标准与技术研究院最终选择了不依赖格问题的备用算法。其中一种备选算法叫做 SIKE，基于同源性椭圆曲线的数学原理。如今，椭圆曲线已用于一些加密系统，但是通常不被认为是量子安全的。而基于同源性椭圆曲线的算法，则被认为可能是量子安全的。 isogeny n. 同源 elliptic adj. 椭圆形的；简略的 curves n. 曲线｜ v. 沿曲线运动

Wrongly, as it turned out. In July 2022 Wouter Castryck and Thomas Decru, mathematicians at Katholieke Universiteit Leuven in Belgium, announced that they had found a way to crack SIKE. Worse still, their method could unlock data encrypted by SIKE in just four minutes, using a ten-year-old desktop PC. Fortunately, SIKE was the only example of an isogeny-based elliptic-curve cryptosystem under consideration by NIST, so this result did not imperil any other algorithms. Cue a big sigh of relief, and SIKE’s removal from the list of contenders for PQC.

事实证明，这是错误的。2022 年 7 月，Belgium 的 Katholieke 大学的数学家 Wouter Castryck 和 Thomas Decru 宣布他们找到了一种破解 SIKE 的方法。更糟糕的是，他们的方法可以在短短四分钟内使用一台十年前的台式电脑解开由 SIKE 加密的数据。幸运的是，SIKE 是 NIST 正在考虑的唯一基于同源的椭圆曲线密码系统的例子，因此这个结果不会危及任何其他算法。这让人松了一口气，SIKE 从 PQC 竞选人名单中移除了。 as it turned out 结果显示；事实证明 worse still 更糟糕的是 imperil v. 危及；使陷于危险 Cue a big sigh of relief 长舒一口气（如释重负）

Then in April 2024 came another unexpected result. Yilei Chen, of Tsinghua University in Beijing, issued a paper detailing a quantum algorithm that could solve certain lattice problems. This suggested that algorithms based on such problems might, after all, be vulnerable to quantum attack. Given that three out of four of NIST’s preferred algorithms were of this type, this was a potentially disastrous finding. Fortunately, a flaw was found in the paper almost immediately, and cryptographers sighed with relief once again.

在2024年4月出现了另外一个意料之外的结果。Beijing 的 Tsinghua 大学的 Yilei Chen 发表了一篇论文详细叙述了一种能够解决特定格问题的量子算法。这表明了基于此类问题的算法最终可能会受到量子攻击的威胁。美国国家标准与技术研究院首选的四种算法中的三种都是属于这一类型，这是潜在灾难的发现。幸运的是，这篇论文几乎立即被发现存在一个缺陷，加密学家再次松了一口气。 vulnerable adj. 脆弱的；易受伤的 after all 毕竟；终究 flaw n. 瑕疵｜ v.使有缺陷；使有裂痕 almost immediately 几乎立即 sigh v. 叹气｜ n. 叹息；叹气

One of NIST’s approved lattice-based algorithms, ML-KEM, is a method for distributing secret encryption keys, which allow the right recipient to decrypt the scrambled data. The other, ML-DSA, is an algorithm for digital signatures, a technique that allows users to prove their identity.

美国国家标准与技术研究院认可的基于格问题的算法之一， ML-KEM，是一种用于分发密钥的方法，这些密钥可以让正确的接收者解密被加密的数据。另外一个算法叫 ML-DSA，它基于数字签名，这项技术允许用户证明其身份。 recipient n. 接受者；容器｜ adj. 容易接受的 scramble v. 攀登；争抢；混杂｜ n. 攀登；争夺；混乱

The third approved algorithm, SLH-DSA, is an alternative to ML-DSA based on a hash-based algorithm—“to avoid relying only on the security of lattices”, NIST explained. NIST will also continue to evaluate a trio of other algorithms, reliant on neither lattices nor elliptic curves, as possible alternatives to ML-KEM. They are thought to be highly secure, but require more storage space for encryption keys and enciphered data than ML-KEM does.

美国国家标准与技术研究院（NIST）解释道，第三个被认可的算法，SLH-DSA是以哈希为基础的算法，是 ML-DSA 算法的替代方案——“避免仅仅依靠格问题的安全性” 。美国国家标准与技术研究院（NIST）将持续评估另外三种算法，这些算法既不依赖于格问题也不依赖于椭圆曲线。作为 ML-KEM 的可能替代算法，它们被认为相比于 ML-KEM 算法是高安全性的，但是需要更多的空间来储存密钥和加密后的数据。 trio n. 三人一组；三重奏 a trio of 三个；三人组 reliant adj. 信任的；依靠的 encipher v. 把…译成密码

There is strength in such diversity. The scare over Dr Chen’s paper highlighted the fact that there has not been enough analysis of lattice-based systems to be confident of their security, notes Bruce Schneier, a cryptography guru at Harvard University. People have tried and failed to break lattice-based algorithms with conventional computers for decades, but there has been much less research into how they might be broken using a quantum computer. Adoption of the new NIST standards should go ahead, he says, but large organisations should aim to be “crypto-agile” as they switch to PQC. That means switching in a way that facilitates further switches in future, as better algorithms become available, or flaws are found in existing ones.

多样性中存在优势。Dr Chen 的论文引发的恐慌显示出了一个事实，人们对基于格问题的系统的分析还不够充分，无法信任其安全性，Harvard 大学权威的密码学家 Bruce Schneier 指出。他说，近十年人们使用传统计算机尝试并失败求解格问题算法，但是只有更少的研究认为它们被量子计算机所破解。采纳美国国家标准与技术的标准应该提前，但是组织机构需要以“灵活加密”的方式来转向后量子加密。这意味着要以一种更便于以后进行进一步转换的方式（无论是有更好的算法出现，还是现有算法被发现存在缺陷）来进行转换， guru n. 领袖；专家；权威 agile adj. 敏捷的；灵活的

The work underpinning a successful transition has been under way for some time, says Scott Crowder, a quantum specialist at IBM, a computing giant. IBM has made a PQC software update for its Z series mainframe computers, for example, which are still widely used in many industries. Similarly, earlier this year Apple implemented ML-KEM on the iMessage service used on its iPhones, iPads and Macs.

For a typical large company, says Mr Crowder, 80% of the job of switching to PQC will be handled by vendors providing upgrades and patches. The other 20% is more difficult, requiring companies to rejig custom-built internal systems.

计算机行业巨头 IBM 的量子专家 Scott Crowder 表示，在成功转换的基础上的工作已经进行了一段时间。例如，IBM 为其 Z 系列主机进行了 PQC 软件更新，这些主机仍被广泛应用于许多行业。同样，今年早些时候，苹果在其 iPhone、iPad 和 Mac 的 iMessage 服务上使用了ML-KEM。Mr Crowder 表示，对于一个典型的大公司来说，切换到 PQC 的工作量中，有 80% 将由供应商通过升级和补丁来处理。而剩下的 20% 则更困难，需要公司重新调整其定制的内部系统。 underpin n. 基础；支柱｜ v. 加强…的基础；巩固；支持 series n. 连续；系列 mainframe n. 主机 industry n. 行业；工业 vendor n. 小贩；卖主 rejig v. 重新组织；重新安排 custom-built adj. 定制的

One approach, which can ease the transition and also provide extra reassurance, is known as “hybrid” or “composite” cryptography. This involves layering existing, conventional cryptography with PQC. That way, if either system is broken, the other still provides some protection. This can act as an insurance policy for organisations required by regulators to adopt PQC but worried that it may not be totally secure.

The possibility still exists that flaws will be found in NIST’s new standards. But that is no reason to delay. The transition will not be easy, and will not be risk-free. But the time to start is now. ■

一种既能简化过渡过程又能提供额外保障的方法被称为“混合”或“复合”加密。这涉及到叠加已经存在的传统的加密和 PQC。这种方式，即使一个系统被破坏，另外一个仍将提供一些防护。这可以作为一种保险策略，适用于那些被监管机构要求将为采纳 PQC 但是又担心其不完全安全的组织。在 NIST 的新标准中仍然有可能发现缺陷。但这不是推迟的理由。转型过程将不会轻松，也不会没有风险。但是，现在正是开始的时机。 one approach 一种方法 ease v. 缓解；减轻｜ n. 安逸；轻松 reassurance n. 再保证；使放心；使安慰 hybrid n. 混合物；杂交种｜ adj. 杂种的；混合的 composite adj. 合成的；复合的｜ n. 合成物；复合物 regulator n. 调节器；监管者