Paper 2025/869

One for All, All for One: Universal semi-agnostic quantum circuit for solving (Standard) Abelian Hidden Subgroup Problems

Abstract

Quantum algorithms for factoring, finite-field discrete logarithms (DLP), and elliptic-curve discrete logarithms (ECDLP) are usually presented as three separate attack pipelines, even though all three are instances of the Abelian Hidden Subgroup Problem (AHSP). We prove that the semi-agnostic elliptic-curve discrete logarithm problem (semi-agnostic ECDLP), defined on smooth elliptic curves, singular nodal cubics, and over rings such as $\mathbb{Z}_N$, is complete for all standard abelian hidden subgroup problems (SAHSPs). In other words, factoring, finite-field DLP, and ECDLP all reduce to semi-agnostic ECDLP. This gives the first completeness theorem for the cryptographic subclass of HSP. To argue minimality from the practical point of view (for example, the minimal size of Shor's circuit implementation), we formalize the No Efficient Injective Homomorphism (NEIH) hypothesis: no generic polynomial-time injective homomorphism exists from elliptic curve subgroups into small cyclic groups. NEIH is strongly supported by three provable limitations: (i) the embedding-degree barrier, (ii) an algebraic rigidity lemma, and (iii) a generic-group model barrier, ruling out non-algebraic embeddings without already solving the ECDLP. The completeness result has practical implications, as it identifies a minimal universal Shor engine: a single, programmable Weierstrass circuit that implements reversible field arithmetic and point addition on a smooth or nodal Weierstrass model. This one circuit instance suffices to execute Shor's algorithm for factoring, finite-field DLP, and ECDLP without recompilation and with the same asymptotic resources as specialized designs.

Note: Revised version