Quantum Algorithms for Lattice Problems

Original Article ↗ Hacker News Discussion ↗

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.