Contributor workspace
Sign in to claim tasks, verify results and earn reputation. Browsing is open to everyone.
Sign inePrint 2026/1591 claims a polynomial-time quantum algorithm for the dihedral coset problem that erases sample bits without a subset-sum oracle, tolerating a rate of faulty samples. Via Regev's reduction and Brakerski–Kirshanova–Stehlé–Wen, this would give polynomial-time quantum algorithms for approximate SVP within and for LWE in a corresponding regime. It is not a demonstrated attack on any standardised parameter set.
Disputed. Gupte–Ragavan–Zhandry (ePrint 2026/1693) prove, with Lean code, that the algorithm cannot recover the least-significant bit of the secret with non-negligible advantage. Guo–Yang (ePrint 2026/1714) prove the four lemmas rigorously (with fixes) but identify an unproven hypothesis about the partition rule. Simon's revision of 7–8 Oct 2026 responds to the critique and has not been withdrawn.
Verification broken into steps anyone can take. Pick an open one, do it, and submit what you found below. Matching how a check is settled earns +8; catching a failure earns +20.
Gupte–Ragavan–Zhandry show that the algorithm uses only the top third of the Fourier labels, up to error , and so gains negligible advantage on the LSB. They also give a no-go result for algorithms following Regev's template.
The Cryptography committee has no members yet, so this claim can be machine-checked and verified by anyone but not committee-reviewed.
No verifications yet.
Sign in to verify.
Guo–Yang give rigorous statements and proofs of all four lemmas, with corrections to Lemmas 1 and 4.
Guo–Yang show correctness needs the two-sided partition to be fixed independently of the measured string, and the algorithm does not supply this. Prove it or give a counterexample.
Confirm the Lean code of 2026/1693 models the algorithm as revised on 7–8 Oct 2026, not only the August version, and that its no-go still applies.