A Fourier-Label Information-Loss Barrier for Dihedral Coset Algorithms
Aparna Gupte, Seyoon Ragavan, Mark Zhandry
quant-ph
Sep 30, 2026 · v1
cs.CR
TL;DR
Releases Lean 4 code formalizing the no-go theorem for Fourier-label-discarding dihedral coset algorithms, to aid verifiability.
Abstract
We establish a no-go theorem for a broad class of quantum algorithms for the dihedral coset problem (DCP). We consider the Fourier-sampling and subset-sum-measurement template proposed by Regev (SIAM Journal on Computing, 2004), which is one of the main approaches to solving DCP. Suppose that, after measuring the lower $n-1$ bits of the subset sum, the algorithm discards any $ω(\log n)$ bits from each of the Fourier labels. Then we prove that the algorithm cannot succeed in solving DCP. This shows that any algorithm following this template must make extensive use of the Fourier labels, and thus serves as a useful guide for developing algorithms for DCP. As a main application, we show that the recent algorithm by Simon (IACR ePrint:2026/1591, August 11 2026) does not solve DCP. We show that after the subset-sum measurement, this algorithm can be implemented (up to exponentially-small error) using only the most-significant third of the Fourier labels, and is therefore subject to our general no-go theorem. To help with verifiability, we release Lean 4 code for our results.
Problem
Regev's Fourier-sampling and subset-sum-measurement template is a main approach to the dihedral coset problem (DCP), whose efficient solution would break lattice-based cryptography. A recent algorithm by Simon claims a quantum polynomial-time DCP algorithm within this template, and it needs to be assessed.
Approach
The authors prove a no-go theorem: if, after measuring the lower n-1 bits of the subset sum, an algorithm discards ω(log n) bits of each Fourier label, it cannot solve DCP. The proof bounds the trace distance between the algorithm's state and states with dephased control registers, using trace-norm and averaging lemmas. They then show that Simon's algorithm can be simulated, up to exponentially small error, using only the most-significant third of the Fourier labels. Lean 4 code for the results is released.
Results
Any algorithm following the template must make extensive use of the Fourier labels. As a corollary, Simon's algorithm does not solve DCP and so does not threaten lattice-based cryptosystems.
