Skip to content

Back to the catalog

Further Elaborations on the Provable Dual Attack
eprint.iacr.orgpaper

Further Elaborations on the Provable Dual Attack

Further Elaborations on the Provable Dual Attack is an October 2026 ePrint paper by Kaveh Bashiri presenting a provable dual attack on LWE that recovers a subvector of the secret, with an explicit success-probability bound and no heuristic assumptions. It unifies the analyses of Pouly and Shen (EUROCRYPT 2024) and Bashiri and Wiemers (2025). Applied to ML-KEM it improves the first provable dual attack by 22 to 100 bits; it is also applied to ML-DSA and tested on small instances. The author states ML-KEM and ML-DSA are not threatened.

TL;DR Gives a fully provable LWE dual attack with explicit success bounds and tighter ML-KEM and ML-DSA cost estimates, without threatening either.
Open original ↗
Document

What it is

"Further Elaborations on the Provable Dual Attack" is a Cryptology ePrint paper (2026/2565, received 20 October 2026, approved 21 October 2026) by Kaveh Bashiri, who lists a BSI address. It is a preprint with no venue. It gives a dual attack on LWE that recovers a subvector of the secret, with an explicit lower bound on success probability and no heuristic assumptions.

How it works

The analysis merges the provable approaches of Pouly and Shen (EUROCRYPT 2024) and Bashiri and Wiemers (J. Math. Cryptol. 2025). It also removes the few informal assumptions those works still used.

Following Qu, Tian, Wang, and Xu (ePrint 2026/2117), the dual vectors are sampled from the sublattice spanned by the first vectors of a reduced basis. The key ingredient is a first-moment estimate for wrong candidates, based on the exact uniform distribution of some appearing cosets. This lets the paper drop the usual assumptions about shortest vectors.

Preconditions / Affected

The ML-KEM result needs one heuristic about its structured matrix. The size of the improvement depends on an assumption about the rank of the sublattice:

  • With no rank assumption, the attack improves on the first provable dual attack by 22 to 52 bits.
  • With the rank bounded as in Qu, Tian, Wang, and Xu, the improvement is 47 to 100 bits. Against that paper's own bounds the gain is 21 to 56 bits.

The paper also applies the method to ML-DSA and tests the attack on small instances.

Caveats

The author states that the results do not threaten the security of ML-KEM or ML-DSA. The gains are measured against earlier provable dual attacks, not against the best known heuristic attacks. The page gives no absolute bit-security figures, parameter-set breakdown or experiment sizes, so the abstract alone cannot show how close any parameter set comes to its target.

Organisations named here

  • Bashiri and Wiemers
  • Pouly and Shen
  • Qu, Tian, Wang, and Xu

Technologies named here

  • ML-KEM
  • ML-DSA
  • Learning-with-errors problem instances
  • NIST

Related in other