Quantum Algorithms for Lattice Problems

Original Article ↗ Hacker News Discussion ↗

A new paper briefly claimed the first polynomial-time quantum algorithm for key lattice problems underlying many post‑quantum cryptosystems, raising fears that popular schemes like LWE and Ring‑LWE could be fundamentally weakened. Commenters examined how the claimed algorithm’s parameter limits meant it would not immediately break NIST-standardized schemes such as CRYSTALS-Kyber, but stressed that even a theoretical shift from subexponential to polynomial behavior would be a major warning sign. An update from the author later acknowledged a critical bug that invalidates the central claim, easing immediate concerns while still highlighting how fragile current assumptions about quantum resistance can be.

Scope and Main Claim

  • Paper proposed the first polynomial‑time quantum algorithm for certain LWE/lattice problems.
  • Original excitement focused on changing the best‑known complexity from (sub)exponential to polynomial for a core hardness assumption in lattice‑based cryptography.

Limitations of the Attack

  • Authors state their algorithm does not break practical schemes like CRYSTALS‑Kyber:
    • Requires modulus q roughly ≥ n²; Kyber uses much smaller q relative to dimension n.
    • Only quantum‑polynomial time in parameter regimes not used by NIST PQC candidates.
  • Multiple commenters stress: current Kyber/Dilithium/NTRU/Falcon, etc., are not broken by this result as stated.

Significance and Future Risk

  • Some argue that moving from subexponential to polynomial in any regime is alarming; first constructions are rarely optimal, and improvements might eventually hit practical parameters.
  • Others respond that the new algorithm’s scope is narrow and parameter‑dependent, and that “best known attacks” language is always provisional in cryptography.

Impact on FHE and Non‑Lattice Schemes

  • Concern that some fully homomorphic encryption schemes (e.g., BFV) use very large moduli and might be more exposed if the technique generalizes.
  • Non‑lattice PQC options (code‑based such as Classic McEliece, others in NIST Round 4) are noted as important fallbacks.

NIST, NSA, and Hybrid Cryptography

  • Clarification that NIST is planning guidance on hybrid classical+PQC schemes but doesn’t mandate them; efficiency concerns favor pure PQC in large deployments.
  • NSA is said to be pushing for “PQC only.”
  • Some commenters strongly favor hybridization for safety; others mention worries about potential backdoors, while also presenting a more charitable view (uncertainty about interactions between schemes).

Quantum Computing Practicality

  • Long subthread debates how close scalable quantum computers are, the real factoring records, and noise/error‑correction limits.
  • Views range from “decades away” to “within 20 years,” with disagreements over how impressive current factoring demos are.

Paper Update / Bug

  • Later update (April 18): the author reports a bug in Step 9 that they cannot fix.
  • As a result, the claim of a polynomial‑time quantum algorithm for LWE with polynomial modulus‑noise ratios is explicitly withdrawn, though some techniques may remain of theoretical interest.