30 年来最重要的量子算法突破?
![图片](https://image.jiqizhixin.com/uploads/editor/1e15b1bb-2068-4c54-8ce1-52a269dab79f/640.png)
论文地址:https://eprint.iacr.org/2024/555.pdf 论文标题:Quantum Algorithms for Lattice Problems
它在科学上的意义将是双层的:第一,这将是自 30 年前 Peter Shor 提出大数分解的量子算法以来,最重要的量子算法突破。 第二,这将对美国 NIST 过去 10 年来选择后量子密码设计的思路产生颠覆性的影响,因为多数选出的后量子密码方案都是基于 Lattice Problems 或 LWE。陈一镭的工作无疑将使他们安全性受到质疑。
这篇论文提出的算法及分析极为新颖而深奥。回想 Wiles 1994 年解决费马大定理(Fermat's Last Theorem),以及 Perelman 2002 年解决庞佳莱猜想(Poincaré Conjecture)后,都经过一年以上专家们方能彻底认证其正确性。陈一镭的工作,预料也需要数月时间才能完成验证认可。我们静候科学界对此工作的后续反应。
![图片](https://image.jiqizhixin.com/uploads/editor/3cf83344-414f-4258-a5ce-52d5e8b00df7/640.png)
![图片](https://image.jiqizhixin.com/uploads/editor/707e3b91-1419-4fee-81f8-006cc1970629/640.png)
![图片](https://image.jiqizhixin.com/uploads/editor/f3ad51cd-f21c-4521-b04b-744e587895b4/640.png)
![图片](https://image.jiqizhixin.com/uploads/editor/6609fdfe-70b6-484a-b645-15ded6466f3e/640.png)
3.1 节展示了具有几个已知秘密坐标的 LWE 和标准 LWE 一样难; 3.2 介绍了将 LWE 转换成具有唯一最短向量的特殊 q-ary 格; 3.3 节列出了主要量子算法中使用的参数; 3.4 节概述了主要的量子算法; 3.5 节详细提供了主要量子算法的九个步骤,但将所有长度超过三页的证明推迟到第 3.6 节; 3.6 节提供了第 3.5 节中遗漏的所有详细证明。
![图片](https://image.jiqizhixin.com/uploads/editor/2722601e-7f83-4bc8-b23a-dbe2dfd691fe/640.png)
![图片](https://image.jiqizhixin.com/uploads/editor/44732b55-6ec1-4dfc-b4a1-808f2a91a42e/640.png)
![图片](https://image.jiqizhixin.com/uploads/editor/7bb57674-287d-42c5-996b-c3d1cded4334/640.png)
![图片](https://image.jiqizhixin.com/uploads/editor/e3256211-5fd8-4b26-8aab-d75391c0dc1c/640.png)
![图片](https://image.jiqizhixin.com/uploads/editor/75242919-da63-47ce-80d1-3082db681dc9/640.png)
![图片](https://image.jiqizhixin.com/uploads/editor/8adf4a4b-78ab-4ec8-92b5-fb52d0378a7a/640.png)
![图片](https://image.jiqizhixin.com/uploads/editor/a7ecd50d-23d6-4cb9-b512-3db5d2d11950/640.png)
![图片](https://image.jiqizhixin.com/uploads/editor/9498c880-ae24-4104-9f87-468436fa97b8/640.png)
![图片](https://image.jiqizhixin.com/uploads/editor/7231b25b-9d6d-4df6-b2cc-bec2540157d9/640.png)
![图片](https://image.jiqizhixin.com/uploads/editor/8cb9da17-ef07-4140-9882-79d394dad999/640.png)
![图片](https://image.jiqizhixin.com/uploads/editor/bba33ba3-5035-4bc6-b614-6a7546e87576/640.png)
![图片](https://image.jiqizhixin.com/uploads/editor/a9bf4e13-c8a8-435c-8f07-fd3e3f58a8c3/640.png)
![图片](https://image.jiqizhixin.com/uploads/editor/43840f43-e25f-42cb-888f-b9a5eec65e09/640.png)
![图片](https://image.jiqizhixin.com/uploads/editor/3a1e4c5e-25a0-4569-8260-d6ad5c91c860/640.png)
![图片](https://image.jiqizhixin.com/uploads/editor/e68405f6-f61e-4bea-beac-c90c0da4c1d3/640.png)
![图片](https://image.jiqizhixin.com/uploads/editor/86592018-2280-4c72-8521-13310edc8962/640.png)
![图片](https://image.jiqizhixin.com/uploads/editor/fed99621-75f2-48f0-b689-5957b77799b0/640.png)
![图片](https://image.jiqizhixin.com/uploads/editor/53325385-fd1f-43ac-bade-a28e1bfb0ee2/640.png)
![图片](https://image.jiqizhixin.com/uploads/editor/a29d83a8-4f03-422a-8c93-9c1a37bd3c2f/640.png)
![图片](https://image.jiqizhixin.com/uploads/editor/7184c4be-8c18-4c34-a27f-5a34d87988bf/640.png)
![图片](https://image.jiqizhixin.com/uploads/editor/df44531d-e9a0-48fc-8251-278f9222c875/640.png)
![图片](https://image.jiqizhixin.com/uploads/editor/e791869d-e095-4dbd-aa26-81601295589c/640.png)
![图片](https://image.jiqizhixin.com/uploads/editor/510bb8a8-fb92-43f7-a1b4-80f6a9d48eeb/640.png)
![图片](https://image.jiqizhixin.com/uploads/editor/2ac4b9c8-c772-4a1e-b1b3-51a24bebc6c9/640.png)
![图片](https://image.jiqizhixin.com/uploads/editor/a1f1117f-bec3-4c1c-b0d3-c4586918d44a/640.png)
![图片](https://image.jiqizhixin.com/uploads/editor/dd676f3d-c4d1-4b74-aac6-cfb28c391ecc/640.png)
![图片](https://image.jiqizhixin.com/uploads/editor/1b1439a1-3c38-42be-9ba5-e78d9feeb9bc/640.png)
![图片](https://image.jiqizhixin.com/uploads/editor/34e84ca1-f445-43ef-ad0c-bed2b7f4a98f/640.png)
![图片](https://image.jiqizhixin.com/uploads/editor/c76dfd52-9d5d-4d80-8f3e-130ca3ceb933/640.png)
![图片](https://image.jiqizhixin.com/uploads/editor/b4891860-8b8f-46a7-a0e0-71aaad297386/640.png)
![图片](https://image.jiqizhixin.com/uploads/editor/905abf9a-937e-4c3a-ba8f-73e235b252f9/640.png)
![图片](https://image.jiqizhixin.com/uploads/editor/83774aac-fb5d-4323-ad89-d61f434f7b63/640.png)