W kwietniu 2024 społeczność zajmująca się kryptografią i bezpieczeństwem została poruszona nowymi badaniami Yilei Chena. jeżeli te wyniki by się utrzymały, mogłoby to to potencjalnie wpłynąć na bezpieczeństwo stosowanej kryptografii, zwłaszcza w erze komputerów kwantowych. Praca ta była bardzo trudna do zrozumienia ze względu na jej złożoność. Została już wycofana po znalezieniu błędu. Czyli się nie utrzymało. Możemy jednak wyciągnąć z tego naukę.
"Update on April 18: Step 9 of the algorithm contains a bug, which I don’t know how to fix. See Section 3.5.9 (Page 37) for details. I sincerely thank Hongxun Wu and (independently) Thomas Vidick for finding the bug today. Now the claim of showing a polynomial time quantum algorithm for solving LWE with polynomial modulus-noise ratios does not hold."
Nasze systemy szyfrowania z kluczem publicznym są zbudowane na problemach matematycznych, które z założenia są trudne do rozwiązania bez tajnego klucza (tj. łatwo je zaszyfrować, trudno odszyfrować), takich jak te używane w RSA lub systemach opartych na krzywych eliptycznych. Bezpieczeństwo całego Internetu zależy od tego, czy ta kryptografia zachowuje siłę. Wiemy jednak, iż komputery kwantowe mogą pewnego dnia podważyć to bezpieczeństwo. To właśnie zmotywowało prace nad algorytmami post-kwantowymi, które są w tej chwili standaryzowane, a także testowane / wdrażane przez duże firmy technologiczne.
Nowe schematy obejmują te oparte na problemach sieciowych (lattice problems; np. NTRU, Kyber, Dilithium). Działają one w oparciu o podobne podstawowe założenie, jak te obecnie: szyfrowanie jest proste, a odszyfrowanie trudne (niemożliwe, jeżeli nie masz klucza). Struktura matematyczna tych rozwiązań jest jednak zupełnie inna.
Chociaż choćby postęp, o którym mowa w wycofanym już artykule, nie złamał ich bezpośrednio, można powiedzieć, iż nieco zmniejszał poczucie bezpieczeństwa (gdyby się utrzymał). Innymi słowy: nie tak miało być, a przynajmniej nie tak szybko. Co więcej, jeżeli te schematy zostałyby złamane, migracja do nich byłaby bezcelowa. A migracja postępuje i tego wymaga się choćby prawnie, w USA i w Unii Europejskiej.
Kwestia ta podkreśla ciągły rozwój i wyzwania w kryptografii, na które duży wpływ będzie miał przyszły rozwój algorytmów kwantowych. Musimy to obserwować.
