Quantum Inversion of Units in Group Rings: Block Dimension, Not Commutativity, Governs Hardness
Abstract
Several public-key schemes base their security on the belief that inverting a unit of a group ring is hard. A recent result showed that this belief is false on a quantum computer when the group is abelian. To restore security, designers moved to non-abelian groups, especially dihedral groups, believing that the hardness of the dihedral hidden subgroup problem (HSP) would protect the scheme. This paper shows that unit inversion is a different problem and does not require an HSP solver. Instead, it can be solved by a change of basis that splits the group ring into small matrix blocks. We prove that unit inversion is polynomial-time, classically and quantumly, when an efficient generalized Fourier transform exists, the group ring is semisimple, and the largest matrix block has polynomial size. Dihedral group rings satisfy these conditions because their irreducible representations have dimension at most 2 and an efficient Fourier transform exists. We give an explicit reversible quantum circuit for the block-inversion step and validate it in a register-level simulator. We also identify the exact structural boundary where the method stops and propose a candidate construction in the surviving regime under a new, clearly stated security assumption. The constructive results are supported by reproducible software artifacts and experiments.
Related
- The Quantum Overlap Gap Property and Algorithmic Hardness for the Quantum Hypergraph Max-Cut Problem
- On Certifying Source Sampling Hardness in Quantum Generative Modeling
- Hardness of Approximating Quantum Code Distance Beyond √N
- Structured Quantum Hardness from Unstructured Assumptions
- Encoding universal quantum computation into quantized Berry phases: Hardness results and classical algorithms
BibTeX
@misc{gupta2026quantum,
title = {{Quantum Inversion of Units in Group Rings: Block Dimension, Not Commutativity, Governs Hardness}},
author = {Bhanwar Gupta},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.10596},
eprint = {2609.10596},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.10596},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Quantum Inversion of Units in Group Rings: Block Dimension, Not Commutativity, Governs Hardness
AU - Bhanwar Gupta
PY - 2026
DA - 2026/09/07
PB - arXiv
DO - 10.48550/arxiv.2609.10596
UR - https://arxiv.org/abs/2609.10596
AB - Several public-key schemes base their security on the belief that inverting a unit of a group ring is hard. A recent result showed that this belief is false on a quantum computer when the group is abelian. To restore security, designers moved to non-abelian groups, especially dihedral groups, believing that the hardness of the dihedral hidden subgroup problem (HSP) would protect the scheme. This paper shows that unit inversion is a different problem and does not require an HSP solver. Instead, it can be solved by a change of basis that splits the group ring into small matrix blocks. We prove that unit inversion is polynomial-time, classically and quantumly, when an efficient generalized Fourier transform exists, the group ring is semisimple, and the largest matrix block has polynomial size. Dihedral group rings satisfy these conditions because their irreducible representations have dimension at most 2 and an efficient Fourier transform exists. We give an explicit reversible quantum circuit for the block-inversion step and validate it in a register-level simulator. We also identify the exact structural boundary where the method stops and propose a candidate construction in the surviving regime under a new, clearly stated security assumption. The constructive results are supported by reproducible software artifacts and experiments.
ER -