A quick post on Chen’s algorithm

Update (April 19): Yilei Chen announced the discovery of a bug in the algorithm, which he does not know how to fix. This was independently discovered by Hongxun Wu and Thomas Vidick. At present, the paper does not provide a polynomial-time algorithm for solving LWE.
更新（4 月 19 日）：陈一磊宣布在算法中发现了一个错误，他不知道如何修复。这是由吴鸿勋和托马斯·维迪克独立发现的。目前，该文尚未提供用于求解LWE的多项式时间算法。

If you’re a normal person — that is, a person who doesn’t obsessively follow the latest cryptography news — you probably missed last week’s cryptography bombshell. That news comes in the form of a new e-print authored by Yilei Chen, “Quantum Algorithms for Lattice Problems“, which has roiled the cryptography research community. The result is now being evaluated by experts in lattices and quantum algorithm design (and to be clear, I am not one!) but if it holds up, it’s going to be quite a bad day/week/month/year for the applied cryptography community.
如果你是一个普通人——也就是说，一个不痴迷于关注最新密码学新闻的人——你可能错过了上周的密码学重磅炸弹。这一消息以陈一磊撰写的新电子印刷品“晶格问题的量子算法”的形式出现，该印刷品扰乱了密码学研究界。现在，晶格和量子算法设计方面的专家正在评估这一结果（需要明确的是，我不是其中之一！），但如果它成立，对于应用密码学社区来说，这将是一个相当糟糕的一天/一周/一个月/一年。

Rather than elaborate at length, here’s quick set of five bullet-points giving the background.
与其详细阐述，不如快速列出五个要点，给出背景。

(1) Cryptographers like to build modern public-key encryption schemes on top of mathematical problems that are believed to be “hard”. In practice, we need problems with a specific structure: we can construct efficient solutions for those who hold a secret key, or “trapdoor”, and yet also admit no efficient solution for folks who don’t. While many problems have been considered (and often discarded), most schemes we use today are based on three problems: factoring (the RSA cryptosystem), discrete logarithm (Diffie-Hellman, DSA) and elliptic curve discrete logarithm problem (EC-Diffie-Hellman, ECDSA etc.)
（1）密码学家喜欢在被认为是“困难”的数学问题之上构建现代公钥加密方案。在实践中，我们需要具有特定结构的问题：我们可以为那些拥有密钥或“活板门”的人构建有效的解决方案，但对于那些没有密钥的人，我们也承认没有有效的解决方案。虽然已经考虑了许多问题（并且经常被丢弃），但我们今天使用的大多数方案都基于三个问题：因式分解（RSA 密码系统）、离散对数（Diffie-Hellman，DSA）和椭圆曲线离散对数问题（EC-Diffie-Hellman，ECDSA 等）。

(2) While we would like to believe our favorite problems are fundamentally “hard”, we know this isn’t really true. Researchers have devised algorithms that solve all of these problems quite efficiently (i.e., in polynomial time) — provided someone figures out how to build a quantum computer powerful enough to run the attack algorithms. Fortunately such a computer has not yet been built!
（2）虽然我们愿意相信我们最喜欢的问题从根本上说是“困难的”，但我们知道这并不是真的。研究人员已经设计出能够非常有效地解决所有这些问题的算法（即在多项式时间内）——前提是有人弄清楚如何构建一台足够强大的量子计算机来运行攻击算法。幸运的是，这样的计算机还没有建成！

(3) Even though quantum computers are not yet powerful enough to break our public-key crypto, the mere threat of future quantum attacks has inspired industry, government and academia to join forces Fellowship-of-the-Ring-style in order to tackle the problem right now. This isn’t merely about future-proofing our systems: even if quantum computers take decades to build, future quantum computers could break encrypted messages we send today!
（3）尽管量子计算机还不够强大，无法破解我们的公钥加密，但未来量子攻击的威胁已经激发了工业界、政府和学术界联合起来，以解决这个问题。这不仅仅是为了让我们的系统面向未来：即使量子计算机需要几十年的时间来构建，未来的量子计算机也可以破解我们今天发送的加密信息！

(4) One conspicuous outcome of this fellowship is NIST’s Post-Quantum Cryptography (PQC) competition: this was an open competition designed to standardize “post-quantum” cryptographic schemes. Critically, these schemes must be based on different mathematical problems — most notably, problems that don’t seem to admit efficient quantum solutions.
（4）该奖学金的一个显着成果是NIST的后量子密码学（PQC）竞赛：这是一项旨在标准化“后量子”密码学方案的公开竞赛。至关重要的是，这些方案必须基于不同的数学问题——最值得注意的是，这些问题似乎不允许有效的量子解决方案。

(5) Within this new set of schemes, the most popular class of schemes are based on problems related to mathematical objects called lattices. NIST-approved schemes based on lattice problems include Kyber and Dilithium (which I wrote about recently.) Lattice problems are also the basis of several efficient fully-homomorphic encryption (FHE) schemes.
（5）在这组新的方案中，最流行的一类方案是基于与称为格的数学对象相关的问题。NIST批准的基于晶格问题的方案包括Kyber和Dilithium（我最近写过）。晶格问题也是几种高效的全同态加密（FHE）方案的基础。

This background sets up the new result.
此背景设置了新结果。

Chen’s (not yet peer-reviewed) preprint claims a new quantum algorithm that efficiently solves the “shortest independent vector problem” (SIVP, as well as GapSVP) in lattices with specific parameters. If it holds up, the result could (with numerous important caveats) allow future quantum computers to break schemes that depend on the hardness of specific instances of these problems. The good news here is that even if the result is correct, the vulnerable parameters are very specific: Chen’s algorithm does not immediately apply to the recently-standardized NIST algorithms such as Kyber or Dilithium. Moreover, the exact concrete complexity of the algorithm is not instantly clear: it may turn out to be impractical to run, even if quantum computers become available.
Chen（尚未经过同行评审）的预印本声称一种新的量子算法，该算法可以有效地解决具有特定参数的晶格中的“最短独立向量问题”（SIVP以及GapSVP）。如果它成立，结果可能（有许多重要的警告）允许未来的量子计算机打破依赖于这些问题的特定实例的硬度的方案。好消息是，即使结果是正确的，易受攻击的参数也非常具体：Chen的算法并不能立即应用于最近标准化的NIST算法，如Kyber或Dilithium。此外，该算法的确切具体复杂性尚不清楚：即使量子计算机可用，它也可能被证明是不切实际的。

But there is a saying in our field that attacks only get better. If Chen’s result can be improved upon, then quantum algorithms could render obsolete an entire generation of “post-quantum” lattice-based schemes, forcing cryptographers and industry back to the drawing board.
但是在我们的领域有一句话，攻击只会变得更好。如果Chen的结果能够得到改进，那么量子算法可能会使整整一代基于“后量子”晶格的方案过时，迫使密码学家和工业界回到绘图板。

In other words, both a great technical result — and possibly a mild disaster.
换句话说，这既是一个伟大的技术成果，也可能是一场轻微的灾难。

As previously mentioned: I am neither an expert in lattice-based cryptography nor quantum computing. The folks who are those things are very busy trying to validate the writeup: and more than a few big results have fallen apart upon detailed inspection. For those searching for the latest developments, here’s a nice writeup by Nigel Smart that doesn’t tackle the correctness of the quantum algorithm (see updates at the bottom), but does talk about the possible implications for FHE and PQC schemes (TL;DR: bad for some FHE schemes, but really depends on the concrete details of the algorithm’s running time.) And here’s another brief note on a “bug” that was found in the paper, that seems to have been quickly addressed by the author.
如前所述：我既不是基于格的密码学专家，也不是量子计算方面的专家。那些做这些事情的人非常忙于验证这篇文章：在详细检查后，许多重大结果已经分崩离析。对于那些寻找最新发展的人来说，这里有一篇不错的文章，作者 Nigel Smart 没有解决量子算法的正确性（见底部的更新），但确实谈到了对 FHE 和 PQC 方案的可能影响（TL;DR：对某些 FHE 方案不利，但实际上取决于算法运行时间的具体细节。这是关于论文中发现的“错误”的另一个简短说明，作者似乎很快就解决了这个问题。

Up until this week I had intended to write another long wonky post about complexity theory, lattices, and what it all meant for applied cryptography. But now I hope you’ll forgive me if I hold onto that one, for just a little bit longer.
直到本周，我还打算再写一篇关于复杂性理论、格子以及它对应用密码学意味着什么的长篇文章。但现在我希望你能原谅我，如果我再坚持一会儿。